From: Dmitry Eremin-Solenikov dbaryshkov@gmail.com
Add support for GC256B curve ("TLS Supported Groups" registry, draft-smyshlyaev-tls12-gost-suites) also known as GostR3410-2001-CryptoPro-A and GostR3410-2001-CryptoPro-XchA (RFC 4357).
Signed-off-by: Dmitry Eremin-Solenikov dbaryshkov@gmail.com --- .gitignore | 1 + Makefile.in | 11 ++++ ecc-curve.h | 1 + ecc-gc256b.c | 128 +++++++++++++++++++++++++++++++++++++++ ecc-internal.h | 3 + eccdata.c | 34 ++++++++++- examples/ecc-benchmark.c | 1 + testsuite/testutils.c | 12 +++- 8 files changed, 188 insertions(+), 3 deletions(-) create mode 100644 ecc-gc256b.c
diff --git a/.gitignore b/.gitignore index ea264107fa40..4454ade5a950 100644 --- a/.gitignore +++ b/.gitignore @@ -45,6 +45,7 @@ core /rotors.h /ecc-curve25519.h /ecc-curve448.h +/ecc-gc256b.h /ecc-secp192r1.h /ecc-secp224r1.h /ecc-secp256r1.h diff --git a/Makefile.in b/Makefile.in index 38160bb40fe1..8815e7b76dea 100644 --- a/Makefile.in +++ b/Makefile.in @@ -176,6 +176,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \ ecc-mod.c ecc-mod-inv.c \ ecc-mod-arith.c ecc-pp1-redc.c ecc-pm1-redc.c \ ecc-curve25519.c ecc-curve448.c \ + ecc-gc256b.c \ ecc-secp192r1.c ecc-secp224r1.c ecc-secp256r1.c \ ecc-secp384r1.c ecc-secp521r1.c \ ecc-size.c ecc-j-to-a.c ecc-a-to-j.c \ @@ -396,12 +397,21 @@ ecc-curve25519.h: eccdata.stamp ecc-curve448.h: eccdata.stamp ./eccdata$(EXEEXT_FOR_BUILD) curve448 38 6 $(NUMB_BITS) > $@T && mv $@T $@
+# Some reasonable choices for 256: +# k = 9, c = 6, S = 320, T = 54 ( 45 A + 9 D) 20 KB +# k = 11, c = 6, S = 256, T = 55 ( 44 A + 11 D) 16 KB +# k = 19, c = 7, S = 256, T = 57 ( 38 A + 19 D) 16 KB +# k = 15, c = 6, S = 192, T = 60 ( 45 A + 15 D) 12 KB +ecc-gc256b.h: eccdata.stamp + ./eccdata$(EXEEXT_FOR_BUILD) gc256b 11 6 $(NUMB_BITS) > $@T && mv $@T $@ + eccdata.stamp: eccdata.c $(MAKE) eccdata$(EXEEXT_FOR_BUILD) echo stamp > eccdata.stamp
ecc-curve25519.$(OBJEXT): ecc-curve25519.h ecc-curve448.$(OBJEXT): ecc-curve448.h +ecc-gc256b.$(OBJEXT): ecc-gc256b.h ecc-secp192r1.$(OBJEXT): ecc-secp192r1.h ecc-secp224r1.$(OBJEXT): ecc-secp224r1.h ecc-secp256r1.$(OBJEXT): ecc-secp256r1.h @@ -660,6 +670,7 @@ distcheck: dist clean-here: -rm -f $(TARGETS) *.$(OBJEXT) *.s *.so *.dll *.a \ ecc-curve25519.h ecc-curve448.h \ + ecc-gc256b.h \ ecc-secp192r1.h ecc-secp224r1.h ecc-secp256r1.h \ ecc-secp384r1.h ecc-secp521r1.h \ aesdata$(EXEEXT_FOR_BUILD) \ diff --git a/ecc-curve.h b/ecc-curve.h index 76024a19d24f..b378c8489839 100644 --- a/ecc-curve.h +++ b/ecc-curve.h @@ -43,6 +43,7 @@ extern "C" { /* The contents of this struct is internal. */ struct ecc_curve;
+const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_gc256b(void); const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_secp_192r1(void); const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_secp_224r1(void); const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_secp_256r1(void); diff --git a/ecc-gc256b.c b/ecc-gc256b.c new file mode 100644 index 000000000000..b2d12d0bdf7c --- /dev/null +++ b/ecc-gc256b.c @@ -0,0 +1,128 @@ +/* ecc-gc256b.c + + Copyright (C) 2016-2020 Dmitry Eremin-Solenikov + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <assert.h> + +#include "ecc.h" +#include "ecc-internal.h" + +#define USE_REDC 0 + +#include "ecc-gc256b.h" + +static void +ecc_gc256b_modp (const struct ecc_modulo *m, mp_limb_t *rp) +{ + mp_size_t mn = m->size; + mp_limb_t hi; + + hi = mpn_addmul_1(rp, rp + mn, mn, 0x269); + hi = sec_add_1 (rp, rp, mn, hi * 0x269); + hi = sec_add_1 (rp, rp, mn, hi * 0x269); + assert(hi == 0); +} + +#define ecc_gc256b_modp ecc_gc256b_modp +#define ecc_gc256b_modq ecc_mod + +const struct ecc_curve _nettle_gc256b = +{ + { + 256, + ECC_LIMB_SIZE, + ECC_BMODP_SIZE, + ECC_REDC_SIZE, + ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + 0, + + ecc_p, + ecc_Bmodp, + ecc_Bmodp_shifted, + ecc_redc_ppm1, + + ecc_pp1h, + ecc_gc256b_modp, + ecc_gc256b_modp, + ecc_mod_inv, + NULL, + }, + { + 256, + ECC_LIMB_SIZE, + ECC_BMODQ_SIZE, + 0, + ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + 0, + + ecc_q, + ecc_Bmodq, + ecc_Bmodq_shifted, + NULL, + ecc_qp1h, + + ecc_gc256b_modq, + ecc_gc256b_modq, + ecc_mod_inv, + NULL, + }, + + USE_REDC, + ECC_PIPPENGER_K, + ECC_PIPPENGER_C, + + ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE), + ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + 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), + + ecc_add_jja, + ecc_add_jjj, + ecc_dup_jj, + ecc_mul_a, + ecc_mul_g, + ecc_j_to_a, + + ecc_b, + ecc_g, + ecc_unit, + ecc_table +}; + +const struct ecc_curve *nettle_get_gc256b(void) +{ + return &_nettle_gc256b; +} diff --git a/ecc-internal.h b/ecc-internal.h index c918632df292..0972efaf10d1 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -91,6 +91,9 @@ extern const struct ecc_curve _nettle_secp_521r1; extern const struct ecc_curve _nettle_curve25519; extern const struct ecc_curve _nettle_curve448;
+/* GOST curves, visible with underscore prefix for now */ +extern const struct ecc_curve _nettle_gc256b; + #define ECC_MAX_SIZE ((521 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS)
/* Window size for ecc_mul_a. Using 4 bits seems like a good choice, diff --git a/eccdata.c b/eccdata.c index d76a42bcde6f..3820e150125b 100644 --- a/eccdata.c +++ b/eccdata.c @@ -674,6 +674,38 @@ ecc_curve_init (struct ecc_curve *ecc, const char *curve) "47d0e827cb1595e1470eb88580d5716c" "4cf22832ea2f0ff0df38ab61ca32112f"); } + else if (!strcmp (curve, "gc256b")) + { + ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, + "ffffffffffffffffffffffffffffffff" + "fffffffffffffffffffffffffffffd97", + + "00000000000000000000000000000000" + "000000000000000000000000000000a6", + + "ffffffffffffffffffffffffffffffff" + "6c611070995ad10045841b09b761b893", + + "00000000000000000000000000000000" + "00000000000000000000000000000001", + + "8d91e471e0989cda27df505a453f2b76" + "35294f2ddf23e3b122acc99c9e9f1e14"); + + ecc->ref = ecc_alloc (3); + ecc_set_str (&ecc->ref[0], /* 2 g */ + "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd95", + "726e1b8e1f676325d820afa5bac0d489cad6b0d220dc1c4edd5336636160df83"); + + ecc_set_str (&ecc->ref[1], /* 3 g */ + "8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38d2c", + "76bcd1ca9a23b041d4d9baf507a6cd821267a94c838768e8486117796b788a51"); + + ecc_set_str (&ecc->ref[2], /* 4 g */ + "f7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e4b7", + "83ccf17ba6706d73625cc3534c7a2b9d6ec1ee6a9a7e07c10d84b388de59f741"); + + } else if (!strcmp (curve, "curve448")) { /* curve448, y^2 = x^3 + 156326 x^2 + x (mod p), with p = 2^{448} - 2^{224} - 1. @@ -1316,7 +1348,7 @@ main (int argc, char **argv)
if (argc < 4) { - fprintf (stderr, "Usage: %s CURVE-BITS K C [BITS-PER-LIMB]\n", argv[0]); + fprintf (stderr, "Usage: %s CURVE K C [BITS-PER-LIMB]\n", argv[0]); return EXIT_FAILURE; }
diff --git a/examples/ecc-benchmark.c b/examples/ecc-benchmark.c index d36d46b77bc1..497c76c3e550 100644 --- a/examples/ecc-benchmark.c +++ b/examples/ecc-benchmark.c @@ -314,6 +314,7 @@ const struct ecc_curve * const curves[] = { &_nettle_secp_384r1, &_nettle_curve448, &_nettle_secp_521r1, + &_nettle_gc256b, };
#define numberof(x) (sizeof (x) / sizeof ((x)[0])) diff --git a/testsuite/testutils.c b/testsuite/testutils.c index 7772d2b01661..e4e7c23dcc1b 100644 --- a/testsuite/testutils.c +++ b/testsuite/testutils.c @@ -1677,6 +1677,7 @@ const struct ecc_curve * const ecc_curves[] = { &_nettle_secp_521r1, &_nettle_curve25519, &_nettle_curve448, + &_nettle_gc256b, NULL };
@@ -1728,7 +1729,7 @@ void test_ecc_mul_a (unsigned curve, unsigned n, const mp_limb_t *p) { /* For each curve, the points 2 g, 3 g and 4 g */ - static const struct ecc_ref_point ref[7][3] = { + static const struct ecc_ref_point ref[8][3] = { { { "dafebf5828783f2ad35534631588a3f629a70fb16982a888", "dd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab" }, { "76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da", @@ -1796,9 +1797,16 @@ test_ecc_mul_a (unsigned curve, unsigned n, const mp_limb_t *p) "e005a8dbd5125cf706cbda7ad43aa6449a4a8d952356c3b9fce43c82ec4e1d58bb3a331bdb6767f0bffa9a68fed02dafb822ac13588ed6fc" }, { "49dcbc5c6c0cce2c1419a17226f929ea255a09cf4e0891c693fda4be70c74cc301b7bdf1515dd8ba21aee1798949e120e2ce42ac48ba7f30", "d49077e4accde527164b33a5de021b979cb7c02f0457d845c90dc3227b8a5bc1c0d8f97ea1ca9472b5d444285d0d4f5b32e236f86de51839" }, + }, + { { "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd95", + "726e1b8e1f676325d820afa5bac0d489cad6b0d220dc1c4edd5336636160df83" }, + { "8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38d2c", + "76bcd1ca9a23b041d4d9baf507a6cd821267a94c838768e8486117796b788a51" }, + { "f7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e4b7", + "83ccf17ba6706d73625cc3534c7a2b9d6ec1ee6a9a7e07c10d84b388de59f741" }, } }; - assert (curve < 7); + assert (curve < 8); assert (n <= 4); if (n == 0) {