Add support for GOST GC256B curve

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>
Signed-off-by: Dmitry Baryshkov <dbaryshkov@gmail.com>

8 files changed, 188 insertions, 3 deletions

diff --git a/.gitignore b/.gitignore
index ea264107..4454ade5 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 5f88954b..807f422d 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-gost-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 \
@@ -376,12 +377,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-gost-gc256b.h: eccdata.stamp
+	./eccdata$(EXEEXT_FOR_BUILD) gost_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-gost-gc256b.$(OBJEXT): ecc-gost-gc256b.h
 ecc-secp192r1.$(OBJEXT): ecc-secp192r1.h
 ecc-secp224r1.$(OBJEXT): ecc-secp224r1.h
 ecc-secp256r1.$(OBJEXT): ecc-secp256r1.h
@@ -635,6 +645,7 @@ distcheck: dist
 clean-here:
 	-rm -f $(TARGETS) *.$(OBJEXT) *.$(OBJEXT).d *.s *.so *.dll *.a \
 		ecc-curve25519.h ecc-curve448.h \
+		ecc-gost-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 76024a19..da07b023 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_gost_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-gost-gc256b.c b/ecc-gost-gc256b.c
new file mode 100644
index 00000000..8adc8e17
--- /dev/null
+++ b/ecc-gost-gc256b.c
@@ -0,0 +1,128 @@
+/* ecc-gost-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-gost-gc256b.h"
+
+static void
+ecc_gost_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_gost_gc256b_modp ecc_gost_gc256b_modp
+#define ecc_gost_gc256b_modq ecc_mod
+
+const struct ecc_curve _nettle_gost_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_gost_gc256b_modp,
+    ecc_gost_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_gost_gc256b_modq,
+    ecc_gost_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_gost_gc256b(void)
+{
+  return &_nettle_gost_gc256b;
+}
diff --git a/ecc-internal.h b/ecc-internal.h
index c918632d..53305bc0 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_gost_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 d76a42bc..fd27d56a 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, "gost_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 d36d46b7..42035ca0 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_gost_gc256b,
 };
 
 #define numberof(x)  (sizeof (x) / sizeof ((x)[0]))
diff --git a/testsuite/testutils.c b/testsuite/testutils.c
index 7772d2b0..086bcbc8 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_gost_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)
     {