NimBLE-Arduino 2.1.2
Loading...
Searching...
No Matches
ecc.h
Go to the documentation of this file.
1/* ecc.h - TinyCrypt interface to common ECC functions */
2
3/* Copyright (c) 2014, Kenneth MacKay
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * * Redistributions of source code must retain the above copyright notice, this
10 * list of conditions and the following disclaimer.
11 *
12 * * Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/*
30 * Copyright (C) 2017 by Intel Corporation, All Rights Reserved.
31 *
32 * Redistribution and use in source and binary forms, with or without
33 * modification, are permitted provided that the following conditions are met:
34 *
35 * - Redistributions of source code must retain the above copyright notice,
36 * this list of conditions and the following disclaimer.
37 *
38 * - Redistributions in binary form must reproduce the above copyright
39 * notice, this list of conditions and the following disclaimer in the
40 * documentation and/or other materials provided with the distribution.
41 *
42 * - Neither the name of Intel Corporation nor the names of its contributors
43 * may be used to endorse or promote products derived from this software
44 * without specific prior written permission.
45 *
46 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
47 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
48 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
49 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
50 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
51 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
52 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
53 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
54 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
55 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
56 * POSSIBILITY OF SUCH DAMAGE.
57 */
58
71#ifndef __TC_UECC_H__
72#define __TC_UECC_H__
73
74#include <stdint.h>
75
76#ifdef __cplusplus
77extern "C" {
78#endif
79
80/* Word size (4 bytes considering 32-bits architectures) */
81#define uECC_WORD_SIZE 4
82
83/* setting max number of calls to prng: */
84#ifndef uECC_RNG_MAX_TRIES
85#define uECC_RNG_MAX_TRIES 64
86#endif
87
88/* defining data types to store word and bit counts: */
89typedef int8_t wordcount_t;
90typedef int16_t bitcount_t;
91/* defining data type for comparison result: */
92typedef int8_t cmpresult_t;
93/* defining data type to store ECC coordinate/point in 32bits words: */
94typedef unsigned int uECC_word_t;
95/* defining data type to store an ECC coordinate/point in 64bits words: */
96typedef uint64_t uECC_dword_t;
97
98/* defining masks useful for ecc computations: */
99#define HIGH_BIT_SET 0x80000000
100#define uECC_WORD_BITS 32
101#define uECC_WORD_BITS_SHIFT 5
102#define uECC_WORD_BITS_MASK 0x01F
103
104/* Number of words of 32 bits to represent an element of the the curve p-256: */
105#define NUM_ECC_WORDS 8
106/* Number of bytes to represent an element of the the curve p-256: */
107#define NUM_ECC_BYTES (uECC_WORD_SIZE*NUM_ECC_WORDS)
108
109/* structure that represents an elliptic curve (e.g. p256):*/
110struct uECC_Curve_t;
111typedef const struct uECC_Curve_t * uECC_Curve;
112struct uECC_Curve_t {
113 wordcount_t num_words;
114 wordcount_t num_bytes;
115 bitcount_t num_n_bits;
116 uECC_word_t p[NUM_ECC_WORDS];
117 uECC_word_t n[NUM_ECC_WORDS];
118 uECC_word_t G[NUM_ECC_WORDS * 2];
119 uECC_word_t b[NUM_ECC_WORDS];
120 void (*double_jacobian)(uECC_word_t * X1, uECC_word_t * Y1, uECC_word_t * Z1,
121 uECC_Curve curve);
122 void (*x_side)(uECC_word_t *result, const uECC_word_t *x, uECC_Curve curve);
123 void (*mmod_fast)(uECC_word_t *result, uECC_word_t *product);
124};
125
126/*
127 * @brief computes doubling of point ion jacobian coordinates, in place.
128 * @param X1 IN/OUT -- x coordinate
129 * @param Y1 IN/OUT -- y coordinate
130 * @param Z1 IN/OUT -- z coordinate
131 * @param curve IN -- elliptic curve
132 */
133void double_jacobian_default(uECC_word_t * X1, uECC_word_t * Y1,
134 uECC_word_t * Z1, uECC_Curve curve);
135
136/*
137 * @brief Computes x^3 + ax + b. result must not overlap x.
138 * @param result OUT -- x^3 + ax + b
139 * @param x IN -- value of x
140 * @param curve IN -- elliptic curve
141 */
142void x_side_default(uECC_word_t *result, const uECC_word_t *x,
143 uECC_Curve curve);
144
145/*
146 * @brief Computes result = product % curve_p
147 * from http://www.nsa.gov/ia/_files/nist-routines.pdf
148 * @param result OUT -- product % curve_p
149 * @param product IN -- value to be reduced mod curve_p
150 */
151void vli_mmod_fast_secp256r1(unsigned int *result, unsigned int *product);
152
153/* Bytes to words ordering: */
154#define BYTES_TO_WORDS_8(a, b, c, d, e, f, g, h) 0x##d##c##b##a, 0x##h##g##f##e
155#define BYTES_TO_WORDS_4(a, b, c, d) 0x##d##c##b##a
156#define BITS_TO_WORDS(num_bits) \
157 ((num_bits + ((uECC_WORD_SIZE * 8) - 1)) / (uECC_WORD_SIZE * 8))
158#define BITS_TO_BYTES(num_bits) ((num_bits + 7) / 8)
159
160/* definition of curve NIST p-256: */
161static const struct uECC_Curve_t curve_secp256r1 = {
162 NUM_ECC_WORDS,
163 NUM_ECC_BYTES,
164 256, /* num_n_bits */ {
165 BYTES_TO_WORDS_8(FF, FF, FF, FF, FF, FF, FF, FF),
166 BYTES_TO_WORDS_8(FF, FF, FF, FF, 00, 00, 00, 00),
167 BYTES_TO_WORDS_8(00, 00, 00, 00, 00, 00, 00, 00),
168 BYTES_TO_WORDS_8(01, 00, 00, 00, FF, FF, FF, FF)
169 }, {
170 BYTES_TO_WORDS_8(51, 25, 63, FC, C2, CA, B9, F3),
171 BYTES_TO_WORDS_8(84, 9E, 17, A7, AD, FA, E6, BC),
172 BYTES_TO_WORDS_8(FF, FF, FF, FF, FF, FF, FF, FF),
173 BYTES_TO_WORDS_8(00, 00, 00, 00, FF, FF, FF, FF)
174 }, {
175 BYTES_TO_WORDS_8(96, C2, 98, D8, 45, 39, A1, F4),
176 BYTES_TO_WORDS_8(A0, 33, EB, 2D, 81, 7D, 03, 77),
177 BYTES_TO_WORDS_8(F2, 40, A4, 63, E5, E6, BC, F8),
178 BYTES_TO_WORDS_8(47, 42, 2C, E1, F2, D1, 17, 6B),
179
180 BYTES_TO_WORDS_8(F5, 51, BF, 37, 68, 40, B6, CB),
181 BYTES_TO_WORDS_8(CE, 5E, 31, 6B, 57, 33, CE, 2B),
182 BYTES_TO_WORDS_8(16, 9E, 0F, 7C, 4A, EB, E7, 8E),
183 BYTES_TO_WORDS_8(9B, 7F, 1A, FE, E2, 42, E3, 4F)
184 }, {
185 BYTES_TO_WORDS_8(4B, 60, D2, 27, 3E, 3C, CE, 3B),
186 BYTES_TO_WORDS_8(F6, B0, 53, CC, B0, 06, 1D, 65),
187 BYTES_TO_WORDS_8(BC, 86, 98, 76, 55, BD, EB, B3),
188 BYTES_TO_WORDS_8(E7, 93, 3A, AA, D8, 35, C6, 5A)
189 },
190 &double_jacobian_default,
191 &x_side_default,
192 &vli_mmod_fast_secp256r1
193};
194
195uECC_Curve uECC_secp256r1(void);
196
197/*
198 * @brief Generates a random integer in the range 0 < random < top.
199 * Both random and top have num_words words.
200 * @param random OUT -- random integer in the range 0 < random < top
201 * @param top IN -- upper limit
202 * @param num_words IN -- number of words
203 * @return a random integer in the range 0 < random < top
204 */
205int uECC_generate_random_int(uECC_word_t *random, const uECC_word_t *top,
206 wordcount_t num_words);
207
208
209/* uECC_RNG_Function type
210 * The RNG function should fill 'size' random bytes into 'dest'. It should
211 * return 1 if 'dest' was filled with random data, or 0 if the random data could
212 * not be generated. The filled-in values should be either truly random, or from
213 * a cryptographically-secure PRNG.
214 *
215 * A correctly functioning RNG function must be set (using uECC_set_rng())
216 * before calling uECC_make_key() or uECC_sign().
217 *
218 * Setting a correctly functioning RNG function improves the resistance to
219 * side-channel attacks for uECC_shared_secret().
220 *
221 * A correct RNG function is set by default. If you are building on another
222 * POSIX-compliant system that supports /dev/random or /dev/urandom, you can
223 * define uECC_POSIX to use the predefined RNG.
224 */
225typedef int(*uECC_RNG_Function)(uint8_t *dest, unsigned int size);
226
227/*
228 * @brief Set the function that will be used to generate random bytes. The RNG
229 * function should return 1 if the random data was generated, or 0 if the random
230 * data could not be generated.
231 *
232 * @note On platforms where there is no predefined RNG function, this must be
233 * called before uECC_make_key() or uECC_sign() are used.
234 *
235 * @param rng_function IN -- function that will be used to generate random bytes
236 */
237void uECC_set_rng(uECC_RNG_Function rng_function);
238
239/*
240 * @brief provides current uECC_RNG_Function.
241 * @return Returns the function that will be used to generate random bytes.
242 */
243uECC_RNG_Function uECC_get_rng(void);
244
245/*
246 * @brief computes the size of a private key for the curve in bytes.
247 * @param curve IN -- elliptic curve
248 * @return size of a private key for the curve in bytes.
249 */
250int uECC_curve_private_key_size(uECC_Curve curve);
251
252/*
253 * @brief computes the size of a public key for the curve in bytes.
254 * @param curve IN -- elliptic curve
255 * @return the size of a public key for the curve in bytes.
256 */
257int uECC_curve_public_key_size(uECC_Curve curve);
258
259/*
260 * @brief Compute the corresponding public key for a private key.
261 * @param private_key IN -- The private key to compute the public key for
262 * @param public_key OUT -- Will be filled in with the corresponding public key
263 * @param curve
264 * @return Returns 1 if key was computed successfully, 0 if an error occurred.
265 */
266int uECC_compute_public_key(const uint8_t *private_key,
267 uint8_t *public_key, uECC_Curve curve);
268
269/*
270 * @brief Compute public-key.
271 * @return corresponding public-key.
272 * @param result OUT -- public-key
273 * @param private_key IN -- private-key
274 * @param curve IN -- elliptic curve
275 */
276uECC_word_t EccPoint_compute_public_key(uECC_word_t *result,
277 uECC_word_t *private_key, uECC_Curve curve);
278
279/*
280 * @brief Regularize the bitcount for the private key so that attackers cannot
281 * use a side channel attack to learn the number of leading zeros.
282 * @return Regularized k
283 * @param k IN -- private-key
284 * @param k0 IN/OUT -- regularized k
285 * @param k1 IN/OUT -- regularized k
286 * @param curve IN -- elliptic curve
287 */
288uECC_word_t regularize_k(const uECC_word_t * const k, uECC_word_t *k0,
289 uECC_word_t *k1, uECC_Curve curve);
290
291/*
292 * @brief Point multiplication algorithm using Montgomery's ladder with co-Z
293 * coordinates. See http://eprint.iacr.org/2011/338.pdf.
294 * @note Result may overlap point.
295 * @param result OUT -- returns scalar*point
296 * @param point IN -- elliptic curve point
297 * @param scalar IN -- scalar
298 * @param initial_Z IN -- initial value for z
299 * @param num_bits IN -- number of bits in scalar
300 * @param curve IN -- elliptic curve
301 */
302void EccPoint_mult(uECC_word_t * result, const uECC_word_t * point,
303 const uECC_word_t * scalar, const uECC_word_t * initial_Z,
304 bitcount_t num_bits, uECC_Curve curve);
305
306/*
307 * @brief Constant-time comparison to zero - secure way to compare long integers
308 * @param vli IN -- very long integer
309 * @param num_words IN -- number of words in the vli
310 * @return 1 if vli == 0, 0 otherwise.
311 */
312uECC_word_t uECC_vli_isZero(const uECC_word_t *vli, wordcount_t num_words);
313
314/*
315 * @brief Check if 'point' is the point at infinity
316 * @param point IN -- elliptic curve point
317 * @param curve IN -- elliptic curve
318 * @return if 'point' is the point at infinity, 0 otherwise.
319 */
320uECC_word_t EccPoint_isZero(const uECC_word_t *point, uECC_Curve curve);
321
322/*
323 * @brief computes the sign of left - right, in constant time.
324 * @param left IN -- left term to be compared
325 * @param right IN -- right term to be compared
326 * @param num_words IN -- number of words
327 * @return the sign of left - right
328 */
329cmpresult_t uECC_vli_cmp(const uECC_word_t *left, const uECC_word_t *right,
330 wordcount_t num_words);
331
332/*
333 * @brief computes sign of left - right, not in constant time.
334 * @note should not be used if inputs are part of a secret
335 * @param left IN -- left term to be compared
336 * @param right IN -- right term to be compared
337 * @param num_words IN -- number of words
338 * @return the sign of left - right
339 */
340cmpresult_t uECC_vli_cmp_unsafe(const uECC_word_t *left, const uECC_word_t *right,
341 wordcount_t num_words);
342
343/*
344 * @brief Computes result = (left - right) % mod.
345 * @note Assumes that (left < mod) and (right < mod), and that result does not
346 * overlap mod.
347 * @param result OUT -- (left - right) % mod
348 * @param left IN -- leftright term in modular subtraction
349 * @param right IN -- right term in modular subtraction
350 * @param mod IN -- mod
351 * @param num_words IN -- number of words
352 */
353void uECC_vli_modSub(uECC_word_t *result, const uECC_word_t *left,
354 const uECC_word_t *right, const uECC_word_t *mod,
355 wordcount_t num_words);
356
357/*
358 * @brief Computes P' = (x1', y1', Z3), P + Q = (x3, y3, Z3) or
359 * P => P', Q => P + Q
360 * @note assumes Input P = (x1, y1, Z), Q = (x2, y2, Z)
361 * @param X1 IN -- x coordinate of P
362 * @param Y1 IN -- y coordinate of P
363 * @param X2 IN -- x coordinate of Q
364 * @param Y2 IN -- y coordinate of Q
365 * @param curve IN -- elliptic curve
366 */
367void XYcZ_add(uECC_word_t * X1, uECC_word_t * Y1, uECC_word_t * X2,
368 uECC_word_t * Y2, uECC_Curve curve);
369
370/*
371 * @brief Computes (x1 * z^2, y1 * z^3)
372 * @param X1 IN -- previous x1 coordinate
373 * @param Y1 IN -- previous y1 coordinate
374 * @param Z IN -- z value
375 * @param curve IN -- elliptic curve
376 */
377void apply_z(uECC_word_t * X1, uECC_word_t * Y1, const uECC_word_t * const Z,
378 uECC_Curve curve);
379
380/*
381 * @brief Check if bit is set.
382 * @return Returns nonzero if bit 'bit' of vli is set.
383 * @warning It is assumed that the value provided in 'bit' is within the
384 * boundaries of the word-array 'vli'.
385 * @note The bit ordering layout assumed for vli is: {31, 30, ..., 0},
386 * {63, 62, ..., 32}, {95, 94, ..., 64}, {127, 126,..., 96} for a vli consisting
387 * of 4 uECC_word_t elements.
388 */
389uECC_word_t uECC_vli_testBit(const uECC_word_t *vli, bitcount_t bit);
390
391/*
392 * @brief Computes result = product % mod, where product is 2N words long.
393 * @param result OUT -- product % mod
394 * @param mod IN -- module
395 * @param num_words IN -- number of words
396 * @warning Currently only designed to work for curve_p or curve_n.
397 */
398void uECC_vli_mmod(uECC_word_t *result, uECC_word_t *product,
399 const uECC_word_t *mod, wordcount_t num_words);
400
401/*
402 * @brief Computes modular product (using curve->mmod_fast)
403 * @param result OUT -- (left * right) mod % curve_p
404 * @param left IN -- left term in product
405 * @param right IN -- right term in product
406 * @param curve IN -- elliptic curve
407 */
408void uECC_vli_modMult_fast(uECC_word_t *result, const uECC_word_t *left,
409 const uECC_word_t *right, uECC_Curve curve);
410
411/*
412 * @brief Computes result = left - right.
413 * @note Can modify in place.
414 * @param result OUT -- left - right
415 * @param left IN -- left term in subtraction
416 * @param right IN -- right term in subtraction
417 * @param num_words IN -- number of words
418 * @return borrow
419 */
420uECC_word_t uECC_vli_sub(uECC_word_t *result, const uECC_word_t *left,
421 const uECC_word_t *right, wordcount_t num_words);
422
423/*
424 * @brief Constant-time comparison function(secure way to compare long ints)
425 * @param left IN -- left term in comparison
426 * @param right IN -- right term in comparison
427 * @param num_words IN -- number of words
428 * @return Returns 0 if left == right, 1 otherwise.
429 */
430uECC_word_t uECC_vli_equal(const uECC_word_t *left, const uECC_word_t *right,
431 wordcount_t num_words);
432
433/*
434 * @brief Computes (left * right) % mod
435 * @param result OUT -- (left * right) % mod
436 * @param left IN -- left term in product
437 * @param right IN -- right term in product
438 * @param mod IN -- mod
439 * @param num_words IN -- number of words
440 */
441void uECC_vli_modMult(uECC_word_t *result, const uECC_word_t *left,
442 const uECC_word_t *right, const uECC_word_t *mod,
443 wordcount_t num_words);
444
445/*
446 * @brief Computes (1 / input) % mod
447 * @note All VLIs are the same size.
448 * @note See "Euclid's GCD to Montgomery Multiplication to the Great Divide"
449 * @param result OUT -- (1 / input) % mod
450 * @param input IN -- value to be modular inverted
451 * @param mod IN -- mod
452 * @param num_words -- number of words
453 */
454void uECC_vli_modInv(uECC_word_t *result, const uECC_word_t *input,
455 const uECC_word_t *mod, wordcount_t num_words);
456
457/*
458 * @brief Sets dest = src.
459 * @param dest OUT -- destination buffer
460 * @param src IN -- origin buffer
461 * @param num_words IN -- number of words
462 */
463void uECC_vli_set(uECC_word_t *dest, const uECC_word_t *src,
464 wordcount_t num_words);
465
466/*
467 * @brief Computes (left + right) % mod.
468 * @note Assumes that (left < mod) and right < mod), and that result does not
469 * overlap mod.
470 * @param result OUT -- (left + right) % mod.
471 * @param left IN -- left term in addition
472 * @param right IN -- right term in addition
473 * @param mod IN -- mod
474 * @param num_words IN -- number of words
475 */
476void uECC_vli_modAdd(uECC_word_t *result, const uECC_word_t *left,
477 const uECC_word_t *right, const uECC_word_t *mod,
478 wordcount_t num_words);
479
480/*
481 * @brief Counts the number of bits required to represent vli.
482 * @param vli IN -- very long integer
483 * @param max_words IN -- number of words
484 * @return number of bits in given vli
485 */
486bitcount_t uECC_vli_numBits(const uECC_word_t *vli,
487 const wordcount_t max_words);
488
489/*
490 * @brief Erases (set to 0) vli
491 * @param vli IN -- very long integer
492 * @param num_words IN -- number of words
493 */
494void uECC_vli_clear(uECC_word_t *vli, wordcount_t num_words);
495
496/*
497 * @brief check if it is a valid point in the curve
498 * @param point IN -- point to be checked
499 * @param curve IN -- elliptic curve
500 * @return 0 if point is valid
501 * @exception returns -1 if it is a point at infinity
502 * @exception returns -2 if x or y is smaller than p,
503 * @exception returns -3 if y^2 != x^3 + ax + b.
504 */
505int uECC_valid_point(const uECC_word_t *point, uECC_Curve curve);
506
507/*
508 * @brief Check if a public key is valid.
509 * @param public_key IN -- The public key to be checked.
510 * @return returns 0 if the public key is valid
511 * @exception returns -1 if it is a point at infinity
512 * @exception returns -2 if x or y is smaller than p,
513 * @exception returns -3 if y^2 != x^3 + ax + b.
514 * @exception returns -4 if public key is the group generator.
515 *
516 * @note Note that you are not required to check for a valid public key before
517 * using any other uECC functions. However, you may wish to avoid spending CPU
518 * time computing a shared secret or verifying a signature using an invalid
519 * public key.
520 */
521int uECC_valid_public_key(const uint8_t *public_key, uECC_Curve curve);
522
523 /*
524 * @brief Converts an integer in uECC native format to big-endian bytes.
525 * @param bytes OUT -- bytes representation
526 * @param num_bytes IN -- number of bytes
527 * @param native IN -- uECC native representation
528 */
529void uECC_vli_nativeToBytes(uint8_t *bytes, int num_bytes,
530 const unsigned int *native);
531
532/*
533 * @brief Converts big-endian bytes to an integer in uECC native format.
534 * @param native OUT -- uECC native representation
535 * @param bytes IN -- bytes representation
536 * @param num_bytes IN -- number of bytes
537 */
538void uECC_vli_bytesToNative(unsigned int *native, const uint8_t *bytes,
539 int num_bytes);
540
541#ifdef __cplusplus
542}
543#endif
544
545#endif /* __TC_UECC_H__ */