1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| from random import randint
from os import urandom
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from hashlib import sha1
from typing import Tuple
class Ellipse:
"""Represents the curve x^2 + ay^2 = 1 mod p"""
def __init__(self, a: int, p: int):
self.a = a
self.p = p
def __repr__(self) -> str:
return f"x^2 + {self.a}y^2 = 1 mod {self.p}"
def __eq__(self, other: 'Ellipse') -> bool:
return self.a == other.a and self.p == other.p
def is_on_curve(self, pt: 'Point') -> bool:
x, y = pt.x, pt.y
a, p = self.a, self.p
return (x*x + a * y*y) % p == 1
class Point:
"""Represents a point on curve"""
def __init__(self, curve: Ellipse, x: int, y: int):
self.x = x
self.y = y
self.curve = curve
assert self.curve.is_on_curve(self)
def __repr__(self) -> str:
return f"({self.x}, {self.y})"
def __add__(self, other: 'Point') -> 'Point':
x, y = self.x, self.y
w, z = other.x, other.y
a, p = self.curve.a, self.curve.p
nx = (x*w - a*y*z) % p
ny = (x*z + y*w) % p
return Point(self.curve, nx, ny)
def __mul__(self, n: int) -> 'Point':
assert n > 0
Q = Point(self.curve, 1, 0)
while n > 0:
if n & 1 == 1:
Q += self
self += self
n = n//2
return Q
def __eq__(self, other: 'Point') -> bool:
return self.x == other.x and self.y == other.y
def gen_secret(G: Point) -> Tuple[Point, int]:
priv = randint(1, p)
pub = G*priv
return pub, priv
def encrypt(shared: Point, pt: bytes) -> bytes:
key = sha1(str(shared).encode()).digest()[:16]
iv = urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(pad(pt, 16))
return iv + ct
def decrypt(shared: Point, ct: bytes) -> bytes:
iv, ct = ct[:16], ct[16:]
key = sha1(str(shared).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
pt = cipher.decrypt(ct)
return unpad(pt, 16)
alice_pub = (2138196312148079184382240325330500803425686967483863166176111074666553873369606997586883533252879522314508512610120185663459330505669976143538280185135503158, 1350098408534349199229781714086607605984656432458083815306756044307591092126215092360795039519565477039721903019874871683998662788499599535946383133093677646)
blake_pub = (4568773897927114993549462717422746966489956811871132275386853917467440322628373530720948282919382453518184702625364310911519327021756484938266990998628406420, 3649097172525610846241260554130988388479998230434661435854337888813320693155483292808012277418005770847521067027991154263171652473498536483631820529350606213)
ct = b'q\xfa\xf2\xe5\xe3\xba.H\xa5\x07az\xc0;\xc4%\xdf\xfe\xa0MI>o8\x96M\xb0\xfe]\xb2\xfdi\x8e\x9e\xea\x9f\xca\x98\xf9\x95\xe6&\x1fB\xd5\x0b\xf2\xeb\xac\x18\x82\xdcu\xd5\xd5\x8e<\xb3\xe4\x85e\xddX\xca0;\xe2G\xef7\\uM\x8d0A\xde+\x9fu'
a, p = 376014, (1 << 521) - 1
curve = Ellipse(a, p)
gx = 0x1bcfc82fca1e29598bd932fc4b8c573265e055795ba7d68ca3985a78bb57237b9ca042ab545a66b352655a10b4f60785ba308b060d9b7df2a651ca94eeb63b86fdb
gy = 0xca00d73e3d1570e6c63b506520c4fcc0151130a7f655b0d15ae3227423f304e1f7ffa73198f306d67a24c142b23f72adac5f166da5df68b669bbfda9fb4ef15f8e
G = Point(curve, gx, gy)
Q=Point(curve,blake_pub[0],blake_pub[1])
A=Point(curve,alice_pub[0],alice_pub[1])
e=0
for i in range(1,521):
t=(2^520)//(2^i)
GG=G*t
QQ=Q*t
tmp=e+2^(i-1)
if GG*tmp==QQ:
e=tmp
shared = A * e
print(decrypt(shared, ct))
|
