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-2019 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 1.9.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_curves.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 uint32_t CURVE25519_SQRT_MINUS_1[8] =
45 {
46  0x4A0EA0B0, 0xC4EE1B27, 0xAD2FE478, 0x2F431806,
47  0x3DFBD7A7, 0x2B4D0099, 0x4FC1DF0B, 0x2B832480
48 };
49 
50 
51 /**
52  * @brief Set integer value
53  * @param[out] a Pointer to the integer to be initialized
54  * @param[in] b Initial value
55  **/
56 
57 void curve25519SetInt(uint32_t *a, uint32_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 < 8; 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(uint32_t *r, const uint32_t *a, const uint32_t *b)
80 {
81  uint_t i;
82  uint64_t temp;
83 
84  //Compute R = A + B
85  for(temp = 0, i = 0; i < 8; i++)
86  {
87  temp += a[i];
88  temp += b[i];
89  r[i] = temp & 0xFFFFFFFF;
90  temp >>= 32;
91  }
92 
93  //Perform modular reduction
94  curve25519Red(r, r);
95 }
96 
97 
98 /**
99  * @brief Modular addition
100  * @param[out] r Resulting integer R = (A + B) mod p
101  * @param[in] a An integer such as 0 <= A < p
102  * @param[in] b An integer such as 0 <= B < (2^32 - 1)
103  **/
104 
105 void curve25519AddInt(uint32_t *r, const uint32_t *a, uint32_t b)
106 {
107  uint_t i;
108  uint64_t temp;
109 
110  //Compute R = A + B
111  for(temp = b, i = 0; i < 8; i++)
112  {
113  temp += a[i];
114  r[i] = temp & 0xFFFFFFFF;
115  temp >>= 32;
116  }
117 
118  //Perform modular reduction
119  curve25519Red(r, r);
120 }
121 
122 
123 /**
124  * @brief Modular subtraction
125  * @param[out] r Resulting integer R = (A - B) mod p
126  * @param[in] a An integer such as 0 <= A < p
127  * @param[in] b An integer such as 0 <= B < p
128  **/
129 
130 void curve25519Sub(uint32_t *r, const uint32_t *a, const uint32_t *b)
131 {
132  uint_t i;
133  int64_t temp;
134 
135  //Compute R = A - 19 - B
136  for(temp = -19, i = 0; i < 8; i++)
137  {
138  temp += a[i];
139  temp -= b[i];
140  r[i] = temp & 0xFFFFFFFF;
141  temp >>= 32;
142  }
143 
144  //Compute R = A + (2^255 - 19) - B
145  r[7] += 0x80000000;
146 
147  //Perform modular reduction
148  curve25519Red(r, r);
149 }
150 
151 
152 /**
153  * @brief Modular subtraction
154  * @param[out] r Resulting integer R = (A - B) mod p
155  * @param[in] a An integer such as 0 <= A < p
156  * @param[in] b An integer such as 0 <= B < (2^32 - 1)
157  **/
158 
159 void curve25519SubInt(uint32_t *r, const uint32_t *a, uint32_t b)
160 {
161  uint_t i;
162  int64_t temp;
163 
164  //Set initial value
165  temp = -19;
166  temp -= b;
167 
168  //Compute R = A - 19 - B
169  for(i = 0; i < 8; i++)
170  {
171  temp += a[i];
172  r[i] = temp & 0xFFFFFFFF;
173  temp >>= 32;
174  }
175 
176  //Compute R = A + (2^255 - 19) - B
177  r[7] += 0x80000000;
178 
179  //Perform modular reduction
180  curve25519Red(r, r);
181 }
182 
183 
184 /**
185  * @brief Modular multiplication
186  * @param[out] r Resulting integer R = (A * B) mod p
187  * @param[in] a An integer such as 0 <= A < p
188  * @param[in] b An integer such as 0 <= B < p
189  **/
190 
191 void curve25519Mul(uint32_t *r, const uint32_t *a, const uint32_t *b)
192 {
193  uint_t i;
194  uint_t j;
195  uint64_t c;
196  uint64_t temp;
197  uint32_t u[16];
198 
199  //Initialize variables
200  temp = 0;
201  c = 0;
202 
203  //Comba's method is used to perform multiplication
204  for(i = 0; i < 16; i++)
205  {
206  //The algorithm computes the products, column by column
207  if(i < 8)
208  {
209  //Inner loop
210  for(j = 0; j <= i; j++)
211  {
212  temp += (uint64_t) a[j] * b[i - j];
213  c += temp >> 32;
214  temp &= 0xFFFFFFFF;
215  }
216  }
217  else
218  {
219  //Inner loop
220  for(j = i - 7; j < 8; j++)
221  {
222  temp += (uint64_t) a[j] * b[i - j];
223  c += temp >> 32;
224  temp &= 0xFFFFFFFF;
225  }
226  }
227 
228  //At the bottom of each column, the final result is written to memory
229  u[i] = temp & 0xFFFFFFFF;
230 
231  //Propagate the carry upwards
232  temp = c & 0xFFFFFFFF;
233  c >>= 32;
234  }
235 
236  //Reduce bit 255 (2^255 = 19 mod p)
237  temp = (u[7] >> 31) * 19;
238  //Mask the most significant bit
239  u[7] &= 0x7FFFFFFF;
240 
241  //Perform fast modular reduction (first pass)
242  for(i = 0; i < 8; i++)
243  {
244  temp += u[i];
245  temp += (uint64_t) u[i + 8] * 38;
246  u[i] = temp & 0xFFFFFFFF;
247  temp >>= 32;
248  }
249 
250  //Reduce bit 256 (2^256 = 38 mod p)
251  temp *= 38;
252  //Reduce bit 255 (2^255 = 19 mod p)
253  temp += (u[7] >> 31) * 19;
254  //Mask the most significant bit
255  u[7] &= 0x7FFFFFFF;
256 
257  //Perform fast modular reduction (second pass)
258  for(i = 0; i < 8; i++)
259  {
260  temp += u[i];
261  u[i] = temp & 0xFFFFFFFF;
262  temp >>= 32;
263  }
264 
265  //Reduce non-canonical values
266  curve25519Red(r, u);
267 }
268 
269 
270 /**
271  * @brief Modular multiplication
272  * @param[out] r Resulting integer R = (A * B) mod p
273  * @param[in] a An integer such as 0 <= A < p
274  * @param[in] b An integer such as 0 <= B < (2^32 - 1)
275  **/
276 
277 void curve25519MulInt(uint32_t *r, const uint32_t *a, uint32_t b)
278 {
279  int_t i;
280  uint64_t temp;
281  uint32_t u[8];
282 
283  //Compute R = A * B
284  for(temp = 0, i = 0; i < 8; i++)
285  {
286  temp += (uint64_t) a[i] * b;
287  u[i] = temp & 0xFFFFFFFF;
288  temp >>= 32;
289  }
290 
291  //Reduce bit 256 (2^256 = 38 mod p)
292  temp *= 38;
293  //Reduce bit 255 (2^255 = 19 mod p)
294  temp += (u[7] >> 31) * 19;
295  //Mask the most significant bit
296  u[7] &= 0x7FFFFFFF;
297 
298  //Perform fast modular reduction
299  for(i = 0; i < 8; i++)
300  {
301  temp += u[i];
302  u[i] = temp & 0xFFFFFFFF;
303  temp >>= 32;
304  }
305 
306  //Reduce non-canonical values
307  curve25519Red(r, u);
308 }
309 
310 
311 /**
312  * @brief Modular squaring
313  * @param[out] r Resulting integer R = (A ^ 2) mod p
314  * @param[in] a An integer such as 0 <= A < p
315  **/
316 
317 void curve25519Sqr(uint32_t *r, const uint32_t *a)
318 {
319  //Compute R = (A ^ 2) mod p
320  curve25519Mul(r, a, a);
321 }
322 
323 
324 /**
325  * @brief Raise an integer to power 2^n
326  * @param[out] r Resulting integer R = (A ^ (2^n)) mod p
327  * @param[in] a An integer such as 0 <= A < p
328  * @param[in] n An integer such as n >= 1
329  **/
330 
331 void curve25519Pwr2(uint32_t *r, const uint32_t *a, uint_t n)
332 {
333  uint_t i;
334 
335  //Pre-compute (A ^ 2) mod p
336  curve25519Sqr(r, a);
337 
338  //Compute R = (A ^ (2^n)) mod p
339  for(i = 1; i < n; i++)
340  {
341  curve25519Sqr(r, r);
342  }
343 }
344 
345 
346 /**
347  * @brief Modular reduction
348  * @param[out] r Resulting integer R = A mod p
349  * @param[in] a An integer such as 0 <= A < (2 * p)
350  **/
351 
352 void curve25519Red(uint32_t *r, const uint32_t *a)
353 {
354  uint_t i;
355  uint64_t temp;
356  uint32_t b[8];
357 
358  //Compute B = A + 19
359  for(temp = 19, i = 0; i < 8; i++)
360  {
361  temp += a[i];
362  b[i] = temp & 0xFFFFFFFF;
363  temp >>= 32;
364  }
365 
366  //Compute B = A - (2^255 - 19)
367  b[7] -= 0x80000000;
368 
369  //If B < (2^255 - 19) then R = B, else R = A
370  curve25519Select(r, b, a, (b[7] & 0x80000000) >> 31);
371 }
372 
373 
374 /**
375  * @brief Modular multiplicative inverse
376  * @param[out] r Resulting integer R = A^-1 mod p
377  * @param[in] a An integer such as 0 <= A < p
378  **/
379 
380 void curve25519Inv(uint32_t *r, const uint32_t *a)
381 {
382  uint32_t u[8];
383  uint32_t v[8];
384 
385  //Since GF(p) is a prime field, the Fermat's little theorem can be
386  //used to find the multiplicative inverse of A modulo p
387  curve25519Sqr(u, a);
388  curve25519Mul(u, u, a); //A^(2^2 - 1)
389  curve25519Sqr(u, u);
390  curve25519Mul(v, u, a); //A^(2^3 - 1)
391  curve25519Pwr2(u, v, 3);
392  curve25519Mul(u, u, v); //A^(2^6 - 1)
393  curve25519Sqr(u, u);
394  curve25519Mul(v, u, a); //A^(2^7 - 1)
395  curve25519Pwr2(u, v, 7);
396  curve25519Mul(u, u, v); //A^(2^14 - 1)
397  curve25519Sqr(u, u);
398  curve25519Mul(v, u, a); //A^(2^15 - 1)
399  curve25519Pwr2(u, v, 15);
400  curve25519Mul(u, u, v); //A^(2^30 - 1)
401  curve25519Sqr(u, u);
402  curve25519Mul(v, u, a); //A^(2^31 - 1)
403  curve25519Pwr2(u, v, 31);
404  curve25519Mul(v, u, v); //A^(2^62 - 1)
405  curve25519Pwr2(u, v, 62);
406  curve25519Mul(u, u, v); //A^(2^124 - 1)
407  curve25519Sqr(u, u);
408  curve25519Mul(v, u, a); //A^(2^125 - 1)
409  curve25519Pwr2(u, v, 125);
410  curve25519Mul(u, u, v); //A^(2^250 - 1)
411  curve25519Sqr(u, u);
412  curve25519Sqr(u, u);
413  curve25519Mul(u, u, a);
414  curve25519Sqr(u, u);
415  curve25519Sqr(u, u);
416  curve25519Mul(u, u, a);
417  curve25519Sqr(u, u);
418  curve25519Mul(r, u, a); //A^(2^255 - 21)
419 }
420 
421 
422 /**
423  * @brief Compute the square root of (A / B) modulo p
424  * @param[out] r Resulting integer R = (A / B)^(1 / 2) mod p
425  * @param[in] a An integer such as 0 <= A < p
426  * @param[in] b An integer such as 0 < B < p
427  * @return The function returns 0 if the square root exists, else 1
428  **/
429 
430 uint32_t curve25519Sqrt(uint32_t *r, const uint32_t *a, const uint32_t *b)
431 {
432  uint32_t res1;
433  uint32_t res2;
434  uint32_t c[8];
435  uint32_t u[8];
436  uint32_t v[8];
437 
438  //Compute the candidate root (A / B)^((p + 3) / 8). This can be done
439  //with the following trick, using a single modular powering for both the
440  //inversion of B and the square root: A * B^3 * (A * B^7)^((p - 5) / 8)
441  curve25519Sqr(v, b);
442  curve25519Mul(v, v, b);
443  curve25519Sqr(v, v);
444  curve25519Mul(v, v, b);
445 
446  //Compute C = A * B^7
447  curve25519Mul(c, a, v);
448 
449  //Compute U = C^((p - 5) / 8)
450  curve25519Sqr(u, c);
451  curve25519Mul(u, u, c); //C^(2^2 - 1)
452  curve25519Sqr(u, u);
453  curve25519Mul(v, u, c); //C^(2^3 - 1)
454  curve25519Pwr2(u, v, 3);
455  curve25519Mul(u, u, v); //C^(2^6 - 1)
456  curve25519Sqr(u, u);
457  curve25519Mul(v, u, c); //C^(2^7 - 1)
458  curve25519Pwr2(u, v, 7);
459  curve25519Mul(u, u, v); //C^(2^14 - 1)
460  curve25519Sqr(u, u);
461  curve25519Mul(v, u, c); //C^(2^15 - 1)
462  curve25519Pwr2(u, v, 15);
463  curve25519Mul(u, u, v); //C^(2^30 - 1)
464  curve25519Sqr(u, u);
465  curve25519Mul(v, u, c); //C^(2^31 - 1)
466  curve25519Pwr2(u, v, 31);
467  curve25519Mul(v, u, v); //C^(2^62 - 1)
468  curve25519Pwr2(u, v, 62);
469  curve25519Mul(u, u, v); //C^(2^124 - 1)
470  curve25519Sqr(u, u);
471  curve25519Mul(v, u, c); //C^(2^125 - 1)
472  curve25519Pwr2(u, v, 125);
473  curve25519Mul(u, u, v); //C^(2^250 - 1)
474  curve25519Sqr(u, u);
475  curve25519Sqr(u, u);
476  curve25519Mul(u, u, c); //C^(2^252 - 3)
477 
478  //The first candidate root is U = A * B^3 * (A * B^7)^((p - 5) / 8)
479  curve25519Mul(u, u, a);
480  curve25519Sqr(v, b);
481  curve25519Mul(v, v, b);
482  curve25519Mul(u, u, v);
483 
484  //The second candidate root is V = U * sqrt(-1)
485  curve25519Mul(v, u, CURVE25519_SQRT_MINUS_1);
486 
487  //Calculate C = B * U^2
488  curve25519Sqr(c, u);
489  curve25519Mul(c, c, b);
490 
491  //Check whether B * U^2 = A
492  res1 = curve25519Comp(c, a);
493 
494  //Calculate C = B * V^2
495  curve25519Sqr(c, v);
496  curve25519Mul(c, c, b);
497 
498  //Check whether B * V^2 = A
499  res2 = curve25519Comp(c, a);
500 
501  //Select the first or the second candidate root
502  curve25519Select(r, u, v, res1);
503 
504  //Return 0 if the square root exists
505  return res1 & res2;
506 }
507 
508 
509 /**
510  * @brief Copy an integer
511  * @param[out] a Pointer to the destination integer
512  * @param[in] b Pointer to the source integer
513  **/
514 
515 void curve25519Copy(uint32_t *a, const uint32_t *b)
516 {
517  uint_t i;
518 
519  //Copy the value of the integer
520  for(i = 0; i < 8; i++)
521  {
522  a[i] = b[i];
523  }
524 }
525 
526 
527 /**
528  * @brief Conditional swap
529  * @param[in,out] a Pointer to the first integer
530  * @param[in,out] b Pointer to the second integer
531  * @param[in] c Condition variable
532  **/
533 
534 void curve25519Swap(uint32_t *a, uint32_t *b, uint32_t c)
535 {
536  uint_t i;
537  uint32_t mask;
538  uint32_t dummy;
539 
540  //The mask is the all-1 or all-0 word
541  mask = ~c + 1;
542 
543  //Conditional swap
544  for(i = 0; i < 8; i++)
545  {
546  //Constant time implementation
547  dummy = mask & (a[i] ^ b[i]);
548  a[i] ^= dummy;
549  b[i] ^= dummy;
550  }
551 }
552 
553 
554 /**
555  * @brief Select an integer
556  * @param[out] r Pointer to the destination integer
557  * @param[in] a Pointer to the first source integer
558  * @param[in] b Pointer to the second source integer
559  * @param[in] c Condition variable
560  **/
561 
562 void curve25519Select(uint32_t *r, const uint32_t *a, const uint32_t *b,
563  uint32_t c)
564 {
565  uint_t i;
566  uint32_t mask;
567 
568  //The mask is the all-1 or all-0 word
569  mask = c - 1;
570 
571  //Select between A and B
572  for(i = 0; i < 8; i++)
573  {
574  //Constant time implementation
575  r[i] = (a[i] & mask) | (b[i] & ~mask);
576  }
577 }
578 
579 
580 /**
581  * @brief Compare integers
582  * @param[in] a Pointer to the first integer
583  * @param[in] b Pointer to the second integer
584  * @return The function returns 0 if the A = B, else 1
585  **/
586 
587 uint32_t curve25519Comp(const uint32_t *a, const uint32_t *b)
588 {
589  uint_t i;
590  uint32_t mask;
591 
592  //Initialize mask
593  mask = 0;
594 
595  //Compare A and B
596  for(i = 0; i < 8; i++)
597  {
598  //Constant time implementation
599  mask |= a[i] ^ b[i];
600  }
601 
602  //Return 0 if A = B, else 1
603  return ((uint32_t) (mask | (~mask + 1))) >> 31;
604 }
605 
606 
607 /**
608  * @brief Import an octet string
609  * @param[out] a Pointer to resulting integer
610  * @param[in] data Octet string to be converted
611  **/
612 
613 void curve25519Import(uint32_t *a, const uint8_t *data)
614 {
615  uint_t i;
616 
617  //Import the octet string
618  cryptoMemcpy(a, data, 32);
619 
620  //Convert from little-endian byte order to host byte order
621  for(i = 0; i < 8; i++)
622  {
623  a[i] = letoh32(a[i]);
624  }
625 }
626 
627 
628 /**
629  * @brief Export an octet string
630  * @param[in] a Pointer to the integer to be exported
631  * @param[out] data Octet string resulting from the conversion
632  **/
633 
634 void curve25519Export(uint32_t *a, uint8_t *data)
635 {
636  uint_t i;
637 
638  //Convert from host byte order to little-endian byte order
639  for(i = 0; i < 8; i++)
640  {
641  a[i] = htole32(a[i]);
642  }
643 
644  //Export the octet string
645  cryptoMemcpy(data, a, 32);
646 }
647 
648 #endif
void curve25519MulInt(uint32_t *r, const uint32_t *a, uint32_t b)
Modular multiplication.
Definition: curve25519.c:277
uint8_t a
Definition: ndp.h:410
void curve25519Mul(uint32_t *r, const uint32_t *a, const uint32_t *b)
Modular multiplication.
Definition: curve25519.c:191
signed int int_t
Definition: compiler_port.h:44
uint8_t b[6]
Definition: dtls_misc.h:139
void curve25519SetInt(uint32_t *a, uint32_t b)
Set integer value.
Definition: curve25519.c:57
void curve25519Import(uint32_t *a, const uint8_t *data)
Import an octet string.
Definition: curve25519.c:613
void curve25519AddInt(uint32_t *r, const uint32_t *a, uint32_t b)
Modular addition.
Definition: curve25519.c:105
void curve25519Sqr(uint32_t *r, const uint32_t *a)
Modular squaring.
Definition: curve25519.c:317
uint32_t r
Definition: ndp.h:345
void curve25519Swap(uint32_t *a, uint32_t *b, uint32_t c)
Conditional swap.
Definition: curve25519.c:534
#define letoh32(value)
Definition: cpu_endian.h:414
void curve25519Add(uint32_t *r, const uint32_t *a, const uint32_t *b)
Modular addition.
Definition: curve25519.c:79
#define htole32(value)
Definition: cpu_endian.h:406
void curve25519Red(uint32_t *r, const uint32_t *a)
Modular reduction.
Definition: curve25519.c:352
void curve25519Copy(uint32_t *a, const uint32_t *b)
Copy an integer.
Definition: curve25519.c:515
uint32_t curve25519Sqrt(uint32_t *r, const uint32_t *a, const uint32_t *b)
Compute the square root of (A / B) modulo p.
Definition: curve25519.c:430
General definitions for cryptographic algorithms.
uint8_t mask
Definition: web_socket.h:317
void curve25519Inv(uint32_t *r, const uint32_t *a)
Modular multiplicative inverse.
Definition: curve25519.c:380
uint8_t n
void curve25519Pwr2(uint32_t *r, const uint32_t *a, uint_t n)
Raise an integer to power 2^n.
Definition: curve25519.c:331
#define cryptoMemcpy(dest, src, length)
Definition: crypto.h:642
Curve25519 elliptic curve (constant-time implementation)
void curve25519Select(uint32_t *r, const uint32_t *a, const uint32_t *b, uint32_t c)
Select an integer.
Definition: curve25519.c:562
void curve25519Export(uint32_t *a, uint8_t *data)
Export an octet string.
Definition: curve25519.c:634
void curve25519Sub(uint32_t *r, const uint32_t *a, const uint32_t *b)
Modular subtraction.
Definition: curve25519.c:130
unsigned int uint_t
Definition: compiler_port.h:45
Elliptic curves.
uint8_t data[]
Definition: dtls_misc.h:176
void curve25519SubInt(uint32_t *r, const uint32_t *a, uint32_t b)
Modular subtraction.
Definition: curve25519.c:159
uint32_t curve25519Comp(const uint32_t *a, const uint32_t *b)
Compare integers.
Definition: curve25519.c:587
uint8_t c
Definition: ndp.h:513
Debugging facilities.