Added uECC_generate_random_int(), and made uECC_vli_cmp() constant-time.
diff --git a/asm_avr.inc b/asm_avr.inc index 9f59dae..6bd786c 100644 --- a/asm_avr.inc +++ b/asm_avr.inc
@@ -21654,7 +21654,7 @@ if (carry > 0) { uECC_vli_sub(result, result, curve_p); } - if (uECC_vli_cmp(result, curve_p) > 0) { + if (uECC_vli_cmp_unsafe(result, curve_p) > 0) { uECC_vli_sub(result, result, curve_p); } } @@ -21977,7 +21977,7 @@ if (carry > 0) { uECC_vli_sub(result, result, curve_p); } - if (uECC_vli_cmp(result, curve_p) > 0) { + if (uECC_vli_cmp_unsafe(result, curve_p) > 0) { uECC_vli_sub(result, result, curve_p); } }
diff --git a/curve-specific.inc b/curve-specific.inc index 7ce7e4d..07676e1 100644 --- a/curve-specific.inc +++ b/curve-specific.inc
@@ -193,7 +193,7 @@ omega_mult_secp160r1(product, tmp + num_words_secp160r1 - 1); /* Rq*c */ uECC_vli_add(result, result, product, num_words_secp160r1); /* (C1, r) = r + Rq*c */ - while (uECC_vli_cmp(result, curve_secp160r1.p, num_words_secp160r1) > 0) { + while (uECC_vli_cmp_unsafe(result, curve_secp160r1.p, num_words_secp160r1) > 0) { uECC_vli_sub(result, result, curve_secp160r1.p, num_words_secp160r1); } } @@ -230,7 +230,7 @@ --carry; uECC_vli_sub(result, result, curve_secp160r1.p, num_words_secp160r1); } - if (uECC_vli_cmp(result, curve_secp160r1.p, num_words_secp160r1) > 0) { + if (uECC_vli_cmp_unsafe(result, curve_secp160r1.p, num_words_secp160r1) > 0) { uECC_vli_sub(result, result, curve_secp160r1.p, num_words_secp160r1); } } @@ -344,7 +344,7 @@ tmp[16] = tmp[17] = tmp[18] = tmp[19] = tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0; carry += uECC_vli_add(result, result, tmp, num_words_secp192r1); - while (carry || uECC_vli_cmp(curve_secp192r1.p, result, num_words_secp192r1) != 1) { + while (carry || uECC_vli_cmp_unsafe(curve_secp192r1.p, result, num_words_secp192r1) != 1) { carry -= uECC_vli_sub(result, result, curve_secp192r1.p, num_words_secp192r1); } } @@ -370,7 +370,7 @@ tmp[4] = tmp[5] = 0; carry += uECC_vli_add(result, result, tmp, num_words_secp192r1); - while (carry || uECC_vli_cmp(curve_secp192r1.p, result, num_words_secp192r1) != 1) { + while (carry || uECC_vli_cmp_unsafe(curve_secp192r1.p, result, num_words_secp192r1) != 1) { carry -= uECC_vli_sub(result, result, curve_secp192r1.p, num_words_secp192r1); } } @@ -393,7 +393,7 @@ tmp[2] = 0; carry += uECC_vli_add(result, result, tmp, num_words_secp192r1); - while (carry || uECC_vli_cmp(curve_secp192r1.p, result, num_words_secp192r1) != 1) { + while (carry || uECC_vli_cmp_unsafe(curve_secp192r1.p, result, num_words_secp192r1) != 1) { carry -= uECC_vli_sub(result, result, curve_secp192r1.p, num_words_secp192r1); } } @@ -620,7 +620,7 @@ carry += uECC_vli_add(result, result, curve_secp224r1.p, num_words_secp224r1); } while (carry < 0); } else { - while (carry || uECC_vli_cmp(curve_secp224r1.p, result, num_words_secp224r1) != 1) { + while (carry || uECC_vli_cmp_unsafe(curve_secp224r1.p, result, num_words_secp224r1) != 1) { carry -= uECC_vli_sub(result, result, curve_secp224r1.p, num_words_secp224r1); } } @@ -671,7 +671,7 @@ carry += uECC_vli_add(result, result, curve_secp224r1.p, num_words_secp224r1); } while (carry < 0); } else { - while (carry || uECC_vli_cmp(curve_secp224r1.p, result, num_words_secp224r1) != 1) { + while (carry || uECC_vli_cmp_unsafe(curve_secp224r1.p, result, num_words_secp224r1) != 1) { carry -= uECC_vli_sub(result, result, curve_secp224r1.p, num_words_secp224r1); } } @@ -717,7 +717,7 @@ carry += uECC_vli_add(result, result, curve_secp224r1.p, num_words_secp224r1); } while (carry < 0); } else { - while (uECC_vli_cmp(curve_secp224r1.p, result, num_words_secp224r1) != 1) { + while (uECC_vli_cmp_unsafe(curve_secp224r1.p, result, num_words_secp224r1) != 1) { uECC_vli_sub(result, result, curve_secp224r1.p, num_words_secp224r1); } } @@ -874,7 +874,7 @@ carry += uECC_vli_add(result, result, curve_secp256r1.p, num_words_secp256r1); } while (carry < 0); } else { - while (carry || uECC_vli_cmp(curve_secp256r1.p, result, num_words_secp256r1) != 1) { + while (carry || uECC_vli_cmp_unsafe(curve_secp256r1.p, result, num_words_secp256r1) != 1) { carry -= uECC_vli_sub(result, result, curve_secp256r1.p, num_words_secp256r1); } } @@ -972,7 +972,7 @@ carry += uECC_vli_add(result, result, curve_secp256r1.p, num_words_secp256r1); } while (carry < 0); } else { - while (carry || uECC_vli_cmp(curve_secp256r1.p, result, num_words_secp256r1) != 1) { + while (carry || uECC_vli_cmp_unsafe(curve_secp256r1.p, result, num_words_secp256r1) != 1) { carry -= uECC_vli_sub(result, result, curve_secp256r1.p, num_words_secp256r1); } } @@ -1047,7 +1047,7 @@ carry += uECC_vli_add(result, result, curve_secp256r1.p, num_words_secp256r1); } while (carry < 0); } else { - while (carry || uECC_vli_cmp(curve_secp256r1.p, result, num_words_secp256r1) != 1) { + while (carry || uECC_vli_cmp_unsafe(curve_secp256r1.p, result, num_words_secp256r1) != 1) { carry -= uECC_vli_sub(result, result, curve_secp256r1.p, num_words_secp256r1); } } @@ -1172,7 +1172,7 @@ --carry; uECC_vli_sub(result, result, curve_secp256k1.p, num_words_secp256k1); } - if (uECC_vli_cmp(result, curve_secp256k1.p, num_words_secp256k1) > 0) { + if (uECC_vli_cmp_unsafe(result, curve_secp256k1.p, num_words_secp256k1) > 0) { uECC_vli_sub(result, result, curve_secp256k1.p, num_words_secp256k1); } }
diff --git a/uECC.c b/uECC.c index 3611a26..d34d0c5 100644 --- a/uECC.c +++ b/uECC.c
@@ -139,9 +139,9 @@ } /* Returns sign of left - right. */ -uECC_VLI_API cmpresult_t uECC_vli_cmp(const uECC_word_t *left, - const uECC_word_t *right, - wordcount_t num_words) { +static cmpresult_t uECC_vli_cmp_unsafe(const uECC_word_t *left, + const uECC_word_t *right, + wordcount_t num_words) { wordcount_t i; for (i = num_words - 1; i >= 0; --i) { if (left[i] > right[i]) { @@ -154,7 +154,7 @@ } /* Constant-time comparison function - secure way to compare long integers */ -/* Returns one if left == right, zero otherwise */ +/* Returns one if left == right, zero otherwise. */ uECC_VLI_API uECC_word_t uECC_vli_equal(const uECC_word_t *left, const uECC_word_t *right, wordcount_t num_words) { @@ -166,6 +166,21 @@ return (diff == 0); } +uECC_VLI_API uECC_word_t uECC_vli_sub(uECC_word_t *result, + const uECC_word_t *left, + const uECC_word_t *right, + wordcount_t num_words); + +/* Returns sign of left - right, in constant time. */ +uECC_VLI_API cmpresult_t uECC_vli_cmp(const uECC_word_t *left, + const uECC_word_t *right, + wordcount_t num_words) { + uECC_word_t tmp[uECC_MAX_WORDS]; + uECC_word_t neg = !!uECC_vli_sub(tmp, left, right, num_words); + uECC_word_t equal = uECC_vli_isZero(tmp, num_words); + return (!equal - 2 * neg); +} + /* Computes vli = vli >> 1. */ uECC_VLI_API void uECC_vli_rshift1(uECC_word_t *vli, wordcount_t num_words) { uECC_word_t *end = vli; @@ -390,7 +405,7 @@ const uECC_word_t *mod, wordcount_t num_words) { uECC_word_t carry = uECC_vli_add(result, left, right, num_words); - if (carry || uECC_vli_cmp(result, mod, num_words) >= 0) { + if (carry || uECC_vli_cmp_unsafe(result, mod, num_words) >= 0) { /* result > mod (result = mod + remainder), so subtract mod to get remainder. */ uECC_vli_sub(result, result, mod, num_words); } @@ -553,7 +568,7 @@ uECC_vli_clear(u, num_words); u[0] = 1; uECC_vli_clear(v, num_words); - while ((cmpResult = uECC_vli_cmp(a, b, num_words)) != 0) { + while ((cmpResult = uECC_vli_cmp_unsafe(a, b, num_words)) != 0) { if (EVEN(a)) { uECC_vli_rshift1(a, num_words); vli_modInv_update(u, mod, num_words); @@ -563,7 +578,7 @@ } else if (cmpResult > 0) { uECC_vli_sub(a, a, b, num_words); uECC_vli_rshift1(a, num_words); - if (uECC_vli_cmp(u, v, num_words) < 0) { + if (uECC_vli_cmp_unsafe(u, v, num_words) < 0) { uECC_vli_add(u, u, mod, num_words); } uECC_vli_sub(u, u, v, num_words); @@ -571,7 +586,7 @@ } else { uECC_vli_sub(b, b, a, num_words); uECC_vli_rshift1(b, num_words); - if (uECC_vli_cmp(v, u, num_words) < 0) { + if (uECC_vli_cmp_unsafe(v, u, num_words) < 0) { uECC_vli_add(v, v, mod, num_words); } uECC_vli_sub(v, v, u, num_words); @@ -975,8 +990,8 @@ } /* x and y must be smaller than p. */ - if (uECC_vli_cmp(curve->p, point, num_words) != 1 || - uECC_vli_cmp(curve->p, point + num_words, num_words) != 1) { + if (uECC_vli_cmp_unsafe(curve->p, point, num_words) != 1 || + uECC_vli_cmp_unsafe(curve->p, point + num_words, num_words) != 1) { return 0; } @@ -1262,8 +1277,8 @@ } /* r, s must be < n. */ - if (uECC_vli_cmp(curve->n, r, num_n_words) != 1 || - uECC_vli_cmp(curve->n, s, num_n_words) != 1) { + if (uECC_vli_cmp_unsafe(curve->n, r, num_n_words) != 1 || + uECC_vli_cmp_unsafe(curve->n, s, num_n_words) != 1) { return 0; } @@ -1319,7 +1334,7 @@ apply_z(rx, ry, z, curve); /* v = x1 (mod n) */ - if (uECC_vli_cmp(curve->n, rx, num_n_words) != 1) { + if (uECC_vli_cmp_unsafe(curve->n, rx, num_n_words) != 1) { uECC_vli_sub(rx, rx, curve->n, num_n_words); } @@ -1358,14 +1373,11 @@ } #if uECC_SUPPORT_COMPRESSED_POINT -/* Calculates a = sqrt(a) (mod curve->p) */ void uECC_vli_mod_sqrt(uECC_word_t *a, uECC_Curve curve) { curve->mod_sqrt(a, curve); } #endif -/* Calculates result = product (mod curve->p), where product is up to - 2 * curve->num_words long. */ void uECC_vli_mmod_fast(uECC_word_t *result, uECC_word_t *product, uECC_Curve curve) { #if (uECC_OPTIMIZATION_LEVEL > 0) curve->mmod_fast(result, product); @@ -1374,9 +1386,6 @@ #endif } -/* Multiply a point by a scalar. Points are represented by the X coordinate followed by - the Y coordinate in the same array, both coordinates are curve->num_words long. Note - that scalar must be curve->num_n_words long (NOT curve->num_words). */ void uECC_point_mult(uECC_word_t *result, const uECC_word_t *point, const uECC_word_t *scalar, @@ -1391,4 +1400,22 @@ curve); } +int uECC_generate_random_int(uECC_word_t *random, uECC_Curve curve) { + wordcount_t num_n_words = curve->num_n_words; + bitcount_t num_n_bits = uECC_vli_numBits(curve->n, num_n_words); + uECC_word_t tries; + + for (tries = 0; tries < uECC_RNG_MAX_TRIES; ++tries) { + if (!generate_random_int(random, num_n_words, num_n_bits)) { + return 0; + } + + if (!uECC_vli_isZero(random, num_n_words) && + uECC_vli_cmp(curve->n, random, num_n_words) == 1) + return 1; + } + } + return 0; +} + #endif /* uECC_ENABLE_VLI_API */
diff --git a/uECC_vli.h b/uECC_vli.h index 3145706..475c7d3 100644 --- a/uECC_vli.h +++ b/uECC_vli.h
@@ -29,15 +29,16 @@ /* Sets dest = src. */ void uECC_vli_set(uECC_word_t *dest, const uECC_word_t *src, wordcount_t num_words); -/* Returns sign of left - right. */ -cmpresult_t uECC_vli_cmp(const uECC_word_t *left, const uECC_word_t *right, wordcount_t num_words); - /* Constant-time comparison function - secure way to compare long integers */ /* Returns one if left == right, zero otherwise */ uECC_word_t uECC_vli_equal(const uECC_word_t *left, const uECC_word_t *right, wordcount_t num_words); +/* Constant-time comparison function - secure way to compare long integers */ +/* Returns sign of left - right, in constant time. */ +cmpresult_t uECC_vli_cmp(const uECC_word_t *left, const uECC_word_t *right, wordcount_t num_words); + /* Computes vli = vli >> 1. */ void uECC_vli_rshift1(uECC_word_t *vli, wordcount_t num_words); @@ -134,14 +135,17 @@ const uECC_word_t *uECC_curve_G(uECC_Curve curve); const uECC_word_t *uECC_curve_b(uECC_Curve curve); -/* Multiply a point by a scalar. Points are represented by the X coordinate followed by +/* Multiplies a point by a scalar. Points are represented by the X coordinate followed by the Y coordinate in the same array, both coordinates are curve->num_words long. Note that scalar must be curve->num_n_words long (NOT curve->num_words). */ void uECC_point_mult(uECC_word_t *result, const uECC_word_t *point, const uECC_word_t *scalar, uECC_Curve curve); - + +/* Generates a random integer r in the range 0 < r < curve->n */ +int uECC_generate_random_int(uECC_word_t *random, uECC_Curve curve); + #ifdef __cplusplus } /* end of extern "C" */ #endif