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