[PATCH 8/8] mpi/ec: add fast reduction for secp256k1
Jussi Kivilinna
jussi.kivilinna at iki.fi
Mon Apr 26 23:00:46 CEST 2021
* 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 at iki.fi>
---
mpi/ec.c | 62 +++++++++
tests/t-mpi-point.c | 304 ++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 366 insertions(+)
diff --git a/mpi/ec.c b/mpi/ec.c
index ae1d036a..29b2ce30 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -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 },
};
diff --git a/tests/t-mpi-point.c b/tests/t-mpi-point.c
index 0c4d8905..6cd030f1 100644
--- a/tests/t-mpi-point.c
+++ b/tests/t-mpi-point.c
@@ -3204,6 +3204,302 @@ check_ec_mul (void)
"68118D66A10BD9BF3AAF46FEC052F89ECAC38F795D8D3DBF77416B89602E99AF"
},
+ /* secp256k1 test-vectors from
+ https://chuckbatson.wordpress.com/2014/11/26/secp256k1-test-vectors/ */
+ { /* tv 260 */
+ "secp256k1",
+ "1",
+ "79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798",
+ "483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8"
+ },
+ { /* tv 261 */
+ "secp256k1",
+ "2",
+ "C6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5",
+ "1AE168FEA63DC339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A"
+ },
+ { /* tv 262 */
+ "secp256k1",
+ "3",
+ "F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9",
+ "388F7B0F632DE8140FE337E62A37F3566500A99934C2231B6CB9FD7584B8E672"
+ },
+ { /* tv 263 */
+ "secp256k1",
+ "4",
+ "E493DBF1C10D80F3581E4904930B1404CC6C13900EE0758474FA94ABE8C4CD13",
+ "51ED993EA0D455B75642E2098EA51448D967AE33BFBDFE40CFE97BDC47739922"
+ },
+ { /* tv 264 */
+ "secp256k1",
+ "5",
+ "2F8BDE4D1A07209355B4A7250A5C5128E88B84BDDC619AB7CBA8D569B240EFE4",
+ "D8AC222636E5E3D6D4DBA9DDA6C9C426F788271BAB0D6840DCA87D3AA6AC62D6"
+ },
+ { /* tv 265 */
+ "secp256k1",
+ "6",
+ "FFF97BD5755EEEA420453A14355235D382F6472F8568A18B2F057A1460297556",
+ "AE12777AACFBB620F3BE96017F45C560DE80F0F6518FE4A03C870C36B075F297"
+ },
+ { /* tv 266 */
+ "secp256k1",
+ "7",
+ "5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC",
+ "6AEBCA40BA255960A3178D6D861A54DBA813D0B813FDE7B5A5082628087264DA"
+ },
+ { /* tv 267 */
+ "secp256k1",
+ "8",
+ "2F01E5E15CCA351DAFF3843FB70F3C2F0A1BDD05E5AF888A67784EF3E10A2A01",
+ "5C4DA8A741539949293D082A132D13B4C2E213D6BA5B7617B5DA2CB76CBDE904"
+ },
+ { /* tv 268 */
+ "secp256k1",
+ "9",
+ "ACD484E2F0C7F65309AD178A9F559ABDE09796974C57E714C35F110DFC27CCBE",
+ "CC338921B0A7D9FD64380971763B61E9ADD888A4375F8E0F05CC262AC64F9C37"
+ },
+ { /* tv 269 */
+ "secp256k1",
+ "10",
+ "A0434D9E47F3C86235477C7B1AE6AE5D3442D49B1943C2B752A68E2A47E247C7",
+ "893ABA425419BC27A3B6C7E693A24C696F794C2ED877A1593CBEE53B037368D7"
+ },
+ { /* tv 270 */
+ "secp256k1",
+ "11",
+ "774AE7F858A9411E5EF4246B70C65AAC5649980BE5C17891BBEC17895DA008CB",
+ "D984A032EB6B5E190243DD56D7B7B365372DB1E2DFF9D6A8301D74C9C953C61B"
+ },
+ { /* tv 271 */
+ "secp256k1",
+ "12",
+ "D01115D548E7561B15C38F004D734633687CF4419620095BC5B0F47070AFE85A",
+ "A9F34FFDC815E0D7A8B64537E17BD81579238C5DD9A86D526B051B13F4062327"
+ },
+ { /* tv 272 */
+ "secp256k1",
+ "13",
+ "F28773C2D975288BC7D1D205C3748651B075FBC6610E58CDDEEDDF8F19405AA8",
+ "0AB0902E8D880A89758212EB65CDAF473A1A06DA521FA91F29B5CB52DB03ED81"
+ },
+ { /* tv 273 */
+ "secp256k1",
+ "14",
+ "499FDF9E895E719CFD64E67F07D38E3226AA7B63678949E6E49B241A60E823E4",
+ "CAC2F6C4B54E855190F044E4A7B3D464464279C27A3F95BCC65F40D403A13F5B"
+ },
+ { /* tv 274 */
+ "secp256k1",
+ "15",
+ "D7924D4F7D43EA965A465AE3095FF41131E5946F3C85F79E44ADBCF8E27E080E",
+ "581E2872A86C72A683842EC228CC6DEFEA40AF2BD896D3A5C504DC9FF6A26B58"
+ },
+ { /* tv 275 */
+ "secp256k1",
+ "16",
+ "E60FCE93B59E9EC53011AABC21C23E97B2A31369B87A5AE9C44EE89E2A6DEC0A",
+ "F7E3507399E595929DB99F34F57937101296891E44D23F0BE1F32CCE69616821"
+ },
+ { /* tv 276 */
+ "secp256k1",
+ "17",
+ "DEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34",
+ "4211AB0694635168E997B0EAD2A93DAECED1F4A04A95C0F6CFB199F69E56EB77"
+ },
+ { /* tv 277 */
+ "secp256k1",
+ "18",
+ "5601570CB47F238D2B0286DB4A990FA0F3BA28D1A319F5E7CF55C2A2444DA7CC",
+ "C136C1DC0CBEB930E9E298043589351D81D8E0BC736AE2A1F5192E5E8B061D58"
+ },
+ { /* tv 278 */
+ "secp256k1",
+ "19",
+ "2B4EA0A797A443D293EF5CFF444F4979F06ACFEBD7E86D277475656138385B6C",
+ "85E89BC037945D93B343083B5A1C86131A01F60C50269763B570C854E5C09B7A"
+ },
+ { /* tv 279 */
+ "secp256k1",
+ "20",
+ "4CE119C96E2FA357200B559B2F7DD5A5F02D5290AFF74B03F3E471B273211C97",
+ "12BA26DCB10EC1625DA61FA10A844C676162948271D96967450288EE9233DC3A"
+ },
+ { /* tv 280 */
+ "secp256k1",
+ "112233445566778899",
+ "A90CC3D3F3E146DAADFC74CA1372207CB4B725AE708CEF713A98EDD73D99EF29",
+ "5A79D6B289610C68BC3B47F3D72F9788A26A06868B4D8E433E1E2AD76FB7DC76"
+ },
+ { /* tv 281 */
+ "secp256k1",
+ "112233445566778899112233445566778899",
+ "E5A2636BCFD412EBF36EC45B19BFB68A1BC5F8632E678132B885F7DF99C5E9B3",
+ "736C1CE161AE27B405CAFD2A7520370153C2C861AC51D6C1D5985D9606B45F39"
+ },
+ { /* tv 282 */
+ "secp256k1",
+ "28948022309329048855892746252171976963209391069768726095651290785379"
+ "540373584",
+ "A6B594B38FB3E77C6EDF78161FADE2041F4E09FD8497DB776E546C41567FEB3C",
+ "71444009192228730CD8237A490FEBA2AFE3D27D7CC1136BC97E439D13330D55"
+ },
+ { /* tv 283 */
+ "secp256k1",
+ "57896044618658097711785492504343953926418782139537452191302581570759"
+ "080747168",
+ "00000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C63",
+ "3F3979BF72AE8202983DC989AEC7F2FF2ED91BDD69CE02FC0700CA100E59DDF3"
+ },
+ { /* tv 284 */
+ "secp256k1",
+ "86844066927987146567678238756515930889628173209306178286953872356138"
+ "621120752",
+ "E24CE4BEEE294AA6350FAA67512B99D388693AE4E7F53D19882A6EA169FC1CE1",
+ "8B71E83545FC2B5872589F99D948C03108D36797C4DE363EBD3FF6A9E1A95B10"
+ },
+ { /* tv 285 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494317",
+ "4CE119C96E2FA357200B559B2F7DD5A5F02D5290AFF74B03F3E471B273211C97",
+ "ED45D9234EF13E9DA259E05EF57BB3989E9D6B7D8E269698BAFD77106DCC1FF5"
+ },
+ { /* tv 286 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494318",
+ "2B4EA0A797A443D293EF5CFF444F4979F06ACFEBD7E86D277475656138385B6C",
+ "7A17643FC86BA26C4CBCF7C4A5E379ECE5FE09F3AFD9689C4A8F37AA1A3F60B5"
+ },
+ { /* tv 287 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494319",
+ "5601570CB47F238D2B0286DB4A990FA0F3BA28D1A319F5E7CF55C2A2444DA7CC",
+ "3EC93E23F34146CF161D67FBCA76CAE27E271F438C951D5E0AE6D1A074F9DED7"
+ },
+ { /* tv 288 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494320",
+ "DEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34",
+ "BDEE54F96B9CAE9716684F152D56C251312E0B5FB56A3F09304E660861A910B8"
+ },
+ { /* tv 289 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494321",
+ "E60FCE93B59E9EC53011AABC21C23E97B2A31369B87A5AE9C44EE89E2A6DEC0A",
+ "081CAF8C661A6A6D624660CB0A86C8EFED6976E1BB2DC0F41E0CD330969E940E"
+ },
+ { /* tv 290 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494322",
+ "D7924D4F7D43EA965A465AE3095FF41131E5946F3C85F79E44ADBCF8E27E080E",
+ "A7E1D78D57938D597C7BD13DD733921015BF50D427692C5A3AFB235F095D90D7"
+ },
+ { /* tv 291 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494323",
+ "499FDF9E895E719CFD64E67F07D38E3226AA7B63678949E6E49B241A60E823E4",
+ "353D093B4AB17AAE6F0FBB1B584C2B9BB9BD863D85C06A4339A0BF2AFC5EBCD4"
+ },
+ { /* tv 292 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494324",
+ "F28773C2D975288BC7D1D205C3748651B075FBC6610E58CDDEEDDF8F19405AA8",
+ "F54F6FD17277F5768A7DED149A3250B8C5E5F925ADE056E0D64A34AC24FC0EAE"
+ },
+ { /* tv 293 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494325",
+ "D01115D548E7561B15C38F004D734633687CF4419620095BC5B0F47070AFE85A",
+ "560CB00237EA1F285749BAC81E8427EA86DC73A2265792AD94FAE4EB0BF9D908"
+ },
+ { /* tv 294 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494326",
+ "774AE7F858A9411E5EF4246B70C65AAC5649980BE5C17891BBEC17895DA008CB",
+ "267B5FCD1494A1E6FDBC22A928484C9AC8D24E1D20062957CFE28B3536AC3614"
+ },
+ { /* tv 295 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494327",
+ "A0434D9E47F3C86235477C7B1AE6AE5D3442D49B1943C2B752A68E2A47E247C7",
+ "76C545BDABE643D85C4938196C5DB3969086B3D127885EA6C3411AC3FC8C9358"
+ },
+ { /* tv 296 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494328",
+ "ACD484E2F0C7F65309AD178A9F559ABDE09796974C57E714C35F110DFC27CCBE",
+ "33CC76DE4F5826029BC7F68E89C49E165227775BC8A071F0FA33D9D439B05FF8"
+ },
+ { /* tv 297 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494329",
+ "2F01E5E15CCA351DAFF3843FB70F3C2F0A1BDD05E5AF888A67784EF3E10A2A01",
+ "A3B25758BEAC66B6D6C2F7D5ECD2EC4B3D1DEC2945A489E84A25D3479342132B"
+ },
+ { /* tv 298 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494330",
+ "5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC",
+ "951435BF45DAA69F5CE8729279E5AB2457EC2F47EC02184A5AF7D9D6F78D9755"
+ },
+ { /* tv 299 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494331",
+ "FFF97BD5755EEEA420453A14355235D382F6472F8568A18B2F057A1460297556",
+ "51ED8885530449DF0C4169FE80BA3A9F217F0F09AE701B5FC378F3C84F8A0998"
+ },
+ { /* tv 300 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494332",
+ "2F8BDE4D1A07209355B4A7250A5C5128E88B84BDDC619AB7CBA8D569B240EFE4",
+ "2753DDD9C91A1C292B24562259363BD90877D8E454F297BF235782C459539959"
+ },
+ { /* tv 301 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494333",
+ "E493DBF1C10D80F3581E4904930B1404CC6C13900EE0758474FA94ABE8C4CD13",
+ "AE1266C15F2BAA48A9BD1DF6715AEBB7269851CC404201BF30168422B88C630D"
+ },
+ { /* tv 302 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494334",
+ "F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9",
+ "C77084F09CD217EBF01CC819D5C80CA99AFF5666CB3DDCE4934602897B4715BD"
+ },
+ { /* tv 303 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494335",
+ "C6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5",
+ "E51E970159C23CC65C3A7BE6B99315110809CD9ACD992F1EDC9BCE55AF301705"
+ },
+ { /* tv 304 */
+ "secp256k1",
+ "11579208923731619542357098500868790785283756427907490438260516314151"
+ "8161494336",
+ "79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798",
+ "B7C52588D95C3B9AA25B0403F1EEF75702E84BB7597AABE663B82F6F04EF2777"
+ },
+
{ NULL, NULL, NULL, NULL }
};
gpg_error_t err;
@@ -3225,6 +3521,14 @@ check_ec_mul (void)
once = 1;
continue;
}
+ if (!strcmp(tv[idx].curve, "secp256k1"))
+ {
+ static int once;
+ if (!once)
+ info ("skipping %s in fips mode\n", tv[idx].curve);
+ once = 1;
+ continue;
+ }
}
err = gcry_mpi_ec_new (&ctx, NULL, tv[idx].curve);
--
2.30.2
More information about the Gcrypt-devel
mailing list