1 |
#include "ge.h" |
2 |
#include "precomp_data.h" |
3 |
|
4 |
|
5 |
/* |
6 |
r = p + q |
7 |
*/ |
8 |
|
9 |
void ge_add(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) { |
10 |
fe t0; |
11 |
fe_add(r->X, p->Y, p->X); |
12 |
fe_sub(r->Y, p->Y, p->X); |
13 |
fe_mul(r->Z, r->X, q->YplusX); |
14 |
fe_mul(r->Y, r->Y, q->YminusX); |
15 |
fe_mul(r->T, q->T2d, p->T); |
16 |
fe_mul(r->X, p->Z, q->Z); |
17 |
fe_add(t0, r->X, r->X); |
18 |
fe_sub(r->X, r->Z, r->Y); |
19 |
fe_add(r->Y, r->Z, r->Y); |
20 |
fe_add(r->Z, t0, r->T); |
21 |
fe_sub(r->T, t0, r->T); |
22 |
} |
23 |
|
24 |
|
25 |
static void slide(signed char *r, const unsigned char *a) { |
26 |
int i; |
27 |
int b; |
28 |
int k; |
29 |
|
30 |
for (i = 0; i < 256; ++i) { |
31 |
r[i] = 1 & (a[i >> 3] >> (i & 7)); |
32 |
} |
33 |
|
34 |
for (i = 0; i < 256; ++i) |
35 |
if (r[i]) { |
36 |
for (b = 1; b <= 6 && i + b < 256; ++b) { |
37 |
if (r[i + b]) { |
38 |
if (r[i] + (r[i + b] << b) <= 15) { |
39 |
r[i] += r[i + b] << b; |
40 |
r[i + b] = 0; |
41 |
} else if (r[i] - (r[i + b] << b) >= -15) { |
42 |
r[i] -= r[i + b] << b; |
43 |
|
44 |
for (k = i + b; k < 256; ++k) { |
45 |
if (!r[k]) { |
46 |
r[k] = 1; |
47 |
break; |
48 |
} |
49 |
|
50 |
r[k] = 0; |
51 |
} |
52 |
} else { |
53 |
break; |
54 |
} |
55 |
} |
56 |
} |
57 |
} |
58 |
} |
59 |
|
60 |
/* |
61 |
r = a * A + b * B |
62 |
where a = a[0]+256*a[1]+...+256^31 a[31]. |
63 |
and b = b[0]+256*b[1]+...+256^31 b[31]. |
64 |
B is the Ed25519 base point (x,4/5) with x positive. |
65 |
*/ |
66 |
|
67 |
void ge_double_scalarmult_vartime(ge_p2 *r, const unsigned char *a, const ge_p3 *A, const unsigned char *b) { |
68 |
signed char aslide[256]; |
69 |
signed char bslide[256]; |
70 |
ge_cached Ai[8]; /* A,3A,5A,7A,9A,11A,13A,15A */ |
71 |
ge_p1p1 t; |
72 |
ge_p3 u; |
73 |
ge_p3 A2; |
74 |
int i; |
75 |
slide(aslide, a); |
76 |
slide(bslide, b); |
77 |
ge_p3_to_cached(&Ai[0], A); |
78 |
ge_p3_dbl(&t, A); |
79 |
ge_p1p1_to_p3(&A2, &t); |
80 |
ge_add(&t, &A2, &Ai[0]); |
81 |
ge_p1p1_to_p3(&u, &t); |
82 |
ge_p3_to_cached(&Ai[1], &u); |
83 |
ge_add(&t, &A2, &Ai[1]); |
84 |
ge_p1p1_to_p3(&u, &t); |
85 |
ge_p3_to_cached(&Ai[2], &u); |
86 |
ge_add(&t, &A2, &Ai[2]); |
87 |
ge_p1p1_to_p3(&u, &t); |
88 |
ge_p3_to_cached(&Ai[3], &u); |
89 |
ge_add(&t, &A2, &Ai[3]); |
90 |
ge_p1p1_to_p3(&u, &t); |
91 |
ge_p3_to_cached(&Ai[4], &u); |
92 |
ge_add(&t, &A2, &Ai[4]); |
93 |
ge_p1p1_to_p3(&u, &t); |
94 |
ge_p3_to_cached(&Ai[5], &u); |
95 |
ge_add(&t, &A2, &Ai[5]); |
96 |
ge_p1p1_to_p3(&u, &t); |
97 |
ge_p3_to_cached(&Ai[6], &u); |
98 |
ge_add(&t, &A2, &Ai[6]); |
99 |
ge_p1p1_to_p3(&u, &t); |
100 |
ge_p3_to_cached(&Ai[7], &u); |
101 |
ge_p2_0(r); |
102 |
|
103 |
for (i = 255; i >= 0; --i) { |
104 |
if (aslide[i] || bslide[i]) { |
105 |
break; |
106 |
} |
107 |
} |
108 |
|
109 |
for (; i >= 0; --i) { |
110 |
ge_p2_dbl(&t, r); |
111 |
|
112 |
if (aslide[i] > 0) { |
113 |
ge_p1p1_to_p3(&u, &t); |
114 |
ge_add(&t, &u, &Ai[aslide[i] / 2]); |
115 |
} else if (aslide[i] < 0) { |
116 |
ge_p1p1_to_p3(&u, &t); |
117 |
ge_sub(&t, &u, &Ai[(-aslide[i]) / 2]); |
118 |
} |
119 |
|
120 |
if (bslide[i] > 0) { |
121 |
ge_p1p1_to_p3(&u, &t); |
122 |
ge_madd(&t, &u, &Bi[bslide[i] / 2]); |
123 |
} else if (bslide[i] < 0) { |
124 |
ge_p1p1_to_p3(&u, &t); |
125 |
ge_msub(&t, &u, &Bi[(-bslide[i]) / 2]); |
126 |
} |
127 |
|
128 |
ge_p1p1_to_p2(r, &t); |
129 |
} |
130 |
} |
131 |
|
132 |
|
133 |
static const fe d = { |
134 |
-10913610, 13857413, -15372611, 6949391, 114729, -8787816, -6275908, -3247719, -18696448, -12055116 |
135 |
}; |
136 |
|
137 |
static const fe sqrtm1 = { |
138 |
-32595792, -7943725, 9377950, 3500415, 12389472, -272473, -25146209, -2005654, 326686, 11406482 |
139 |
}; |
140 |
|
141 |
int ge_frombytes_negate_vartime(ge_p3 *h, const unsigned char *s) { |
142 |
fe u; |
143 |
fe v; |
144 |
fe v3; |
145 |
fe vxx; |
146 |
fe check; |
147 |
fe_frombytes(h->Y, s); |
148 |
fe_1(h->Z); |
149 |
fe_sq(u, h->Y); |
150 |
fe_mul(v, u, d); |
151 |
fe_sub(u, u, h->Z); /* u = y^2-1 */ |
152 |
fe_add(v, v, h->Z); /* v = dy^2+1 */ |
153 |
fe_sq(v3, v); |
154 |
fe_mul(v3, v3, v); /* v3 = v^3 */ |
155 |
fe_sq(h->X, v3); |
156 |
fe_mul(h->X, h->X, v); |
157 |
fe_mul(h->X, h->X, u); /* x = uv^7 */ |
158 |
fe_pow22523(h->X, h->X); /* x = (uv^7)^((q-5)/8) */ |
159 |
fe_mul(h->X, h->X, v3); |
160 |
fe_mul(h->X, h->X, u); /* x = uv^3(uv^7)^((q-5)/8) */ |
161 |
fe_sq(vxx, h->X); |
162 |
fe_mul(vxx, vxx, v); |
163 |
fe_sub(check, vxx, u); /* vx^2-u */ |
164 |
|
165 |
if (fe_isnonzero(check)) { |
166 |
fe_add(check, vxx, u); /* vx^2+u */ |
167 |
|
168 |
if (fe_isnonzero(check)) { |
169 |
return -1; |
170 |
} |
171 |
|
172 |
fe_mul(h->X, h->X, sqrtm1); |
173 |
} |
174 |
|
175 |
if (fe_isnegative(h->X) == (s[31] >> 7)) { |
176 |
fe_neg(h->X, h->X); |
177 |
} |
178 |
|
179 |
fe_mul(h->T, h->X, h->Y); |
180 |
return 0; |
181 |
} |
182 |
|
183 |
|
184 |
/* |
185 |
r = p + q |
186 |
*/ |
187 |
|
188 |
void ge_madd(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) { |
189 |
fe t0; |
190 |
fe_add(r->X, p->Y, p->X); |
191 |
fe_sub(r->Y, p->Y, p->X); |
192 |
fe_mul(r->Z, r->X, q->yplusx); |
193 |
fe_mul(r->Y, r->Y, q->yminusx); |
194 |
fe_mul(r->T, q->xy2d, p->T); |
195 |
fe_add(t0, p->Z, p->Z); |
196 |
fe_sub(r->X, r->Z, r->Y); |
197 |
fe_add(r->Y, r->Z, r->Y); |
198 |
fe_add(r->Z, t0, r->T); |
199 |
fe_sub(r->T, t0, r->T); |
200 |
} |
201 |
|
202 |
|
203 |
/* |
204 |
r = p - q |
205 |
*/ |
206 |
|
207 |
void ge_msub(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) { |
208 |
fe t0; |
209 |
|
210 |
fe_add(r->X, p->Y, p->X); |
211 |
fe_sub(r->Y, p->Y, p->X); |
212 |
fe_mul(r->Z, r->X, q->yminusx); |
213 |
fe_mul(r->Y, r->Y, q->yplusx); |
214 |
fe_mul(r->T, q->xy2d, p->T); |
215 |
fe_add(t0, p->Z, p->Z); |
216 |
fe_sub(r->X, r->Z, r->Y); |
217 |
fe_add(r->Y, r->Z, r->Y); |
218 |
fe_sub(r->Z, t0, r->T); |
219 |
fe_add(r->T, t0, r->T); |
220 |
} |
221 |
|
222 |
|
223 |
/* |
224 |
r = p |
225 |
*/ |
226 |
|
227 |
void ge_p1p1_to_p2(ge_p2 *r, const ge_p1p1 *p) { |
228 |
fe_mul(r->X, p->X, p->T); |
229 |
fe_mul(r->Y, p->Y, p->Z); |
230 |
fe_mul(r->Z, p->Z, p->T); |
231 |
} |
232 |
|
233 |
|
234 |
|
235 |
/* |
236 |
r = p |
237 |
*/ |
238 |
|
239 |
void ge_p1p1_to_p3(ge_p3 *r, const ge_p1p1 *p) { |
240 |
fe_mul(r->X, p->X, p->T); |
241 |
fe_mul(r->Y, p->Y, p->Z); |
242 |
fe_mul(r->Z, p->Z, p->T); |
243 |
fe_mul(r->T, p->X, p->Y); |
244 |
} |
245 |
|
246 |
|
247 |
void ge_p2_0(ge_p2 *h) { |
248 |
fe_0(h->X); |
249 |
fe_1(h->Y); |
250 |
fe_1(h->Z); |
251 |
} |
252 |
|
253 |
|
254 |
|
255 |
/* |
256 |
r = 2 * p |
257 |
*/ |
258 |
|
259 |
void ge_p2_dbl(ge_p1p1 *r, const ge_p2 *p) { |
260 |
fe t0; |
261 |
|
262 |
fe_sq(r->X, p->X); |
263 |
fe_sq(r->Z, p->Y); |
264 |
fe_sq2(r->T, p->Z); |
265 |
fe_add(r->Y, p->X, p->Y); |
266 |
fe_sq(t0, r->Y); |
267 |
fe_add(r->Y, r->Z, r->X); |
268 |
fe_sub(r->Z, r->Z, r->X); |
269 |
fe_sub(r->X, t0, r->Y); |
270 |
fe_sub(r->T, r->T, r->Z); |
271 |
} |
272 |
|
273 |
|
274 |
void ge_p3_0(ge_p3 *h) { |
275 |
fe_0(h->X); |
276 |
fe_1(h->Y); |
277 |
fe_1(h->Z); |
278 |
fe_0(h->T); |
279 |
} |
280 |
|
281 |
|
282 |
/* |
283 |
r = 2 * p |
284 |
*/ |
285 |
|
286 |
void ge_p3_dbl(ge_p1p1 *r, const ge_p3 *p) { |
287 |
ge_p2 q; |
288 |
ge_p3_to_p2(&q, p); |
289 |
ge_p2_dbl(r, &q); |
290 |
} |
291 |
|
292 |
|
293 |
|
294 |
/* |
295 |
r = p |
296 |
*/ |
297 |
|
298 |
static const fe d2 = { |
299 |
-21827239, -5839606, -30745221, 13898782, 229458, 15978800, -12551817, -6495438, 29715968, 9444199 |
300 |
}; |
301 |
|
302 |
void ge_p3_to_cached(ge_cached *r, const ge_p3 *p) { |
303 |
fe_add(r->YplusX, p->Y, p->X); |
304 |
fe_sub(r->YminusX, p->Y, p->X); |
305 |
fe_copy(r->Z, p->Z); |
306 |
fe_mul(r->T2d, p->T, d2); |
307 |
} |
308 |
|
309 |
|
310 |
/* |
311 |
r = p |
312 |
*/ |
313 |
|
314 |
void ge_p3_to_p2(ge_p2 *r, const ge_p3 *p) { |
315 |
fe_copy(r->X, p->X); |
316 |
fe_copy(r->Y, p->Y); |
317 |
fe_copy(r->Z, p->Z); |
318 |
} |
319 |
|
320 |
|
321 |
void ge_p3_tobytes(unsigned char *s, const ge_p3 *h) { |
322 |
fe recip; |
323 |
fe x; |
324 |
fe y; |
325 |
fe_invert(recip, h->Z); |
326 |
fe_mul(x, h->X, recip); |
327 |
fe_mul(y, h->Y, recip); |
328 |
fe_tobytes(s, y); |
329 |
s[31] ^= fe_isnegative(x) << 7; |
330 |
} |
331 |
|
332 |
|
333 |
static unsigned char equal(signed char b, signed char c) { |
334 |
unsigned char ub = b; |
335 |
unsigned char uc = c; |
336 |
unsigned char x = ub ^ uc; /* 0: yes; 1..255: no */ |
337 |
uint64_t y = x; /* 0: yes; 1..255: no */ |
338 |
y -= 1; /* large: yes; 0..254: no */ |
339 |
y >>= 63; /* 1: yes; 0: no */ |
340 |
return (unsigned char) y; |
341 |
} |
342 |
|
343 |
static unsigned char negative(signed char b) { |
344 |
uint64_t x = b; /* 18446744073709551361..18446744073709551615: yes; 0..255: no */ |
345 |
x >>= 63; /* 1: yes; 0: no */ |
346 |
return (unsigned char) x; |
347 |
} |
348 |
|
349 |
static void cmov(ge_precomp *t, const ge_precomp *u, unsigned char b) { |
350 |
fe_cmov(t->yplusx, u->yplusx, b); |
351 |
fe_cmov(t->yminusx, u->yminusx, b); |
352 |
fe_cmov(t->xy2d, u->xy2d, b); |
353 |
} |
354 |
|
355 |
|
356 |
static void select(ge_precomp *t, int pos, signed char b) { |
357 |
ge_precomp minust; |
358 |
unsigned char bnegative = negative(b); |
359 |
unsigned char babs = b - (((-bnegative) & b) << 1); |
360 |
fe_1(t->yplusx); |
361 |
fe_1(t->yminusx); |
362 |
fe_0(t->xy2d); |
363 |
cmov(t, &base[pos][0], equal(babs, 1)); |
364 |
cmov(t, &base[pos][1], equal(babs, 2)); |
365 |
cmov(t, &base[pos][2], equal(babs, 3)); |
366 |
cmov(t, &base[pos][3], equal(babs, 4)); |
367 |
cmov(t, &base[pos][4], equal(babs, 5)); |
368 |
cmov(t, &base[pos][5], equal(babs, 6)); |
369 |
cmov(t, &base[pos][6], equal(babs, 7)); |
370 |
cmov(t, &base[pos][7], equal(babs, 8)); |
371 |
fe_copy(minust.yplusx, t->yminusx); |
372 |
fe_copy(minust.yminusx, t->yplusx); |
373 |
fe_neg(minust.xy2d, t->xy2d); |
374 |
cmov(t, &minust, bnegative); |
375 |
} |
376 |
|
377 |
/* |
378 |
h = a * B |
379 |
where a = a[0]+256*a[1]+...+256^31 a[31] |
380 |
B is the Ed25519 base point (x,4/5) with x positive. |
381 |
|
382 |
Preconditions: |
383 |
a[31] <= 127 |
384 |
*/ |
385 |
|
386 |
void ge_scalarmult_base(ge_p3 *h, const unsigned char *a) { |
387 |
signed char e[64]; |
388 |
signed char carry; |
389 |
ge_p1p1 r; |
390 |
ge_p2 s; |
391 |
ge_precomp t; |
392 |
int i; |
393 |
|
394 |
for (i = 0; i < 32; ++i) { |
395 |
e[2 * i + 0] = (a[i] >> 0) & 15; |
396 |
e[2 * i + 1] = (a[i] >> 4) & 15; |
397 |
} |
398 |
|
399 |
/* each e[i] is between 0 and 15 */ |
400 |
/* e[63] is between 0 and 7 */ |
401 |
carry = 0; |
402 |
|
403 |
for (i = 0; i < 63; ++i) { |
404 |
e[i] += carry; |
405 |
carry = e[i] + 8; |
406 |
carry >>= 4; |
407 |
e[i] -= carry << 4; |
408 |
} |
409 |
|
410 |
e[63] += carry; |
411 |
/* each e[i] is between -8 and 8 */ |
412 |
ge_p3_0(h); |
413 |
|
414 |
for (i = 1; i < 64; i += 2) { |
415 |
select(&t, i / 2, e[i]); |
416 |
ge_madd(&r, h, &t); |
417 |
ge_p1p1_to_p3(h, &r); |
418 |
} |
419 |
|
420 |
ge_p3_dbl(&r, h); |
421 |
ge_p1p1_to_p2(&s, &r); |
422 |
ge_p2_dbl(&r, &s); |
423 |
ge_p1p1_to_p2(&s, &r); |
424 |
ge_p2_dbl(&r, &s); |
425 |
ge_p1p1_to_p2(&s, &r); |
426 |
ge_p2_dbl(&r, &s); |
427 |
ge_p1p1_to_p3(h, &r); |
428 |
|
429 |
for (i = 0; i < 64; i += 2) { |
430 |
select(&t, i / 2, e[i]); |
431 |
ge_madd(&r, h, &t); |
432 |
ge_p1p1_to_p3(h, &r); |
433 |
} |
434 |
} |
435 |
|
436 |
|
437 |
/* |
438 |
r = p - q |
439 |
*/ |
440 |
|
441 |
void ge_sub(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) { |
442 |
fe t0; |
443 |
|
444 |
fe_add(r->X, p->Y, p->X); |
445 |
fe_sub(r->Y, p->Y, p->X); |
446 |
fe_mul(r->Z, r->X, q->YminusX); |
447 |
fe_mul(r->Y, r->Y, q->YplusX); |
448 |
fe_mul(r->T, q->T2d, p->T); |
449 |
fe_mul(r->X, p->Z, q->Z); |
450 |
fe_add(t0, r->X, r->X); |
451 |
fe_sub(r->X, r->Z, r->Y); |
452 |
fe_add(r->Y, r->Z, r->Y); |
453 |
fe_sub(r->Z, t0, r->T); |
454 |
fe_add(r->T, t0, r->T); |
455 |
} |
456 |
|
457 |
|
458 |
void ge_tobytes(unsigned char *s, const ge_p2 *h) { |
459 |
fe recip; |
460 |
fe x; |
461 |
fe y; |
462 |
fe_invert(recip, h->Z); |
463 |
fe_mul(x, h->X, recip); |
464 |
fe_mul(y, h->Y, recip); |
465 |
fe_tobytes(s, y); |
466 |
s[31] ^= fe_isnegative(x) << 7; |
467 |
} |