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