ed448.c
Go to the documentation of this file.
1 /**
2  * @file ed448.c
3  * @brief Ed448 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 "ecc/ed448.h"
39 #include "debug.h"
40 
41 //Check crypto library configuration
42 #if (ED448_SUPPORT == ENABLED)
43 
44 //Base point B
45 static const Ed448Point ED448_B =
46 {
47  {
48  0xC70CC05E, 0x2626A82B, 0x8B00938E, 0x433B80E1, 0x2AB66511, 0x12AE1AF7, 0xA3D3A464,
49  0xEA6DE324, 0x470F1767, 0x9E146570, 0x22BF36DA, 0x221D15A6, 0x6BED0DED, 0x4F1970C6
50  },
51  {
52  0xF230FA14, 0x9808795B, 0x4ED7C8AD, 0xFDBD132C, 0xE67C39C4, 0x3AD3FF1C, 0x05A0C2D7,
53  0x87789C1E, 0x6CA39840, 0x4BEA7373, 0x56C9C762, 0x88762037, 0x6EB6BC24, 0x693F4671
54  },
55  {
56  0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
57  0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000
58  }
59 };
60 
61 //Zero (constant)
62 static const uint32_t ED448_ZERO[14] =
63 {
64  0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
65  0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000
66 };
67 
68 //Curve parameter d
69 static const uint32_t ED448_D[14] =
70 {
71  0xFFFF6756, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
72  0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
73 };
74 
75 //Order of the base point L
76 static const uint8_t ED448_L[60] =
77 {
78  0xF3, 0x44, 0x58, 0xAB, 0x92, 0xC2, 0x78, 0x23, 0x55, 0x8F, 0xC5, 0x8D, 0x72, 0xC2, 0x6C, 0x21,
79  0x90, 0x36, 0xD6, 0xAE, 0x49, 0xDB, 0x4E, 0xC4, 0xE9, 0x23, 0xCA, 0x7C, 0xFF, 0xFF, 0xFF, 0xFF,
80  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
81  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x3F, 0x00, 0x00, 0x00, 0x00
82 };
83 
84 //Pre-computed value of mu = b^(2 * k) / L with b = 2^24 and k = 19
85 static const uint8_t ED448_MU[60] =
86 {
87  0x0A, 0xD0, 0xE0, 0xB0, 0x7B, 0x4A, 0xD5, 0xD6, 0x73, 0xC8, 0xAD, 0x0A, 0xA7, 0x23, 0xD7, 0xD8,
88  0x33, 0xE9, 0xFD, 0x96, 0x9C, 0x12, 0x65, 0x4B, 0x12, 0xBB, 0x63, 0xC1, 0x5D, 0x33, 0x08, 0x00,
89  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
90  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x00
91 };
92 
93 
94 /**
95  * @brief EdDSA key pair generation
96  * @param[in] prngAlgo PRNG algorithm
97  * @param[in] prngContext Pointer to the PRNG context
98  * @param[out] privateKey EdDSA private key (57 bytes)
99  * @param[out] publicKey EdDSA public key (57 bytes)
100  * @return Error code
101  **/
102 
103 error_t ed448GenerateKeyPair(const PrngAlgo *prngAlgo, void *prngContext,
104  uint8_t *privateKey, uint8_t *publicKey)
105 {
106  error_t error;
107  uint8_t s[57];
108  Ed448State *state;
109 
110  //Check parameters
111  if(prngAlgo == NULL || prngContext == NULL)
113  if(privateKey == NULL || publicKey == NULL)
115 
116  //The private key is 57 octets of cryptographically secure random data
117  error = prngAlgo->read(prngContext, privateKey, ED448_PRIVATE_KEY_LEN);
118  //Any error to report?
119  if(error)
120  return error;
121 
122  //Allocate working state
123  state = cryptoAllocMem(sizeof(Ed448State));
124  //Failed to allocate memory?
125  if(state == NULL)
126  return ERROR_OUT_OF_MEMORY;
127 
128  //Hash the 57-byte private key using SHA-512
129  shake256Init(&state->shake256Context);
132 
133  //Only the lower 57 bytes are used for generating the public key. Interpret
134  //the buffer as the little-endian integer, forming a secret scalar s
135  shake256Squeeze(&state->shake256Context, s, 57);
136 
137  //The two least significant bits of the first octet are cleared, all eight
138  //bits the last octet are cleared, and the highest bit of the second to
139  //last octet is set
140  s[0] &= 0xFC;
141  s[56] = 0x00;
142  s[55] |= 0x80;
143 
144  //Perform a fixed-base scalar multiplication s * B
145  ed448Mul(state, &state->sb, s, &ED448_B);
146  //The public key A is the encoding of the point s * B
147  ed448Encode(&state->sb, publicKey);
148 
149  //Erase working state
150  cryptoMemset(state, 0, sizeof(Ed448State));
151  //Release working state
152  cryptoFreeMem(state);
153 
154  //Successful processing
155  return NO_ERROR;
156 }
157 
158 
159 /**
160  * @brief EdDSA signature generation
161  * @param[in] privateKey Signer's EdDSA private key (57 bytes)
162  * @param[in] publicKey Signer's EdDSA public key (57 bytes)
163  * @param[in] message Pointer to the message to be signed
164  * @param[in] messageLen Length of the message, in bytes
165  * @param[in] context Constant string specified by the protocol using it
166  * @param[in] contextLen Length of the context, in bytes
167  * @param[in] flag Prehash flag for Ed448ph scheme
168  * @param[out] signature EdDSA signature (114 bytes)
169  * @return Error code
170  **/
171 
172 error_t ed448GenerateSignature(const uint8_t *privateKey,
173  const uint8_t *publicKey, const void *message, size_t messageLen,
174  const void *context, uint8_t contextLen, uint8_t flag, uint8_t *signature)
175 {
176  uint8_t c;
177  Ed448State *state;
178 
179  //Check parameters
180  if(privateKey == NULL || signature == NULL)
182  if(message == NULL && messageLen != 0)
184  if(context == NULL && contextLen != 0)
186 
187  //Allocate working state
188  state = cryptoAllocMem(sizeof(Ed448State));
189  //Failed to allocate memory?
190  if(state == NULL)
191  return ERROR_OUT_OF_MEMORY;
192 
193  //Hash the private key, 57 octets, using SHAKE256(x, 114). Let h denote
194  //the resulting digest
195  shake256Init(&state->shake256Context);
198 
199  //Construct the secret scalar s from the first half of the digest
200  shake256Squeeze(&state->shake256Context, state->s, 57);
201 
202  //The two least significant bits of the first octet are cleared, all eight
203  //bits the last octet are cleared, and the highest bit of the second to
204  //last octet is set
205  state->s[0] &= 0xFC;
206  state->s[56] = 0x00;
207  state->s[55] |= 0x80;
208 
209  //The public key is optional
210  if(publicKey == NULL)
211  {
212  //Perform a fixed-base scalar multiplication s * B
213  ed448Mul(state, &state->sb, state->s, &ED448_B);
214  //The public key A is the encoding of the point s * B
215  ed448Encode(&state->sb, state->t);
216  //Point to the resulting public key
217  publicKey = state->t;
218  }
219 
220  //Let prefix denote the second half of the hash digest
221  shake256Squeeze(&state->shake256Context, state->p, 57);
222 
223  //Compute SHAKE256(dom4(F, C) || prefix || PH(M), 114)
224  shake256Init(&state->shake256Context);
225  shake256Absorb(&state->shake256Context, "SigEd448", 8);
226  shake256Absorb(&state->shake256Context, &flag, sizeof(uint8_t));
227  shake256Absorb(&state->shake256Context, &contextLen, sizeof(uint8_t));
228  shake256Absorb(&state->shake256Context, context, contextLen);
229  shake256Absorb(&state->shake256Context, state->p, 57);
230  shake256Absorb(&state->shake256Context, message, messageLen);
232  shake256Squeeze(&state->shake256Context, state->k, 114);
233 
234  //Reduce the 114-octet digest as a little-endian integer r
235  ed448RedInt(state->r, state->k);
236  //Compute the point r * B
237  ed448Mul(state, &state->rb, state->r, &ED448_B);
238  //Let the string R be the encoding of this point
239  ed448Encode(&state->rb, signature);
240 
241  //Compute SHAKE256(dom4(F, C) || R || A || PH(M), 114) and interpret the
242  //114-octet digest as a little-endian integer k
243  shake256Init(&state->shake256Context);
244  shake256Absorb(&state->shake256Context, "SigEd448", 8);
245  shake256Absorb(&state->shake256Context, &flag, sizeof(uint8_t));
246  shake256Absorb(&state->shake256Context, &contextLen, sizeof(uint8_t));
247  shake256Absorb(&state->shake256Context, context, contextLen);
250  shake256Absorb(&state->shake256Context, message, messageLen);
252  shake256Squeeze(&state->shake256Context, state->k, 114);
253 
254  //Compute S = (r + k * s) mod L. For efficiency, reduce k modulo L first
255  ed448RedInt(state->p, state->k);
256  ed448MulInt(state->k, state->k + 57, state->p, state->s, 57);
257  ed448RedInt(state->p, state->k);
258  ed448AddInt(state->s, state->p, state->r, 57);
259 
260  //Perform modular reduction
261  c = ed448SubInt(state->p, state->s, ED448_L, 57);
262  ed448SelectInt(signature + 57, state->p, state->s, c, 57);
263 
264  //Erase working state
265  cryptoMemset(state, 0, sizeof(Ed448State));
266  //Release working state
267  cryptoFreeMem(state);
268 
269  //Successful processing
270  return NO_ERROR;
271 }
272 
273 
274 /**
275  * @brief EdDSA signature verification
276  * @param[in] publicKey Signer's EdDSA public key (57 bytes)
277  * @param[in] message Message whose signature is to be verified
278  * @param[in] messageLen Length of the message, in bytes
279  * @param[in] context Constant string specified by the protocol using it
280  * @param[in] contextLen Length of the context, in bytes
281  * @param[in] flag Prehash flag for Ed448ph scheme
282  * @param[in] signature EdDSA signature (114 bytes)
283  * @return Error code
284  **/
285 
286 error_t ed448VerifySignature(const uint8_t *publicKey, const void *message,
287  size_t messageLen, const void *context, uint8_t contextLen, uint8_t flag,
288  const uint8_t *signature)
289 {
290  uint32_t ret;
291  Ed448State *state;
292 
293  //Check parameters
294  if(publicKey == NULL || signature == NULL)
296  if(message == NULL && messageLen != 0)
298  if(context == NULL && contextLen != 0)
300 
301  //Allocate working state
302  state = cryptoAllocMem(sizeof(Ed448State));
303  //Failed to allocate memory?
304  if(state == NULL)
305  return ERROR_OUT_OF_MEMORY;
306 
307  //First split the signature into two 32-octet halves. Decode the first
308  //half as a point R
310 
311  //Decode the second half as an integer S, in the range 0 <= s < L
313  ED448_SIGNATURE_LEN / 2);
314 
315  //Ed448 signatures are not malleable due to the verification check that
316  //decoded S is smaller than L (refer to RFC 8032, section 8.4)
317  ret = 1 ^ ed448SubInt(state->p, state->s, ED448_L, ED448_SIGNATURE_LEN / 2);
318 
319  //Decode the public key A as point A'
320  ret |= ed448Decode(&state->ka, publicKey);
321 
322  //Compute SHAKE256(dom4(F, C) || R || A || PH(M), 114) and interpret the
323  //114-octet digest as a little-endian integer k
324  shake256Init(&state->shake256Context);
325  shake256Absorb(&state->shake256Context, "SigEd448", 8);
326  shake256Absorb(&state->shake256Context, &flag, sizeof(uint8_t));
327  shake256Absorb(&state->shake256Context, &contextLen, sizeof(uint8_t));
328  shake256Absorb(&state->shake256Context, context, contextLen);
329  shake256Absorb(&state->shake256Context, state->r, ED448_SIGNATURE_LEN / 2);
331  shake256Absorb(&state->shake256Context, message, messageLen);
333  shake256Squeeze(&state->shake256Context, state->k, 114);
334 
335  //For efficiency, reduce k modulo L first
336  ed448RedInt(state->k, state->k);
337 
338  //Compute the point P = s * B - k * A'
339  curve448Sub(state->ka.x, ED448_ZERO, state->ka.x);
340  ed448Mul(state, &state->sb, state->s, &ED448_B);
341  ed448Mul(state, &state->ka, state->k, &state->ka);
342  ed448Add(state, &state->ka, &state->sb, &state->ka);
343 
344  //Encode of the resulting point P
345  ed448Encode(&state->ka, state->p);
346 
347  //If P = R, then the signature is verified. If P does not equal R,
348  //then the message or the signature may have been modified
349  ret |= ed448CompInt(state->p, signature, ED448_SIGNATURE_LEN / 2);
350 
351  //Erase working state
352  cryptoMemset(state, 0, sizeof(Ed448State));
353  //Release working state
354  cryptoFreeMem(state);
355 
356  //Return status code
357  return (ret == 0) ? NO_ERROR : ERROR_INVALID_SIGNATURE;
358 }
359 
360 
361 /**
362  * @brief Scalar multiplication on Ed448 curve
363  * @param[in] state Pointer to the working state
364  * @param[out] r Resulting point R = d * S
365  * @param[in] k Input scalar
366  * @param[in] p Input point
367  **/
368 
369 void ed448Mul(Ed448State *state, Ed448Point *r, const uint8_t *k,
370  const Ed448Point *p)
371 {
372  int_t i;
373  uint8_t b;
374 
375  //The neutral element is represented by (0, 1, 1)
376  curve448SetInt(state->u.x, 0);
377  curve448SetInt(state->u.y, 1);
378  curve448SetInt(state->u.z, 1);
379 
380  //Perform scalar multiplication
381  for(i = CURVE448_BIT_LEN - 1; i >= 0; i--)
382  {
383  //The scalar is processed in a left-to-right fashion
384  b = (k[i / 8] >> (i % 8)) & 1;
385 
386  //Compute U = 2 * U
387  ed448Double(state, &state->u, &state->u);
388  //Compute V = U + P
389  ed448Add(state, &state->v, &state->u, p);
390 
391  //If b is set, then U = V
392  curve448Select(state->u.x, state->u.x, state->v.x, b);
393  curve448Select(state->u.y, state->u.y, state->v.y, b);
394  curve448Select(state->u.z, state->u.z, state->v.z, b);
395  }
396 
397  //Copy result
398  curve448Copy(r->x, state->u.x);
399  curve448Copy(r->y, state->u.y);
400  curve448Copy(r->z, state->u.z);
401 }
402 
403 
404 /**
405  * @brief Point addition
406  * @param[in] state Pointer to the working state
407  * @param[out] r Resulting point R = P + Q
408  * @param[in] p First operand
409  * @param[in] q Second operand
410  **/
411 
412 void ed448Add(Ed448State *state, Ed448Point *r, const Ed448Point *p,
413  const Ed448Point *q)
414 {
415  //Compute A = X1 * X2
416  curve448Mul(state->a, p->x, q->x);
417  //Compute B = Y1 * Y2
418  curve448Mul(state->b, p->y, q->y);
419  //Compute C = Z1 * Z2
420  curve448Mul(state->c, p->z, q->z);
421  //Compute D = C^2
422  curve448Sqr(state->d, state->c);
423  //Compute E = d * A * B
424  curve448Mul(state->e, state->a, state->b);
425  curve448Mul(state->e, state->e, ED448_D);
426  //Compute F = D + E
427  curve448Add(state->f, state->d, state->e);
428  //Compute G = D - E
429  curve448Sub(state->g, state->d, state->e);
430  //Compute D = (X1 + Y1) * (X2 + Y2)
431  curve448Add(state->d, p->x, p->y);
432  curve448Add(state->e, q->x, q->y);
433  curve448Mul(state->d, state->d, state->e);
434  //Compute X3 = C * G * (D - A - B)
435  curve448Sub(state->d, state->d, state->a);
436  curve448Sub(state->d, state->d, state->b);
437  curve448Mul(state->d, state->d, state->c);
438  curve448Mul(r->x, state->d, state->g);
439  //Compute Y3 = C * F * (B - A)
440  curve448Sub(state->b, state->b, state->a);
441  curve448Mul(state->b, state->b, state->c);
442  curve448Mul(r->y, state->b, state->f);
443  //Compute Z3 = F * G
444  curve448Mul(r->z, state->f, state->g);
445 }
446 
447 
448 /**
449  * @brief Point doubling
450  * @param[in] state Pointer to the working state
451  * @param[out] r Resulting point R = 2 * P
452  * @param[in] p Input point P
453  **/
454 
456 {
457  //Compute A = X1 * X2
458  curve448Mul(state->a, p->x, p->x);
459  //Compute B = Y1 * Y2
460  curve448Mul(state->b, p->y, p->y);
461  //Compute C = Z1 * Z2
462  curve448Mul(state->c, p->z, p->z);
463  //Compute F = A + B
464  curve448Add(state->f, state->a, state->b);
465  //Compute G = F - 2 * C
466  curve448Add(state->c, state->c, state->c);
467  curve448Sub(state->g, state->f, state->c);
468  //Compute D = (X1 + Y1)^2
469  curve448Add(state->d, p->x, p->y);
470  curve448Sqr(state->d, state->d);
471  //Compute X3 = G * (D - F)
472  curve448Sub(state->d, state->d, state->f);
473  curve448Mul(r->x, state->d, state->g);
474  //Compute Y3 = F * (A - B)
475  curve448Sub(state->a, state->a, state->b);
476  curve448Mul(r->y, state->a, state->f);
477  //Compute Z3 = F * G
478  curve448Mul(r->z, state->f, state->g);
479 }
480 
481 
482 /**
483  * @brief Point encoding
484  * @param[in] p Point representation
485  * @param[out] data Octet string resulting from the conversion
486  **/
487 
488 void ed448Encode(Ed448Point *p, uint8_t *data)
489 {
490  //Retrieve affine representation
491  curve448Inv(p->z, p->z);
492  curve448Mul(p->x, p->x, p->z);
493  curve448Mul(p->y, p->y, p->z);
494  curve448SetInt(p->z, 1);
495 
496  //Encode the y-coordinate as a little-endian string of 57 octets. The final
497  //octet is always zero
498  curve448Export(p->y, data);
499  data[56] = 0;
500 
501  //Copy the least significant bit of the x-coordinate to the most significant
502  //bit of the final octet
503  data[56] |= (p->x[0] & 1) << 7;
504 }
505 
506 
507 /**
508  * @brief Point decoding
509  * @param[in] p Point representation
510  * @param[out] data Octet string to be converted
511  **/
512 
513 uint32_t ed448Decode(Ed448Point *p, const uint8_t *data)
514 {
515  uint_t i;
516  uint8_t x0;
517  uint32_t ret;
518  uint64_t temp;
519  uint32_t u[14];
520  uint32_t v[14];
521 
522  //First, interpret the string as an integer in little-endian representation.
523  //Bit 455 of this number is the least significant bit of the x-coordinate
524  //and denote this value x_0
525  x0 = data[56] >> 7;
526 
527  //The y-coordinate is recovered simply by clearing this bit
528  curve448Import(p->y, data);
529 
530  //Compute u = y + 2^224 + 1
531  for(temp = 1, i = 0; i < 7; i++)
532  {
533  temp += p->y[i];
534  u[i] = temp & 0xFFFFFFFF;
535  temp >>= 32;
536  }
537 
538  for(temp += 1, i = 7; i < 14; i++)
539  {
540  temp += p->y[i];
541  u[i] = temp & 0xFFFFFFFF;
542  temp >>= 32;
543  }
544 
545  temp += data[56] & 0x7F;
546  ret = temp & 0xFFFFFFFF;
547 
548  //If the y-coordinate is >= p, decoding fails
549  ret = (ret | (~ret + 1)) >> 31;
550 
551  //The curve equation implies x^2 = (y^2 - 1) / (d * y^2 - 1) mod p
552  //Let u = y^2 - 1 and v = d * y^2 - 1
553  curve448Sqr(v, p->y);
554  curve448SubInt(u, v, 1);
555  curve448Mul(v, v, ED448_D);
556  curve448SubInt(v, v, 1);
557 
558  //Compute u = sqrt(u / v)
559  ret |= curve448Sqrt(u, u, v);
560 
561  //If x = 0, and x_0 = 1, decoding fails
562  ret |= (curve448Comp(u, ED448_ZERO) ^ 1) & x0;
563 
564  //Compute v = p - u
565  curve448Sub(v, ED448_ZERO, u);
566 
567  //Finally, use the x_0 bit to select the right square root
568  curve448Select(p->x, u, v, (x0 ^ u[0]) & 1);
569 
570  //Initialize z-coordinate (projective representation)
571  curve448SetInt(p->z, 1);
572 
573  //Return 0 if the point has been successfully decoded, else 1
574  return ret;
575 }
576 
577 
578 /**
579  * @brief Reduce an integer modulo L
580  *
581  * This function implements Barrett reduction with b = 2^24 and k = 19. The
582  * algorithm requires the precomputation of the quantity mu = b^(2 * k) / L
583  *
584  * @param[out] r Resulting integer R = A mod L
585  * @param[in] a An integer such as 0 <= A < b^(2 * k)
586  **/
587 
588 void ed448RedInt(uint8_t *r, const uint8_t *a)
589 {
590  uint8_t c;
591  uint8_t u[60];
592  uint8_t v[60];
593 
594  //Compute the estimate of the quotient u = ((a / b^(k - 1)) * mu) / b^(k + 1)
595  ed448MulInt(NULL, u, a + 54, ED448_MU, 60);
596  //Compute v = u * L mod b^(k + 1)
597  ed448MulInt(v, NULL, u, ED448_L, 60);
598 
599  //Compute the estimate of the remainder u = a mod b^(k + 1) - v
600  //If u < 0, then u = u + b^(k + 1)
601  ed448SubInt(u, a, v, 60);
602 
603  //This estimation implies that at most two subtractions of L are required to
604  //obtain the correct remainder r
605  c = ed448SubInt(v, u, ED448_L, 60);
606  ed448SelectInt(u, v, u, c, 60);
607  c = ed448SubInt(v, u, ED448_L, 60);
608  ed448SelectInt(u, v, u, c, 60);
609 
610  //Copy the resulting remainder
611  ed448CopyInt(r, u, 57);
612 }
613 
614 
615 /**
616  * @brief Addition of two integers
617  * @param[out] r Resulting integer R = A + B
618  * @param[in] a An integer such as 0 <= A < (2^8)^n
619  * @param[in] b An integer such as 0 <= B < (2^8)^n
620  * @param[in] n Size of the operands, in bytes
621  **/
622 
623 void ed448AddInt(uint8_t *r, const uint8_t *a, const uint8_t *b, uint_t n)
624 {
625  uint_t i;
626  uint16_t temp;
627 
628  //Compute R = A + B
629  for(temp = 0, i = 0; i < n; i++)
630  {
631  temp += a[i];
632  temp += b[i];
633  r[i] = temp & 0xFF;
634  temp >>= 8;
635  }
636 }
637 
638 
639 /**
640  * @brief Subtraction of two integers
641  * @param[out] r Resulting integer R = A - B
642  * @param[in] a An integer such as 0 <= A < (2^8)^n
643  * @param[in] b An integer such as 0 <= B < (2^8)^n
644  * @param[in] n Size of the operands, in bytes
645  * @return 1 if the result is negative, else 0
646  **/
647 
648 uint8_t ed448SubInt(uint8_t *r, const uint8_t *a, const uint8_t *b, uint_t n)
649 {
650  uint_t i;
651  int16_t temp;
652 
653  //Compute R = A - B
654  for(temp = 0, i = 0; i < n; i++)
655  {
656  temp += a[i];
657  temp -= b[i];
658  r[i] = temp & 0xFF;
659  temp >>= 8;
660  }
661 
662  //Return 1 if the result of the subtraction is negative
663  return temp & 1;
664 }
665 
666 
667 /**
668  * @brief Multiplication of two integers
669  * @param[out] rl Low part of the result R = (A + B) mod (2^8)^n
670  * @param[out] rh High part of the result R = (A + B) / (2^8)^n
671  * @param[in] a An integer such as 0 <= A < (2^8)^n
672  * @param[in] b An integer such as 0 <= B < (2^8)^n
673  * @param[in] n Size of the operands, in bytes
674  **/
675 
676 void ed448MulInt(uint8_t *rl, uint8_t *rh, const uint8_t *a,
677  const uint8_t *b, uint_t n)
678 {
679  uint_t i;
680  uint_t j;
681  uint32_t c;
682  uint32_t d;
683  uint64_t temp;
684 
685  //Perform multiplication in base b = 2^24
686  n /= 3;
687 
688  //Compute the low part of the multiplication
689  for(temp = 0, i = 0; i < n; i++)
690  {
691  //The Comba's algorithm computes the products, column by column
692  for(j = 0; j <= i; j++)
693  {
694  c = LOAD24LE(a + 3 * j);
695  d = LOAD24LE(b + 3 * (i - j));
696  temp += (uint64_t) c * d;
697  }
698 
699  //At the bottom of each column, the final result is written to memory
700  if(rl != NULL)
701  {
702  STORE24LE(temp & 0xFFFFFF, rl + 3 * i);
703  }
704 
705  //Propagate the carry upwards
706  temp >>= 24;
707  }
708 
709  //Check whether the high part of the multiplication should be calculated
710  if(rh != NULL)
711  {
712  //Compute the high part of the multiplication
713  for(i = n; i < (2 * n); i++)
714  {
715  //The Comba's algorithm computes the products, column by column
716  for(j = i + 1 - n; j < n; j++)
717  {
718  c = LOAD24LE(a + 3 * j);
719  d = LOAD24LE(b + 3 * (i - j));
720  temp += (uint64_t) c * d;
721  }
722 
723  //At the bottom of each column, the final result is written to memory
724  STORE24LE(temp & 0xFFFFFF, rh + 3 * (i - n));
725 
726  //Propagate the carry upwards
727  temp >>= 24;
728  }
729  }
730 }
731 
732 
733 /**
734  * @brief Copy an integer
735  * @param[out] a Pointer to the destination integer
736  * @param[in] b Pointer to the source integer
737  * @param[in] n Size of the integers, in bytes
738  **/
739 
740 void ed448CopyInt(uint8_t *a, const uint8_t *b, uint_t n)
741 {
742  uint_t i;
743 
744  //Copy the value of the integer
745  for(i = 0; i < n; i++)
746  {
747  a[i] = b[i];
748  }
749 }
750 
751 
752 /**
753  * @brief Select an integer
754  * @param[out] r Pointer to the destination integer
755  * @param[in] a Pointer to the first source integer
756  * @param[in] b Pointer to the second source integer
757  * @param[in] c Condition variable
758  * @param[in] n Size of the integers, in bytes
759  **/
760 
761 void ed448SelectInt(uint8_t *r, const uint8_t *a, const uint8_t *b,
762  uint8_t c, uint_t n)
763 {
764  uint_t i;
765  uint8_t mask;
766 
767  //The mask is the all-1 or all-0 word
768  mask = c - 1;
769 
770  //Select between A and B
771  for(i = 0; i < n; i++)
772  {
773  //Constant time implementation
774  r[i] = (a[i] & mask) | (b[i] & ~mask);
775  }
776 }
777 
778 
779 /**
780  * @brief Compare integers
781  * @param[in] a Pointer to the first integer
782  * @param[in] b Pointer to the second integer
783  * @param[in] n Size of the integers, in bytes
784  * @return The function returns 0 if the A = B, else 1
785  **/
786 
787 uint8_t ed448CompInt(const uint8_t *a, const uint8_t *b, uint_t n)
788 {
789  uint_t i;
790  uint8_t mask;
791 
792  //Initialize mask
793  mask = 0;
794 
795  //Compare A and B
796  for(i = 0; i < n; i++)
797  {
798  //Constant time implementation
799  mask |= a[i] ^ b[i];
800  }
801 
802  //Return 0 if A = B, else 1
803  return ((uint8_t) (mask | (~mask + 1))) >> 7;
804 }
805 
806 #endif
Curve448 elliptic curve (constant-time implementation)
void ed448CopyInt(uint8_t *a, const uint8_t *b, uint_t n)
Copy an integer.
Definition: ed448.c:740
void ed448Mul(Ed448State *state, Ed448Point *r, const uint8_t *k, const Ed448Point *p)
Scalar multiplication on Ed448 curve.
Definition: ed448.c:369
uint8_t a
Definition: ndp.h:410
Common interface for pseudo-random number generators.
Definition: crypto.h:1168
signed int int_t
Definition: compiler_port.h:44
void ed448AddInt(uint8_t *r, const uint8_t *a, const uint8_t *b, uint_t n)
Addition of two integers.
Definition: ed448.c:623
void curve448Select(uint32_t *r, const uint32_t *a, const uint32_t *b, uint32_t c)
Select an integer.
Definition: curve448.c:575
uint32_t f[14]
Definition: ed448.h:90
#define CURVE448_BIT_LEN
Definition: curve448.h:38
PrngAlgoRead read
Definition: crypto.h:1176
uint8_t b[6]
Definition: dtls_misc.h:139
uint8_t p
Definition: ndp.h:298
void curve448Export(uint32_t *a, uint8_t *data)
Export an octet string.
Definition: curve448.c:647
#define ED448_PUBLIC_KEY_LEN
Definition: ed448.h:41
void curve448Copy(uint32_t *a, const uint32_t *b)
Copy an integer.
Definition: curve448.c:528
uint8_t signature
Definition: tls.h:1370
uint32_t e[14]
Definition: ed448.h:89
error_t ed448VerifySignature(const uint8_t *publicKey, const void *message, size_t messageLen, const void *context, uint8_t contextLen, uint8_t flag, const uint8_t *signature)
EdDSA signature verification.
Definition: ed448.c:286
#define ED448_SIGNATURE_LEN
Definition: ed448.h:43
@ ERROR_OUT_OF_MEMORY
Definition: error.h:63
void shake256Init(Shake256Context *context)
Initialize SHAKE256 context.
Definition: shake256.c:92
void curve448SubInt(uint32_t *r, const uint32_t *a, uint32_t b)
Modular subtraction.
Definition: curve448.c:160
Ed448Point ka
Definition: ed448.h:80
uint32_t r
Definition: ndp.h:345
void shake256Squeeze(Shake256Context *context, uint8_t *output, size_t length)
Extract data from the squeezing phase.
Definition: shake256.c:132
Ed448Point sb
Definition: ed448.h:82
void ed448RedInt(uint8_t *r, const uint8_t *a)
Reduce an integer modulo L.
Definition: ed448.c:588
#define STORE24LE(a, p)
Definition: cpu_endian.h:251
void ed448Encode(Ed448Point *p, uint8_t *data)
Point encoding.
Definition: ed448.c:488
@ ERROR_INVALID_PARAMETER
Invalid parameter.
Definition: error.h:47
error_t
Error codes.
Definition: error.h:42
void curve448Import(uint32_t *a, const uint8_t *data)
Import an octet string.
Definition: curve448.c:626
uint32_t ed448Decode(Ed448Point *p, const uint8_t *data)
Point decoding.
Definition: ed448.c:513
uint32_t a[14]
Definition: ed448.h:85
void ed448MulInt(uint8_t *rl, uint8_t *rh, const uint8_t *a, const uint8_t *b, uint_t n)
Multiplication of two integers.
Definition: ed448.c:676
void curve448Inv(uint32_t *r, const uint32_t *a)
Modular multiplicative inverse.
Definition: curve448.c:403
uint32_t z[14]
Definition: ed448.h:64
void ed448SelectInt(uint8_t *r, const uint8_t *a, const uint8_t *b, uint8_t c, uint_t n)
Select an integer.
Definition: ed448.c:761
void shake256Absorb(Shake256Context *context, const void *input, size_t length)
Absorb data.
Definition: shake256.c:106
void curve448Sqr(uint32_t *r, const uint32_t *a)
Modular squaring.
Definition: curve448.c:332
Ed448Point rb
Definition: ed448.h:81
General definitions for cryptographic algorithms.
uint8_t t[57]
Definition: ed448.h:79
uint8_t mask
Definition: web_socket.h:317
uint8_t s[57]
Definition: ed448.h:78
Shake256Context shake256Context
Definition: ed448.h:74
void curve448SetInt(uint32_t *a, uint32_t b)
Set integer value.
Definition: curve448.c:50
uint32_t d[14]
Definition: ed448.h:88
Ed448Point u
Definition: ed448.h:83
uint8_t ed448CompInt(const uint8_t *a, const uint8_t *b, uint_t n)
Compare integers.
Definition: ed448.c:787
Ed448Point v
Definition: ed448.h:84
uint32_t x[14]
Definition: ed448.h:62
#define ED448_PRIVATE_KEY_LEN
Definition: ed448.h:39
#define cryptoMemset(p, value, length)
Definition: crypto.h:636
uint8_t ed448SubInt(uint8_t *r, const uint8_t *a, const uint8_t *b, uint_t n)
Subtraction of two integers.
Definition: ed448.c:648
uint32_t y[14]
Definition: ed448.h:63
void shake256Final(Shake256Context *context)
Finish absorbing phase.
Definition: shake256.c:118
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
error_t ed448GenerateKeyPair(const PrngAlgo *prngAlgo, void *prngContext, uint8_t *privateKey, uint8_t *publicKey)
EdDSA key pair generation.
Definition: ed448.c:103
Projective point representation.
Definition: ed448.h:60
uint8_t n
#define cryptoMemcpy(dest, src, length)
Definition: crypto.h:642
#define cryptoFreeMem(p)
Definition: crypto.h:630
uint32_t b[14]
Definition: ed448.h:86
void curve448Add(uint32_t *r, const uint32_t *a, const uint32_t *b)
Modular addition.
Definition: curve448.c:72
void ed448Double(Ed448State *state, Ed448Point *r, const Ed448Point *p)
Point doubling.
Definition: ed448.c:455
uint8_t s
uint8_t message[]
Definition: chap.h:152
#define cryptoAllocMem(size)
Definition: crypto.h:625
uint8_t r[57]
Definition: ed448.h:77
uint32_t g[14]
Definition: ed448.h:91
void curve448Sub(uint32_t *r, const uint32_t *a, const uint32_t *b)
Modular subtraction.
Definition: curve448.c:123
void ed448Add(Ed448State *state, Ed448Point *r, const Ed448Point *p, const Ed448Point *q)
Point addition.
Definition: ed448.c:412
void curve448Mul(uint32_t *r, const uint32_t *a, const uint32_t *b)
Modular multiplication.
Definition: curve448.c:199
uint8_t p[57]
Definition: ed448.h:76
unsigned int uint_t
Definition: compiler_port.h:45
Elliptic curves.
uint8_t data[]
Definition: dtls_misc.h:176
#define LOAD24LE(p)
Definition: cpu_endian.h:175
@ ERROR_INVALID_SIGNATURE
Definition: error.h:223
Ed448 elliptic curve (constant-time implementation)
error_t ed448GenerateSignature(const uint8_t *privateKey, const uint8_t *publicKey, const void *message, size_t messageLen, const void *context, uint8_t contextLen, uint8_t flag, uint8_t *signature)
EdDSA signature generation.
Definition: ed448.c:172
Ed448 working state.
Definition: ed448.h:72
uint32_t c[14]
Definition: ed448.h:87
uint32_t curve448Comp(const uint32_t *a, const uint32_t *b)
Compare integers.
Definition: curve448.c:600
@ NO_ERROR
Success.
Definition: error.h:44
uint8_t c
Definition: ndp.h:513
Debugging facilities.
uint8_t k[114]
Definition: ed448.h:75