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