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