diff options
| author | Niels Möller <nisse@lysator.liu.se> | 2020-10-20 22:20:02 +0200 |
|---|---|---|
| committer | Niels Möller <nisse@lysator.liu.se> | 2020-11-11 20:56:46 +0100 |
| commit | 219fcda017035d0e2af0af35b5a65115d092c1c2 (patch) | |
| tree | 968f354028b52fd59366e55af85d7f6ab9d80474 /ecc-secp224r1.c | |
| parent | 8b3f84f8c47e3f425d5a1d322cea3557cefc5c89 (diff) | |
| download | nettle-219fcda017035d0e2af0af35b5a65115d092c1c2.tar.gz | |
Optimize modular inversion for secp224r1 and secp256r1
* ecc-secp224r1.c (ecc_secp224r1_inv): New function, modular
inverse using powering.
(_nettle_secp_224r1): Analogous updates. Increases signing
performance roughly 17% on x86_64.
* ecc-secp256r1.c (ecc_secp256r1_inv): New function, modular
inverse using powering.
(_nettle_secp_256r1): Analogous updates. Increases signing
performance roughly 6% on x86_64.
Diffstat (limited to 'ecc-secp224r1.c')
| -rw-r--r-- | ecc-secp224r1.c | 57 |
1 files changed, 54 insertions, 3 deletions
diff --git a/ecc-secp224r1.c b/ecc-secp224r1.c index 30a9b5a9..4b0fd9ba 100644 --- a/ecc-secp224r1.c +++ b/ecc-secp224r1.c @@ -62,6 +62,57 @@ ecc_secp224r1_modp (const struct ecc_modulo *m, mp_limb_t *rp, mp_limb_t *xp); # error Configuration error #endif +#define ECC_SECP224R1_INV_ITCH (4*ECC_LIMB_SIZE) + +static void +ecc_secp224r1_inv (const struct ecc_modulo *p, + mp_limb_t *rp, const mp_limb_t *ap, + mp_limb_t *scratch) +{ +#define a7 scratch +#define t0 (scratch + 1*ECC_LIMB_SIZE) +#define a31m1 t0 +#define a96m1 a7 +#define tp (scratch + 2*ECC_LIMB_SIZE) + + /* Addition chain for p - 2 = 2^{224} - 2^{96} - 1 + + 7 = 1 + 2 (2+1) 2 S + 2 M + 2^{31} - 1 = 1 + 2 (2^{15} + 1)(1 + 2 (2^7 + 1) (1 + 2 (2^3+1) * 7)) + 28 S + 6 M + 2^{34} - 1 = 2^3 (2^{31} - 1) + 7 3 S + M + 2^{65} - 1 = 2^{31}(2^{34} - 1) + 2^{31} - 1 31 S + M + 2^{96} - 1 = 2^{31}(2^{65} - 1) + 2^{31} - 1 31 S + M + 2^{127} - 1 = 2^{31}(2^{96} - 1) + 2^{31} - 1 31 S + M + + 2^{224} - 2^{96} - 1 97 S + M + = 2^{97}(2^{127} - 1) + 2^{96} - 1 + + This addition chain needs 223 squarings and 13 multiplies. + */ + ecc_mod_sqr (p, rp, ap, tp); /* a^2 */ + ecc_mod_mul (p, rp, rp, ap, tp); /* a^3 */ + ecc_mod_sqr (p, rp, rp, tp); /* a^6 */ + ecc_mod_mul (p, a7, rp, ap, tp); /* a^{2^3-1} a7 */ + + ecc_mod_pow_2kp1 (p, rp, a7, 3, tp); /* a^{2^6 - 1} */ + ecc_mod_sqr (p, rp, rp, tp); /* a^{2^7 - 2} */ + ecc_mod_mul (p, rp, rp, ap, tp); /* a^{2^7 - 1} */ + ecc_mod_pow_2kp1 (p, t0, rp, 7, tp); /* a^{2^14 - 1} */ + ecc_mod_sqr (p, rp, t0, tp); /* a^{2^15 - 2} */ + ecc_mod_mul (p, rp, rp, ap, tp); /* a^{2^15 - 1} */ + ecc_mod_pow_2kp1 (p, t0, rp, 15, tp); /* a^{2^30 - 1} */ + ecc_mod_sqr (p, rp, t0, tp); /* a^{2^31 - 2} */ + ecc_mod_mul (p, a31m1, rp, ap, tp); /* a^{2^31 - 1} a7, a31m1 */ + + ecc_mod_pow_2k_mul (p, rp, a31m1, 3, a7, tp); /* a^{2^34 - 1} a31m1 */ + ecc_mod_pow_2k_mul (p, rp, rp, 31, a31m1, tp); /* a^{2^65 - 1} a31m1 */ + ecc_mod_pow_2k_mul (p, a96m1, rp, 31, a31m1, tp); /* a^{2^96 - 1} a31m1, a96m1 */ + ecc_mod_pow_2k_mul (p, rp, a96m1, 31, a31m1, tp); /* a^{2^{127} - 1} a96m1 */ + ecc_mod_pow_2k_mul (p, rp, rp, 97, a96m1, tp); /* a^{2^{224} - 2^{96} - 1 */ +} + + const struct ecc_curve _nettle_secp_224r1 = { { @@ -69,7 +120,7 @@ const struct ecc_curve _nettle_secp_224r1 = ECC_LIMB_SIZE, ECC_BMODP_SIZE, -ECC_REDC_SIZE, - ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + ECC_SECP224R1_INV_ITCH, 0, ecc_p, @@ -80,7 +131,7 @@ const struct ecc_curve _nettle_secp_224r1 = ecc_secp224r1_modp, USE_REDC ? ecc_secp224r1_redc : ecc_secp224r1_modp, - USE_REDC ? ecc_mod_inv_redc : ecc_mod_inv, + ecc_secp224r1_inv, NULL, }, { @@ -112,7 +163,7 @@ const struct ecc_curve _nettle_secp_224r1 = ECC_DUP_JJ_ITCH (ECC_LIMB_SIZE), ECC_MUL_A_ITCH (ECC_LIMB_SIZE), ECC_MUL_G_ITCH (ECC_LIMB_SIZE), - ECC_J_TO_A_ITCH (ECC_LIMB_SIZE), + 2*ECC_LIMB_SIZE + ECC_SECP224R1_INV_ITCH, ecc_add_jja, ecc_add_jjj, |