1 |
|
|
/* $OpenBSD: fe25519.c,v 1.3 2013/12/09 11:03:45 markus Exp $ */ |
2 |
|
|
|
3 |
|
|
/* |
4 |
|
|
* Public Domain, Authors: Daniel J. Bernstein, Niels Duif, Tanja Lange, |
5 |
|
|
* Peter Schwabe, Bo-Yin Yang. |
6 |
|
|
* Copied from supercop-20130419/crypto_sign/ed25519/ref/fe25519.c |
7 |
|
|
*/ |
8 |
|
|
|
9 |
|
|
#define WINDOWSIZE 1 /* Should be 1,2, or 4 */ |
10 |
|
|
#define WINDOWMASK ((1<<WINDOWSIZE)-1) |
11 |
|
|
|
12 |
|
|
#include "fe25519.h" |
13 |
|
|
|
14 |
|
|
static crypto_uint32 equal(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */ |
15 |
|
|
{ |
16 |
|
620 |
crypto_uint32 x = a ^ b; /* 0: yes; 1..65535: no */ |
17 |
|
310 |
x -= 1; /* 4294967295: yes; 0..65534: no */ |
18 |
|
310 |
x >>= 31; /* 1: yes; 0: no */ |
19 |
|
310 |
return x; |
20 |
|
|
} |
21 |
|
|
|
22 |
|
|
static crypto_uint32 ge(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */ |
23 |
|
|
{ |
24 |
|
|
unsigned int x = a; |
25 |
|
20 |
x -= (unsigned int) b; /* 0..65535: yes; 4294901761..4294967295: no */ |
26 |
|
10 |
x >>= 31; /* 0: yes; 1: no */ |
27 |
|
10 |
x ^= 1; /* 1: yes; 0: no */ |
28 |
|
10 |
return x; |
29 |
|
|
} |
30 |
|
|
|
31 |
|
|
static crypto_uint32 times19(crypto_uint32 a) |
32 |
|
|
{ |
33 |
|
54120 |
return (a << 4) + (a << 1) + a; |
34 |
|
|
} |
35 |
|
|
|
36 |
|
|
static crypto_uint32 times38(crypto_uint32 a) |
37 |
|
|
{ |
38 |
|
317440 |
return (a << 5) + (a << 2) + (a << 1); |
39 |
|
|
} |
40 |
|
|
|
41 |
|
|
static void reduce_add_sub(fe25519 *r) |
42 |
|
|
{ |
43 |
|
|
crypto_uint32 t; |
44 |
|
|
int i,rep; |
45 |
|
|
|
46 |
✓✓ |
46255 |
for(rep=0;rep<4;rep++) |
47 |
|
|
{ |
48 |
|
16820 |
t = r->v[31] >> 7; |
49 |
|
16820 |
r->v[31] &= 127; |
50 |
|
16820 |
t = times19(t); |
51 |
|
16820 |
r->v[0] += t; |
52 |
✓✓ |
1076480 |
for(i=0;i<31;i++) |
53 |
|
|
{ |
54 |
|
521420 |
t = r->v[i] >> 8; |
55 |
|
521420 |
r->v[i+1] += t; |
56 |
|
521420 |
r->v[i] &= 255; |
57 |
|
|
} |
58 |
|
|
} |
59 |
|
4205 |
} |
60 |
|
|
|
61 |
|
|
static void reduce_mul(fe25519 *r) |
62 |
|
|
{ |
63 |
|
|
crypto_uint32 t; |
64 |
|
|
int i,rep; |
65 |
|
|
|
66 |
✓✓ |
35840 |
for(rep=0;rep<2;rep++) |
67 |
|
|
{ |
68 |
|
10240 |
t = r->v[31] >> 7; |
69 |
|
10240 |
r->v[31] &= 127; |
70 |
|
10240 |
t = times19(t); |
71 |
|
10240 |
r->v[0] += t; |
72 |
✓✓ |
655360 |
for(i=0;i<31;i++) |
73 |
|
|
{ |
74 |
|
317440 |
t = r->v[i] >> 8; |
75 |
|
317440 |
r->v[i+1] += t; |
76 |
|
317440 |
r->v[i] &= 255; |
77 |
|
|
} |
78 |
|
|
} |
79 |
|
5120 |
} |
80 |
|
|
|
81 |
|
|
/* reduction modulo 2^255-19 */ |
82 |
|
|
void fe25519_freeze(fe25519 *r) |
83 |
|
|
{ |
84 |
|
|
int i; |
85 |
|
20 |
crypto_uint32 m = equal(r->v[31],127); |
86 |
✓✓ |
620 |
for(i=30;i>0;i--) |
87 |
|
300 |
m &= equal(r->v[i],255); |
88 |
|
10 |
m &= ge(r->v[0],237); |
89 |
|
|
|
90 |
|
10 |
m = -m; |
91 |
|
|
|
92 |
|
10 |
r->v[31] -= m&127; |
93 |
✓✓ |
620 |
for(i=30;i>0;i--) |
94 |
|
300 |
r->v[i] -= m&255; |
95 |
|
10 |
r->v[0] -= m&237; |
96 |
|
10 |
} |
97 |
|
|
|
98 |
|
|
void fe25519_unpack(fe25519 *r, const unsigned char x[32]) |
99 |
|
|
{ |
100 |
|
|
int i; |
101 |
|
|
for(i=0;i<32;i++) r->v[i] = x[i]; |
102 |
|
|
r->v[31] &= 127; |
103 |
|
|
} |
104 |
|
|
|
105 |
|
|
/* Assumes input x being reduced below 2^255 */ |
106 |
|
|
void fe25519_pack(unsigned char r[32], const fe25519 *x) |
107 |
|
|
{ |
108 |
|
|
int i; |
109 |
|
10 |
fe25519 y = *x; |
110 |
|
5 |
fe25519_freeze(&y); |
111 |
✓✓ |
330 |
for(i=0;i<32;i++) |
112 |
|
160 |
r[i] = y.v[i]; |
113 |
|
5 |
} |
114 |
|
|
|
115 |
|
|
int fe25519_iszero(const fe25519 *x) |
116 |
|
|
{ |
117 |
|
|
int i; |
118 |
|
|
int r; |
119 |
|
|
fe25519 t = *x; |
120 |
|
|
fe25519_freeze(&t); |
121 |
|
|
r = equal(t.v[0],0); |
122 |
|
|
for(i=1;i<32;i++) |
123 |
|
|
r &= equal(t.v[i],0); |
124 |
|
|
return r; |
125 |
|
|
} |
126 |
|
|
|
127 |
|
|
int fe25519_iseq_vartime(const fe25519 *x, const fe25519 *y) |
128 |
|
|
{ |
129 |
|
|
int i; |
130 |
|
|
fe25519 t1 = *x; |
131 |
|
|
fe25519 t2 = *y; |
132 |
|
|
fe25519_freeze(&t1); |
133 |
|
|
fe25519_freeze(&t2); |
134 |
|
|
for(i=0;i<32;i++) |
135 |
|
|
if(t1.v[i] != t2.v[i]) return 0; |
136 |
|
|
return 1; |
137 |
|
|
} |
138 |
|
|
|
139 |
|
|
void fe25519_cmov(fe25519 *r, const fe25519 *x, unsigned char b) |
140 |
|
|
{ |
141 |
|
|
int i; |
142 |
|
7650 |
crypto_uint32 mask = b; |
143 |
|
3825 |
mask = -mask; |
144 |
✓✓ |
252450 |
for(i=0;i<32;i++) r->v[i] ^= mask & (x->v[i] ^ r->v[i]); |
145 |
|
3825 |
} |
146 |
|
|
|
147 |
|
|
unsigned char fe25519_getparity(const fe25519 *x) |
148 |
|
|
{ |
149 |
|
10 |
fe25519 t = *x; |
150 |
|
5 |
fe25519_freeze(&t); |
151 |
|
10 |
return t.v[0] & 1; |
152 |
|
5 |
} |
153 |
|
|
|
154 |
|
|
void fe25519_setone(fe25519 *r) |
155 |
|
|
{ |
156 |
|
|
int i; |
157 |
|
10 |
r->v[0] = 1; |
158 |
✓✓ |
320 |
for(i=1;i<32;i++) r->v[i]=0; |
159 |
|
5 |
} |
160 |
|
|
|
161 |
|
|
void fe25519_setzero(fe25519 *r) |
162 |
|
|
{ |
163 |
|
|
int i; |
164 |
✓✓ |
28475 |
for(i=0;i<32;i++) r->v[i]=0; |
165 |
|
425 |
} |
166 |
|
|
|
167 |
|
|
void fe25519_neg(fe25519 *r, const fe25519 *x) |
168 |
|
|
{ |
169 |
|
850 |
fe25519 t; |
170 |
|
|
int i; |
171 |
✓✓ |
28050 |
for(i=0;i<32;i++) t.v[i]=x->v[i]; |
172 |
|
425 |
fe25519_setzero(r); |
173 |
|
425 |
fe25519_sub(r, r, &t); |
174 |
|
425 |
} |
175 |
|
|
|
176 |
|
|
void fe25519_add(fe25519 *r, const fe25519 *x, const fe25519 *y) |
177 |
|
|
{ |
178 |
|
|
int i; |
179 |
✓✓ |
140700 |
for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i]; |
180 |
|
2100 |
reduce_add_sub(r); |
181 |
|
2100 |
} |
182 |
|
|
|
183 |
|
|
void fe25519_sub(fe25519 *r, const fe25519 *x, const fe25519 *y) |
184 |
|
|
{ |
185 |
|
|
int i; |
186 |
|
4210 |
crypto_uint32 t[32]; |
187 |
|
2105 |
t[0] = x->v[0] + 0x1da; |
188 |
|
2105 |
t[31] = x->v[31] + 0xfe; |
189 |
✓✓ |
130510 |
for(i=1;i<31;i++) t[i] = x->v[i] + 0x1fe; |
190 |
✓✓ |
138930 |
for(i=0;i<32;i++) r->v[i] = t[i] - y->v[i]; |
191 |
|
2105 |
reduce_add_sub(r); |
192 |
|
2105 |
} |
193 |
|
|
|
194 |
|
|
void fe25519_mul(fe25519 *r, const fe25519 *x, const fe25519 *y) |
195 |
|
|
{ |
196 |
|
|
int i,j; |
197 |
|
10240 |
crypto_uint32 t[63]; |
198 |
✓✓ |
655360 |
for(i=0;i<63;i++)t[i] = 0; |
199 |
|
|
|
200 |
✓✓ |
337920 |
for(i=0;i<32;i++) |
201 |
✓✓ |
10813440 |
for(j=0;j<32;j++) |
202 |
|
5242880 |
t[i+j] += x->v[i] * y->v[j]; |
203 |
|
|
|
204 |
✓✓ |
327680 |
for(i=32;i<63;i++) |
205 |
|
158720 |
r->v[i-32] = t[i-32] + times38(t[i]); |
206 |
|
5120 |
r->v[31] = t[31]; /* result now in r[0]...r[31] */ |
207 |
|
|
|
208 |
|
5120 |
reduce_mul(r); |
209 |
|
5120 |
} |
210 |
|
|
|
211 |
|
|
void fe25519_square(fe25519 *r, const fe25519 *x) |
212 |
|
|
{ |
213 |
|
2540 |
fe25519_mul(r, x, x); |
214 |
|
1270 |
} |
215 |
|
|
|
216 |
|
|
void fe25519_invert(fe25519 *r, const fe25519 *x) |
217 |
|
|
{ |
218 |
|
10 |
fe25519 z2; |
219 |
|
5 |
fe25519 z9; |
220 |
|
5 |
fe25519 z11; |
221 |
|
5 |
fe25519 z2_5_0; |
222 |
|
5 |
fe25519 z2_10_0; |
223 |
|
5 |
fe25519 z2_20_0; |
224 |
|
5 |
fe25519 z2_50_0; |
225 |
|
5 |
fe25519 z2_100_0; |
226 |
|
5 |
fe25519 t0; |
227 |
|
5 |
fe25519 t1; |
228 |
|
|
int i; |
229 |
|
|
|
230 |
|
5 |
/* 2 */ fe25519_square(&z2,x); |
231 |
|
5 |
/* 4 */ fe25519_square(&t1,&z2); |
232 |
|
5 |
/* 8 */ fe25519_square(&t0,&t1); |
233 |
|
5 |
/* 9 */ fe25519_mul(&z9,&t0,x); |
234 |
|
5 |
/* 11 */ fe25519_mul(&z11,&z9,&z2); |
235 |
|
5 |
/* 22 */ fe25519_square(&t0,&z11); |
236 |
|
5 |
/* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t0,&z9); |
237 |
|
|
|
238 |
|
5 |
/* 2^6 - 2^1 */ fe25519_square(&t0,&z2_5_0); |
239 |
|
5 |
/* 2^7 - 2^2 */ fe25519_square(&t1,&t0); |
240 |
|
5 |
/* 2^8 - 2^3 */ fe25519_square(&t0,&t1); |
241 |
|
5 |
/* 2^9 - 2^4 */ fe25519_square(&t1,&t0); |
242 |
|
5 |
/* 2^10 - 2^5 */ fe25519_square(&t0,&t1); |
243 |
|
5 |
/* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t0,&z2_5_0); |
244 |
|
|
|
245 |
|
5 |
/* 2^11 - 2^1 */ fe25519_square(&t0,&z2_10_0); |
246 |
|
5 |
/* 2^12 - 2^2 */ fe25519_square(&t1,&t0); |
247 |
✓✓ |
50 |
/* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); } |
248 |
|
5 |
/* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t1,&z2_10_0); |
249 |
|
|
|
250 |
|
5 |
/* 2^21 - 2^1 */ fe25519_square(&t0,&z2_20_0); |
251 |
|
5 |
/* 2^22 - 2^2 */ fe25519_square(&t1,&t0); |
252 |
✓✓ |
100 |
/* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); } |
253 |
|
5 |
/* 2^40 - 2^0 */ fe25519_mul(&t0,&t1,&z2_20_0); |
254 |
|
|
|
255 |
|
5 |
/* 2^41 - 2^1 */ fe25519_square(&t1,&t0); |
256 |
|
5 |
/* 2^42 - 2^2 */ fe25519_square(&t0,&t1); |
257 |
✓✓ |
50 |
/* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); } |
258 |
|
5 |
/* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t0,&z2_10_0); |
259 |
|
|
|
260 |
|
5 |
/* 2^51 - 2^1 */ fe25519_square(&t0,&z2_50_0); |
261 |
|
5 |
/* 2^52 - 2^2 */ fe25519_square(&t1,&t0); |
262 |
✓✓ |
250 |
/* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); } |
263 |
|
5 |
/* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t1,&z2_50_0); |
264 |
|
|
|
265 |
|
5 |
/* 2^101 - 2^1 */ fe25519_square(&t1,&z2_100_0); |
266 |
|
5 |
/* 2^102 - 2^2 */ fe25519_square(&t0,&t1); |
267 |
✓✓ |
500 |
/* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fe25519_square(&t1,&t0); fe25519_square(&t0,&t1); } |
268 |
|
5 |
/* 2^200 - 2^0 */ fe25519_mul(&t1,&t0,&z2_100_0); |
269 |
|
|
|
270 |
|
5 |
/* 2^201 - 2^1 */ fe25519_square(&t0,&t1); |
271 |
|
5 |
/* 2^202 - 2^2 */ fe25519_square(&t1,&t0); |
272 |
✓✓ |
250 |
/* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fe25519_square(&t0,&t1); fe25519_square(&t1,&t0); } |
273 |
|
5 |
/* 2^250 - 2^0 */ fe25519_mul(&t0,&t1,&z2_50_0); |
274 |
|
|
|
275 |
|
5 |
/* 2^251 - 2^1 */ fe25519_square(&t1,&t0); |
276 |
|
5 |
/* 2^252 - 2^2 */ fe25519_square(&t0,&t1); |
277 |
|
5 |
/* 2^253 - 2^3 */ fe25519_square(&t1,&t0); |
278 |
|
5 |
/* 2^254 - 2^4 */ fe25519_square(&t0,&t1); |
279 |
|
5 |
/* 2^255 - 2^5 */ fe25519_square(&t1,&t0); |
280 |
|
5 |
/* 2^255 - 21 */ fe25519_mul(r,&t1,&z11); |
281 |
|
5 |
} |
282 |
|
|
|
283 |
|
|
void fe25519_pow2523(fe25519 *r, const fe25519 *x) |
284 |
|
|
{ |
285 |
|
|
fe25519 z2; |
286 |
|
|
fe25519 z9; |
287 |
|
|
fe25519 z11; |
288 |
|
|
fe25519 z2_5_0; |
289 |
|
|
fe25519 z2_10_0; |
290 |
|
|
fe25519 z2_20_0; |
291 |
|
|
fe25519 z2_50_0; |
292 |
|
|
fe25519 z2_100_0; |
293 |
|
|
fe25519 t; |
294 |
|
|
int i; |
295 |
|
|
|
296 |
|
|
/* 2 */ fe25519_square(&z2,x); |
297 |
|
|
/* 4 */ fe25519_square(&t,&z2); |
298 |
|
|
/* 8 */ fe25519_square(&t,&t); |
299 |
|
|
/* 9 */ fe25519_mul(&z9,&t,x); |
300 |
|
|
/* 11 */ fe25519_mul(&z11,&z9,&z2); |
301 |
|
|
/* 22 */ fe25519_square(&t,&z11); |
302 |
|
|
/* 2^5 - 2^0 = 31 */ fe25519_mul(&z2_5_0,&t,&z9); |
303 |
|
|
|
304 |
|
|
/* 2^6 - 2^1 */ fe25519_square(&t,&z2_5_0); |
305 |
|
|
/* 2^10 - 2^5 */ for (i = 1;i < 5;i++) { fe25519_square(&t,&t); } |
306 |
|
|
/* 2^10 - 2^0 */ fe25519_mul(&z2_10_0,&t,&z2_5_0); |
307 |
|
|
|
308 |
|
|
/* 2^11 - 2^1 */ fe25519_square(&t,&z2_10_0); |
309 |
|
|
/* 2^20 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); } |
310 |
|
|
/* 2^20 - 2^0 */ fe25519_mul(&z2_20_0,&t,&z2_10_0); |
311 |
|
|
|
312 |
|
|
/* 2^21 - 2^1 */ fe25519_square(&t,&z2_20_0); |
313 |
|
|
/* 2^40 - 2^20 */ for (i = 1;i < 20;i++) { fe25519_square(&t,&t); } |
314 |
|
|
/* 2^40 - 2^0 */ fe25519_mul(&t,&t,&z2_20_0); |
315 |
|
|
|
316 |
|
|
/* 2^41 - 2^1 */ fe25519_square(&t,&t); |
317 |
|
|
/* 2^50 - 2^10 */ for (i = 1;i < 10;i++) { fe25519_square(&t,&t); } |
318 |
|
|
/* 2^50 - 2^0 */ fe25519_mul(&z2_50_0,&t,&z2_10_0); |
319 |
|
|
|
320 |
|
|
/* 2^51 - 2^1 */ fe25519_square(&t,&z2_50_0); |
321 |
|
|
/* 2^100 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); } |
322 |
|
|
/* 2^100 - 2^0 */ fe25519_mul(&z2_100_0,&t,&z2_50_0); |
323 |
|
|
|
324 |
|
|
/* 2^101 - 2^1 */ fe25519_square(&t,&z2_100_0); |
325 |
|
|
/* 2^200 - 2^100 */ for (i = 1;i < 100;i++) { fe25519_square(&t,&t); } |
326 |
|
|
/* 2^200 - 2^0 */ fe25519_mul(&t,&t,&z2_100_0); |
327 |
|
|
|
328 |
|
|
/* 2^201 - 2^1 */ fe25519_square(&t,&t); |
329 |
|
|
/* 2^250 - 2^50 */ for (i = 1;i < 50;i++) { fe25519_square(&t,&t); } |
330 |
|
|
/* 2^250 - 2^0 */ fe25519_mul(&t,&t,&z2_50_0); |
331 |
|
|
|
332 |
|
|
/* 2^251 - 2^1 */ fe25519_square(&t,&t); |
333 |
|
|
/* 2^252 - 2^2 */ fe25519_square(&t,&t); |
334 |
|
|
/* 2^252 - 3 */ fe25519_mul(r,&t,x); |
335 |
|
|
} |