forked from jimmysong/programmingbitcoin
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathecc.py
More file actions
205 lines (168 loc) · 6.4 KB
/
ecc.py
File metadata and controls
205 lines (168 loc) · 6.4 KB
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
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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
from unittest import TestCase
class FieldElement:
def __init__(self, num, prime):
if num >= prime or num < 0:
error = 'Num {} not in field range 0 to {}'.format(
num, prime - 1)
raise ValueError(error)
self.num = num
self.prime = prime
def __repr__(self):
return 'FieldElement_{}({})'.format(self.prime, self.num)
def __eq__(self, other):
if other is None:
return False
return self.num == other.num and self.prime == other.prime
def __ne__(self, other):
# this should be the inverse of the == operator
return not (self == other)
def __add__(self, other):
if self.prime != other.prime:
raise TypeError('Cannot add two numbers in different Fields')
# self.num and other.num are the actual values
# self.prime is what we need to mod against
num = (self.num + other.num) % self.prime
# We return an element of the same class
return self.__class__(num, self.prime)
def __sub__(self, other):
if self.prime != other.prime:
raise TypeError('Cannot subtract two numbers in different Fields')
# self.num and other.num are the actual values
# self.prime is what we need to mod against
num = (self.num - other.num) % self.prime
# We return an element of the same class
return self.__class__(num, self.prime)
def __mul__(self, other):
if self.prime != other.prime:
raise TypeError('Cannot multiply two numbers in different Fields')
# self.num and other.num are the actual values
# self.prime is what we need to mod against
num = (self.num * other.num) % self.prime
# We return an element of the same class
return self.__class__(num, self.prime)
def __pow__(self, exponent):
n = exponent % (self.prime - 1)
num = pow(self.num, n, self.prime)
return self.__class__(num, self.prime)
def __truediv__(self, other):
if self.prime != other.prime:
raise TypeError('Cannot divide two numbers in different Fields')
# self.num and other.num are the actual values
# self.prime is what we need to mod against
# use fermat's little theorem:
# self.num**(p-1) % p == 1
# this means:
# 1/n == pow(n, p-2, p)
num = (self.num * pow(other.num, self.prime - 2, self.prime)) % self.prime
# We return an element of the same class
return self.__class__(num, self.prime)
class FieldElementTest(TestCase):
def test_ne(self):
a = FieldElement(2, 31)
b = FieldElement(2, 31)
c = FieldElement(15, 31)
self.assertEqual(a, b)
self.assertTrue(a != c)
self.assertFalse(a != b)
def test_add(self):
a = FieldElement(2, 31)
b = FieldElement(15, 31)
self.assertEqual(a + b, FieldElement(17, 31))
a = FieldElement(17, 31)
b = FieldElement(21, 31)
self.assertEqual(a + b, FieldElement(7, 31))
def test_sub(self):
a = FieldElement(29, 31)
b = FieldElement(4, 31)
self.assertEqual(a - b, FieldElement(25, 31))
a = FieldElement(15, 31)
b = FieldElement(30, 31)
self.assertEqual(a - b, FieldElement(16, 31))
def test_mul(self):
a = FieldElement(24, 31)
b = FieldElement(19, 31)
self.assertEqual(a * b, FieldElement(22, 31))
def test_pow(self):
a = FieldElement(17, 31)
self.assertEqual(a**3, FieldElement(15, 31))
a = FieldElement(5, 31)
b = FieldElement(18, 31)
self.assertEqual(a**5 * b, FieldElement(16, 31))
def test_div(self):
a = FieldElement(3, 31)
b = FieldElement(24, 31)
self.assertEqual(a / b, FieldElement(4, 31))
a = FieldElement(17, 31)
self.assertEqual(a**-3, FieldElement(29, 31))
a = FieldElement(4, 31)
b = FieldElement(11, 31)
self.assertEqual(a**-4 * b, FieldElement(13, 31))
# tag::source1[]
class Point:
def __init__(self, x, y, a, b):
self.a = a
self.b = b
self.x = x
self.y = y
# end::source1[]
# tag::source2[]
if self.x is None and self.y is None: # <1>
return
# end::source2[]
# tag::source1[]
if self.y**2 != self.x**3 + a * x + b: # <1>
raise ValueError('({}, {}) is not on the curve'.format(x, y))
def __eq__(self, other): # <2>
return self.x == other.x and self.y == other.y \
and self.a == other.a and self.b == other.b
# end::source1[]
def __ne__(self, other):
# this should be the inverse of the == operator
raise NotImplementedError
def __repr__(self):
if self.x is None:
return 'Point(infinity)'
else:
return 'Point({},{})_{}_{}'.format(self.x, self.y, self.a, self.b)
# tag::source3[]
def __add__(self, other): # <2>
if self.a != other.a or self.b != other.b:
raise TypeError('Points {}, {} are not on the same curve'.format(self, other))
if self.x is None: # <3>
return other
if other.x is None: # <4>
return self
# end::source3[]
# Case 1: self.x == other.x, self.y != other.y
# Result is point at infinity
# Case 2: self.x ≠ other.x
# Formula (x3,y3)==(x1,y1)+(x2,y2)
# s=(y2-y1)/(x2-x1)
# x3=s**2-x1-x2
# y3=s*(x1-x3)-y1
# Case 3: self == other
# Formula (x3,y3)=(x1,y1)+(x1,y1)
# s=(3*x1**2+a)/(2*y1)
# x3=s**2-2*x1
# y3=s*(x1-x3)-y1
raise NotImplementedError
class PointTest(TestCase):
def test_ne(self):
a = Point(x=3, y=-7, a=5, b=7)
b = Point(x=18, y=77, a=5, b=7)
self.assertTrue(a != b)
self.assertFalse(a != a)
def test_add0(self):
a = Point(x=None, y=None, a=5, b=7)
b = Point(x=2, y=5, a=5, b=7)
c = Point(x=2, y=-5, a=5, b=7)
self.assertEqual(a + b, b)
self.assertEqual(b + a, b)
self.assertEqual(b + c, a)
def test_add1(self):
a = Point(x=3, y=7, a=5, b=7)
b = Point(x=-1, y=-1, a=5, b=7)
self.assertEqual(a + b, Point(x=2, y=-5, a=5, b=7))
def test_add2(self):
a = Point(x=-1, y=1, a=5, b=7)
self.assertEqual(a + a, Point(x=18, y=-77, a=5, b=7))