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