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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159 | class Curve:
# Curve
WEIERSTRASS = 0
MONTGOMERY = 1
def __init__(self, a, b, t):
self._a = a
self._b = b
if t not in (Curve.WEIERSTRASS, Curve.MONTGOMERY):
raise Exception(f"The type of the curve is not recognized")
self._type = t
self._xtmp = np.linspace(-5, 5, 500).tolist()
self._x = list()
self._y = list()
self._yn = list()
self._points = list()
self._pointsSym = list()
def f(self, x):
if self._type == Curve.WEIERSTRASS:
y = pow(x, 3) + (self._a * x) + self._b
if self._type == Curve.MONTGOMERY:
y = pow(x, 3) + (3 * pow(x, 2)) + x
if y > 0:
return sqrt(y)
return None
def generatePoints(self):
for x in self._xtmp:
y = self.f(x)
if y is None:
continue
self._x.append(x)
self._y.append(y)
self._yn.append(-y)
self._points.append(Point(
x,
y
))
self._pointsSym.append(Point(
x,
-y
))
@property
def x(self):
return self._x
@property
def y(self):
return self._y
@property
def yn(self):
return self._yn
def getPoints(self):
return self._points
def getPointsSym(self):
return self._pointsSym
def add(self, P, Q) -> Point:
"""
This function operathe addition operation on two points P and Q
Args:
P (Object): The first Point on the curve
Q (Object): The second Point on the curve
Returns:
Return the Point object R
"""
## Check if P or Q are infinity
if (P.x, P.y) == (0, 0) and (Q.x, Q.y) == (0, 0):
return Point(0, 0)
elif (P.x, P.y) == (0, 0):
return Point(Q.x, Q.y)
elif (Q.x, Q.y) == (0, 0):
return Point(P.x, P.y)
# point doubling
if P.x == Q.x:
# Infinity
if P.y != Q.y or Q.y == 0:
return Point(0, 0)
# Point doubling
try:
inv = pow(2 * P.y, -1); # It's working with the inverse modular, WHY ???
m = ((3 * pow(P.x, 2)) + self._a) * inv
except ValueError:
return Point(0, 0)
else:
try:
inv = pow(Q.x - P.x, -1)
m = (Q.y - P.y) * inv
except ValueError:
# May call this Exception: base is not invertible for the given modulus
# I return an Infinity point until I fixed that
return Point(0, 0)
xr = (pow(m, 2) - P.x - Q.x)
yr = (m * (P.x - xr)) - P.y
return Point(xr, yr)
def scalar(self, P, n) -> Point:
"""
This function compute a Scalar Multiplication of P, n time. This algorithm is also known as Double and Add.
Args:
P (point): the Point to multiplication
n (Integer): multiplicate n time P
Returns:
Return the result of the Scalar multiplication
"""
binary = bin(n)[2:]
binary = binary[::-1] # We need to reverse the binary
nP = Point(0, 0)
Rtmp = P
for b in binary:
if b == '1':
nP = self.add(nP, Rtmp)
Rtmp = self.add(Rtmp, Rtmp) # Double P
return nP
def find_reverse(self, P):
"""
This function return the reverse of the Point P
Args:
P (Point): Point object to find
Returns:
Return the object Pr, which is the reverse point of P
"""
Pr = None
for p in self._pointsSym:
if P.x == p.x and -P.y == p.y:
Pr = Point(p.x, p.y)
break
return Pr
|