diff options
author | Jussi Kivilinna <jussi.kivilinna@iki.fi> | 2021-04-24 20:47:40 +0300 |
---|---|---|
committer | Jussi Kivilinna <jussi.kivilinna@iki.fi> | 2021-06-19 16:29:31 +0300 |
commit | 6dfab8cfb94ccb485a15b13df3c499cbb06fddf2 (patch) | |
tree | 0ec3a44bc7ffb4ce9def3a157415809a3fab3823 /mpi/ec.c | |
parent | 9d909cb67e70fd792926ac1e2ab305b2cc96bc27 (diff) | |
download | libgcrypt-6dfab8cfb94ccb485a15b13df3c499cbb06fddf2.tar.gz |
mpi/ec: add fast reduction for secp256k1
* mpi/ec.c (ec_secp256k1_mod): New.
(field_table): Add 'secp256k1'.
* tests/t-mpi-point.c (check_ec_mul): Add secp256k1 test vectors.
--
Benchmark on Ryzen 7 5800X (x86_64):
Before:
secp256k1 | nanosecs/iter cycles/iter auto Mhz
mult | 482336 2340443 4852
After (~20% faster):
secp256k1 | nanosecs/iter cycles/iter auto Mhz
mult | 392941 1906540 4852
Signed-off-by: Jussi Kivilinna <jussi.kivilinna@iki.fi>
Diffstat (limited to 'mpi/ec.c')
-rw-r--r-- | mpi/ec.c | 62 |
1 files changed, 62 insertions, 0 deletions
@@ -576,6 +576,59 @@ ec_pow2_448 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx) ec_mulm_448 (w, b, b, ctx); } + +/* Fast reduction for secp256k1 */ +static void +ec_secp256k1_mod (gcry_mpi_t w, mpi_ec_t ctx) +{ + mpi_size_t wsize = (256 + BITS_PER_MPI_LIMB - 1) / BITS_PER_MPI_LIMB; + mpi_limb_t n[wsize + 1]; + mpi_limb_t s[wsize + 1]; + mpi_limb_t cy, borrow; + mpi_ptr_t wp; + + MPN_NORMALIZE (w->d, w->nlimbs); + if (w->nlimbs > 2 * 256 / BITS_PER_MPI_LIMB) + log_bug ("W must be less than m^2\n"); + + RESIZE_AND_CLEAR_IF_NEEDED (w, wsize * 2); + + wp = w->d; + + /* mod P (2^256 - 2^32 - 977) */ + + /* first pass of reduction */ + memcpy (n, wp + wsize, wsize * BYTES_PER_MPI_LIMB); +#if BITS_PER_MPI_LIMB == 64 + s[wsize] = _gcry_mpih_lshift (s, wp + wsize, wsize, 32); +#else + s[0] = 0; + memcpy (s + 1, wp + wsize, wsize * BYTES_PER_MPI_LIMB); +#endif + wp[wsize] = _gcry_mpih_addmul_1 (wp, n, wsize, 977); + cy = _gcry_mpih_add_n (wp, wp, s, wsize + 1); + + /* second pass of reduction */ +#if BITS_PER_MPI_LIMB == 64 + /* cy == 0 */ + memset (n + 1, 0, (wsize - 1) * BYTES_PER_MPI_LIMB); + umul_ppmm(n[1], n[0], wp[wsize], ((mpi_limb_t)1 << 32) + 977); +#else + memset (n + 2, 0, (wsize - 2) * BYTES_PER_MPI_LIMB); + umul_ppmm(n[1], n[0], wp[wsize], 977); + add_ssaaaa(n[2], n[1], 0, n[1], 0, cy * 977); + add_ssaaaa(n[2], n[1], n[2], n[1], cy, wp[wsize]); +#endif + cy = _gcry_mpih_add_n (wp, wp, n, wsize); + + borrow = _gcry_mpih_sub_n (s, wp, ctx->p->d, wsize); + mpih_set_cond (wp, s, wsize, (cy != 0UL) | (borrow == 0UL)); + + w->nlimbs = wsize; + MPN_NORMALIZE (wp, w->nlimbs); +} + + struct field_table { const char *p; @@ -655,6 +708,15 @@ static const struct field_table field_table[] = { NULL, _gcry_mpi_ec_nist521_mod }, + { + "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", + NULL, + NULL, + NULL, + NULL, + NULL, + ec_secp256k1_mod + }, { NULL, NULL, NULL, NULL, NULL, NULL }, }; |