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
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
|
from ctypes import *
from base64 import *
DECAF = CDLL("build/lib/libdecaf.so")
F = GF(2^448-2^224-1)
d = -39081
E = EllipticCurve(F,[0,2-4*d,0,1,0])
p_tor4 = E.lift_x(-1)
Tor = [p_tor4 * i for i in xrange(4)]
q = 2^446-0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d
FQ = GF(q)
isoMagic = 1/sqrt(F(39082/39081)-1)
passing = True
# TODO: pathological cases
# TODO: Elligator
# TODO: double scalar mul
# TODO: Curve25519
def random_array(length):
answer = "".join([chr(randint(0,255)) for i in xrange(length)])
return answer
def from_le(buf):
return sum([256^i * ord(x) for i,x in enumerate(buf)])
def youfail(why,n):
print ("Fail on test %d!"%n), why
global passing
passing = False
def run_test(i):
try:
s = DecafScalar.random()
t = DecafScalar.random()
p = DecafPoint.random()
q = DecafPoint.random()
s*p + t*q
if s*(t*p) != (s*t)*p:
raise Exception("Mul doesn't work")
(p+q-p-q).ser() # i guess...
except Exception, e:
youfail(e,i)
def run_all_tests(n = 100):
for testno in xrange(n):
run_test(testno)
if passing:
print "Passed all %d tests." % n
def to_le(x,n):
x = int(x)
if x >= 256^n:
raise Exception("Integer too big in to_le(%d,%d)" % (x,n))
return "".join([chr(x>>(8*i) & 255) for i in xrange(n)])
class DecafScalar():
_UNDER = c_uint64 * int(7)
def __init__(self,cstruct=None,scalar=None):
if cstruct is None:
cstruct = DecafScalar._UNDER()
memmove(addressof(cstruct),
DECAF.decaf_448_scalar_zero,
8*7
)
if scalar is None:
scalar = E(0)
self.cstruct = cstruct
self.scalar = scalar
self._check()
@staticmethod
def _c_deser(str):
buffer = (c_uint8*int(56)).from_buffer_copy(str)
cstruct = DecafScalar._UNDER()
ret = DECAF.decaf_448_scalar_decode(cstruct,buffer,c_uint64(-1))
if ret != -1:
raise Exception("scalar didn't decode")
return cstruct
@staticmethod
def _sage_deser(str):
s = from_le(str)
if s >= FQ.cardinality(): raise Exception("scalar didn't decode")
return FQ(s)
def __eq__(self,other):
csays = bool(DECAF.decaf_448_scalar_eq(self.cstruct,other.cstruct))
sagesays = any([self.scalar == other.scalar + t for t in Tor])
if csays != sagesays:
raise Exception("C and SAGE don't agree: %d %d" % (csays, sagesays))
return csays
def __ne__(self,other):
return not self==other
def __add__(self,other):
cstruct = DecafScalar._UNDER()
DECAF.decaf_448_scalar_add(cstruct,self.cstruct,other.cstruct)
return DecafScalar(cstruct,self.scalar + other.scalar)
def __sub__(self,other):
cstruct = DecafScalar._UNDER()
DECAF.decaf_448_scalar_sub(cstruct,self.cstruct,other.cstruct)
return DecafScalar(cstruct,self.scalar - other.scalar)
def __mul__(self,other):
if isinstance(other,DecafScalar):
cstruct = DecafScalar._UNDER()
DECAF.decaf_448_scalar_mul(cstruct,self.cstruct,other.cstruct)
return DecafScalar(cstruct,self.scalar * other.scalar)
elif isinstance(other,DecafPoint):
cstruct = DecafPoint._UNDER()
DECAF.decaf_448_point_scalarmul(cstruct,other.cstruct,self.cstruct)
return DecafPoint(cstruct,int(self.scalar) * other.point)
else: raise Exception("Nope")
def __div__(self,other):
return self / other.inverse()
def inverse(self):
cstruct = DecafScalar._UNDER()
z = DECAF.decaf_448_scalar_invert(cstruct,self.cstruct)
if bool(z) != (self.scalar == 0):
raise Exception("C and SAGE don't agree")
return DecafScalar(cstruct,1/self.scalar)
def __neg__(self):
cstruct = DecafScalar._UNDER()
DECAF.decaf_448_scalar_negate(cstruct,self.cstruct)
return DecafScalar(cstruct,-self.scalar)
def __str__(self):
return " ".join(["%02x"%ord(b) for b in self.ser()])
def __repr__(self):
return "DecafScalar.fromInt(%d)" % self.scalar
@classmethod
def fromInt(cls,i):
return cls.deser(to_le(i,56))
def to64(self):
return b64encode(self.ser())
@classmethod
def from64(cls,str):
return cls.deser(b64decode(str))
@classmethod
def deser(cls,str):
good = True
try: cstruct = cls._c_deser(str)
except Exception: good = False
good2 = True
try: scalar = cls._sage_deser(str)
except Exception: good2 = False
if good != good2:
raise Exception("C and SAGE don't agree")
elif not good:
raise Exception("scalar didn't decode")
return cls(cstruct,scalar)
@classmethod
def random(cls):
while True:
try: return cls.deser(random_array(56))
except Exception: pass
@staticmethod
def _c_ser(cstruct):
buffer = (c_uint8*int(56))()
DECAF.decaf_448_scalar_encode(buffer,cstruct)
return str(bytearray(buffer))
def ser(self):
return self._c_ser(self.cstruct)
@staticmethod
def _sage_ser(P):
return to_le(P,56)
def _check(self):
ss = self._sage_ser(self.scalar)
cs = self._c_ser(self.cstruct)
if ss != cs:
print ss
print cs
raise Exception("Check failed!")
return True
class DecafPoint():
@staticmethod
def _UNDER():
size = int(8*8*4)
alignment = 32
buf1 = bytearray(size+alignment-1)
buf2 = (c_char * int(size+alignment-1)).from_buffer(buf1)
raw_addr = addressof(buf2)
offset = (-raw_addr) % alignment
return (c_char*size).from_buffer(buf2,int(offset))
def __init__(self,cstruct=None,point=None):
if cstruct is None:
cstruct = DecafPoint._UNDER()
memmove(addressof(cstruct),
DECAF.decaf_448_point_identity,
8*8*4
)
if point is None:
point = E(0)
self.cstruct = cstruct
self.point = point
self._check()
@staticmethod
def _c_deser(str):
buffer = (c_uint8*int(56)).from_buffer_copy(str)
cstruct = DecafPoint._UNDER()
ret = DECAF.decaf_448_point_decode(cstruct,buffer,c_uint64(-1))
if ret != -1:
raise Exception("Point didn't decode")
return cstruct
@staticmethod
def _sage_deser(str):
s = from_le(str)
if is_odd(s): raise Exception("Point didn't decode")
if (s==0): return E(0)
if not E.is_x_coord(s^2): raise Exception("Point didn't decode")
P = E.lift_x(s^2)
if is_odd(int(2*s^2*isoMagic/P.xy()[1])): P = -P
return P
def __eq__(self,other):
csays = bool(DECAF.decaf_448_point_eq(self.cstruct,other.cstruct))
sagesays = any([self.point == other.point + t for t in Tor])
if csays != sagesays:
raise Exception("C and SAGE don't agree: %d %d" % (csays, sagesays))
return csays
def __ne__(self,other):
return not self==other
def __add__(self,other):
cstruct = DecafPoint._UNDER()
DECAF.decaf_448_point_add(cstruct,self.cstruct,other.cstruct)
return DecafPoint(cstruct,self.point + other.point)
def __sub__(self,other):
cstruct = DecafPoint._UNDER()
DECAF.decaf_448_point_sub(cstruct,self.cstruct,other.cstruct)
return DecafPoint(cstruct,self.point - other.point)
def __mul__(self,other):
if isinstance(other,DecafScalar):
return other*self
else:
raise Exception("nope")
def __div__(self,other):
if isinstance(other,DecafScalar):
return other.inverse()*self
else:
raise Exception("nope")
def __neg__(self):
cstruct = DecafPoint._UNDER()
DECAF.decaf_448_point_negate(cstruct,self.cstruct)
return DecafPoint(cstruct,-self.point)
def __str__(self):
return " ".join(["%02x"%ord(b) for b in self.ser()])
def __repr__(self):
return "DecafPoint.from64('%s')" % self.to64()
def to64(self):
return b64encode(self.ser())
@classmethod
def from64(cls,str):
return cls.deser(b64decode(str))
@classmethod
def deser(cls,str):
good = True
try: cstruct = cls._c_deser(str)
except Exception: good = False
good2 = True
try: point = cls._sage_deser(str)
except Exception: good2 = False
if good != good2:
raise Exception("C and SAGE don't agree")
elif not good:
raise Exception("Point didn't decode")
return cls(cstruct,point)
@classmethod
def random(cls):
while True:
try: return cls.deser(random_array(56))
except Exception: pass
@staticmethod
def _c_ser(cstruct):
buffer = (c_uint8*int(56))()
DECAF.decaf_448_point_encode(buffer,cstruct)
return str(bytearray(buffer))
def ser(self):
return self._c_ser(self.cstruct)
@staticmethod
def _sage_ser(P):
if P == E(0): return to_le(0,56)
x,y = P.xy()
s = sqrt(x)
if s==0: return to_le(0,56)
if is_odd(int(2*s^2*isoMagic/y)): s = 1/s
if is_odd(int(s)): s = -s
return to_le(s,56)
def _check(self):
ss = self._sage_ser(self.point)
cs = self._c_ser(self.cstruct)
if ss != cs:
print "SAGE",b64encode(ss)
print "C ",b64encode(cs)
raise Exception("Check failed!")
return True
run_all_tests()
|
