curve448.c
Go to the documentation of this file.
1 /**
2  * @file curve448.c
3  * @brief Curve448 elliptic curve
4  *
5  * @section License
6  *
7  * SPDX-License-Identifier: GPL-2.0-or-later
8  *
9  * Copyright (C) 2010-2026 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.6.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.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  int32_t temp;
75 
76  //Compute R = A + B
77  temp = a[0] + b[0];
78  r[0] = temp & 0x0FFFFFFF;
79  temp = ASR32(temp, 28);
80  temp += a[1] + b[1];
81  r[1] = temp & 0x0FFFFFFF;
82  temp = ASR32(temp, 28);
83  temp += a[2] + b[2];
84  r[2] = temp & 0x0FFFFFFF;
85  temp = ASR32(temp, 28);
86  temp += a[3] + b[3];
87  r[3] = temp & 0x0FFFFFFF;
88  temp = ASR32(temp, 28);
89  temp += a[4] + b[4];
90  r[4] = temp & 0x0FFFFFFF;
91  temp = ASR32(temp, 28);
92  temp += a[5] + b[5];
93  r[5] = temp & 0x0FFFFFFF;
94  temp = ASR32(temp, 28);
95  temp += a[6] + b[6];
96  r[6] = temp & 0x0FFFFFFF;
97  temp = ASR32(temp, 28);
98  temp += a[7] + b[7];
99  r[7] = temp & 0x0FFFFFFF;
100  temp = ASR32(temp, 28);
101  temp += a[8] + b[8];
102  r[8] = temp & 0x0FFFFFFF;
103  temp = ASR32(temp, 28);
104  temp += a[9] + b[9];
105  r[9] = temp & 0x0FFFFFFF;
106  temp = ASR32(temp, 28);
107  temp += a[10] + b[10];
108  r[10] = temp & 0x0FFFFFFF;
109  temp = ASR32(temp, 28);
110  temp += a[11] + b[11];
111  r[11] = temp & 0x0FFFFFFF;
112  temp = ASR32(temp, 28);
113  temp += a[12] + b[12];
114  r[12] = temp & 0x0FFFFFFF;
115  temp = ASR32(temp, 28);
116  temp += a[13] + b[13];
117  r[13] = temp & 0x0FFFFFFF;
118  temp = ASR32(temp, 28);
119  temp += a[14] + b[14];
120  r[14] = temp & 0x0FFFFFFF;
121  temp = ASR32(temp, 28);
122  temp += a[15] + b[15];
123  r[15] = temp & 0x0FFFFFFF;
124  temp = ASR32(temp, 28);
125 
126  //Perform modular reduction (2^448 = 2^224 + 1)
127  r[0] += temp;
128  r[8] += temp;
129 }
130 
131 
132 /**
133  * @brief Modular addition
134  * @param[out] r Resulting integer R = (A + B) mod p
135  * @param[in] a An integer such as 0 <= A < p
136  * @param[in] b An integer such as 0 <= B < (2^28 - 1)
137  **/
138 
139 void curve448AddInt(int32_t *r, const int32_t *a, int32_t b)
140 {
141  uint_t i;
142  int32_t temp;
143 
144  //Compute R = A + B
145  for(temp = b, i = 0; i < 16; i++)
146  {
147  temp += a[i];
148  r[i] = temp & 0x0FFFFFFF;
149  temp = ASR32(temp, 28);
150  }
151 
152  //Perform modular reduction (2^448 = 2^224 + 1)
153  r[0] += temp;
154  r[8] += temp;
155 }
156 
157 
158 /**
159  * @brief Modular subtraction
160  * @param[out] r Resulting integer R = (A - B) mod p
161  * @param[in] a An integer such as 0 <= A < p
162  * @param[in] b An integer such as 0 <= B < p
163  **/
164 
165 void curve448Sub(int32_t *r, const int32_t *a, const int32_t *b)
166 {
167  int32_t temp;
168 
169  //Compute R = A - B
170  temp = a[0] - b[0];
171  r[0] = temp & 0x0FFFFFFF;
172  temp = ASR32(temp, 28);
173  temp += a[1] - b[1];
174  r[1] = temp & 0x0FFFFFFF;
175  temp = ASR32(temp, 28);
176  temp += a[2] - b[2];
177  r[2] = temp & 0x0FFFFFFF;
178  temp = ASR32(temp, 28);
179  temp += a[3] - b[3];
180  r[3] = temp & 0x0FFFFFFF;
181  temp = ASR32(temp, 28);
182  temp += a[4] - b[4];
183  r[4] = temp & 0x0FFFFFFF;
184  temp = ASR32(temp, 28);
185  temp += a[5] - b[5];
186  r[5] = temp & 0x0FFFFFFF;
187  temp = ASR32(temp, 28);
188  temp += a[6] - b[6];
189  r[6] = temp & 0x0FFFFFFF;
190  temp = ASR32(temp, 28);
191  temp += a[7] - b[7];
192  r[7] = temp & 0x0FFFFFFF;
193  temp = ASR32(temp, 28);
194  temp += a[8] - b[8];
195  r[8] = temp & 0x0FFFFFFF;
196  temp = ASR32(temp, 28);
197  temp += a[9] - b[9];
198  r[9] = temp & 0x0FFFFFFF;
199  temp = ASR32(temp, 28);
200  temp += a[10] - b[10];
201  r[10] = temp & 0x0FFFFFFF;
202  temp = ASR32(temp, 28);
203  temp += a[11] - b[11];
204  r[11] = temp & 0x0FFFFFFF;
205  temp = ASR32(temp, 28);
206  temp += a[12] - b[12];
207  r[12] = temp & 0x0FFFFFFF;
208  temp = ASR32(temp, 28);
209  temp += a[13] - b[13];
210  r[13] = temp & 0x0FFFFFFF;
211  temp = ASR32(temp, 28);
212  temp += a[14] - b[14];
213  r[14] = temp & 0x0FFFFFFF;
214  temp = ASR32(temp, 28);
215  temp += a[15] - b[15];
216  r[15] = temp & 0x0FFFFFFF;
217  temp = ASR32(temp, 28);
218 
219  //Perform modular reduction (2^448 = 2^224 + 1)
220  r[0] += temp;
221  r[8] += temp;
222 }
223 
224 
225 /**
226  * @brief Modular subtraction
227  * @param[out] r Resulting integer R = (A - B) mod p
228  * @param[in] a An integer such as 0 <= A < p
229  * @param[in] b An integer such as 0 <= B < (2^28 - 1)
230  **/
231 
232 void curve448SubInt(int32_t *r, const int32_t *a, int32_t b)
233 {
234  uint_t i;
235  int32_t temp;
236 
237  //Compute R = A - B
238  for(temp = -b, i = 0; i < 16; i++)
239  {
240  temp += a[i];
241  r[i] = temp & 0x0FFFFFFF;
242  temp = ASR32(temp, 28);
243  }
244 
245  //Perform modular reduction (2^448 = 2^224 + 1)
246  r[0] += temp;
247  r[8] += temp;
248 }
249 
250 
251 /**
252  * @brief 224-bit multiplication
253  * @param[out] r Resulting integer R = A * B
254  * @param[in] a An integer such as 0 <= A < (2^224 - 1)
255  * @param[in] b An integer such as 0 <= B < (2^224 - 1)
256  **/
257 
258 __weak_func void curve448Mul224(int32_t *r, const int32_t *a, const int32_t *b)
259 {
260  int64_t acc;
261 
262  //Compute R = A * B
263  acc = (int64_t) a[0] * b[0];
264  r[0] = acc & 0x0FFFFFFF;
265  acc = ASR64(acc, 28);
266  acc += (int64_t) a[0] * b[1];
267  acc += (int64_t) a[1] * b[0];
268  r[1] = acc & 0x0FFFFFFF;
269  acc = ASR64(acc, 28);
270  acc += (int64_t) a[0] * b[2];
271  acc += (int64_t) a[1] * b[1];
272  acc += (int64_t) a[2] * b[0];
273  r[2] = acc & 0x0FFFFFFF;
274  acc = ASR64(acc, 28);
275  acc += (int64_t) a[0] * b[3];
276  acc += (int64_t) a[1] * b[2];
277  acc += (int64_t) a[2] * b[1];
278  acc += (int64_t) a[3] * b[0];
279  r[3] = acc & 0x0FFFFFFF;
280  acc = ASR64(acc, 28);
281  acc += (int64_t) a[0] * b[4];
282  acc += (int64_t) a[1] * b[3];
283  acc += (int64_t) a[2] * b[2];
284  acc += (int64_t) a[3] * b[1];
285  acc += (int64_t) a[4] * b[0];
286  r[4] = acc & 0x0FFFFFFF;
287  acc = ASR64(acc, 28);
288  acc += (int64_t) a[0] * b[5];
289  acc += (int64_t) a[1] * b[4];
290  acc += (int64_t) a[2] * b[3];
291  acc += (int64_t) a[3] * b[2];
292  acc += (int64_t) a[4] * b[1];
293  acc += (int64_t) a[5] * b[0];
294  r[5] = acc & 0x0FFFFFFF;
295  acc = ASR64(acc, 28);
296  acc += (int64_t) a[0] * b[6];
297  acc += (int64_t) a[1] * b[5];
298  acc += (int64_t) a[2] * b[4];
299  acc += (int64_t) a[3] * b[3];
300  acc += (int64_t) a[4] * b[2];
301  acc += (int64_t) a[5] * b[1];
302  acc += (int64_t) a[6] * b[0];
303  r[6] = acc & 0x0FFFFFFF;
304  acc = ASR64(acc, 28);
305  acc += (int64_t) a[0] * b[7];
306  acc += (int64_t) a[1] * b[6];
307  acc += (int64_t) a[2] * b[5];
308  acc += (int64_t) a[3] * b[4];
309  acc += (int64_t) a[4] * b[3];
310  acc += (int64_t) a[5] * b[2];
311  acc += (int64_t) a[6] * b[1];
312  acc += (int64_t) a[7] * b[0];
313  r[7] = acc & 0x0FFFFFFF;
314  acc = ASR64(acc, 28);
315  acc += (int64_t) a[1] * b[7];
316  acc += (int64_t) a[2] * b[6];
317  acc += (int64_t) a[3] * b[5];
318  acc += (int64_t) a[4] * b[4];
319  acc += (int64_t) a[5] * b[3];
320  acc += (int64_t) a[6] * b[2];
321  acc += (int64_t) a[7] * b[1];
322  r[8] = acc & 0x0FFFFFFF;
323  acc = ASR64(acc, 28);
324  acc += (int64_t) a[2] * b[7];
325  acc += (int64_t) a[3] * b[6];
326  acc += (int64_t) a[4] * b[5];
327  acc += (int64_t) a[5] * b[4];
328  acc += (int64_t) a[6] * b[3];
329  acc += (int64_t) a[7] * b[2];
330  r[9] = acc & 0x0FFFFFFF;
331  acc = ASR64(acc, 28);
332  acc += (int64_t) a[3] * b[7];
333  acc += (int64_t) a[4] * b[6];
334  acc += (int64_t) a[5] * b[5];
335  acc += (int64_t) a[6] * b[4];
336  acc += (int64_t) a[7] * b[3];
337  r[10] = acc & 0x0FFFFFFF;
338  acc = ASR64(acc, 28);
339  acc += (int64_t) a[4] * b[7];
340  acc += (int64_t) a[5] * b[6];
341  acc += (int64_t) a[6] * b[5];
342  acc += (int64_t) a[7] * b[4];
343  r[11] = acc & 0x0FFFFFFF;
344  acc = ASR64(acc, 28);
345  acc += (int64_t) a[5] * b[7];
346  acc += (int64_t) a[6] * b[6];
347  acc += (int64_t) a[7] * b[5];
348  r[12] = acc & 0x0FFFFFFF;
349  acc = ASR64(acc, 28);
350  acc += (int64_t) a[6] * b[7];
351  acc += (int64_t) a[7] * b[6];
352  r[13] = acc & 0x0FFFFFFF;
353  acc = ASR64(acc, 28);
354  acc += (int64_t) a[7] * b[7];
355  r[14] = acc & 0x0FFFFFFF;
356  acc = ASR64(acc, 28);
357  r[15] = acc & 0x0FFFFFFF;
358  acc = ASR64(acc, 28);
359 
360  //Perform modular reduction (2^448 = 2^224 + 1)
361  r[0] += (int32_t) acc;
362  r[8] += (int32_t) acc;
363 }
364 
365 
366 /**
367  * @brief Modular multiplication
368  * @param[out] r Resulting integer R = (A * B) mod p
369  * @param[in] a An integer such as 0 <= A < p
370  * @param[in] b An integer such as 0 <= B < p
371  **/
372 
373 __weak_func void curve448Mul(int32_t *r, const int32_t *a, const int32_t *b)
374 {
375  int32_t c;
376  int32_t temp;
377  int32_t u[16];
378  int32_t v[16];
379  int32_t w[16];
380 
381  //Precompute A0+A1
382  u[0] = a[0] + a[8];
383  u[1] = a[1] + a[9];
384  u[2] = a[2] + a[10];
385  u[3] = a[3] + a[11];
386  u[4] = a[4] + a[12];
387  u[5] = a[5] + a[13];
388  u[6] = a[6] + a[14];
389  u[7] = a[7] + a[15];
390 
391  //Precompute B0+B1
392  v[0] = b[0] + b[8];
393  v[1] = b[1] + b[9];
394  v[2] = b[2] + b[10];
395  v[3] = b[3] + b[11];
396  v[4] = b[4] + b[12];
397  v[5] = b[5] + b[13];
398  v[6] = b[6] + b[14];
399  v[7] = b[7] + b[15];
400 
401  //Compute W = (A0+A1)*(B0+B1)
402  curve448Mul224(w, u, v);
403  //Compute U = A0*B0
404  curve448Mul224(u, a, b);
405  //Compute V = A1*B1
406  curve448Mul224(v, a + 8, b + 8);
407 
408  //Karatsuba multiplication can be fused with reduction mod p, and it doesn't
409  //make the multiplication algorithm more complex
410  temp = u[0] - u[8] + v[0] + w[8];
411  r[0] = temp & 0x0FFFFFFF;
412  temp = ASR32(temp, 28);
413  temp += u[1] - u[9] + v[1] + w[9];
414  r[1] = temp & 0x0FFFFFFF;
415  temp = ASR32(temp, 28);
416  temp += u[2] - u[10] + v[2] + w[10];
417  r[2] = temp & 0x0FFFFFFF;
418  temp = ASR32(temp, 28);
419  temp += u[3] - u[11] + v[3] + w[11];
420  r[3] = temp & 0x0FFFFFFF;
421  temp = ASR32(temp, 28);
422  temp += u[4] - u[12] + v[4] + w[12];
423  r[4] = temp & 0x0FFFFFFF;
424  temp = ASR32(temp, 28);
425  temp += u[5] - u[13] + v[5] + w[13];
426  r[5] = temp & 0x0FFFFFFF;
427  temp = ASR32(temp, 28);
428  temp += u[6] - u[14] + v[6] + w[14];
429  r[6] = temp & 0x0FFFFFFF;
430  temp = ASR32(temp, 28);
431  temp += u[7] - u[15] + v[7] + w[15];
432  r[7] = temp & 0x0FFFFFFF;
433  temp = ASR32(temp, 28);
434  temp += -u[0] + v[8] + w[0] + w[8];
435  r[8] = temp & 0x0FFFFFFF;
436  temp = ASR32(temp, 28);
437  temp += -u[1] + v[9] + w[1] + w[9];
438  r[9] = temp & 0x0FFFFFFF;
439  temp = ASR32(temp, 28);
440  temp += -u[2] + v[10] + w[2] + w[10];
441  r[10] = temp & 0x0FFFFFFF;
442  temp = ASR32(temp, 28);
443  temp += -u[3] + v[11] + w[3] + w[11];
444  r[11] = temp & 0x0FFFFFFF;
445  temp = ASR32(temp, 28);
446  temp += -u[4] + v[12] + w[4] + w[12];
447  r[12] = temp & 0x0FFFFFFF;
448  temp = ASR32(temp, 28);
449  temp += -u[5] + v[13] + w[5] + w[13];
450  r[13] = temp & 0x0FFFFFFF;
451  temp = ASR32(temp, 28);
452  temp += -u[6] + v[14] + w[6] + w[14];
453  r[14] = temp & 0x0FFFFFFF;
454  temp = ASR32(temp, 28);
455  temp += -u[7] + v[15] + w[7] + w[15];
456  r[15] = temp & 0x0FFFFFFF;
457  temp = ASR32(temp, 28);
458 
459  //Perform modular reduction (2^448 = 2^224 + 1)
460  c = temp;
461  temp = r[0] + c;
462  r[0] = temp & 0x0FFFFFFF;
463  temp = ASR32(temp, 28);
464  r[1] += temp;
465  temp = r[8] + c;
466  r[8] = temp & 0x0FFFFFFF;
467  temp = ASR32(temp, 28);
468  r[9] += temp;
469 }
470 
471 
472 /**
473  * @brief Modular multiplication
474  * @param[out] r Resulting integer R = (A * B) mod p
475  * @param[in] a An integer such as 0 <= A < p
476  * @param[in] b An integer such as 0 <= B < (2^28 - 1)
477  **/
478 
479 __weak_func void curve448MulInt(int32_t *r, const int32_t *a, int32_t b)
480 {
481  uint_t i;
482  int64_t temp;
483 
484  //Compute R = A * B
485  for(temp = 0, i = 0; i < 16; i++)
486  {
487  temp += (int64_t) a[i] * b;
488  r[i] = temp & 0x0FFFFFFF;
489  temp = ASR64(temp, 28);
490  }
491 
492  //Perform modular reduction (2^448 = 2^224 + 1)
493  r[0] += (int32_t) temp;
494  r[8] += (int32_t) temp;
495 }
496 
497 
498 /**
499  * @brief Modular squaring
500  * @param[out] r Resulting integer R = (A ^ 2) mod p
501  * @param[in] a An integer such as 0 <= A < p
502  **/
503 
504 __weak_func void curve448Sqr(int32_t *r, const int32_t *a)
505 {
506  //Compute R = (A ^ 2) mod p
507  curve448Mul(r, a, a);
508 }
509 
510 
511 /**
512  * @brief Raise an integer to power 2^n
513  * @param[out] r Resulting integer R = (A ^ (2^n)) mod p
514  * @param[in] a An integer such as 0 <= A < p
515  * @param[in] n An integer such as n >= 1
516  **/
517 
518 void curve448Pwr2(int32_t *r, const int32_t *a, uint_t n)
519 {
520  uint_t i;
521 
522  //Pre-compute (A ^ 2) mod p
523  curve448Sqr(r, a);
524 
525  //Compute R = (A ^ (2^n)) mod p
526  for(i = 1; i < n; i++)
527  {
528  curve448Sqr(r, r);
529  }
530 }
531 
532 
533 /**
534  * @brief Modular multiplicative inverse
535  * @param[out] r Resulting integer R = A^-1 mod p
536  * @param[in] a An integer such as 0 <= A < p
537  **/
538 
539 void curve448Inv(int32_t *r, const int32_t *a)
540 {
541  int32_t u[16];
542  int32_t v[16];
543 
544  //Since GF(p) is a prime field, the Fermat's little theorem can be
545  //used to find the multiplicative inverse of A modulo p
546  curve448Sqr(u, a);
547  curve448Mul(u, u, a); //A^(2^2 - 1)
548  curve448Sqr(u, u);
549  curve448Mul(v, u, a); //A^(2^3 - 1)
550  curve448Pwr2(u, v, 3);
551  curve448Mul(v, u, v); //A^(2^6 - 1)
552  curve448Pwr2(u, v, 6);
553  curve448Mul(u, u, v); //A^(2^12 - 1)
554  curve448Sqr(u, u);
555  curve448Mul(v, u, a); //A^(2^13 - 1)
556  curve448Pwr2(u, v, 13);
557  curve448Mul(u, u, v); //A^(2^26 - 1)
558  curve448Sqr(u, u);
559  curve448Mul(v, u, a); //A^(2^27 - 1)
560  curve448Pwr2(u, v, 27);
561  curve448Mul(u, u, v); //A^(2^54 - 1)
562  curve448Sqr(u, u);
563  curve448Mul(v, u, a); //A^(2^55 - 1)
564  curve448Pwr2(u, v, 55);
565  curve448Mul(u, u, v); //A^(2^110 - 1)
566  curve448Sqr(u, u);
567  curve448Mul(v, u, a); //A^(2^111 - 1)
568  curve448Pwr2(u, v, 111);
569  curve448Mul(v, u, v); //A^(2^222 - 1)
570  curve448Sqr(u, v);
571  curve448Mul(u, u, a); //A^(2^223 - 1)
572  curve448Pwr2(u, u, 223);
573  curve448Mul(u, u, v); //A^(2^446 - 2^222 - 1)
574  curve448Sqr(u, u);
575  curve448Sqr(u, u);
576  curve448Mul(r, u, a); //A^(2^448 - 2^224 - 3)
577 }
578 
579 
580 /**
581  * @brief Compute the square root of (A / B) modulo p
582  * @param[out] r Resulting integer R = (A / B)^(1 / 2) mod p
583  * @param[in] a An integer such as 0 <= A < p
584  * @param[in] b An integer such as 0 < B < p
585  * @return The function returns 0 if the square root exists, else 1
586  **/
587 
588 uint32_t curve448Sqrt(int32_t *r, const int32_t *a, const int32_t *b)
589 {
590  uint32_t res;
591  int32_t c[16];
592  int32_t u[16];
593  int32_t v[16];
594 
595  //Compute the candidate root (A / B)^((p + 1) / 4). This can be done
596  //with the following trick, using a single modular powering for both the
597  //inversion of B and the square root: A^3 * B * (A^5 * B^3)^((p - 3) / 4)
598  curve448Sqr(u, a);
599  curve448Sqr(u, u);
600  curve448Mul(u, u, a);
601  curve448Sqr(v, b);
602  curve448Mul(v, v, b);
603 
604  //Compute C = A^5 * B^3
605  curve448Mul(c, u, v);
606 
607  //Compute U = C^((p - 3) / 4)
608  curve448Sqr(u, c);
609  curve448Mul(u, u, c); //C^(2^2 - 1)
610  curve448Sqr(u, u);
611  curve448Mul(v, u, c); //C^(2^3 - 1)
612  curve448Pwr2(u, v, 3);
613  curve448Mul(v, u, v); //C^(2^6 - 1)
614  curve448Pwr2(u, v, 6);
615  curve448Mul(u, u, v); //C^(2^12 - 1)
616  curve448Sqr(u, u);
617  curve448Mul(v, u, c); //C^(2^13 - 1)
618  curve448Pwr2(u, v, 13);
619  curve448Mul(u, u, v); //C^(2^26 - 1)
620  curve448Sqr(u, u);
621  curve448Mul(v, u, c); //C^(2^27 - 1)
622  curve448Pwr2(u, v, 27);
623  curve448Mul(u, u, v); //C^(2^54 - 1)
624  curve448Sqr(u, u);
625  curve448Mul(v, u, c); //C^(2^55 - 1)
626  curve448Pwr2(u, v, 55);
627  curve448Mul(u, u, v); //C^(2^110 - 1)
628  curve448Sqr(u, u);
629  curve448Mul(v, u, c); //C^(2^111 - 1)
630  curve448Pwr2(u, v, 111);
631  curve448Mul(v, u, v); //C^(2^222 - 1)
632  curve448Sqr(u, v);
633  curve448Mul(u, u, c); //C^(2^223 - 1)
634  curve448Pwr2(u, u, 223);
635  curve448Mul(u, u, v); //C^(2^446 - 2^222 - 1)
636 
637  //The candidate root is U = A^3 * B * (A^5 * B^3)^((p - 3) / 4)
638  curve448Sqr(v, a);
639  curve448Mul(v, v, a);
640  curve448Mul(u, u, v);
641  curve448Mul(u, u, b);
642  curve448Canonicalize(u, u);
643 
644  //Calculate C = B * U^2
645  curve448Sqr(c, u);
646  curve448Mul(c, c, b);
647  curve448Canonicalize(c, c);
648 
649  //Reduce non-canonical values of A
650  curve448Canonicalize(v, a);
651 
652  //Check whether B * U^2 = A
653  res = curve448Comp(c, v);
654 
655  //Copy the candidate root
656  curve448Copy(r, u);
657 
658  //Return 0 if the square root exists
659  return res;
660 }
661 
662 
663 /**
664  * @brief Reduce non-canonical value
665  * @param[out] r Resulting integer R = A mod p
666  * @param[in] a An integer such as 0 <= A < (2^448 - 1)
667  **/
668 
669 void curve448Canonicalize(int32_t *r, const int32_t *a)
670 {
671  uint_t i;
672  int32_t temp;
673  int32_t b[16];
674 
675  //Perform modular reduction (first pass)
676  for(temp = 0, i = 0; i < 16; i++)
677  {
678  temp += a[i];
679  r[i] = temp & 0x0FFFFFFF;
680  temp = ASR32(temp, 28);
681  }
682 
683  //Perform modular reduction (second pass)
684  for(r[8] += temp, i = 0; i < 16; i++)
685  {
686  temp += r[i];
687  r[i] = temp & 0x0FFFFFFF;
688  temp = ASR32(temp, 28);
689  }
690 
691  //Compute B = A - (2^448 - 2^224 - 1)
692  for(temp = 1, i = 0; i < 8; i++)
693  {
694  temp += r[i];
695  b[i] = temp & 0x0FFFFFFF;
696  temp = ASR32(temp, 28);
697  }
698 
699  for(temp += 1, i = 8; i < 16; i++)
700  {
701  temp += r[i];
702  b[i] = temp & 0x0FFFFFFF;
703  temp = ASR32(temp, 28);
704  }
705 
706  //Compute the highest term of the result
707  temp -= 1;
708 
709  //If B < (2^448 - 2^224 + 1) then R = B, else R = A
710  curve448Select(r, b, r, temp & 1);
711 }
712 
713 
714 /**
715  * @brief Copy an integer
716  * @param[out] a Pointer to the destination integer
717  * @param[in] b Pointer to the source integer
718  **/
719 
720 void curve448Copy(int32_t *a, const int32_t *b)
721 {
722  uint_t i;
723 
724  //Copy the value of the integer
725  for(i = 0; i < 16; i++)
726  {
727  a[i] = b[i];
728  }
729 }
730 
731 
732 /**
733  * @brief Conditional swap
734  * @param[in,out] a Pointer to the first integer
735  * @param[in,out] b Pointer to the second integer
736  * @param[in] c Condition variable
737  **/
738 
739 void curve448Swap(int32_t *a, int32_t *b, uint32_t c)
740 {
741  uint_t i;
742  uint32_t mask;
743  uint32_t dummy;
744 
745  //The mask is the all-1 or all-0 word
746  mask = ~c + 1;
747 
748  //Conditional swap
749  for(i = 0; i < 16; i++)
750  {
751  //Constant time implementation
752  dummy = mask & (a[i] ^ b[i]);
753  a[i] ^= dummy;
754  b[i] ^= dummy;
755  }
756 }
757 
758 
759 /**
760  * @brief Select an integer
761  * @param[out] r Pointer to the destination integer
762  * @param[in] a Pointer to the first source integer
763  * @param[in] b Pointer to the second source integer
764  * @param[in] c Condition variable
765  **/
766 
767 void curve448Select(int32_t *r, const int32_t *a, const int32_t *b,
768  uint32_t c)
769 {
770  uint_t i;
771  uint32_t mask;
772 
773  //The mask is the all-1 or all-0 word
774  mask = c - 1;
775 
776  //Select between A and B
777  for(i = 0; i < 16; i++)
778  {
779  //Constant time implementation
780  r[i] = (a[i] & mask) | (b[i] & ~mask);
781  }
782 }
783 
784 
785 /**
786  * @brief Compare integers
787  * @param[in] a Pointer to the first integer
788  * @param[in] b Pointer to the second integer
789  * @return The function returns 0 if the A = B, else 1
790  **/
791 
792 uint32_t curve448Comp(const int32_t *a, const int32_t *b)
793 {
794  uint_t i;
795  uint32_t mask;
796 
797  //Initialize mask
798  mask = 0;
799 
800  //Compare A and B
801  for(i = 0; i < 16; i++)
802  {
803  //Constant time implementation
804  mask |= a[i] ^ b[i];
805  }
806 
807  //Return 0 if A = B, else 1
808  return ((uint32_t) (mask | (~mask + 1))) >> 31;
809 }
810 
811 
812 /**
813  * @brief Import an octet string
814  * @param[out] a Pointer to resulting integer
815  * @param[in] data Octet string to be converted
816  **/
817 
818 void curve448Import(int32_t *a, const uint8_t *data)
819 {
820  uint_t i;
821  uint32_t temp;
822 
823  //Pack the octet string into 16 words of 28 bits
824  for(a[0] = 0, i = 0; i < 7; i++)
825  {
826  temp = LOAD32LE(data + i * 4);
827  a[i] |= (temp << (i * 4)) & 0x0FFFFFFF;
828  a[i + 1] = temp >> (28 - i * 4);
829  }
830 
831  for(a[8] = 0, i = 0; i < 7; i++)
832  {
833  temp = LOAD32LE(data + (i + 7) * 4);
834  a[i + 8] |= (temp << (i * 4)) & 0x0FFFFFFF;
835  a[i + 9] = temp >> (28 - i * 4);
836  }
837 }
838 
839 
840 /**
841  * @brief Export an octet string
842  * @param[in] a Pointer to the integer to be exported
843  * @param[out] data Octet string resulting from the conversion
844  **/
845 
846 void curve448Export(int32_t *a, uint8_t *data)
847 {
848  uint_t i;
849  uint32_t temp;
850 
851  //Unpack the 16 words of 28 bits
852  for(i = 0; i < 7; i++)
853  {
854  temp = (a[i + 1] << (28 - i * 4)) | (a[i] >> (i * 4));
855  STORE32LE(temp, data + i * 4);
856  }
857 
858  for(i = 0; i < 7; i++)
859  {
860  temp = (a[i + 9] << (28 - 4 * i)) | (a[i + 8] >> (i * 4));
861  STORE32LE(temp, data + (i + 7) * 4);
862  }
863 }
864 
865 #endif
curve448SubInt
void curve448SubInt(int32_t *r, const int32_t *a, int32_t b)
Modular subtraction.
Definition: curve448.c:232
curve448.h
Curve448 elliptic curve.
b
uint8_t b
Definition: nbns_common.h:122
curve448Comp
uint32_t curve448Comp(const int32_t *a, const int32_t *b)
Compare integers.
Definition: curve448.c:792
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:767
curve448Swap
void curve448Swap(int32_t *a, int32_t *b, uint32_t c)
Conditional swap.
Definition: curve448.c:739
data
uint8_t data[]
Definition: ethernet.h:224
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:504
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:588
res
const uint8_t res[]
curve448Inv
void curve448Inv(int32_t *r, const int32_t *a)
Modular multiplicative inverse.
Definition: curve448.c:539
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:669
curve448Mul
__weak_func void curve448Mul(int32_t *r, const int32_t *a, const int32_t *b)
Modular multiplication.
Definition: curve448.c:373
curve448Copy
void curve448Copy(int32_t *a, const int32_t *b)
Copy an integer.
Definition: curve448.c:720
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
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:518
curve448Export
void curve448Export(int32_t *a, uint8_t *data)
Export an octet string.
Definition: curve448.c:846
curve448Sub
void curve448Sub(int32_t *r, const int32_t *a, const int32_t *b)
Modular subtraction.
Definition: curve448.c:165
curve448AddInt
void curve448AddInt(int32_t *r, const int32_t *a, int32_t b)
Modular addition.
Definition: curve448.c:139
ASR64
#define ASR64(a, n)
Definition: crypto.h:1017
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
curve448MulInt
__weak_func void curve448MulInt(int32_t *r, const int32_t *a, int32_t b)
Modular multiplication.
Definition: curve448.c:479
ec.h
ECC (Elliptic Curve Cryptography)
curve448Import
void curve448Import(int32_t *a, const uint8_t *data)
Import an octet string.
Definition: curve448.c:818
ASR32
#define ASR32(a, n)
Definition: crypto.h:1013
c
uint8_t c
Definition: ndp.h:514
curve448Mul224
__weak_func void curve448Mul224(int32_t *r, const int32_t *a, const int32_t *b)
224-bit multiplication
Definition: curve448.c:258
debug.h
Debugging facilities.