diff options
Diffstat (limited to 'ecc-secp384r1.c')
-rw-r--r-- | ecc-secp384r1.c | 66 |
1 files changed, 63 insertions, 3 deletions
diff --git a/ecc-secp384r1.c b/ecc-secp384r1.c index 54bcd112..53017a15 100644 --- a/ecc-secp384r1.c +++ b/ecc-secp384r1.c @@ -146,7 +146,67 @@ ecc_secp384r1_modp (const struct ecc_modulo *p, mp_limb_t *rp) #else #define ecc_secp384r1_modp ecc_mod #endif + +#define ECC_SECP384R1_INV_ITCH (7*ECC_LIMB_SIZE) + +static void +ecc_secp384r1_inv (const struct ecc_modulo *p, + mp_limb_t *rp, const mp_limb_t *ap, + mp_limb_t *scratch) +{ +#define a3 scratch +#define a5m1 (scratch + ECC_LIMB_SIZE) + /* Using as destination clobbers t0 */ +#define a15m1 (scratch + 2*ECC_LIMB_SIZE) + /* Overlaps a5m1 */ +#define a30m1 (scratch + ECC_LIMB_SIZE) +#define t0 (scratch + 3*ECC_LIMB_SIZE) +#define t1 (scratch + 5*ECC_LIMB_SIZE) + /* + Addition chain for + + p - 2 = 2^{384} - 2^{128} - 2^{96} + 2^{32} - 3 + + 3 = 1 + 2 + 2^4 - 1 = 15 = (2^2 + 1) * 3 + 2^5 - 1 = 1 + 2(2^4 - 1) + 2^{15} - 1 = (1 + 2^5(1 + 2^5)) (2^5-1) + 2^{30} - 1 = (2^{15} + 1) (2^{15} - 1) + 2^{60} - 1 = (2^{30} + 1) (2^{30} - 1) + 2^{120} - 1 = (2^{60} + 1) (2^{60} - 1) + 2^{240} - 1 = (2^{120} + 1)(2^{120} - 1) + 2^{255} - 1 = 2^{15} (2^{240} - 1) + 2^{15} - 1 + 2^{286} - 2^{30} - 1 = 2^{31} (2^{255} - 1) + 2^{30} - 1 + + 2^{288} - 2^{32} - 1 = 2^2 (2^{286} - 2^{30} - 1) + 3 + 2^{382} - 2^{126} - 2^{94} + 2^{30} - 1 + = 2^{94} (2^{288} - 2^{32} - 1) + 2^{30} - 1 + + This addition chain needs 383 squarings and 14 multiplies. + + */ + ecc_mod_sqr (p, rp, ap); /* a^2 */ + ecc_mod_mul (p, a3, ap, rp); /* a^3 */ + ecc_mod_pow_2kp1 (p, rp, a3, 2, t0); /* a^{2^4 - 1}, a3 */ + ecc_mod_sqr (p, t0, rp); /* a^{2^5 - 2} */ + ecc_mod_mul (p, a5m1, ap, t0); /* a^{2^5 - 1}, a3 a5m1 */ + + ecc_mod_pow_2kp1 (p, rp, a5m1, 5, t0); /* a^{2^{10} - 1, a3, a5m1*/ + ecc_mod_pow_2k_mul (p, a15m1, rp, 5, a5m1, t1); /* a^{2^{15} - 1}, a3, a5m1 a15m1 */ + ecc_mod_pow_2kp1 (p, t0, a15m1, 15, rp); /* a^{2^{30} - 1}, a3 a15m1 a30m1 */ + mpn_copyi (a30m1, t0, ECC_LIMB_SIZE); + ecc_mod_pow_2kp1 (p, t0, a30m1, 30, rp); /* a^{2^{60} - 1, a3 a15m1 a30m1 */ + ecc_mod_pow_2kp1 (p, rp, t0, 60, t1); /* a^{2^{120} - 1, a3 a15m1 a30m1 */ + ecc_mod_pow_2kp1 (p, t0, rp, 120, t1); /* a^{2^{240} - 1, a3 a15m1 a30m1 */ + ecc_mod_pow_2k_mul (p, rp, t0, 15, a15m1, t1); /* a^{2^{255} - 1, a3 a30m1 */ + ecc_mod_pow_2k_mul (p, t0, rp, 31, a30m1, t1); /* a^{2^{286} - 2^{30} - 1}, a3 a30m1 */ + + ecc_mod_pow_2k_mul (p, rp, t0, 2, a3, t1); /* a^{2^{288} - 2^{32} - 1, a30m1 */ + ecc_mod_pow_2k_mul (p, t0, rp, 94, a30m1, t1); /* a^{2^{392} - 2^{126} - 2^{94} + 2^{30} - 1 */ + ecc_mod_pow_2k_mul (p, rp, t0, 2, ap, t1); +} + const struct ecc_curve _nettle_secp_384r1 = { { @@ -154,7 +214,7 @@ const struct ecc_curve _nettle_secp_384r1 = ECC_LIMB_SIZE, ECC_BMODP_SIZE, ECC_REDC_SIZE, - ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + ECC_SECP384R1_INV_ITCH, 0, ecc_p, @@ -165,7 +225,7 @@ const struct ecc_curve _nettle_secp_384r1 = ecc_secp384r1_modp, ecc_secp384r1_modp, - ecc_mod_inv, + ecc_secp384r1_inv, NULL, }, { @@ -197,7 +257,7 @@ const struct ecc_curve _nettle_secp_384r1 = 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_SECP384R1_INV_ITCH, ecc_add_jja, ecc_add_jjj, |