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-j-to-a.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-j-to-a.c')
-rw-r--r-- | ecc-j-to-a.c | 40 |
1 files changed, 8 insertions, 32 deletions
diff --git a/ecc-j-to-a.c b/ecc-j-to-a.c index eca10f0f..faaaa717 100644 --- a/ecc-j-to-a.c +++ b/ecc-j-to-a.c @@ -45,47 +45,24 @@ ecc_j_to_a (const struct ecc_curve *ecc, mp_limb_t *scratch) { #define izp scratch -#define up (scratch + 2*ecc->p.size) #define iz2p (scratch + ecc->p.size) #define iz3p (scratch + 2*ecc->p.size) -#define izBp (scratch + 3*ecc->p.size) #define tp scratch mp_limb_t cy; - if (ecc->use_redc) - { - /* Set v = (r_z / B^2)^-1, - - r_x = p_x v^2 / B^3 = ((v/B * v)/B * p_x)/B - r_y = p_y v^3 / B^4 = (((v/B * v)/B * v)/B * p_y)/B - */ - - mpn_copyi (up, p + 2*ecc->p.size, ecc->p.size); - mpn_zero (up + ecc->p.size, ecc->p.size); - ecc->p.reduce (&ecc->p, up); - mpn_zero (up + ecc->p.size, ecc->p.size); - ecc->p.reduce (&ecc->p, up); - - ecc->p.invert (&ecc->p, izp, up, up + ecc->p.size); + ecc->p.invert (&ecc->p, izp, p+2*ecc->p.size, izp + 2 * ecc->p.size); + ecc_modp_sqr (ecc, iz2p, izp); - /* Divide this common factor by B */ - mpn_copyi (izBp, izp, ecc->p.size); - mpn_zero (izBp + ecc->p.size, ecc->p.size); - ecc->p.reduce (&ecc->p, izBp); - - ecc_modp_mul (ecc, iz2p, izp, izBp); - } - else + if (ecc->use_redc) { - /* Set s = p_z^{-1}, r_x = p_x s^2, r_y = p_y s^3 */ - - mpn_copyi (up, p+2*ecc->p.size, ecc->p.size); /* p_z */ - ecc->p.invert (&ecc->p, izp, up, up + ecc->p.size); - - ecc_modp_sqr (ecc, iz2p, izp); + /* Divide this common factor by B, instead of applying redc to + both x and y outputs. */ + mpn_zero (iz2p + ecc->p.size, ecc->p.size); + ecc->p.reduce (&ecc->p, iz2p); } + /* r_x <-- x / z^2 */ ecc_modp_mul (ecc, iz3p, iz2p, p); /* ecc_modp (and ecc_modp_mul) may return a value up to 2p - 1, so do a conditional subtraction. */ @@ -112,7 +89,6 @@ ecc_j_to_a (const struct ecc_curve *ecc, cnd_copy (cy, r + ecc->p.size, tp, ecc->p.size); #undef izp -#undef up #undef iz2p #undef iz3p #undef tp |