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
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
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
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
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
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
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
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
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
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
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
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
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
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
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