1 #include <string.h>
2
3 #include "private/common.h"
4 #include "utils.h"
5
6 /*
7 h = 0
8 */
9
10 static inline void
fe25519_0(fe25519 h)11 fe25519_0(fe25519 h)
12 {
13 memset(&h[0], 0, 5 * sizeof h[0]);
14 }
15
16 /*
17 h = 1
18 */
19
20 static inline void
fe25519_1(fe25519 h)21 fe25519_1(fe25519 h)
22 {
23 h[0] = 1;
24 memset(&h[1], 0, 4 * sizeof h[0]);
25 }
26
27 /*
28 h = f + g
29 Can overlap h with f or g.
30 */
31
32 static inline void
fe25519_add(fe25519 h,const fe25519 f,const fe25519 g)33 fe25519_add(fe25519 h, const fe25519 f, const fe25519 g)
34 {
35 uint64_t h0 = f[0] + g[0];
36 uint64_t h1 = f[1] + g[1];
37 uint64_t h2 = f[2] + g[2];
38 uint64_t h3 = f[3] + g[3];
39 uint64_t h4 = f[4] + g[4];
40
41 h[0] = h0;
42 h[1] = h1;
43 h[2] = h2;
44 h[3] = h3;
45 h[4] = h4;
46 }
47
48 /*
49 h = f - g
50 */
51
52 static void
fe25519_sub(fe25519 h,const fe25519 f,const fe25519 g)53 fe25519_sub(fe25519 h, const fe25519 f, const fe25519 g)
54 {
55 const uint64_t mask = 0x7ffffffffffffULL;
56 uint64_t h0, h1, h2, h3, h4;
57
58 h0 = g[0];
59 h1 = g[1];
60 h2 = g[2];
61 h3 = g[3];
62 h4 = g[4];
63
64 h1 += h0 >> 51;
65 h0 &= mask;
66 h2 += h1 >> 51;
67 h1 &= mask;
68 h3 += h2 >> 51;
69 h2 &= mask;
70 h4 += h3 >> 51;
71 h3 &= mask;
72 h0 += 19ULL * (h4 >> 51);
73 h4 &= mask;
74
75 h0 = (f[0] + 0xfffffffffffdaULL) - h0;
76 h1 = (f[1] + 0xffffffffffffeULL) - h1;
77 h2 = (f[2] + 0xffffffffffffeULL) - h2;
78 h3 = (f[3] + 0xffffffffffffeULL) - h3;
79 h4 = (f[4] + 0xffffffffffffeULL) - h4;
80
81 h[0] = h0;
82 h[1] = h1;
83 h[2] = h2;
84 h[3] = h3;
85 h[4] = h4;
86 }
87
88 /*
89 h = -f
90 */
91
92 static inline void
fe25519_neg(fe25519 h,const fe25519 f)93 fe25519_neg(fe25519 h, const fe25519 f)
94 {
95 fe25519 zero;
96
97 fe25519_0(zero);
98 fe25519_sub(h, zero, f);
99 }
100
101 /*
102 Replace (f,g) with (g,g) if b == 1;
103 replace (f,g) with (f,g) if b == 0.
104 *
105 Preconditions: b in {0,1}.
106 */
107
108 static void
fe25519_cmov(fe25519 f,const fe25519 g,unsigned int b)109 fe25519_cmov(fe25519 f, const fe25519 g, unsigned int b)
110 {
111 const uint64_t mask = (uint64_t) (-(int64_t) b);
112
113 uint64_t f0 = f[0];
114 uint64_t f1 = f[1];
115 uint64_t f2 = f[2];
116 uint64_t f3 = f[3];
117 uint64_t f4 = f[4];
118
119 uint64_t x0 = f0 ^ g[0];
120 uint64_t x1 = f1 ^ g[1];
121 uint64_t x2 = f2 ^ g[2];
122 uint64_t x3 = f3 ^ g[3];
123 uint64_t x4 = f4 ^ g[4];
124
125 x0 &= mask;
126 x1 &= mask;
127 x2 &= mask;
128 x3 &= mask;
129 x4 &= mask;
130
131 f[0] = f0 ^ x0;
132 f[1] = f1 ^ x1;
133 f[2] = f2 ^ x2;
134 f[3] = f3 ^ x3;
135 f[4] = f4 ^ x4;
136 }
137
138 /*
139 Replace (f,g) with (g,f) if b == 1;
140 replace (f,g) with (f,g) if b == 0.
141
142 Preconditions: b in {0,1}.
143 */
144
145 static void
fe25519_cswap(fe25519 f,fe25519 g,unsigned int b)146 fe25519_cswap(fe25519 f, fe25519 g, unsigned int b)
147 {
148 const uint64_t mask = (uint64_t) (-(int64_t) b);
149
150 uint64_t f0 = f[0];
151 uint64_t f1 = f[1];
152 uint64_t f2 = f[2];
153 uint64_t f3 = f[3];
154 uint64_t f4 = f[4];
155
156 uint64_t g0 = g[0];
157 uint64_t g1 = g[1];
158 uint64_t g2 = g[2];
159 uint64_t g3 = g[3];
160 uint64_t g4 = g[4];
161
162 uint64_t x0 = f0 ^ g0;
163 uint64_t x1 = f1 ^ g1;
164 uint64_t x2 = f2 ^ g2;
165 uint64_t x3 = f3 ^ g3;
166 uint64_t x4 = f4 ^ g4;
167
168 x0 &= mask;
169 x1 &= mask;
170 x2 &= mask;
171 x3 &= mask;
172 x4 &= mask;
173
174 f[0] = f0 ^ x0;
175 f[1] = f1 ^ x1;
176 f[2] = f2 ^ x2;
177 f[3] = f3 ^ x3;
178 f[4] = f4 ^ x4;
179
180 g[0] = g0 ^ x0;
181 g[1] = g1 ^ x1;
182 g[2] = g2 ^ x2;
183 g[3] = g3 ^ x3;
184 g[4] = g4 ^ x4;
185 }
186
187 /*
188 h = f
189 */
190
191 static inline void
fe25519_copy(fe25519 h,const fe25519 f)192 fe25519_copy(fe25519 h, const fe25519 f)
193 {
194 uint64_t f0 = f[0];
195 uint64_t f1 = f[1];
196 uint64_t f2 = f[2];
197 uint64_t f3 = f[3];
198 uint64_t f4 = f[4];
199
200 h[0] = f0;
201 h[1] = f1;
202 h[2] = f2;
203 h[3] = f3;
204 h[4] = f4;
205 }
206
207 /*
208 return 1 if f is in {1,3,5,...,q-2}
209 return 0 if f is in {0,2,4,...,q-1}
210 */
211
212 static inline int
fe25519_isnegative(const fe25519 f)213 fe25519_isnegative(const fe25519 f)
214 {
215 unsigned char s[32];
216
217 fe25519_tobytes(s, f);
218
219 return s[0] & 1;
220 }
221
222 /*
223 return 1 if f == 0
224 return 0 if f != 0
225 */
226
227 static inline int
fe25519_iszero(const fe25519 f)228 fe25519_iszero(const fe25519 f)
229 {
230 unsigned char s[32];
231
232 fe25519_tobytes(s, f);
233
234 return sodium_is_zero(s, 32);
235 }
236
237 /*
238 h = f * g
239 Can overlap h with f or g.
240 */
241
242 static void
fe25519_mul(fe25519 h,const fe25519 f,const fe25519 g)243 fe25519_mul(fe25519 h, const fe25519 f, const fe25519 g)
244 {
245 const uint64_t mask = 0x7ffffffffffffULL;
246 uint128_t r0, r1, r2, r3, r4, carry;
247 uint64_t f0, f1, f2, f3, f4;
248 uint64_t f1_19, f2_19, f3_19, f4_19;
249 uint64_t g0, g1, g2, g3, g4;
250 uint64_t r00, r01, r02, r03, r04;
251
252 f0 = f[0];
253 f1 = f[1];
254 f2 = f[2];
255 f3 = f[3];
256 f4 = f[4];
257
258 g0 = g[0];
259 g1 = g[1];
260 g2 = g[2];
261 g3 = g[3];
262 g4 = g[4];
263
264 f1_19 = 19ULL * f1;
265 f2_19 = 19ULL * f2;
266 f3_19 = 19ULL * f3;
267 f4_19 = 19ULL * f4;
268
269 r0 = ((uint128_t) f0 ) * ((uint128_t) g0);
270 r0 += ((uint128_t) f1_19) * ((uint128_t) g4);
271 r0 += ((uint128_t) f2_19) * ((uint128_t) g3);
272 r0 += ((uint128_t) f3_19) * ((uint128_t) g2);
273 r0 += ((uint128_t) f4_19) * ((uint128_t) g1);
274
275 r1 = ((uint128_t) f0 ) * ((uint128_t) g1);
276 r1 += ((uint128_t) f1 ) * ((uint128_t) g0);
277 r1 += ((uint128_t) f2_19) * ((uint128_t) g4);
278 r1 += ((uint128_t) f3_19) * ((uint128_t) g3);
279 r1 += ((uint128_t) f4_19) * ((uint128_t) g2);
280
281 r2 = ((uint128_t) f0 ) * ((uint128_t) g2);
282 r2 += ((uint128_t) f1 ) * ((uint128_t) g1);
283 r2 += ((uint128_t) f2 ) * ((uint128_t) g0);
284 r2 += ((uint128_t) f3_19) * ((uint128_t) g4);
285 r2 += ((uint128_t) f4_19) * ((uint128_t) g3);
286
287 r3 = ((uint128_t) f0 ) * ((uint128_t) g3);
288 r3 += ((uint128_t) f1 ) * ((uint128_t) g2);
289 r3 += ((uint128_t) f2 ) * ((uint128_t) g1);
290 r3 += ((uint128_t) f3 ) * ((uint128_t) g0);
291 r3 += ((uint128_t) f4_19) * ((uint128_t) g4);
292
293 r4 = ((uint128_t) f0 ) * ((uint128_t) g4);
294 r4 += ((uint128_t) f1 ) * ((uint128_t) g3);
295 r4 += ((uint128_t) f2 ) * ((uint128_t) g2);
296 r4 += ((uint128_t) f3 ) * ((uint128_t) g1);
297 r4 += ((uint128_t) f4 ) * ((uint128_t) g0);
298
299 r00 = ((uint64_t) r0) & mask;
300 carry = r0 >> 51;
301 r1 += carry;
302 r01 = ((uint64_t) r1) & mask;
303 carry = r1 >> 51;
304 r2 += carry;
305 r02 = ((uint64_t) r2) & mask;
306 carry = r2 >> 51;
307 r3 += carry;
308 r03 = ((uint64_t) r3) & mask;
309 carry = r3 >> 51;
310 r4 += carry;
311 r04 = ((uint64_t) r4) & mask;
312 carry = r4 >> 51;
313 r00 += 19ULL * (uint64_t) carry;
314 carry = r00 >> 51;
315 r00 &= mask;
316 r01 += (uint64_t) carry;
317 carry = r01 >> 51;
318 r01 &= mask;
319 r02 += (uint64_t) carry;
320
321 h[0] = r00;
322 h[1] = r01;
323 h[2] = r02;
324 h[3] = r03;
325 h[4] = r04;
326 }
327
328 /*
329 h = f * f
330 Can overlap h with f.
331 */
332
333 static void
fe25519_sq(fe25519 h,const fe25519 f)334 fe25519_sq(fe25519 h, const fe25519 f)
335 {
336 const uint64_t mask = 0x7ffffffffffffULL;
337 uint128_t r0, r1, r2, r3, r4, carry;
338 uint64_t f0, f1, f2, f3, f4;
339 uint64_t f0_2, f1_2, f1_38, f2_38, f3_38, f3_19, f4_19;
340 uint64_t r00, r01, r02, r03, r04;
341
342 f0 = f[0];
343 f1 = f[1];
344 f2 = f[2];
345 f3 = f[3];
346 f4 = f[4];
347
348 f0_2 = f0 << 1;
349 f1_2 = f1 << 1;
350
351 f1_38 = 38ULL * f1;
352 f2_38 = 38ULL * f2;
353 f3_38 = 38ULL * f3;
354
355 f3_19 = 19ULL * f3;
356 f4_19 = 19ULL * f4;
357
358 r0 = ((uint128_t) f0 ) * ((uint128_t) f0);
359 r0 += ((uint128_t) f1_38) * ((uint128_t) f4);
360 r0 += ((uint128_t) f2_38) * ((uint128_t) f3);
361
362 r1 = ((uint128_t) f0_2 ) * ((uint128_t) f1);
363 r1 += ((uint128_t) f2_38) * ((uint128_t) f4);
364 r1 += ((uint128_t) f3_19) * ((uint128_t) f3);
365
366 r2 = ((uint128_t) f0_2 ) * ((uint128_t) f2);
367 r2 += ((uint128_t) f1 ) * ((uint128_t) f1);
368 r2 += ((uint128_t) f3_38) * ((uint128_t) f4);
369
370 r3 = ((uint128_t) f0_2 ) * ((uint128_t) f3);
371 r3 += ((uint128_t) f1_2 ) * ((uint128_t) f2);
372 r3 += ((uint128_t) f4_19) * ((uint128_t) f4);
373
374 r4 = ((uint128_t) f0_2 ) * ((uint128_t) f4);
375 r4 += ((uint128_t) f1_2 ) * ((uint128_t) f3);
376 r4 += ((uint128_t) f2 ) * ((uint128_t) f2);
377
378 r00 = ((uint64_t) r0) & mask;
379 carry = r0 >> 51;
380 r1 += carry;
381 r01 = ((uint64_t) r1) & mask;
382 carry = r1 >> 51;
383 r2 += carry;
384 r02 = ((uint64_t) r2) & mask;
385 carry = r2 >> 51;
386 r3 += carry;
387 r03 = ((uint64_t) r3) & mask;
388 carry = r3 >> 51;
389 r4 += carry;
390 r04 = ((uint64_t) r4) & mask;
391 carry = r4 >> 51;
392 r00 += 19ULL * (uint64_t) carry;
393 carry = r00 >> 51;
394 r00 &= mask;
395 r01 += (uint64_t) carry;
396 carry = r01 >> 51;
397 r01 &= mask;
398 r02 += (uint64_t) carry;
399
400 h[0] = r00;
401 h[1] = r01;
402 h[2] = r02;
403 h[3] = r03;
404 h[4] = r04;
405 }
406
407 /*
408 h = 2 * f * f
409 Can overlap h with f.
410 */
411
412 static void
fe25519_sq2(fe25519 h,const fe25519 f)413 fe25519_sq2(fe25519 h, const fe25519 f)
414 {
415 const uint64_t mask = 0x7ffffffffffffULL;
416 uint128_t r0, r1, r2, r3, r4, carry;
417 uint64_t f0, f1, f2, f3, f4;
418 uint64_t f0_2, f1_2, f1_38, f2_38, f3_38, f3_19, f4_19;
419 uint64_t r00, r01, r02, r03, r04;
420
421 f0 = f[0];
422 f1 = f[1];
423 f2 = f[2];
424 f3 = f[3];
425 f4 = f[4];
426
427 f0_2 = f0 << 1;
428 f1_2 = f1 << 1;
429
430 f1_38 = 38ULL * f1;
431 f2_38 = 38ULL * f2;
432 f3_38 = 38ULL * f3;
433
434 f3_19 = 19ULL * f3;
435 f4_19 = 19ULL * f4;
436
437 r0 = ((uint128_t) f0 ) * ((uint128_t) f0);
438 r0 += ((uint128_t) f1_38) * ((uint128_t) f4);
439 r0 += ((uint128_t) f2_38) * ((uint128_t) f3);
440
441 r1 = ((uint128_t) f0_2 ) * ((uint128_t) f1);
442 r1 += ((uint128_t) f2_38) * ((uint128_t) f4);
443 r1 += ((uint128_t) f3_19) * ((uint128_t) f3);
444
445 r2 = ((uint128_t) f0_2 ) * ((uint128_t) f2);
446 r2 += ((uint128_t) f1 ) * ((uint128_t) f1);
447 r2 += ((uint128_t) f3_38) * ((uint128_t) f4);
448
449 r3 = ((uint128_t) f0_2 ) * ((uint128_t) f3);
450 r3 += ((uint128_t) f1_2 ) * ((uint128_t) f2);
451 r3 += ((uint128_t) f4_19) * ((uint128_t) f4);
452
453 r4 = ((uint128_t) f0_2 ) * ((uint128_t) f4);
454 r4 += ((uint128_t) f1_2 ) * ((uint128_t) f3);
455 r4 += ((uint128_t) f2 ) * ((uint128_t) f2);
456
457 r0 <<= 1;
458 r1 <<= 1;
459 r2 <<= 1;
460 r3 <<= 1;
461 r4 <<= 1;
462
463 r00 = ((uint64_t) r0) & mask;
464 carry = r0 >> 51;
465 r1 += carry;
466 r01 = ((uint64_t) r1) & mask;
467 carry = r1 >> 51;
468 r2 += carry;
469 r02 = ((uint64_t) r2) & mask;
470 carry = r2 >> 51;
471 r3 += carry;
472 r03 = ((uint64_t) r3) & mask;
473 carry = r3 >> 51;
474 r4 += carry;
475 r04 = ((uint64_t) r4) & mask;
476 carry = r4 >> 51;
477 r00 += 19ULL * (uint64_t) carry;
478 carry = r00 >> 51;
479 r00 &= mask;
480 r01 += (uint64_t) carry;
481 carry = r01 >> 51;
482 r01 &= mask;
483 r02 += (uint64_t) carry;
484
485 h[0] = r00;
486 h[1] = r01;
487 h[2] = r02;
488 h[3] = r03;
489 h[4] = r04;
490 }
491
492 static void
fe25519_scalar_product(fe25519 h,const fe25519 f,uint32_t n)493 fe25519_scalar_product(fe25519 h, const fe25519 f, uint32_t n)
494 {
495 const uint64_t mask = 0x7ffffffffffffULL;
496 uint128_t a;
497 uint128_t sn = (uint128_t) n;
498 uint64_t h0, h1, h2, h3, h4;
499
500 a = f[0] * sn;
501 h0 = ((uint64_t) a) & mask;
502 a = f[1] * sn + ((uint64_t) (a >> 51));
503 h1 = ((uint64_t) a) & mask;
504 a = f[2] * sn + ((uint64_t) (a >> 51));
505 h2 = ((uint64_t) a) & mask;
506 a = f[3] * sn + ((uint64_t) (a >> 51));
507 h3 = ((uint64_t) a) & mask;
508 a = f[4] * sn + ((uint64_t) (a >> 51));
509 h4 = ((uint64_t) a) & mask;
510
511 h0 += (a >> 51) * 19ULL;
512
513 h[0] = h0;
514 h[1] = h1;
515 h[2] = h2;
516 h[3] = h3;
517 h[4] = h4;
518 }
519