diff options
author | Niels Möller <nisse@lysator.liu.se> | 2020-01-29 17:16:03 +0100 |
---|---|---|
committer | Niels Möller <nisse@lysator.liu.se> | 2020-01-29 17:16:03 +0100 |
commit | 87099691e752f25e3c044ed59ae47224599291bf (patch) | |
tree | 2abf884b2842be0ea41647ae6d8ed6af7ae3738e /ecc-mod-inv.c | |
parent | 4733b05484304fc766ed0d904dfe833ff35df92d (diff) | |
download | nettle-87099691e752f25e3c044ed59ae47224599291bf.tar.gz |
Make ecc modular inversion use redc form, for relevant curves.invert-with-redc
* ecc-mod-inv.c (ecc_mod_inv_destructive): New helper function,
not preserving input argument. Extracted from old ecc_mod_inv.
(ecc_mod_inv): Call ecc_mod_inv_destructive.
(ecc_mod_inv_redc): New inversion function, with input and output
in redc form.
* ecc-secp224r1.c: Select between ecc_mod_inv and ecc_mod_inv_redc.
* ecc-secp256r1.c: Likewise.
* ecc-j-to-a.c (ecc_j_to_a): Simplify redc-related logic, taking
advantage of ecc->p.invert handling redc, when appropriate. Reduce
scratch need from 5n to 4n in the process (assuming inversion
needs 2n).
* testsuite/ecc-modinv-test.c (ref_modinv): Updated to do redc, if
appropriate.
Diffstat (limited to 'ecc-mod-inv.c')
-rw-r--r-- | ecc-mod-inv.c | 53 |
1 files changed, 41 insertions, 12 deletions
diff --git a/ecc-mod-inv.c b/ecc-mod-inv.c index 8cfd2e3b..f306d7de 100644 --- a/ecc-mod-inv.c +++ b/ecc-mod-inv.c @@ -54,22 +54,19 @@ cnd_neg (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n) } } -/* Compute a^{-1} mod m, with running time depending only on the size. - Returns zero if a == 0 (mod m), to be consistent with a^{phi(m)-1}. - Also needs (m+1)/2, and m must be odd. - - Needs 2n limbs available at rp, and 2n additional scratch limbs. +/* Compute v = a^{-1} mod m, with running time depending only on the + size. Returns zero if a == 0 (mod m), to be consistent with + a^{phi(m)-1}. Also needs (m+1)/2, and m must be odd. The value at + ap is destroyed in the process. */ /* FIXME: Could use mpn_sec_invert (in GMP-6), but with a bit more scratch need since it doesn't precompute (m+1)/2. */ -void -ecc_mod_inv (const struct ecc_modulo *m, - mp_limb_t *vp, const mp_limb_t *in_ap, - mp_limb_t *scratch) +static void +ecc_mod_inv_destructive (const struct ecc_modulo *m, + mp_limb_t *vp, mp_limb_t *ap) { -#define ap scratch -#define bp (scratch + n) +#define bp (ap + n) #define up (vp + n) mp_size_t n = m->size; @@ -94,7 +91,6 @@ ecc_mod_inv (const struct ecc_modulo *m, mpn_zero (up+1, n - 1); mpn_copyi (bp, m->m, n); mpn_zero (vp, n); - mpn_copyi (ap, in_ap, n); for (i = m->bit_size + GMP_NUMB_BITS * n; i-- > 0; ) { @@ -158,3 +154,36 @@ ecc_mod_inv (const struct ecc_modulo *m, #undef bp #undef up } + +/* Needs 2n limbs available at rp, and 2n additional scratch + limbs. */ +void +ecc_mod_inv (const struct ecc_modulo *m, + mp_limb_t *vp, const mp_limb_t *ap, + mp_limb_t *scratch) +{ + mpn_copyi (scratch, ap, m->size); + ecc_mod_inv_destructive (m, vp, scratch); +} + +/* Inversion, with input and output in redc form. I.e., we want v = + a^-1 (mod m), but inputs and outputs are v' = vB, a' = aB. Then + v' a' = B^2 (mod b), and we do the inversion as + + v' = (a / B^2)^-1 (mod m) +*/ + +void +ecc_mod_inv_redc (const struct ecc_modulo *m, + mp_limb_t *vp, const mp_limb_t *ap, + mp_limb_t *scratch) +{ + mpn_copyi (scratch, ap, m->size); + + mpn_zero (scratch + m->size, m->size); + m->reduce (m, scratch); + mpn_zero (scratch + m->size, m->size); + m->reduce (m, scratch); + + ecc_mod_inv_destructive (m, vp, scratch); +} |