diff options
| author | Niels Möller <nisse@lysator.liu.se> | 2021-11-08 17:51:07 +0100 |
|---|---|---|
| committer | Niels Möller <nisse@lysator.liu.se> | 2021-11-08 17:51:07 +0100 |
| commit | 4e987de3c0a15f059e4d7bb296f0ceb83f6c7354 (patch) | |
| tree | 9177983ae9bf84233055e995f1585c7fa25a9f96 /ecc-secp521r1.c | |
| parent | 2adc4268f22f2951bc3ba1a6a08687fa2fee52f4 (diff) | |
| download | nettle-4e987de3c0a15f059e4d7bb296f0ceb83f6c7354.tar.gz | |
Implement secp521r1 square root, based on patch by Wim Lewis.
Diffstat (limited to 'ecc-secp521r1.c')
| -rw-r--r-- | ecc-secp521r1.c | 40 |
1 files changed, 37 insertions, 3 deletions
diff --git a/ecc-secp521r1.c b/ecc-secp521r1.c index 1b09e7b1..26314e59 100644 --- a/ecc-secp521r1.c +++ b/ecc-secp521r1.c @@ -43,6 +43,8 @@ #include "ecc-secp521r1.h" +#define B_SHIFT (521 % GMP_NUMB_BITS) + #if HAVE_NATIVE_ecc_secp521r1_modp #define ecc_secp521r1_modp _nettle_ecc_secp521r1_modp void @@ -50,7 +52,6 @@ ecc_secp521r1_modp (const struct ecc_modulo *m, mp_limb_t *rp, mp_limb_t *xp); #else -#define B_SHIFT (521 % GMP_NUMB_BITS) #define BMODP_SHIFT (GMP_NUMB_BITS - B_SHIFT) #define BMODP ((mp_limb_t) 1 << BMODP_SHIFT) @@ -121,6 +122,39 @@ ecc_secp521r1_inv (const struct ecc_modulo *p, ecc_mod_mul (p, rp, rp, ap, tp); /* a^{2^519 - 3} */ } +#define ECC_SECP521R1_SQRT_ITCH (2*ECC_LIMB_SIZE) + +static int +ecc_secp521r1_sqrt (const struct ecc_modulo *m, + mp_limb_t *rp, + const mp_limb_t *cp, + mp_limb_t *scratch) +{ + mp_limb_t hi; + + /* This computes the square root modulo p256 using the identity: + + sqrt(c) = c^(2^519) (mod P-521) + + which can be seen as a special case of Tonelli-Shanks with e=1. + */ + + ecc_mod_pow_2k (m, rp, cp, 519, scratch); + + /* Check result. */ + ecc_mod_sqr (m, scratch, rp, scratch); + ecc_mod_sub (m, scratch, scratch, cp); + + /* Reduce top bits, since ecc_mod_zero_p requires input < 2p */ + hi = scratch[ECC_LIMB_SIZE-1] >> B_SHIFT; + scratch[ECC_LIMB_SIZE-1] = (scratch[ECC_LIMB_SIZE-1] + & (((mp_limb_t) 1 << B_SHIFT)-1)) + + sec_add_1 (scratch, scratch, ECC_LIMB_SIZE - 1, hi); + + return ecc_mod_zero_p (m, scratch); +} + + const struct ecc_curve _nettle_secp_521r1 = { { @@ -129,7 +163,7 @@ const struct ecc_curve _nettle_secp_521r1 = ECC_BMODP_SIZE, ECC_REDC_SIZE, ECC_SECP521R1_INV_ITCH, - 0, + ECC_SECP521R1_SQRT_ITCH, 0, ecc_p, @@ -141,7 +175,7 @@ const struct ecc_curve _nettle_secp_521r1 = ecc_secp521r1_modp, ecc_secp521r1_modp, ecc_secp521r1_inv, - NULL, + ecc_secp521r1_sqrt, NULL, }, { |