Absolute File Name: | /home/opencoverage/opencoverage/guest-scripts/openssl/src/crypto/ec/curve25519.c |
Source code | Switch to Preprocessed file |
Line | Source | Count | ||||||
---|---|---|---|---|---|---|---|---|
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 | - | |||||||
19 | typedef uint64_t fe64[4]; | - | ||||||
20 | - | |||||||
21 | int 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 | */ | - | ||||||
32 | void x25519_fe64_mul(fe64 h, const fe64 f, const fe64 g); | - | ||||||
33 | void x25519_fe64_sqr(fe64 h, const fe64 f); | - | ||||||
34 | void x25519_fe64_mul121666(fe64 h, fe64 f); | - | ||||||
35 | void x25519_fe64_add(fe64 h, const fe64 f, const fe64 g); | - | ||||||
36 | void x25519_fe64_sub(fe64 h, const fe64 f, const fe64 g); | - | ||||||
37 | void 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 | - | |||||||
45 | static 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 | - | |||||||
61 | static 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 | - | |||||||
69 | static 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 | - | |||||||
77 | static 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 | - | |||||||
85 | static 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 | - | |||||||
93 | static 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++) {
| 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 | - | |||||||
106 | static 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)
| 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)
| 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)
| 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)
| 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)
| 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)
| 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)
| 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)
| 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 | */ | - | ||||||
201 | static 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) {
| 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 | - | |||||||
266 | typedef uint64_t fe51[5]; | - | ||||||
267 | - | |||||||
268 | static const uint64_t MASK51 = 0x7ffffffffffff; | - | ||||||
269 | - | |||||||
270 | static 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:
| 5832 | ||||||
283 | } | - | ||||||
284 | - | |||||||
285 | static 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:
| 8748 | ||||||
297 | } | - | ||||||
298 | - | |||||||
299 | static 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:
| 2916 | ||||||
318 | - | |||||||
319 | static 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:
| 2916 | ||||||
377 | - | |||||||
378 | # if defined(X25519_ASM) | - | ||||||
379 | void x25519_fe51_mul(fe51 h, const fe51 f, const fe51 g); | - | ||||||
380 | void x25519_fe51_sqr(fe51 h, const fe51 f); | - | ||||||
381 | void 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 | - | |||||||
387 | typedef __uint128_t u128; | - | ||||||
388 | - | |||||||
389 | static 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 | - | |||||||
447 | static 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 | - | |||||||
501 | static 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 | - | |||||||
528 | static 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:
| 2974320 | ||||||
536 | - | |||||||
537 | static 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:
| 2974320 | ||||||
549 | - | |||||||
550 | static 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:
| 2916 | ||||||
558 | - | |||||||
559 | static 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:
| 5832 | ||||||
567 | - | |||||||
568 | static 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:
| 2916 | ||||||
576 | - | |||||||
577 | static 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++) {
| 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:
| 7435800 | ||||||
588 | } executed 1487160 times by 1 test: end of block Executed by:
| 1487160 | ||||||
589 | - | |||||||
590 | static 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)
| 2916-11664 | ||||||
624 | fe51_sq(t2, t2); executed 11664 times by 1 test: x25519_fe51_sqr(t2, t2); Executed by:
| 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)
| 2916-26244 | ||||||
634 | fe51_sq(t2, t2); executed 26244 times by 1 test: x25519_fe51_sqr(t2, t2); Executed by:
| 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)
| 2916-55404 | ||||||
641 | fe51_sq(t3, t3); executed 55404 times by 1 test: x25519_fe51_sqr(t3, t3); Executed by:
| 55404 | ||||||
642 | - | |||||||
643 | fe51_mul(t2, t3, t2); | - | ||||||
644 | - | |||||||
645 | /* t2 = z ** (2 ** 10) * (2 ** 40 - 1) */ | - | ||||||
646 | for (i = 0; i < 10; ++i)
| 2916-29160 | ||||||
647 | fe51_sq(t2, t2); executed 29160 times by 1 test: x25519_fe51_sqr(t2, t2); Executed by:
| 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)
| 2916-142884 | ||||||
655 | fe51_sq(t2, t2); executed 142884 times by 1 test: x25519_fe51_sqr(t2, t2); Executed by:
| 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)
| 2916-288684 | ||||||
662 | fe51_sq(t3, t3); executed 288684 times by 1 test: x25519_fe51_sqr(t3, t3); Executed by:
| 288684 | ||||||
663 | - | |||||||
664 | fe51_mul(t2, t3, t2); | - | ||||||
665 | - | |||||||
666 | /* t2 = z ** ((2 ** 50) * (2 ** 200 - 1) */ | - | ||||||
667 | for (i = 0; i < 50; ++i)
| 2916-145800 | ||||||
668 | fe51_sq(t2, t2); executed 145800 times by 1 test: x25519_fe51_sqr(t2, t2); Executed by:
| 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)
| 2916-14580 | ||||||
675 | fe51_sq(t1, t1); executed 14580 times by 1 test: x25519_fe51_sqr(t1, t1); Executed by:
| 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:
| 2916 | ||||||
680 | - | |||||||
681 | /* | - | ||||||
682 | * Duplicate of original x25519_scalar_mult_generic, but using | - | ||||||
683 | * fe51_* subroutines. | - | ||||||
684 | */ | - | ||||||
685 | static 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()) {
| 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) {
| 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:
| 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:
| 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. */ | - | ||||||
759 | typedef int32_t fe[10]; | - | ||||||
760 | - | |||||||
761 | static const int64_t kBottom25Bits = 0x1ffffffLL; | - | ||||||
762 | static const int64_t kBottom26Bits = 0x3ffffffLL; | - | ||||||
763 | static const int64_t kTop39Bits = 0xfffffffffe000000LL; | - | ||||||
764 | static const int64_t kTop38Bits = 0xfffffffffc000000LL; | - | ||||||
765 | - | |||||||
766 | static 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:
| 630 | ||||||
772 | } | - | ||||||
773 | - | |||||||
774 | static 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:
| 634 | ||||||
781 | } | - | ||||||
782 | - | |||||||
783 | static 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:
| 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. */ | - | ||||||
852 | static 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:
| 6366 | ||||||
931 | - | |||||||
932 | /* h = f */ | - | ||||||
933 | static 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:
| 822135 | ||||||
936 | - | |||||||
937 | /* h = 0 */ | - | ||||||
938 | static executed 414160 times by 1 test: void fe_0(fe h) { memset(h, 0, sizeof(int32_t) * 10); }end of block Executed by:
executed 414160 times by 1 test: end of block Executed by:
| 414160 | ||||||
939 | - | |||||||
940 | /* h = 1 */ | - | ||||||
941 | static 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:
| 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. */ | - | ||||||
955 | static void fe_add(fe h, const fe f, const fe g) { | - | ||||||
956 | unsigned i; | - | ||||||
957 | for (i = 0; i < 10; i++) {
| 1671652-16716520 | ||||||
958 | h[i] = f[i] + g[i]; | - | ||||||
959 | } executed 16716520 times by 1 test: end of block Executed by:
| 16716520 | ||||||
960 | } executed 1671652 times by 1 test: end of block Executed by:
| 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. */ | - | ||||||
971 | static void fe_sub(fe h, const fe f, const fe g) { | - | ||||||
972 | unsigned i; | - | ||||||
973 | for (i = 0; i < 10; i++) {
| 1296758-12967580 | ||||||
974 | h[i] = f[i] - g[i]; | - | ||||||
975 | } executed 12967580 times by 1 test: end of block Executed by:
| 12967580 | ||||||
976 | } executed 1296758 times by 1 test: end of block Executed by:
| 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. */ | - | ||||||
1005 | static 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:
| 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. */ | - | ||||||
1231 | static 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:
| 1681806 | ||||||
1361 | - | |||||||
1362 | static 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) {
| 6285-25140 | ||||||
1395 | fe_sq(t2, t2); | - | ||||||
1396 | } executed 25140 times by 1 test: end of block Executed by:
| 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) {
| 6285-56565 | ||||||
1406 | fe_sq(t2, t2); | - | ||||||
1407 | } executed 56565 times by 1 test: end of block Executed by:
| 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) {
| 6285-119415 | ||||||
1413 | fe_sq(t3, t3); | - | ||||||
1414 | } executed 119415 times by 1 test: end of block Executed by:
| 119415 | ||||||
1415 | fe_mul(t2, t3, t2); | - | ||||||
1416 | - | |||||||
1417 | /* t2 = z ** (2 ** 10) * (2 ** 40 - 1) */ | - | ||||||
1418 | for (i = 0; i < 10; ++i) {
| 6285-62850 | ||||||
1419 | fe_sq(t2, t2); | - | ||||||
1420 | } executed 62850 times by 1 test: end of block Executed by:
| 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) {
| 6285-307965 | ||||||
1427 | fe_sq(t2, t2); | - | ||||||
1428 | } executed 307965 times by 1 test: end of block Executed by:
| 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) {
| 6285-622215 | ||||||
1434 | fe_sq(t3, t3); | - | ||||||
1435 | } executed 622215 times by 1 test: end of block Executed by:
| 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) {
| 6285-307965 | ||||||
1441 | fe_sq(t2, t2); | - | ||||||
1442 | } executed 307965 times by 1 test: end of block Executed by:
| 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) {
| 6285-25140 | ||||||
1450 | fe_sq(t1, t1); | - | ||||||
1451 | } executed 25140 times by 1 test: end of block Executed by:
| 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:
| 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. */ | - | ||||||
1464 | static void fe_neg(fe h, const fe f) { | - | ||||||
1465 | unsigned i; | - | ||||||
1466 | for (i = 0; i < 10; i++) {
| 401627-4016270 | ||||||
1467 | h[i] = -f[i]; | - | ||||||
1468 | } executed 4016270 times by 1 test: end of block Executed by:
| 4016270 | ||||||
1469 | } executed 401627 times by 1 test: end of block Executed by:
| 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}. */ | - | ||||||
1475 | static 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++) {
| 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:
| 108432000 | ||||||
1483 | } executed 10843200 times by 1 test: end of block Executed by:
| 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. */ | - | ||||||
1490 | static 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:
| 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. */ | - | ||||||
1503 | static 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:
| 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. */ | - | ||||||
1519 | static 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:
| 27622 | ||||||
1660 | - | |||||||
1661 | static 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) {
| 10 | ||||||
1670 | fe_sq(t1, t1); | - | ||||||
1671 | } executed 10 times by 1 test: end of block Executed by:
| 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) {
| 10-40 | ||||||
1678 | fe_sq(t1, t1); | - | ||||||
1679 | } executed 40 times by 1 test: end of block Executed by:
| 40 | ||||||
1680 | fe_mul(t0, t1, t0); | - | ||||||
1681 | fe_sq(t1, t0); | - | ||||||
1682 | for (i = 1; i < 10; ++i) {
| 10-90 | ||||||
1683 | fe_sq(t1, t1); | - | ||||||
1684 | } executed 90 times by 1 test: end of block Executed by:
| 90 | ||||||
1685 | fe_mul(t1, t1, t0); | - | ||||||
1686 | fe_sq(t2, t1); | - | ||||||
1687 | for (i = 1; i < 20; ++i) {
| 10-190 | ||||||
1688 | fe_sq(t2, t2); | - | ||||||
1689 | } executed 190 times by 1 test: end of block Executed by:
| 190 | ||||||
1690 | fe_mul(t1, t2, t1); | - | ||||||
1691 | fe_sq(t1, t1); | - | ||||||
1692 | for (i = 1; i < 10; ++i) {
| 10-90 | ||||||
1693 | fe_sq(t1, t1); | - | ||||||
1694 | } executed 90 times by 1 test: end of block Executed by:
| 90 | ||||||
1695 | fe_mul(t0, t1, t0); | - | ||||||
1696 | fe_sq(t1, t0); | - | ||||||
1697 | for (i = 1; i < 50; ++i) {
| 10-490 | ||||||
1698 | fe_sq(t1, t1); | - | ||||||
1699 | } executed 490 times by 1 test: end of block Executed by:
| 490 | ||||||
1700 | fe_mul(t1, t1, t0); | - | ||||||
1701 | fe_sq(t2, t1); | - | ||||||
1702 | for (i = 1; i < 100; ++i) {
| 10-990 | ||||||
1703 | fe_sq(t2, t2); | - | ||||||
1704 | } executed 990 times by 1 test: end of block Executed by:
| 990 | ||||||
1705 | fe_mul(t1, t2, t1); | - | ||||||
1706 | fe_sq(t1, t1); | - | ||||||
1707 | for (i = 1; i < 50; ++i) {
| 10-490 | ||||||
1708 | fe_sq(t1, t1); | - | ||||||
1709 | } executed 490 times by 1 test: end of block Executed by:
| 490 | ||||||
1710 | fe_mul(t0, t1, t0); | - | ||||||
1711 | fe_sq(t0, t0); | - | ||||||
1712 | for (i = 1; i < 2; ++i) {
| 10 | ||||||
1713 | fe_sq(t0, t0); | - | ||||||
1714 | } executed 10 times by 1 test: end of block Executed by:
| 10 | ||||||
1715 | fe_mul(out, t0, z); | - | ||||||
1716 | } executed 10 times by 1 test: end of block Executed by:
| 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 | - | |||||||
1730 | typedef struct { | - | ||||||
1731 | fe X; | - | ||||||
1732 | fe Y; | - | ||||||
1733 | fe Z; | - | ||||||
1734 | } ge_p2; | - | ||||||
1735 | - | |||||||
1736 | typedef struct { | - | ||||||
1737 | fe X; | - | ||||||
1738 | fe Y; | - | ||||||
1739 | fe Z; | - | ||||||
1740 | fe T; | - | ||||||
1741 | } ge_p3; | - | ||||||
1742 | - | |||||||
1743 | typedef struct { | - | ||||||
1744 | fe X; | - | ||||||
1745 | fe Y; | - | ||||||
1746 | fe Z; | - | ||||||
1747 | fe T; | - | ||||||
1748 | } ge_p1p1; | - | ||||||
1749 | - | |||||||
1750 | typedef struct { | - | ||||||
1751 | fe yplusx; | - | ||||||
1752 | fe yminusx; | - | ||||||
1753 | fe xy2d; | - | ||||||
1754 | } ge_precomp; | - | ||||||
1755 | - | |||||||
1756 | typedef struct { | - | ||||||
1757 | fe YplusX; | - | ||||||
1758 | fe YminusX; | - | ||||||
1759 | fe Z; | - | ||||||
1760 | fe T2d; | - | ||||||
1761 | } ge_cached; | - | ||||||
1762 | - | |||||||
1763 | static 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:
| 10 | ||||||
1774 | - | |||||||
1775 | static 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:
| 46 | ||||||
1786 | - | |||||||
1787 | static const fe d = {-10913610, 13857413, -15372611, 6949391, 114729, | - | ||||||
1788 | -8787816, -6275908, -3247719, -18696448, -12055116}; | - | ||||||
1789 | - | |||||||
1790 | static const fe sqrtm1 = {-32595792, -7943725, 9377950, 3500415, 12389472, | - | ||||||
1791 | -272473, -25146209, -2005654, 326686, 11406482}; | - | ||||||
1792 | - | |||||||
1793 | static 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)) {
| 5 | ||||||
1821 | fe_add(check, vxx, u); /* vx^2+u */ | - | ||||||
1822 | if (fe_isnonzero(check)) {
| 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:
| 5 | ||||||
1827 | - | |||||||
1828 | if (fe_isnegative(h->X) != (s[31] >> 7)) {
| 3-7 | ||||||
1829 | fe_neg(h->X, h->X); | - | ||||||
1830 | } executed 7 times by 1 test: end of block Executed by:
| 7 | ||||||
1831 | - | |||||||
1832 | fe_mul(h->T, h->X, h->Y); | - | ||||||
1833 | return 0; executed 10 times by 1 test: return 0; Executed by:
| 10 | ||||||
1834 | } | - | ||||||
1835 | - | |||||||
1836 | static 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:
| 10 | ||||||
1841 | - | |||||||
1842 | static 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:
| 6275 | ||||||
1848 | - | |||||||
1849 | static 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:
| 401600 | ||||||
1854 | - | |||||||
1855 | /* r = p */ | - | ||||||
1856 | static 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:
| 6285 | ||||||
1861 | - | |||||||
1862 | static const fe d2 = {-21827239, -5839606, -30745221, 13898782, 229458, | - | ||||||
1863 | 15978800, -12551817, -6495438, 29715968, 9444199}; | - | ||||||
1864 | - | |||||||
1865 | /* r = p */ | - | ||||||
1866 | static 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:
| 80 | ||||||
1872 | - | |||||||
1873 | /* r = p */ | - | ||||||
1874 | static 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:
| 21337 | ||||||
1879 | - | |||||||
1880 | /* r = p */ | - | ||||||
1881 | static 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:
| 408806 | ||||||
1887 | - | |||||||
1888 | /* r = 2 * p */ | - | ||||||
1889 | static 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:
| 27622 | ||||||
1902 | - | |||||||
1903 | /* r = 2 * p */ | - | ||||||
1904 | static 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:
| 6285 | ||||||
1909 | - | |||||||
1910 | /* r = p + q */ | - | ||||||
1911 | static 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:
| 401834 | ||||||
1925 | - | |||||||
1926 | /* r = p - q */ | - | ||||||
1927 | static 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:
| 186 | ||||||
1941 | - | |||||||
1942 | /* r = p + q */ | - | ||||||
1943 | static 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:
| 305 | ||||||
1958 | - | |||||||
1959 | /* r = p - q */ | - | ||||||
1960 | static 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:
| 196 | ||||||
1975 | - | |||||||
1976 | static 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:
| 3212800 | ||||||
1984 | } | - | ||||||
1985 | - | |||||||
1986 | static 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:
| 3614400 | ||||||
1991 | - | |||||||
1992 | /* k25519Precomp[i][j] = (j+1)*256^i*B */ | - | ||||||
1993 | static 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 |