ed25519.c
Go to the documentation of this file.
1 /**
2  * @file ed25519.c
3  * @brief Ed25519 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/curve25519.h"
36 #include "ecc/ed25519.h"
37 #include "debug.h"
38 
39 //Check crypto library configuration
40 #if (ED25519_SUPPORT == ENABLED)
41 
42 //Base point B
43 static const Ed25519Point ED25519_B =
44 {
45  {
46  0x8F25D51A, 0xC9562D60, 0x9525A7B2, 0x692CC760,
47  0xFDD6DC5C, 0xC0A4E231, 0xCD6E53FE, 0x216936D3
48  },
49  {
50  0x66666658, 0x66666666, 0x66666666, 0x66666666,
51  0x66666666, 0x66666666, 0x66666666, 0x66666666
52  },
53  {
54  0x00000001, 0x00000000, 0x00000000, 0x00000000,
55  0x00000000, 0x00000000, 0x00000000, 0x00000000
56  },
57  {
58  0xA5B7DDA3, 0x6DDE8AB3, 0x775152F5, 0x20F09F80,
59  0x64ABE37D, 0x66EA4E8E, 0xD78B7665, 0x67875F0F
60  }
61 };
62 
63 //Zero (constant)
64 static const uint32_t ED25519_ZERO[8] =
65 {
66  0x00000000, 0x00000000, 0x00000000, 0x00000000,
67  0x00000000, 0x00000000, 0x00000000, 0x00000000
68 };
69 
70 //Curve parameter d
71 static const uint32_t ED25519_D[8] =
72 {
73  0x135978A3, 0x75EB4DCA, 0x4141D8AB, 0x00700A4D,
74  0x7779E898, 0x8CC74079, 0x2B6FFE73, 0x52036CEE
75 };
76 
77 //Pre-computed value of 2 * d
78 static const uint32_t ED25519_2D[8] =
79 {
80  0x26B2F159, 0xEBD69B94, 0x8283B156, 0x00E0149A,
81  0xEEF3D130, 0x198E80F2, 0x56DFFCE7, 0x2406D9DC
82 };
83 
84 //Order of the base point L
85 static const uint8_t ED25519_L[33] =
86 {
87  0xED, 0xD3, 0xF5, 0x5C, 0x1A, 0x63, 0x12, 0x58,
88  0xD6, 0x9C, 0xF7, 0xA2, 0xDE, 0xF9, 0xDE, 0x14,
89  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
90  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10,
91  0x00,
92 };
93 
94 //Pre-computed value of mu = b^(2 * k) / L with b = 2^8 and k = 32
95 static const uint8_t ED25519_MU[33] =
96 {
97  0x1B, 0x13, 0x2C, 0x0A, 0xA3, 0xE5, 0x9C, 0xED,
98  0xA7, 0x29, 0x63, 0x08, 0x5D, 0x21, 0x06, 0x21,
99  0xEB, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
100  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
101  0x0F
102 };
103 
104 
105 /**
106  * @brief EdDSA key pair generation
107  * @param[in] prngAlgo PRNG algorithm
108  * @param[in] prngContext Pointer to the PRNG context
109  * @param[out] privateKey EdDSA private key (32 bytes)
110  * @param[out] publicKey EdDSA public key (32 bytes)
111  * @return Error code
112  **/
113 
114 error_t ed25519GenerateKeyPair(const PrngAlgo *prngAlgo, void *prngContext,
115  uint8_t *privateKey, uint8_t *publicKey)
116 {
117  error_t error;
118  uint8_t *s;
119  Ed25519State *state;
120 
121  //Check parameters
122  if(prngAlgo == NULL || prngContext == NULL)
124  if(privateKey == NULL || publicKey == NULL)
126 
127  //The private key is 32 octets of cryptographically secure random data
128  error = prngAlgo->read(prngContext, privateKey, ED25519_PRIVATE_KEY_LEN);
129  //Any error to report?
130  if(error)
131  return error;
132 
133  //Allocate working state
134  state = cryptoAllocMem(sizeof(Ed25519State));
135  //Failed to allocate memory?
136  if(state == NULL)
137  return ERROR_OUT_OF_MEMORY;
138 
139  //Hash the 32-byte private key using SHA-512
140  sha512Init(&state->sha512Context);
141  sha512Update(&state->sha512Context, privateKey, ED25519_PRIVATE_KEY_LEN);
142  sha512Final(&state->sha512Context, NULL);
143 
144  //Only the lower 32 bytes are used for generating the public key. Interpret
145  //the buffer as the little-endian integer, forming a secret scalar s
146  s = state->sha512Context.digest;
147 
148  //The lowest three bits of the first octet are cleared, the highest bit
149  //of the last octet is cleared, and the second highest bit of the last
150  //octet is set
151  s[0] &= 0xF8;
152  s[31] &= 0x7F;
153  s[31] |= 0x40;
154 
155  //Perform a fixed-base scalar multiplication s * B
156  ed25519Mul(state, &state->sb, s, &ED25519_B);
157  //The public key A is the encoding of the point s * B
158  ed25519Encode(&state->sb, publicKey);
159 
160  //Erase working state
161  cryptoMemset(state, 0, sizeof(Ed25519State));
162  //Release working state
163  cryptoFreeMem(state);
164 
165  //Successful processing
166  return NO_ERROR;
167 }
168 
169 
170 /**
171  * @brief EdDSA signature generation
172  * @param[in] privateKey Signer's EdDSA private key (32 bytes)
173  * @param[in] publicKey Signer's EdDSA public key (32 bytes)
174  * @param[in] message Pointer to the message to be signed
175  * @param[in] messageLen Length of the message, in bytes
176  * @param[in] context Constant string specified by the protocol using it
177  * @param[in] contextLen Length of the context, in bytes
178  * @param[in] flag Prehash flag for Ed25519ph scheme
179  * @param[out] signature EdDSA signature (64 bytes)
180  * @return Error code
181  **/
182 
183 error_t ed25519GenerateSignature(const uint8_t *privateKey,
184  const uint8_t *publicKey, const void *message, size_t messageLen,
185  const void *context, uint8_t contextLen, uint8_t flag, uint8_t *signature)
186 {
187  uint8_t c;
188  Ed25519State *state;
189 
190  //Check parameters
191  if(privateKey == NULL || signature == NULL)
193  if(message == NULL && messageLen != 0)
195  if(context == NULL && contextLen != 0)
197 
198  //Allocate working state
199  state = cryptoAllocMem(sizeof(Ed25519State));
200  //Failed to allocate memory?
201  if(state == NULL)
202  return ERROR_OUT_OF_MEMORY;
203 
204  //Hash the private key, 32 octets, using SHA-512. Let h denote the
205  //resulting digest
206  sha512Init(&state->sha512Context);
207  sha512Update(&state->sha512Context, privateKey, ED25519_PRIVATE_KEY_LEN);
208  sha512Final(&state->sha512Context, NULL);
209 
210  //Construct the secret scalar s from the first half of the digest
211  cryptoMemcpy(state->s, state->sha512Context.digest, 32);
212 
213  //The lowest three bits of the first octet are cleared, the highest bit
214  //of the last octet is cleared, and the second highest bit of the last
215  //octet is set
216  state->s[0] &= 0xF8;
217  state->s[31] &= 0x7F;
218  state->s[31] |= 0x40;
219 
220  //The public key is optional
221  if(publicKey == NULL)
222  {
223  //Perform a fixed-base scalar multiplication s * B
224  ed25519Mul(state, &state->sb, state->s, &ED25519_B);
225  //The public key A is the encoding of the point s * B
226  ed25519Encode(&state->sb, state->k);
227  //Point to the resulting public key
228  publicKey = state->k;
229  }
230 
231  //Let prefix denote the second half of the hash digest
232  cryptoMemcpy(state->p, state->sha512Context.digest + 32, 32);
233 
234  //Initialize SHA-512 context
235  sha512Init(&state->sha512Context);
236 
237  //For Ed25519ctx and Ed25519ph schemes, dom2(x, y) is the octet string
238  //"SigEd25519 no Ed25519 collisions" || octet(x) || octet(OLEN(y)) || y,
239  //where x is in range 0-255 and y is an octet string of at most 255 octets
240  if(context != NULL || flag != 0)
241  {
242  sha512Update(&state->sha512Context, "SigEd25519 no Ed25519 collisions", 32);
243  sha512Update(&state->sha512Context, &flag, sizeof(uint8_t));
244  sha512Update(&state->sha512Context, &contextLen, sizeof(uint8_t));
245  sha512Update(&state->sha512Context, context, contextLen);
246  }
247 
248  //Compute SHA-512(dom2(F, C) || prefix || PH(M))
249  sha512Update(&state->sha512Context, state->p, 32);
250  sha512Update(&state->sha512Context, message, messageLen);
251  sha512Final(&state->sha512Context, NULL);
252 
253  //Reduce the 64-octet digest as a little-endian integer r
254  ed25519RedInt(state->r, state->sha512Context.digest);
255  //Compute the point r * B
256  ed25519Mul(state, &state->rb, state->r, &ED25519_B);
257  //Let the string R be the encoding of this point
258  ed25519Encode(&state->rb, signature);
259 
260  //Initialize SHA-512 context
261  sha512Init(&state->sha512Context);
262 
263  //For Ed25519ctx and Ed25519ph schemes, dom2(x, y) is the octet string
264  //"SigEd25519 no Ed25519 collisions" || octet(x) || octet(OLEN(y)) || y,
265  //where x is in range 0-255 and y is an octet string of at most 255 octets
266  if(context != NULL || flag != 0)
267  {
268  sha512Update(&state->sha512Context, "SigEd25519 no Ed25519 collisions", 32);
269  sha512Update(&state->sha512Context, &flag, sizeof(uint8_t));
270  sha512Update(&state->sha512Context, &contextLen, sizeof(uint8_t));
271  sha512Update(&state->sha512Context, context, contextLen);
272  }
273 
274  //Compute SHA512(dom2(F, C) || R || A || PH(M)) and interpret the 64-octet
275  //digest as a little-endian integer k
278  sha512Update(&state->sha512Context, message, messageLen);
279  sha512Final(&state->sha512Context, state->k);
280 
281  //Compute S = (r + k * s) mod L. For efficiency, reduce k modulo L first
282  ed25519RedInt(state->p, state->k);
283  ed25519MulInt(state->k, state->k + 32, state->p, state->s, 32);
284  ed25519RedInt(state->p, state->k);
285  ed25519AddInt(state->s, state->p, state->r, 32);
286 
287  //Perform modular reduction
288  c = ed25519SubInt(state->p, state->s, ED25519_L, 32);
289  ed25519SelectInt(signature + 32, state->p, state->s, c, 32);
290 
291  //Erase working state
292  cryptoMemset(state, 0, sizeof(Ed25519State));
293  //Release working state
294  cryptoFreeMem(state);
295 
296  //Successful processing
297  return NO_ERROR;
298 }
299 
300 
301 /**
302  * @brief EdDSA signature verification
303  * @param[in] publicKey Signer's EdDSA public key (32 bytes)
304  * @param[in] message Message whose signature is to be verified
305  * @param[in] messageLen Length of the message, in bytes
306  * @param[in] context Constant string specified by the protocol using it
307  * @param[in] contextLen Length of the context, in bytes
308  * @param[in] flag Prehash flag for Ed25519ph scheme
309  * @param[in] signature EdDSA signature (64 bytes)
310  * @return Error code
311  **/
312 
313 error_t ed25519VerifySignature(const uint8_t *publicKey, const void *message,
314  size_t messageLen, const void *context, uint8_t contextLen, uint8_t flag,
315  const uint8_t *signature)
316 {
317  uint32_t ret;
318  Ed25519State *state;
319 
320  //Check parameters
321  if(publicKey == NULL || signature == NULL)
323  if(message == NULL && messageLen != 0)
325  if(context == NULL && contextLen != 0)
327 
328  //Allocate working state
329  state = cryptoAllocMem(sizeof(Ed25519State));
330  //Failed to allocate memory?
331  if(state == NULL)
332  return ERROR_OUT_OF_MEMORY;
333 
334  //First split the signature into two 32-octet halves. Decode the first
335  //half as a point R
337 
338  //Decode the second half as an integer S, in the range 0 <= s < L
341 
342  //Decode the public key A as point A'
343  ret = ed25519Decode(&state->ka, publicKey);
344 
345  //Initialize SHA-512 context
346  sha512Init(&state->sha512Context);
347 
348  //For Ed25519ctx and Ed25519ph schemes, dom2(x, y) is the octet string
349  //"SigEd25519 no Ed25519 collisions" || octet(x) || octet(OLEN(y)) || y,
350  //where x is in range 0-255 and y is an octet string of at most 255 octets
351  if(context != NULL || flag != 0)
352  {
353  sha512Update(&state->sha512Context, "SigEd25519 no Ed25519 collisions", 32);
354  sha512Update(&state->sha512Context, &flag, sizeof(uint8_t));
355  sha512Update(&state->sha512Context, &contextLen, sizeof(uint8_t));
356  sha512Update(&state->sha512Context, context, contextLen);
357  }
358 
359  //Compute SHA512(dom2(F, C) || R || A || PH(M))
360  sha512Update(&state->sha512Context, state->r, ED25519_SIGNATURE_LEN / 2);
362  sha512Update(&state->sha512Context, message, messageLen);
363 
364  //Interpret the 64-octet digest as a little-endian integer k
365  sha512Final(&state->sha512Context, state->k);
366 
367  //For efficiency, reduce k modulo L first
368  ed25519RedInt(state->k, state->k);
369 
370  //Compute the point P = s * B - k * A'
371  curve25519Sub(state->ka.x, ED25519_ZERO, state->ka.x);
372  curve25519Sub(state->ka.t, ED25519_ZERO, state->ka.t);
373  ed25519Mul(state, &state->sb, state->s, &ED25519_B);
374  ed25519Mul(state, &state->ka, state->k, &state->ka);
375  ed25519Add(state, &state->ka, &state->sb, &state->ka);
376 
377  //Encode of the resulting point P
378  ed25519Encode(&state->ka, state->p);
379 
380  //If P = R, then the signature is verified. If P does not equal R,
381  //then the message or the signature may have been modified
382  ret |= ed25519CompInt(state->p, signature, ED25519_SIGNATURE_LEN / 2);
383 
384  //Erase working state
385  cryptoMemset(state, 0, sizeof(Ed25519State));
386  //Release working state
387  cryptoFreeMem(state);
388 
389  //Return status code
390  return (ret == 0) ? NO_ERROR : ERROR_INVALID_SIGNATURE;
391 }
392 
393 
394 /**
395  * @brief Scalar multiplication on Ed25519 curve
396  * @param[in] state Pointer to the working state
397  * @param[out] r Resulting point R = d * S
398  * @param[in] k Input scalar
399  * @param[in] p Input point
400  **/
401 
402 void ed25519Mul(Ed25519State *state, Ed25519Point *r, const uint8_t *k,
403  const Ed25519Point *p)
404 {
405  int_t i;
406  uint8_t b;
407 
408  //The neutral element is represented by (0, 1, 1, 0)
409  curve25519SetInt(state->u.x, 0);
410  curve25519SetInt(state->u.y, 1);
411  curve25519SetInt(state->u.z, 1);
412  curve25519SetInt(state->u.t, 0);
413 
414  //Perform scalar multiplication
415  for(i = CURVE25519_BIT_LEN - 1; i >= 0; i--)
416  {
417  //The scalar is processed in a left-to-right fashion
418  b = (k[i / 8] >> (i % 8)) & 1;
419 
420  //Compute U = 2 * U
421  ed25519Double(state, &state->u, &state->u);
422  //Compute V = U + P
423  ed25519Add(state, &state->v, &state->u, p);
424 
425  //If b is set, then U = V
426  curve25519Select(state->u.x, state->u.x, state->v.x, b);
427  curve25519Select(state->u.y, state->u.y, state->v.y, b);
428  curve25519Select(state->u.z, state->u.z, state->v.z, b);
429  curve25519Select(state->u.t, state->u.t, state->v.t, b);
430  }
431 
432  //Copy result
433  curve25519Copy(r->x, state->u.x);
434  curve25519Copy(r->y, state->u.y);
435  curve25519Copy(r->z, state->u.z);
436  curve25519Copy(r->t, state->u.t);
437 }
438 
439 
440 /**
441  * @brief Point addition
442  * @param[in] state Pointer to the working state
443  * @param[out] r Resulting point R = P + Q
444  * @param[in] p First operand
445  * @param[in] q Second operand
446  * @return Error code
447  **/
448 
450  const Ed25519Point *q)
451 {
452  //Compute A = (Y1 + X1) * (Y2 + X2)
453  curve25519Add(state->c, p->y, p->x);
454  curve25519Add(state->d, q->y, q->x);
455  curve25519Mul(state->a, state->c, state->d);
456  //Compute B = (Y1 - X1) * (Y2 - X2)
457  curve25519Sub(state->c, p->y, p->x);
458  curve25519Sub(state->d, q->y, q->x);
459  curve25519Mul(state->b, state->c, state->d);
460  //Compute C = 2 * Z1 * Z2
461  curve25519Mul(state->c, p->z, q->z);
462  curve25519Add(state->c, state->c, state->c);
463  //Compute D = (2 * d) * T1 * T2
464  curve25519Mul(state->d, p->t, q->t);
465  curve25519Mul(state->d, state->d, ED25519_2D);
466  //Compute E = A + B
467  curve25519Add(state->e, state->a, state->b);
468  //Compute F = A - B
469  curve25519Sub(state->f, state->a, state->b);
470  //Compute G = C + D
471  curve25519Add(state->g, state->c, state->d);
472  //Compute H = C - D
473  curve25519Sub(state->h, state->c, state->d);
474  //Compute X3 = F * H
475  curve25519Mul(r->x, state->f, state->h);
476  //Compute Y3 = E * G
477  curve25519Mul(r->y, state->e, state->g);
478  //Compute Z3 = G * H
479  curve25519Mul(r->z, state->g, state->h);
480  //Compute T3 = E * F
481  curve25519Mul(r->t, state->e, state->f);
482 }
483 
484 
485 /**
486  * @brief Point doubling
487  * @param[in] state Pointer to the working state
488  * @param[out] r Resulting point R = 2 * P
489  * @param[in] p Input point P
490  **/
491 
493 {
494  //Compute A = X1^2
495  curve25519Sqr(state->a, p->x);
496  //Compute B = Y1^2
497  curve25519Sqr(state->b, p->y);
498  //Compute C = 2 * Z1^2
499  curve25519Sqr(state->c, p->z);
500  curve25519Add(state->c, state->c, state->c);
501  //Compute E = A + B
502  curve25519Add(state->e, state->a, state->b);
503  //Compute F = E - (X1 + Y1)^2
504  curve25519Add(state->f, p->x, p->y);
505  curve25519Sqr(state->f, state->f);
506  curve25519Sub(state->f, state->e, state->f);
507  //Compute G = A - B
508  curve25519Sub(state->g, state->a, state->b);
509  //Compute H = C + G
510  curve25519Add(state->h, state->c, state->g);
511  //Compute X3 = F * H
512  curve25519Mul(r->x, state->f, state->h);
513  //Compute Y3 = E * G
514  curve25519Mul(r->y, state->e, state->g);
515  //Compute Z3 = G * H
516  curve25519Mul(r->z, state->g, state->h);
517  //Compute T3 = E * F
518  curve25519Mul(r->t, state->e, state->f);
519 }
520 
521 
522 /**
523  * @brief Point encoding
524  * @param[in] p Point representation
525  * @param[out] data Octet string resulting from the conversion
526  **/
527 
529 {
530  //Retrieve affine representation
531  curve25519Inv(p->z, p->z);
532  curve25519Mul(p->x, p->x, p->z);
533  curve25519Mul(p->y, p->y, p->z);
534  curve25519SetInt(p->z, 1);
535  curve25519Mul(p->t, p->x, p->y);
536 
537  //Encode the y-coordinate as a little-endian string of 32 octets. The most
538  //significant bit of the final octet is always zero
539  curve25519Export(p->y, data);
540 
541  //Copy the least significant bit of the x-coordinate to the most significant
542  //bit of the final octet
543  data[31] |= (p->x[0] & 1) << 7;
544 }
545 
546 
547 /**
548  * @brief Point decoding
549  * @param[in] p Point representation
550  * @param[out] data Octet string to be converted
551  **/
552 
553 uint32_t ed25519Decode(Ed25519Point *p, const uint8_t *data)
554 {
555  uint_t i;
556  uint8_t x0;
557  uint32_t ret;
558  uint64_t temp;
559  uint32_t u[8];
560  uint32_t v[8];
561 
562  //First, interpret the string as an integer in little-endian representation.
563  //Bit 255 of this number is the least significant bit of the x-coordinate
564  //and denote this value x_0
565  x0 = data[31] >> 7;
566 
567  //The y-coordinate is recovered simply by clearing this bit
568  curve25519Import(p->y, data);
569  p->y[7] &= 0x7FFFFFFF;
570 
571  //Compute u = y + 19
572  for(temp = 19, i = 0; i < 8; i++)
573  {
574  temp += p->y[i];
575  u[i] = temp & 0xFFFFFFFF;
576  temp >>= 32;
577  }
578 
579  //If the y-coordinate is >= p, decoding fails
580  ret = (u[7] >> 31) & 1;
581 
582  //The curve equation implies x^2 = (y^2 - 1) / (d * y^2 + 1) mod p
583  //Let u = y^2 - 1 and v = d * y^2 + 1
584  curve25519Sqr(v, p->y);
585  curve25519SubInt(u, v, 1);
586  curve25519Mul(v, v, ED25519_D);
587  curve25519AddInt(v, v, 1);
588 
589  //Compute u = sqrt(u / v)
590  ret |= curve25519Sqrt(u, u, v);
591 
592  //If x = 0, and x_0 = 1, decoding fails
593  ret |= (curve25519Comp(u, ED25519_ZERO) ^ 1) & x0;
594 
595  //Compute v = p - u
596  curve25519Sub(v, ED25519_ZERO, u);
597 
598  //Finally, use the x_0 bit to select the right square root
599  curve25519Select(p->x, u, v, (x0 ^ u[0]) & 1);
600 
601  //Calculate extended point representation
602  curve25519SetInt(p->z, 1);
603  curve25519Mul(p->t, p->x, p->y);
604 
605  //Return 0 if the point has been successfully decoded, else 1
606  return ret;
607 }
608 
609 
610 /**
611  * @brief Reduce an integer modulo L
612  *
613  * This function implements Barrett reduction with b = 2^8 and k = 32. The
614  * algorithm requires the precomputation of the quantity mu = b^(2 * k) / L
615  *
616  * @param[out] r Resulting integer R = A mod L
617  * @param[in] a An integer such as 0 <= A < b^(2 * k)
618  **/
619 
620 void ed25519RedInt(uint8_t *r, const uint8_t *a)
621 {
622  uint8_t c;
623  uint8_t u[33];
624  uint8_t v[33];
625 
626  //Compute the estimate of the quotient u = ((a / b^(k - 1)) * mu) / b^(k + 1)
627  ed25519MulInt(NULL, u, a + 31, ED25519_MU, 33);
628  //Compute v = u * L mod b^(k + 1)
629  ed25519MulInt(v, NULL, u, ED25519_L, 33);
630 
631  //Compute the estimate of the remainder u = a mod b^(k + 1) - v
632  //If u < 0, then u = u + b^(k + 1)
633  ed25519SubInt(u, a, v, 33);
634 
635  //This estimation implies that at most two subtractions of L are required to
636  //obtain the correct remainder r
637  c = ed25519SubInt(v, u, ED25519_L, 33);
638  ed25519SelectInt(u, v, u, c, 33);
639  c = ed25519SubInt(v, u, ED25519_L, 33);
640  ed25519SelectInt(u, v, u, c, 33);
641 
642  //Copy the resulting remainder
643  ed25519CopyInt(r, u, 32);
644 }
645 
646 
647 /**
648  * @brief Addition of two integers
649  * @param[out] r Resulting integer R = A + B
650  * @param[in] a An integer such as 0 <= A < (2^8)^n
651  * @param[in] b An integer such as 0 <= B < (2^8)^n
652  * @param[in] n Size of the operands, in bytes
653  **/
654 
655 void ed25519AddInt(uint8_t *r, const uint8_t *a, const uint8_t *b, uint_t n)
656 {
657  uint_t i;
658  uint16_t temp;
659 
660  //Compute R = A + B
661  for(temp = 0, i = 0; i < n; i++)
662  {
663  temp += a[i];
664  temp += b[i];
665  r[i] = temp & 0xFF;
666  temp >>= 8;
667  }
668 }
669 
670 
671 /**
672  * @brief Subtraction of two integers
673  * @param[out] r Resulting integer R = A - B
674  * @param[in] a An integer such as 0 <= A < (2^8)^n
675  * @param[in] b An integer such as 0 <= B < (2^8)^n
676  * @param[in] n Size of the operands, in bytes
677  * @return 1 if the result is negative, else 0
678  **/
679 
680 uint8_t ed25519SubInt(uint8_t *r, const uint8_t *a, const uint8_t *b, uint_t n)
681 {
682  uint_t i;
683  int16_t temp;
684 
685  //Compute R = A - B
686  for(temp = 0, i = 0; i < n; i++)
687  {
688  temp += a[i];
689  temp -= b[i];
690  r[i] = temp & 0xFF;
691  temp >>= 8;
692  }
693 
694  //Return 1 if the result of the subtraction is negative
695  return temp & 1;
696 }
697 
698 
699 /**
700  * @brief Multiplication of two integers
701  * @param[out] rl Low part of the result R = (A + B) mod (2^8)^n
702  * @param[out] rh High part of the result R = (A + B) / (2^8)^n
703  * @param[in] a An integer such as 0 <= A < (2^8)^n
704  * @param[in] b An integer such as 0 <= B < (2^8)^n
705  * @param[in] n Size of the operands, in bytes
706  **/
707 
708 void ed25519MulInt(uint8_t *rl, uint8_t *rh, const uint8_t *a,
709  const uint8_t *b, uint_t n)
710 {
711  uint_t i;
712  uint_t j;
713  uint32_t temp;
714 
715  //Compute the low part of the multiplication
716  for(temp = 0, i = 0; i < n; i++)
717  {
718  //The Comba's algorithm computes the products, column by column
719  for(j = 0; j <= i; j++)
720  {
721  temp += (uint16_t) a[j] * b[i - j];
722  }
723 
724  //At the bottom of each column, the final result is written to memory
725  if(rl != NULL)
726  {
727  rl[i] = temp & 0xFF;
728  }
729 
730  //Propagate the carry upwards
731  temp >>= 8;
732  }
733 
734  //Check whether the high part of the multiplication should be calculated
735  if(rh != NULL)
736  {
737  //Compute the high part of the multiplication
738  for(i = n; i < (2 * n); i++)
739  {
740  //The Comba's algorithm computes the products, column by column
741  for(j = i + 1 - n; j < n; j++)
742  {
743  temp += (uint16_t) a[j] * b[i - j];
744  }
745 
746  //At the bottom of each column, the final result is written to memory
747  rh[i - n] = temp & 0xFF;
748 
749  //Propagate the carry upwards
750  temp >>= 8;
751  }
752  }
753 }
754 
755 
756 /**
757  * @brief Copy an integer
758  * @param[out] a Pointer to the destination integer
759  * @param[in] b Pointer to the source integer
760  * @param[in] n Size of the integers, in bytes
761  **/
762 
763 void ed25519CopyInt(uint8_t *a, const uint8_t *b, uint_t n)
764 {
765  uint_t i;
766 
767  //Copy the value of the integer
768  for(i = 0; i < n; i++)
769  {
770  a[i] = b[i];
771  }
772 }
773 
774 
775 /**
776  * @brief Select an integer
777  * @param[out] r Pointer to the destination integer
778  * @param[in] a Pointer to the first source integer
779  * @param[in] b Pointer to the second source integer
780  * @param[in] c Condition variable
781  * @param[in] n Size of the integers, in bytes
782  **/
783 
784 void ed25519SelectInt(uint8_t *r, const uint8_t *a, const uint8_t *b,
785  uint8_t c, uint_t n)
786 {
787  uint_t i;
788  uint8_t mask;
789 
790  //The mask is the all-1 or all-0 word
791  mask = c - 1;
792 
793  //Select between A and B
794  for(i = 0; i < n; i++)
795  {
796  //Constant time implementation
797  r[i] = (a[i] & mask) | (b[i] & ~mask);
798  }
799 }
800 
801 
802 /**
803  * @brief Compare integers
804  * @param[in] a Pointer to the first integer
805  * @param[in] b Pointer to the second integer
806  * @param[in] n Size of the integers, in bytes
807  * @return The function returns 0 if the A = B, else 1
808  **/
809 
810 uint8_t ed25519CompInt(const uint8_t *a, const uint8_t *b, uint_t n)
811 {
812  uint_t i;
813  uint8_t mask;
814 
815  //Initialize mask
816  mask = 0;
817 
818  //Compare A and B
819  for(i = 0; i < n; i++)
820  {
821  //Constant time implementation
822  mask |= a[i] ^ b[i];
823  }
824 
825  //Return 0 if A = B, else 1
826  return ((uint8_t) (mask | (~mask + 1))) >> 7;
827 }
828 
829 #endif
Sha512Context sha512Context
Definition: ed25519.h:73
void curve25519Inv(uint32_t *r, const uint32_t *a)
Modular multiplicative inverse.
Definition: curve25519.c:378
Ed25519Point ka
Definition: ed25519.h:78
void curve25519AddInt(uint32_t *r, const uint32_t *a, uint32_t b)
Modular addition.
Definition: curve25519.c:103
uint32_t ed25519Decode(Ed25519Point *p, const uint8_t *data)
Point decoding.
Definition: ed25519.c:553
uint8_t c
Definition: ndp.h:510
#define cryptoMemcpy(dest, src, length)
Definition: crypto.h:590
uint32_t a[8]
Definition: ed25519.h:83
#define cryptoFreeMem(p)
Definition: crypto.h:578
uint8_t ed25519SubInt(uint8_t *r, const uint8_t *a, const uint8_t *b, uint_t n)
Subtraction of two integers.
Definition: ed25519.c:680
#define ED25519_PRIVATE_KEY_LEN
Definition: ed25519.h:37
Debugging facilities.
void ed25519Double(Ed25519State *state, Ed25519Point *r, const Ed25519Point *p)
Point doubling.
Definition: ed25519.c:492
Extended point representation.
Definition: ed25519.h:58
void ed25519Mul(Ed25519State *state, Ed25519Point *r, const uint8_t *k, const Ed25519Point *p)
Scalar multiplication on Ed25519 curve.
Definition: ed25519.c:402
uint8_t p
Definition: ndp.h:295
void curve25519Mul(uint32_t *r, const uint32_t *a, const uint32_t *b)
Modular multiplication.
Definition: curve25519.c:189
#define cryptoAllocMem(size)
Definition: crypto.h:573
uint8_t message[]
Definition: chap.h:150
uint32_t e[8]
Definition: ed25519.h:87
General definitions for cryptographic algorithms.
Invalid parameter.
Definition: error.h:45
error_t ed25519GenerateSignature(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: ed25519.c:183
uint32_t y[8]
Definition: ed25519.h:61
void curve25519Export(uint32_t *a, uint8_t *data)
Export an octet string.
Definition: curve25519.c:632
uint32_t g[8]
Definition: ed25519.h:89
uint32_t b[8]
Definition: ed25519.h:84
void ed25519AddInt(uint8_t *r, const uint8_t *a, const uint8_t *b, uint_t n)
Addition of two integers.
Definition: ed25519.c:655
#define ED25519_SIGNATURE_LEN
Definition: ed25519.h:41
void curve25519Select(uint32_t *r, const uint32_t *a, const uint32_t *b, uint32_t c)
Select an integer.
Definition: curve25519.c:560
uint32_t t[8]
Definition: ed25519.h:63
void sha512Final(Sha512Context *context, uint8_t *digest)
Finish the SHA-512 message digest.
Definition: sha512.c:213
uint8_t k[64]
Definition: ed25519.h:74
Curve25519 elliptic curve (constant-time implementation)
uint8_t a
Definition: ndp.h:407
Elliptic curves.
uint32_t d[8]
Definition: ed25519.h:86
void curve25519SetInt(uint32_t *a, uint32_t b)
Set integer value.
Definition: curve25519.c:55
uint32_t z[8]
Definition: ed25519.h:62
uint8_t mask
Definition: web_socket.h:315
void ed25519Encode(Ed25519Point *p, uint8_t *data)
Point encoding.
Definition: ed25519.c:528
signed int int_t
Definition: compiler_port.h:42
void ed25519CopyInt(uint8_t *a, const uint8_t *b, uint_t n)
Copy an integer.
Definition: ed25519.c:763
void curve25519Copy(uint32_t *a, const uint32_t *b)
Copy an integer.
Definition: curve25519.c:513
Ed25519Point rb
Definition: ed25519.h:79
void ed25519RedInt(uint8_t *r, const uint8_t *a)
Reduce an integer modulo L.
Definition: ed25519.c:620
Ed25519 elliptic curve (constant-time implementation)
Ed25519Point sb
Definition: ed25519.h:80
uint32_t f[8]
Definition: ed25519.h:88
error_t ed25519GenerateKeyPair(const PrngAlgo *prngAlgo, void *prngContext, uint8_t *privateKey, uint8_t *publicKey)
EdDSA key pair generation.
Definition: ed25519.c:114
void curve25519Sqr(uint32_t *r, const uint32_t *a)
Modular squaring.
Definition: curve25519.c:315
uint8_t signature
Definition: tls.h:1364
void curve25519Add(uint32_t *r, const uint32_t *a, const uint32_t *b)
Modular addition.
Definition: curve25519.c:77
uint8_t s
uint32_t c[8]
Definition: ed25519.h:85
void ed25519MulInt(uint8_t *rl, uint8_t *rh, const uint8_t *a, const uint8_t *b, uint_t n)
Multiplication of two integers.
Definition: ed25519.c:708
void sha512Update(Sha512Context *context, const void *data, size_t length)
Update the SHA-512 context with a portion of the message being hashed.
Definition: sha512.c:174
Success.
Definition: error.h:42
uint32_t curve25519Comp(const uint32_t *a, const uint32_t *b)
Compare integers.
Definition: curve25519.c:585
Ed25519Point v
Definition: ed25519.h:82
error_t
Error codes.
Definition: error.h:40
unsigned int uint_t
Definition: compiler_port.h:43
uint8_t data[]
Definition: dtls_misc.h:167
uint32_t curve25519Sqrt(uint32_t *r, const uint32_t *a, const uint32_t *b)
Compute the square root of (A / B) modulo p.
Definition: curve25519.c:428
Common interface for pseudo-random number generators.
Definition: crypto.h:1091
void curve25519Sub(uint32_t *r, const uint32_t *a, const uint32_t *b)
Modular subtraction.
Definition: curve25519.c:128
uint32_t r
Definition: ndp.h:342
error_t ed25519VerifySignature(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: ed25519.c:313
void curve25519Import(uint32_t *a, const uint8_t *data)
Import an octet string.
Definition: curve25519.c:611
void sha512Init(Sha512Context *context)
Initialize SHA-512 message digest context.
Definition: sha512.c:148
uint32_t h[8]
Definition: ed25519.h:90
uint8_t r[32]
Definition: ed25519.h:76
#define cryptoMemset(p, value, length)
Definition: crypto.h:584
uint8_t s[32]
Definition: ed25519.h:77
uint8_t digest[64]
Definition: sha512.h:59
uint8_t n
uint32_t x[8]
Definition: ed25519.h:60
Ed25519Point u
Definition: ed25519.h:81
#define ED25519_PUBLIC_KEY_LEN
Definition: ed25519.h:39
uint8_t p[32]
Definition: ed25519.h:75
uint8_t b[6]
Definition: dtls_misc.h:130
PrngAlgoRead read
Definition: crypto.h:1099
uint8_t ed25519CompInt(const uint8_t *a, const uint8_t *b, uint_t n)
Compare integers.
Definition: ed25519.c:810
Ed25519 working state.
Definition: ed25519.h:71
void ed25519SelectInt(uint8_t *r, const uint8_t *a, const uint8_t *b, uint8_t c, uint_t n)
Select an integer.
Definition: ed25519.c:784
#define CURVE25519_BIT_LEN
Definition: curve25519.h:36
void ed25519Add(Ed25519State *state, Ed25519Point *r, const Ed25519Point *p, const Ed25519Point *q)
Point addition.
Definition: ed25519.c:449
void curve25519SubInt(uint32_t *r, const uint32_t *a, uint32_t b)
Modular subtraction.
Definition: curve25519.c:157