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(h: r->X, f: p->Y, g: p->X); |
12 | fe_sub(h: r->Y, f: p->Y, g: p->X); |
13 | fe_mul(h: r->Z, f: r->X, g: q->YplusX); |
14 | fe_mul(h: r->Y, f: r->Y, g: q->YminusX); |
15 | fe_mul(h: r->T, f: q->T2d, g: p->T); |
16 | fe_mul(h: r->X, f: p->Z, g: q->Z); |
17 | fe_add(h: t0, f: r->X, g: r->X); |
18 | fe_sub(h: r->X, f: r->Z, g: r->Y); |
19 | fe_add(h: r->Y, f: r->Z, g: r->Y); |
20 | fe_add(h: r->Z, f: t0, g: r->T); |
21 | fe_sub(h: r->T, f: t0, g: 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(r: aslide, a); |
76 | slide(r: bslide, a: b); |
77 | ge_p3_to_cached(r: &Ai[0], p: A); |
78 | ge_p3_dbl(r: &t, p: A); |
79 | ge_p1p1_to_p3(r: &A2, p: &t); |
80 | ge_add(r: &t, p: &A2, q: &Ai[0]); |
81 | ge_p1p1_to_p3(r: &u, p: &t); |
82 | ge_p3_to_cached(r: &Ai[1], p: &u); |
83 | ge_add(r: &t, p: &A2, q: &Ai[1]); |
84 | ge_p1p1_to_p3(r: &u, p: &t); |
85 | ge_p3_to_cached(r: &Ai[2], p: &u); |
86 | ge_add(r: &t, p: &A2, q: &Ai[2]); |
87 | ge_p1p1_to_p3(r: &u, p: &t); |
88 | ge_p3_to_cached(r: &Ai[3], p: &u); |
89 | ge_add(r: &t, p: &A2, q: &Ai[3]); |
90 | ge_p1p1_to_p3(r: &u, p: &t); |
91 | ge_p3_to_cached(r: &Ai[4], p: &u); |
92 | ge_add(r: &t, p: &A2, q: &Ai[4]); |
93 | ge_p1p1_to_p3(r: &u, p: &t); |
94 | ge_p3_to_cached(r: &Ai[5], p: &u); |
95 | ge_add(r: &t, p: &A2, q: &Ai[5]); |
96 | ge_p1p1_to_p3(r: &u, p: &t); |
97 | ge_p3_to_cached(r: &Ai[6], p: &u); |
98 | ge_add(r: &t, p: &A2, q: &Ai[6]); |
99 | ge_p1p1_to_p3(r: &u, p: &t); |
100 | ge_p3_to_cached(r: &Ai[7], p: &u); |
101 | ge_p2_0(h: 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(r: &t, p: r); |
111 | |
112 | if (aslide[i] > 0) { |
113 | ge_p1p1_to_p3(r: &u, p: &t); |
114 | ge_add(r: &t, p: &u, q: &Ai[aslide[i] / 2]); |
115 | } else if (aslide[i] < 0) { |
116 | ge_p1p1_to_p3(r: &u, p: &t); |
117 | ge_sub(r: &t, p: &u, q: &Ai[(-aslide[i]) / 2]); |
118 | } |
119 | |
120 | if (bslide[i] > 0) { |
121 | ge_p1p1_to_p3(r: &u, p: &t); |
122 | ge_madd(r: &t, p: &u, q: &Bi[bslide[i] / 2]); |
123 | } else if (bslide[i] < 0) { |
124 | ge_p1p1_to_p3(r: &u, p: &t); |
125 | ge_msub(r: &t, p: &u, q: &Bi[(-bslide[i]) / 2]); |
126 | } |
127 | |
128 | ge_p1p1_to_p2(r, p: &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: h->Y, s); |
148 | fe_1(h: h->Z); |
149 | fe_sq(h: u, f: h->Y); |
150 | fe_mul(h: v, f: u, g: d); |
151 | fe_sub(h: u, f: u, g: h->Z); /* u = y^2-1 */ |
152 | fe_add(h: v, f: v, g: h->Z); /* v = dy^2+1 */ |
153 | fe_sq(h: v3, f: v); |
154 | fe_mul(h: v3, f: v3, g: v); /* v3 = v^3 */ |
155 | fe_sq(h: h->X, f: v3); |
156 | fe_mul(h: h->X, f: h->X, g: v); |
157 | fe_mul(h: h->X, f: h->X, g: u); /* x = uv^7 */ |
158 | fe_pow22523(out: h->X, z: h->X); /* x = (uv^7)^((q-5)/8) */ |
159 | fe_mul(h: h->X, f: h->X, g: v3); |
160 | fe_mul(h: h->X, f: h->X, g: u); /* x = uv^3(uv^7)^((q-5)/8) */ |
161 | fe_sq(h: vxx, f: h->X); |
162 | fe_mul(h: vxx, f: vxx, g: v); |
163 | fe_sub(h: check, f: vxx, g: u); /* vx^2-u */ |
164 | |
165 | if (fe_isnonzero(f: check)) { |
166 | fe_add(h: check, f: vxx, g: u); /* vx^2+u */ |
167 | |
168 | if (fe_isnonzero(f: check)) { |
169 | return -1; |
170 | } |
171 | |
172 | fe_mul(h: h->X, f: h->X, g: sqrtm1); |
173 | } |
174 | |
175 | if (fe_isnegative(f: h->X) == (s[31] >> 7)) { |
176 | fe_neg(h: h->X, f: h->X); |
177 | } |
178 | |
179 | fe_mul(h: h->T, f: h->X, g: 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(h: r->X, f: p->Y, g: p->X); |
191 | fe_sub(h: r->Y, f: p->Y, g: p->X); |
192 | fe_mul(h: r->Z, f: r->X, g: q->yplusx); |
193 | fe_mul(h: r->Y, f: r->Y, g: q->yminusx); |
194 | fe_mul(h: r->T, f: q->xy2d, g: p->T); |
195 | fe_add(h: t0, f: p->Z, g: p->Z); |
196 | fe_sub(h: r->X, f: r->Z, g: r->Y); |
197 | fe_add(h: r->Y, f: r->Z, g: r->Y); |
198 | fe_add(h: r->Z, f: t0, g: r->T); |
199 | fe_sub(h: r->T, f: t0, g: 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(h: r->X, f: p->Y, g: p->X); |
211 | fe_sub(h: r->Y, f: p->Y, g: p->X); |
212 | fe_mul(h: r->Z, f: r->X, g: q->yminusx); |
213 | fe_mul(h: r->Y, f: r->Y, g: q->yplusx); |
214 | fe_mul(h: r->T, f: q->xy2d, g: p->T); |
215 | fe_add(h: t0, f: p->Z, g: p->Z); |
216 | fe_sub(h: r->X, f: r->Z, g: r->Y); |
217 | fe_add(h: r->Y, f: r->Z, g: r->Y); |
218 | fe_sub(h: r->Z, f: t0, g: r->T); |
219 | fe_add(h: r->T, f: t0, g: 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(h: r->X, f: p->X, g: p->T); |
229 | fe_mul(h: r->Y, f: p->Y, g: p->Z); |
230 | fe_mul(h: r->Z, f: p->Z, g: 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(h: r->X, f: p->X, g: p->T); |
241 | fe_mul(h: r->Y, f: p->Y, g: p->Z); |
242 | fe_mul(h: r->Z, f: p->Z, g: p->T); |
243 | fe_mul(h: r->T, f: p->X, g: p->Y); |
244 | } |
245 | |
246 | |
247 | void ge_p2_0(ge_p2 *h) { |
248 | fe_0(h: h->X); |
249 | fe_1(h: h->Y); |
250 | fe_1(h: 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(h: r->X, f: p->X); |
263 | fe_sq(h: r->Z, f: p->Y); |
264 | fe_sq2(h: r->T, f: p->Z); |
265 | fe_add(h: r->Y, f: p->X, g: p->Y); |
266 | fe_sq(h: t0, f: r->Y); |
267 | fe_add(h: r->Y, f: r->Z, g: r->X); |
268 | fe_sub(h: r->Z, f: r->Z, g: r->X); |
269 | fe_sub(h: r->X, f: t0, g: r->Y); |
270 | fe_sub(h: r->T, f: r->T, g: r->Z); |
271 | } |
272 | |
273 | |
274 | void ge_p3_0(ge_p3 *h) { |
275 | fe_0(h: h->X); |
276 | fe_1(h: h->Y); |
277 | fe_1(h: h->Z); |
278 | fe_0(h: 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(r: &q, p); |
289 | ge_p2_dbl(r, p: &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(h: r->YplusX, f: p->Y, g: p->X); |
304 | fe_sub(h: r->YminusX, f: p->Y, g: p->X); |
305 | fe_copy(h: r->Z, f: p->Z); |
306 | fe_mul(h: r->T2d, f: p->T, g: 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(h: r->X, f: p->X); |
316 | fe_copy(h: r->Y, f: p->Y); |
317 | fe_copy(h: r->Z, f: 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(out: recip, z: h->Z); |
326 | fe_mul(h: x, f: h->X, g: recip); |
327 | fe_mul(h: y, f: h->Y, g: recip); |
328 | fe_tobytes(s, h: y); |
329 | s[31] ^= fe_isnegative(f: 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, ge_precomp *u, unsigned char b) { |
350 | fe_cmov(f: t->yplusx, g: u->yplusx, b); |
351 | fe_cmov(f: t->yminusx, g: u->yminusx, b); |
352 | fe_cmov(f: t->xy2d, g: 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(h: t->yplusx); |
361 | fe_1(h: t->yminusx); |
362 | fe_0(h: t->xy2d); |
363 | cmov(t, u: &base[pos][0], b: equal(b: babs, c: 1)); |
364 | cmov(t, u: &base[pos][1], b: equal(b: babs, c: 2)); |
365 | cmov(t, u: &base[pos][2], b: equal(b: babs, c: 3)); |
366 | cmov(t, u: &base[pos][3], b: equal(b: babs, c: 4)); |
367 | cmov(t, u: &base[pos][4], b: equal(b: babs, c: 5)); |
368 | cmov(t, u: &base[pos][5], b: equal(b: babs, c: 6)); |
369 | cmov(t, u: &base[pos][6], b: equal(b: babs, c: 7)); |
370 | cmov(t, u: &base[pos][7], b: equal(b: babs, c: 8)); |
371 | fe_copy(h: minust.yplusx, f: t->yminusx); |
372 | fe_copy(h: minust.yminusx, f: t->yplusx); |
373 | fe_neg(h: minust.xy2d, f: t->xy2d); |
374 | cmov(t, u: &minust, b: 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: &t, pos: i / 2, b: e[i]); |
416 | ge_madd(r: &r, p: h, q: &t); |
417 | ge_p1p1_to_p3(r: h, p: &r); |
418 | } |
419 | |
420 | ge_p3_dbl(r: &r, p: h); |
421 | ge_p1p1_to_p2(r: &s, p: &r); |
422 | ge_p2_dbl(r: &r, p: &s); |
423 | ge_p1p1_to_p2(r: &s, p: &r); |
424 | ge_p2_dbl(r: &r, p: &s); |
425 | ge_p1p1_to_p2(r: &s, p: &r); |
426 | ge_p2_dbl(r: &r, p: &s); |
427 | ge_p1p1_to_p3(r: h, p: &r); |
428 | |
429 | for (i = 0; i < 64; i += 2) { |
430 | select(t: &t, pos: i / 2, b: e[i]); |
431 | ge_madd(r: &r, p: h, q: &t); |
432 | ge_p1p1_to_p3(r: h, p: &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(h: r->X, f: p->Y, g: p->X); |
445 | fe_sub(h: r->Y, f: p->Y, g: p->X); |
446 | fe_mul(h: r->Z, f: r->X, g: q->YminusX); |
447 | fe_mul(h: r->Y, f: r->Y, g: q->YplusX); |
448 | fe_mul(h: r->T, f: q->T2d, g: p->T); |
449 | fe_mul(h: r->X, f: p->Z, g: q->Z); |
450 | fe_add(h: t0, f: r->X, g: r->X); |
451 | fe_sub(h: r->X, f: r->Z, g: r->Y); |
452 | fe_add(h: r->Y, f: r->Z, g: r->Y); |
453 | fe_sub(h: r->Z, f: t0, g: r->T); |
454 | fe_add(h: r->T, f: t0, g: 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(out: recip, z: h->Z); |
463 | fe_mul(h: x, f: h->X, g: recip); |
464 | fe_mul(h: y, f: h->Y, g: recip); |
465 | fe_tobytes(s, h: y); |
466 | s[31] ^= fe_isnegative(f: x) << 7; |
467 | } |
468 | |