ecc: Introduce _vli_mmod_slow that works with curve_p and curve_n
PATCH 2/3 ecc: Introduce _vli_mmod_slow that works with curve_p and curve_n
--- ell/ecc-external.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++ ell/ecc-private.h | 3 ++ 2 files changed, 78 insertions(+)
ell/ecc-external.c +75 -0
@@ -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
ell/ecc-private.h +3 -0
@@ -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);
Signature · 1 line
2.41.0