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