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