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-2025 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.5.0
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/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 An integer such as 0 <= B < (2^28 - 1)
48  **/
49 
50 void curve448SetInt(int32_t *a, int32_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 < 16; 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(int32_t *r, const int32_t *a, const int32_t *b)
73 {
74 #if (CURVE448_SPEED_OPTIMIZATION_LEVEL <= 1)
75  uint_t i;
76  int32_t temp;
77 
78  //Compute R = A + B
79  for(temp = 0, i = 0; i < 16; i++)
80  {
81  temp += a[i] + b[i];
82  r[i] = temp & 0x0FFFFFFF;
83  temp >>= 28;
84  }
85 
86  //Perform modular reduction (2^448 = 2^224 + 1)
87  r[0] += temp;
88  r[8] += temp;
89 #else
90  int32_t temp;
91 
92  //Compute R = A + B
93  temp = a[0] + b[0];
94  r[0] = temp & 0x0FFFFFFF;
95  temp >>= 28;
96  temp += a[1] + b[1];
97  r[1] = temp & 0x0FFFFFFF;
98  temp >>= 28;
99  temp += a[2] + b[2];
100  r[2] = temp & 0x0FFFFFFF;
101  temp >>= 28;
102  temp += a[3] + b[3];
103  r[3] = temp & 0x0FFFFFFF;
104  temp >>= 28;
105  temp += a[4] + b[4];
106  r[4] = temp & 0x0FFFFFFF;
107  temp >>= 28;
108  temp += a[5] + b[5];
109  r[5] = temp & 0x0FFFFFFF;
110  temp >>= 28;
111  temp += a[6] + b[6];
112  r[6] = temp & 0x0FFFFFFF;
113  temp >>= 28;
114  temp += a[7] + b[7];
115  r[7] = temp & 0x0FFFFFFF;
116  temp >>= 28;
117  temp += a[8] + b[8];
118  r[8] = temp & 0x0FFFFFFF;
119  temp >>= 28;
120  temp += a[9] + b[9];
121  r[9] = temp & 0x0FFFFFFF;
122  temp >>= 28;
123  temp += a[10] + b[10];
124  r[10] = temp & 0x0FFFFFFF;
125  temp >>= 28;
126  temp += a[11] + b[11];
127  r[11] = temp & 0x0FFFFFFF;
128  temp >>= 28;
129  temp += a[12] + b[12];
130  r[12] = temp & 0x0FFFFFFF;
131  temp >>= 28;
132  temp += a[13] + b[13];
133  r[13] = temp & 0x0FFFFFFF;
134  temp >>= 28;
135  temp += a[14] + b[14];
136  r[14] = temp & 0x0FFFFFFF;
137  temp >>= 28;
138  temp += a[15] + b[15];
139  r[15] = temp & 0x0FFFFFFF;
140  temp >>= 28;
141 
142  //Perform modular reduction (2^448 = 2^224 + 1)
143  r[0] += temp;
144  r[8] += temp;
145 #endif
146 }
147 
148 
149 /**
150  * @brief Modular addition
151  * @param[out] r Resulting integer R = (A + B) mod p
152  * @param[in] a An integer such as 0 <= A < p
153  * @param[in] b An integer such as 0 <= B < (2^28 - 1)
154  **/
155 
156 void curve448AddInt(int32_t *r, const int32_t *a, int32_t b)
157 {
158  uint_t i;
159  int32_t temp;
160 
161  //Compute R = A + B
162  for(temp = b, i = 0; i < 16; i++)
163  {
164  temp += a[i];
165  r[i] = temp & 0x0FFFFFFF;
166  temp >>= 28;
167  }
168 
169  //Perform modular reduction (2^448 = 2^224 + 1)
170  r[0] += temp;
171  r[8] += temp;
172 }
173 
174 
175 /**
176  * @brief Modular subtraction
177  * @param[out] r Resulting integer R = (A - B) mod p
178  * @param[in] a An integer such as 0 <= A < p
179  * @param[in] b An integer such as 0 <= B < p
180  **/
181 
182 void curve448Sub(int32_t *r, const int32_t *a, const int32_t *b)
183 {
184 #if (CURVE448_SPEED_OPTIMIZATION_LEVEL <= 1)
185  uint_t i;
186  int32_t temp;
187 
188  //Compute R = A - B
189  for(temp = 0, i = 0; i < 16; i++)
190  {
191  temp += a[i] - b[i];
192  r[i] = temp & 0x0FFFFFFF;
193  temp >>= 28;
194  }
195 
196  //Perform modular reduction (2^448 = 2^224 + 1)
197  r[0] += temp;
198  r[8] += temp;
199 #else
200  int32_t temp;
201 
202  //Compute R = A - B
203  temp = a[0] - b[0];
204  r[0] = temp & 0x0FFFFFFF;
205  temp >>= 28;
206  temp += a[1] - b[1];
207  r[1] = temp & 0x0FFFFFFF;
208  temp >>= 28;
209  temp += a[2] - b[2];
210  r[2] = temp & 0x0FFFFFFF;
211  temp >>= 28;
212  temp += a[3] - b[3];
213  r[3] = temp & 0x0FFFFFFF;
214  temp >>= 28;
215  temp += a[4] - b[4];
216  r[4] = temp & 0x0FFFFFFF;
217  temp >>= 28;
218  temp += a[5] - b[5];
219  r[5] = temp & 0x0FFFFFFF;
220  temp >>= 28;
221  temp += a[6] - b[6];
222  r[6] = temp & 0x0FFFFFFF;
223  temp >>= 28;
224  temp += a[7] - b[7];
225  r[7] = temp & 0x0FFFFFFF;
226  temp >>= 28;
227  temp += a[8] - b[8];
228  r[8] = temp & 0x0FFFFFFF;
229  temp >>= 28;
230  temp += a[9] - b[9];
231  r[9] = temp & 0x0FFFFFFF;
232  temp >>= 28;
233  temp += a[10] - b[10];
234  r[10] = temp & 0x0FFFFFFF;
235  temp >>= 28;
236  temp += a[11] - b[11];
237  r[11] = temp & 0x0FFFFFFF;
238  temp >>= 28;
239  temp += a[12] - b[12];
240  r[12] = temp & 0x0FFFFFFF;
241  temp >>= 28;
242  temp += a[13] - b[13];
243  r[13] = temp & 0x0FFFFFFF;
244  temp >>= 28;
245  temp += a[14] - b[14];
246  r[14] = temp & 0x0FFFFFFF;
247  temp >>= 28;
248  temp += a[15] - b[15];
249  r[15] = temp & 0x0FFFFFFF;
250  temp >>= 28;
251 
252  //Perform modular reduction (2^448 = 2^224 + 1)
253  r[0] += temp;
254  r[8] += temp;
255 #endif
256 }
257 
258 
259 /**
260  * @brief Modular subtraction
261  * @param[out] r Resulting integer R = (A - B) mod p
262  * @param[in] a An integer such as 0 <= A < p
263  * @param[in] b An integer such as 0 <= B < (2^28 - 1)
264  **/
265 
266 void curve448SubInt(int32_t *r, const int32_t *a, int32_t b)
267 {
268  uint_t i;
269  int32_t temp;
270 
271  //Compute R = A - B
272  for(temp = -b, i = 0; i < 16; i++)
273  {
274  temp += a[i];
275  r[i] = temp & 0x0FFFFFFF;
276  temp >>= 28;
277  }
278 
279  //Perform modular reduction (2^448 = 2^224 + 1)
280  r[0] += temp;
281  r[8] += temp;
282 }
283 
284 
285 /**
286  * @brief 224-bit multiplication
287  * @param[out] r Resulting integer R = A * B
288  * @param[in] a An integer such as 0 <= A < (2^224 - 1)
289  * @param[in] b An integer such as 0 <= B < (2^224 - 1)
290  **/
291 
292 void curve448Mul224(int32_t *r, const int32_t *a, const int32_t *b)
293 {
294 #if (CURVE448_SPEED_OPTIMIZATION_LEVEL == 0)
295  uint_t i;
296  uint_t j;
297  int64_t acc;
298 
299  //Comba's method is used to perform multiplication
300  for(acc = 0, i = 0; i < 16; i++)
301  {
302  //The algorithm computes the products, column by column
303  if(i < 8)
304  {
305  //Inner loop
306  for(j = 0; j <= i; j++)
307  {
308  acc += (int64_t) a[j] * b[i - j];
309  }
310  }
311  else
312  {
313  //Inner loop
314  for(j = i - 7; j < 8; j++)
315  {
316  acc += (int64_t) a[j] * b[i - j];
317  }
318  }
319 
320  //At the bottom of each column, the final result is written to memory
321  r[i] = acc & 0x0FFFFFFF;
322  //Propagate the carry upwards
323  acc >>= 28;
324  }
325 
326  //Perform modular reduction (2^448 = 2^224 + 1)
327  r[0] += (int32_t) acc;
328  r[8] += (int32_t) acc;
329 #else
330  int64_t acc;
331 
332  //Compute R = A * B
333  acc = (int64_t) a[0] * b[0];
334  r[0] = acc & 0x0FFFFFFF;
335  acc >>= 28;
336  acc += (int64_t) a[0] * b[1];
337  acc += (int64_t) a[1] * b[0];
338  r[1] = acc & 0x0FFFFFFF;
339  acc >>= 28;
340  acc += (int64_t) a[0] * b[2];
341  acc += (int64_t) a[1] * b[1];
342  acc += (int64_t) a[2] * b[0];
343  r[2] = acc & 0x0FFFFFFF;
344  acc >>= 28;
345  acc += (int64_t) a[0] * b[3];
346  acc += (int64_t) a[1] * b[2];
347  acc += (int64_t) a[2] * b[1];
348  acc += (int64_t) a[3] * b[0];
349  r[3] = acc & 0x0FFFFFFF;
350  acc >>= 28;
351  acc += (int64_t) a[0] * b[4];
352  acc += (int64_t) a[1] * b[3];
353  acc += (int64_t) a[2] * b[2];
354  acc += (int64_t) a[3] * b[1];
355  acc += (int64_t) a[4] * b[0];
356  r[4] = acc & 0x0FFFFFFF;
357  acc >>= 28;
358  acc += (int64_t) a[0] * b[5];
359  acc += (int64_t) a[1] * b[4];
360  acc += (int64_t) a[2] * b[3];
361  acc += (int64_t) a[3] * b[2];
362  acc += (int64_t) a[4] * b[1];
363  acc += (int64_t) a[5] * b[0];
364  r[5] = acc & 0x0FFFFFFF;
365  acc >>= 28;
366  acc += (int64_t) a[0] * b[6];
367  acc += (int64_t) a[1] * b[5];
368  acc += (int64_t) a[2] * b[4];
369  acc += (int64_t) a[3] * b[3];
370  acc += (int64_t) a[4] * b[2];
371  acc += (int64_t) a[5] * b[1];
372  acc += (int64_t) a[6] * b[0];
373  r[6] = acc & 0x0FFFFFFF;
374  acc >>= 28;
375  acc += (int64_t) a[0] * b[7];
376  acc += (int64_t) a[1] * b[6];
377  acc += (int64_t) a[2] * b[5];
378  acc += (int64_t) a[3] * b[4];
379  acc += (int64_t) a[4] * b[3];
380  acc += (int64_t) a[5] * b[2];
381  acc += (int64_t) a[6] * b[1];
382  acc += (int64_t) a[7] * b[0];
383  r[7] = acc & 0x0FFFFFFF;
384  acc >>= 28;
385  acc += (int64_t) a[1] * b[7];
386  acc += (int64_t) a[2] * b[6];
387  acc += (int64_t) a[3] * b[5];
388  acc += (int64_t) a[4] * b[4];
389  acc += (int64_t) a[5] * b[3];
390  acc += (int64_t) a[6] * b[2];
391  acc += (int64_t) a[7] * b[1];
392  r[8] = acc & 0x0FFFFFFF;
393  acc >>= 28;
394  acc += (int64_t) a[2] * b[7];
395  acc += (int64_t) a[3] * b[6];
396  acc += (int64_t) a[4] * b[5];
397  acc += (int64_t) a[5] * b[4];
398  acc += (int64_t) a[6] * b[3];
399  acc += (int64_t) a[7] * b[2];
400  r[9] = acc & 0x0FFFFFFF;
401  acc >>= 28;
402  acc += (int64_t) a[3] * b[7];
403  acc += (int64_t) a[4] * b[6];
404  acc += (int64_t) a[5] * b[5];
405  acc += (int64_t) a[6] * b[4];
406  acc += (int64_t) a[7] * b[3];
407  r[10] = acc & 0x0FFFFFFF;
408  acc >>= 28;
409  acc += (int64_t) a[4] * b[7];
410  acc += (int64_t) a[5] * b[6];
411  acc += (int64_t) a[6] * b[5];
412  acc += (int64_t) a[7] * b[4];
413  r[11] = acc & 0x0FFFFFFF;
414  acc >>= 28;
415  acc += (int64_t) a[5] * b[7];
416  acc += (int64_t) a[6] * b[6];
417  acc += (int64_t) a[7] * b[5];
418  r[12] = acc & 0x0FFFFFFF;
419  acc >>= 28;
420  acc += (int64_t) a[6] * b[7];
421  acc += (int64_t) a[7] * b[6];
422  r[13] = acc & 0x0FFFFFFF;
423  acc >>= 28;
424  acc += (int64_t) a[7] * b[7];
425  r[14] = acc & 0x0FFFFFFF;
426  acc >>= 28;
427  r[15] = acc & 0x0FFFFFFF;
428  acc >>= 28;
429 
430  //Perform modular reduction (2^448 = 2^224 + 1)
431  r[0] += (int32_t) acc;
432  r[8] += (int32_t) acc;
433 #endif
434 }
435 
436 
437 /**
438  * @brief Modular multiplication
439  * @param[out] r Resulting integer R = (A * B) mod p
440  * @param[in] a An integer such as 0 <= A < p
441  * @param[in] b An integer such as 0 <= B < p
442  **/
443 
444 __weak_func void curve448Mul(int32_t *r, const int32_t *a, const int32_t *b)
445 {
446 #if (CURVE448_SPEED_OPTIMIZATION_LEVEL == 0)
447  uint_t i;
448  uint_t j;
449  int64_t acc1;
450  int64_t acc2;
451  int64_t acc3;
452  int32_t aa[8];
453  int32_t bb[8];
454  int32_t u[16];
455 
456  //Let A = A0+(A1*w) and B = B0+(B1*w). Precompute AA = A0+A1 and BB = B0+B1
457  for(i = 0; i < 8; i++)
458  {
459  aa[i] = a[i] + a[i + 8];
460  bb[i] = b[i] + b[i + 8];
461  }
462 
463  //Clear accumulators
464  acc1 = 0;
465  acc2 = 0;
466 
467  //Karatsuba multiplication can be fused with reduction mod p, and it doesn't
468  //make the multiplication algorithm more complex
469  for(i = 0; i < 8; i++)
470  {
471  //Compute the lower part of A1*B1, AA*BB and A0*B0
472  for(acc3 = 0, j = 0; j <= i; j++)
473  {
474  acc1 += (int64_t) a[8 + j] * b[8 + i - j];
475  acc2 += (int64_t) aa[j] * bb[i - j];
476  acc3 += (int64_t) a[j] * b[i - j];
477  }
478 
479  //Update accumulators
480  acc1 += acc3;
481  acc2 -= acc3;
482 
483  //Compute the upper part of A0*B0, A1*B1 and AA*BB
484  for(acc3 = 0, j = i + 1; j < 8; j++)
485  {
486  acc1 -= (int64_t) a[j] * b[8 + i - j];
487  acc2 += (int64_t) a[8 + j] * b[16 + i - j];
488  acc3 += (int64_t) aa[j] * bb[8 + i - j];
489  }
490 
491  //Update accumulators
492  acc1 += acc3;
493  acc2 += acc3;
494 
495  //The 2 columns are written to memory
496  u[i] = (int32_t) acc1 & 0x0FFFFFFF;
497  acc1 >>= 28;
498  u[i + 8] = (int32_t) acc2 & 0x0FFFFFFF;
499  acc2 >>= 28;
500  }
501 
502  //Perform modular reduction (2^448 = 2^224 + 1)
503  acc1 += acc2;
504 
505  //Propagate carries
506  acc2 += u[0];
507  u[0] = (int32_t) acc2 & 0x0FFFFFFF;
508  acc2 >>= 28;
509  u[1] += (int32_t) acc2;
510  acc1 += u[8];
511  u[8] = (int32_t) acc1 & 0x0FFFFFFF;
512  acc1 >>= 28;
513  u[9] += (int32_t) acc1;
514 
515  //Copy result
516  curve448Copy(r, u);
517 #elif (CURVE448_SPEED_OPTIMIZATION_LEVEL == 1)
518  uint_t i;
519  int32_t c;
520  int32_t temp;
521  int32_t u[16];
522  int32_t v[16];
523  int32_t w[16];
524 
525  //Precompute A0+A1 and B0+B1
526  for(temp = 0, i = 0; i < 8; i++)
527  {
528  u[i] = a[i] + a[i + 8];
529  v[i] = b[i] + b[i + 8];
530  }
531 
532  //Compute W = (A0+A1)*(B0+B1)
533  curve448Mul224(w, u, v);
534  //Compute U = A0*B0
535  curve448Mul224(u, a, b);
536  //Compute V = A1*B1
537  curve448Mul224(v, a + 8, b + 8);
538 
539  //Karatsuba multiplication can be fused with reduction mod p, and it doesn't
540  //make the multiplication algorithm more complex
541  for(temp = 0, i = 0; i < 8; i++)
542  {
543  temp += u[i] - u[i + 8] + v[i] + w[i + 8];
544  r[i] = temp & 0x0FFFFFFF;
545  temp >>= 28;
546  }
547 
548  for(i = 0; i < 8; i++)
549  {
550  temp += -u[i] + v[i + 8] + w[i] + w[i + 8];
551  r[i + 8] = temp & 0x0FFFFFFF;
552  temp >>= 28;
553  }
554 
555  //Perform modular reduction (2^448 = 2^224 + 1)
556  c = temp;
557  temp = r[0] + c;
558  r[0] = temp & 0x0FFFFFFF;
559  temp >>= 28;
560  r[1] += temp;
561  temp = r[8] + c;
562  r[8] = temp & 0x0FFFFFFF;
563  temp >>= 28;
564  r[9] += temp;
565 #else
566  int32_t c;
567  int32_t temp;
568  int32_t u[16];
569  int32_t v[16];
570  int32_t w[16];
571 
572  //Precompute A0+A1
573  u[0] = a[0] + a[8];
574  u[1] = a[1] + a[9];
575  u[2] = a[2] + a[10];
576  u[3] = a[3] + a[11];
577  u[4] = a[4] + a[12];
578  u[5] = a[5] + a[13];
579  u[6] = a[6] + a[14];
580  u[7] = a[7] + a[15];
581 
582  //Precompute B0+B1
583  v[0] = b[0] + b[8];
584  v[1] = b[1] + b[9];
585  v[2] = b[2] + b[10];
586  v[3] = b[3] + b[11];
587  v[4] = b[4] + b[12];
588  v[5] = b[5] + b[13];
589  v[6] = b[6] + b[14];
590  v[7] = b[7] + b[15];
591 
592  //Compute W = (A0+A1)*(B0+B1)
593  curve448Mul224(w, u, v);
594  //Compute U = A0*B0
595  curve448Mul224(u, a, b);
596  //Compute V = A1*B1
597  curve448Mul224(v, a + 8, b + 8);
598 
599  //Karatsuba multiplication can be fused with reduction mod p, and it doesn't
600  //make the multiplication algorithm more complex
601  temp = u[0] - u[8] + v[0] + w[8];
602  r[0] = temp & 0x0FFFFFFF;
603  temp >>= 28;
604  temp += u[1] - u[9] + v[1] + w[9];
605  r[1] = temp & 0x0FFFFFFF;
606  temp >>= 28;
607  temp += u[2] - u[10] + v[2] + w[10];
608  r[2] = temp & 0x0FFFFFFF;
609  temp >>= 28;
610  temp += u[3] - u[11] + v[3] + w[11];
611  r[3] = temp & 0x0FFFFFFF;
612  temp >>= 28;
613  temp += u[4] - u[12] + v[4] + w[12];
614  r[4] = temp & 0x0FFFFFFF;
615  temp >>= 28;
616  temp += u[5] - u[13] + v[5] + w[13];
617  r[5] = temp & 0x0FFFFFFF;
618  temp >>= 28;
619  temp += u[6] - u[14] + v[6] + w[14];
620  r[6] = temp & 0x0FFFFFFF;
621  temp >>= 28;
622  temp += u[7] - u[15] + v[7] + w[15];
623  r[7] = temp & 0x0FFFFFFF;
624  temp >>= 28;
625  temp += -u[0] + v[8] + w[0] + w[8];
626  r[8] = temp & 0x0FFFFFFF;
627  temp >>= 28;
628  temp += -u[1] + v[9] + w[1] + w[9];
629  r[9] = temp & 0x0FFFFFFF;
630  temp >>= 28;
631  temp += -u[2] + v[10] + w[2] + w[10];
632  r[10] = temp & 0x0FFFFFFF;
633  temp >>= 28;
634  temp += -u[3] + v[11] + w[3] + w[11];
635  r[11] = temp & 0x0FFFFFFF;
636  temp >>= 28;
637  temp += -u[4] + v[12] + w[4] + w[12];
638  r[12] = temp & 0x0FFFFFFF;
639  temp >>= 28;
640  temp += -u[5] + v[13] + w[5] + w[13];
641  r[13] = temp & 0x0FFFFFFF;
642  temp >>= 28;
643  temp += -u[6] + v[14] + w[6] + w[14];
644  r[14] = temp & 0x0FFFFFFF;
645  temp >>= 28;
646  temp += -u[7] + v[15] + w[7] + w[15];
647  r[15] = temp & 0x0FFFFFFF;
648  temp >>= 28;
649 
650  //Perform modular reduction (2^448 = 2^224 + 1)
651  c = temp;
652  temp = r[0] + c;
653  r[0] = temp & 0x0FFFFFFF;
654  temp >>= 28;
655  r[1] += temp;
656  temp = r[8] + c;
657  r[8] = temp & 0x0FFFFFFF;
658  temp >>= 28;
659  r[9] += temp;
660 #endif
661 }
662 
663 
664 /**
665  * @brief Modular multiplication
666  * @param[out] r Resulting integer R = (A * B) mod p
667  * @param[in] a An integer such as 0 <= A < p
668  * @param[in] b An integer such as 0 <= B < (2^28 - 1)
669  **/
670 
671 void curve448MulInt(int32_t *r, const int32_t *a, int32_t b)
672 {
673  uint_t i;
674  int64_t temp;
675 
676  //Compute R = A * B
677  for(temp = 0, i = 0; i < 16; i++)
678  {
679  temp += (int64_t) a[i] * b;
680  r[i] = temp & 0x0FFFFFFF;
681  temp >>= 28;
682  }
683 
684  //Perform modular reduction (2^448 = 2^224 + 1)
685  r[0] += (int32_t) temp;
686  r[8] += (int32_t) temp;
687 }
688 
689 
690 /**
691  * @brief Modular squaring
692  * @param[out] r Resulting integer R = (A ^ 2) mod p
693  * @param[in] a An integer such as 0 <= A < p
694  **/
695 
696 __weak_func void curve448Sqr(int32_t *r, const int32_t *a)
697 {
698  //Compute R = (A ^ 2) mod p
699  curve448Mul(r, a, a);
700 }
701 
702 
703 /**
704  * @brief Raise an integer to power 2^n
705  * @param[out] r Resulting integer R = (A ^ (2^n)) mod p
706  * @param[in] a An integer such as 0 <= A < p
707  * @param[in] n An integer such as n >= 1
708  **/
709 
710 void curve448Pwr2(int32_t *r, const int32_t *a, uint_t n)
711 {
712  uint_t i;
713 
714  //Pre-compute (A ^ 2) mod p
715  curve448Sqr(r, a);
716 
717  //Compute R = (A ^ (2^n)) mod p
718  for(i = 1; i < n; i++)
719  {
720  curve448Sqr(r, r);
721  }
722 }
723 
724 
725 /**
726  * @brief Modular multiplicative inverse
727  * @param[out] r Resulting integer R = A^-1 mod p
728  * @param[in] a An integer such as 0 <= A < p
729  **/
730 
731 void curve448Inv(int32_t *r, const int32_t *a)
732 {
733  int32_t u[16];
734  int32_t v[16];
735 
736  //Since GF(p) is a prime field, the Fermat's little theorem can be
737  //used to find the multiplicative inverse of A modulo p
738  curve448Sqr(u, a);
739  curve448Mul(u, u, a); //A^(2^2 - 1)
740  curve448Sqr(u, u);
741  curve448Mul(v, u, a); //A^(2^3 - 1)
742  curve448Pwr2(u, v, 3);
743  curve448Mul(v, u, v); //A^(2^6 - 1)
744  curve448Pwr2(u, v, 6);
745  curve448Mul(u, u, v); //A^(2^12 - 1)
746  curve448Sqr(u, u);
747  curve448Mul(v, u, a); //A^(2^13 - 1)
748  curve448Pwr2(u, v, 13);
749  curve448Mul(u, u, v); //A^(2^26 - 1)
750  curve448Sqr(u, u);
751  curve448Mul(v, u, a); //A^(2^27 - 1)
752  curve448Pwr2(u, v, 27);
753  curve448Mul(u, u, v); //A^(2^54 - 1)
754  curve448Sqr(u, u);
755  curve448Mul(v, u, a); //A^(2^55 - 1)
756  curve448Pwr2(u, v, 55);
757  curve448Mul(u, u, v); //A^(2^110 - 1)
758  curve448Sqr(u, u);
759  curve448Mul(v, u, a); //A^(2^111 - 1)
760  curve448Pwr2(u, v, 111);
761  curve448Mul(v, u, v); //A^(2^222 - 1)
762  curve448Sqr(u, v);
763  curve448Mul(u, u, a); //A^(2^223 - 1)
764  curve448Pwr2(u, u, 223);
765  curve448Mul(u, u, v); //A^(2^446 - 2^222 - 1)
766  curve448Sqr(u, u);
767  curve448Sqr(u, u);
768  curve448Mul(r, u, a); //A^(2^448 - 2^224 - 3)
769 }
770 
771 
772 /**
773  * @brief Compute the square root of (A / B) modulo p
774  * @param[out] r Resulting integer R = (A / B)^(1 / 2) mod p
775  * @param[in] a An integer such as 0 <= A < p
776  * @param[in] b An integer such as 0 < B < p
777  * @return The function returns 0 if the square root exists, else 1
778  **/
779 
780 uint32_t curve448Sqrt(int32_t *r, const int32_t *a, const int32_t *b)
781 {
782  uint32_t res;
783  int32_t c[16];
784  int32_t u[16];
785  int32_t v[16];
786 
787  //Compute the candidate root (A / B)^((p + 1) / 4). This can be done
788  //with the following trick, using a single modular powering for both the
789  //inversion of B and the square root: A^3 * B * (A^5 * B^3)^((p - 3) / 4)
790  curve448Sqr(u, a);
791  curve448Sqr(u, u);
792  curve448Mul(u, u, a);
793  curve448Sqr(v, b);
794  curve448Mul(v, v, b);
795 
796  //Compute C = A^5 * B^3
797  curve448Mul(c, u, v);
798 
799  //Compute U = C^((p - 3) / 4)
800  curve448Sqr(u, c);
801  curve448Mul(u, u, c); //C^(2^2 - 1)
802  curve448Sqr(u, u);
803  curve448Mul(v, u, c); //C^(2^3 - 1)
804  curve448Pwr2(u, v, 3);
805  curve448Mul(v, u, v); //C^(2^6 - 1)
806  curve448Pwr2(u, v, 6);
807  curve448Mul(u, u, v); //C^(2^12 - 1)
808  curve448Sqr(u, u);
809  curve448Mul(v, u, c); //C^(2^13 - 1)
810  curve448Pwr2(u, v, 13);
811  curve448Mul(u, u, v); //C^(2^26 - 1)
812  curve448Sqr(u, u);
813  curve448Mul(v, u, c); //C^(2^27 - 1)
814  curve448Pwr2(u, v, 27);
815  curve448Mul(u, u, v); //C^(2^54 - 1)
816  curve448Sqr(u, u);
817  curve448Mul(v, u, c); //C^(2^55 - 1)
818  curve448Pwr2(u, v, 55);
819  curve448Mul(u, u, v); //C^(2^110 - 1)
820  curve448Sqr(u, u);
821  curve448Mul(v, u, c); //C^(2^111 - 1)
822  curve448Pwr2(u, v, 111);
823  curve448Mul(v, u, v); //C^(2^222 - 1)
824  curve448Sqr(u, v);
825  curve448Mul(u, u, c); //C^(2^223 - 1)
826  curve448Pwr2(u, u, 223);
827  curve448Mul(u, u, v); //C^(2^446 - 2^222 - 1)
828 
829  //The candidate root is U = A^3 * B * (A^5 * B^3)^((p - 3) / 4)
830  curve448Sqr(v, a);
831  curve448Mul(v, v, a);
832  curve448Mul(u, u, v);
833  curve448Mul(u, u, b);
834  curve448Canonicalize(u, u);
835 
836  //Calculate C = B * U^2
837  curve448Sqr(c, u);
838  curve448Mul(c, c, b);
839  curve448Canonicalize(c, c);
840 
841  //Reduce non-canonical values of A
842  curve448Canonicalize(v, a);
843 
844  //Check whether B * U^2 = A
845  res = curve448Comp(c, v);
846 
847  //Copy the candidate root
848  curve448Copy(r, u);
849 
850  //Return 0 if the square root exists
851  return res;
852 }
853 
854 
855 /**
856  * @brief Reduce non-canonical value
857  * @param[out] r Resulting integer R = A mod p
858  * @param[in] a An integer such as 0 <= A < (2^448 - 1)
859  **/
860 
861 void curve448Canonicalize(int32_t *r, const int32_t *a)
862 {
863  uint_t i;
864  int32_t temp;
865  int32_t b[16];
866 
867  //Perform modular reduction (first pass)
868  for(temp = 0, i = 0; i < 16; i++)
869  {
870  temp += a[i];
871  r[i] = temp & 0x0FFFFFFF;
872  temp >>= 28;
873  }
874 
875  //Perform modular reduction (second pass)
876  for(r[8] += temp, i = 0; i < 16; i++)
877  {
878  temp += r[i];
879  r[i] = temp & 0x0FFFFFFF;
880  temp >>= 28;
881  }
882 
883  //Compute B = A - (2^448 - 2^224 - 1)
884  for(temp = 1, i = 0; i < 8; i++)
885  {
886  temp += r[i];
887  b[i] = temp & 0x0FFFFFFF;
888  temp >>= 28;
889  }
890 
891  for(temp += 1, i = 8; i < 16; i++)
892  {
893  temp += r[i];
894  b[i] = temp & 0x0FFFFFFF;
895  temp >>= 28;
896  }
897 
898  //Compute the highest term of the result
899  temp -= 1;
900 
901  //If B < (2^448 - 2^224 + 1) then R = B, else R = A
902  curve448Select(r, b, r, temp & 1);
903 }
904 
905 
906 /**
907  * @brief Copy an integer
908  * @param[out] a Pointer to the destination integer
909  * @param[in] b Pointer to the source integer
910  **/
911 
912 void curve448Copy(int32_t *a, const int32_t *b)
913 {
914  uint_t i;
915 
916  //Copy the value of the integer
917  for(i = 0; i < 16; i++)
918  {
919  a[i] = b[i];
920  }
921 }
922 
923 
924 /**
925  * @brief Conditional swap
926  * @param[in,out] a Pointer to the first integer
927  * @param[in,out] b Pointer to the second integer
928  * @param[in] c Condition variable
929  **/
930 
931 void curve448Swap(int32_t *a, int32_t *b, uint32_t c)
932 {
933  uint_t i;
934  uint32_t mask;
935  uint32_t dummy;
936 
937  //The mask is the all-1 or all-0 word
938  mask = ~c + 1;
939 
940  //Conditional swap
941  for(i = 0; i < 16; i++)
942  {
943  //Constant time implementation
944  dummy = mask & (a[i] ^ b[i]);
945  a[i] ^= dummy;
946  b[i] ^= dummy;
947  }
948 }
949 
950 
951 /**
952  * @brief Select an integer
953  * @param[out] r Pointer to the destination integer
954  * @param[in] a Pointer to the first source integer
955  * @param[in] b Pointer to the second source integer
956  * @param[in] c Condition variable
957  **/
958 
959 void curve448Select(int32_t *r, const int32_t *a, const int32_t *b,
960  uint32_t c)
961 {
962  uint_t i;
963  uint32_t mask;
964 
965  //The mask is the all-1 or all-0 word
966  mask = c - 1;
967 
968  //Select between A and B
969  for(i = 0; i < 16; i++)
970  {
971  //Constant time implementation
972  r[i] = (a[i] & mask) | (b[i] & ~mask);
973  }
974 }
975 
976 
977 /**
978  * @brief Compare integers
979  * @param[in] a Pointer to the first integer
980  * @param[in] b Pointer to the second integer
981  * @return The function returns 0 if the A = B, else 1
982  **/
983 
984 uint32_t curve448Comp(const int32_t *a, const int32_t *b)
985 {
986  uint_t i;
987  uint32_t mask;
988 
989  //Initialize mask
990  mask = 0;
991 
992  //Compare A and B
993  for(i = 0; i < 16; i++)
994  {
995  //Constant time implementation
996  mask |= a[i] ^ b[i];
997  }
998 
999  //Return 0 if A = B, else 1
1000  return ((uint32_t) (mask | (~mask + 1))) >> 31;
1001 }
1002 
1003 
1004 /**
1005  * @brief Import an octet string
1006  * @param[out] a Pointer to resulting integer
1007  * @param[in] data Octet string to be converted
1008  **/
1009 
1010 void curve448Import(int32_t *a, const uint8_t *data)
1011 {
1012  uint_t i;
1013  uint32_t temp;
1014 
1015  //Pack the octet string into 16 words of 28 bits
1016  for(a[0] = 0, i = 0; i < 7; i++)
1017  {
1018  temp = LOAD32LE(data + i * 4);
1019  a[i] |= (temp << (i * 4)) & 0x0FFFFFFF;
1020  a[i + 1] = temp >> (28 - i * 4);
1021  }
1022 
1023  for(a[8] = 0, i = 0; i < 7; i++)
1024  {
1025  temp = LOAD32LE(data + (i + 7) * 4);
1026  a[i + 8] |= (temp << (i * 4)) & 0x0FFFFFFF;
1027  a[i + 9] = temp >> (28 - i * 4);
1028  }
1029 }
1030 
1031 
1032 /**
1033  * @brief Export an octet string
1034  * @param[in] a Pointer to the integer to be exported
1035  * @param[out] data Octet string resulting from the conversion
1036  **/
1037 
1038 void curve448Export(int32_t *a, uint8_t *data)
1039 {
1040  uint_t i;
1041  uint32_t temp;
1042 
1043  //Unpack the 16 words of 28 bits
1044  for(i = 0; i < 7; i++)
1045  {
1046  temp = (a[i + 1] << (28 - i * 4)) | (a[i] >> (i * 4));
1047  STORE32LE(temp, data + i * 4);
1048  }
1049 
1050  for(i = 0; i < 7; i++)
1051  {
1052  temp = (a[i + 9] << (28 - 4 * i)) | (a[i + 8] >> (i * 4));
1053  STORE32LE(temp, data + (i + 7) * 4);
1054  }
1055 }
1056 
1057 #endif
curve448SubInt
void curve448SubInt(int32_t *r, const int32_t *a, int32_t b)
Modular subtraction.
Definition: curve448.c:266
curve448.h
Curve448 elliptic curve (constant-time implementation)
b
uint8_t b
Definition: nbns_common.h:104
curve448Comp
uint32_t curve448Comp(const int32_t *a, const int32_t *b)
Compare integers.
Definition: curve448.c:984
a
uint8_t a
Definition: ndp.h:411
curve448Select
void curve448Select(int32_t *r, const int32_t *a, const int32_t *b, uint32_t c)
Select an integer.
Definition: curve448.c:959
curve448Swap
void curve448Swap(int32_t *a, int32_t *b, uint32_t c)
Conditional swap.
Definition: curve448.c:931
data
uint8_t data[]
Definition: ethernet.h:222
STORE32LE
#define STORE32LE(a, p)
Definition: cpu_endian.h:279
curve448Sqr
__weak_func void curve448Sqr(int32_t *r, const int32_t *a)
Modular squaring.
Definition: curve448.c:696
aa
uint8_t aa
Definition: dns_common.h:187
curve448Sqrt
uint32_t curve448Sqrt(int32_t *r, const int32_t *a, const int32_t *b)
Compute the square root of (A / B) modulo p.
Definition: curve448.c:780
res
const uint8_t res[]
curve448Inv
void curve448Inv(int32_t *r, const int32_t *a)
Modular multiplicative inverse.
Definition: curve448.c:731
r
uint8_t r
Definition: ndp.h:346
curve448Canonicalize
void curve448Canonicalize(int32_t *r, const int32_t *a)
Reduce non-canonical value.
Definition: curve448.c:861
curve448Mul
__weak_func void curve448Mul(int32_t *r, const int32_t *a, const int32_t *b)
Modular multiplication.
Definition: curve448.c:444
curve448Copy
void curve448Copy(int32_t *a, const int32_t *b)
Copy an integer.
Definition: curve448.c:912
crypto.h
General definitions for cryptographic algorithms.
mask
uint8_t mask
Definition: web_socket.h:319
u
uint8_t u
Definition: lldp_ext_med.h:213
curve448Add
void curve448Add(int32_t *r, const int32_t *a, const int32_t *b)
Modular addition.
Definition: curve448.c:72
curve448Mul224
void curve448Mul224(int32_t *r, const int32_t *a, const int32_t *b)
224-bit multiplication
Definition: curve448.c:292
curve448MulInt
void curve448MulInt(int32_t *r, const int32_t *a, int32_t b)
Modular multiplication.
Definition: curve448.c:671
n
uint8_t n
Definition: dhcpv6_common.h:416
curve448Pwr2
void curve448Pwr2(int32_t *r, const int32_t *a, uint_t n)
Raise an integer to power 2^n.
Definition: curve448.c:710
curve448Export
void curve448Export(int32_t *a, uint8_t *data)
Export an octet string.
Definition: curve448.c:1038
curve448Sub
void curve448Sub(int32_t *r, const int32_t *a, const int32_t *b)
Modular subtraction.
Definition: curve448.c:182
curve448AddInt
void curve448AddInt(int32_t *r, const int32_t *a, int32_t b)
Modular addition.
Definition: curve448.c:156
curve448SetInt
void curve448SetInt(int32_t *a, int32_t b)
Set integer value.
Definition: curve448.c:50
LOAD32LE
#define LOAD32LE(p)
Definition: cpu_endian.h:203
uint_t
unsigned int uint_t
Definition: compiler_port.h:57
ec.h
ECC (Elliptic Curve Cryptography)
curve448Import
void curve448Import(int32_t *a, const uint8_t *data)
Import an octet string.
Definition: curve448.c:1010
c
uint8_t c
Definition: ndp.h:514
debug.h
Debugging facilities.