curve25519.c
Go to the documentation of this file.
1 /**
2  * @file curve25519.c
3  * @brief Curve25519 elliptic curve
4  *
5  * @section License
6  *
7  * SPDX-License-Identifier: GPL-2.0-or-later
8  *
9  * Copyright (C) 2010-2026 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.6.6
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  int32_t temp;
82 
83  //Compute R = A + B
84  temp = a[0] + b[0];
85  r[0] = temp & 0x1FFFFFFF;
86  temp = ASR32(temp, 29);
87  temp += a[1] + b[1];
88  r[1] = temp & 0x1FFFFFFF;
89  temp = ASR32(temp, 29);
90  temp += a[2] + b[2];
91  r[2] = temp & 0x1FFFFFFF;
92  temp = ASR32(temp, 29);
93  temp += a[3] + b[3];
94  r[3] = temp & 0x1FFFFFFF;
95  temp = ASR32(temp, 29);
96  temp += a[4] + b[4];
97  r[4] = temp & 0x1FFFFFFF;
98  temp = ASR32(temp, 29);
99  temp += a[5] + b[5];
100  r[5] = temp & 0x1FFFFFFF;
101  temp = ASR32(temp, 29);
102  temp += a[6] + b[6];
103  r[6] = temp & 0x1FFFFFFF;
104  temp = ASR32(temp, 29);
105  temp += a[7] + b[7];
106  r[7] = temp & 0x1FFFFFFF;
107  temp = ASR32(temp, 29);
108  temp += a[8] + b[8];
109  r[8] = temp & 0x007FFFFF;
110  temp = ASR32(temp, 23);
111 
112  //Perform modular reduction (2^255 = 19)
113  r[0] += temp * 19;
114 }
115 
116 
117 /**
118  * @brief Modular addition
119  * @param[out] r Resulting integer R = (A + B) mod p
120  * @param[in] a An integer such as 0 <= A < p
121  * @param[in] b An integer such as 0 <= B < (2^32 - 1)
122  **/
123 
124 void curve25519AddInt(int32_t *r, const int32_t *a, int32_t b)
125 {
126  uint_t i;
127  int32_t temp;
128 
129  //Compute R = A + B
130  for(temp = b, i = 0; i < 8; i++)
131  {
132  temp += a[i];
133  r[i] = temp & 0x1FFFFFFF;
134  temp = ASR32(temp, 29);
135  }
136 
137  temp += a[8];
138  r[8] = temp & 0x007FFFFF;
139  temp = ASR32(temp, 23);
140 
141  //Perform modular reduction (2^255 = 19)
142  r[0] += temp * 19;
143 }
144 
145 
146 /**
147  * @brief Modular subtraction
148  * @param[out] r Resulting integer R = (A - B) mod p
149  * @param[in] a An integer such as 0 <= A < p
150  * @param[in] b An integer such as 0 <= B < p
151  **/
152 
153 void curve25519Sub(int32_t *r, const int32_t *a, const int32_t *b)
154 {
155  int32_t temp;
156 
157  //Compute R = A - B
158  temp = a[0] - b[0];
159  r[0] = temp & 0x1FFFFFFF;
160  temp = ASR32(temp, 29);
161  temp += a[1] - b[1];
162  r[1] = temp & 0x1FFFFFFF;
163  temp = ASR32(temp, 29);
164  temp += a[2] - b[2];
165  r[2] = temp & 0x1FFFFFFF;
166  temp = ASR32(temp, 29);
167  temp += a[3] - b[3];
168  r[3] = temp & 0x1FFFFFFF;
169  temp = ASR32(temp, 29);
170  temp += a[4] - b[4];
171  r[4] = temp & 0x1FFFFFFF;
172  temp = ASR32(temp, 29);
173  temp += a[5] - b[5];
174  r[5] = temp & 0x1FFFFFFF;
175  temp = ASR32(temp, 29);
176  temp += a[6] - b[6];
177  r[6] = temp & 0x1FFFFFFF;
178  temp = ASR32(temp, 29);
179  temp += a[7] - b[7];
180  r[7] = temp & 0x1FFFFFFF;
181  temp = ASR32(temp, 29);
182  temp += a[8] - b[8];
183  r[8] = temp & 0x007FFFFF;
184  temp = ASR32(temp, 23);
185 
186  //Perform modular reduction
187  r[0] += temp * 19;
188 }
189 
190 
191 /**
192  * @brief Modular subtraction
193  * @param[out] r Resulting integer R = (A - B) mod p
194  * @param[in] a An integer such as 0 <= A < p
195  * @param[in] b An integer such as 0 <= B < (2^32 - 1)
196  **/
197 
198 void curve25519SubInt(int32_t *r, const int32_t *a, int32_t b)
199 {
200  uint_t i;
201  int32_t temp;
202 
203  //Compute R = A - B
204  for(temp = -b, i = 0; i < 8; i++)
205  {
206  temp += a[i];
207  r[i] = temp & 0x1FFFFFFF;
208  temp = ASR32(temp, 29);
209  }
210 
211  temp += a[8];
212  r[8] = temp & 0x007FFFFF;
213  temp = ASR32(temp, 23);
214 
215  //Perform modular reduction (2^255 = 19)
216  r[0] += temp * 19;
217 }
218 
219 
220 /**
221  * @brief Modular multiplication
222  * @param[out] r Resulting integer R = (A * B) mod p
223  * @param[in] a An integer such as 0 <= A < p
224  * @param[in] b An integer such as 0 <= B < p
225  **/
226 
227 __weak_func void curve25519Mul(int32_t *r, const int32_t *a, const int32_t *b)
228 {
229  int64_t temp;
230  int32_t u[18];
231 
232  //Compute R = A * B
233  temp = (int64_t) a[0] * b[0];
234  u[0] = temp & 0x1FFFFFFF;
235  temp = ASR64(temp, 29);
236  temp += (int64_t) a[0] * b[1];
237  temp += (int64_t) a[1] * b[0];
238  u[1] = temp & 0x1FFFFFFF;
239  temp = ASR64(temp, 29);
240  temp += (int64_t) a[0] * b[2];
241  temp += (int64_t) a[1] * b[1];
242  temp += (int64_t) a[2] * b[0];
243  u[2] = temp & 0x1FFFFFFF;
244  temp = ASR64(temp, 29);
245  temp += (int64_t) a[0] * b[3];
246  temp += (int64_t) a[1] * b[2];
247  temp += (int64_t) a[2] * b[1];
248  temp += (int64_t) a[3] * b[0];
249  u[3] = temp & 0x1FFFFFFF;
250  temp = ASR64(temp, 29);
251  temp += (int64_t) a[0] * b[4];
252  temp += (int64_t) a[1] * b[3];
253  temp += (int64_t) a[2] * b[2];
254  temp += (int64_t) a[3] * b[1];
255  temp += (int64_t) a[4] * b[0];
256  u[4] = temp & 0x1FFFFFFF;
257  temp = ASR64(temp, 29);
258  temp += (int64_t) a[0] * b[5];
259  temp += (int64_t) a[1] * b[4];
260  temp += (int64_t) a[2] * b[3];
261  temp += (int64_t) a[3] * b[2];
262  temp += (int64_t) a[4] * b[1];
263  temp += (int64_t) a[5] * b[0];
264  u[5] = temp & 0x1FFFFFFF;
265  temp = ASR64(temp, 29);
266  temp += (int64_t) a[0] * b[6];
267  temp += (int64_t) a[1] * b[5];
268  temp += (int64_t) a[2] * b[4];
269  temp += (int64_t) a[3] * b[3];
270  temp += (int64_t) a[4] * b[2];
271  temp += (int64_t) a[5] * b[1];
272  temp += (int64_t) a[6] * b[0];
273  u[6] = temp & 0x1FFFFFFF;
274  temp = ASR64(temp, 29);
275  temp += (int64_t) a[0] * b[7];
276  temp += (int64_t) a[1] * b[6];
277  temp += (int64_t) a[2] * b[5];
278  temp += (int64_t) a[3] * b[4];
279  temp += (int64_t) a[4] * b[3];
280  temp += (int64_t) a[5] * b[2];
281  temp += (int64_t) a[6] * b[1];
282  temp += (int64_t) a[7] * b[0];
283  u[7] = temp & 0x1FFFFFFF;
284  temp = ASR64(temp, 29);
285  temp += (int64_t) a[0] * b[8];
286  temp += (int64_t) a[1] * b[7];
287  temp += (int64_t) a[2] * b[6];
288  temp += (int64_t) a[3] * b[5];
289  temp += (int64_t) a[4] * b[4];
290  temp += (int64_t) a[5] * b[3];
291  temp += (int64_t) a[6] * b[2];
292  temp += (int64_t) a[7] * b[1];
293  temp += (int64_t) a[8] * b[0];
294  u[8] = temp & 0x1FFFFFFF;
295  temp = ASR64(temp, 29);
296  temp += (int64_t) a[1] * b[8];
297  temp += (int64_t) a[2] * b[7];
298  temp += (int64_t) a[3] * b[6];
299  temp += (int64_t) a[4] * b[5];
300  temp += (int64_t) a[5] * b[4];
301  temp += (int64_t) a[6] * b[3];
302  temp += (int64_t) a[7] * b[2];
303  temp += (int64_t) a[8] * b[1];
304  u[9] = temp & 0x1FFFFFFF;
305  temp = ASR64(temp, 29);
306  temp += (int64_t) a[2] * b[8];
307  temp += (int64_t) a[3] * b[7];
308  temp += (int64_t) a[4] * b[6];
309  temp += (int64_t) a[5] * b[5];
310  temp += (int64_t) a[6] * b[4];
311  temp += (int64_t) a[7] * b[3];
312  temp += (int64_t) a[8] * b[2];
313  u[10] = temp & 0x1FFFFFFF;
314  temp = ASR64(temp, 29);
315  temp += (int64_t) a[3] * b[8];
316  temp += (int64_t) a[4] * b[7];
317  temp += (int64_t) a[5] * b[6];
318  temp += (int64_t) a[6] * b[5];
319  temp += (int64_t) a[7] * b[4];
320  temp += (int64_t) a[8] * b[3];
321  u[11] = temp & 0x1FFFFFFF;
322  temp = ASR64(temp, 29);
323  temp += (int64_t) a[4] * b[8];
324  temp += (int64_t) a[5] * b[7];
325  temp += (int64_t) a[6] * b[6];
326  temp += (int64_t) a[7] * b[5];
327  temp += (int64_t) a[8] * b[4];
328  u[12] = temp & 0x1FFFFFFF;
329  temp = ASR64(temp, 29);
330  temp += (int64_t) a[5] * b[8];
331  temp += (int64_t) a[6] * b[7];
332  temp += (int64_t) a[7] * b[6];
333  temp += (int64_t) a[8] * b[5];
334  u[13] = temp & 0x1FFFFFFF;
335  temp = ASR64(temp, 29);
336  temp += (int64_t) a[6] * b[8];
337  temp += (int64_t) a[7] * b[7];
338  temp += (int64_t) a[8] * b[6];
339  u[14] = temp & 0x1FFFFFFF;
340  temp = ASR64(temp, 29);
341  temp += (int64_t) a[7] * b[8];
342  temp += (int64_t) a[8] * b[7];
343  u[15] = temp & 0x1FFFFFFF;
344  temp = ASR64(temp, 29);
345  temp += (int64_t) a[8] * b[8];
346  u[16] = temp & 0x1FFFFFFF;
347  temp = ASR64(temp, 29);
348  u[17] = temp & 0xFFFFFFFF;
349 
350  //Perform modular reduction (first pass)
351  temp = u[0];
352  temp += (int64_t) u[9] * 1216;
353  r[0] = temp & 0x1FFFFFFF;
354  temp = ASR64(temp, 29);
355  temp += u[1];
356  temp += (int64_t) u[10] * 1216;
357  r[1] = temp & 0x1FFFFFFF;
358  temp = ASR64(temp, 29);
359  temp += u[2];
360  temp += (int64_t) u[11] * 1216;
361  r[2] = temp & 0x1FFFFFFF;
362  temp = ASR64(temp, 29);
363  temp += u[3];
364  temp += (int64_t) u[12] * 1216;
365  r[3] = temp & 0x1FFFFFFF;
366  temp = ASR64(temp, 29);
367  temp += u[4];
368  temp += (int64_t) u[13] * 1216;
369  r[4] = temp & 0x1FFFFFFF;
370  temp = ASR64(temp, 29);
371  temp += u[5];
372  temp += (int64_t) u[14] * 1216;
373  r[5] = temp & 0x1FFFFFFF;
374  temp = ASR64(temp, 29);
375  temp += u[6];
376  temp += (int64_t) u[15] * 1216;
377  r[6] = temp & 0x1FFFFFFF;
378  temp = ASR64(temp, 29);
379  temp += u[7];
380  temp += (int64_t) u[16] * 1216;
381  r[7] = temp & 0x1FFFFFFF;
382  temp = ASR64(temp, 29);
383  temp += u[8];
384  temp += (int64_t) u[17] * 1216;
385  r[8] = temp & 0x007FFFFF;
386  temp = ASR64(temp, 23);
387 
388  //Perform modular reduction (second pass)
389  temp *= 19;
390  temp += r[0];
391  r[0] = temp & 0x1FFFFFFF;
392  temp = ASR64(temp, 29);
393  r[1] += temp & 0xFFFFFFFF;
394 }
395 
396 
397 /**
398  * @brief Modular multiplication
399  * @param[out] r Resulting integer R = (A * B) mod p
400  * @param[in] a An integer such as 0 <= A < p
401  * @param[in] b An integer such as 0 <= B < (2^29 - 1)
402  **/
403 
404 __weak_func void curve25519MulInt(int32_t *r, const int32_t *a, int32_t b)
405 {
406  int64_t temp;
407 
408  //Compute R = A * B
409  temp = (int64_t) a[0] * b;
410  r[0] = temp & 0x1FFFFFFF;
411  temp = ASR64(temp, 29);
412  temp += (int64_t) a[1] * b;
413  r[1] = temp & 0x1FFFFFFF;
414  temp = ASR64(temp, 29);
415  temp += (int64_t) a[2] * b;
416  r[2] = temp & 0x1FFFFFFF;
417  temp = ASR64(temp, 29);
418  temp += (int64_t) a[3] * b;
419  r[3] = temp & 0x1FFFFFFF;
420  temp = ASR64(temp, 29);
421  temp += (int64_t) a[4] * b;
422  r[4] = temp & 0x1FFFFFFF;
423  temp = ASR64(temp, 29);
424  temp += (int64_t) a[5] * b;
425  r[5] = temp & 0x1FFFFFFF;
426  temp = ASR64(temp, 29);
427  temp += (int64_t) a[6] * b;
428  r[6] = temp & 0x1FFFFFFF;
429  temp = ASR64(temp, 29);
430  temp += (int64_t) a[7] * b;
431  r[7] = temp & 0x1FFFFFFF;
432  temp = ASR64(temp, 29);
433  temp += (int64_t) a[8] * b;
434  r[8] = temp & 0x007FFFFF;
435  temp = ASR64(temp, 23);
436 
437  //Perform modular reduction (2^255 = 19)
438  temp *= 19;
439  temp += r[0];
440  r[0] = temp & 0x1FFFFFFF;
441  temp = ASR64(temp, 29);
442  r[1] += temp & 0xFFFFFFFF;
443 }
444 
445 
446 /**
447  * @brief Modular squaring
448  * @param[out] r Resulting integer R = (A ^ 2) mod p
449  * @param[in] a An integer such as 0 <= A < p
450  **/
451 
452 __weak_func void curve25519Sqr(int32_t *r, const int32_t *a)
453 {
454  //Compute R = (A ^ 2) mod p
455  curve25519Mul(r, a, a);
456 }
457 
458 
459 /**
460  * @brief Raise an integer to power 2^n
461  * @param[out] r Resulting integer R = (A ^ (2^n)) mod p
462  * @param[in] a An integer such as 0 <= A < p
463  * @param[in] n An integer such as n >= 1
464  **/
465 
466 void curve25519Pwr2(int32_t *r, const int32_t *a, uint_t n)
467 {
468  uint_t i;
469 
470  //Pre-compute (A ^ 2) mod p
471  curve25519Sqr(r, a);
472 
473  //Compute R = (A ^ (2^n)) mod p
474  for(i = 1; i < n; i++)
475  {
476  curve25519Sqr(r, r);
477  }
478 }
479 
480 
481 /**
482  * @brief Modular multiplicative inverse
483  * @param[out] r Resulting integer R = A^-1 mod p
484  * @param[in] a An integer such as 0 <= A < p
485  **/
486 
487 void curve25519Inv(int32_t *r, const int32_t *a)
488 {
489  int32_t u[9];
490  int32_t v[9];
491 
492  //Since GF(p) is a prime field, the Fermat's little theorem can be
493  //used to find the multiplicative inverse of A modulo p
494  curve25519Sqr(u, a);
495  curve25519Mul(u, u, a); //A^(2^2 - 1)
496  curve25519Sqr(u, u);
497  curve25519Mul(v, u, a); //A^(2^3 - 1)
498  curve25519Pwr2(u, v, 3);
499  curve25519Mul(u, u, v); //A^(2^6 - 1)
500  curve25519Sqr(u, u);
501  curve25519Mul(v, u, a); //A^(2^7 - 1)
502  curve25519Pwr2(u, v, 7);
503  curve25519Mul(u, u, v); //A^(2^14 - 1)
504  curve25519Sqr(u, u);
505  curve25519Mul(v, u, a); //A^(2^15 - 1)
506  curve25519Pwr2(u, v, 15);
507  curve25519Mul(u, u, v); //A^(2^30 - 1)
508  curve25519Sqr(u, u);
509  curve25519Mul(v, u, a); //A^(2^31 - 1)
510  curve25519Pwr2(u, v, 31);
511  curve25519Mul(v, u, v); //A^(2^62 - 1)
512  curve25519Pwr2(u, v, 62);
513  curve25519Mul(u, u, v); //A^(2^124 - 1)
514  curve25519Sqr(u, u);
515  curve25519Mul(v, u, a); //A^(2^125 - 1)
516  curve25519Pwr2(u, v, 125);
517  curve25519Mul(u, u, v); //A^(2^250 - 1)
518  curve25519Sqr(u, u);
519  curve25519Sqr(u, u);
520  curve25519Mul(u, u, a); //A^(2^252 - 3)
521  curve25519Sqr(u, u);
522  curve25519Sqr(u, u);
523  curve25519Mul(u, u, a); //A^(2^254 - 11)
524  curve25519Sqr(u, u);
525  curve25519Mul(r, u, a); //A^(2^255 - 21)
526 }
527 
528 
529 /**
530  * @brief Compute the square root of (A / B) modulo p
531  * @param[out] r Resulting integer R = (A / B)^(1 / 2) mod p
532  * @param[in] a An integer such as 0 <= A < p
533  * @param[in] b An integer such as 0 < B < p
534  * @return The function returns 0 if the square root exists, else 1
535  **/
536 
537 uint32_t curve25519Sqrt(int32_t *r, const int32_t *a, const int32_t *b)
538 {
539  uint32_t res1;
540  uint32_t res2;
541  int32_t c[9];
542  int32_t u[9];
543  int32_t v[9];
544  int32_t w[9];
545 
546  //Compute the candidate root (A / B)^((p + 3) / 8). This can be done
547  //with the following trick, using a single modular powering for both the
548  //inversion of B and the square root: A * B^3 * (A * B^7)^((p - 5) / 8)
549  curve25519Sqr(v, b);
550  curve25519Mul(v, v, b);
551  curve25519Sqr(v, v);
552  curve25519Mul(v, v, b);
553 
554  //Compute C = A * B^7
555  curve25519Mul(c, a, v);
556 
557  //Compute U = C^((p - 5) / 8)
558  curve25519Sqr(u, c);
559  curve25519Mul(u, u, c); //C^(2^2 - 1)
560  curve25519Sqr(u, u);
561  curve25519Mul(v, u, c); //C^(2^3 - 1)
562  curve25519Pwr2(u, v, 3);
563  curve25519Mul(u, u, v); //C^(2^6 - 1)
564  curve25519Sqr(u, u);
565  curve25519Mul(v, u, c); //C^(2^7 - 1)
566  curve25519Pwr2(u, v, 7);
567  curve25519Mul(u, u, v); //C^(2^14 - 1)
568  curve25519Sqr(u, u);
569  curve25519Mul(v, u, c); //C^(2^15 - 1)
570  curve25519Pwr2(u, v, 15);
571  curve25519Mul(u, u, v); //C^(2^30 - 1)
572  curve25519Sqr(u, u);
573  curve25519Mul(v, u, c); //C^(2^31 - 1)
574  curve25519Pwr2(u, v, 31);
575  curve25519Mul(v, u, v); //C^(2^62 - 1)
576  curve25519Pwr2(u, v, 62);
577  curve25519Mul(u, u, v); //C^(2^124 - 1)
578  curve25519Sqr(u, u);
579  curve25519Mul(v, u, c); //C^(2^125 - 1)
580  curve25519Pwr2(u, v, 125);
581  curve25519Mul(u, u, v); //C^(2^250 - 1)
582  curve25519Sqr(u, u);
583  curve25519Sqr(u, u);
584  curve25519Mul(u, u, c); //C^(2^252 - 3)
585 
586  //The first candidate root is U = A * B^3 * (A * B^7)^((p - 5) / 8)
587  curve25519Mul(u, u, a);
588  curve25519Sqr(v, b);
589  curve25519Mul(v, v, b);
590  curve25519Mul(u, u, v);
591  curve25519Canonicalize(u, u);
592 
593  //The second candidate root is V = U * sqrt(-1)
594  curve25519Mul(v, u, CURVE25519_SQRT_MINUS_1);
595  curve25519Canonicalize(v, v);
596 
597  //Reduce non-canonical values of A
598  curve25519Canonicalize(w, a);
599 
600  //Calculate C = B * U^2
601  curve25519Sqr(c, u);
602  curve25519Mul(c, c, b);
603  curve25519Canonicalize(c, c);
604 
605  //Check whether B * U^2 = A
606  res1 = curve25519Comp(c, w);
607 
608  //Calculate C = B * V^2
609  curve25519Sqr(c, v);
610  curve25519Mul(c, c, b);
611  curve25519Canonicalize(c, c);
612 
613  //Check whether B * V^2 = A
614  res2 = curve25519Comp(c, w);
615 
616  //Select the first or the second candidate root
617  curve25519Select(r, u, v, res1);
618 
619  //Return 0 if the square root exists
620  return res1 & res2;
621 }
622 
623 
624 /**
625  * @brief Reduce non-canonical value
626  * @param[out] r Resulting integer R = A mod p
627  * @param[in] a An integer such as 0 <= A < (2^255 - 1)
628  **/
629 
630 void curve25519Canonicalize(int32_t *r, const int32_t *a)
631 {
632  uint_t i;
633  int32_t temp;
634  int32_t b[9];
635 
636  //Perform modular reduction (first pass)
637  for(temp = 0, i = 0; i < 8; i++)
638  {
639  temp += a[i];
640  r[i] = temp & 0x1FFFFFFF;
641  temp = ASR32(temp, 29);
642  }
643 
644  temp += a[8];
645  r[8] = temp & 0x007FFFFF;
646  temp = ASR32(temp, 23);
647 
648  //Perform modular reduction (second pass)
649  for(temp *= 19, i = 0; i < 9; i++)
650  {
651  temp += r[i];
652  r[i] = temp & 0x1FFFFFFF;
653  temp = ASR32(temp, 29);
654  }
655 
656  //Compute B = A + 19
657  for(temp = 19, i = 0; i < 9; i++)
658  {
659  temp += r[i];
660  b[i] = temp & 0x1FFFFFFF;
661  temp = ASR32(temp, 29);
662  }
663 
664  //Compute B = A - (2^255 - 19)
665  b[8] -= 0x00800000;
666  b[8] &= 0x00FFFFFF;
667 
668  //If B < (2^255 - 19) then R = B, else R = A
669  curve25519Select(r, b, r, (b[8] & 0x00800000) >> 23);
670 }
671 
672 
673 /**
674  * @brief Copy an integer
675  * @param[out] a Pointer to the destination integer
676  * @param[in] b Pointer to the source integer
677  **/
678 
679 void curve25519Copy(int32_t *a, const int32_t *b)
680 {
681  uint_t i;
682 
683  //Copy the value of the integer
684  for(i = 0; i < 9; i++)
685  {
686  a[i] = b[i];
687  }
688 }
689 
690 
691 /**
692  * @brief Conditional swap
693  * @param[in,out] a Pointer to the first integer
694  * @param[in,out] b Pointer to the second integer
695  * @param[in] c Condition variable
696  **/
697 
698 void curve25519Swap(int32_t *a, int32_t *b, uint32_t c)
699 {
700  uint_t i;
701  uint32_t mask;
702  uint32_t dummy;
703 
704  //The mask is the all-1 or all-0 word
705  mask = ~c + 1;
706 
707  //Conditional swap
708  for(i = 0; i < 9; i++)
709  {
710  //Constant time implementation
711  dummy = mask & (a[i] ^ b[i]);
712  a[i] ^= dummy;
713  b[i] ^= dummy;
714  }
715 }
716 
717 
718 /**
719  * @brief Select an integer
720  * @param[out] r Pointer to the destination integer
721  * @param[in] a Pointer to the first source integer
722  * @param[in] b Pointer to the second source integer
723  * @param[in] c Condition variable
724  **/
725 
726 void curve25519Select(int32_t *r, const int32_t *a, const int32_t *b,
727  uint32_t c)
728 {
729  uint_t i;
730  uint32_t mask;
731 
732  //The mask is the all-1 or all-0 word
733  mask = c - 1;
734 
735  //Select between A and B
736  for(i = 0; i < 9; i++)
737  {
738  //Constant time implementation
739  r[i] = (a[i] & mask) | (b[i] & ~mask);
740  }
741 }
742 
743 
744 /**
745  * @brief Compare integers
746  * @param[in] a Pointer to the first integer
747  * @param[in] b Pointer to the second integer
748  * @return The function returns 0 if the A = B, else 1
749  **/
750 
751 uint32_t curve25519Comp(const int32_t *a, const int32_t *b)
752 {
753  uint_t i;
754  uint32_t mask;
755 
756  //Initialize mask
757  mask = 0;
758 
759  //Compare A and B
760  for(i = 0; i < 9; i++)
761  {
762  //Constant time implementation
763  mask |= a[i] ^ b[i];
764  }
765 
766  //Return 0 if A = B, else 1
767  return ((uint32_t) (mask | (~mask + 1))) >> 31;
768 }
769 
770 
771 /**
772  * @brief Import an octet string
773  * @param[out] a Pointer to resulting integer
774  * @param[in] data Octet string to be converted
775  **/
776 
777 void curve25519Import(int32_t *a, const uint8_t *data)
778 {
779  uint_t i;
780  uint32_t temp;
781 
782  //Pack the octet string into 9 words of 29 bits
783  for(a[0] = 0, i = 0; i < 8; i++)
784  {
785  temp = LOAD32LE(data + i * 4);
786  a[i] |= (temp << (i * 3)) & 0x1FFFFFFF;
787  a[i + 1] = temp >> (29 - i * 3);
788  }
789 }
790 
791 
792 /**
793  * @brief Export an octet string
794  * @param[in] a Pointer to the integer to be exported
795  * @param[out] data Octet string resulting from the conversion
796  **/
797 
798 void curve25519Export(int32_t *a, uint8_t *data)
799 {
800  uint_t i;
801  uint32_t temp;
802 
803  //Unpack the 9 words of 29 bits
804  for(i = 0; i < 8; i++)
805  {
806  temp = (a[i + 1] << (29 - i * 3)) | (a[i] >> (i * 3));
807  STORE32LE(temp, data + i * 4);
808  }
809 }
810 
811 #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:630
b
uint8_t b
Definition: nbns_common.h:122
a
uint8_t a
Definition: ndp.h:411
curve25519Export
void curve25519Export(int32_t *a, uint8_t *data)
Export an octet string.
Definition: curve25519.c:798
data
uint8_t data[]
Definition: ethernet.h:224
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:726
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:537
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:751
crypto.h
General definitions for cryptographic algorithms.
curve25519Sqr
__weak_func void curve25519Sqr(int32_t *r, const int32_t *a)
Modular squaring.
Definition: curve25519.c:452
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:679
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:698
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:487
curve25519Sub
void curve25519Sub(int32_t *r, const int32_t *a, const int32_t *b)
Modular subtraction.
Definition: curve25519.c:153
n
uint8_t n
Definition: dhcpv6_common.h:416
curve25519.h
Curve25519 elliptic curve.
ASR64
#define ASR64(a, n)
Definition: crypto.h:1017
curve25519AddInt
void curve25519AddInt(int32_t *r, const int32_t *a, int32_t b)
Modular addition.
Definition: curve25519.c:124
curve25519MulInt
__weak_func void curve25519MulInt(int32_t *r, const int32_t *a, int32_t b)
Modular multiplication.
Definition: curve25519.c:404
curve25519Import
void curve25519Import(int32_t *a, const uint8_t *data)
Import an octet string.
Definition: curve25519.c:777
curve25519Pwr2
void curve25519Pwr2(int32_t *r, const int32_t *a, uint_t n)
Raise an integer to power 2^n.
Definition: curve25519.c:466
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:227
uint_t
unsigned int uint_t
Definition: compiler_port.h:57
ec.h
ECC (Elliptic Curve Cryptography)
ASR32
#define ASR32(a, n)
Definition: crypto.h:1013
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:198