1 /* Copyright (c) 2020, Google Inc.
2 *
3 * Permission to use, copy, modify, and/or distribute this software for any
4 * purpose with or without fee is hereby granted, provided that the above
5 * copyright notice and this permission notice appear in all copies.
6 *
7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
10 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
14
15 // Some of this code is taken from the ref10 version of Ed25519 in SUPERCOP
16 // 20141124 (http://bench.cr.yp.to/supercop.html). That code is released as
17 // public domain. Other parts have been replaced to call into code generated by
18 // Fiat (https://github.com/mit-plv/fiat-crypto) in //third_party/fiat.
19 //
20 // The field functions are shared by Ed25519 and X25519 where possible.
21
22 #include <GFp/mem.h>
23
24 #include "internal.h"
25 #include "../internal.h"
26
27 #if defined(_MSC_VER) && !defined(__clang__)
28 // '=': conversion from 'int64_t' to 'int32_t', possible loss of data
29 #pragma warning(disable: 4242)
30 // '=': conversion from 'int32_t' to 'uint8_t', possible loss of data
31 #pragma warning(disable: 4244)
32 #endif
33
34 #if defined(__GNUC__)
35 #pragma GCC diagnostic ignored "-Wconversion"
36 #pragma GCC diagnostic ignored "-Wsign-conversion"
37 #endif
38
39 // Various pre-computed constants.
40 #include "./curve25519_tables.h"
41
42 #if defined(BORINGSSL_CURVE25519_64BIT)
43 #if defined(__GNUC__)
44 #pragma GCC diagnostic ignored "-Wpedantic"
45 #endif
46 #include "../../third_party/fiat/curve25519_64.h"
47 #else
48 #include "../../third_party/fiat/curve25519_32.h"
49 #endif // BORINGSSL_CURVE25519_64BIT
50
51
52 // Low-level intrinsic operations
53
load_3(const uint8_t * in)54 static uint64_t load_3(const uint8_t *in) {
55 uint64_t result;
56 result = (uint64_t)in[0];
57 result |= ((uint64_t)in[1]) << 8;
58 result |= ((uint64_t)in[2]) << 16;
59 return result;
60 }
61
load_4(const uint8_t * in)62 static uint64_t load_4(const uint8_t *in) {
63 uint64_t result;
64 result = (uint64_t)in[0];
65 result |= ((uint64_t)in[1]) << 8;
66 result |= ((uint64_t)in[2]) << 16;
67 result |= ((uint64_t)in[3]) << 24;
68 return result;
69 }
70
71
72 // Field operations.
73
74 #if defined(BORINGSSL_CURVE25519_64BIT)
75
76 // assert_fe asserts that |f| satisfies bounds:
77 //
78 // [[0x0 ~> 0x8cccccccccccc],
79 // [0x0 ~> 0x8cccccccccccc],
80 // [0x0 ~> 0x8cccccccccccc],
81 // [0x0 ~> 0x8cccccccccccc],
82 // [0x0 ~> 0x8cccccccccccc]]
83 //
84 // See comments in curve25519_64.h for which functions use these bounds for
85 // inputs or outputs.
86 #define assert_fe(f) \
87 do { \
88 for (unsigned _assert_fe_i = 0; _assert_fe_i < 5; _assert_fe_i++) { \
89 dev_assert_secret(f[_assert_fe_i] <= UINT64_C(0x8cccccccccccc)); \
90 } \
91 } while (0)
92
93 // assert_fe_loose asserts that |f| satisfies bounds:
94 //
95 // [[0x0 ~> 0x1a666666666664],
96 // [0x0 ~> 0x1a666666666664],
97 // [0x0 ~> 0x1a666666666664],
98 // [0x0 ~> 0x1a666666666664],
99 // [0x0 ~> 0x1a666666666664]]
100 //
101 // See comments in curve25519_64.h for which functions use these bounds for
102 // inputs or outputs.
103 #define assert_fe_loose(f) \
104 do { \
105 for (unsigned _assert_fe_i = 0; _assert_fe_i < 5; _assert_fe_i++) { \
106 dev_assert_secret(f[_assert_fe_i] <= UINT64_C(0x1a666666666664)); \
107 } \
108 } while (0)
109
110 #else
111
112 // assert_fe asserts that |f| satisfies bounds:
113 //
114 // [[0x0 ~> 0x4666666], [0x0 ~> 0x2333333],
115 // [0x0 ~> 0x4666666], [0x0 ~> 0x2333333],
116 // [0x0 ~> 0x4666666], [0x0 ~> 0x2333333],
117 // [0x0 ~> 0x4666666], [0x0 ~> 0x2333333],
118 // [0x0 ~> 0x4666666], [0x0 ~> 0x2333333]]
119 //
120 // See comments in curve25519_32.h for which functions use these bounds for
121 // inputs or outputs.
122 #define assert_fe(f) \
123 do { \
124 for (unsigned _assert_fe_i = 0; _assert_fe_i < 10; _assert_fe_i++) { \
125 dev_assert_secret(f[_assert_fe_i] <= \
126 ((_assert_fe_i & 1) ? 0x2333333u : 0x4666666u)); \
127 } \
128 } while (0)
129
130 // assert_fe_loose asserts that |f| satisfies bounds:
131 //
132 // [[0x0 ~> 0xd333332], [0x0 ~> 0x6999999],
133 // [0x0 ~> 0xd333332], [0x0 ~> 0x6999999],
134 // [0x0 ~> 0xd333332], [0x0 ~> 0x6999999],
135 // [0x0 ~> 0xd333332], [0x0 ~> 0x6999999],
136 // [0x0 ~> 0xd333332], [0x0 ~> 0x6999999]]
137 //
138 // See comments in curve25519_32.h for which functions use these bounds for
139 // inputs or outputs.
140 #define assert_fe_loose(f) \
141 do { \
142 for (unsigned _assert_fe_i = 0; _assert_fe_i < 10; _assert_fe_i++) { \
143 dev_assert_secret(f[_assert_fe_i] <= \
144 ((_assert_fe_i & 1) ? 0x6999999u : 0xd333332u)); \
145 } \
146 } while (0)
147
148 #endif // BORINGSSL_CURVE25519_64BIT
149
150 OPENSSL_STATIC_ASSERT(sizeof(fe) == sizeof(fe_limb_t) * FE_NUM_LIMBS,
151 "fe_limb_t[FE_NUM_LIMBS] is inconsistent with fe");
152
fe_frombytes_strict(fe * h,const uint8_t s[32])153 static void fe_frombytes_strict(fe *h, const uint8_t s[32]) {
154 // |fiat_25519_from_bytes| requires the top-most bit be clear.
155 dev_assert_secret((s[31] & 0x80) == 0);
156 fiat_25519_from_bytes(h->v, s);
157 assert_fe(h->v);
158 }
159
fe_frombytes(fe * h,const uint8_t s[32])160 static void fe_frombytes(fe *h, const uint8_t s[32]) {
161 uint8_t s_copy[32];
162 GFp_memcpy(s_copy, s, 32);
163 s_copy[31] &= 0x7f;
164 fe_frombytes_strict(h, s_copy);
165 }
166
fe_tobytes(uint8_t s[32],const fe * f)167 static void fe_tobytes(uint8_t s[32], const fe *f) {
168 assert_fe(f->v);
169 fiat_25519_to_bytes(s, f->v);
170 }
171
172 // h = 0
fe_0(fe * h)173 static void fe_0(fe *h) {
174 GFp_memset(h, 0, sizeof(fe));
175 }
176
fe_loose_0(fe_loose * h)177 static void fe_loose_0(fe_loose *h) {
178 GFp_memset(h, 0, sizeof(fe_loose));
179 }
180
181 // h = 1
fe_1(fe * h)182 static void fe_1(fe *h) {
183 GFp_memset(h, 0, sizeof(fe));
184 h->v[0] = 1;
185 }
186
fe_loose_1(fe_loose * h)187 static void fe_loose_1(fe_loose *h) {
188 GFp_memset(h, 0, sizeof(fe_loose));
189 h->v[0] = 1;
190 }
191
192 // h = f + g
193 // Can overlap h with f or g.
fe_add(fe_loose * h,const fe * f,const fe * g)194 static void fe_add(fe_loose *h, const fe *f, const fe *g) {
195 assert_fe(f->v);
196 assert_fe(g->v);
197 fiat_25519_add(h->v, f->v, g->v);
198 assert_fe_loose(h->v);
199 }
200
201 // h = f - g
202 // Can overlap h with f or g.
fe_sub(fe_loose * h,const fe * f,const fe * g)203 static void fe_sub(fe_loose *h, const fe *f, const fe *g) {
204 assert_fe(f->v);
205 assert_fe(g->v);
206 fiat_25519_sub(h->v, f->v, g->v);
207 assert_fe_loose(h->v);
208 }
209
fe_carry(fe * h,const fe_loose * f)210 static void fe_carry(fe *h, const fe_loose* f) {
211 assert_fe_loose(f->v);
212 fiat_25519_carry(h->v, f->v);
213 assert_fe(h->v);
214 }
215
fe_mul_impl(fe_limb_t out[FE_NUM_LIMBS],const fe_limb_t in1[FE_NUM_LIMBS],const fe_limb_t in2[FE_NUM_LIMBS])216 static void fe_mul_impl(fe_limb_t out[FE_NUM_LIMBS],
217 const fe_limb_t in1[FE_NUM_LIMBS],
218 const fe_limb_t in2[FE_NUM_LIMBS]) {
219 assert_fe_loose(in1);
220 assert_fe_loose(in2);
221 fiat_25519_carry_mul(out, in1, in2);
222 assert_fe(out);
223 }
224
fe_mul_ltt(fe_loose * h,const fe * f,const fe * g)225 static void fe_mul_ltt(fe_loose *h, const fe *f, const fe *g) {
226 fe_mul_impl(h->v, f->v, g->v);
227 }
228
229 // static void fe_mul_llt(fe_loose *h, const fe_loose *f, const fe *g) was
230 // removed. This comment is here to make diffs vs. BoringSSL easier to read.
231
232
fe_mul_ttt(fe * h,const fe * f,const fe * g)233 static void fe_mul_ttt(fe *h, const fe *f, const fe *g) {
234 fe_mul_impl(h->v, f->v, g->v);
235 }
236
fe_mul_tlt(fe * h,const fe_loose * f,const fe * g)237 static void fe_mul_tlt(fe *h, const fe_loose *f, const fe *g) {
238 fe_mul_impl(h->v, f->v, g->v);
239 }
240
fe_mul_ttl(fe * h,const fe * f,const fe_loose * g)241 static void fe_mul_ttl(fe *h, const fe *f, const fe_loose *g) {
242 fe_mul_impl(h->v, f->v, g->v);
243 }
244
fe_mul_tll(fe * h,const fe_loose * f,const fe_loose * g)245 static void fe_mul_tll(fe *h, const fe_loose *f, const fe_loose *g) {
246 fe_mul_impl(h->v, f->v, g->v);
247 }
248
fe_sq_tl(fe * h,const fe_loose * f)249 static void fe_sq_tl(fe *h, const fe_loose *f) {
250 assert_fe_loose(f->v);
251 fiat_25519_carry_square(h->v, f->v);
252 assert_fe(h->v);
253 }
254
fe_sq_tt(fe * h,const fe * f)255 static void fe_sq_tt(fe *h, const fe *f) {
256 assert_fe_loose(f->v);
257 fiat_25519_carry_square(h->v, f->v);
258 assert_fe(h->v);
259 }
260
261 // Replace (f,g) with (g,f) if b == 1;
262 // replace (f,g) with (f,g) if b == 0.
263 //
264 // Preconditions: b in {0,1}.
fe_cswap(fe * f,fe * g,fe_limb_t b)265 static void fe_cswap(fe *f, fe *g, fe_limb_t b) {
266 b = 0-b;
267 for (unsigned i = 0; i < FE_NUM_LIMBS; i++) {
268 fe_limb_t x = f->v[i] ^ g->v[i];
269 x &= b;
270 f->v[i] ^= x;
271 g->v[i] ^= x;
272 }
273 }
274
fe_mul121666(fe * h,const fe_loose * f)275 static void fe_mul121666(fe *h, const fe_loose *f) {
276 assert_fe_loose(f->v);
277 fiat_25519_carry_scmul_121666(h->v, f->v);
278 assert_fe(h->v);
279 }
280
281 // h = -f
fe_neg(fe_loose * h,const fe * f)282 static void fe_neg(fe_loose *h, const fe *f) {
283 assert_fe(f->v);
284 fiat_25519_opp(h->v, f->v);
285 assert_fe_loose(h->v);
286 }
287
288 // Replace (f,g) with (g,g) if b == 1;
289 // replace (f,g) with (f,g) if b == 0.
290 //
291 // Preconditions: b in {0,1}.
fe_cmov(fe_loose * f,const fe_loose * g,fe_limb_t b)292 static void fe_cmov(fe_loose *f, const fe_loose *g, fe_limb_t b) {
293 // Silence an unused function warning. |fiat_25519_selectznz| isn't quite the
294 // calling convention the rest of this code wants, so implement it by hand.
295 //
296 // TODO(davidben): Switch to fiat's calling convention, or ask fiat to emit a
297 // different one.
298 (void)fiat_25519_selectznz;
299
300 b = 0-b;
301 for (unsigned i = 0; i < FE_NUM_LIMBS; i++) {
302 fe_limb_t x = f->v[i] ^ g->v[i];
303 x &= b;
304 f->v[i] ^= x;
305 }
306 }
307
308 // h = f
fe_copy(fe * h,const fe * f)309 static void fe_copy(fe *h, const fe *f) {
310 fe_limbs_copy(h->v, f->v);
311 }
312
fe_copy_lt(fe_loose * h,const fe * f)313 static void fe_copy_lt(fe_loose *h, const fe *f) {
314 fe_limbs_copy(h->v, f->v);
315 }
316 #if !defined(OPENSSL_SMALL)
fe_copy_ll(fe_loose * h,const fe_loose * f)317 static void fe_copy_ll(fe_loose *h, const fe_loose *f) {
318 fe_limbs_copy(h->v, f->v);
319 }
320 #endif // !defined(OPENSSL_SMALL)
321
fe_loose_invert(fe * out,const fe_loose * z)322 static void fe_loose_invert(fe *out, const fe_loose *z) {
323 fe t0;
324 fe t1;
325 fe t2;
326 fe t3;
327 int i;
328
329 fe_sq_tl(&t0, z);
330 fe_sq_tt(&t1, &t0);
331 for (i = 1; i < 2; ++i) {
332 fe_sq_tt(&t1, &t1);
333 }
334 fe_mul_tlt(&t1, z, &t1);
335 fe_mul_ttt(&t0, &t0, &t1);
336 fe_sq_tt(&t2, &t0);
337 fe_mul_ttt(&t1, &t1, &t2);
338 fe_sq_tt(&t2, &t1);
339 for (i = 1; i < 5; ++i) {
340 fe_sq_tt(&t2, &t2);
341 }
342 fe_mul_ttt(&t1, &t2, &t1);
343 fe_sq_tt(&t2, &t1);
344 for (i = 1; i < 10; ++i) {
345 fe_sq_tt(&t2, &t2);
346 }
347 fe_mul_ttt(&t2, &t2, &t1);
348 fe_sq_tt(&t3, &t2);
349 for (i = 1; i < 20; ++i) {
350 fe_sq_tt(&t3, &t3);
351 }
352 fe_mul_ttt(&t2, &t3, &t2);
353 fe_sq_tt(&t2, &t2);
354 for (i = 1; i < 10; ++i) {
355 fe_sq_tt(&t2, &t2);
356 }
357 fe_mul_ttt(&t1, &t2, &t1);
358 fe_sq_tt(&t2, &t1);
359 for (i = 1; i < 50; ++i) {
360 fe_sq_tt(&t2, &t2);
361 }
362 fe_mul_ttt(&t2, &t2, &t1);
363 fe_sq_tt(&t3, &t2);
364 for (i = 1; i < 100; ++i) {
365 fe_sq_tt(&t3, &t3);
366 }
367 fe_mul_ttt(&t2, &t3, &t2);
368 fe_sq_tt(&t2, &t2);
369 for (i = 1; i < 50; ++i) {
370 fe_sq_tt(&t2, &t2);
371 }
372 fe_mul_ttt(&t1, &t2, &t1);
373 fe_sq_tt(&t1, &t1);
374 for (i = 1; i < 5; ++i) {
375 fe_sq_tt(&t1, &t1);
376 }
377 fe_mul_ttt(out, &t1, &t0);
378 }
379
fe_invert(fe * out,const fe * z)380 static void fe_invert(fe *out, const fe *z) {
381 fe_loose l;
382 fe_copy_lt(&l, z);
383 fe_loose_invert(out, &l);
384 }
385
386 // return 0 if f == 0
387 // return 1 if f != 0
fe_isnonzero(const fe_loose * f)388 static int fe_isnonzero(const fe_loose *f) {
389 fe tight;
390 fe_carry(&tight, f);
391 uint8_t s[32];
392 fe_tobytes(s, &tight);
393
394 static const uint8_t zero[32] = {0};
395 return GFp_memcmp(s, zero, sizeof(zero)) != 0;
396 }
397
398 // return 1 if f is in {1,3,5,...,q-2}
399 // return 0 if f is in {0,2,4,...,q-1}
fe_isnegative(const fe * f)400 static int fe_isnegative(const fe *f) {
401 uint8_t s[32];
402 fe_tobytes(s, f);
403 return s[0] & 1;
404 }
405
fe_sq2_tt(fe * h,const fe * f)406 static void fe_sq2_tt(fe *h, const fe *f) {
407 // h = f^2
408 fe_sq_tt(h, f);
409
410 // h = h + h
411 fe_loose tmp;
412 fe_add(&tmp, h, h);
413 fe_carry(h, &tmp);
414 }
415
fe_pow22523(fe * out,const fe * z)416 static void fe_pow22523(fe *out, const fe *z) {
417 fe t0;
418 fe t1;
419 fe t2;
420 int i;
421
422 fe_sq_tt(&t0, z);
423 fe_sq_tt(&t1, &t0);
424 for (i = 1; i < 2; ++i) {
425 fe_sq_tt(&t1, &t1);
426 }
427 fe_mul_ttt(&t1, z, &t1);
428 fe_mul_ttt(&t0, &t0, &t1);
429 fe_sq_tt(&t0, &t0);
430 fe_mul_ttt(&t0, &t1, &t0);
431 fe_sq_tt(&t1, &t0);
432 for (i = 1; i < 5; ++i) {
433 fe_sq_tt(&t1, &t1);
434 }
435 fe_mul_ttt(&t0, &t1, &t0);
436 fe_sq_tt(&t1, &t0);
437 for (i = 1; i < 10; ++i) {
438 fe_sq_tt(&t1, &t1);
439 }
440 fe_mul_ttt(&t1, &t1, &t0);
441 fe_sq_tt(&t2, &t1);
442 for (i = 1; i < 20; ++i) {
443 fe_sq_tt(&t2, &t2);
444 }
445 fe_mul_ttt(&t1, &t2, &t1);
446 fe_sq_tt(&t1, &t1);
447 for (i = 1; i < 10; ++i) {
448 fe_sq_tt(&t1, &t1);
449 }
450 fe_mul_ttt(&t0, &t1, &t0);
451 fe_sq_tt(&t1, &t0);
452 for (i = 1; i < 50; ++i) {
453 fe_sq_tt(&t1, &t1);
454 }
455 fe_mul_ttt(&t1, &t1, &t0);
456 fe_sq_tt(&t2, &t1);
457 for (i = 1; i < 100; ++i) {
458 fe_sq_tt(&t2, &t2);
459 }
460 fe_mul_ttt(&t1, &t2, &t1);
461 fe_sq_tt(&t1, &t1);
462 for (i = 1; i < 50; ++i) {
463 fe_sq_tt(&t1, &t1);
464 }
465 fe_mul_ttt(&t0, &t1, &t0);
466 fe_sq_tt(&t0, &t0);
467 for (i = 1; i < 2; ++i) {
468 fe_sq_tt(&t0, &t0);
469 }
470 fe_mul_ttt(out, &t0, z);
471 }
472
473
474 // Group operations.
475
GFp_x25519_ge_frombytes_vartime(ge_p3 * h,const uint8_t s[32])476 int GFp_x25519_ge_frombytes_vartime(ge_p3 *h, const uint8_t s[32]) {
477 fe u;
478 fe_loose v;
479 fe v3;
480 fe vxx;
481 fe_loose check;
482
483 fe_frombytes(&h->Y, s);
484 fe_1(&h->Z);
485 fe_sq_tt(&v3, &h->Y);
486 fe_mul_ttt(&vxx, &v3, &d);
487 fe_sub(&v, &v3, &h->Z); // u = y^2-1
488 fe_carry(&u, &v);
489 fe_add(&v, &vxx, &h->Z); // v = dy^2+1
490
491 fe_sq_tl(&v3, &v);
492 fe_mul_ttl(&v3, &v3, &v); // v3 = v^3
493 fe_sq_tt(&h->X, &v3);
494 fe_mul_ttl(&h->X, &h->X, &v);
495 fe_mul_ttt(&h->X, &h->X, &u); // x = uv^7
496
497 fe_pow22523(&h->X, &h->X); // x = (uv^7)^((q-5)/8)
498 fe_mul_ttt(&h->X, &h->X, &v3);
499 fe_mul_ttt(&h->X, &h->X, &u); // x = uv^3(uv^7)^((q-5)/8)
500
501 fe_sq_tt(&vxx, &h->X);
502 fe_mul_ttl(&vxx, &vxx, &v);
503 fe_sub(&check, &vxx, &u);
504 if (fe_isnonzero(&check)) {
505 fe_add(&check, &vxx, &u);
506 if (fe_isnonzero(&check)) {
507 return 0;
508 }
509 fe_mul_ttt(&h->X, &h->X, &sqrtm1);
510 }
511
512 if (fe_isnegative(&h->X) != (s[31] >> 7)) {
513 fe_loose t;
514 fe_neg(&t, &h->X);
515 fe_carry(&h->X, &t);
516 }
517
518 fe_mul_ttt(&h->T, &h->X, &h->Y);
519 return 1;
520 }
521
ge_p2_0(ge_p2 * h)522 static void ge_p2_0(ge_p2 *h) {
523 fe_0(&h->X);
524 fe_1(&h->Y);
525 fe_1(&h->Z);
526 }
527
ge_p3_0(ge_p3 * h)528 static void ge_p3_0(ge_p3 *h) {
529 fe_0(&h->X);
530 fe_1(&h->Y);
531 fe_1(&h->Z);
532 fe_0(&h->T);
533 }
534
ge_precomp_0(ge_precomp * h)535 static void ge_precomp_0(ge_precomp *h) {
536 fe_loose_1(&h->yplusx);
537 fe_loose_1(&h->yminusx);
538 fe_loose_0(&h->xy2d);
539 }
540
541 // r = p
ge_p3_to_p2(ge_p2 * r,const ge_p3 * p)542 static void ge_p3_to_p2(ge_p2 *r, const ge_p3 *p) {
543 fe_copy(&r->X, &p->X);
544 fe_copy(&r->Y, &p->Y);
545 fe_copy(&r->Z, &p->Z);
546 }
547
548 // r = p
x25519_ge_p3_to_cached(ge_cached * r,const ge_p3 * p)549 static void x25519_ge_p3_to_cached(ge_cached *r, const ge_p3 *p) {
550 fe_add(&r->YplusX, &p->Y, &p->X);
551 fe_sub(&r->YminusX, &p->Y, &p->X);
552 fe_copy_lt(&r->Z, &p->Z);
553 fe_mul_ltt(&r->T2d, &p->T, &d2);
554 }
555
556 // r = p
x25519_ge_p1p1_to_p2(ge_p2 * r,const ge_p1p1 * p)557 static void x25519_ge_p1p1_to_p2(ge_p2 *r, const ge_p1p1 *p) {
558 fe_mul_tll(&r->X, &p->X, &p->T);
559 fe_mul_tll(&r->Y, &p->Y, &p->Z);
560 fe_mul_tll(&r->Z, &p->Z, &p->T);
561 }
562
563 // r = p
x25519_ge_p1p1_to_p3(ge_p3 * r,const ge_p1p1 * p)564 static void x25519_ge_p1p1_to_p3(ge_p3 *r, const ge_p1p1 *p) {
565 fe_mul_tll(&r->X, &p->X, &p->T);
566 fe_mul_tll(&r->Y, &p->Y, &p->Z);
567 fe_mul_tll(&r->Z, &p->Z, &p->T);
568 fe_mul_tll(&r->T, &p->X, &p->Y);
569 }
570
571 // r = 2 * p
ge_p2_dbl(ge_p1p1 * r,const ge_p2 * p)572 static void ge_p2_dbl(ge_p1p1 *r, const ge_p2 *p) {
573 fe trX, trZ, trT;
574 fe t0;
575
576 fe_sq_tt(&trX, &p->X);
577 fe_sq_tt(&trZ, &p->Y);
578 fe_sq2_tt(&trT, &p->Z);
579 fe_add(&r->Y, &p->X, &p->Y);
580 fe_sq_tl(&t0, &r->Y);
581
582 fe_add(&r->Y, &trZ, &trX);
583 fe_sub(&r->Z, &trZ, &trX);
584 fe_carry(&trZ, &r->Y);
585 fe_sub(&r->X, &t0, &trZ);
586 fe_carry(&trZ, &r->Z);
587 fe_sub(&r->T, &trT, &trZ);
588 }
589
590 // r = 2 * p
ge_p3_dbl(ge_p1p1 * r,const ge_p3 * p)591 static void ge_p3_dbl(ge_p1p1 *r, const ge_p3 *p) {
592 ge_p2 q;
593 ge_p3_to_p2(&q, p);
594 ge_p2_dbl(r, &q);
595 }
596
597 // r = p + q
ge_madd(ge_p1p1 * r,const ge_p3 * p,const ge_precomp * q)598 static void ge_madd(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) {
599 fe trY, trZ, trT;
600
601 fe_add(&r->X, &p->Y, &p->X);
602 fe_sub(&r->Y, &p->Y, &p->X);
603 fe_mul_tll(&trZ, &r->X, &q->yplusx);
604 fe_mul_tll(&trY, &r->Y, &q->yminusx);
605 fe_mul_tlt(&trT, &q->xy2d, &p->T);
606 fe_add(&r->T, &p->Z, &p->Z);
607 fe_sub(&r->X, &trZ, &trY);
608 fe_add(&r->Y, &trZ, &trY);
609 fe_carry(&trZ, &r->T);
610 fe_add(&r->Z, &trZ, &trT);
611 fe_sub(&r->T, &trZ, &trT);
612 }
613
614 // r = p - q
ge_msub(ge_p1p1 * r,const ge_p3 * p,const ge_precomp * q)615 static void ge_msub(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) {
616 fe trY, trZ, trT;
617
618 fe_add(&r->X, &p->Y, &p->X);
619 fe_sub(&r->Y, &p->Y, &p->X);
620 fe_mul_tll(&trZ, &r->X, &q->yminusx);
621 fe_mul_tll(&trY, &r->Y, &q->yplusx);
622 fe_mul_tlt(&trT, &q->xy2d, &p->T);
623 fe_add(&r->T, &p->Z, &p->Z);
624 fe_sub(&r->X, &trZ, &trY);
625 fe_add(&r->Y, &trZ, &trY);
626 fe_carry(&trZ, &r->T);
627 fe_sub(&r->Z, &trZ, &trT);
628 fe_add(&r->T, &trZ, &trT);
629 }
630
631 // r = p + q
x25519_ge_add(ge_p1p1 * r,const ge_p3 * p,const ge_cached * q)632 static void x25519_ge_add(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) {
633 fe trX, trY, trZ, trT;
634
635 fe_add(&r->X, &p->Y, &p->X);
636 fe_sub(&r->Y, &p->Y, &p->X);
637 fe_mul_tll(&trZ, &r->X, &q->YplusX);
638 fe_mul_tll(&trY, &r->Y, &q->YminusX);
639 fe_mul_tlt(&trT, &q->T2d, &p->T);
640 fe_mul_ttl(&trX, &p->Z, &q->Z);
641 fe_add(&r->T, &trX, &trX);
642 fe_sub(&r->X, &trZ, &trY);
643 fe_add(&r->Y, &trZ, &trY);
644 fe_carry(&trZ, &r->T);
645 fe_add(&r->Z, &trZ, &trT);
646 fe_sub(&r->T, &trZ, &trT);
647 }
648
649 // r = p - q
x25519_ge_sub(ge_p1p1 * r,const ge_p3 * p,const ge_cached * q)650 static void x25519_ge_sub(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) {
651 fe trX, trY, trZ, trT;
652
653 fe_add(&r->X, &p->Y, &p->X);
654 fe_sub(&r->Y, &p->Y, &p->X);
655 fe_mul_tll(&trZ, &r->X, &q->YminusX);
656 fe_mul_tll(&trY, &r->Y, &q->YplusX);
657 fe_mul_tlt(&trT, &q->T2d, &p->T);
658 fe_mul_ttl(&trX, &p->Z, &q->Z);
659 fe_add(&r->T, &trX, &trX);
660 fe_sub(&r->X, &trZ, &trY);
661 fe_add(&r->Y, &trZ, &trY);
662 fe_carry(&trZ, &r->T);
663 fe_sub(&r->Z, &trZ, &trT);
664 fe_add(&r->T, &trZ, &trT);
665 }
666
equal(signed char b,signed char c)667 static uint8_t equal(signed char b, signed char c) {
668 uint8_t ub = b;
669 uint8_t uc = c;
670 uint8_t x = ub ^ uc; // 0: yes; 1..255: no
671 uint32_t y = x; // 0: yes; 1..255: no
672 y -= 1; // 4294967295: yes; 0..254: no
673 y >>= 31; // 1: yes; 0: no
674 return y;
675 }
676
cmov(ge_precomp * t,const ge_precomp * u,uint8_t b)677 static void cmov(ge_precomp *t, const ge_precomp *u, uint8_t b) {
678 fe_cmov(&t->yplusx, &u->yplusx, b);
679 fe_cmov(&t->yminusx, &u->yminusx, b);
680 fe_cmov(&t->xy2d, &u->xy2d, b);
681 }
682
683 #if defined(OPENSSL_SMALL)
684
x25519_ge_scalarmult_small_precomp(ge_p3 * h,const uint8_t a[32],const uint8_t precomp_table[15* 2* 32])685 static void x25519_ge_scalarmult_small_precomp(
686 ge_p3 *h, const uint8_t a[32], const uint8_t precomp_table[15 * 2 * 32]) {
687 // precomp_table is first expanded into matching |ge_precomp|
688 // elements.
689 ge_precomp multiples[15];
690
691 unsigned i;
692 for (i = 0; i < 15; i++) {
693 // The precomputed table is assumed to already clear the top bit, so
694 // |fe_frombytes_strict| may be used directly.
695 const uint8_t *bytes = &precomp_table[i*(2 * 32)];
696 fe x, y;
697 fe_frombytes_strict(&x, bytes);
698 fe_frombytes_strict(&y, bytes + 32);
699
700 ge_precomp *out = &multiples[i];
701 fe_add(&out->yplusx, &y, &x);
702 fe_sub(&out->yminusx, &y, &x);
703 fe_mul_ltt(&out->xy2d, &x, &y);
704 fe_mul_llt(&out->xy2d, &out->xy2d, &d2);
705 }
706
707 // See the comment above |k25519SmallPrecomp| about the structure of the
708 // precomputed elements. This loop does 64 additions and 64 doublings to
709 // calculate the result.
710 ge_p3_0(h);
711
712 for (i = 63; i < 64; i--) {
713 unsigned j;
714 signed char index = 0;
715
716 for (j = 0; j < 4; j++) {
717 const uint8_t bit = 1 & (a[(8 * j) + (i / 8)] >> (i & 7));
718 index |= (bit << j);
719 }
720
721 ge_precomp e;
722 ge_precomp_0(&e);
723
724 for (j = 1; j < 16; j++) {
725 cmov(&e, &multiples[j-1], equal(index, j));
726 }
727
728 ge_cached cached;
729 ge_p1p1 r;
730 x25519_ge_p3_to_cached(&cached, h);
731 x25519_ge_add(&r, h, &cached);
732 x25519_ge_p1p1_to_p3(h, &r);
733
734 ge_madd(&r, h, &e);
735 x25519_ge_p1p1_to_p3(h, &r);
736 }
737 }
738
x25519_ge_scalarmult_base(ge_p3 * h,const uint8_t a[32])739 void x25519_ge_scalarmult_base(ge_p3 *h, const uint8_t a[32]) {
740 x25519_ge_scalarmult_small_precomp(h, a, k25519SmallPrecomp);
741 }
742
743 #else
744
negative(signed char b)745 static uint8_t negative(signed char b) {
746 uint32_t x = b;
747 x >>= 31; // 1: yes; 0: no
748 return x;
749 }
750
table_select(ge_precomp * t,int pos,signed char b)751 static void table_select(ge_precomp *t, int pos, signed char b) {
752 ge_precomp minust;
753 uint8_t bnegative = negative(b);
754 uint8_t babs = b - ((uint8_t)((-bnegative) & b) << 1);
755
756 ge_precomp_0(t);
757 cmov(t, &k25519Precomp[pos][0], equal(babs, 1));
758 cmov(t, &k25519Precomp[pos][1], equal(babs, 2));
759 cmov(t, &k25519Precomp[pos][2], equal(babs, 3));
760 cmov(t, &k25519Precomp[pos][3], equal(babs, 4));
761 cmov(t, &k25519Precomp[pos][4], equal(babs, 5));
762 cmov(t, &k25519Precomp[pos][5], equal(babs, 6));
763 cmov(t, &k25519Precomp[pos][6], equal(babs, 7));
764 cmov(t, &k25519Precomp[pos][7], equal(babs, 8));
765 fe_copy_ll(&minust.yplusx, &t->yminusx);
766 fe_copy_ll(&minust.yminusx, &t->yplusx);
767
768 // NOTE: the input table is canonical, but types don't encode it
769 fe tmp;
770 fe_carry(&tmp, &t->xy2d);
771 fe_neg(&minust.xy2d, &tmp);
772
773 cmov(t, &minust, bnegative);
774 }
775
776 // h = a * B
777 // where a = a[0]+256*a[1]+...+256^31 a[31]
778 // B is the Ed25519 base point (x,4/5) with x positive.
779 //
780 // Preconditions:
781 // a[31] <= 127
GFp_x25519_ge_scalarmult_base(ge_p3 * h,const uint8_t * a)782 void GFp_x25519_ge_scalarmult_base(ge_p3 *h, const uint8_t *a) {
783 signed char e[64];
784 signed char carry;
785 ge_p1p1 r;
786 ge_p2 s;
787 ge_precomp t;
788 int i;
789
790 for (i = 0; i < 32; ++i) {
791 e[2 * i + 0] = (a[i] >> 0) & 15;
792 e[2 * i + 1] = (a[i] >> 4) & 15;
793 }
794 // each e[i] is between 0 and 15
795 // e[63] is between 0 and 7
796
797 carry = 0;
798 for (i = 0; i < 63; ++i) {
799 e[i] += carry;
800 carry = e[i] + 8;
801 carry >>= 4;
802 e[i] -= carry << 4;
803 }
804 e[63] += carry;
805 // each e[i] is between -8 and 8
806
807 ge_p3_0(h);
808 for (i = 1; i < 64; i += 2) {
809 table_select(&t, i / 2, e[i]);
810 ge_madd(&r, h, &t);
811 x25519_ge_p1p1_to_p3(h, &r);
812 }
813
814 ge_p3_dbl(&r, h);
815 x25519_ge_p1p1_to_p2(&s, &r);
816 ge_p2_dbl(&r, &s);
817 x25519_ge_p1p1_to_p2(&s, &r);
818 ge_p2_dbl(&r, &s);
819 x25519_ge_p1p1_to_p2(&s, &r);
820 ge_p2_dbl(&r, &s);
821 x25519_ge_p1p1_to_p3(h, &r);
822
823 for (i = 0; i < 64; i += 2) {
824 table_select(&t, i / 2, e[i]);
825 ge_madd(&r, h, &t);
826 x25519_ge_p1p1_to_p3(h, &r);
827 }
828 }
829
830 #endif
831
slide(signed char * r,const uint8_t * a)832 static void slide(signed char *r, const uint8_t *a) {
833 int i;
834 int b;
835 int k;
836
837 for (i = 0; i < 256; ++i) {
838 r[i] = 1 & (a[i >> 3] >> (i & 7));
839 }
840
841 for (i = 0; i < 256; ++i) {
842 if (r[i]) {
843 for (b = 1; b <= 6 && i + b < 256; ++b) {
844 if (r[i + b]) {
845 if (r[i] + (r[i + b] << b) <= 15) {
846 r[i] += r[i + b] << b;
847 r[i + b] = 0;
848 } else if (r[i] - (r[i + b] << b) >= -15) {
849 r[i] -= r[i + b] << b;
850 for (k = i + b; k < 256; ++k) {
851 if (!r[k]) {
852 r[k] = 1;
853 break;
854 }
855 r[k] = 0;
856 }
857 } else {
858 break;
859 }
860 }
861 }
862 }
863 }
864 }
865
866 // r = a * A + b * B
867 // where a = a[0]+256*a[1]+...+256^31 a[31].
868 // and b = b[0]+256*b[1]+...+256^31 b[31].
869 // B is the Ed25519 base point (x,4/5) with x positive.
ge_double_scalarmult_vartime(ge_p2 * r,const uint8_t * a,const ge_p3 * A,const uint8_t * b)870 static void ge_double_scalarmult_vartime(ge_p2 *r, const uint8_t *a,
871 const ge_p3 *A, const uint8_t *b) {
872 signed char aslide[256];
873 signed char bslide[256];
874 ge_cached Ai[8]; // A,3A,5A,7A,9A,11A,13A,15A
875 ge_p1p1 t;
876 ge_p3 u;
877 ge_p3 A2;
878 int i;
879
880 slide(aslide, a);
881 slide(bslide, b);
882
883 x25519_ge_p3_to_cached(&Ai[0], A);
884 ge_p3_dbl(&t, A);
885 x25519_ge_p1p1_to_p3(&A2, &t);
886 x25519_ge_add(&t, &A2, &Ai[0]);
887 x25519_ge_p1p1_to_p3(&u, &t);
888 x25519_ge_p3_to_cached(&Ai[1], &u);
889 x25519_ge_add(&t, &A2, &Ai[1]);
890 x25519_ge_p1p1_to_p3(&u, &t);
891 x25519_ge_p3_to_cached(&Ai[2], &u);
892 x25519_ge_add(&t, &A2, &Ai[2]);
893 x25519_ge_p1p1_to_p3(&u, &t);
894 x25519_ge_p3_to_cached(&Ai[3], &u);
895 x25519_ge_add(&t, &A2, &Ai[3]);
896 x25519_ge_p1p1_to_p3(&u, &t);
897 x25519_ge_p3_to_cached(&Ai[4], &u);
898 x25519_ge_add(&t, &A2, &Ai[4]);
899 x25519_ge_p1p1_to_p3(&u, &t);
900 x25519_ge_p3_to_cached(&Ai[5], &u);
901 x25519_ge_add(&t, &A2, &Ai[5]);
902 x25519_ge_p1p1_to_p3(&u, &t);
903 x25519_ge_p3_to_cached(&Ai[6], &u);
904 x25519_ge_add(&t, &A2, &Ai[6]);
905 x25519_ge_p1p1_to_p3(&u, &t);
906 x25519_ge_p3_to_cached(&Ai[7], &u);
907
908 ge_p2_0(r);
909
910 for (i = 255; i >= 0; --i) {
911 if (aslide[i] || bslide[i]) {
912 break;
913 }
914 }
915
916 for (; i >= 0; --i) {
917 ge_p2_dbl(&t, r);
918
919 if (aslide[i] > 0) {
920 x25519_ge_p1p1_to_p3(&u, &t);
921 x25519_ge_add(&t, &u, &Ai[aslide[i] / 2]);
922 } else if (aslide[i] < 0) {
923 x25519_ge_p1p1_to_p3(&u, &t);
924 x25519_ge_sub(&t, &u, &Ai[(-aslide[i]) / 2]);
925 }
926
927 if (bslide[i] > 0) {
928 x25519_ge_p1p1_to_p3(&u, &t);
929 ge_madd(&t, &u, &Bi[bslide[i] / 2]);
930 } else if (bslide[i] < 0) {
931 x25519_ge_p1p1_to_p3(&u, &t);
932 ge_msub(&t, &u, &Bi[(-bslide[i]) / 2]);
933 }
934
935 x25519_ge_p1p1_to_p2(r, &t);
936 }
937 }
938
939 // int64_lshift21 returns |a << 21| but is defined when shifting bits into the
940 // sign bit. This works around a language flaw in C.
int64_lshift21(int64_t a)941 static inline int64_t int64_lshift21(int64_t a) {
942 return (int64_t)((uint64_t)a << 21);
943 }
944
945 // The set of scalars is \Z/l
946 // where l = 2^252 + 27742317777372353535851937790883648493.
947
948 // Input:
949 // s[0]+256*s[1]+...+256^63*s[63] = s
950 //
951 // Output:
952 // s[0]+256*s[1]+...+256^31*s[31] = s mod l
953 // where l = 2^252 + 27742317777372353535851937790883648493.
954 // Overwrites s in place.
GFp_x25519_sc_reduce(uint8_t s[64])955 void GFp_x25519_sc_reduce(uint8_t s[64]) {
956 int64_t s0 = 2097151 & load_3(s);
957 int64_t s1 = 2097151 & (load_4(s + 2) >> 5);
958 int64_t s2 = 2097151 & (load_3(s + 5) >> 2);
959 int64_t s3 = 2097151 & (load_4(s + 7) >> 7);
960 int64_t s4 = 2097151 & (load_4(s + 10) >> 4);
961 int64_t s5 = 2097151 & (load_3(s + 13) >> 1);
962 int64_t s6 = 2097151 & (load_4(s + 15) >> 6);
963 int64_t s7 = 2097151 & (load_3(s + 18) >> 3);
964 int64_t s8 = 2097151 & load_3(s + 21);
965 int64_t s9 = 2097151 & (load_4(s + 23) >> 5);
966 int64_t s10 = 2097151 & (load_3(s + 26) >> 2);
967 int64_t s11 = 2097151 & (load_4(s + 28) >> 7);
968 int64_t s12 = 2097151 & (load_4(s + 31) >> 4);
969 int64_t s13 = 2097151 & (load_3(s + 34) >> 1);
970 int64_t s14 = 2097151 & (load_4(s + 36) >> 6);
971 int64_t s15 = 2097151 & (load_3(s + 39) >> 3);
972 int64_t s16 = 2097151 & load_3(s + 42);
973 int64_t s17 = 2097151 & (load_4(s + 44) >> 5);
974 int64_t s18 = 2097151 & (load_3(s + 47) >> 2);
975 int64_t s19 = 2097151 & (load_4(s + 49) >> 7);
976 int64_t s20 = 2097151 & (load_4(s + 52) >> 4);
977 int64_t s21 = 2097151 & (load_3(s + 55) >> 1);
978 int64_t s22 = 2097151 & (load_4(s + 57) >> 6);
979 int64_t s23 = (load_4(s + 60) >> 3);
980 int64_t carry0;
981 int64_t carry1;
982 int64_t carry2;
983 int64_t carry3;
984 int64_t carry4;
985 int64_t carry5;
986 int64_t carry6;
987 int64_t carry7;
988 int64_t carry8;
989 int64_t carry9;
990 int64_t carry10;
991 int64_t carry11;
992 int64_t carry12;
993 int64_t carry13;
994 int64_t carry14;
995 int64_t carry15;
996 int64_t carry16;
997
998 s11 += s23 * 666643;
999 s12 += s23 * 470296;
1000 s13 += s23 * 654183;
1001 s14 -= s23 * 997805;
1002 s15 += s23 * 136657;
1003 s16 -= s23 * 683901;
1004 s23 = 0;
1005
1006 s10 += s22 * 666643;
1007 s11 += s22 * 470296;
1008 s12 += s22 * 654183;
1009 s13 -= s22 * 997805;
1010 s14 += s22 * 136657;
1011 s15 -= s22 * 683901;
1012 s22 = 0;
1013
1014 s9 += s21 * 666643;
1015 s10 += s21 * 470296;
1016 s11 += s21 * 654183;
1017 s12 -= s21 * 997805;
1018 s13 += s21 * 136657;
1019 s14 -= s21 * 683901;
1020 s21 = 0;
1021
1022 s8 += s20 * 666643;
1023 s9 += s20 * 470296;
1024 s10 += s20 * 654183;
1025 s11 -= s20 * 997805;
1026 s12 += s20 * 136657;
1027 s13 -= s20 * 683901;
1028 s20 = 0;
1029
1030 s7 += s19 * 666643;
1031 s8 += s19 * 470296;
1032 s9 += s19 * 654183;
1033 s10 -= s19 * 997805;
1034 s11 += s19 * 136657;
1035 s12 -= s19 * 683901;
1036 s19 = 0;
1037
1038 s6 += s18 * 666643;
1039 s7 += s18 * 470296;
1040 s8 += s18 * 654183;
1041 s9 -= s18 * 997805;
1042 s10 += s18 * 136657;
1043 s11 -= s18 * 683901;
1044 s18 = 0;
1045
1046 carry6 = (s6 + (1 << 20)) >> 21;
1047 s7 += carry6;
1048 s6 -= int64_lshift21(carry6);
1049 carry8 = (s8 + (1 << 20)) >> 21;
1050 s9 += carry8;
1051 s8 -= int64_lshift21(carry8);
1052 carry10 = (s10 + (1 << 20)) >> 21;
1053 s11 += carry10;
1054 s10 -= int64_lshift21(carry10);
1055 carry12 = (s12 + (1 << 20)) >> 21;
1056 s13 += carry12;
1057 s12 -= int64_lshift21(carry12);
1058 carry14 = (s14 + (1 << 20)) >> 21;
1059 s15 += carry14;
1060 s14 -= int64_lshift21(carry14);
1061 carry16 = (s16 + (1 << 20)) >> 21;
1062 s17 += carry16;
1063 s16 -= int64_lshift21(carry16);
1064
1065 carry7 = (s7 + (1 << 20)) >> 21;
1066 s8 += carry7;
1067 s7 -= int64_lshift21(carry7);
1068 carry9 = (s9 + (1 << 20)) >> 21;
1069 s10 += carry9;
1070 s9 -= int64_lshift21(carry9);
1071 carry11 = (s11 + (1 << 20)) >> 21;
1072 s12 += carry11;
1073 s11 -= int64_lshift21(carry11);
1074 carry13 = (s13 + (1 << 20)) >> 21;
1075 s14 += carry13;
1076 s13 -= int64_lshift21(carry13);
1077 carry15 = (s15 + (1 << 20)) >> 21;
1078 s16 += carry15;
1079 s15 -= int64_lshift21(carry15);
1080
1081 s5 += s17 * 666643;
1082 s6 += s17 * 470296;
1083 s7 += s17 * 654183;
1084 s8 -= s17 * 997805;
1085 s9 += s17 * 136657;
1086 s10 -= s17 * 683901;
1087 s17 = 0;
1088
1089 s4 += s16 * 666643;
1090 s5 += s16 * 470296;
1091 s6 += s16 * 654183;
1092 s7 -= s16 * 997805;
1093 s8 += s16 * 136657;
1094 s9 -= s16 * 683901;
1095 s16 = 0;
1096
1097 s3 += s15 * 666643;
1098 s4 += s15 * 470296;
1099 s5 += s15 * 654183;
1100 s6 -= s15 * 997805;
1101 s7 += s15 * 136657;
1102 s8 -= s15 * 683901;
1103 s15 = 0;
1104
1105 s2 += s14 * 666643;
1106 s3 += s14 * 470296;
1107 s4 += s14 * 654183;
1108 s5 -= s14 * 997805;
1109 s6 += s14 * 136657;
1110 s7 -= s14 * 683901;
1111 s14 = 0;
1112
1113 s1 += s13 * 666643;
1114 s2 += s13 * 470296;
1115 s3 += s13 * 654183;
1116 s4 -= s13 * 997805;
1117 s5 += s13 * 136657;
1118 s6 -= s13 * 683901;
1119 s13 = 0;
1120
1121 s0 += s12 * 666643;
1122 s1 += s12 * 470296;
1123 s2 += s12 * 654183;
1124 s3 -= s12 * 997805;
1125 s4 += s12 * 136657;
1126 s5 -= s12 * 683901;
1127 s12 = 0;
1128
1129 carry0 = (s0 + (1 << 20)) >> 21;
1130 s1 += carry0;
1131 s0 -= int64_lshift21(carry0);
1132 carry2 = (s2 + (1 << 20)) >> 21;
1133 s3 += carry2;
1134 s2 -= int64_lshift21(carry2);
1135 carry4 = (s4 + (1 << 20)) >> 21;
1136 s5 += carry4;
1137 s4 -= int64_lshift21(carry4);
1138 carry6 = (s6 + (1 << 20)) >> 21;
1139 s7 += carry6;
1140 s6 -= int64_lshift21(carry6);
1141 carry8 = (s8 + (1 << 20)) >> 21;
1142 s9 += carry8;
1143 s8 -= int64_lshift21(carry8);
1144 carry10 = (s10 + (1 << 20)) >> 21;
1145 s11 += carry10;
1146 s10 -= int64_lshift21(carry10);
1147
1148 carry1 = (s1 + (1 << 20)) >> 21;
1149 s2 += carry1;
1150 s1 -= int64_lshift21(carry1);
1151 carry3 = (s3 + (1 << 20)) >> 21;
1152 s4 += carry3;
1153 s3 -= int64_lshift21(carry3);
1154 carry5 = (s5 + (1 << 20)) >> 21;
1155 s6 += carry5;
1156 s5 -= int64_lshift21(carry5);
1157 carry7 = (s7 + (1 << 20)) >> 21;
1158 s8 += carry7;
1159 s7 -= int64_lshift21(carry7);
1160 carry9 = (s9 + (1 << 20)) >> 21;
1161 s10 += carry9;
1162 s9 -= int64_lshift21(carry9);
1163 carry11 = (s11 + (1 << 20)) >> 21;
1164 s12 += carry11;
1165 s11 -= int64_lshift21(carry11);
1166
1167 s0 += s12 * 666643;
1168 s1 += s12 * 470296;
1169 s2 += s12 * 654183;
1170 s3 -= s12 * 997805;
1171 s4 += s12 * 136657;
1172 s5 -= s12 * 683901;
1173 s12 = 0;
1174
1175 carry0 = s0 >> 21;
1176 s1 += carry0;
1177 s0 -= int64_lshift21(carry0);
1178 carry1 = s1 >> 21;
1179 s2 += carry1;
1180 s1 -= int64_lshift21(carry1);
1181 carry2 = s2 >> 21;
1182 s3 += carry2;
1183 s2 -= int64_lshift21(carry2);
1184 carry3 = s3 >> 21;
1185 s4 += carry3;
1186 s3 -= int64_lshift21(carry3);
1187 carry4 = s4 >> 21;
1188 s5 += carry4;
1189 s4 -= int64_lshift21(carry4);
1190 carry5 = s5 >> 21;
1191 s6 += carry5;
1192 s5 -= int64_lshift21(carry5);
1193 carry6 = s6 >> 21;
1194 s7 += carry6;
1195 s6 -= int64_lshift21(carry6);
1196 carry7 = s7 >> 21;
1197 s8 += carry7;
1198 s7 -= int64_lshift21(carry7);
1199 carry8 = s8 >> 21;
1200 s9 += carry8;
1201 s8 -= int64_lshift21(carry8);
1202 carry9 = s9 >> 21;
1203 s10 += carry9;
1204 s9 -= int64_lshift21(carry9);
1205 carry10 = s10 >> 21;
1206 s11 += carry10;
1207 s10 -= int64_lshift21(carry10);
1208 carry11 = s11 >> 21;
1209 s12 += carry11;
1210 s11 -= int64_lshift21(carry11);
1211
1212 s0 += s12 * 666643;
1213 s1 += s12 * 470296;
1214 s2 += s12 * 654183;
1215 s3 -= s12 * 997805;
1216 s4 += s12 * 136657;
1217 s5 -= s12 * 683901;
1218 s12 = 0;
1219
1220 carry0 = s0 >> 21;
1221 s1 += carry0;
1222 s0 -= int64_lshift21(carry0);
1223 carry1 = s1 >> 21;
1224 s2 += carry1;
1225 s1 -= int64_lshift21(carry1);
1226 carry2 = s2 >> 21;
1227 s3 += carry2;
1228 s2 -= int64_lshift21(carry2);
1229 carry3 = s3 >> 21;
1230 s4 += carry3;
1231 s3 -= int64_lshift21(carry3);
1232 carry4 = s4 >> 21;
1233 s5 += carry4;
1234 s4 -= int64_lshift21(carry4);
1235 carry5 = s5 >> 21;
1236 s6 += carry5;
1237 s5 -= int64_lshift21(carry5);
1238 carry6 = s6 >> 21;
1239 s7 += carry6;
1240 s6 -= int64_lshift21(carry6);
1241 carry7 = s7 >> 21;
1242 s8 += carry7;
1243 s7 -= int64_lshift21(carry7);
1244 carry8 = s8 >> 21;
1245 s9 += carry8;
1246 s8 -= int64_lshift21(carry8);
1247 carry9 = s9 >> 21;
1248 s10 += carry9;
1249 s9 -= int64_lshift21(carry9);
1250 carry10 = s10 >> 21;
1251 s11 += carry10;
1252 s10 -= int64_lshift21(carry10);
1253
1254 s[0] = s0 >> 0;
1255 s[1] = s0 >> 8;
1256 s[2] = (s0 >> 16) | (s1 << 5);
1257 s[3] = s1 >> 3;
1258 s[4] = s1 >> 11;
1259 s[5] = (s1 >> 19) | (s2 << 2);
1260 s[6] = s2 >> 6;
1261 s[7] = (s2 >> 14) | (s3 << 7);
1262 s[8] = s3 >> 1;
1263 s[9] = s3 >> 9;
1264 s[10] = (s3 >> 17) | (s4 << 4);
1265 s[11] = s4 >> 4;
1266 s[12] = s4 >> 12;
1267 s[13] = (s4 >> 20) | (s5 << 1);
1268 s[14] = s5 >> 7;
1269 s[15] = (s5 >> 15) | (s6 << 6);
1270 s[16] = s6 >> 2;
1271 s[17] = s6 >> 10;
1272 s[18] = (s6 >> 18) | (s7 << 3);
1273 s[19] = s7 >> 5;
1274 s[20] = s7 >> 13;
1275 s[21] = s8 >> 0;
1276 s[22] = s8 >> 8;
1277 s[23] = (s8 >> 16) | (s9 << 5);
1278 s[24] = s9 >> 3;
1279 s[25] = s9 >> 11;
1280 s[26] = (s9 >> 19) | (s10 << 2);
1281 s[27] = s10 >> 6;
1282 s[28] = (s10 >> 14) | (s11 << 7);
1283 s[29] = s11 >> 1;
1284 s[30] = s11 >> 9;
1285 s[31] = s11 >> 17;
1286 }
1287
1288 // Input:
1289 // a[0]+256*a[1]+...+256^31*a[31] = a
1290 // b[0]+256*b[1]+...+256^31*b[31] = b
1291 // c[0]+256*c[1]+...+256^31*c[31] = c
1292 //
1293 // Output:
1294 // s[0]+256*s[1]+...+256^31*s[31] = (ab+c) mod l
1295 // where l = 2^252 + 27742317777372353535851937790883648493.
sc_muladd(uint8_t * s,const uint8_t * a,const uint8_t * b,const uint8_t * c)1296 static void sc_muladd(uint8_t *s, const uint8_t *a, const uint8_t *b,
1297 const uint8_t *c) {
1298 int64_t a0 = 2097151 & load_3(a);
1299 int64_t a1 = 2097151 & (load_4(a + 2) >> 5);
1300 int64_t a2 = 2097151 & (load_3(a + 5) >> 2);
1301 int64_t a3 = 2097151 & (load_4(a + 7) >> 7);
1302 int64_t a4 = 2097151 & (load_4(a + 10) >> 4);
1303 int64_t a5 = 2097151 & (load_3(a + 13) >> 1);
1304 int64_t a6 = 2097151 & (load_4(a + 15) >> 6);
1305 int64_t a7 = 2097151 & (load_3(a + 18) >> 3);
1306 int64_t a8 = 2097151 & load_3(a + 21);
1307 int64_t a9 = 2097151 & (load_4(a + 23) >> 5);
1308 int64_t a10 = 2097151 & (load_3(a + 26) >> 2);
1309 int64_t a11 = (load_4(a + 28) >> 7);
1310 int64_t b0 = 2097151 & load_3(b);
1311 int64_t b1 = 2097151 & (load_4(b + 2) >> 5);
1312 int64_t b2 = 2097151 & (load_3(b + 5) >> 2);
1313 int64_t b3 = 2097151 & (load_4(b + 7) >> 7);
1314 int64_t b4 = 2097151 & (load_4(b + 10) >> 4);
1315 int64_t b5 = 2097151 & (load_3(b + 13) >> 1);
1316 int64_t b6 = 2097151 & (load_4(b + 15) >> 6);
1317 int64_t b7 = 2097151 & (load_3(b + 18) >> 3);
1318 int64_t b8 = 2097151 & load_3(b + 21);
1319 int64_t b9 = 2097151 & (load_4(b + 23) >> 5);
1320 int64_t b10 = 2097151 & (load_3(b + 26) >> 2);
1321 int64_t b11 = (load_4(b + 28) >> 7);
1322 int64_t c0 = 2097151 & load_3(c);
1323 int64_t c1 = 2097151 & (load_4(c + 2) >> 5);
1324 int64_t c2 = 2097151 & (load_3(c + 5) >> 2);
1325 int64_t c3 = 2097151 & (load_4(c + 7) >> 7);
1326 int64_t c4 = 2097151 & (load_4(c + 10) >> 4);
1327 int64_t c5 = 2097151 & (load_3(c + 13) >> 1);
1328 int64_t c6 = 2097151 & (load_4(c + 15) >> 6);
1329 int64_t c7 = 2097151 & (load_3(c + 18) >> 3);
1330 int64_t c8 = 2097151 & load_3(c + 21);
1331 int64_t c9 = 2097151 & (load_4(c + 23) >> 5);
1332 int64_t c10 = 2097151 & (load_3(c + 26) >> 2);
1333 int64_t c11 = (load_4(c + 28) >> 7);
1334 int64_t s0;
1335 int64_t s1;
1336 int64_t s2;
1337 int64_t s3;
1338 int64_t s4;
1339 int64_t s5;
1340 int64_t s6;
1341 int64_t s7;
1342 int64_t s8;
1343 int64_t s9;
1344 int64_t s10;
1345 int64_t s11;
1346 int64_t s12;
1347 int64_t s13;
1348 int64_t s14;
1349 int64_t s15;
1350 int64_t s16;
1351 int64_t s17;
1352 int64_t s18;
1353 int64_t s19;
1354 int64_t s20;
1355 int64_t s21;
1356 int64_t s22;
1357 int64_t s23;
1358 int64_t carry0;
1359 int64_t carry1;
1360 int64_t carry2;
1361 int64_t carry3;
1362 int64_t carry4;
1363 int64_t carry5;
1364 int64_t carry6;
1365 int64_t carry7;
1366 int64_t carry8;
1367 int64_t carry9;
1368 int64_t carry10;
1369 int64_t carry11;
1370 int64_t carry12;
1371 int64_t carry13;
1372 int64_t carry14;
1373 int64_t carry15;
1374 int64_t carry16;
1375 int64_t carry17;
1376 int64_t carry18;
1377 int64_t carry19;
1378 int64_t carry20;
1379 int64_t carry21;
1380 int64_t carry22;
1381
1382 s0 = c0 + a0 * b0;
1383 s1 = c1 + a0 * b1 + a1 * b0;
1384 s2 = c2 + a0 * b2 + a1 * b1 + a2 * b0;
1385 s3 = c3 + a0 * b3 + a1 * b2 + a2 * b1 + a3 * b0;
1386 s4 = c4 + a0 * b4 + a1 * b3 + a2 * b2 + a3 * b1 + a4 * b0;
1387 s5 = c5 + a0 * b5 + a1 * b4 + a2 * b3 + a3 * b2 + a4 * b1 + a5 * b0;
1388 s6 = c6 + a0 * b6 + a1 * b5 + a2 * b4 + a3 * b3 + a4 * b2 + a5 * b1 + a6 * b0;
1389 s7 = c7 + a0 * b7 + a1 * b6 + a2 * b5 + a3 * b4 + a4 * b3 + a5 * b2 +
1390 a6 * b1 + a7 * b0;
1391 s8 = c8 + a0 * b8 + a1 * b7 + a2 * b6 + a3 * b5 + a4 * b4 + a5 * b3 +
1392 a6 * b2 + a7 * b1 + a8 * b0;
1393 s9 = c9 + a0 * b9 + a1 * b8 + a2 * b7 + a3 * b6 + a4 * b5 + a5 * b4 +
1394 a6 * b3 + a7 * b2 + a8 * b1 + a9 * b0;
1395 s10 = c10 + a0 * b10 + a1 * b9 + a2 * b8 + a3 * b7 + a4 * b6 + a5 * b5 +
1396 a6 * b4 + a7 * b3 + a8 * b2 + a9 * b1 + a10 * b0;
1397 s11 = c11 + a0 * b11 + a1 * b10 + a2 * b9 + a3 * b8 + a4 * b7 + a5 * b6 +
1398 a6 * b5 + a7 * b4 + a8 * b3 + a9 * b2 + a10 * b1 + a11 * b0;
1399 s12 = a1 * b11 + a2 * b10 + a3 * b9 + a4 * b8 + a5 * b7 + a6 * b6 + a7 * b5 +
1400 a8 * b4 + a9 * b3 + a10 * b2 + a11 * b1;
1401 s13 = a2 * b11 + a3 * b10 + a4 * b9 + a5 * b8 + a6 * b7 + a7 * b6 + a8 * b5 +
1402 a9 * b4 + a10 * b3 + a11 * b2;
1403 s14 = a3 * b11 + a4 * b10 + a5 * b9 + a6 * b8 + a7 * b7 + a8 * b6 + a9 * b5 +
1404 a10 * b4 + a11 * b3;
1405 s15 = a4 * b11 + a5 * b10 + a6 * b9 + a7 * b8 + a8 * b7 + a9 * b6 + a10 * b5 +
1406 a11 * b4;
1407 s16 = a5 * b11 + a6 * b10 + a7 * b9 + a8 * b8 + a9 * b7 + a10 * b6 + a11 * b5;
1408 s17 = a6 * b11 + a7 * b10 + a8 * b9 + a9 * b8 + a10 * b7 + a11 * b6;
1409 s18 = a7 * b11 + a8 * b10 + a9 * b9 + a10 * b8 + a11 * b7;
1410 s19 = a8 * b11 + a9 * b10 + a10 * b9 + a11 * b8;
1411 s20 = a9 * b11 + a10 * b10 + a11 * b9;
1412 s21 = a10 * b11 + a11 * b10;
1413 s22 = a11 * b11;
1414 s23 = 0;
1415
1416 carry0 = (s0 + (1 << 20)) >> 21;
1417 s1 += carry0;
1418 s0 -= int64_lshift21(carry0);
1419 carry2 = (s2 + (1 << 20)) >> 21;
1420 s3 += carry2;
1421 s2 -= int64_lshift21(carry2);
1422 carry4 = (s4 + (1 << 20)) >> 21;
1423 s5 += carry4;
1424 s4 -= int64_lshift21(carry4);
1425 carry6 = (s6 + (1 << 20)) >> 21;
1426 s7 += carry6;
1427 s6 -= int64_lshift21(carry6);
1428 carry8 = (s8 + (1 << 20)) >> 21;
1429 s9 += carry8;
1430 s8 -= int64_lshift21(carry8);
1431 carry10 = (s10 + (1 << 20)) >> 21;
1432 s11 += carry10;
1433 s10 -= int64_lshift21(carry10);
1434 carry12 = (s12 + (1 << 20)) >> 21;
1435 s13 += carry12;
1436 s12 -= int64_lshift21(carry12);
1437 carry14 = (s14 + (1 << 20)) >> 21;
1438 s15 += carry14;
1439 s14 -= int64_lshift21(carry14);
1440 carry16 = (s16 + (1 << 20)) >> 21;
1441 s17 += carry16;
1442 s16 -= int64_lshift21(carry16);
1443 carry18 = (s18 + (1 << 20)) >> 21;
1444 s19 += carry18;
1445 s18 -= int64_lshift21(carry18);
1446 carry20 = (s20 + (1 << 20)) >> 21;
1447 s21 += carry20;
1448 s20 -= int64_lshift21(carry20);
1449 carry22 = (s22 + (1 << 20)) >> 21;
1450 s23 += carry22;
1451 s22 -= int64_lshift21(carry22);
1452
1453 carry1 = (s1 + (1 << 20)) >> 21;
1454 s2 += carry1;
1455 s1 -= int64_lshift21(carry1);
1456 carry3 = (s3 + (1 << 20)) >> 21;
1457 s4 += carry3;
1458 s3 -= int64_lshift21(carry3);
1459 carry5 = (s5 + (1 << 20)) >> 21;
1460 s6 += carry5;
1461 s5 -= int64_lshift21(carry5);
1462 carry7 = (s7 + (1 << 20)) >> 21;
1463 s8 += carry7;
1464 s7 -= int64_lshift21(carry7);
1465 carry9 = (s9 + (1 << 20)) >> 21;
1466 s10 += carry9;
1467 s9 -= int64_lshift21(carry9);
1468 carry11 = (s11 + (1 << 20)) >> 21;
1469 s12 += carry11;
1470 s11 -= int64_lshift21(carry11);
1471 carry13 = (s13 + (1 << 20)) >> 21;
1472 s14 += carry13;
1473 s13 -= int64_lshift21(carry13);
1474 carry15 = (s15 + (1 << 20)) >> 21;
1475 s16 += carry15;
1476 s15 -= int64_lshift21(carry15);
1477 carry17 = (s17 + (1 << 20)) >> 21;
1478 s18 += carry17;
1479 s17 -= int64_lshift21(carry17);
1480 carry19 = (s19 + (1 << 20)) >> 21;
1481 s20 += carry19;
1482 s19 -= int64_lshift21(carry19);
1483 carry21 = (s21 + (1 << 20)) >> 21;
1484 s22 += carry21;
1485 s21 -= int64_lshift21(carry21);
1486
1487 s11 += s23 * 666643;
1488 s12 += s23 * 470296;
1489 s13 += s23 * 654183;
1490 s14 -= s23 * 997805;
1491 s15 += s23 * 136657;
1492 s16 -= s23 * 683901;
1493 s23 = 0;
1494
1495 s10 += s22 * 666643;
1496 s11 += s22 * 470296;
1497 s12 += s22 * 654183;
1498 s13 -= s22 * 997805;
1499 s14 += s22 * 136657;
1500 s15 -= s22 * 683901;
1501 s22 = 0;
1502
1503 s9 += s21 * 666643;
1504 s10 += s21 * 470296;
1505 s11 += s21 * 654183;
1506 s12 -= s21 * 997805;
1507 s13 += s21 * 136657;
1508 s14 -= s21 * 683901;
1509 s21 = 0;
1510
1511 s8 += s20 * 666643;
1512 s9 += s20 * 470296;
1513 s10 += s20 * 654183;
1514 s11 -= s20 * 997805;
1515 s12 += s20 * 136657;
1516 s13 -= s20 * 683901;
1517 s20 = 0;
1518
1519 s7 += s19 * 666643;
1520 s8 += s19 * 470296;
1521 s9 += s19 * 654183;
1522 s10 -= s19 * 997805;
1523 s11 += s19 * 136657;
1524 s12 -= s19 * 683901;
1525 s19 = 0;
1526
1527 s6 += s18 * 666643;
1528 s7 += s18 * 470296;
1529 s8 += s18 * 654183;
1530 s9 -= s18 * 997805;
1531 s10 += s18 * 136657;
1532 s11 -= s18 * 683901;
1533 s18 = 0;
1534
1535 carry6 = (s6 + (1 << 20)) >> 21;
1536 s7 += carry6;
1537 s6 -= int64_lshift21(carry6);
1538 carry8 = (s8 + (1 << 20)) >> 21;
1539 s9 += carry8;
1540 s8 -= int64_lshift21(carry8);
1541 carry10 = (s10 + (1 << 20)) >> 21;
1542 s11 += carry10;
1543 s10 -= int64_lshift21(carry10);
1544 carry12 = (s12 + (1 << 20)) >> 21;
1545 s13 += carry12;
1546 s12 -= int64_lshift21(carry12);
1547 carry14 = (s14 + (1 << 20)) >> 21;
1548 s15 += carry14;
1549 s14 -= int64_lshift21(carry14);
1550 carry16 = (s16 + (1 << 20)) >> 21;
1551 s17 += carry16;
1552 s16 -= int64_lshift21(carry16);
1553
1554 carry7 = (s7 + (1 << 20)) >> 21;
1555 s8 += carry7;
1556 s7 -= int64_lshift21(carry7);
1557 carry9 = (s9 + (1 << 20)) >> 21;
1558 s10 += carry9;
1559 s9 -= int64_lshift21(carry9);
1560 carry11 = (s11 + (1 << 20)) >> 21;
1561 s12 += carry11;
1562 s11 -= int64_lshift21(carry11);
1563 carry13 = (s13 + (1 << 20)) >> 21;
1564 s14 += carry13;
1565 s13 -= int64_lshift21(carry13);
1566 carry15 = (s15 + (1 << 20)) >> 21;
1567 s16 += carry15;
1568 s15 -= int64_lshift21(carry15);
1569
1570 s5 += s17 * 666643;
1571 s6 += s17 * 470296;
1572 s7 += s17 * 654183;
1573 s8 -= s17 * 997805;
1574 s9 += s17 * 136657;
1575 s10 -= s17 * 683901;
1576 s17 = 0;
1577
1578 s4 += s16 * 666643;
1579 s5 += s16 * 470296;
1580 s6 += s16 * 654183;
1581 s7 -= s16 * 997805;
1582 s8 += s16 * 136657;
1583 s9 -= s16 * 683901;
1584 s16 = 0;
1585
1586 s3 += s15 * 666643;
1587 s4 += s15 * 470296;
1588 s5 += s15 * 654183;
1589 s6 -= s15 * 997805;
1590 s7 += s15 * 136657;
1591 s8 -= s15 * 683901;
1592 s15 = 0;
1593
1594 s2 += s14 * 666643;
1595 s3 += s14 * 470296;
1596 s4 += s14 * 654183;
1597 s5 -= s14 * 997805;
1598 s6 += s14 * 136657;
1599 s7 -= s14 * 683901;
1600 s14 = 0;
1601
1602 s1 += s13 * 666643;
1603 s2 += s13 * 470296;
1604 s3 += s13 * 654183;
1605 s4 -= s13 * 997805;
1606 s5 += s13 * 136657;
1607 s6 -= s13 * 683901;
1608 s13 = 0;
1609
1610 s0 += s12 * 666643;
1611 s1 += s12 * 470296;
1612 s2 += s12 * 654183;
1613 s3 -= s12 * 997805;
1614 s4 += s12 * 136657;
1615 s5 -= s12 * 683901;
1616 s12 = 0;
1617
1618 carry0 = (s0 + (1 << 20)) >> 21;
1619 s1 += carry0;
1620 s0 -= int64_lshift21(carry0);
1621 carry2 = (s2 + (1 << 20)) >> 21;
1622 s3 += carry2;
1623 s2 -= int64_lshift21(carry2);
1624 carry4 = (s4 + (1 << 20)) >> 21;
1625 s5 += carry4;
1626 s4 -= int64_lshift21(carry4);
1627 carry6 = (s6 + (1 << 20)) >> 21;
1628 s7 += carry6;
1629 s6 -= int64_lshift21(carry6);
1630 carry8 = (s8 + (1 << 20)) >> 21;
1631 s9 += carry8;
1632 s8 -= int64_lshift21(carry8);
1633 carry10 = (s10 + (1 << 20)) >> 21;
1634 s11 += carry10;
1635 s10 -= int64_lshift21(carry10);
1636
1637 carry1 = (s1 + (1 << 20)) >> 21;
1638 s2 += carry1;
1639 s1 -= int64_lshift21(carry1);
1640 carry3 = (s3 + (1 << 20)) >> 21;
1641 s4 += carry3;
1642 s3 -= int64_lshift21(carry3);
1643 carry5 = (s5 + (1 << 20)) >> 21;
1644 s6 += carry5;
1645 s5 -= int64_lshift21(carry5);
1646 carry7 = (s7 + (1 << 20)) >> 21;
1647 s8 += carry7;
1648 s7 -= int64_lshift21(carry7);
1649 carry9 = (s9 + (1 << 20)) >> 21;
1650 s10 += carry9;
1651 s9 -= int64_lshift21(carry9);
1652 carry11 = (s11 + (1 << 20)) >> 21;
1653 s12 += carry11;
1654 s11 -= int64_lshift21(carry11);
1655
1656 s0 += s12 * 666643;
1657 s1 += s12 * 470296;
1658 s2 += s12 * 654183;
1659 s3 -= s12 * 997805;
1660 s4 += s12 * 136657;
1661 s5 -= s12 * 683901;
1662 s12 = 0;
1663
1664 carry0 = s0 >> 21;
1665 s1 += carry0;
1666 s0 -= int64_lshift21(carry0);
1667 carry1 = s1 >> 21;
1668 s2 += carry1;
1669 s1 -= int64_lshift21(carry1);
1670 carry2 = s2 >> 21;
1671 s3 += carry2;
1672 s2 -= int64_lshift21(carry2);
1673 carry3 = s3 >> 21;
1674 s4 += carry3;
1675 s3 -= int64_lshift21(carry3);
1676 carry4 = s4 >> 21;
1677 s5 += carry4;
1678 s4 -= int64_lshift21(carry4);
1679 carry5 = s5 >> 21;
1680 s6 += carry5;
1681 s5 -= int64_lshift21(carry5);
1682 carry6 = s6 >> 21;
1683 s7 += carry6;
1684 s6 -= int64_lshift21(carry6);
1685 carry7 = s7 >> 21;
1686 s8 += carry7;
1687 s7 -= int64_lshift21(carry7);
1688 carry8 = s8 >> 21;
1689 s9 += carry8;
1690 s8 -= int64_lshift21(carry8);
1691 carry9 = s9 >> 21;
1692 s10 += carry9;
1693 s9 -= int64_lshift21(carry9);
1694 carry10 = s10 >> 21;
1695 s11 += carry10;
1696 s10 -= int64_lshift21(carry10);
1697 carry11 = s11 >> 21;
1698 s12 += carry11;
1699 s11 -= int64_lshift21(carry11);
1700
1701 s0 += s12 * 666643;
1702 s1 += s12 * 470296;
1703 s2 += s12 * 654183;
1704 s3 -= s12 * 997805;
1705 s4 += s12 * 136657;
1706 s5 -= s12 * 683901;
1707 s12 = 0;
1708
1709 carry0 = s0 >> 21;
1710 s1 += carry0;
1711 s0 -= int64_lshift21(carry0);
1712 carry1 = s1 >> 21;
1713 s2 += carry1;
1714 s1 -= int64_lshift21(carry1);
1715 carry2 = s2 >> 21;
1716 s3 += carry2;
1717 s2 -= int64_lshift21(carry2);
1718 carry3 = s3 >> 21;
1719 s4 += carry3;
1720 s3 -= int64_lshift21(carry3);
1721 carry4 = s4 >> 21;
1722 s5 += carry4;
1723 s4 -= int64_lshift21(carry4);
1724 carry5 = s5 >> 21;
1725 s6 += carry5;
1726 s5 -= int64_lshift21(carry5);
1727 carry6 = s6 >> 21;
1728 s7 += carry6;
1729 s6 -= int64_lshift21(carry6);
1730 carry7 = s7 >> 21;
1731 s8 += carry7;
1732 s7 -= int64_lshift21(carry7);
1733 carry8 = s8 >> 21;
1734 s9 += carry8;
1735 s8 -= int64_lshift21(carry8);
1736 carry9 = s9 >> 21;
1737 s10 += carry9;
1738 s9 -= int64_lshift21(carry9);
1739 carry10 = s10 >> 21;
1740 s11 += carry10;
1741 s10 -= int64_lshift21(carry10);
1742
1743 s[0] = s0 >> 0;
1744 s[1] = s0 >> 8;
1745 s[2] = (s0 >> 16) | (s1 << 5);
1746 s[3] = s1 >> 3;
1747 s[4] = s1 >> 11;
1748 s[5] = (s1 >> 19) | (s2 << 2);
1749 s[6] = s2 >> 6;
1750 s[7] = (s2 >> 14) | (s3 << 7);
1751 s[8] = s3 >> 1;
1752 s[9] = s3 >> 9;
1753 s[10] = (s3 >> 17) | (s4 << 4);
1754 s[11] = s4 >> 4;
1755 s[12] = s4 >> 12;
1756 s[13] = (s4 >> 20) | (s5 << 1);
1757 s[14] = s5 >> 7;
1758 s[15] = (s5 >> 15) | (s6 << 6);
1759 s[16] = s6 >> 2;
1760 s[17] = s6 >> 10;
1761 s[18] = (s6 >> 18) | (s7 << 3);
1762 s[19] = s7 >> 5;
1763 s[20] = s7 >> 13;
1764 s[21] = s8 >> 0;
1765 s[22] = s8 >> 8;
1766 s[23] = (s8 >> 16) | (s9 << 5);
1767 s[24] = s9 >> 3;
1768 s[25] = s9 >> 11;
1769 s[26] = (s9 >> 19) | (s10 << 2);
1770 s[27] = s10 >> 6;
1771 s[28] = (s10 >> 14) | (s11 << 7);
1772 s[29] = s11 >> 1;
1773 s[30] = s11 >> 9;
1774 s[31] = s11 >> 17;
1775 }
1776
1777
GFp_x25519_scalar_mult_generic_masked(uint8_t out[32],const uint8_t scalar_masked[32],const uint8_t point[32])1778 void GFp_x25519_scalar_mult_generic_masked(uint8_t out[32],
1779 const uint8_t scalar_masked[32],
1780 const uint8_t point[32]) {
1781 fe x1, x2, z2, x3, z3, tmp0, tmp1;
1782 fe_loose x2l, z2l, x3l, tmp0l, tmp1l;
1783
1784 uint8_t e[32];
1785 GFp_memcpy(e, scalar_masked, 32);
1786 // The following implementation was transcribed to Coq and proven to
1787 // correspond to unary scalar multiplication in affine coordinates given that
1788 // x1 != 0 is the x coordinate of some point on the curve. It was also checked
1789 // in Coq that doing a ladderstep with x1 = x3 = 0 gives z2' = z3' = 0, and z2
1790 // = z3 = 0 gives z2' = z3' = 0. The statement was quantified over the
1791 // underlying field, so it applies to Curve25519 itself and the quadratic
1792 // twist of Curve25519. It was not proven in Coq that prime-field arithmetic
1793 // correctly simulates extension-field arithmetic on prime-field values.
1794 // The decoding of the byte array representation of e was not considered.
1795 // Specification of Montgomery curves in affine coordinates:
1796 // <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Spec/MontgomeryCurve.v#L27>
1797 // Proof that these form a group that is isomorphic to a Weierstrass curve:
1798 // <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curves/Montgomery/AffineProofs.v#L35>
1799 // Coq transcription and correctness proof of the loop (where scalarbits=255):
1800 // <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curves/Montgomery/XZ.v#L118>
1801 // <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curves/Montgomery/XZProofs.v#L278>
1802 // preconditions: 0 <= e < 2^255 (not necessarily e < order), fe_invert(0) = 0
1803 fe_frombytes(&x1, point);
1804 fe_1(&x2);
1805 fe_0(&z2);
1806 fe_copy(&x3, &x1);
1807 fe_1(&z3);
1808
1809 unsigned swap = 0;
1810 int pos;
1811 for (pos = 254; pos >= 0; --pos) {
1812 // loop invariant as of right before the test, for the case where x1 != 0:
1813 // pos >= -1; if z2 = 0 then x2 is nonzero; if z3 = 0 then x3 is nonzero
1814 // let r := e >> (pos+1) in the following equalities of projective points:
1815 // to_xz (r*P) === if swap then (x3, z3) else (x2, z2)
1816 // to_xz ((r+1)*P) === if swap then (x2, z2) else (x3, z3)
1817 // x1 is the nonzero x coordinate of the nonzero point (r*P-(r+1)*P)
1818 unsigned b = 1 & (e[pos / 8] >> (pos & 7));
1819 swap ^= b;
1820 fe_cswap(&x2, &x3, swap);
1821 fe_cswap(&z2, &z3, swap);
1822 swap = b;
1823 // Coq transcription of ladderstep formula (called from transcribed loop):
1824 // <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curves/Montgomery/XZ.v#L89>
1825 // <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curves/Montgomery/XZProofs.v#L131>
1826 // x1 != 0 <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curves/Montgomery/XZProofs.v#L217>
1827 // x1 = 0 <https://github.com/mit-plv/fiat-crypto/blob/2456d821825521f7e03e65882cc3521795b0320f/src/Curves/Montgomery/XZProofs.v#L147>
1828 fe_sub(&tmp0l, &x3, &z3);
1829 fe_sub(&tmp1l, &x2, &z2);
1830 fe_add(&x2l, &x2, &z2);
1831 fe_add(&z2l, &x3, &z3);
1832 fe_mul_tll(&z3, &tmp0l, &x2l);
1833 fe_mul_tll(&z2, &z2l, &tmp1l);
1834 fe_sq_tl(&tmp0, &tmp1l);
1835 fe_sq_tl(&tmp1, &x2l);
1836 fe_add(&x3l, &z3, &z2);
1837 fe_sub(&z2l, &z3, &z2);
1838 fe_mul_ttt(&x2, &tmp1, &tmp0);
1839 fe_sub(&tmp1l, &tmp1, &tmp0);
1840 fe_sq_tl(&z2, &z2l);
1841 fe_mul121666(&z3, &tmp1l);
1842 fe_sq_tl(&x3, &x3l);
1843 fe_add(&tmp0l, &tmp0, &z3);
1844 fe_mul_ttt(&z3, &x1, &z2);
1845 fe_mul_tll(&z2, &tmp1l, &tmp0l);
1846 }
1847 // here pos=-1, so r=e, so to_xz (e*P) === if swap then (x3, z3) else (x2, z2)
1848 fe_cswap(&x2, &x3, swap);
1849 fe_cswap(&z2, &z3, swap);
1850
1851 fe_invert(&z2, &z2);
1852 fe_mul_ttt(&x2, &x2, &z2);
1853 fe_tobytes(out, &x2);
1854 }
1855
GFp_x25519_public_from_private_generic_masked(uint8_t out_public_value[32],const uint8_t private_key_masked[32])1856 void GFp_x25519_public_from_private_generic_masked(uint8_t out_public_value[32],
1857 const uint8_t private_key_masked[32]) {
1858 uint8_t e[32];
1859 GFp_memcpy(e, private_key_masked, 32);
1860
1861 ge_p3 A;
1862 GFp_x25519_ge_scalarmult_base(&A, e);
1863
1864 // We only need the u-coordinate of the curve25519 point. The map is
1865 // u=(y+1)/(1-y). Since y=Y/Z, this gives u=(Z+Y)/(Z-Y).
1866 fe_loose zplusy, zminusy;
1867 fe zminusy_inv;
1868 fe_add(&zplusy, &A.Z, &A.Y);
1869 fe_sub(&zminusy, &A.Z, &A.Y);
1870 fe_loose_invert(&zminusy_inv, &zminusy);
1871 fe_mul_tlt(&zminusy_inv, &zplusy, &zminusy_inv);
1872 fe_tobytes(out_public_value, &zminusy_inv);
1873 }
1874
GFp_x25519_fe_invert(fe * out,const fe * z)1875 void GFp_x25519_fe_invert(fe *out, const fe *z) {
1876 fe_invert(out, z);
1877 }
1878
GFp_x25519_fe_isnegative(const fe * f)1879 uint8_t GFp_x25519_fe_isnegative(const fe *f) {
1880 return (uint8_t)fe_isnegative(f);
1881 }
1882
GFp_x25519_fe_mul_ttt(fe * h,const fe * f,const fe * g)1883 void GFp_x25519_fe_mul_ttt(fe *h, const fe *f, const fe *g) {
1884 fe_mul_ttt(h, f, g);
1885 }
1886
GFp_x25519_fe_neg(fe * f)1887 void GFp_x25519_fe_neg(fe *f) {
1888 fe_loose t;
1889 fe_neg(&t, f);
1890 fe_carry(f, &t);
1891 }
1892
GFp_x25519_fe_tobytes(uint8_t s[32],const fe * h)1893 void GFp_x25519_fe_tobytes(uint8_t s[32], const fe *h) {
1894 fe_tobytes(s, h);
1895 }
1896
GFp_x25519_ge_double_scalarmult_vartime(ge_p2 * r,const uint8_t * a,const ge_p3 * A,const uint8_t * b)1897 void GFp_x25519_ge_double_scalarmult_vartime(ge_p2 *r, const uint8_t *a,
1898 const ge_p3 *A, const uint8_t *b) {
1899 ge_double_scalarmult_vartime(r, a, A, b);
1900 }
1901
GFp_x25519_sc_mask(uint8_t a[32])1902 void GFp_x25519_sc_mask(uint8_t a[32]) {
1903 a[0] &= 248;
1904 a[31] &= 127;
1905 a[31] |= 64;
1906 }
1907
GFp_x25519_sc_muladd(uint8_t * s,const uint8_t * a,const uint8_t * b,const uint8_t * c)1908 void GFp_x25519_sc_muladd(uint8_t *s, const uint8_t *a, const uint8_t *b,
1909 const uint8_t *c) {
1910 sc_muladd(s, a, b, c);
1911 }
1912