diff options
author | Marcel Holtmann <marcel@holtmann.org> | 2023-11-09 15:20:55 +0100 |
---|---|---|
committer | Denis Kenzior <denkenz@gmail.com> | 2023-11-09 09:28:55 -0600 |
commit | 659a48d6bf3ab83f7f17ede42d0e98608704b3cc (patch) | |
tree | 77d373ab90500f60dcdc61b2f06253562b09c958 | |
parent | 5d35ed29ff95d040bbec89165156fd9598ddf80b (diff) |
ecc: Introduce _vli_mmod_slow that works with curve_p and curve_n
-rw-r--r-- | ell/ecc-external.c | 75 | ||||
-rw-r--r-- | ell/ecc-private.h | 3 |
2 files changed, 78 insertions, 0 deletions
diff --git a/ell/ecc-external.c b/ell/ecc-external.c index 46f710bf..7a088232 100644 --- a/ell/ecc-external.c +++ b/ell/ecc-external.c @@ -314,6 +314,81 @@ void _vli_mod_sub(uint64_t *result, const uint64_t *left, _vli_add(result, result, mod, ndigits); } +/* Counts the number of 64-bit "digits" in vli. */ +static unsigned int _vli_num_digits(const uint64_t *vli, unsigned int ndigits) +{ + int i; + + /* Search from the end until we find a non-zero digit. + * We do it in reverse because we expect that most digits will + * be nonzero. + */ + for (i = ndigits - 1; i >= 0 && vli[i] == 0; i--); + + return (i + 1); +} + +/* Counts the number of bits required for vli. */ +static unsigned int _vli_num_bits(const uint64_t *vli, unsigned int ndigits) +{ + unsigned int i, num_digits; + uint64_t digit; + + num_digits = _vli_num_digits(vli, ndigits); + if (num_digits == 0) + return 0; + + digit = vli[num_digits - 1]; + for (i = 0; digit; i++) + digit >>= 1; + + return ((num_digits - 1) * 64 + i); +} + +/* Computes result = product % mod, where product is 2N words long. + * Currently only designed to work for curve_p or curve_n. + */ +void _vli_mmod_slow(uint64_t *result, const uint64_t *product, + const uint64_t *mod, unsigned int ndigits) +{ + uint64_t mod_m[2 * L_ECC_MAX_DIGITS]; + uint64_t tmp[2 * L_ECC_MAX_DIGITS]; + uint64_t *v[2] = { tmp, (uint64_t *) product }; + uint64_t carry = 0; + unsigned int i; + /* Shift mod so its highest set bit is at the maximum position. */ + int shift = (ndigits * 2 * 64) - _vli_num_bits(mod, ndigits); + int word_shift = shift / 64; + int bit_shift = shift % 64; + + vli_clear(mod_m, word_shift); + if (bit_shift > 0) { + for (i = 0; i < ndigits; ++i) { + mod_m[word_shift + i] = (mod[i] << bit_shift) | carry; + carry = mod[i] >> (64 - bit_shift); + } + } else + vli_set(mod_m + word_shift, mod, ndigits); + + for (i = 1; shift >= 0; --shift) { + uint64_t borrow = 0; + unsigned int j; + + for (j = 0; j < ndigits * 2; ++j) { + uint64_t diff = v[i][j] - mod_m[j] - borrow; + + if (diff != v[i][j]) + borrow = (diff > v[i][j]); + v[1 - i][j] = diff; + } + i = !(i ^ borrow); /* Swap the index if there was no borrow */ + _vli_rshift1(mod_m, ndigits); + mod_m[ndigits - 1] |= mod_m[ndigits] << (64 - 1); + _vli_rshift1(mod_m + ndigits, ndigits); + } + vli_set(result, v[i], ndigits); +} + /* Computes p_result = p_product % curve_p. * See algorithm 5 and 6 from * http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf diff --git a/ell/ecc-private.h b/ell/ecc-private.h index dcf676d9..de84bc64 100644 --- a/ell/ecc-private.h +++ b/ell/ecc-private.h @@ -86,6 +86,9 @@ void _vli_mod_add(uint64_t *result, const uint64_t *left, const uint64_t *right, void _vli_rshift1(uint64_t *vli, unsigned int ndigits); +void _vli_mmod_slow(uint64_t *result, const uint64_t *product, + const uint64_t *mod, unsigned int ndigits); + bool _vli_mmod_fast(uint64_t *result, const uint64_t *product, const uint64_t *curve_prime, unsigned int ndigits); |