Prevent sptps_test from sending overly large UDP packets.
[tinc] / src / ed25519 / ge.c
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, 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 - shlu8(((-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] -= shl32(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 }