ecdh.c
Go to the documentation of this file.
1 /**
2  * @file ecdh.c
3  * @brief ECDH (Elliptic Curve Diffie-Hellman) key exchange
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/ecdh.h"
37 #include "ecc/x25519.h"
38 #include "ecc/x448.h"
39 #include "debug.h"
40 
41 //Check crypto library configuration
42 #if (ECDH_SUPPORT == ENABLED)
43 
44 
45 /**
46  * @brief Initialize ECDH context
47  * @param[in] context Pointer to the ECDH context
48  **/
49 
50 void ecdhInit(EcdhContext *context)
51 {
52  //Initialize EC domain parameters
53  ecInitDomainParameters(&context->params);
54 
55  //Initialize private and public keys
56  mpiInit(&context->da);
57  ecInit(&context->qa);
58  ecInit(&context->qb);
59 }
60 
61 
62 /**
63  * @brief Release ECDH context
64  * @param[in] context Pointer to the ECDH context
65  **/
66 
67 void ecdhFree(EcdhContext *context)
68 {
69  //Release EC domain parameters
70  ecFreeDomainParameters(&context->params);
71 
72  //Release private and public keys
73  mpiFree(&context->da);
74  ecFree(&context->qa);
75  ecFree(&context->qb);
76 }
77 
78 
79 /**
80  * @brief ECDH key pair generation
81  * @param[in] context Pointer to the ECDH context
82  * @param[in] prngAlgo PRNG algorithm
83  * @param[in] prngContext Pointer to the PRNG context
84  * @return Error code
85  **/
86 
88  const PrngAlgo *prngAlgo, void *prngContext)
89 {
90  error_t error;
91 
92  //Debug message
93  TRACE_DEBUG("Generating ECDH key pair...\r\n");
94 
95  //Weierstrass elliptic curve?
96  if(context->params.type == EC_CURVE_TYPE_SECT_K1 ||
97  context->params.type == EC_CURVE_TYPE_SECT_R1 ||
98  context->params.type == EC_CURVE_TYPE_SECT_R2 ||
99  context->params.type == EC_CURVE_TYPE_SECP_K1 ||
100  context->params.type == EC_CURVE_TYPE_SECP_R1 ||
101  context->params.type == EC_CURVE_TYPE_SECP_R2 ||
103  {
104  uint_t n;
105 
106  //Let N be the bit length of q
107  n = mpiGetBitLength(&context->params.q);
108 
109  //Generated a pseudorandom number
110  error = mpiRand(&context->da, n, prngAlgo, prngContext);
111 
112  //Check status code
113  if(!error)
114  {
115  //Make sure that 0 < da < q
116  if(mpiComp(&context->da, &context->params.q) >= 0)
117  {
118  error = mpiShiftRight(&context->da, 1);
119  }
120  }
121 
122  //Check status code
123  if(!error)
124  {
125  //Debug message
126  TRACE_DEBUG(" Private key:\r\n");
127  TRACE_DEBUG_MPI(" ", &context->da);
128 
129  //Compute Qa = da.G
130  error = ecMult(&context->params, &context->qa, &context->da,
131  &context->params.g);
132  }
133 
134  //Check status code
135  if(!error)
136  {
137  //Convert the public key to affine representation
138  error = ecAffinify(&context->params, &context->qa, &context->qa);
139  }
140 
141  //Check status code
142  if(!error)
143  {
144  //Debug message
145  TRACE_DEBUG(" Public key X:\r\n");
146  TRACE_DEBUG_MPI(" ", &context->qa.x);
147  TRACE_DEBUG(" Public key Y:\r\n");
148  TRACE_DEBUG_MPI(" ", &context->qa.y);
149  }
150  }
151 #if (X25519_SUPPORT == ENABLED)
152  //Curve25519 elliptic curve?
153  else if(context->params.type == EC_CURVE_TYPE_X25519)
154  {
155  uint8_t da[CURVE25519_BYTE_LEN];
156  uint8_t qa[CURVE25519_BYTE_LEN];
157  uint8_t g[CURVE25519_BYTE_LEN];
158 
159  //Generate 32 random bytes
160  error = prngAlgo->read(prngContext, da, CURVE25519_BYTE_LEN);
161 
162  //Check status code
163  if(!error)
164  {
165  //Debug message
166  TRACE_DEBUG(" Private key:\r\n");
168 
169  //Get the u-coordinate of the base point
170  error = mpiExport(&context->params.g.x, g, CURVE25519_BYTE_LEN,
172  }
173 
174  //Check status code
175  if(!error)
176  {
177  //Generate the public value using X25519 function
178  error = x25519(qa, da, g);
179  }
180 
181  //Check status code
182  if(!error)
183  {
184  //Save private key
185  error = mpiImport(&context->da, da, CURVE25519_BYTE_LEN,
187  }
188 
189  //Check status code
190  if(!error)
191  {
192  //Debug message
193  TRACE_DEBUG(" Public key:\r\n");
195 
196  //Save public key
197  error = mpiImport(&context->qa.x, qa, CURVE25519_BYTE_LEN,
199  }
200  }
201 #endif
202 #if (X448_SUPPORT == ENABLED)
203  //Curve448 elliptic curve?
204  else if(context->params.type == EC_CURVE_TYPE_X448)
205  {
206  uint8_t da[CURVE448_BYTE_LEN];
207  uint8_t qa[CURVE448_BYTE_LEN];
208  uint8_t g[CURVE448_BYTE_LEN];
209 
210  //Generate 56 random bytes
211  error = prngAlgo->read(prngContext, da, CURVE448_BYTE_LEN);
212 
213  //Check status code
214  if(!error)
215  {
216  //Debug message
217  TRACE_DEBUG(" Private key:\r\n");
219 
220  //Get the u-coordinate of the base point
221  error = mpiExport(&context->params.g.x, g, CURVE448_BYTE_LEN,
223  }
224 
225  //Check status code
226  if(!error)
227  {
228  //Generate the public value using X448 function
229  error = x448(qa, da, g);
230  }
231 
232  //Check status code
233  if(!error)
234  {
235  //Save private key
236  error = mpiImport(&context->da, da, CURVE448_BYTE_LEN,
238  }
239 
240  //Check status code
241  if(!error)
242  {
243  //Debug message
244  TRACE_DEBUG(" Public key:\r\n");
246 
247  //Save public key
248  error = mpiImport(&context->qa.x, qa, CURVE448_BYTE_LEN,
250  }
251  }
252 #endif
253  //Invalid elliptic curve?
254  else
255  {
256  //Report an error
257  error = ERROR_INVALID_TYPE;
258  }
259 
260  //Return status code
261  return error;
262 }
263 
264 
265 /**
266  * @brief Check ECDH public key
267  * @param[in] params EC domain parameters
268  * @param[in] publicKey Public key to be checked
269  * @return Error code
270  **/
271 
273 {
274  bool_t valid;
275 
276  //Initialize flag
277  valid = FALSE;
278 
279  //Weierstrass elliptic curve?
280  if(params->type == EC_CURVE_TYPE_SECT_K1 ||
281  params->type == EC_CURVE_TYPE_SECT_R1 ||
282  params->type == EC_CURVE_TYPE_SECT_R2 ||
283  params->type == EC_CURVE_TYPE_SECP_K1 ||
284  params->type == EC_CURVE_TYPE_SECP_R1 ||
285  params->type == EC_CURVE_TYPE_SECP_R2 ||
287  {
288  //Verify that 0 <= Qx < p
289  if(mpiCompInt(&publicKey->x, 0) >= 0 &&
290  mpiComp(&publicKey->x, &params->p) < 0)
291  {
292  //Verify that 0 <= Qy < p
293  if(mpiCompInt(&publicKey->y, 0) >= 0 &&
294  mpiComp(&publicKey->y, &params->p) < 0)
295  {
296  //Check whether the point is on the curve
297  valid = ecIsPointAffine(params, publicKey);
298  }
299  }
300 
301  //Valid point?
302  if(valid)
303  {
304  //If the cofactor is not 1, the implementation must verify that n.Q
305  //is the point at the infinity
306  if(params->h != 1)
307  {
308  error_t error;
309  EcPoint r;
310 
311  //Initialize flag
312  valid = FALSE;
313  //Initialize EC points
314  ecInit(&r);
315 
316  //Convert the peer's public key to projective representation
317  error = ecProjectify(params, publicKey, publicKey);
318 
319  //Check status code
320  if(!error)
321  {
322  //Compute R = n.Q
323  error = ecMult(params, &r, &params->q, publicKey);
324  }
325 
326  //Check status code
327  if(!error)
328  {
329  //Verify that the result is the point at the infinity
330  if(mpiCompInt(&r.z, 0) == 0)
331  {
332  valid = TRUE;
333  }
334  }
335 
336  //Release EC point
337  ecFree(&r);
338  }
339  }
340  }
341 #if (X25519_SUPPORT == ENABLED)
342  //Curve25519 elliptic curve?
343  else if(params->type == EC_CURVE_TYPE_X25519)
344  {
345  //The public key does not need to be validated
346  valid = TRUE;
347  }
348 #endif
349 #if (X448_SUPPORT == ENABLED)
350  //Curve448 elliptic curve?
351  else if(params->type == EC_CURVE_TYPE_X448)
352  {
353  //The public key does not need to be validated
354  valid = TRUE;
355  }
356 #endif
357  //Invalid elliptic curve?
358  else
359  {
360  //Just for sanity
361  valid = FALSE;
362  }
363 
364  //Return status code
365  if(valid)
366  {
367  return NO_ERROR;
368  }
369  else
370  {
372  }
373 }
374 
375 
376 /**
377  * @brief Compute ECDH shared secret
378  * @param[in] context Pointer to the ECDH context
379  * @param[out] output Buffer where to store the shared secret
380  * @param[in] outputSize Size of the buffer in bytes
381  * @param[out] outputLen Length of the resulting shared secret
382  * @return Error code
383  **/
384 
386  uint8_t *output, size_t outputSize, size_t *outputLen)
387 {
388  error_t error;
389 
390  //Debug message
391  TRACE_DEBUG("Computing Diffie-Hellman shared secret...\r\n");
392 
393  //Weierstrass elliptic curve?
394  if(context->params.type == EC_CURVE_TYPE_SECT_K1 ||
395  context->params.type == EC_CURVE_TYPE_SECT_R1 ||
396  context->params.type == EC_CURVE_TYPE_SECT_R2 ||
397  context->params.type == EC_CURVE_TYPE_SECP_K1 ||
398  context->params.type == EC_CURVE_TYPE_SECP_R1 ||
399  context->params.type == EC_CURVE_TYPE_SECP_R2 ||
401  {
402  size_t k;
403  EcPoint z;
404 
405  //Get the length in octets of the prime modulus
406  k = mpiGetByteLength(&context->params.p);
407 
408  //Make sure that the output buffer is large enough
409  if(outputSize >= k)
410  {
411  //Length of the resulting shared secret
412  *outputLen = k;
413 
414  //Initialize EC points
415  ecInit(&z);
416 
417  //Convert the peer's public key to projective representation
418  error = ecProjectify(&context->params, &context->qb, &context->qb);
419 
420  //Check status code
421  if(!error)
422  {
423  //Compute Z = da.Qb
424  error = ecMult(&context->params, &z, &context->da, &context->qb);
425  }
426 
427  //Check status code
428  if(!error)
429  {
430  //Convert Z to affine representation
431  error = ecAffinify(&context->params, &z, &z);
432  }
433 
434  //Check status code
435  if(!error)
436  {
437  //The shared secret is the x-coordinate of Z
438  error = mpiExport(&z.x, output, k, MPI_FORMAT_BIG_ENDIAN);
439  }
440 
441  //Release EC point
442  ecFree(&z);
443  }
444  else
445  {
446  //Report an error
447  error = ERROR_INVALID_LENGTH;
448  }
449  }
450 #if (X25519_SUPPORT == ENABLED)
451  //Curve25519 elliptic curve?
452  else if(context->params.type == EC_CURVE_TYPE_X25519)
453  {
454  uint_t i;
455  uint8_t mask;
456  uint8_t da[CURVE25519_BYTE_LEN];
457  uint8_t qb[CURVE25519_BYTE_LEN];
458 
459  //Make sure that the output buffer is large enough
460  if(outputSize >= CURVE25519_BYTE_LEN)
461  {
462  //Length of the resulting shared secret
463  *outputLen = CURVE25519_BYTE_LEN;
464 
465  //Retrieve private key
466  error = mpiExport(&context->da, da, CURVE25519_BYTE_LEN,
468 
469  //Check status code
470  if(!error)
471  {
472  //Get peer's public key
473  error = mpiExport(&context->qb.x, qb, CURVE25519_BYTE_LEN,
475  }
476 
477  //Check status code
478  if(!error)
479  {
480  //Generate shared secret K using X25519 function
481  error = x25519(output, da, qb);
482  }
483 
484  //Since Curve25519 has a cofactor of 8, an input point of small order
485  //will eliminate any contribution from the other party's private key
486  if(!error)
487  {
488  //This situation can be detected by checking for the all-zero output
489  for(mask = 0, i = 0; i < CURVE25519_BYTE_LEN; i++)
490  {
491  mask |= output[i];
492  }
493 
494  //Check whether K is the all-zero value and abort if so (refer to
495  //RFC 8422, sections 5.10 and 5.11)
496  if(mask == 0)
497  {
498  error = ERROR_ILLEGAL_PARAMETER;
499  }
500  }
501  }
502  else
503  {
504  //Report an error
505  error = ERROR_INVALID_LENGTH;
506  }
507  }
508 #endif
509 #if (X448_SUPPORT == ENABLED)
510  //Curve448 elliptic curve?
511  else if(context->params.type == EC_CURVE_TYPE_X448)
512  {
513  uint_t i;
514  uint8_t mask;
515  uint8_t da[CURVE448_BYTE_LEN];
516  uint8_t qb[CURVE448_BYTE_LEN];
517 
518  //Make sure that the output buffer is large enough
519  if(outputSize >= CURVE448_BYTE_LEN)
520  {
521  //Length of the resulting shared secret
522  *outputLen = CURVE448_BYTE_LEN;
523 
524  //Retrieve private key
525  error = mpiExport(&context->da, da, CURVE448_BYTE_LEN,
527 
528  //Check status code
529  if(!error)
530  {
531  //Get peer's public key
532  error = mpiExport(&context->qb.x, qb, CURVE448_BYTE_LEN,
534  }
535 
536  //Check status code
537  if(!error)
538  {
539  //Generate shared secret K using X448 function
540  error = x448(output, da, qb);
541  }
542 
543  //Since Curve448 has a cofactor of 4, an input point of small order
544  //will eliminate any contribution from the other party's private key
545  if(!error)
546  {
547  //This situation can be detected by checking for the all-zero output
548  for(mask = 0, i = 0; i < CURVE448_BYTE_LEN; i++)
549  {
550  mask |= output[i];
551  }
552 
553  //Check whether K is the all-zero value and abort if so (refer to
554  //RFC 8422, sections 5.10 and 5.11)
555  if(mask == 0)
556  {
557  error = ERROR_ILLEGAL_PARAMETER;
558  }
559  }
560  }
561  else
562  {
563  //Report an error
564  error = ERROR_INVALID_LENGTH;
565  }
566  }
567 #endif
568  //Invalid elliptic curve?
569  else
570  {
571  //Report an error
572  error = ERROR_INVALID_TYPE;
573  }
574 
575  //Check status code
576  if(!error)
577  {
578  //Debug message
579  TRACE_DEBUG(" Shared secret (%" PRIuSIZE " bytes):\r\n", *outputLen);
580  TRACE_DEBUG_ARRAY(" ", output, *outputLen);
581  }
582 
583  //Return status code
584  return error;
585 }
586 
587 #endif
int bool_t
Definition: compiler_port.h:49
Mpi p
Prime.
Definition: ec.h:67
Common interface for pseudo-random number generators.
Definition: crypto.h:1168
error_t x448(uint8_t *r, const uint8_t *k, const uint8_t *u)
X448 function (scalar multiplication on Curve448)
Definition: x448.c:53
@ ERROR_ILLEGAL_PARAMETER
Definition: error.h:237
void ecInitDomainParameters(EcDomainParameters *params)
Initialize EC domain parameters.
Definition: ec.c:55
PrngAlgoRead read
Definition: crypto.h:1176
#define TRUE
Definition: os_port.h:50
void ecdhFree(EcdhContext *context)
Release ECDH context.
Definition: ecdh.c:67
EcPoint qa
One's own public key.
Definition: ecdh.h:52
#define CURVE448_BYTE_LEN
Definition: curve448.h:39
EcPoint g
Base point G.
Definition: ec.h:70
EcPoint qb
Peer's public key.
Definition: ecdh.h:53
ECDH (Elliptic Curve Diffie-Hellman) key exchange.
uint32_t h
Cofactor h.
Definition: ec.h:72
error_t mpiShiftRight(Mpi *r, uint_t n)
Right shift operation.
Definition: mpi.c:1073
@ EC_CURVE_TYPE_SECP_K1
Definition: ec_curves.h:270
error_t mpiRand(Mpi *r, uint_t length, const PrngAlgo *prngAlgo, void *prngContext)
Generate a random value.
Definition: mpi.c:468
Mpi y
y-coordinate
Definition: ec.h:54
error_t mpiImport(Mpi *r, const uint8_t *data, uint_t length, MpiFormat format)
Octet string to integer conversion.
Definition: mpi.c:533
EC domain parameters.
Definition: ec.h:63
__weak error_t ecMult(const EcDomainParameters *params, EcPoint *r, const Mpi *d, const EcPoint *s)
Scalar multiplication.
Definition: ec.c:835
@ EC_CURVE_TYPE_X448
Definition: ec_curves.h:275
void ecFreeDomainParameters(EcDomainParameters *params)
Release EC domain parameters.
Definition: ec.c:75
void mpiInit(Mpi *r)
Initialize a multiple precision integer.
Definition: mpi.c:48
error_t x25519(uint8_t *r, const uint8_t *k, const uint8_t *u)
X25519 function (scalar multiplication on Curve25519)
Definition: x25519.c:53
X448 function implementation.
uint32_t r
Definition: ndp.h:345
#define FALSE
Definition: os_port.h:46
@ EC_CURVE_TYPE_SECP_R1
Definition: ec_curves.h:271
error_t mpiExport(const Mpi *a, uint8_t *data, uint_t length, MpiFormat format)
Integer to octet string conversion.
Definition: mpi.c:618
@ MPI_FORMAT_LITTLE_ENDIAN
Definition: mpi.h:60
error_t
Error codes.
Definition: error.h:42
#define CURVE25519_BYTE_LEN
Definition: curve25519.h:39
Mpi da
One's own private key.
Definition: ecdh.h:51
void ecInit(EcPoint *r)
Initialize elliptic curve point.
Definition: ec.c:156
@ EC_CURVE_TYPE_SECT_R1
Definition: ec_curves.h:268
__weak bool_t ecIsPointAffine(const EcDomainParameters *params, const EcPoint *s)
Check whether the affine point S is on the curve.
Definition: ec.c:414
@ ERROR_INVALID_LENGTH
Definition: error.h:109
@ EC_CURVE_TYPE_SECT_K1
Definition: ec_curves.h:267
General definitions for cryptographic algorithms.
Mpi x
x-coordinate
Definition: ec.h:53
uint8_t mask
Definition: web_socket.h:317
@ ERROR_INVALID_TYPE
Definition: error.h:113
Elliptic curve point.
Definition: ec.h:51
error_t ecProjectify(const EcDomainParameters *params, EcPoint *r, const EcPoint *s)
Compute projective representation.
Definition: ec.c:344
X25519 function implementation.
@ EC_CURVE_TYPE_SECT_R2
Definition: ec_curves.h:269
uint_t mpiGetBitLength(const Mpi *a)
Get the actual length in bits.
Definition: mpi.c:195
error_t ecdhComputeSharedSecret(EcdhContext *context, uint8_t *output, size_t outputSize, size_t *outputLen)
Compute ECDH shared secret.
Definition: ecdh.c:385
uint8_t z
Definition: dns_common.h:175
#define TRACE_DEBUG(...)
Definition: debug.h:106
void ecdhInit(EcdhContext *context)
Initialize ECDH context.
Definition: ecdh.c:50
__weak error_t ecAffinify(const EcDomainParameters *params, EcPoint *r, const EcPoint *s)
Recover affine representation.
Definition: ec.c:368
#define TRACE_DEBUG_ARRAY(p, a, n)
Definition: debug.h:107
uint8_t n
@ EC_CURVE_TYPE_X25519
Definition: ec_curves.h:274
@ EC_CURVE_TYPE_SECP_R2
Definition: ec_curves.h:272
@ MPI_FORMAT_BIG_ENDIAN
Definition: mpi.h:61
EcCurveType type
Curve type.
Definition: ec.h:66
int_t mpiComp(const Mpi *a, const Mpi *b)
Compare two multiple precision integers.
Definition: mpi.c:295
#define PRIuSIZE
Definition: compiler_port.h:78
unsigned int uint_t
Definition: compiler_port.h:45
#define TRACE_DEBUG_MPI(p, a)
Definition: debug.h:109
void ecFree(EcPoint *r)
Release an elliptic curve point.
Definition: ec.c:170
int_t mpiCompInt(const Mpi *a, int_t b)
Compare a multiple precision integer with an integer.
Definition: mpi.c:339
@ EC_CURVE_TYPE_BRAINPOOLP_R1
Definition: ec_curves.h:273
error_t ecdhCheckPublicKey(const EcDomainParameters *params, EcPoint *publicKey)
Check ECDH public key.
Definition: ecdh.c:272
Mpi q
Order of the point G.
Definition: ec.h:71
EcDomainParameters params
Definition: ecdh.h:50
ECDH context.
Definition: ecdh.h:48
@ NO_ERROR
Success.
Definition: error.h:44
Debugging facilities.
error_t ecdhGenerateKeyPair(EcdhContext *context, const PrngAlgo *prngAlgo, void *prngContext)
ECDH key pair generation.
Definition: ecdh.c:87
uint_t mpiGetByteLength(const Mpi *a)
Get the actual length in bytes.
Definition: mpi.c:156
void mpiFree(Mpi *r)
Release a multiple precision integer.
Definition: mpi.c:62