curve25519.c
Go to the documentation of this file.
1 /**
2  * @file curve25519.c
3  * @brief Curve25519 elliptic curve (constant-time implementation)
4  *
5  * @section License
6  *
7  * SPDX-License-Identifier: GPL-2.0-or-later
8  *
9  * Copyright (C) 2010-2025 Oryx Embedded SARL. All rights reserved.
10  *
11  * This file is part of CycloneCRYPTO Open.
12  *
13  * This program is free software; you can redistribute it and/or
14  * modify it under the terms of the GNU General Public License
15  * as published by the Free Software Foundation; either version 2
16  * of the License, or (at your option) any later version.
17  *
18  * This program is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21  * GNU General Public License for more details.
22  *
23  * You should have received a copy of the GNU General Public License
24  * along with this program; if not, write to the Free Software Foundation,
25  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
26  *
27  * @author Oryx Embedded SARL (www.oryx-embedded.com)
28  * @version 2.5.0
29  **/
30 
31 //Switch to the appropriate trace level
32 #define TRACE_LEVEL CRYPTO_TRACE_LEVEL
33 
34 //Dependencies
35 #include "core/crypto.h"
36 #include "ecc/ec.h"
37 #include "ecc/curve25519.h"
38 #include "debug.h"
39 
40 //Check crypto library configuration
41 #if (X25519_SUPPORT == ENABLED || ED25519_SUPPORT == ENABLED)
42 
43 //Square root of -1 modulo p (constant)
44 static const int32_t CURVE25519_SQRT_MINUS_1[9] =
45 {
46  0x0A0EA0B0, 0x0770D93A, 0x0BF91E31, 0x06300D5A, 0x1D7A72F4,
47  0x004C9EFD, 0x1C2CAD34, 0x1009F83B, 0x002B8324
48 };
49 
50 
51 /**
52  * @brief Set integer value
53  * @param[out] a Pointer to the integer to be initialized
54  * @param[in] b An integer such as 0 <= B < (2^29 - 1)
55  **/
56 
57 void curve25519SetInt(int32_t *a, int32_t b)
58 {
59  uint_t i;
60 
61  //Set the value of the least significant word
62  a[0] = b;
63 
64  //Initialize the rest of the integer
65  for(i = 1; i < 9; i++)
66  {
67  a[i] = 0;
68  }
69 }
70 
71 
72 /**
73  * @brief Modular addition
74  * @param[out] r Resulting integer R = (A + B) mod p
75  * @param[in] a An integer such as 0 <= A < p
76  * @param[in] b An integer such as 0 <= B < p
77  **/
78 
79 void curve25519Add(int32_t *r, const int32_t *a, const int32_t *b)
80 {
81 #if (CURVE25519_SPEED_OPTIMIZATION_LEVEL <= 1)
82  uint_t i;
83  int32_t temp;
84 
85  //Compute R = A + B
86  for(temp = 0, i = 0; i < 8; i++)
87  {
88  temp += a[i] + b[i];
89  r[i] = temp & 0x1FFFFFFF;
90  temp >>= 29;
91  }
92 
93  temp += a[8] + b[8];
94  r[8] = temp & 0x007FFFFF;
95  temp >>= 23;
96 
97  //Perform modular reduction (2^255 = 19)
98  r[0] += temp * 19;
99 #else
100  int32_t temp;
101 
102  //Compute R = A + B
103  temp = a[0] + b[0];
104  r[0] = temp & 0x1FFFFFFF;
105  temp >>= 29;
106  temp += a[1] + b[1];
107  r[1] = temp & 0x1FFFFFFF;
108  temp >>= 29;
109  temp += a[2] + b[2];
110  r[2] = temp & 0x1FFFFFFF;
111  temp >>= 29;
112  temp += a[3] + b[3];
113  r[3] = temp & 0x1FFFFFFF;
114  temp >>= 29;
115  temp += a[4] + b[4];
116  r[4] = temp & 0x1FFFFFFF;
117  temp >>= 29;
118  temp += a[5] + b[5];
119  r[5] = temp & 0x1FFFFFFF;
120  temp >>= 29;
121  temp += a[6] + b[6];
122  r[6] = temp & 0x1FFFFFFF;
123  temp >>= 29;
124  temp += a[7] + b[7];
125  r[7] = temp & 0x1FFFFFFF;
126  temp >>= 29;
127  temp += a[8] + b[8];
128  r[8] = temp & 0x007FFFFF;
129  temp >>= 23;
130 
131  //Perform modular reduction (2^255 = 19)
132  r[0] += temp * 19;
133 #endif
134 }
135 
136 
137 /**
138  * @brief Modular addition
139  * @param[out] r Resulting integer R = (A + B) mod p
140  * @param[in] a An integer such as 0 <= A < p
141  * @param[in] b An integer such as 0 <= B < (2^32 - 1)
142  **/
143 
144 void curve25519AddInt(int32_t *r, const int32_t *a, int32_t b)
145 {
146  uint_t i;
147  int32_t temp;
148 
149  //Compute R = A + B
150  for(temp = b, i = 0; i < 8; i++)
151  {
152  temp += a[i];
153  r[i] = temp & 0x1FFFFFFF;
154  temp >>= 29;
155  }
156 
157  temp += a[8];
158  r[8] = temp & 0x007FFFFF;
159  temp >>= 23;
160 
161  //Perform modular reduction (2^255 = 19)
162  r[0] += temp * 19;
163 }
164 
165 
166 /**
167  * @brief Modular subtraction
168  * @param[out] r Resulting integer R = (A - B) mod p
169  * @param[in] a An integer such as 0 <= A < p
170  * @param[in] b An integer such as 0 <= B < p
171  **/
172 
173 void curve25519Sub(int32_t *r, const int32_t *a, const int32_t *b)
174 {
175 #if (CURVE25519_SPEED_OPTIMIZATION_LEVEL <= 1)
176  uint_t i;
177  int32_t temp;
178 
179  //Compute R = A - B
180  for(temp = 0, i = 0; i < 8; i++)
181  {
182  temp += a[i] - b[i];
183  r[i] = temp & 0x1FFFFFFF;
184  temp >>= 29;
185  }
186 
187  temp += a[8] - b[8];
188  r[8] = temp & 0x007FFFFF;
189  temp >>= 23;
190 
191  //Perform modular reduction (2^255 = 19)
192  r[0] += temp * 19;
193 #else
194  int32_t temp;
195 
196  //Compute R = A - B
197  temp = a[0] - b[0];
198  r[0] = temp & 0x1FFFFFFF;
199  temp >>= 29;
200  temp += a[1] - b[1];
201  r[1] = temp & 0x1FFFFFFF;
202  temp >>= 29;
203  temp += a[2] - b[2];
204  r[2] = temp & 0x1FFFFFFF;
205  temp >>= 29;
206  temp += a[3] - b[3];
207  r[3] = temp & 0x1FFFFFFF;
208  temp >>= 29;
209  temp += a[4] - b[4];
210  r[4] = temp & 0x1FFFFFFF;
211  temp >>= 29;
212  temp += a[5] - b[5];
213  r[5] = temp & 0x1FFFFFFF;
214  temp >>= 29;
215  temp += a[6] - b[6];
216  r[6] = temp & 0x1FFFFFFF;
217  temp >>= 29;
218  temp += a[7] - b[7];
219  r[7] = temp & 0x1FFFFFFF;
220  temp >>= 29;
221  temp += a[8] - b[8];
222  r[8] = temp & 0x007FFFFF;
223  temp >>= 23;
224 
225  //Perform modular reduction
226  r[0] += temp * 19;
227 #endif
228 }
229 
230 
231 /**
232  * @brief Modular subtraction
233  * @param[out] r Resulting integer R = (A - B) mod p
234  * @param[in] a An integer such as 0 <= A < p
235  * @param[in] b An integer such as 0 <= B < (2^32 - 1)
236  **/
237 
238 void curve25519SubInt(int32_t *r, const int32_t *a, int32_t b)
239 {
240  uint_t i;
241  int32_t temp;
242 
243  //Compute R = A - B
244  for(temp = -b, i = 0; i < 8; i++)
245  {
246  temp += a[i];
247  r[i] = temp & 0x1FFFFFFF;
248  temp >>= 29;
249  }
250 
251  temp += a[8];
252  r[8] = temp & 0x007FFFFF;
253  temp >>= 23;
254 
255  //Perform modular reduction (2^255 = 19)
256  r[0] += temp * 19;
257 }
258 
259 
260 /**
261  * @brief Modular multiplication
262  * @param[out] r Resulting integer R = (A * B) mod p
263  * @param[in] a An integer such as 0 <= A < p
264  * @param[in] b An integer such as 0 <= B < p
265  **/
266 
267 __weak_func void curve25519Mul(int32_t *r, const int32_t *a, const int32_t *b)
268 {
269 #if (CURVE25519_SPEED_OPTIMIZATION_LEVEL == 0)
270  uint_t i;
271  uint_t j;
272  int64_t temp;
273  int32_t u[18];
274 
275  //Comba's method is used to perform multiplication
276  for(temp = 0, i = 0; i < 18; i++)
277  {
278  //The algorithm computes the products, column by column
279  if(i < 9)
280  {
281  //Inner loop
282  for(j = 0; j <= i; j++)
283  {
284  temp += (int64_t) a[j] * b[i - j];
285  }
286  }
287  else
288  {
289  //Inner loop
290  for(j = i - 8; j < 9; j++)
291  {
292  temp += (int64_t) a[j] * b[i - j];
293  }
294  }
295 
296  //At the bottom of each column, the final result is written to memory
297  u[i] = temp & 0x1FFFFFFF;
298  //Propagate the carry upwards
299  temp >>= 29;
300  }
301 
302  //Perform modular reduction (first pass)
303  for(temp = 0, i = 0; i < 8; i++)
304  {
305  temp += u[i];
306  temp += (int64_t) u[i + 9] * 1216;
307  r[i] = temp & 0x1FFFFFFF;
308  temp >>= 29;
309  }
310 
311  temp += u[8];
312  temp += (int64_t) u[17] * 1216;
313  r[8] = temp & 0x007FFFFF;
314  temp >>= 23;
315 
316  //Perform modular reduction (second pass)
317  temp *= 19;
318  temp += r[0];
319  r[0] = temp & 0x1FFFFFFF;
320  temp >>= 29;
321  r[1] += temp & 0xFFFFFFFF;
322 #else
323  int64_t temp;
324  int32_t u[18];
325 
326  //Compute R = A * B
327  temp = (int64_t) a[0] * b[0];
328  u[0] = temp & 0x1FFFFFFF;
329  temp >>= 29;
330  temp += (int64_t) a[0] * b[1];
331  temp += (int64_t) a[1] * b[0];
332  u[1] = temp & 0x1FFFFFFF;
333  temp >>= 29;
334  temp += (int64_t) a[0] * b[2];
335  temp += (int64_t) a[1] * b[1];
336  temp += (int64_t) a[2] * b[0];
337  u[2] = temp & 0x1FFFFFFF;
338  temp >>= 29;
339  temp += (int64_t) a[0] * b[3];
340  temp += (int64_t) a[1] * b[2];
341  temp += (int64_t) a[2] * b[1];
342  temp += (int64_t) a[3] * b[0];
343  u[3] = temp & 0x1FFFFFFF;
344  temp >>= 29;
345  temp += (int64_t) a[0] * b[4];
346  temp += (int64_t) a[1] * b[3];
347  temp += (int64_t) a[2] * b[2];
348  temp += (int64_t) a[3] * b[1];
349  temp += (int64_t) a[4] * b[0];
350  u[4] = temp & 0x1FFFFFFF;
351  temp >>= 29;
352  temp += (int64_t) a[0] * b[5];
353  temp += (int64_t) a[1] * b[4];
354  temp += (int64_t) a[2] * b[3];
355  temp += (int64_t) a[3] * b[2];
356  temp += (int64_t) a[4] * b[1];
357  temp += (int64_t) a[5] * b[0];
358  u[5] = temp & 0x1FFFFFFF;
359  temp >>= 29;
360  temp += (int64_t) a[0] * b[6];
361  temp += (int64_t) a[1] * b[5];
362  temp += (int64_t) a[2] * b[4];
363  temp += (int64_t) a[3] * b[3];
364  temp += (int64_t) a[4] * b[2];
365  temp += (int64_t) a[5] * b[1];
366  temp += (int64_t) a[6] * b[0];
367  u[6] = temp & 0x1FFFFFFF;
368  temp >>= 29;
369  temp += (int64_t) a[0] * b[7];
370  temp += (int64_t) a[1] * b[6];
371  temp += (int64_t) a[2] * b[5];
372  temp += (int64_t) a[3] * b[4];
373  temp += (int64_t) a[4] * b[3];
374  temp += (int64_t) a[5] * b[2];
375  temp += (int64_t) a[6] * b[1];
376  temp += (int64_t) a[7] * b[0];
377  u[7] = temp & 0x1FFFFFFF;
378  temp >>= 29;
379  temp += (int64_t) a[0] * b[8];
380  temp += (int64_t) a[1] * b[7];
381  temp += (int64_t) a[2] * b[6];
382  temp += (int64_t) a[3] * b[5];
383  temp += (int64_t) a[4] * b[4];
384  temp += (int64_t) a[5] * b[3];
385  temp += (int64_t) a[6] * b[2];
386  temp += (int64_t) a[7] * b[1];
387  temp += (int64_t) a[8] * b[0];
388  u[8] = temp & 0x1FFFFFFF;
389  temp >>= 29;
390  temp += (int64_t) a[1] * b[8];
391  temp += (int64_t) a[2] * b[7];
392  temp += (int64_t) a[3] * b[6];
393  temp += (int64_t) a[4] * b[5];
394  temp += (int64_t) a[5] * b[4];
395  temp += (int64_t) a[6] * b[3];
396  temp += (int64_t) a[7] * b[2];
397  temp += (int64_t) a[8] * b[1];
398  u[9] = temp & 0x1FFFFFFF;
399  temp >>= 29;
400  temp += (int64_t) a[2] * b[8];
401  temp += (int64_t) a[3] * b[7];
402  temp += (int64_t) a[4] * b[6];
403  temp += (int64_t) a[5] * b[5];
404  temp += (int64_t) a[6] * b[4];
405  temp += (int64_t) a[7] * b[3];
406  temp += (int64_t) a[8] * b[2];
407  u[10] = temp & 0x1FFFFFFF;
408  temp >>= 29;
409  temp += (int64_t) a[3] * b[8];
410  temp += (int64_t) a[4] * b[7];
411  temp += (int64_t) a[5] * b[6];
412  temp += (int64_t) a[6] * b[5];
413  temp += (int64_t) a[7] * b[4];
414  temp += (int64_t) a[8] * b[3];
415  u[11] = temp & 0x1FFFFFFF;
416  temp >>= 29;
417  temp += (int64_t) a[4] * b[8];
418  temp += (int64_t) a[5] * b[7];
419  temp += (int64_t) a[6] * b[6];
420  temp += (int64_t) a[7] * b[5];
421  temp += (int64_t) a[8] * b[4];
422  u[12] = temp & 0x1FFFFFFF;
423  temp >>= 29;
424  temp += (int64_t) a[5] * b[8];
425  temp += (int64_t) a[6] * b[7];
426  temp += (int64_t) a[7] * b[6];
427  temp += (int64_t) a[8] * b[5];
428  u[13] = temp & 0x1FFFFFFF;
429  temp >>= 29;
430  temp += (int64_t) a[6] * b[8];
431  temp += (int64_t) a[7] * b[7];
432  temp += (int64_t) a[8] * b[6];
433  u[14] = temp & 0x1FFFFFFF;
434  temp >>= 29;
435  temp += (int64_t) a[7] * b[8];
436  temp += (int64_t) a[8] * b[7];
437  u[15] = temp & 0x1FFFFFFF;
438  temp >>= 29;
439  temp += (int64_t) a[8] * b[8];
440  u[16] = temp & 0x1FFFFFFF;
441  temp >>= 29;
442  u[17] = temp & 0xFFFFFFFF;
443 
444  //Perform modular reduction (first pass)
445  temp = u[0];
446  temp += (int64_t) u[9] * 1216;
447  r[0] = temp & 0x1FFFFFFF;
448  temp >>= 29;
449  temp += u[1];
450  temp += (int64_t) u[10] * 1216;
451  r[1] = temp & 0x1FFFFFFF;
452  temp >>= 29;
453  temp += u[2];
454  temp += (int64_t) u[11] * 1216;
455  r[2] = temp & 0x1FFFFFFF;
456  temp >>= 29;
457  temp += u[3];
458  temp += (int64_t) u[12] * 1216;
459  r[3] = temp & 0x1FFFFFFF;
460  temp >>= 29;
461  temp += u[4];
462  temp += (int64_t) u[13] * 1216;
463  r[4] = temp & 0x1FFFFFFF;
464  temp >>= 29;
465  temp += u[5];
466  temp += (int64_t) u[14] * 1216;
467  r[5] = temp & 0x1FFFFFFF;
468  temp >>= 29;
469  temp += u[6];
470  temp += (int64_t) u[15] * 1216;
471  r[6] = temp & 0x1FFFFFFF;
472  temp >>= 29;
473  temp += u[7];
474  temp += (int64_t) u[16] * 1216;
475  r[7] = temp & 0x1FFFFFFF;
476  temp >>= 29;
477  temp += u[8];
478  temp += (int64_t) u[17] * 1216;
479  r[8] = temp & 0x007FFFFF;
480  temp >>= 23;
481 
482  //Perform modular reduction (second pass)
483  temp *= 19;
484  temp += r[0];
485  r[0] = temp & 0x1FFFFFFF;
486  temp >>= 29;
487  r[1] += temp & 0xFFFFFFFF;
488 #endif
489 }
490 
491 
492 /**
493  * @brief Modular multiplication
494  * @param[out] r Resulting integer R = (A * B) mod p
495  * @param[in] a An integer such as 0 <= A < p
496  * @param[in] b An integer such as 0 <= B < (2^29 - 1)
497  **/
498 
499 void curve25519MulInt(int32_t *r, const int32_t *a, int32_t b)
500 {
501 #if (CURVE25519_SPEED_OPTIMIZATION_LEVEL == 0)
502  int_t i;
503  int64_t temp;
504 
505  //Compute R = A * B
506  for(temp = 0, i = 0; i < 8; i++)
507  {
508  temp += (int64_t) a[i] * b;
509  r[i] = temp & 0x1FFFFFFF;
510  temp >>= 29;
511  }
512 
513  temp += (int64_t) a[8] * b;
514  r[8] = temp & 0x007FFFFF;
515  temp >>= 23;
516 
517  //Perform modular reduction (2^255 = 19)
518  temp *= 19;
519  temp += r[0];
520  r[0] = temp & 0x1FFFFFFF;
521  temp >>= 29;
522  r[1] += temp & 0xFFFFFFFF;
523 #else
524  int64_t temp;
525 
526  //Compute R = A * B
527  temp = (int64_t) a[0] * b;
528  r[0] = temp & 0x1FFFFFFF;
529  temp >>= 29;
530  temp += (int64_t) a[1] * b;
531  r[1] = temp & 0x1FFFFFFF;
532  temp >>= 29;
533  temp += (int64_t) a[2] * b;
534  r[2] = temp & 0x1FFFFFFF;
535  temp >>= 29;
536  temp += (int64_t) a[3] * b;
537  r[3] = temp & 0x1FFFFFFF;
538  temp >>= 29;
539  temp += (int64_t) a[4] * b;
540  r[4] = temp & 0x1FFFFFFF;
541  temp >>= 29;
542  temp += (int64_t) a[5] * b;
543  r[5] = temp & 0x1FFFFFFF;
544  temp >>= 29;
545  temp += (int64_t) a[6] * b;
546  r[6] = temp & 0x1FFFFFFF;
547  temp >>= 29;
548  temp += (int64_t) a[7] * b;
549  r[7] = temp & 0x1FFFFFFF;
550  temp >>= 29;
551  temp += (int64_t) a[8] * b;
552  r[8] = temp & 0x007FFFFF;
553  temp >>= 23;
554 
555  //Perform modular reduction (2^255 = 19)
556  temp *= 19;
557  temp += r[0];
558  r[0] = temp & 0x1FFFFFFF;
559  temp >>= 29;
560  r[1] += temp & 0xFFFFFFFF;
561 #endif
562 }
563 
564 
565 /**
566  * @brief Modular squaring
567  * @param[out] r Resulting integer R = (A ^ 2) mod p
568  * @param[in] a An integer such as 0 <= A < p
569  **/
570 
571 __weak_func void curve25519Sqr(int32_t *r, const int32_t *a)
572 {
573  //Compute R = (A ^ 2) mod p
574  curve25519Mul(r, a, a);
575 }
576 
577 
578 /**
579  * @brief Raise an integer to power 2^n
580  * @param[out] r Resulting integer R = (A ^ (2^n)) mod p
581  * @param[in] a An integer such as 0 <= A < p
582  * @param[in] n An integer such as n >= 1
583  **/
584 
585 void curve25519Pwr2(int32_t *r, const int32_t *a, uint_t n)
586 {
587  uint_t i;
588 
589  //Pre-compute (A ^ 2) mod p
590  curve25519Sqr(r, a);
591 
592  //Compute R = (A ^ (2^n)) mod p
593  for(i = 1; i < n; i++)
594  {
595  curve25519Sqr(r, r);
596  }
597 }
598 
599 
600 /**
601  * @brief Modular multiplicative inverse
602  * @param[out] r Resulting integer R = A^-1 mod p
603  * @param[in] a An integer such as 0 <= A < p
604  **/
605 
606 void curve25519Inv(int32_t *r, const int32_t *a)
607 {
608  int32_t u[9];
609  int32_t v[9];
610 
611  //Since GF(p) is a prime field, the Fermat's little theorem can be
612  //used to find the multiplicative inverse of A modulo p
613  curve25519Sqr(u, a);
614  curve25519Mul(u, u, a); //A^(2^2 - 1)
615  curve25519Sqr(u, u);
616  curve25519Mul(v, u, a); //A^(2^3 - 1)
617  curve25519Pwr2(u, v, 3);
618  curve25519Mul(u, u, v); //A^(2^6 - 1)
619  curve25519Sqr(u, u);
620  curve25519Mul(v, u, a); //A^(2^7 - 1)
621  curve25519Pwr2(u, v, 7);
622  curve25519Mul(u, u, v); //A^(2^14 - 1)
623  curve25519Sqr(u, u);
624  curve25519Mul(v, u, a); //A^(2^15 - 1)
625  curve25519Pwr2(u, v, 15);
626  curve25519Mul(u, u, v); //A^(2^30 - 1)
627  curve25519Sqr(u, u);
628  curve25519Mul(v, u, a); //A^(2^31 - 1)
629  curve25519Pwr2(u, v, 31);
630  curve25519Mul(v, u, v); //A^(2^62 - 1)
631  curve25519Pwr2(u, v, 62);
632  curve25519Mul(u, u, v); //A^(2^124 - 1)
633  curve25519Sqr(u, u);
634  curve25519Mul(v, u, a); //A^(2^125 - 1)
635  curve25519Pwr2(u, v, 125);
636  curve25519Mul(u, u, v); //A^(2^250 - 1)
637  curve25519Sqr(u, u);
638  curve25519Sqr(u, u);
639  curve25519Mul(u, u, a); //A^(2^252 - 3)
640  curve25519Sqr(u, u);
641  curve25519Sqr(u, u);
642  curve25519Mul(u, u, a); //A^(2^254 - 11)
643  curve25519Sqr(u, u);
644  curve25519Mul(r, u, a); //A^(2^255 - 21)
645 }
646 
647 
648 /**
649  * @brief Compute the square root of (A / B) modulo p
650  * @param[out] r Resulting integer R = (A / B)^(1 / 2) mod p
651  * @param[in] a An integer such as 0 <= A < p
652  * @param[in] b An integer such as 0 < B < p
653  * @return The function returns 0 if the square root exists, else 1
654  **/
655 
656 uint32_t curve25519Sqrt(int32_t *r, const int32_t *a, const int32_t *b)
657 {
658  uint32_t res1;
659  uint32_t res2;
660  int32_t c[9];
661  int32_t u[9];
662  int32_t v[9];
663  int32_t w[9];
664 
665  //Compute the candidate root (A / B)^((p + 3) / 8). This can be done
666  //with the following trick, using a single modular powering for both the
667  //inversion of B and the square root: A * B^3 * (A * B^7)^((p - 5) / 8)
668  curve25519Sqr(v, b);
669  curve25519Mul(v, v, b);
670  curve25519Sqr(v, v);
671  curve25519Mul(v, v, b);
672 
673  //Compute C = A * B^7
674  curve25519Mul(c, a, v);
675 
676  //Compute U = C^((p - 5) / 8)
677  curve25519Sqr(u, c);
678  curve25519Mul(u, u, c); //C^(2^2 - 1)
679  curve25519Sqr(u, u);
680  curve25519Mul(v, u, c); //C^(2^3 - 1)
681  curve25519Pwr2(u, v, 3);
682  curve25519Mul(u, u, v); //C^(2^6 - 1)
683  curve25519Sqr(u, u);
684  curve25519Mul(v, u, c); //C^(2^7 - 1)
685  curve25519Pwr2(u, v, 7);
686  curve25519Mul(u, u, v); //C^(2^14 - 1)
687  curve25519Sqr(u, u);
688  curve25519Mul(v, u, c); //C^(2^15 - 1)
689  curve25519Pwr2(u, v, 15);
690  curve25519Mul(u, u, v); //C^(2^30 - 1)
691  curve25519Sqr(u, u);
692  curve25519Mul(v, u, c); //C^(2^31 - 1)
693  curve25519Pwr2(u, v, 31);
694  curve25519Mul(v, u, v); //C^(2^62 - 1)
695  curve25519Pwr2(u, v, 62);
696  curve25519Mul(u, u, v); //C^(2^124 - 1)
697  curve25519Sqr(u, u);
698  curve25519Mul(v, u, c); //C^(2^125 - 1)
699  curve25519Pwr2(u, v, 125);
700  curve25519Mul(u, u, v); //C^(2^250 - 1)
701  curve25519Sqr(u, u);
702  curve25519Sqr(u, u);
703  curve25519Mul(u, u, c); //C^(2^252 - 3)
704 
705  //The first candidate root is U = A * B^3 * (A * B^7)^((p - 5) / 8)
706  curve25519Mul(u, u, a);
707  curve25519Sqr(v, b);
708  curve25519Mul(v, v, b);
709  curve25519Mul(u, u, v);
710  curve25519Canonicalize(u, u);
711 
712  //The second candidate root is V = U * sqrt(-1)
713  curve25519Mul(v, u, CURVE25519_SQRT_MINUS_1);
714  curve25519Canonicalize(v, v);
715 
716  //Reduce non-canonical values of A
717  curve25519Canonicalize(w, a);
718 
719  //Calculate C = B * U^2
720  curve25519Sqr(c, u);
721  curve25519Mul(c, c, b);
722  curve25519Canonicalize(c, c);
723 
724  //Check whether B * U^2 = A
725  res1 = curve25519Comp(c, w);
726 
727  //Calculate C = B * V^2
728  curve25519Sqr(c, v);
729  curve25519Mul(c, c, b);
730  curve25519Canonicalize(c, c);
731 
732  //Check whether B * V^2 = A
733  res2 = curve25519Comp(c, w);
734 
735  //Select the first or the second candidate root
736  curve25519Select(r, u, v, res1);
737 
738  //Return 0 if the square root exists
739  return res1 & res2;
740 }
741 
742 
743 /**
744  * @brief Reduce non-canonical value
745  * @param[out] r Resulting integer R = A mod p
746  * @param[in] a An integer such as 0 <= A < (2^255 - 1)
747  **/
748 
749 void curve25519Canonicalize(int32_t *r, const int32_t *a)
750 {
751  uint_t i;
752  int32_t temp;
753  int32_t b[9];
754 
755  //Perform modular reduction (first pass)
756  for(temp = 0, i = 0; i < 8; i++)
757  {
758  temp += a[i];
759  r[i] = temp & 0x1FFFFFFF;
760  temp >>= 29;
761  }
762 
763  temp += a[8];
764  r[8] = temp & 0x007FFFFF;
765  temp >>= 23;
766 
767  //Perform modular reduction (second pass)
768  for(temp *= 19, i = 0; i < 9; i++)
769  {
770  temp += r[i];
771  r[i] = temp & 0x1FFFFFFF;
772  temp >>= 29;
773  }
774 
775  //Compute B = A + 19
776  for(temp = 19, i = 0; i < 9; i++)
777  {
778  temp += r[i];
779  b[i] = temp & 0x1FFFFFFF;
780  temp >>= 29;
781  }
782 
783  //Compute B = A - (2^255 - 19)
784  b[8] -= 0x00800000;
785  b[8] &= 0x00FFFFFF;
786 
787  //If B < (2^255 - 19) then R = B, else R = A
788  curve25519Select(r, b, r, (b[8] & 0x00800000) >> 23);
789 }
790 
791 
792 /**
793  * @brief Copy an integer
794  * @param[out] a Pointer to the destination integer
795  * @param[in] b Pointer to the source integer
796  **/
797 
798 void curve25519Copy(int32_t *a, const int32_t *b)
799 {
800  uint_t i;
801 
802  //Copy the value of the integer
803  for(i = 0; i < 9; i++)
804  {
805  a[i] = b[i];
806  }
807 }
808 
809 
810 /**
811  * @brief Conditional swap
812  * @param[in,out] a Pointer to the first integer
813  * @param[in,out] b Pointer to the second integer
814  * @param[in] c Condition variable
815  **/
816 
817 void curve25519Swap(int32_t *a, int32_t *b, uint32_t c)
818 {
819  uint_t i;
820  uint32_t mask;
821  uint32_t dummy;
822 
823  //The mask is the all-1 or all-0 word
824  mask = ~c + 1;
825 
826  //Conditional swap
827  for(i = 0; i < 9; i++)
828  {
829  //Constant time implementation
830  dummy = mask & (a[i] ^ b[i]);
831  a[i] ^= dummy;
832  b[i] ^= dummy;
833  }
834 }
835 
836 
837 /**
838  * @brief Select an integer
839  * @param[out] r Pointer to the destination integer
840  * @param[in] a Pointer to the first source integer
841  * @param[in] b Pointer to the second source integer
842  * @param[in] c Condition variable
843  **/
844 
845 void curve25519Select(int32_t *r, const int32_t *a, const int32_t *b,
846  uint32_t c)
847 {
848  uint_t i;
849  uint32_t mask;
850 
851  //The mask is the all-1 or all-0 word
852  mask = c - 1;
853 
854  //Select between A and B
855  for(i = 0; i < 9; i++)
856  {
857  //Constant time implementation
858  r[i] = (a[i] & mask) | (b[i] & ~mask);
859  }
860 }
861 
862 
863 /**
864  * @brief Compare integers
865  * @param[in] a Pointer to the first integer
866  * @param[in] b Pointer to the second integer
867  * @return The function returns 0 if the A = B, else 1
868  **/
869 
870 uint32_t curve25519Comp(const int32_t *a, const int32_t *b)
871 {
872  uint_t i;
873  uint32_t mask;
874 
875  //Initialize mask
876  mask = 0;
877 
878  //Compare A and B
879  for(i = 0; i < 9; i++)
880  {
881  //Constant time implementation
882  mask |= a[i] ^ b[i];
883  }
884 
885  //Return 0 if A = B, else 1
886  return ((uint32_t) (mask | (~mask + 1))) >> 31;
887 }
888 
889 
890 /**
891  * @brief Import an octet string
892  * @param[out] a Pointer to resulting integer
893  * @param[in] data Octet string to be converted
894  **/
895 
896 void curve25519Import(int32_t *a, const uint8_t *data)
897 {
898  uint_t i;
899  uint32_t temp;
900 
901  //Pack the octet string into 9 words of 29 bits
902  for(a[0] = 0, i = 0; i < 8; i++)
903  {
904  temp = LOAD32LE(data + i * 4);
905  a[i] |= (temp << (i * 3)) & 0x1FFFFFFF;
906  a[i + 1] = temp >> (29 - i * 3);
907  }
908 }
909 
910 
911 /**
912  * @brief Export an octet string
913  * @param[in] a Pointer to the integer to be exported
914  * @param[out] data Octet string resulting from the conversion
915  **/
916 
917 void curve25519Export(int32_t *a, uint8_t *data)
918 {
919  uint_t i;
920  uint32_t temp;
921 
922  //Unpack the 9 words of 29 bits
923  for(i = 0; i < 8; i++)
924  {
925  temp = (a[i + 1] << (29 - i * 3)) | (a[i] >> (i * 3));
926  STORE32LE(temp, data + i * 4);
927  }
928 }
929 
930 #endif
curve25519Add
void curve25519Add(int32_t *r, const int32_t *a, const int32_t *b)
Modular addition.
Definition: curve25519.c:79
curve25519Canonicalize
void curve25519Canonicalize(int32_t *r, const int32_t *a)
Reduce non-canonical value.
Definition: curve25519.c:749
b
uint8_t b
Definition: nbns_common.h:104
a
uint8_t a
Definition: ndp.h:411
int_t
signed int int_t
Definition: compiler_port.h:56
curve25519Export
void curve25519Export(int32_t *a, uint8_t *data)
Export an octet string.
Definition: curve25519.c:917
data
uint8_t data[]
Definition: ethernet.h:222
STORE32LE
#define STORE32LE(a, p)
Definition: cpu_endian.h:279
curve25519Select
void curve25519Select(int32_t *r, const int32_t *a, const int32_t *b, uint32_t c)
Select an integer.
Definition: curve25519.c:845
curve25519Sqrt
uint32_t curve25519Sqrt(int32_t *r, const int32_t *a, const int32_t *b)
Compute the square root of (A / B) modulo p.
Definition: curve25519.c:656
r
uint8_t r
Definition: ndp.h:346
curve25519Comp
uint32_t curve25519Comp(const int32_t *a, const int32_t *b)
Compare integers.
Definition: curve25519.c:870
crypto.h
General definitions for cryptographic algorithms.
curve25519Sqr
__weak_func void curve25519Sqr(int32_t *r, const int32_t *a)
Modular squaring.
Definition: curve25519.c:571
mask
uint8_t mask
Definition: web_socket.h:319
curve25519Copy
void curve25519Copy(int32_t *a, const int32_t *b)
Copy an integer.
Definition: curve25519.c:798
u
uint8_t u
Definition: lldp_ext_med.h:213
curve25519Swap
void curve25519Swap(int32_t *a, int32_t *b, uint32_t c)
Conditional swap.
Definition: curve25519.c:817
curve25519SetInt
void curve25519SetInt(int32_t *a, int32_t b)
Set integer value.
Definition: curve25519.c:57
curve25519Inv
void curve25519Inv(int32_t *r, const int32_t *a)
Modular multiplicative inverse.
Definition: curve25519.c:606
curve25519Sub
void curve25519Sub(int32_t *r, const int32_t *a, const int32_t *b)
Modular subtraction.
Definition: curve25519.c:173
n
uint8_t n
Definition: dhcpv6_common.h:416
curve25519.h
Curve25519 elliptic curve (constant-time implementation)
curve25519MulInt
void curve25519MulInt(int32_t *r, const int32_t *a, int32_t b)
Modular multiplication.
Definition: curve25519.c:499
curve25519AddInt
void curve25519AddInt(int32_t *r, const int32_t *a, int32_t b)
Modular addition.
Definition: curve25519.c:144
curve25519Import
void curve25519Import(int32_t *a, const uint8_t *data)
Import an octet string.
Definition: curve25519.c:896
curve25519Pwr2
void curve25519Pwr2(int32_t *r, const int32_t *a, uint_t n)
Raise an integer to power 2^n.
Definition: curve25519.c:585
LOAD32LE
#define LOAD32LE(p)
Definition: cpu_endian.h:203
curve25519Mul
__weak_func void curve25519Mul(int32_t *r, const int32_t *a, const int32_t *b)
Modular multiplication.
Definition: curve25519.c:267
uint_t
unsigned int uint_t
Definition: compiler_port.h:57
ec.h
ECC (Elliptic Curve Cryptography)
c
uint8_t c
Definition: ndp.h:514
debug.h
Debugging facilities.
curve25519SubInt
void curve25519SubInt(int32_t *r, const int32_t *a, int32_t b)
Modular subtraction.
Definition: curve25519.c:238