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