OpenCoverage

curve25519.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/openssl/src/crypto/ec/curve25519.c
Source codeSwitch to Preprocessed file
LineSourceCount
1/*-
2 * Copyright 2016-2018 The OpenSSL Project Authors. All Rights Reserved.-
3 *-
4 * Licensed under the OpenSSL license (the "License"). You may not use-
5 * this file except in compliance with the License. You can obtain a copy-
6 * in the file LICENSE in the source distribution or at-
7 * https://www.openssl.org/source/license.html-
8 */-
9-
10#include <string.h>-
11#include "ec_lcl.h"-
12#include <openssl/sha.h>-
13-
14#if defined(X25519_ASM) && (defined(__x86_64) || defined(__x86_64__) || \-
15 defined(_M_AMD64) || defined(_M_X64))-
16-
17# define BASE_2_64_IMPLEMENTED-
18-
19typedef uint64_t fe64[4];-
20-
21int x25519_fe64_eligible(void);-
22-
23/*-
24 * Following subroutines perform corresponding operations modulo-
25 * 2^256-38, i.e. double the curve modulus. However, inputs and-
26 * outputs are permitted to be partially reduced, i.e. to remain-
27 * in [0..2^256) range. It's all tied up in final fe64_tobytes-
28 * that performs full reduction modulo 2^255-19.-
29 *-
30 * There are no reference C implementations for these.-
31 */-
32void x25519_fe64_mul(fe64 h, const fe64 f, const fe64 g);-
33void x25519_fe64_sqr(fe64 h, const fe64 f);-
34void x25519_fe64_mul121666(fe64 h, fe64 f);-
35void x25519_fe64_add(fe64 h, const fe64 f, const fe64 g);-
36void x25519_fe64_sub(fe64 h, const fe64 f, const fe64 g);-
37void x25519_fe64_tobytes(uint8_t *s, const fe64 f);-
38# define fe64_mul x25519_fe64_mul-
39# define fe64_sqr x25519_fe64_sqr-
40# define fe64_mul121666 x25519_fe64_mul121666-
41# define fe64_add x25519_fe64_add-
42# define fe64_sub x25519_fe64_sub-
43# define fe64_tobytes x25519_fe64_tobytes-
44-
45static uint64_t load_8(const uint8_t *in)-
46{-
47 uint64_t result;-
48-
49 result = in[0];-
50 result |= ((uint64_t)in[1]) << 8;-
51 result |= ((uint64_t)in[2]) << 16;-
52 result |= ((uint64_t)in[3]) << 24;-
53 result |= ((uint64_t)in[4]) << 32;-
54 result |= ((uint64_t)in[5]) << 40;-
55 result |= ((uint64_t)in[6]) << 48;-
56 result |= ((uint64_t)in[7]) << 56;-
57-
58 return result;
never executed: return result;
0
59}-
60-
61static void fe64_frombytes(fe64 h, const uint8_t *s)-
62{-
63 h[0] = load_8(s);-
64 h[1] = load_8(s + 8);-
65 h[2] = load_8(s + 16);-
66 h[3] = load_8(s + 24) & 0x7fffffffffffffff;-
67}
never executed: end of block
0
68-
69static void fe64_0(fe64 h)-
70{-
71 h[0] = 0;-
72 h[1] = 0;-
73 h[2] = 0;-
74 h[3] = 0;-
75}
never executed: end of block
0
76-
77static void fe64_1(fe64 h)-
78{-
79 h[0] = 1;-
80 h[1] = 0;-
81 h[2] = 0;-
82 h[3] = 0;-
83}
never executed: end of block
0
84-
85static void fe64_copy(fe64 h, const fe64 f)-
86{-
87 h[0] = f[0];-
88 h[1] = f[1];-
89 h[2] = f[2];-
90 h[3] = f[3];-
91}
never executed: end of block
0
92-
93static void fe64_cswap(fe64 f, fe64 g, unsigned int b)-
94{-
95 int i;-
96 uint64_t mask = 0 - (uint64_t)b;-
97-
98 for (i = 0; i < 4; i++) {
i < 4Description
TRUEnever evaluated
FALSEnever evaluated
0
99 uint64_t x = f[i] ^ g[i];-
100 x &= mask;-
101 f[i] ^= x;-
102 g[i] ^= x;-
103 }
never executed: end of block
0
104}
never executed: end of block
0
105-
106static void fe64_invert(fe64 out, const fe64 z)-
107{-
108 fe64 t0;-
109 fe64 t1;-
110 fe64 t2;-
111 fe64 t3;-
112 int i;-
113-
114 /*-
115 * Compute z ** -1 = z ** (2 ** 255 - 19 - 2) with the exponent as-
116 * 2 ** 255 - 21 = (2 ** 5) * (2 ** 250 - 1) + 11.-
117 */-
118-
119 /* t0 = z ** 2 */-
120 fe64_sqr(t0, z);-
121-
122 /* t1 = t0 ** (2 ** 2) = z ** 8 */-
123 fe64_sqr(t1, t0);-
124 fe64_sqr(t1, t1);-
125-
126 /* t1 = z * t1 = z ** 9 */-
127 fe64_mul(t1, z, t1);-
128 /* t0 = t0 * t1 = z ** 11 -- stash t0 away for the end. */-
129 fe64_mul(t0, t0, t1);-
130-
131 /* t2 = t0 ** 2 = z ** 22 */-
132 fe64_sqr(t2, t0);-
133-
134 /* t1 = t1 * t2 = z ** (2 ** 5 - 1) */-
135 fe64_mul(t1, t1, t2);-
136-
137 /* t2 = t1 ** (2 ** 5) = z ** ((2 ** 5) * (2 ** 5 - 1)) */-
138 fe64_sqr(t2, t1);-
139 for (i = 1; i < 5; ++i)
i < 5Description
TRUEnever evaluated
FALSEnever evaluated
0
140 fe64_sqr(t2, t2);
never executed: x25519_fe64_sqr(t2, t2);
0
141-
142 /* t1 = t1 * t2 = z ** ((2 ** 5 + 1) * (2 ** 5 - 1)) = z ** (2 ** 10 - 1) */-
143 fe64_mul(t1, t2, t1);-
144-
145 /* Continuing similarly... */-
146-
147 /* t2 = z ** (2 ** 20 - 1) */-
148 fe64_sqr(t2, t1);-
149 for (i = 1; i < 10; ++i)
i < 10Description
TRUEnever evaluated
FALSEnever evaluated
0
150 fe64_sqr(t2, t2);
never executed: x25519_fe64_sqr(t2, t2);
0
151-
152 fe64_mul(t2, t2, t1);-
153-
154 /* t2 = z ** (2 ** 40 - 1) */-
155 fe64_sqr(t3, t2);-
156 for (i = 1; i < 20; ++i)
i < 20Description
TRUEnever evaluated
FALSEnever evaluated
0
157 fe64_sqr(t3, t3);
never executed: x25519_fe64_sqr(t3, t3);
0
158-
159 fe64_mul(t2, t3, t2);-
160-
161 /* t2 = z ** (2 ** 10) * (2 ** 40 - 1) */-
162 for (i = 0; i < 10; ++i)
i < 10Description
TRUEnever evaluated
FALSEnever evaluated
0
163 fe64_sqr(t2, t2);
never executed: x25519_fe64_sqr(t2, t2);
0
164-
165 /* t1 = z ** (2 ** 50 - 1) */-
166 fe64_mul(t1, t2, t1);-
167-
168 /* t2 = z ** (2 ** 100 - 1) */-
169 fe64_sqr(t2, t1);-
170 for (i = 1; i < 50; ++i)
i < 50Description
TRUEnever evaluated
FALSEnever evaluated
0
171 fe64_sqr(t2, t2);
never executed: x25519_fe64_sqr(t2, t2);
0
172-
173 fe64_mul(t2, t2, t1);-
174-
175 /* t2 = z ** (2 ** 200 - 1) */-
176 fe64_sqr(t3, t2);-
177 for (i = 1; i < 100; ++i)
i < 100Description
TRUEnever evaluated
FALSEnever evaluated
0
178 fe64_sqr(t3, t3);
never executed: x25519_fe64_sqr(t3, t3);
0
179-
180 fe64_mul(t2, t3, t2);-
181-
182 /* t2 = z ** ((2 ** 50) * (2 ** 200 - 1) */-
183 for (i = 0; i < 50; ++i)
i < 50Description
TRUEnever evaluated
FALSEnever evaluated
0
184 fe64_sqr(t2, t2);
never executed: x25519_fe64_sqr(t2, t2);
0
185-
186 /* t1 = z ** (2 ** 250 - 1) */-
187 fe64_mul(t1, t2, t1);-
188-
189 /* t1 = z ** ((2 ** 5) * (2 ** 250 - 1)) */-
190 for (i = 0; i < 5; ++i)
i < 5Description
TRUEnever evaluated
FALSEnever evaluated
0
191 fe64_sqr(t1, t1);
never executed: x25519_fe64_sqr(t1, t1);
0
192-
193 /* Recall t0 = z ** 11; out = z ** (2 ** 255 - 21) */-
194 fe64_mul(out, t1, t0);-
195}
never executed: end of block
0
196-
197/*-
198 * Duplicate of original x25519_scalar_mult_generic, but using-
199 * fe64_* subroutines.-
200 */-
201static void x25519_scalar_mulx(uint8_t out[32], const uint8_t scalar[32],-
202 const uint8_t point[32])-
203{-
204 fe64 x1, x2, z2, x3, z3, tmp0, tmp1;-
205 uint8_t e[32];-
206 unsigned swap = 0;-
207 int pos;-
208-
209 memcpy(e, scalar, 32);-
210 e[0] &= 0xf8;-
211 e[31] &= 0x7f;-
212 e[31] |= 0x40;-
213 fe64_frombytes(x1, point);-
214 fe64_1(x2);-
215 fe64_0(z2);-
216 fe64_copy(x3, x1);-
217 fe64_1(z3);-
218-
219 for (pos = 254; pos >= 0; --pos) {
pos >= 0Description
TRUEnever evaluated
FALSEnever evaluated
0
220 unsigned int b = 1 & (e[pos / 8] >> (pos & 7));-
221-
222 swap ^= b;-
223 fe64_cswap(x2, x3, swap);-
224 fe64_cswap(z2, z3, swap);-
225 swap = b;-
226 fe64_sub(tmp0, x3, z3);-
227 fe64_sub(tmp1, x2, z2);-
228 fe64_add(x2, x2, z2);-
229 fe64_add(z2, x3, z3);-
230 fe64_mul(z3, x2, tmp0);-
231 fe64_mul(z2, z2, tmp1);-
232 fe64_sqr(tmp0, tmp1);-
233 fe64_sqr(tmp1, x2);-
234 fe64_add(x3, z3, z2);-
235 fe64_sub(z2, z3, z2);-
236 fe64_mul(x2, tmp1, tmp0);-
237 fe64_sub(tmp1, tmp1, tmp0);-
238 fe64_sqr(z2, z2);-
239 fe64_mul121666(z3, tmp1);-
240 fe64_sqr(x3, x3);-
241 fe64_add(tmp0, tmp0, z3);-
242 fe64_mul(z3, x1, z2);-
243 fe64_mul(z2, tmp1, tmp0);-
244 }
never executed: end of block
0
245-
246 fe64_invert(z2, z2);-
247 fe64_mul(x2, x2, z2);-
248 fe64_tobytes(out, x2);-
249-
250 OPENSSL_cleanse(e, sizeof(e));-
251}
never executed: end of block
0
252#endif-
253-
254#if defined(X25519_ASM) \-
255 || ( (defined(__SIZEOF_INT128__) && __SIZEOF_INT128__ == 16) \-
256 && !defined(__sparc__) \-
257 && !(defined(__ANDROID__) && !defined(__clang__)) )-
258/*-
259 * Base 2^51 implementation. It's virtually no different from reference-
260 * base 2^25.5 implementation in respect to lax boundary conditions for-
261 * intermediate values and even individual limbs. So that whatever you-
262 * know about the reference, applies even here...-
263 */-
264# define BASE_2_51_IMPLEMENTED-
265-
266typedef uint64_t fe51[5];-
267-
268static const uint64_t MASK51 = 0x7ffffffffffff;-
269-
270static uint64_t load_7(const uint8_t *in)-
271{-
272 uint64_t result;-
273-
274 result = in[0];-
275 result |= ((uint64_t)in[1]) << 8;-
276 result |= ((uint64_t)in[2]) << 16;-
277 result |= ((uint64_t)in[3]) << 24;-
278 result |= ((uint64_t)in[4]) << 32;-
279 result |= ((uint64_t)in[5]) << 40;-
280 result |= ((uint64_t)in[6]) << 48;-
281-
282 return result;
executed 5832 times by 1 test: return result;
Executed by:
  • libcrypto.so.1.1
5832
283}-
284-
285static uint64_t load_6(const uint8_t *in)-
286{-
287 uint64_t result;-
288-
289 result = in[0];-
290 result |= ((uint64_t)in[1]) << 8;-
291 result |= ((uint64_t)in[2]) << 16;-
292 result |= ((uint64_t)in[3]) << 24;-
293 result |= ((uint64_t)in[4]) << 32;-
294 result |= ((uint64_t)in[5]) << 40;-
295-
296 return result;
executed 8748 times by 1 test: return result;
Executed by:
  • libcrypto.so.1.1
8748
297}-
298-
299static void fe51_frombytes(fe51 h, const uint8_t *s)-
300{-
301 uint64_t h0 = load_7(s); /* 56 bits */-
302 uint64_t h1 = load_6(s + 7) << 5; /* 53 bits */-
303 uint64_t h2 = load_7(s + 13) << 2; /* 58 bits */-
304 uint64_t h3 = load_6(s + 20) << 7; /* 55 bits */-
305 uint64_t h4 = (load_6(s + 26) & 0x7fffffffffff) << 4; /* 51 bits */-
306-
307 h1 |= h0 >> 51; h0 &= MASK51;-
308 h2 |= h1 >> 51; h1 &= MASK51;-
309 h3 |= h2 >> 51; h2 &= MASK51;-
310 h4 |= h3 >> 51; h3 &= MASK51;-
311-
312 h[0] = h0;-
313 h[1] = h1;-
314 h[2] = h2;-
315 h[3] = h3;-
316 h[4] = h4;-
317}
executed 2916 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
2916
318-
319static void fe51_tobytes(uint8_t *s, const fe51 h)-
320{-
321 uint64_t h0 = h[0];-
322 uint64_t h1 = h[1];-
323 uint64_t h2 = h[2];-
324 uint64_t h3 = h[3];-
325 uint64_t h4 = h[4];-
326 uint64_t q;-
327-
328 /* compare to modulus */-
329 q = (h0 + 19) >> 51;-
330 q = (h1 + q) >> 51;-
331 q = (h2 + q) >> 51;-
332 q = (h3 + q) >> 51;-
333 q = (h4 + q) >> 51;-
334-
335 /* full reduce */-
336 h0 += 19 * q;-
337 h1 += h0 >> 51; h0 &= MASK51;-
338 h2 += h1 >> 51; h1 &= MASK51;-
339 h3 += h2 >> 51; h2 &= MASK51;-
340 h4 += h3 >> 51; h3 &= MASK51;-
341 h4 &= MASK51;-
342-
343 /* smash */-
344 s[0] = (uint8_t)(h0 >> 0);-
345 s[1] = (uint8_t)(h0 >> 8);-
346 s[2] = (uint8_t)(h0 >> 16);-
347 s[3] = (uint8_t)(h0 >> 24);-
348 s[4] = (uint8_t)(h0 >> 32);-
349 s[5] = (uint8_t)(h0 >> 40);-
350 s[6] = (uint8_t)((h0 >> 48) | ((uint32_t)h1 << 3));-
351 s[7] = (uint8_t)(h1 >> 5);-
352 s[8] = (uint8_t)(h1 >> 13);-
353 s[9] = (uint8_t)(h1 >> 21);-
354 s[10] = (uint8_t)(h1 >> 29);-
355 s[11] = (uint8_t)(h1 >> 37);-
356 s[12] = (uint8_t)((h1 >> 45) | ((uint32_t)h2 << 6));-
357 s[13] = (uint8_t)(h2 >> 2);-
358 s[14] = (uint8_t)(h2 >> 10);-
359 s[15] = (uint8_t)(h2 >> 18);-
360 s[16] = (uint8_t)(h2 >> 26);-
361 s[17] = (uint8_t)(h2 >> 34);-
362 s[18] = (uint8_t)(h2 >> 42);-
363 s[19] = (uint8_t)((h2 >> 50) | ((uint32_t)h3 << 1));-
364 s[20] = (uint8_t)(h3 >> 7);-
365 s[21] = (uint8_t)(h3 >> 15);-
366 s[22] = (uint8_t)(h3 >> 23);-
367 s[23] = (uint8_t)(h3 >> 31);-
368 s[24] = (uint8_t)(h3 >> 39);-
369 s[25] = (uint8_t)((h3 >> 47) | ((uint32_t)h4 << 4));-
370 s[26] = (uint8_t)(h4 >> 4);-
371 s[27] = (uint8_t)(h4 >> 12);-
372 s[28] = (uint8_t)(h4 >> 20);-
373 s[29] = (uint8_t)(h4 >> 28);-
374 s[30] = (uint8_t)(h4 >> 36);-
375 s[31] = (uint8_t)(h4 >> 44);-
376}
executed 2916 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
2916
377-
378# if defined(X25519_ASM)-
379void x25519_fe51_mul(fe51 h, const fe51 f, const fe51 g);-
380void x25519_fe51_sqr(fe51 h, const fe51 f);-
381void x25519_fe51_mul121666(fe51 h, fe51 f);-
382# define fe51_mul x25519_fe51_mul-
383# define fe51_sq x25519_fe51_sqr-
384# define fe51_mul121666 x25519_fe51_mul121666-
385# else-
386-
387typedef __uint128_t u128;-
388-
389static void fe51_mul(fe51 h, const fe51 f, const fe51 g)-
390{-
391 u128 h0, h1, h2, h3, h4;-
392 uint64_t f_i, g0, g1, g2, g3, g4;-
393-
394 f_i = f[0];-
395 h0 = (u128)f_i * (g0 = g[0]);-
396 h1 = (u128)f_i * (g1 = g[1]);-
397 h2 = (u128)f_i * (g2 = g[2]);-
398 h3 = (u128)f_i * (g3 = g[3]);-
399 h4 = (u128)f_i * (g4 = g[4]);-
400-
401 f_i = f[1];-
402 h0 += (u128)f_i * (g4 *= 19);-
403 h1 += (u128)f_i * g0;-
404 h2 += (u128)f_i * g1;-
405 h3 += (u128)f_i * g2;-
406 h4 += (u128)f_i * g3;-
407-
408 f_i = f[2];-
409 h0 += (u128)f_i * (g3 *= 19);-
410 h1 += (u128)f_i * g4;-
411 h2 += (u128)f_i * g0;-
412 h3 += (u128)f_i * g1;-
413 h4 += (u128)f_i * g2;-
414-
415 f_i = f[3];-
416 h0 += (u128)f_i * (g2 *= 19);-
417 h1 += (u128)f_i * g3;-
418 h2 += (u128)f_i * g4;-
419 h3 += (u128)f_i * g0;-
420 h4 += (u128)f_i * g1;-
421-
422 f_i = f[4];-
423 h0 += (u128)f_i * (g1 *= 19);-
424 h1 += (u128)f_i * g2;-
425 h2 += (u128)f_i * g3;-
426 h3 += (u128)f_i * g4;-
427 h4 += (u128)f_i * g0;-
428-
429 /* partial [lazy] reduction */-
430 h3 += (uint64_t)(h2 >> 51); g2 = (uint64_t)h2 & MASK51;-
431 h1 += (uint64_t)(h0 >> 51); g0 = (uint64_t)h0 & MASK51;-
432-
433 h4 += (uint64_t)(h3 >> 51); g3 = (uint64_t)h3 & MASK51;-
434 g2 += (uint64_t)(h1 >> 51); g1 = (uint64_t)h1 & MASK51;-
435-
436 g0 += (uint64_t)(h4 >> 51) * 19; g4 = (uint64_t)h4 & MASK51;-
437 g3 += g2 >> 51; g2 &= MASK51;-
438 g1 += g0 >> 51; g0 &= MASK51;-
439-
440 h[0] = g0;-
441 h[1] = g1;-
442 h[2] = g2;-
443 h[3] = g3;-
444 h[4] = g4;-
445}-
446-
447static void fe51_sq(fe51 h, const fe51 f)-
448{-
449# if defined(OPENSSL_SMALL_FOOTPRINT)-
450 fe51_mul(h, f, f);-
451# else-
452 /* dedicated squaring gives 16-25% overall improvement */-
453 uint64_t g0 = f[0];-
454 uint64_t g1 = f[1];-
455 uint64_t g2 = f[2];-
456 uint64_t g3 = f[3];-
457 uint64_t g4 = f[4];-
458 u128 h0, h1, h2, h3, h4;-
459-
460 h0 = (u128)g0 * g0; g0 *= 2;-
461 h1 = (u128)g0 * g1;-
462 h2 = (u128)g0 * g2;-
463 h3 = (u128)g0 * g3;-
464 h4 = (u128)g0 * g4;-
465-
466 g0 = g4; /* borrow g0 */-
467 h3 += (u128)g0 * (g4 *= 19);-
468-
469 h2 += (u128)g1 * g1; g1 *= 2;-
470 h3 += (u128)g1 * g2;-
471 h4 += (u128)g1 * g3;-
472 h0 += (u128)g1 * g4;-
473-
474 g0 = g3; /* borrow g0 */-
475 h1 += (u128)g0 * (g3 *= 19);-
476 h2 += (u128)(g0 * 2) * g4;-
477-
478 h4 += (u128)g2 * g2; g2 *= 2;-
479 h0 += (u128)g2 * g3;-
480 h1 += (u128)g2 * g4;-
481-
482 /* partial [lazy] reduction */-
483 h3 += (uint64_t)(h2 >> 51); g2 = (uint64_t)h2 & MASK51;-
484 h1 += (uint64_t)(h0 >> 51); g0 = (uint64_t)h0 & MASK51;-
485-
486 h4 += (uint64_t)(h3 >> 51); g3 = (uint64_t)h3 & MASK51;-
487 g2 += (uint64_t)(h1 >> 51); g1 = (uint64_t)h1 & MASK51;-
488-
489 g0 += (uint64_t)(h4 >> 51) * 19; g4 = (uint64_t)h4 & MASK51;-
490 g3 += g2 >> 51; g2 &= MASK51;-
491 g1 += g0 >> 51; g0 &= MASK51;-
492-
493 h[0] = g0;-
494 h[1] = g1;-
495 h[2] = g2;-
496 h[3] = g3;-
497 h[4] = g4;-
498# endif-
499}-
500-
501static void fe51_mul121666(fe51 h, fe51 f)-
502{-
503 u128 h0 = f[0] * (u128)121666;-
504 u128 h1 = f[1] * (u128)121666;-
505 u128 h2 = f[2] * (u128)121666;-
506 u128 h3 = f[3] * (u128)121666;-
507 u128 h4 = f[4] * (u128)121666;-
508 uint64_t g0, g1, g2, g3, g4;-
509-
510 h3 += (uint64_t)(h2 >> 51); g2 = (uint64_t)h2 & MASK51;-
511 h1 += (uint64_t)(h0 >> 51); g0 = (uint64_t)h0 & MASK51;-
512-
513 h4 += (uint64_t)(h3 >> 51); g3 = (uint64_t)h3 & MASK51;-
514 g2 += (uint64_t)(h1 >> 51); g1 = (uint64_t)h1 & MASK51;-
515-
516 g0 += (uint64_t)(h4 >> 51) * 19; g4 = (uint64_t)h4 & MASK51;-
517 g3 += g2 >> 51; g2 &= MASK51;-
518 g1 += g0 >> 51; g0 &= MASK51;-
519-
520 h[0] = g0;-
521 h[1] = g1;-
522 h[2] = g2;-
523 h[3] = g3;-
524 h[4] = g4;-
525}-
526# endif-
527-
528static void fe51_add(fe51 h, const fe51 f, const fe51 g)-
529{-
530 h[0] = f[0] + g[0];-
531 h[1] = f[1] + g[1];-
532 h[2] = f[2] + g[2];-
533 h[3] = f[3] + g[3];-
534 h[4] = f[4] + g[4];-
535}
executed 2974320 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
2974320
536-
537static void fe51_sub(fe51 h, const fe51 f, const fe51 g)-
538{-
539 /*-
540 * Add 2*modulus to ensure that result remains positive-
541 * even if subtrahend is partially reduced.-
542 */-
543 h[0] = (f[0] + 0xfffffffffffda) - g[0];-
544 h[1] = (f[1] + 0xffffffffffffe) - g[1];-
545 h[2] = (f[2] + 0xffffffffffffe) - g[2];-
546 h[3] = (f[3] + 0xffffffffffffe) - g[3];-
547 h[4] = (f[4] + 0xffffffffffffe) - g[4];-
548}
executed 2974320 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
2974320
549-
550static void fe51_0(fe51 h)-
551{-
552 h[0] = 0;-
553 h[1] = 0;-
554 h[2] = 0;-
555 h[3] = 0;-
556 h[4] = 0;-
557}
executed 2916 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
2916
558-
559static void fe51_1(fe51 h)-
560{-
561 h[0] = 1;-
562 h[1] = 0;-
563 h[2] = 0;-
564 h[3] = 0;-
565 h[4] = 0;-
566}
executed 5832 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
5832
567-
568static void fe51_copy(fe51 h, const fe51 f)-
569{-
570 h[0] = f[0];-
571 h[1] = f[1];-
572 h[2] = f[2];-
573 h[3] = f[3];-
574 h[4] = f[4];-
575}
executed 2916 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
2916
576-
577static void fe51_cswap(fe51 f, fe51 g, unsigned int b)-
578{-
579 int i;-
580 uint64_t mask = 0 - (uint64_t)b;-
581-
582 for (i = 0; i < 5; i++) {
i < 5Description
TRUEevaluated 7435800 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 1487160 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
1487160-7435800
583 int64_t x = f[i] ^ g[i];-
584 x &= mask;-
585 f[i] ^= x;-
586 g[i] ^= x;-
587 }
executed 7435800 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
7435800
588}
executed 1487160 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
1487160
589-
590static void fe51_invert(fe51 out, const fe51 z)-
591{-
592 fe51 t0;-
593 fe51 t1;-
594 fe51 t2;-
595 fe51 t3;-
596 int i;-
597-
598 /*-
599 * Compute z ** -1 = z ** (2 ** 255 - 19 - 2) with the exponent as-
600 * 2 ** 255 - 21 = (2 ** 5) * (2 ** 250 - 1) + 11.-
601 */-
602-
603 /* t0 = z ** 2 */-
604 fe51_sq(t0, z);-
605-
606 /* t1 = t0 ** (2 ** 2) = z ** 8 */-
607 fe51_sq(t1, t0);-
608 fe51_sq(t1, t1);-
609-
610 /* t1 = z * t1 = z ** 9 */-
611 fe51_mul(t1, z, t1);-
612 /* t0 = t0 * t1 = z ** 11 -- stash t0 away for the end. */-
613 fe51_mul(t0, t0, t1);-
614-
615 /* t2 = t0 ** 2 = z ** 22 */-
616 fe51_sq(t2, t0);-
617-
618 /* t1 = t1 * t2 = z ** (2 ** 5 - 1) */-
619 fe51_mul(t1, t1, t2);-
620-
621 /* t2 = t1 ** (2 ** 5) = z ** ((2 ** 5) * (2 ** 5 - 1)) */-
622 fe51_sq(t2, t1);-
623 for (i = 1; i < 5; ++i)
i < 5Description
TRUEevaluated 11664 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 2916 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
2916-11664
624 fe51_sq(t2, t2);
executed 11664 times by 1 test: x25519_fe51_sqr(t2, t2);
Executed by:
  • libcrypto.so.1.1
11664
625-
626 /* t1 = t1 * t2 = z ** ((2 ** 5 + 1) * (2 ** 5 - 1)) = z ** (2 ** 10 - 1) */-
627 fe51_mul(t1, t2, t1);-
628-
629 /* Continuing similarly... */-
630-
631 /* t2 = z ** (2 ** 20 - 1) */-
632 fe51_sq(t2, t1);-
633 for (i = 1; i < 10; ++i)
i < 10Description
TRUEevaluated 26244 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 2916 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
2916-26244
634 fe51_sq(t2, t2);
executed 26244 times by 1 test: x25519_fe51_sqr(t2, t2);
Executed by:
  • libcrypto.so.1.1
26244
635-
636 fe51_mul(t2, t2, t1);-
637-
638 /* t2 = z ** (2 ** 40 - 1) */-
639 fe51_sq(t3, t2);-
640 for (i = 1; i < 20; ++i)
i < 20Description
TRUEevaluated 55404 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 2916 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
2916-55404
641 fe51_sq(t3, t3);
executed 55404 times by 1 test: x25519_fe51_sqr(t3, t3);
Executed by:
  • libcrypto.so.1.1
55404
642-
643 fe51_mul(t2, t3, t2);-
644-
645 /* t2 = z ** (2 ** 10) * (2 ** 40 - 1) */-
646 for (i = 0; i < 10; ++i)
i < 10Description
TRUEevaluated 29160 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 2916 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
2916-29160
647 fe51_sq(t2, t2);
executed 29160 times by 1 test: x25519_fe51_sqr(t2, t2);
Executed by:
  • libcrypto.so.1.1
29160
648-
649 /* t1 = z ** (2 ** 50 - 1) */-
650 fe51_mul(t1, t2, t1);-
651-
652 /* t2 = z ** (2 ** 100 - 1) */-
653 fe51_sq(t2, t1);-
654 for (i = 1; i < 50; ++i)
i < 50Description
TRUEevaluated 142884 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 2916 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
2916-142884
655 fe51_sq(t2, t2);
executed 142884 times by 1 test: x25519_fe51_sqr(t2, t2);
Executed by:
  • libcrypto.so.1.1
142884
656-
657 fe51_mul(t2, t2, t1);-
658-
659 /* t2 = z ** (2 ** 200 - 1) */-
660 fe51_sq(t3, t2);-
661 for (i = 1; i < 100; ++i)
i < 100Description
TRUEevaluated 288684 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 2916 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
2916-288684
662 fe51_sq(t3, t3);
executed 288684 times by 1 test: x25519_fe51_sqr(t3, t3);
Executed by:
  • libcrypto.so.1.1
288684
663-
664 fe51_mul(t2, t3, t2);-
665-
666 /* t2 = z ** ((2 ** 50) * (2 ** 200 - 1) */-
667 for (i = 0; i < 50; ++i)
i < 50Description
TRUEevaluated 145800 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 2916 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
2916-145800
668 fe51_sq(t2, t2);
executed 145800 times by 1 test: x25519_fe51_sqr(t2, t2);
Executed by:
  • libcrypto.so.1.1
145800
669-
670 /* t1 = z ** (2 ** 250 - 1) */-
671 fe51_mul(t1, t2, t1);-
672-
673 /* t1 = z ** ((2 ** 5) * (2 ** 250 - 1)) */-
674 for (i = 0; i < 5; ++i)
i < 5Description
TRUEevaluated 14580 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 2916 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
2916-14580
675 fe51_sq(t1, t1);
executed 14580 times by 1 test: x25519_fe51_sqr(t1, t1);
Executed by:
  • libcrypto.so.1.1
14580
676-
677 /* Recall t0 = z ** 11; out = z ** (2 ** 255 - 21) */-
678 fe51_mul(out, t1, t0);-
679}
executed 2916 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
2916
680-
681/*-
682 * Duplicate of original x25519_scalar_mult_generic, but using-
683 * fe51_* subroutines.-
684 */-
685static void x25519_scalar_mult(uint8_t out[32], const uint8_t scalar[32],-
686 const uint8_t point[32])-
687{-
688 fe51 x1, x2, z2, x3, z3, tmp0, tmp1;-
689 uint8_t e[32];-
690 unsigned swap = 0;-
691 int pos;-
692-
693# ifdef BASE_2_64_IMPLEMENTED-
694 if (x25519_fe64_eligible()) {
x25519_fe64_eligible()Description
TRUEnever evaluated
FALSEevaluated 2916 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
0-2916
695 x25519_scalar_mulx(out, scalar, point);-
696 return;
never executed: return;
0
697 }-
698# endif-
699-
700 memcpy(e, scalar, 32);-
701 e[0] &= 0xf8;-
702 e[31] &= 0x7f;-
703 e[31] |= 0x40;-
704 fe51_frombytes(x1, point);-
705 fe51_1(x2);-
706 fe51_0(z2);-
707 fe51_copy(x3, x1);-
708 fe51_1(z3);-
709-
710 for (pos = 254; pos >= 0; --pos) {
pos >= 0Description
TRUEevaluated 743580 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 2916 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
2916-743580
711 unsigned int b = 1 & (e[pos / 8] >> (pos & 7));-
712-
713 swap ^= b;-
714 fe51_cswap(x2, x3, swap);-
715 fe51_cswap(z2, z3, swap);-
716 swap = b;-
717 fe51_sub(tmp0, x3, z3);-
718 fe51_sub(tmp1, x2, z2);-
719 fe51_add(x2, x2, z2);-
720 fe51_add(z2, x3, z3);-
721 fe51_mul(z3, tmp0, x2);-
722 fe51_mul(z2, z2, tmp1);-
723 fe51_sq(tmp0, tmp1);-
724 fe51_sq(tmp1, x2);-
725 fe51_add(x3, z3, z2);-
726 fe51_sub(z2, z3, z2);-
727 fe51_mul(x2, tmp1, tmp0);-
728 fe51_sub(tmp1, tmp1, tmp0);-
729 fe51_sq(z2, z2);-
730 fe51_mul121666(z3, tmp1);-
731 fe51_sq(x3, x3);-
732 fe51_add(tmp0, tmp0, z3);-
733 fe51_mul(z3, x1, z2);-
734 fe51_mul(z2, tmp1, tmp0);-
735 }
executed 743580 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
743580
736-
737 fe51_invert(z2, z2);-
738 fe51_mul(x2, x2, z2);-
739 fe51_tobytes(out, x2);-
740-
741 OPENSSL_cleanse(e, sizeof(e));-
742}
executed 2916 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
2916
743#endif-
744-
745/*-
746 * Reference base 2^25.5 implementation.-
747 */-
748/*-
749 * This code is mostly taken from the ref10 version of Ed25519 in SUPERCOP-
750 * 20141124 (http://bench.cr.yp.to/supercop.html).-
751 *-
752 * The field functions are shared by Ed25519 and X25519 where possible.-
753 */-
754-
755/* fe means field element. Here the field is \Z/(2^255-19). An element t,-
756 * entries t[0]...t[9], represents the integer t[0]+2^26 t[1]+2^51 t[2]+2^77-
757 * t[3]+2^102 t[4]+...+2^230 t[9]. Bounds on each t[i] vary depending on-
758 * context. */-
759typedef int32_t fe[10];-
760-
761static const int64_t kBottom25Bits = 0x1ffffffLL;-
762static const int64_t kBottom26Bits = 0x3ffffffLL;-
763static const int64_t kTop39Bits = 0xfffffffffe000000LL;-
764static const int64_t kTop38Bits = 0xfffffffffc000000LL;-
765-
766static uint64_t load_3(const uint8_t *in) {-
767 uint64_t result;-
768 result = (uint64_t)in[0];-
769 result |= ((uint64_t)in[1]) << 8;-
770 result |= ((uint64_t)in[2]) << 16;-
771 return result;
executed 630 times by 1 test: return result;
Executed by:
  • libcrypto.so.1.1
630
772}-
773-
774static uint64_t load_4(const uint8_t *in) {-
775 uint64_t result;-
776 result = (uint64_t)in[0];-
777 result |= ((uint64_t)in[1]) << 8;-
778 result |= ((uint64_t)in[2]) << 16;-
779 result |= ((uint64_t)in[3]) << 24;-
780 return result;
executed 634 times by 1 test: return result;
Executed by:
  • libcrypto.so.1.1
634
781}-
782-
783static void fe_frombytes(fe h, const uint8_t *s) {-
784 /* Ignores top bit of h. */-
785 int64_t h0 = load_4(s);-
786 int64_t h1 = load_3(s + 4) << 6;-
787 int64_t h2 = load_3(s + 7) << 5;-
788 int64_t h3 = load_3(s + 10) << 3;-
789 int64_t h4 = load_3(s + 13) << 2;-
790 int64_t h5 = load_4(s + 16);-
791 int64_t h6 = load_3(s + 20) << 7;-
792 int64_t h7 = load_3(s + 23) << 5;-
793 int64_t h8 = load_3(s + 26) << 4;-
794 int64_t h9 = (load_3(s + 29) & 8388607) << 2;-
795 int64_t carry0;-
796 int64_t carry1;-
797 int64_t carry2;-
798 int64_t carry3;-
799 int64_t carry4;-
800 int64_t carry5;-
801 int64_t carry6;-
802 int64_t carry7;-
803 int64_t carry8;-
804 int64_t carry9;-
805-
806 carry9 = h9 + (1 << 24); h0 += (carry9 >> 25) * 19; h9 -= carry9 & kTop39Bits;-
807 carry1 = h1 + (1 << 24); h2 += carry1 >> 25; h1 -= carry1 & kTop39Bits;-
808 carry3 = h3 + (1 << 24); h4 += carry3 >> 25; h3 -= carry3 & kTop39Bits;-
809 carry5 = h5 + (1 << 24); h6 += carry5 >> 25; h5 -= carry5 & kTop39Bits;-
810 carry7 = h7 + (1 << 24); h8 += carry7 >> 25; h7 -= carry7 & kTop39Bits;-
811-
812 carry0 = h0 + (1 << 25); h1 += carry0 >> 26; h0 -= carry0 & kTop38Bits;-
813 carry2 = h2 + (1 << 25); h3 += carry2 >> 26; h2 -= carry2 & kTop38Bits;-
814 carry4 = h4 + (1 << 25); h5 += carry4 >> 26; h4 -= carry4 & kTop38Bits;-
815 carry6 = h6 + (1 << 25); h7 += carry6 >> 26; h6 -= carry6 & kTop38Bits;-
816 carry8 = h8 + (1 << 25); h9 += carry8 >> 26; h8 -= carry8 & kTop38Bits;-
817-
818 h[0] = (int32_t)h0;-
819 h[1] = (int32_t)h1;-
820 h[2] = (int32_t)h2;-
821 h[3] = (int32_t)h3;-
822 h[4] = (int32_t)h4;-
823 h[5] = (int32_t)h5;-
824 h[6] = (int32_t)h6;-
825 h[7] = (int32_t)h7;-
826 h[8] = (int32_t)h8;-
827 h[9] = (int32_t)h9;-
828}
executed 10 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
10
829-
830/* Preconditions:-
831 * |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.-
832 *-
833 * Write p=2^255-19; q=floor(h/p).-
834 * Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))).-
835 *-
836 * Proof:-
837 * Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4.-
838 * Also have |h-2^230 h9|<2^231 so |19 2^(-255)(h-2^230 h9)|<1/4.-
839 *-
840 * Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9).-
841 * Then 0<y<1.-
842 *-
843 * Write r=h-pq.-
844 * Have 0<=r<=p-1=2^255-20.-
845 * Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1.-
846 *-
847 * Write x=r+19(2^-255)r+y.-
848 * Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q.-
849 *-
850 * Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1))-
851 * so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q. */-
852static void fe_tobytes(uint8_t *s, const fe h) {-
853 int32_t h0 = h[0];-
854 int32_t h1 = h[1];-
855 int32_t h2 = h[2];-
856 int32_t h3 = h[3];-
857 int32_t h4 = h[4];-
858 int32_t h5 = h[5];-
859 int32_t h6 = h[6];-
860 int32_t h7 = h[7];-
861 int32_t h8 = h[8];-
862 int32_t h9 = h[9];-
863 int32_t q;-
864-
865 q = (19 * h9 + (((int32_t) 1) << 24)) >> 25;-
866 q = (h0 + q) >> 26;-
867 q = (h1 + q) >> 25;-
868 q = (h2 + q) >> 26;-
869 q = (h3 + q) >> 25;-
870 q = (h4 + q) >> 26;-
871 q = (h5 + q) >> 25;-
872 q = (h6 + q) >> 26;-
873 q = (h7 + q) >> 25;-
874 q = (h8 + q) >> 26;-
875 q = (h9 + q) >> 25;-
876-
877 /* Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20. */-
878 h0 += 19 * q;-
879 /* Goal: Output h-2^255 q, which is between 0 and 2^255-20. */-
880-
881 h1 += h0 >> 26; h0 &= kBottom26Bits;-
882 h2 += h1 >> 25; h1 &= kBottom25Bits;-
883 h3 += h2 >> 26; h2 &= kBottom26Bits;-
884 h4 += h3 >> 25; h3 &= kBottom25Bits;-
885 h5 += h4 >> 26; h4 &= kBottom26Bits;-
886 h6 += h5 >> 25; h5 &= kBottom25Bits;-
887 h7 += h6 >> 26; h6 &= kBottom26Bits;-
888 h8 += h7 >> 25; h7 &= kBottom25Bits;-
889 h9 += h8 >> 26; h8 &= kBottom26Bits;-
890 h9 &= kBottom25Bits;-
891 /* h10 = carry9 */-
892-
893 /* Goal: Output h0+...+2^255 h10-2^255 q, which is between 0 and 2^255-20.-
894 * Have h0+...+2^230 h9 between 0 and 2^255-1;-
895 * evidently 2^255 h10-2^255 q = 0.-
896 * Goal: Output h0+...+2^230 h9. */-
897-
898 s[0] = (uint8_t)(h0 >> 0);-
899 s[1] = (uint8_t)(h0 >> 8);-
900 s[2] = (uint8_t)(h0 >> 16);-
901 s[3] = (uint8_t)((h0 >> 24) | ((uint32_t)(h1) << 2));-
902 s[4] = (uint8_t)(h1 >> 6);-
903 s[5] = (uint8_t)(h1 >> 14);-
904 s[6] = (uint8_t)((h1 >> 22) | ((uint32_t)(h2) << 3));-
905 s[7] = (uint8_t)(h2 >> 5);-
906 s[8] = (uint8_t)(h2 >> 13);-
907 s[9] = (uint8_t)((h2 >> 21) | ((uint32_t)(h3) << 5));-
908 s[10] = (uint8_t)(h3 >> 3);-
909 s[11] = (uint8_t)(h3 >> 11);-
910 s[12] = (uint8_t)((h3 >> 19) | ((uint32_t)(h4) << 6));-
911 s[13] = (uint8_t)(h4 >> 2);-
912 s[14] = (uint8_t)(h4 >> 10);-
913 s[15] = (uint8_t)(h4 >> 18);-
914 s[16] = (uint8_t)(h5 >> 0);-
915 s[17] = (uint8_t)(h5 >> 8);-
916 s[18] = (uint8_t)(h5 >> 16);-
917 s[19] = (uint8_t)((h5 >> 24) | ((uint32_t)(h6) << 1));-
918 s[20] = (uint8_t)(h6 >> 7);-
919 s[21] = (uint8_t)(h6 >> 15);-
920 s[22] = (uint8_t)((h6 >> 23) | ((uint32_t)(h7) << 3));-
921 s[23] = (uint8_t)(h7 >> 5);-
922 s[24] = (uint8_t)(h7 >> 13);-
923 s[25] = (uint8_t)((h7 >> 21) | ((uint32_t)(h8) << 4));-
924 s[26] = (uint8_t)(h8 >> 4);-
925 s[27] = (uint8_t)(h8 >> 12);-
926 s[28] = (uint8_t)((h8 >> 20) | ((uint32_t)(h9) << 6));-
927 s[29] = (uint8_t)(h9 >> 2);-
928 s[30] = (uint8_t)(h9 >> 10);-
929 s[31] = (uint8_t)(h9 >> 18);-
930}
executed 6366 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
6366
931-
932/* h = f */-
933static void fe_copy(fe h, const fe f) {-
934 memmove(h, f, sizeof(int32_t) * 10);-
935}
executed 822135 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
822135
936-
937/* h = 0 */-
938static
executed 414160 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
void fe_0(fe h) { memset(h, 0, sizeof(int32_t) * 10); }
executed 414160 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
414160
939-
940/* h = 1 */-
941static void fe_1(fe h) {-
942 memset(h, 0, sizeof(int32_t) * 10);-
943 h[0] = 1;-
944}
executed 815780 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
815780
945-
946/* h = f + g-
947 * Can overlap h with f or g.-
948 *-
949 * Preconditions:-
950 * |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.-
951 * |g| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.-
952 *-
953 * Postconditions:-
954 * |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. */-
955static void fe_add(fe h, const fe f, const fe g) {-
956 unsigned i;-
957 for (i = 0; i < 10; i++) {
i < 10Description
TRUEevaluated 16716520 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 1671652 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
1671652-16716520
958 h[i] = f[i] + g[i];-
959 }
executed 16716520 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
16716520
960}
executed 1671652 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
1671652
961-
962/* h = f - g-
963 * Can overlap h with f or g.-
964 *-
965 * Preconditions:-
966 * |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.-
967 * |g| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.-
968 *-
969 * Postconditions:-
970 * |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. */-
971static void fe_sub(fe h, const fe f, const fe g) {-
972 unsigned i;-
973 for (i = 0; i < 10; i++) {
i < 10Description
TRUEevaluated 12967580 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 1296758 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
1296758-12967580
974 h[i] = f[i] - g[i];-
975 }
executed 12967580 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
12967580
976}
executed 1296758 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
1296758
977-
978/* h = f * g-
979 * Can overlap h with f or g.-
980 *-
981 * Preconditions:-
982 * |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.-
983 * |g| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.-
984 *-
985 * Postconditions:-
986 * |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.-
987 *-
988 * Notes on implementation strategy:-
989 *-
990 * Using schoolbook multiplication.-
991 * Karatsuba would save a little in some cost models.-
992 *-
993 * Most multiplications by 2 and 19 are 32-bit precomputations;-
994 * cheaper than 64-bit postcomputations.-
995 *-
996 * There is one remaining multiplication by 19 in the carry chain;-
997 * one *19 precomputation can be merged into this,-
998 * but the resulting data flow is considerably less clean.-
999 *-
1000 * There are 12 carries below.-
1001 * 10 of them are 2-way parallelizable and vectorizable.-
1002 * Can get away with 11 carries, but then data flow is much deeper.-
1003 *-
1004 * With tighter constraints on inputs can squeeze carries into int32. */-
1005static void fe_mul(fe h, const fe f, const fe g) {-
1006 int32_t f0 = f[0];-
1007 int32_t f1 = f[1];-
1008 int32_t f2 = f[2];-
1009 int32_t f3 = f[3];-
1010 int32_t f4 = f[4];-
1011 int32_t f5 = f[5];-
1012 int32_t f6 = f[6];-
1013 int32_t f7 = f[7];-
1014 int32_t f8 = f[8];-
1015 int32_t f9 = f[9];-
1016 int32_t g0 = g[0];-
1017 int32_t g1 = g[1];-
1018 int32_t g2 = g[2];-
1019 int32_t g3 = g[3];-
1020 int32_t g4 = g[4];-
1021 int32_t g5 = g[5];-
1022 int32_t g6 = g[6];-
1023 int32_t g7 = g[7];-
1024 int32_t g8 = g[8];-
1025 int32_t g9 = g[9];-
1026 int32_t g1_19 = 19 * g1; /* 1.959375*2^29 */-
1027 int32_t g2_19 = 19 * g2; /* 1.959375*2^30; still ok */-
1028 int32_t g3_19 = 19 * g3;-
1029 int32_t g4_19 = 19 * g4;-
1030 int32_t g5_19 = 19 * g5;-
1031 int32_t g6_19 = 19 * g6;-
1032 int32_t g7_19 = 19 * g7;-
1033 int32_t g8_19 = 19 * g8;-
1034 int32_t g9_19 = 19 * g9;-
1035 int32_t f1_2 = 2 * f1;-
1036 int32_t f3_2 = 2 * f3;-
1037 int32_t f5_2 = 2 * f5;-
1038 int32_t f7_2 = 2 * f7;-
1039 int32_t f9_2 = 2 * f9;-
1040 int64_t f0g0 = f0 * (int64_t) g0;-
1041 int64_t f0g1 = f0 * (int64_t) g1;-
1042 int64_t f0g2 = f0 * (int64_t) g2;-
1043 int64_t f0g3 = f0 * (int64_t) g3;-
1044 int64_t f0g4 = f0 * (int64_t) g4;-
1045 int64_t f0g5 = f0 * (int64_t) g5;-
1046 int64_t f0g6 = f0 * (int64_t) g6;-
1047 int64_t f0g7 = f0 * (int64_t) g7;-
1048 int64_t f0g8 = f0 * (int64_t) g8;-
1049 int64_t f0g9 = f0 * (int64_t) g9;-
1050 int64_t f1g0 = f1 * (int64_t) g0;-
1051 int64_t f1g1_2 = f1_2 * (int64_t) g1;-
1052 int64_t f1g2 = f1 * (int64_t) g2;-
1053 int64_t f1g3_2 = f1_2 * (int64_t) g3;-
1054 int64_t f1g4 = f1 * (int64_t) g4;-
1055 int64_t f1g5_2 = f1_2 * (int64_t) g5;-
1056 int64_t f1g6 = f1 * (int64_t) g6;-
1057 int64_t f1g7_2 = f1_2 * (int64_t) g7;-
1058 int64_t f1g8 = f1 * (int64_t) g8;-
1059 int64_t f1g9_38 = f1_2 * (int64_t) g9_19;-
1060 int64_t f2g0 = f2 * (int64_t) g0;-
1061 int64_t f2g1 = f2 * (int64_t) g1;-
1062 int64_t f2g2 = f2 * (int64_t) g2;-
1063 int64_t f2g3 = f2 * (int64_t) g3;-
1064 int64_t f2g4 = f2 * (int64_t) g4;-
1065 int64_t f2g5 = f2 * (int64_t) g5;-
1066 int64_t f2g6 = f2 * (int64_t) g6;-
1067 int64_t f2g7 = f2 * (int64_t) g7;-
1068 int64_t f2g8_19 = f2 * (int64_t) g8_19;-
1069 int64_t f2g9_19 = f2 * (int64_t) g9_19;-
1070 int64_t f3g0 = f3 * (int64_t) g0;-
1071 int64_t f3g1_2 = f3_2 * (int64_t) g1;-
1072 int64_t f3g2 = f3 * (int64_t) g2;-
1073 int64_t f3g3_2 = f3_2 * (int64_t) g3;-
1074 int64_t f3g4 = f3 * (int64_t) g4;-
1075 int64_t f3g5_2 = f3_2 * (int64_t) g5;-
1076 int64_t f3g6 = f3 * (int64_t) g6;-
1077 int64_t f3g7_38 = f3_2 * (int64_t) g7_19;-
1078 int64_t f3g8_19 = f3 * (int64_t) g8_19;-
1079 int64_t f3g9_38 = f3_2 * (int64_t) g9_19;-
1080 int64_t f4g0 = f4 * (int64_t) g0;-
1081 int64_t f4g1 = f4 * (int64_t) g1;-
1082 int64_t f4g2 = f4 * (int64_t) g2;-
1083 int64_t f4g3 = f4 * (int64_t) g3;-
1084 int64_t f4g4 = f4 * (int64_t) g4;-
1085 int64_t f4g5 = f4 * (int64_t) g5;-
1086 int64_t f4g6_19 = f4 * (int64_t) g6_19;-
1087 int64_t f4g7_19 = f4 * (int64_t) g7_19;-
1088 int64_t f4g8_19 = f4 * (int64_t) g8_19;-
1089 int64_t f4g9_19 = f4 * (int64_t) g9_19;-
1090 int64_t f5g0 = f5 * (int64_t) g0;-
1091 int64_t f5g1_2 = f5_2 * (int64_t) g1;-
1092 int64_t f5g2 = f5 * (int64_t) g2;-
1093 int64_t f5g3_2 = f5_2 * (int64_t) g3;-
1094 int64_t f5g4 = f5 * (int64_t) g4;-
1095 int64_t f5g5_38 = f5_2 * (int64_t) g5_19;-
1096 int64_t f5g6_19 = f5 * (int64_t) g6_19;-
1097 int64_t f5g7_38 = f5_2 * (int64_t) g7_19;-
1098 int64_t f5g8_19 = f5 * (int64_t) g8_19;-
1099 int64_t f5g9_38 = f5_2 * (int64_t) g9_19;-
1100 int64_t f6g0 = f6 * (int64_t) g0;-
1101 int64_t f6g1 = f6 * (int64_t) g1;-
1102 int64_t f6g2 = f6 * (int64_t) g2;-
1103 int64_t f6g3 = f6 * (int64_t) g3;-
1104 int64_t f6g4_19 = f6 * (int64_t) g4_19;-
1105 int64_t f6g5_19 = f6 * (int64_t) g5_19;-
1106 int64_t f6g6_19 = f6 * (int64_t) g6_19;-
1107 int64_t f6g7_19 = f6 * (int64_t) g7_19;-
1108 int64_t f6g8_19 = f6 * (int64_t) g8_19;-
1109 int64_t f6g9_19 = f6 * (int64_t) g9_19;-
1110 int64_t f7g0 = f7 * (int64_t) g0;-
1111 int64_t f7g1_2 = f7_2 * (int64_t) g1;-
1112 int64_t f7g2 = f7 * (int64_t) g2;-
1113 int64_t f7g3_38 = f7_2 * (int64_t) g3_19;-
1114 int64_t f7g4_19 = f7 * (int64_t) g4_19;-
1115 int64_t f7g5_38 = f7_2 * (int64_t) g5_19;-
1116 int64_t f7g6_19 = f7 * (int64_t) g6_19;-
1117 int64_t f7g7_38 = f7_2 * (int64_t) g7_19;-
1118 int64_t f7g8_19 = f7 * (int64_t) g8_19;-
1119 int64_t f7g9_38 = f7_2 * (int64_t) g9_19;-
1120 int64_t f8g0 = f8 * (int64_t) g0;-
1121 int64_t f8g1 = f8 * (int64_t) g1;-
1122 int64_t f8g2_19 = f8 * (int64_t) g2_19;-
1123 int64_t f8g3_19 = f8 * (int64_t) g3_19;-
1124 int64_t f8g4_19 = f8 * (int64_t) g4_19;-
1125 int64_t f8g5_19 = f8 * (int64_t) g5_19;-
1126 int64_t f8g6_19 = f8 * (int64_t) g6_19;-
1127 int64_t f8g7_19 = f8 * (int64_t) g7_19;-
1128 int64_t f8g8_19 = f8 * (int64_t) g8_19;-
1129 int64_t f8g9_19 = f8 * (int64_t) g9_19;-
1130 int64_t f9g0 = f9 * (int64_t) g0;-
1131 int64_t f9g1_38 = f9_2 * (int64_t) g1_19;-
1132 int64_t f9g2_19 = f9 * (int64_t) g2_19;-
1133 int64_t f9g3_38 = f9_2 * (int64_t) g3_19;-
1134 int64_t f9g4_19 = f9 * (int64_t) g4_19;-
1135 int64_t f9g5_38 = f9_2 * (int64_t) g5_19;-
1136 int64_t f9g6_19 = f9 * (int64_t) g6_19;-
1137 int64_t f9g7_38 = f9_2 * (int64_t) g7_19;-
1138 int64_t f9g8_19 = f9 * (int64_t) g8_19;-
1139 int64_t f9g9_38 = f9_2 * (int64_t) g9_19;-
1140 int64_t h0 = f0g0+f1g9_38+f2g8_19+f3g7_38+f4g6_19+f5g5_38+f6g4_19+f7g3_38+f8g2_19+f9g1_38;-
1141 int64_t h1 = f0g1+f1g0 +f2g9_19+f3g8_19+f4g7_19+f5g6_19+f6g5_19+f7g4_19+f8g3_19+f9g2_19;-
1142 int64_t h2 = f0g2+f1g1_2 +f2g0 +f3g9_38+f4g8_19+f5g7_38+f6g6_19+f7g5_38+f8g4_19+f9g3_38;-
1143 int64_t h3 = f0g3+f1g2 +f2g1 +f3g0 +f4g9_19+f5g8_19+f6g7_19+f7g6_19+f8g5_19+f9g4_19;-
1144 int64_t h4 = f0g4+f1g3_2 +f2g2 +f3g1_2 +f4g0 +f5g9_38+f6g8_19+f7g7_38+f8g6_19+f9g5_38;-
1145 int64_t h5 = f0g5+f1g4 +f2g3 +f3g2 +f4g1 +f5g0 +f6g9_19+f7g8_19+f8g7_19+f9g6_19;-
1146 int64_t h6 = f0g6+f1g5_2 +f2g4 +f3g3_2 +f4g2 +f5g1_2 +f6g0 +f7g9_38+f8g8_19+f9g7_38;-
1147 int64_t h7 = f0g7+f1g6 +f2g5 +f3g4 +f4g3 +f5g2 +f6g1 +f7g0 +f8g9_19+f9g8_19;-
1148 int64_t h8 = f0g8+f1g7_2 +f2g6 +f3g5_2 +f4g4 +f5g3_2 +f6g2 +f7g1_2 +f8g0 +f9g9_38;-
1149 int64_t h9 = f0g9+f1g8 +f2g7 +f3g6 +f4g5 +f5g4 +f6g3 +f7g2 +f8g1 +f9g0 ;-
1150 int64_t carry0;-
1151 int64_t carry1;-
1152 int64_t carry2;-
1153 int64_t carry3;-
1154 int64_t carry4;-
1155 int64_t carry5;-
1156 int64_t carry6;-
1157 int64_t carry7;-
1158 int64_t carry8;-
1159 int64_t carry9;-
1160-
1161 /* |h0| <= (1.65*1.65*2^52*(1+19+19+19+19)+1.65*1.65*2^50*(38+38+38+38+38))-
1162 * i.e. |h0| <= 1.4*2^60; narrower ranges for h2, h4, h6, h8-
1163 * |h1| <= (1.65*1.65*2^51*(1+1+19+19+19+19+19+19+19+19))-
1164 * i.e. |h1| <= 1.7*2^59; narrower ranges for h3, h5, h7, h9 */-
1165-
1166 carry0 = h0 + (1 << 25); h1 += carry0 >> 26; h0 -= carry0 & kTop38Bits;-
1167 carry4 = h4 + (1 << 25); h5 += carry4 >> 26; h4 -= carry4 & kTop38Bits;-
1168 /* |h0| <= 2^25 */-
1169 /* |h4| <= 2^25 */-
1170 /* |h1| <= 1.71*2^59 */-
1171 /* |h5| <= 1.71*2^59 */-
1172-
1173 carry1 = h1 + (1 << 24); h2 += carry1 >> 25; h1 -= carry1 & kTop39Bits;-
1174 carry5 = h5 + (1 << 24); h6 += carry5 >> 25; h5 -= carry5 & kTop39Bits;-
1175 /* |h1| <= 2^24; from now on fits into int32 */-
1176 /* |h5| <= 2^24; from now on fits into int32 */-
1177 /* |h2| <= 1.41*2^60 */-
1178 /* |h6| <= 1.41*2^60 */-
1179-
1180 carry2 = h2 + (1 << 25); h3 += carry2 >> 26; h2 -= carry2 & kTop38Bits;-
1181 carry6 = h6 + (1 << 25); h7 += carry6 >> 26; h6 -= carry6 & kTop38Bits;-
1182 /* |h2| <= 2^25; from now on fits into int32 unchanged */-
1183 /* |h6| <= 2^25; from now on fits into int32 unchanged */-
1184 /* |h3| <= 1.71*2^59 */-
1185 /* |h7| <= 1.71*2^59 */-
1186-
1187 carry3 = h3 + (1 << 24); h4 += carry3 >> 25; h3 -= carry3 & kTop39Bits;-
1188 carry7 = h7 + (1 << 24); h8 += carry7 >> 25; h7 -= carry7 & kTop39Bits;-
1189 /* |h3| <= 2^24; from now on fits into int32 unchanged */-
1190 /* |h7| <= 2^24; from now on fits into int32 unchanged */-
1191 /* |h4| <= 1.72*2^34 */-
1192 /* |h8| <= 1.41*2^60 */-
1193-
1194 carry4 = h4 + (1 << 25); h5 += carry4 >> 26; h4 -= carry4 & kTop38Bits;-
1195 carry8 = h8 + (1 << 25); h9 += carry8 >> 26; h8 -= carry8 & kTop38Bits;-
1196 /* |h4| <= 2^25; from now on fits into int32 unchanged */-
1197 /* |h8| <= 2^25; from now on fits into int32 unchanged */-
1198 /* |h5| <= 1.01*2^24 */-
1199 /* |h9| <= 1.71*2^59 */-
1200-
1201 carry9 = h9 + (1 << 24); h0 += (carry9 >> 25) * 19; h9 -= carry9 & kTop39Bits;-
1202 /* |h9| <= 2^24; from now on fits into int32 unchanged */-
1203 /* |h0| <= 1.1*2^39 */-
1204-
1205 carry0 = h0 + (1 << 25); h1 += carry0 >> 26; h0 -= carry0 & kTop38Bits;-
1206 /* |h0| <= 2^25; from now on fits into int32 unchanged */-
1207 /* |h1| <= 1.01*2^24 */-
1208-
1209 h[0] = (int32_t)h0;-
1210 h[1] = (int32_t)h1;-
1211 h[2] = (int32_t)h2;-
1212 h[3] = (int32_t)h3;-
1213 h[4] = (int32_t)h4;-
1214 h[5] = (int32_t)h5;-
1215 h[6] = (int32_t)h6;-
1216 h[7] = (int32_t)h7;-
1217 h[8] = (int32_t)h8;-
1218 h[9] = (int32_t)h9;-
1219}
executed 2983050 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
2983050
1220-
1221/* h = f * f-
1222 * Can overlap h with f.-
1223 *-
1224 * Preconditions:-
1225 * |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.-
1226 *-
1227 * Postconditions:-
1228 * |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.-
1229 *-
1230 * See fe_mul.c for discussion of implementation strategy. */-
1231static void fe_sq(fe h, const fe f) {-
1232 int32_t f0 = f[0];-
1233 int32_t f1 = f[1];-
1234 int32_t f2 = f[2];-
1235 int32_t f3 = f[3];-
1236 int32_t f4 = f[4];-
1237 int32_t f5 = f[5];-
1238 int32_t f6 = f[6];-
1239 int32_t f7 = f[7];-
1240 int32_t f8 = f[8];-
1241 int32_t f9 = f[9];-
1242 int32_t f0_2 = 2 * f0;-
1243 int32_t f1_2 = 2 * f1;-
1244 int32_t f2_2 = 2 * f2;-
1245 int32_t f3_2 = 2 * f3;-
1246 int32_t f4_2 = 2 * f4;-
1247 int32_t f5_2 = 2 * f5;-
1248 int32_t f6_2 = 2 * f6;-
1249 int32_t f7_2 = 2 * f7;-
1250 int32_t f5_38 = 38 * f5; /* 1.959375*2^30 */-
1251 int32_t f6_19 = 19 * f6; /* 1.959375*2^30 */-
1252 int32_t f7_38 = 38 * f7; /* 1.959375*2^30 */-
1253 int32_t f8_19 = 19 * f8; /* 1.959375*2^30 */-
1254 int32_t f9_38 = 38 * f9; /* 1.959375*2^30 */-
1255 int64_t f0f0 = f0 * (int64_t) f0;-
1256 int64_t f0f1_2 = f0_2 * (int64_t) f1;-
1257 int64_t f0f2_2 = f0_2 * (int64_t) f2;-
1258 int64_t f0f3_2 = f0_2 * (int64_t) f3;-
1259 int64_t f0f4_2 = f0_2 * (int64_t) f4;-
1260 int64_t f0f5_2 = f0_2 * (int64_t) f5;-
1261 int64_t f0f6_2 = f0_2 * (int64_t) f6;-
1262 int64_t f0f7_2 = f0_2 * (int64_t) f7;-
1263 int64_t f0f8_2 = f0_2 * (int64_t) f8;-
1264 int64_t f0f9_2 = f0_2 * (int64_t) f9;-
1265 int64_t f1f1_2 = f1_2 * (int64_t) f1;-
1266 int64_t f1f2_2 = f1_2 * (int64_t) f2;-
1267 int64_t f1f3_4 = f1_2 * (int64_t) f3_2;-
1268 int64_t f1f4_2 = f1_2 * (int64_t) f4;-
1269 int64_t f1f5_4 = f1_2 * (int64_t) f5_2;-
1270 int64_t f1f6_2 = f1_2 * (int64_t) f6;-
1271 int64_t f1f7_4 = f1_2 * (int64_t) f7_2;-
1272 int64_t f1f8_2 = f1_2 * (int64_t) f8;-
1273 int64_t f1f9_76 = f1_2 * (int64_t) f9_38;-
1274 int64_t f2f2 = f2 * (int64_t) f2;-
1275 int64_t f2f3_2 = f2_2 * (int64_t) f3;-
1276 int64_t f2f4_2 = f2_2 * (int64_t) f4;-
1277 int64_t f2f5_2 = f2_2 * (int64_t) f5;-
1278 int64_t f2f6_2 = f2_2 * (int64_t) f6;-
1279 int64_t f2f7_2 = f2_2 * (int64_t) f7;-
1280 int64_t f2f8_38 = f2_2 * (int64_t) f8_19;-
1281 int64_t f2f9_38 = f2 * (int64_t) f9_38;-
1282 int64_t f3f3_2 = f3_2 * (int64_t) f3;-
1283 int64_t f3f4_2 = f3_2 * (int64_t) f4;-
1284 int64_t f3f5_4 = f3_2 * (int64_t) f5_2;-
1285 int64_t f3f6_2 = f3_2 * (int64_t) f6;-
1286 int64_t f3f7_76 = f3_2 * (int64_t) f7_38;-
1287 int64_t f3f8_38 = f3_2 * (int64_t) f8_19;-
1288 int64_t f3f9_76 = f3_2 * (int64_t) f9_38;-
1289 int64_t f4f4 = f4 * (int64_t) f4;-
1290 int64_t f4f5_2 = f4_2 * (int64_t) f5;-
1291 int64_t f4f6_38 = f4_2 * (int64_t) f6_19;-
1292 int64_t f4f7_38 = f4 * (int64_t) f7_38;-
1293 int64_t f4f8_38 = f4_2 * (int64_t) f8_19;-
1294 int64_t f4f9_38 = f4 * (int64_t) f9_38;-
1295 int64_t f5f5_38 = f5 * (int64_t) f5_38;-
1296 int64_t f5f6_38 = f5_2 * (int64_t) f6_19;-
1297 int64_t f5f7_76 = f5_2 * (int64_t) f7_38;-
1298 int64_t f5f8_38 = f5_2 * (int64_t) f8_19;-
1299 int64_t f5f9_76 = f5_2 * (int64_t) f9_38;-
1300 int64_t f6f6_19 = f6 * (int64_t) f6_19;-
1301 int64_t f6f7_38 = f6 * (int64_t) f7_38;-
1302 int64_t f6f8_38 = f6_2 * (int64_t) f8_19;-
1303 int64_t f6f9_38 = f6 * (int64_t) f9_38;-
1304 int64_t f7f7_38 = f7 * (int64_t) f7_38;-
1305 int64_t f7f8_38 = f7_2 * (int64_t) f8_19;-
1306 int64_t f7f9_76 = f7_2 * (int64_t) f9_38;-
1307 int64_t f8f8_19 = f8 * (int64_t) f8_19;-
1308 int64_t f8f9_38 = f8 * (int64_t) f9_38;-
1309 int64_t f9f9_38 = f9 * (int64_t) f9_38;-
1310 int64_t h0 = f0f0 +f1f9_76+f2f8_38+f3f7_76+f4f6_38+f5f5_38;-
1311 int64_t h1 = f0f1_2+f2f9_38+f3f8_38+f4f7_38+f5f6_38;-
1312 int64_t h2 = f0f2_2+f1f1_2 +f3f9_76+f4f8_38+f5f7_76+f6f6_19;-
1313 int64_t h3 = f0f3_2+f1f2_2 +f4f9_38+f5f8_38+f6f7_38;-
1314 int64_t h4 = f0f4_2+f1f3_4 +f2f2 +f5f9_76+f6f8_38+f7f7_38;-
1315 int64_t h5 = f0f5_2+f1f4_2 +f2f3_2 +f6f9_38+f7f8_38;-
1316 int64_t h6 = f0f6_2+f1f5_4 +f2f4_2 +f3f3_2 +f7f9_76+f8f8_19;-
1317 int64_t h7 = f0f7_2+f1f6_2 +f2f5_2 +f3f4_2 +f8f9_38;-
1318 int64_t h8 = f0f8_2+f1f7_4 +f2f6_2 +f3f5_4 +f4f4 +f9f9_38;-
1319 int64_t h9 = f0f9_2+f1f8_2 +f2f7_2 +f3f6_2 +f4f5_2;-
1320 int64_t carry0;-
1321 int64_t carry1;-
1322 int64_t carry2;-
1323 int64_t carry3;-
1324 int64_t carry4;-
1325 int64_t carry5;-
1326 int64_t carry6;-
1327 int64_t carry7;-
1328 int64_t carry8;-
1329 int64_t carry9;-
1330-
1331 carry0 = h0 + (1 << 25); h1 += carry0 >> 26; h0 -= carry0 & kTop38Bits;-
1332 carry4 = h4 + (1 << 25); h5 += carry4 >> 26; h4 -= carry4 & kTop38Bits;-
1333-
1334 carry1 = h1 + (1 << 24); h2 += carry1 >> 25; h1 -= carry1 & kTop39Bits;-
1335 carry5 = h5 + (1 << 24); h6 += carry5 >> 25; h5 -= carry5 & kTop39Bits;-
1336-
1337 carry2 = h2 + (1 << 25); h3 += carry2 >> 26; h2 -= carry2 & kTop38Bits;-
1338 carry6 = h6 + (1 << 25); h7 += carry6 >> 26; h6 -= carry6 & kTop38Bits;-
1339-
1340 carry3 = h3 + (1 << 24); h4 += carry3 >> 25; h3 -= carry3 & kTop39Bits;-
1341 carry7 = h7 + (1 << 24); h8 += carry7 >> 25; h7 -= carry7 & kTop39Bits;-
1342-
1343 carry4 = h4 + (1 << 25); h5 += carry4 >> 26; h4 -= carry4 & kTop38Bits;-
1344 carry8 = h8 + (1 << 25); h9 += carry8 >> 26; h8 -= carry8 & kTop38Bits;-
1345-
1346 carry9 = h9 + (1 << 24); h0 += (carry9 >> 25) * 19; h9 -= carry9 & kTop39Bits;-
1347-
1348 carry0 = h0 + (1 << 25); h1 += carry0 >> 26; h0 -= carry0 & kTop38Bits;-
1349-
1350 h[0] = (int32_t)h0;-
1351 h[1] = (int32_t)h1;-
1352 h[2] = (int32_t)h2;-
1353 h[3] = (int32_t)h3;-
1354 h[4] = (int32_t)h4;-
1355 h[5] = (int32_t)h5;-
1356 h[6] = (int32_t)h6;-
1357 h[7] = (int32_t)h7;-
1358 h[8] = (int32_t)h8;-
1359 h[9] = (int32_t)h9;-
1360}
executed 1681806 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
1681806
1361-
1362static void fe_invert(fe out, const fe z) {-
1363 fe t0;-
1364 fe t1;-
1365 fe t2;-
1366 fe t3;-
1367 int i;-
1368-
1369 /*-
1370 * Compute z ** -1 = z ** (2 ** 255 - 19 - 2) with the exponent as-
1371 * 2 ** 255 - 21 = (2 ** 5) * (2 ** 250 - 1) + 11.-
1372 */-
1373-
1374 /* t0 = z ** 2 */-
1375 fe_sq(t0, z);-
1376-
1377 /* t1 = t0 ** (2 ** 2) = z ** 8 */-
1378 fe_sq(t1, t0);-
1379 fe_sq(t1, t1);-
1380-
1381 /* t1 = z * t1 = z ** 9 */-
1382 fe_mul(t1, z, t1);-
1383 /* t0 = t0 * t1 = z ** 11 -- stash t0 away for the end. */-
1384 fe_mul(t0, t0, t1);-
1385-
1386 /* t2 = t0 ** 2 = z ** 22 */-
1387 fe_sq(t2, t0);-
1388-
1389 /* t1 = t1 * t2 = z ** (2 ** 5 - 1) */-
1390 fe_mul(t1, t1, t2);-
1391-
1392 /* t2 = t1 ** (2 ** 5) = z ** ((2 ** 5) * (2 ** 5 - 1)) */-
1393 fe_sq(t2, t1);-
1394 for (i = 1; i < 5; ++i) {
i < 5Description
TRUEevaluated 25140 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 6285 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
6285-25140
1395 fe_sq(t2, t2);-
1396 }
executed 25140 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
25140
1397-
1398 /* t1 = t1 * t2 = z ** ((2 ** 5 + 1) * (2 ** 5 - 1)) = z ** (2 ** 10 - 1) */-
1399 fe_mul(t1, t2, t1);-
1400-
1401 /* Continuing similarly... */-
1402-
1403 /* t2 = z ** (2 ** 20 - 1) */-
1404 fe_sq(t2, t1);-
1405 for (i = 1; i < 10; ++i) {
i < 10Description
TRUEevaluated 56565 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 6285 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
6285-56565
1406 fe_sq(t2, t2);-
1407 }
executed 56565 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
56565
1408 fe_mul(t2, t2, t1);-
1409-
1410 /* t2 = z ** (2 ** 40 - 1) */-
1411 fe_sq(t3, t2);-
1412 for (i = 1; i < 20; ++i) {
i < 20Description
TRUEevaluated 119415 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 6285 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
6285-119415
1413 fe_sq(t3, t3);-
1414 }
executed 119415 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
119415
1415 fe_mul(t2, t3, t2);-
1416-
1417 /* t2 = z ** (2 ** 10) * (2 ** 40 - 1) */-
1418 for (i = 0; i < 10; ++i) {
i < 10Description
TRUEevaluated 62850 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 6285 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
6285-62850
1419 fe_sq(t2, t2);-
1420 }
executed 62850 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
62850
1421 /* t1 = z ** (2 ** 50 - 1) */-
1422 fe_mul(t1, t2, t1);-
1423-
1424 /* t2 = z ** (2 ** 100 - 1) */-
1425 fe_sq(t2, t1);-
1426 for (i = 1; i < 50; ++i) {
i < 50Description
TRUEevaluated 307965 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 6285 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
6285-307965
1427 fe_sq(t2, t2);-
1428 }
executed 307965 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
307965
1429 fe_mul(t2, t2, t1);-
1430-
1431 /* t2 = z ** (2 ** 200 - 1) */-
1432 fe_sq(t3, t2);-
1433 for (i = 1; i < 100; ++i) {
i < 100Description
TRUEevaluated 622215 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 6285 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
6285-622215
1434 fe_sq(t3, t3);-
1435 }
executed 622215 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
622215
1436 fe_mul(t2, t3, t2);-
1437-
1438 /* t2 = z ** ((2 ** 50) * (2 ** 200 - 1) */-
1439 fe_sq(t2, t2);-
1440 for (i = 1; i < 50; ++i) {
i < 50Description
TRUEevaluated 307965 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 6285 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
6285-307965
1441 fe_sq(t2, t2);-
1442 }
executed 307965 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
307965
1443-
1444 /* t1 = z ** (2 ** 250 - 1) */-
1445 fe_mul(t1, t2, t1);-
1446-
1447 /* t1 = z ** ((2 ** 5) * (2 ** 250 - 1)) */-
1448 fe_sq(t1, t1);-
1449 for (i = 1; i < 5; ++i) {
i < 5Description
TRUEevaluated 25140 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 6285 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
6285-25140
1450 fe_sq(t1, t1);-
1451 }
executed 25140 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
25140
1452-
1453 /* Recall t0 = z ** 11; out = z ** (2 ** 255 - 21) */-
1454 fe_mul(out, t1, t0);-
1455}
executed 6285 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
6285
1456-
1457/* h = -f-
1458 *-
1459 * Preconditions:-
1460 * |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.-
1461 *-
1462 * Postconditions:-
1463 * |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. */-
1464static void fe_neg(fe h, const fe f) {-
1465 unsigned i;-
1466 for (i = 0; i < 10; i++) {
i < 10Description
TRUEevaluated 4016270 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 401627 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
401627-4016270
1467 h[i] = -f[i];-
1468 }
executed 4016270 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
4016270
1469}
executed 401627 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
401627
1470-
1471/* Replace (f,g) with (g,g) if b == 1;-
1472 * replace (f,g) with (f,g) if b == 0.-
1473 *-
1474 * Preconditions: b in {0,1}. */-
1475static void fe_cmov(fe f, const fe g, unsigned b) {-
1476 size_t i;-
1477 b = 0-b;-
1478 for (i = 0; i < 10; i++) {
i < 10Description
TRUEevaluated 108432000 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 10843200 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
10843200-108432000
1479 int32_t x = f[i] ^ g[i];-
1480 x &= b;-
1481 f[i] ^= x;-
1482 }
executed 108432000 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
108432000
1483}
executed 10843200 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
10843200
1484-
1485/* return 0 if f == 0-
1486 * return 1 if f != 0-
1487 *-
1488 * Preconditions:-
1489 * |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. */-
1490static int fe_isnonzero(const fe f) {-
1491 uint8_t s[32];-
1492 static const uint8_t zero[32] = {0};-
1493 fe_tobytes(s, f);-
1494-
1495 return CRYPTO_memcmp(s, zero, sizeof(zero)) != 0;
executed 15 times by 1 test: return CRYPTO_memcmp(s, zero, sizeof(zero)) != 0;
Executed by:
  • libcrypto.so.1.1
15
1496}-
1497-
1498/* return 1 if f is in {1,3,5,...,q-2}-
1499 * return 0 if f is in {0,2,4,...,q-1}-
1500 *-
1501 * Preconditions:-
1502 * |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. */-
1503static int fe_isnegative(const fe f) {-
1504 uint8_t s[32];-
1505 fe_tobytes(s, f);-
1506 return s[0] & 1;
executed 66 times by 1 test: return s[0] & 1;
Executed by:
  • libcrypto.so.1.1
66
1507}-
1508-
1509/* h = 2 * f * f-
1510 * Can overlap h with f.-
1511 *-
1512 * Preconditions:-
1513 * |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.-
1514 *-
1515 * Postconditions:-
1516 * |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.-
1517 *-
1518 * See fe_mul.c for discussion of implementation strategy. */-
1519static void fe_sq2(fe h, const fe f) {-
1520 int32_t f0 = f[0];-
1521 int32_t f1 = f[1];-
1522 int32_t f2 = f[2];-
1523 int32_t f3 = f[3];-
1524 int32_t f4 = f[4];-
1525 int32_t f5 = f[5];-
1526 int32_t f6 = f[6];-
1527 int32_t f7 = f[7];-
1528 int32_t f8 = f[8];-
1529 int32_t f9 = f[9];-
1530 int32_t f0_2 = 2 * f0;-
1531 int32_t f1_2 = 2 * f1;-
1532 int32_t f2_2 = 2 * f2;-
1533 int32_t f3_2 = 2 * f3;-
1534 int32_t f4_2 = 2 * f4;-
1535 int32_t f5_2 = 2 * f5;-
1536 int32_t f6_2 = 2 * f6;-
1537 int32_t f7_2 = 2 * f7;-
1538 int32_t f5_38 = 38 * f5; /* 1.959375*2^30 */-
1539 int32_t f6_19 = 19 * f6; /* 1.959375*2^30 */-
1540 int32_t f7_38 = 38 * f7; /* 1.959375*2^30 */-
1541 int32_t f8_19 = 19 * f8; /* 1.959375*2^30 */-
1542 int32_t f9_38 = 38 * f9; /* 1.959375*2^30 */-
1543 int64_t f0f0 = f0 * (int64_t) f0;-
1544 int64_t f0f1_2 = f0_2 * (int64_t) f1;-
1545 int64_t f0f2_2 = f0_2 * (int64_t) f2;-
1546 int64_t f0f3_2 = f0_2 * (int64_t) f3;-
1547 int64_t f0f4_2 = f0_2 * (int64_t) f4;-
1548 int64_t f0f5_2 = f0_2 * (int64_t) f5;-
1549 int64_t f0f6_2 = f0_2 * (int64_t) f6;-
1550 int64_t f0f7_2 = f0_2 * (int64_t) f7;-
1551 int64_t f0f8_2 = f0_2 * (int64_t) f8;-
1552 int64_t f0f9_2 = f0_2 * (int64_t) f9;-
1553 int64_t f1f1_2 = f1_2 * (int64_t) f1;-
1554 int64_t f1f2_2 = f1_2 * (int64_t) f2;-
1555 int64_t f1f3_4 = f1_2 * (int64_t) f3_2;-
1556 int64_t f1f4_2 = f1_2 * (int64_t) f4;-
1557 int64_t f1f5_4 = f1_2 * (int64_t) f5_2;-
1558 int64_t f1f6_2 = f1_2 * (int64_t) f6;-
1559 int64_t f1f7_4 = f1_2 * (int64_t) f7_2;-
1560 int64_t f1f8_2 = f1_2 * (int64_t) f8;-
1561 int64_t f1f9_76 = f1_2 * (int64_t) f9_38;-
1562 int64_t f2f2 = f2 * (int64_t) f2;-
1563 int64_t f2f3_2 = f2_2 * (int64_t) f3;-
1564 int64_t f2f4_2 = f2_2 * (int64_t) f4;-
1565 int64_t f2f5_2 = f2_2 * (int64_t) f5;-
1566 int64_t f2f6_2 = f2_2 * (int64_t) f6;-
1567 int64_t f2f7_2 = f2_2 * (int64_t) f7;-
1568 int64_t f2f8_38 = f2_2 * (int64_t) f8_19;-
1569 int64_t f2f9_38 = f2 * (int64_t) f9_38;-
1570 int64_t f3f3_2 = f3_2 * (int64_t) f3;-
1571 int64_t f3f4_2 = f3_2 * (int64_t) f4;-
1572 int64_t f3f5_4 = f3_2 * (int64_t) f5_2;-
1573 int64_t f3f6_2 = f3_2 * (int64_t) f6;-
1574 int64_t f3f7_76 = f3_2 * (int64_t) f7_38;-
1575 int64_t f3f8_38 = f3_2 * (int64_t) f8_19;-
1576 int64_t f3f9_76 = f3_2 * (int64_t) f9_38;-
1577 int64_t f4f4 = f4 * (int64_t) f4;-
1578 int64_t f4f5_2 = f4_2 * (int64_t) f5;-
1579 int64_t f4f6_38 = f4_2 * (int64_t) f6_19;-
1580 int64_t f4f7_38 = f4 * (int64_t) f7_38;-
1581 int64_t f4f8_38 = f4_2 * (int64_t) f8_19;-
1582 int64_t f4f9_38 = f4 * (int64_t) f9_38;-
1583 int64_t f5f5_38 = f5 * (int64_t) f5_38;-
1584 int64_t f5f6_38 = f5_2 * (int64_t) f6_19;-
1585 int64_t f5f7_76 = f5_2 * (int64_t) f7_38;-
1586 int64_t f5f8_38 = f5_2 * (int64_t) f8_19;-
1587 int64_t f5f9_76 = f5_2 * (int64_t) f9_38;-
1588 int64_t f6f6_19 = f6 * (int64_t) f6_19;-
1589 int64_t f6f7_38 = f6 * (int64_t) f7_38;-
1590 int64_t f6f8_38 = f6_2 * (int64_t) f8_19;-
1591 int64_t f6f9_38 = f6 * (int64_t) f9_38;-
1592 int64_t f7f7_38 = f7 * (int64_t) f7_38;-
1593 int64_t f7f8_38 = f7_2 * (int64_t) f8_19;-
1594 int64_t f7f9_76 = f7_2 * (int64_t) f9_38;-
1595 int64_t f8f8_19 = f8 * (int64_t) f8_19;-
1596 int64_t f8f9_38 = f8 * (int64_t) f9_38;-
1597 int64_t f9f9_38 = f9 * (int64_t) f9_38;-
1598 int64_t h0 = f0f0 +f1f9_76+f2f8_38+f3f7_76+f4f6_38+f5f5_38;-
1599 int64_t h1 = f0f1_2+f2f9_38+f3f8_38+f4f7_38+f5f6_38;-
1600 int64_t h2 = f0f2_2+f1f1_2 +f3f9_76+f4f8_38+f5f7_76+f6f6_19;-
1601 int64_t h3 = f0f3_2+f1f2_2 +f4f9_38+f5f8_38+f6f7_38;-
1602 int64_t h4 = f0f4_2+f1f3_4 +f2f2 +f5f9_76+f6f8_38+f7f7_38;-
1603 int64_t h5 = f0f5_2+f1f4_2 +f2f3_2 +f6f9_38+f7f8_38;-
1604 int64_t h6 = f0f6_2+f1f5_4 +f2f4_2 +f3f3_2 +f7f9_76+f8f8_19;-
1605 int64_t h7 = f0f7_2+f1f6_2 +f2f5_2 +f3f4_2 +f8f9_38;-
1606 int64_t h8 = f0f8_2+f1f7_4 +f2f6_2 +f3f5_4 +f4f4 +f9f9_38;-
1607 int64_t h9 = f0f9_2+f1f8_2 +f2f7_2 +f3f6_2 +f4f5_2;-
1608 int64_t carry0;-
1609 int64_t carry1;-
1610 int64_t carry2;-
1611 int64_t carry3;-
1612 int64_t carry4;-
1613 int64_t carry5;-
1614 int64_t carry6;-
1615 int64_t carry7;-
1616 int64_t carry8;-
1617 int64_t carry9;-
1618-
1619 h0 += h0;-
1620 h1 += h1;-
1621 h2 += h2;-
1622 h3 += h3;-
1623 h4 += h4;-
1624 h5 += h5;-
1625 h6 += h6;-
1626 h7 += h7;-
1627 h8 += h8;-
1628 h9 += h9;-
1629-
1630 carry0 = h0 + (1 << 25); h1 += carry0 >> 26; h0 -= carry0 & kTop38Bits;-
1631 carry4 = h4 + (1 << 25); h5 += carry4 >> 26; h4 -= carry4 & kTop38Bits;-
1632-
1633 carry1 = h1 + (1 << 24); h2 += carry1 >> 25; h1 -= carry1 & kTop39Bits;-
1634 carry5 = h5 + (1 << 24); h6 += carry5 >> 25; h5 -= carry5 & kTop39Bits;-
1635-
1636 carry2 = h2 + (1 << 25); h3 += carry2 >> 26; h2 -= carry2 & kTop38Bits;-
1637 carry6 = h6 + (1 << 25); h7 += carry6 >> 26; h6 -= carry6 & kTop38Bits;-
1638-
1639 carry3 = h3 + (1 << 24); h4 += carry3 >> 25; h3 -= carry3 & kTop39Bits;-
1640 carry7 = h7 + (1 << 24); h8 += carry7 >> 25; h7 -= carry7 & kTop39Bits;-
1641-
1642 carry4 = h4 + (1 << 25); h5 += carry4 >> 26; h4 -= carry4 & kTop38Bits;-
1643 carry8 = h8 + (1 << 25); h9 += carry8 >> 26; h8 -= carry8 & kTop38Bits;-
1644-
1645 carry9 = h9 + (1 << 24); h0 += (carry9 >> 25) * 19; h9 -= carry9 & kTop39Bits;-
1646-
1647 carry0 = h0 + (1 << 25); h1 += carry0 >> 26; h0 -= carry0 & kTop38Bits;-
1648-
1649 h[0] = (int32_t)h0;-
1650 h[1] = (int32_t)h1;-
1651 h[2] = (int32_t)h2;-
1652 h[3] = (int32_t)h3;-
1653 h[4] = (int32_t)h4;-
1654 h[5] = (int32_t)h5;-
1655 h[6] = (int32_t)h6;-
1656 h[7] = (int32_t)h7;-
1657 h[8] = (int32_t)h8;-
1658 h[9] = (int32_t)h9;-
1659}
executed 27622 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
27622
1660-
1661static void fe_pow22523(fe out, const fe z) {-
1662 fe t0;-
1663 fe t1;-
1664 fe t2;-
1665 int i;-
1666-
1667 fe_sq(t0, z);-
1668 fe_sq(t1, t0);-
1669 for (i = 1; i < 2; ++i) {
i < 2Description
TRUEevaluated 10 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 10 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
10
1670 fe_sq(t1, t1);-
1671 }
executed 10 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
10
1672 fe_mul(t1, z, t1);-
1673 fe_mul(t0, t0, t1);-
1674 fe_sq(t0, t0);-
1675 fe_mul(t0, t1, t0);-
1676 fe_sq(t1, t0);-
1677 for (i = 1; i < 5; ++i) {
i < 5Description
TRUEevaluated 40 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 10 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
10-40
1678 fe_sq(t1, t1);-
1679 }
executed 40 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
40
1680 fe_mul(t0, t1, t0);-
1681 fe_sq(t1, t0);-
1682 for (i = 1; i < 10; ++i) {
i < 10Description
TRUEevaluated 90 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 10 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
10-90
1683 fe_sq(t1, t1);-
1684 }
executed 90 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
90
1685 fe_mul(t1, t1, t0);-
1686 fe_sq(t2, t1);-
1687 for (i = 1; i < 20; ++i) {
i < 20Description
TRUEevaluated 190 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 10 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
10-190
1688 fe_sq(t2, t2);-
1689 }
executed 190 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
190
1690 fe_mul(t1, t2, t1);-
1691 fe_sq(t1, t1);-
1692 for (i = 1; i < 10; ++i) {
i < 10Description
TRUEevaluated 90 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 10 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
10-90
1693 fe_sq(t1, t1);-
1694 }
executed 90 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
90
1695 fe_mul(t0, t1, t0);-
1696 fe_sq(t1, t0);-
1697 for (i = 1; i < 50; ++i) {
i < 50Description
TRUEevaluated 490 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 10 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
10-490
1698 fe_sq(t1, t1);-
1699 }
executed 490 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
490
1700 fe_mul(t1, t1, t0);-
1701 fe_sq(t2, t1);-
1702 for (i = 1; i < 100; ++i) {
i < 100Description
TRUEevaluated 990 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 10 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
10-990
1703 fe_sq(t2, t2);-
1704 }
executed 990 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
990
1705 fe_mul(t1, t2, t1);-
1706 fe_sq(t1, t1);-
1707 for (i = 1; i < 50; ++i) {
i < 50Description
TRUEevaluated 490 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 10 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
10-490
1708 fe_sq(t1, t1);-
1709 }
executed 490 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
490
1710 fe_mul(t0, t1, t0);-
1711 fe_sq(t0, t0);-
1712 for (i = 1; i < 2; ++i) {
i < 2Description
TRUEevaluated 10 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 10 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
10
1713 fe_sq(t0, t0);-
1714 }
executed 10 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
10
1715 fe_mul(out, t0, z);-
1716}
executed 10 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
10
1717-
1718/* ge means group element.-
1719-
1720 * Here the group is the set of pairs (x,y) of field elements (see fe.h)-
1721 * satisfying -x^2 + y^2 = 1 + d x^2y^2-
1722 * where d = -121665/121666.-
1723 *-
1724 * Representations:-
1725 * ge_p2 (projective): (X:Y:Z) satisfying x=X/Z, y=Y/Z-
1726 * ge_p3 (extended): (X:Y:Z:T) satisfying x=X/Z, y=Y/Z, XY=ZT-
1727 * ge_p1p1 (completed): ((X:Z),(Y:T)) satisfying x=X/Z, y=Y/T-
1728 * ge_precomp (Duif): (y+x,y-x,2dxy) */-
1729-
1730typedef struct {-
1731 fe X;-
1732 fe Y;-
1733 fe Z;-
1734} ge_p2;-
1735-
1736typedef struct {-
1737 fe X;-
1738 fe Y;-
1739 fe Z;-
1740 fe T;-
1741} ge_p3;-
1742-
1743typedef struct {-
1744 fe X;-
1745 fe Y;-
1746 fe Z;-
1747 fe T;-
1748} ge_p1p1;-
1749-
1750typedef struct {-
1751 fe yplusx;-
1752 fe yminusx;-
1753 fe xy2d;-
1754} ge_precomp;-
1755-
1756typedef struct {-
1757 fe YplusX;-
1758 fe YminusX;-
1759 fe Z;-
1760 fe T2d;-
1761} ge_cached;-
1762-
1763static void ge_tobytes(uint8_t *s, const ge_p2 *h) {-
1764 fe recip;-
1765 fe x;-
1766 fe y;-
1767-
1768 fe_invert(recip, h->Z);-
1769 fe_mul(x, h->X, recip);-
1770 fe_mul(y, h->Y, recip);-
1771 fe_tobytes(s, y);-
1772 s[31] ^= fe_isnegative(x) << 7;-
1773}
executed 10 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
10
1774-
1775static void ge_p3_tobytes(uint8_t *s, const ge_p3 *h) {-
1776 fe recip;-
1777 fe x;-
1778 fe y;-
1779-
1780 fe_invert(recip, h->Z);-
1781 fe_mul(x, h->X, recip);-
1782 fe_mul(y, h->Y, recip);-
1783 fe_tobytes(s, y);-
1784 s[31] ^= fe_isnegative(x) << 7;-
1785}
executed 46 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
46
1786-
1787static const fe d = {-10913610, 13857413, -15372611, 6949391, 114729,-
1788 -8787816, -6275908, -3247719, -18696448, -12055116};-
1789-
1790static const fe sqrtm1 = {-32595792, -7943725, 9377950, 3500415, 12389472,-
1791 -272473, -25146209, -2005654, 326686, 11406482};-
1792-
1793static int ge_frombytes_vartime(ge_p3 *h, const uint8_t *s) {-
1794 fe u;-
1795 fe v;-
1796 fe v3;-
1797 fe vxx;-
1798 fe check;-
1799-
1800 fe_frombytes(h->Y, s);-
1801 fe_1(h->Z);-
1802 fe_sq(u, h->Y);-
1803 fe_mul(v, u, d);-
1804 fe_sub(u, u, h->Z); /* u = y^2-1 */-
1805 fe_add(v, v, h->Z); /* v = dy^2+1 */-
1806-
1807 fe_sq(v3, v);-
1808 fe_mul(v3, v3, v); /* v3 = v^3 */-
1809 fe_sq(h->X, v3);-
1810 fe_mul(h->X, h->X, v);-
1811 fe_mul(h->X, h->X, u); /* x = uv^7 */-
1812-
1813 fe_pow22523(h->X, h->X); /* x = (uv^7)^((q-5)/8) */-
1814 fe_mul(h->X, h->X, v3);-
1815 fe_mul(h->X, h->X, u); /* x = uv^3(uv^7)^((q-5)/8) */-
1816-
1817 fe_sq(vxx, h->X);-
1818 fe_mul(vxx, vxx, v);-
1819 fe_sub(check, vxx, u); /* vx^2-u */-
1820 if (fe_isnonzero(check)) {
fe_isnonzero(check)Description
TRUEevaluated 5 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 5 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
5
1821 fe_add(check, vxx, u); /* vx^2+u */-
1822 if (fe_isnonzero(check)) {
fe_isnonzero(check)Description
TRUEnever evaluated
FALSEevaluated 5 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
0-5
1823 return -1;
never executed: return -1;
0
1824 }-
1825 fe_mul(h->X, h->X, sqrtm1);-
1826 }
executed 5 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
5
1827-
1828 if (fe_isnegative(h->X) != (s[31] >> 7)) {
fe_isnegative(...= (s[31] >> 7)Description
TRUEevaluated 7 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
FALSEevaluated 3 times by 1 test
Evaluated by:
  • libcrypto.so.1.1
3-7
1829 fe_neg(h->X, h->X);-
1830 }
executed 7 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
7
1831-
1832 fe_mul(h->T, h->X, h->Y);-
1833 return 0;
executed 10 times by 1 test: return 0;
Executed by:
  • libcrypto.so.1.1
10
1834}-
1835-
1836static void ge_p2_0(ge_p2 *h) {-
1837 fe_0(h->X);-
1838 fe_1(h->Y);-
1839 fe_1(h->Z);-
1840}
executed 10 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
10
1841-
1842static void ge_p3_0(ge_p3 *h) {-
1843 fe_0(h->X);-
1844 fe_1(h->Y);-
1845 fe_1(h->Z);-
1846 fe_0(h->T);-
1847}
executed 6275 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
6275
1848-
1849static void ge_precomp_0(ge_precomp *h) {-
1850 fe_1(h->yplusx);-
1851 fe_1(h->yminusx);-
1852 fe_0(h->xy2d);-
1853}
executed 401600 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
401600
1854-
1855/* r = p */-
1856static void ge_p3_to_p2(ge_p2 *r, const ge_p3 *p) {-
1857 fe_copy(r->X, p->X);-
1858 fe_copy(r->Y, p->Y);-
1859 fe_copy(r->Z, p->Z);-
1860}
executed 6285 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
6285
1861-
1862static const fe d2 = {-21827239, -5839606, -30745221, 13898782, 229458,-
1863 15978800, -12551817, -6495438, 29715968, 9444199};-
1864-
1865/* r = p */-
1866static void ge_p3_to_cached(ge_cached *r, const ge_p3 *p) {-
1867 fe_add(r->YplusX, p->Y, p->X);-
1868 fe_sub(r->YminusX, p->Y, p->X);-
1869 fe_copy(r->Z, p->Z);-
1870 fe_mul(r->T2d, p->T, d2);-
1871}
executed 80 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
80
1872-
1873/* r = p */-
1874static void ge_p1p1_to_p2(ge_p2 *r, const ge_p1p1 *p) {-
1875 fe_mul(r->X, p->X, p->T);-
1876 fe_mul(r->Y, p->Y, p->Z);-
1877 fe_mul(r->Z, p->Z, p->T);-
1878}
executed 21337 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
21337
1879-
1880/* r = p */-
1881static void ge_p1p1_to_p3(ge_p3 *r, const ge_p1p1 *p) {-
1882 fe_mul(r->X, p->X, p->T);-
1883 fe_mul(r->Y, p->Y, p->Z);-
1884 fe_mul(r->Z, p->Z, p->T);-
1885 fe_mul(r->T, p->X, p->Y);-
1886}
executed 408806 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
408806
1887-
1888/* r = 2 * p */-
1889static void ge_p2_dbl(ge_p1p1 *r, const ge_p2 *p) {-
1890 fe t0;-
1891-
1892 fe_sq(r->X, p->X);-
1893 fe_sq(r->Z, p->Y);-
1894 fe_sq2(r->T, p->Z);-
1895 fe_add(r->Y, p->X, p->Y);-
1896 fe_sq(t0, r->Y);-
1897 fe_add(r->Y, r->Z, r->X);-
1898 fe_sub(r->Z, r->Z, r->X);-
1899 fe_sub(r->X, t0, r->Y);-
1900 fe_sub(r->T, r->T, r->Z);-
1901}
executed 27622 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
27622
1902-
1903/* r = 2 * p */-
1904static void ge_p3_dbl(ge_p1p1 *r, const ge_p3 *p) {-
1905 ge_p2 q;-
1906 ge_p3_to_p2(&q, p);-
1907 ge_p2_dbl(r, &q);-
1908}
executed 6285 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
6285
1909-
1910/* r = p + q */-
1911static void ge_madd(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) {-
1912 fe t0;-
1913-
1914 fe_add(r->X, p->Y, p->X);-
1915 fe_sub(r->Y, p->Y, p->X);-
1916 fe_mul(r->Z, r->X, q->yplusx);-
1917 fe_mul(r->Y, r->Y, q->yminusx);-
1918 fe_mul(r->T, q->xy2d, p->T);-
1919 fe_add(t0, p->Z, p->Z);-
1920 fe_sub(r->X, r->Z, r->Y);-
1921 fe_add(r->Y, r->Z, r->Y);-
1922 fe_add(r->Z, t0, r->T);-
1923 fe_sub(r->T, t0, r->T);-
1924}
executed 401834 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
401834
1925-
1926/* r = p - q */-
1927static void ge_msub(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) {-
1928 fe t0;-
1929-
1930 fe_add(r->X, p->Y, p->X);-
1931 fe_sub(r->Y, p->Y, p->X);-
1932 fe_mul(r->Z, r->X, q->yminusx);-
1933 fe_mul(r->Y, r->Y, q->yplusx);-
1934 fe_mul(r->T, q->xy2d, p->T);-
1935 fe_add(t0, p->Z, p->Z);-
1936 fe_sub(r->X, r->Z, r->Y);-
1937 fe_add(r->Y, r->Z, r->Y);-
1938 fe_sub(r->Z, t0, r->T);-
1939 fe_add(r->T, t0, r->T);-
1940}
executed 186 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
186
1941-
1942/* r = p + q */-
1943static void ge_add(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) {-
1944 fe t0;-
1945-
1946 fe_add(r->X, p->Y, p->X);-
1947 fe_sub(r->Y, p->Y, p->X);-
1948 fe_mul(r->Z, r->X, q->YplusX);-
1949 fe_mul(r->Y, r->Y, q->YminusX);-
1950 fe_mul(r->T, q->T2d, p->T);-
1951 fe_mul(r->X, p->Z, q->Z);-
1952 fe_add(t0, r->X, r->X);-
1953 fe_sub(r->X, r->Z, r->Y);-
1954 fe_add(r->Y, r->Z, r->Y);-
1955 fe_add(r->Z, t0, r->T);-
1956 fe_sub(r->T, t0, r->T);-
1957}
executed 305 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
305
1958-
1959/* r = p - q */-
1960static void ge_sub(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) {-
1961 fe t0;-
1962-
1963 fe_add(r->X, p->Y, p->X);-
1964 fe_sub(r->Y, p->Y, p->X);-
1965 fe_mul(r->Z, r->X, q->YminusX);-
1966 fe_mul(r->Y, r->Y, q->YplusX);-
1967 fe_mul(r->T, q->T2d, p->T);-
1968 fe_mul(r->X, p->Z, q->Z);-
1969 fe_add(t0, r->X, r->X);-
1970 fe_sub(r->X, r->Z, r->Y);-
1971 fe_add(r->Y, r->Z, r->Y);-
1972 fe_sub(r->Z, t0, r->T);-
1973 fe_add(r->T, t0, r->T);-
1974}
executed 196 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
196
1975-
1976static uint8_t equal(signed char b, signed char c) {-
1977 uint8_t ub = b;-
1978 uint8_t uc = c;-
1979 uint8_t x = ub ^ uc; /* 0: yes; 1..255: no */-
1980 uint32_t y = x; /* 0: yes; 1..255: no */-
1981 y -= 1; /* 4294967295: yes; 0..254: no */-
1982 y >>= 31; /* 1: yes; 0: no */-
1983 return y;
executed 3212800 times by 1 test: return y;
Executed by:
  • libcrypto.so.1.1
3212800
1984}-
1985-
1986static void cmov(ge_precomp *t, const ge_precomp *u, uint8_t b) {-
1987 fe_cmov(t->yplusx, u->yplusx, b);-
1988 fe_cmov(t->yminusx, u->yminusx, b);-
1989 fe_cmov(t->xy2d, u->xy2d, b);-
1990}
executed 3614400 times by 1 test: end of block
Executed by:
  • libcrypto.so.1.1
3614400
1991-
1992/* k25519Precomp[i][j] = (j+1)*256^i*B */-
1993static const ge_precomp k25519Precomp[32][8] = {-
1994 {-
1995 {-
1996 {25967493, -14356035, 29566456, 3660896, -12694345, 4014787,-
1997 27544626, -11754271, -6079156, 2047605},-
1998 {-12545711, 934262, -2722910, 3049990, -727428, 9406986, 12720692,-
1999 5043384, 19500929, -15469378},-
2000 {-8738181, 4489570, 9688441, -14785194, 10184609, -12363380,-
2001 29287919, 11864899, -24514362, -4438546},-
2002 },-
2003 {-
2004 {-12815894, -12976347, -21581243, 11784320, -25355658, -2750717,-
2005 -11717903, -3814571, -358445, -10211303},-
2006 {-21703237, 6903825, 27185491, 6451973, -29577724, -9554005,-
2007 -15616551, 11189268, -26829678, -5319081},-
2008 {26966642, 11152617, 32442495, 15396054, 14353839, -12752335,-
2009 -3128826, -9541118, -15472047, -4166697},-
2010 },-
2011 {-
2012 {15636291, -9688557, 24204773, -7912398, 616977, -16685262,-
2013 27787600, -14772189, 28944400, -1550024},-
2014 {16568933, 4717097, -11556148, -1102322, 15682896, -11807043,-
2015 16354577, -11775962, 7689662, 11199574},-
2016 {30464156, -5976125, -11779434, -15670865, 23220365, 15915852,-
2017 7512774, 10017326, -17749093, -9920357},-
2018 },-
2019 {-
2020 {-17036878, 13921892, 10945806, -6033431, 27105052, -16084379,-
2021 -28926210, 15006023, 3284568, -6276540},-
2022 {23599295, -8306047, -11193664, -7687416, 13236774, 10506355,-
2023 7464579, 9656445, 13059162, 10374397},-
2024 {7798556, 16710257, 3033922, 2874086, 28997861, 2835604, 32406664,-
2025 -3839045, -641708, -101325},-
2026 },-
2027 {-
2028 {10861363, 11473154, 27284546, 1981175, -30064349, 12577861,-
2029 32867885, 14515107, -15438304, 10819380},-
2030 {4708026, 6336745, 20377586, 9066809, -11272109, 6594696, -25653668,-
2031 12483688, -12668491, 5581306},-
2032 {19563160, 16186464, -29386857, 4097519, 10237984, -4348115,-
2033 28542350, 13850243, -23678021, -15815942},-
2034 },-
2035 {-
2036 {-15371964, -12862754, 32573250, 4720197, -26436522, 5875511,-
2037 -19188627, -15224819, -9818940, -12085777},-
2038 {-8549212, 109983, 15149363, 2178705, 22900618, 4543417, 3044240,-
2039 -15689887, 1762328, 14866737},-
2040 {-18199695, -15951423, -10473290, 1707278, -17185920, 3916101,-
2041 -28236412, 3959421, 27914454, 4383652},-
2042 },-
2043 {-
2044 {5153746, 9909285, 1723747, -2777874, 30523605, 5516873, 19480852,-
2045 5230134, -23952439, -15175766},-
2046 {-30269007, -3463509, 7665486, 10083793, 28475525, 1649722,-
2047 20654025, 16520125, 30598449, 7715701},-
2048 {28881845, 14381568, 9657904, 3680757, -20181635, 7843316,-
2049 -31400660, 1370708, 29794553, -1409300},-
2050 },-
2051 {-
2052 {14499471, -2729599, -33191113, -4254652, 28494862, 14271267,-
2053 30290735, 10876454, -33154098, 2381726},-
2054 {-7195431, -2655363, -14730155, 462251, -27724326, 3941372,-
2055 -6236617, 3696005, -32300832, 15351955},-
2056 {27431194, 8222322, 16448760, -3907995, -18707002, 11938355,-
2057 -32961401, -2970515, 29551813, 10109425},-
2058 },-
2059 },-
2060 {-
2061 {-
2062 {-13657040, -13155431, -31283750, 11777098, 21447386, 6519384,-
2063 -2378284, -1627556, 10092783, -4764171},-
2064 {27939166, 14210322, 4677035, 16277044, -22964462, -12398139,-
2065 -32508754, 12005538, -17810127, 12803510},-
2066 {17228999, -15661624, -1233527, 300140, -1224870, -11714777,-
2067 30364213, -9038194, 18016357, 4397660},-
2068 },-
2069 {-
2070 {-10958843, -7690207, 4776341, -14954238, 27850028, -15602212,-
2071 -26619106, 14544525, -17477504, 982639},-
2072 {29253598, 15796703, -2863982, -9908884, 10057023, 3163536, 7332899,-
2073 -4120128, -21047696, 9934963},-
2074 {5793303, 16271923, -24131614, -10116404, 29188560, 1206517,-
2075 -14747930, 4559895, -30123922, -10897950},-
2076 },-
2077 {-
2078 {-27643952, -11493006, 16282657, -11036493, 28414021, -15012264,-
2079 24191034, 4541697, -13338309, 5500568},-
2080 {12650548, -1497113, 9052871, 11355358, -17680037, -8400164,-
2081 -17430592, 12264343, 10874051, 13524335},-
2082 {25556948, -3045990, 714651, 2510400, 23394682, -10415330, 33119038,-
2083 5080568, -22528059, 5376628},-
2084 },-
2085 {-
2086 {-26088264, -4011052, -17013699, -3537628, -6726793, 1920897,-
2087 -22321305, -9447443, 4535768, 1569007},-
2088 {-2255422, 14606630, -21692440, -8039818, 28430649, 8775819,-
2089 -30494562, 3044290, 31848280, 12543772},-
2090 {-22028579, 2943893, -31857513, 6777306, 13784462, -4292203,-
2091 -27377195, -2062731, 7718482, 14474653},-
2092 },-
2093 {-
2094 {2385315, 2454213, -22631320, 46603, -4437935, -15680415, 656965,-
2095 -7236665, 24316168, -5253567},-
2096 {13741529, 10911568, -33233417, -8603737, -20177830, -1033297,-
2097 33040651, -13424532, -20729456, 8321686},-
2098 {21060490, -2212744, 15712757, -4336099, 1639040, 10656336,-
2099 23845965, -11874838, -9984458, 608372},-
2100 },-
2101 {-
2102 {-13672732, -15087586, -10889693, -7557059, -6036909, 11305547,-
2103 1123968, -6780577, 27229399, 23887},-
2104 {-23244140, -294205, -11744728, 14712571, -29465699, -2029617,-
2105 12797024, -6440308, -1633405, 16678954},-
2106 {-29500620, 4770662, -16054387, 14001338, 7830047, 9564805,-
2107 -1508144, -4795045, -17169265, 4904953},-
2108 },-
2109 {-
2110 {24059557, 14617003, 19037157, -15039908, 19766093, -14906429,-
2111 5169211, 16191880, 2128236, -4326833},-
2112 {-16981152, 4124966, -8540610, -10653797, 30336522, -14105247,-
2113 -29806336, 916033, -6882542, -2986532},-
2114 {-22630907, 12419372, -7134229, -7473371, -16478904, 16739175,-
2115 285431, 2763829, 15736322, 4143876},-
2116 },-
2117 {-
2118 {2379352, 11839345, -4110402, -5988665, 11274298, 794957, 212801,-
2119 -14594663, 23527084, -16458268},-
2120 {33431127, -11130478, -17838966, -15626900, 8909499, 8376530,-
2121 -32625340, 4087881, -15188911, -14416214},-
2122 {1767683, 7197987, -13205226, -2022635, -13091350, 448826, 5799055,-
2123 4357868, -4774191, -16323038},-
2124 },-
2125 },-
2126 {-
2127 {-
2128 {6721966, 13833823, -23523388, -1551314, 26354293, -11863321,-
2129 23365147, -3949732, 7390890, 2759800},-
2130 {4409041, 2052381, 23373853, 10530217, 7676779, -12885954, 21302353,-
2131 -4264057, 1244380, -12919645},-
2132 {-4421239, 7169619, 4982368, -2957590, 30256825, -2777540, 14086413,-
2133 9208236, 15886429, 16489664},-
2134 },-
2135 {-
2136 {1996075, 10375649, 14346367, 13311202, -6874135, -16438411,-
2137 -13693198, 398369, -30606455, -712933},-
2138 {-25307465, 9795880, -2777414, 14878809, -33531835, 14780363,-
2139 13348553, 12076947, -30836462, 5113182},-
2140 {-17770784, 11797796, 31950843, 13929123, -25888302, 12288344,-
2141 -30341101, -7336386, 13847711, 5387222},-
2142 },-
2143 {-
2144 {-18582163, -3416217, 17824843, -2340966, 22744343, -10442611,-
2145 8763061, 3617786, -19600662, 10370991},-
2146 {20246567, -14369378, 22358229, -543712, 18507283, -10413996,-
2147 14554437, -8746092, 32232924, 16763880},-
2148 {9648505, 10094563, 26416693, 14745928, -30374318, -6472621,-
2149 11094161, 15689506, 3140038, -16510092},-
2150 },-
2151 {-
2152 {-16160072, 5472695, 31895588, 4744994, 8823515, 10365685,-
2153 -27224800, 9448613, -28774454, 366295},-
2154 {19153450, 11523972, -11096490, -6503142, -24647631, 5420647,-
2155 28344573, 8041113, 719605, 11671788},-
2156 {8678025, 2694440, -6808014, 2517372, 4964326, 11152271, -15432916,-
2157 -15266516, 27000813, -10195553},-
2158 },-
2159 {-
2160 {-15157904, 7134312, 8639287, -2814877, -7235688, 10421742, 564065,-
2161 5336097, 6750977, -14521026},-
2162 {11836410, -3979488, 26297894, 16080799, 23455045, 15735944,-
2163 1695823, -8819122, 8169720, 16220347},-
2164 {-18115838, 8653647, 17578566, -6092619, -8025777, -16012763,-
2165 -11144307, -2627664, -5990708, -14166033},-
2166 },-
2167 {-
2168 {-23308498, -10968312, 15213228, -10081214, -30853605, -11050004,-
2169 27884329, 2847284, 2655861, 1738395},-
2170 {-27537433, -14253021, -25336301, -8002780, -9370762, 8129821,-
2171 21651608, -3239336, -19087449, -11005278},-
2172 {1533110, 3437855, 23735889, 459276, 29970501, 11335377, 26030092,-
2173 5821408, 10478196, 8544890},-
2174 },-
2175 {-
2176 {32173121, -16129311, 24896207, 3921497, 22579056, -3410854,-
2177 19270449, 12217473, 17789017, -3395995},-
2178 {-30552961, -2228401, -15578829, -10147201, 13243889, 517024,-
2179 15479401, -3853233, 30460520, 1052596},-
2180 {-11614875, 13323618, 32618793, 8175907, -15230173, 12596687,-
2181 27491595, -4612359, 3179268, -9478891},-
2182 },-
2183 {-
2184 {31947069, -14366651, -4640583, -15339921, -15125977, -6039709,-
2185 -14756777, -16411740, 19072640, -9511060},-
2186 {11685058, 11822410, 3158003, -13952594, 33402194, -4165066,-
2187 5977896, -5215017, 473099, 5040608},-
2188 {-20290863, 8198642, -27410132, 11602123, 1290375, -2799760,-
2189 28326862, 1721092, -19558642, -3131606},-
2190 },-
2191 },-
2192 {-
2193 {-
2194 {7881532, 10687937, 7578723, 7738378, -18951012, -2553952, 21820786,-
2195 8076149, -27868496, 11538389},-
2196 {-19935666, 3899861, 18283497, -6801568, -15728660, -11249211,-
2197 8754525, 7446702, -5676054, 5797016},-
2198 {-11295600, -3793569, -15782110, -7964573, 12708869, -8456199,-
2199 2014099, -9050574, -2369172, -5877341},-
2200 },-
2201 {-
2202 {-22472376, -11568741, -27682020, 1146375, 18956691, 16640559,-
2203 1192730, -3714199, 15123619, 10811505},-
2204 {14352098, -3419715, -18942044, 10822655, 32750596, 4699007, -70363,-
2205 15776356, -28886779, -11974553},-
2206 {-28241164, -8072475, -4978962, -5315317, 29416931, 1847569,-
2207 -20654173, -16484855, 4714547, -9600655},-
2208 },-
2209 {-
2210 {15200332, 8368572, 19679101, 15970074, -31872674, 1959451,-
2211 24611599, -4543832, -11745876, 12340220},-
2212 {12876937, -10480056, 33134381, 6590940, -6307776, 14872440,-
2213 9613953, 8241152, 15370987, 9608631},-
2214 {-4143277, -12014408, 8446281, -391603, 4407738, 13629032, -7724868,-
2215 15866074, -28210621, -8814099},-
2216 },-
2217 {-
2218 {26660628, -15677655, 8393734, 358047, -7401291, 992988, -23904233,-
2219 858697, 20571223, 8420556},-
2220 {14620715, 13067227, -15447274, 8264467, 14106269, 15080814,-
2221 33531827, 12516406, -21574435, -12476749},-
2222 {236881, 10476226, 57258, -14677024, 6472998, 2466984, 17258519,-
2223 7256740, 8791136, 15069930},-
2224 },-
2225 {-
2226 {1276410, -9371918, 22949635, -16322807, -23493039, -5702186,-
2227 14711875, 4874229, -30663140, -2331391},-
2228 {5855666, 4990204, -13711848, 7294284, -7804282, 1924647, -1423175,-
2229 -7912378, -33069337, 9234253},-
2230 {20590503, -9018988, 31529744, -7352666, -2706834, 10650548,-
2231 31559055, -11609587, 18979186, 13396066},-
2232 },-
2233 {-
2234 {24474287, 4968103, 22267082, 4407354, 24063882, -8325180,-
2235 -18816887, 13594782, 33514650, 7021958},-
2236 {-11566906, -6565505, -21365085, 15928892, -26158305, 4315421,-
2237 -25948728, -3916677, -21480480, 12868082},-
2238 {-28635013, 13504661, 19988037, -2132761, 21078225, 6443208,-
2239 -21446107, 2244500, -12455797, -8089383},-
2240 },-
2241 {-
2242 {-30595528, 13793479, -5852820, 319136, -25723172, -6263899,-
2243 33086546, 8957937, -15233648, 5540521},-
2244 {-11630176, -11503902, -8119500, -7643073, 2620056, 1022908,-
2245 -23710744, -1568984, -16128528, -14962807},-
2246 {23152971, 775386, 27395463, 14006635, -9701118, 4649512, 1689819,-
2247 892185, -11513277, -15205948},-
2248 },-
2249 {-
2250 {9770129, 9586738, 26496094, 4324120, 1556511, -3550024, 27453819,-
2251 4763127, -19179614, 5867134},-
2252 {-32765025, 1927590, 31726409, -4753295, 23962434, -16019500,-
2253 27846559, 5931263, -29749703, -16108455},-
2254 {27461885, -2977536, 22380810, 1815854, -23033753, -3031938,-
2255 7283490, -15148073, -19526700, 7734629},-
2256 },-
2257 },-
2258 {-
2259 {-
2260 {-8010264, -9590817, -11120403, 6196038, 29344158, -13430885,-
2261 7585295, -3176626, 18549497, 15302069},-
2262 {-32658337, -6171222, -7672793, -11051681, 6258878, 13504381,-
2263 10458790, -6418461, -8872242, 8424746},-
2264 {24687205, 8613276, -30667046, -3233545, 1863892, -1830544,-
2265 19206234, 7134917, -11284482, -828919},-
2266 },-
2267 {-
2268 {11334899, -9218022, 8025293, 12707519, 17523892, -10476071,-
2269 10243738, -14685461, -5066034, 16498837},-
2270 {8911542, 6887158, -9584260, -6958590, 11145641, -9543680, 17303925,-
2271 -14