From 87099691e752f25e3c044ed59ae47224599291bf Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Niels=20M=C3=B6ller?= Date: Wed, 29 Jan 2020 17:16:03 +0100 Subject: Make ecc modular inversion use redc form, for relevant curves. * 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. --- ecc-internal.h | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'ecc-internal.h') diff --git a/ecc-internal.h b/ecc-internal.h index 9516023a..2c1e57e8 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -52,6 +52,7 @@ #define ecc_mod_random _nettle_ecc_mod_random #define ecc_mod _nettle_ecc_mod #define ecc_mod_inv _nettle_ecc_mod_inv +#define ecc_mod_inv_redc _nettle_ecc_mod_inv_redc #define ecc_hash _nettle_ecc_hash #define gost_hash _nettle_gost_hash #define ecc_a_to_j _nettle_ecc_a_to_j @@ -168,6 +169,8 @@ struct ecc_modulo ecc_mod_func *mod; ecc_mod_func *reduce; + /* For moduli where we use redc, the invert and sqrt functions work + with inputs and outputs in redc form. */ ecc_mod_inv_func *invert; ecc_mod_sqrt_func *sqrt; }; @@ -228,6 +231,7 @@ ecc_mod_func ecc_pp1_redc; ecc_mod_func ecc_pm1_redc; ecc_mod_inv_func ecc_mod_inv; +ecc_mod_inv_func ecc_mod_inv_redc; void ecc_mod_add (const struct ecc_modulo *m, mp_limb_t *rp, @@ -432,7 +436,8 @@ curve448_eh_to_x (mp_limb_t *xp, const mp_limb_t *p, /* Current scratch needs: */ #define ECC_MOD_INV_ITCH(size) (2*(size)) -#define ECC_J_TO_A_ITCH(size) (5*(size)) +/* Only valid when using the general ecc_mod_inv/ecc_mod_inv_redc ! */ +#define ECC_J_TO_A_ITCH(size) (4*(size)) #define ECC_EH_TO_A_ITCH(size, inv) (2*(size)+(inv)) #define ECC_DUP_JJ_ITCH(size) (5*(size)) #define ECC_DUP_EH_ITCH(size) (5*(size)) -- cgit v1.2.1