1#include "ge.h"
2#include "precomp_data.h"
3
4
5/*
6r = p + q
7*/
8
9void 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
25static 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/*
61r = a * A + b * B
62where a = a[0]+256*a[1]+...+256^31 a[31].
63and b = b[0]+256*b[1]+...+256^31 b[31].
64B is the Ed25519 base point (x,4/5) with x positive.
65*/
66
67void 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
133static const fe d = {
134 -10913610, 13857413, -15372611, 6949391, 114729, -8787816, -6275908, -3247719, -18696448, -12055116
135};
136
137static const fe sqrtm1 = {
138 -32595792, -7943725, 9377950, 3500415, 12389472, -272473, -25146209, -2005654, 326686, 11406482
139};
140
141int 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/*
185r = p + q
186*/
187
188void 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/*
204r = p - q
205*/
206
207void 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/*
224r = p
225*/
226
227void 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/*
236r = p
237*/
238
239void 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
247void 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/*
256r = 2 * p
257*/
258
259void 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
274void 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/*
283r = 2 * p
284*/
285
286void 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/*
295r = p
296*/
297
298static const fe d2 = {
299 -21827239, -5839606, -30745221, 13898782, 229458, 15978800, -12551817, -6495438, 29715968, 9444199
300};
301
302void 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/*
311r = p
312*/
313
314void 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
321void 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
333static 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
343static 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
349static 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
356static 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/*
378h = a * B
379where a = a[0]+256*a[1]+...+256^31 a[31]
380B is the Ed25519 base point (x,4/5) with x positive.
381
382Preconditions:
383 a[31] <= 127
384*/
385
386void 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/*
438r = p - q
439*/
440
441void 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
458void 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