Merge branch 'ecc-gost'

24 files changed, 1452 insertions, 6 deletions

diff --git a/.gitignore b/.gitignore
index ea264107..48e2b7f4 100644
--- a/.gitignore
+++ b/.gitignore
@@ -45,6 +45,8 @@ core
 /rotors.h
 /ecc-curve25519.h
 /ecc-curve448.h
+/ecc-gost-gc256b.h
+/ecc-gost-gc512a.h
 /ecc-secp192r1.h
 /ecc-secp224r1.h
 /ecc-secp256r1.h
diff --git a/ChangeLog b/ChangeLog
index 1946eda8..38781996 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,32 @@
 2020-01-26  Niels Möller  <nisse@lysator.liu.se>
 
+	Support for GOST DSA, contributed by Dmitry Baryshkov.
+	* gostdsa-verify.c (gostdsa_verify): New file and function.
+	* gostdsa-sign.c (gostdsa_sign): New file and function.
+	* ecc-gostdsa-verify.c (ecdsa_in_range, ecc_gostdsa_verify_itch)
+	(ecc_gostdsa_verify): New file and functions.
+	* ecc-gostdsa-sign.c (ecc_gostdsa_sign_itch, ecc_gostdsa_sign):
+	New file and functions.
+	* ecc-internal.h (ECC_GOSTDSA_SIGN_ITCH): New macro.
+	* ecc-hash.c (gost_hash): New function.
+	* testsuite/gostdsa-verify-test.c: New test.
+	* testsuite/gostdsa-sign-test.c: New test.
+	* testsuite/gostdsa-keygen-test.c: New test.
+	* testsuite/Makefile.in (TS_HOGWEED_SOURCES): Add new tests.
+
+	Support for GOST gc256b and gc512a curves, contributed by Dmitry
+	Baryshkov.
+	* eccdata.c (ecc_curve_init): Add parameters for gost_gc256b and
+	gost_gc512a.
+	* ecc-gost-gc256b.c: New file, define _nettle_gost_gc256b.
+	* ecc-gost-gc512a.c: New file, define _nettle_gost_gc512a.
+	* Makefile.in: Add rules to generate ecc-gost-gc256b.h and
+	ecc-gost-gc512a.h.
+	(hogweed_SOURCES): Add ecc-gost-gc256b.c ecc-gost-gc512a.c.
+	* examples/ecc-benchmark.c (curves): Add to list.
+	* testsuite/testutils.c (ecc_curves): Add to list.
+	(test_ecc_mul_a): Reference points for new curves.
+
 	* NEWS: Started on entries for Nettle-3.6.
 
 2020-01-25  Niels Möller  <nisse@lysator.liu.se>
diff --git a/Makefile.in b/Makefile.in
index 5f88954b..f876e5e8 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-gost-gc512a.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 \
@@ -188,6 +189,8 @@ hogweed_SOURCES = sexp.c sexp-format.c \
 		  ecc-point.c ecc-scalar.c ecc-point-mul.c ecc-point-mul-g.c \
 		  ecc-ecdsa-sign.c ecdsa-sign.c \
 		  ecc-ecdsa-verify.c ecdsa-verify.c ecdsa-keygen.c \
+		  ecc-gostdsa-sign.c gostdsa-sign.c \
+		  ecc-gostdsa-verify.c gostdsa-verify.c \
 		  curve25519-mul-g.c curve25519-mul.c curve25519-eh-to-x.c \
 		  curve448-mul-g.c curve448-mul.c curve448-eh-to-x.c \
 		  eddsa-compress.c eddsa-decompress.c eddsa-expand.c \
@@ -204,7 +207,7 @@ HEADERS = aes.h arcfour.h arctwo.h asn1.h blowfish.h \
 	  cbc.h ccm.h cfb.h chacha.h chacha-poly1305.h ctr.h \
 	  curve25519.h curve448.h des.h dsa.h dsa-compat.h eax.h \
 	  ecc-curve.h ecc.h ecdsa.h eddsa.h \
-	  gcm.h gost28147.h gosthash94.h hmac.h \
+	  gcm.h gost28147.h gostdsa.h gosthash94.h hmac.h \
 	  knuth-lfib.h hkdf.h \
 	  macros.h \
 	  cmac.h siv-cmac.h \
@@ -376,12 +379,31 @@ 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 $@
+
+# Some reasonable choices for 512:
+# k = 22, c =  6, S = 256, T = 110 ( 88 A + 22 D) 32 KB
+# k = 29, c =  6, S = 192, T = 116 ( 87 A + 29 D) 24 KB
+# k = 21, c =  5, S = 160, T = 126 (105 A + 21 D) 20 KB
+# k = 43, c =  6, S = 128, T = 129 ( 86 A + 43 D) 16 KB
+# k = 35, c =  5, S =  96, T = 140 (105 A + 35 D) 12 KB
+ecc-gost-gc512a.h: eccdata.stamp
+	./eccdata$(EXEEXT_FOR_BUILD) gost_gc512a 43 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-gost-gc512a.$(OBJEXT): ecc-gost-gc512a.h
 ecc-secp192r1.$(OBJEXT): ecc-secp192r1.h
 ecc-secp224r1.$(OBJEXT): ecc-secp224r1.h
 ecc-secp256r1.$(OBJEXT): ecc-secp256r1.h
@@ -635,6 +657,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-gost-gc512a.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..8f050404 100644
--- a/ecc-curve.h
+++ b/ecc-curve.h
@@ -43,6 +43,8 @@ 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_gost_gc512a(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-gost-gc512a.c b/ecc-gost-gc512a.c
new file mode 100644
index 00000000..6d210925
--- /dev/null
+++ b/ecc-gost-gc512a.c
@@ -0,0 +1,128 @@
+/* ecc-gost-gc512a.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-gc512a.h"
+
+static void
+ecc_gost_gc512a_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, 0x239);
+  hi = sec_add_1 (rp, rp, mn, hi * 0x239);
+  hi = sec_add_1 (rp, rp, mn, hi * 0x239);
+  assert(hi == 0);
+}
+
+#define ecc_gost_gc512a_modp ecc_gost_gc512a_modp
+#define ecc_gost_gc512a_modq ecc_mod
+
+const struct ecc_curve _nettle_gost_gc512a =
+{
+  {
+    512,
+    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_gc512a_modp,
+    ecc_gost_gc512a_modp,
+    ecc_mod_inv,
+    NULL,
+  },
+  {
+    512,
+    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_gc512a_modq,
+    ecc_gost_gc512a_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_gc512a(void)
+{
+  return &_nettle_gost_gc512a;
+}
diff --git a/ecc-gostdsa-sign.c b/ecc-gostdsa-sign.c
new file mode 100644
index 00000000..00eeef81
--- /dev/null
+++ b/ecc-gostdsa-sign.c
@@ -0,0 +1,101 @@
+/* ecc-gostdsa-sign.c
+
+   Copyright (C) 2015 Dmitry Eremin-Solenikov
+   Copyright (C) 2013, 2014 Niels Möller
+
+   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 <stdlib.h>
+
+#include "gostdsa.h"
+#include "ecc-internal.h"
+
+/* Low-level GOST DSA signing */
+
+mp_size_t
+ecc_gostdsa_sign_itch (const struct ecc_curve *ecc)
+{
+  /* Needs 3*ecc->p.size + scratch for ecc->mul_g. Currently same for
+     ecc_mul_g and ecc_mul_g_eh. */
+  return ECC_GOSTDSA_SIGN_ITCH (ecc->p.size);
+}
+
+/* NOTE: Caller should check if r or s is zero. */
+void
+ecc_gostdsa_sign (const struct ecc_curve *ecc,
+		const mp_limb_t *zp,
+		const mp_limb_t *kp,
+		size_t length, const uint8_t *digest,
+		mp_limb_t *rp, mp_limb_t *sp,
+		mp_limb_t *scratch)
+{
+#define P	    scratch
+#define hp	    (scratch + 4*ecc->p.size)
+#define tp	    (scratch + 2*ecc->p.size)
+#define t2p	    scratch
+  /* Procedure, according to GOST 34.10. q denotes the group
+     order.
+
+     1. k <-- uniformly random, 0 < k < q
+
+     2. C <-- (c_x, c_y) = k g
+
+     3. r <-- c_x mod q
+
+     4. s <-- (r*z + k*h) mod q.
+  */
+
+  ecc->mul_g (ecc, P, kp, P + 3*ecc->p.size);
+  /* x coordinate only, modulo q */
+  ecc->h_to_a (ecc, 2, rp, P, P + 3*ecc->p.size);
+
+  /* Process hash digest */
+  gost_hash (&ecc->q, hp, length, digest);
+  if (mpn_zero_p (hp, ecc->p.size))
+    mpn_add_1 (hp, hp, ecc->p.size, 1);
+
+  ecc_modq_mul (ecc, tp, rp, zp);
+  ecc_modq_mul (ecc, t2p, kp, hp);
+  ecc_modq_add (ecc, sp, tp, t2p);
+
+  /* Also reduce mod ecc->q. It should already be < 2*ecc->q,
+   * so one subtraction should suffice. */
+
+  *scratch = mpn_sub_n (tp, sp, ecc->q.m, ecc->p.size);
+  cnd_copy (*scratch == 0, sp, tp, ecc->p.size);
+
+#undef P
+#undef hp
+#undef tp
+#undef t2p
+}
diff --git a/ecc-gostdsa-verify.c b/ecc-gostdsa-verify.c
new file mode 100644
index 00000000..4358132b
--- /dev/null
+++ b/ecc-gostdsa-verify.c
@@ -0,0 +1,130 @@
+/* ecc-gostdsa-verify.c
+
+   Copyright (C) 2015 Dmitry Eremin-Solenikov
+   Copyright (C) 2013, 2014 Niels Möller
+
+   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 <stdlib.h>
+
+#include "gostdsa.h"
+#include "ecc-internal.h"
+
+/* Low-level GOST DSA verify */
+
+static int
+ecdsa_in_range (const struct ecc_curve *ecc, const mp_limb_t *xp)
+{
+  return !mpn_zero_p (xp, ecc->p.size)
+    && mpn_cmp (xp, ecc->q.m, ecc->p.size) < 0;
+}
+
+mp_size_t
+ecc_gostdsa_verify_itch (const struct ecc_curve *ecc)
+{
+  /* Largest storage need is for the ecc->mul call. */
+  return 5*ecc->p.size + ecc->mul_itch;
+}
+
+/* FIXME: Use faster primitives, not requiring side-channel silence. */
+int
+ecc_gostdsa_verify (const struct ecc_curve *ecc,
+		  const mp_limb_t *pp, /* Public key */
+		  size_t length, const uint8_t *digest,
+		  const mp_limb_t *rp, const mp_limb_t *sp,
+		  mp_limb_t *scratch)
+{
+  /* Procedure, according to GOST R 34.10. q denotes the group
+     order.
+
+     1. Check 0 < r, s < q.
+
+     2. v <-- h^{-1}  (mod q)
+
+     3. z1  <-- s * v (mod q)
+
+     4. z2  <-- -r * v (mod q)
+
+     5. R = u1 G + u2 Y
+
+     6. Signature is valid if R_x = r (mod q).
+  */
+
+#define hp (scratch)
+#define vp (scratch + ecc->p.size)
+#define z1 (scratch + 3*ecc->p.size)
+#define z2 (scratch + 4*ecc->p.size)
+
+#define P1 (scratch + 4*ecc->p.size)
+#define P2 (scratch)
+
+
+  if (! (ecdsa_in_range (ecc, rp)
+	 && ecdsa_in_range (ecc, sp)))
+    return 0;
+
+  gost_hash (&ecc->q, hp, length, digest);
+
+  if (mpn_zero_p (hp, ecc->p.size))
+    mpn_add_1 (hp, hp, ecc->p.size, 1);
+
+  /* Compute v */
+  ecc->q.invert (&ecc->q, vp, hp, vp + 2*ecc->p.size);
+
+  /* z1 = s / h, P1 = z1 * G */
+  ecc_modq_mul (ecc, z1, sp, vp);
+
+  /* z2 = - r / h, P2 = z2 * Y */
+  ecc_modq_mul (ecc, z2, rp, vp);
+  mpn_sub_n (z2, ecc->q.m, z2, ecc->p.size);
+
+   /* Total storage: 5*ecc->p.size + ecc->mul_itch */
+  ecc->mul (ecc, P2, z2, pp, z2 + ecc->p.size);
+
+  /* Total storage: 7*ecc->p.size + ecc->mul_g_itch (ecc->p.size) */
+  ecc->mul_g (ecc, P1, z1, P1 + 3*ecc->p.size);
+
+  /* Total storage: 6*ecc->p.size + ecc->add_hhh_itch */
+  ecc->add_hhh (ecc, P1, P1, P2, P1 + 3*ecc->p.size);
+
+  /* x coordinate only, modulo q */
+  ecc->h_to_a (ecc, 2, P2, P1, P1 + 3*ecc->p.size);
+
+  return (mpn_cmp (rp, P2, ecc->p.size) == 0);
+#undef P2
+#undef P1
+#undef z2
+#undef z1
+#undef hp
+#undef vp
+}
diff --git a/ecc-hash.c b/ecc-hash.c
index 4e830a51..07877110 100644
--- a/ecc-hash.c
+++ b/ecc-hash.c
@@ -62,3 +62,14 @@ ecc_hash (const struct ecc_modulo *m,
     /* We got a few extra bits, at the low end. Discard them. */
     mpn_rshift (hp, hp, m->size + 1, 8*length - m->bit_size);
 }
+
+void
+gost_hash (const struct ecc_modulo *m,
+	   mp_limb_t *hp,
+	   size_t length, const uint8_t *digest)
+{
+  if (length > ((size_t) m->bit_size + 7) / 8)
+    length = (m->bit_size + 7) / 8;
+
+  mpn_set_base256_le (hp, m->size + 1, digest, length);
+}
diff --git a/ecc-internal.h b/ecc-internal.h
index c918632d..0022e0ab 100644
--- a/ecc-internal.h
+++ b/ecc-internal.h
@@ -53,6 +53,7 @@
 #define ecc_mod _nettle_ecc_mod
 #define ecc_mod_inv _nettle_ecc_mod_inv
 #define ecc_hash _nettle_ecc_hash
+#define gost_hash _nettle_gost_hash
 #define ecc_a_to_j _nettle_ecc_a_to_j
 #define ecc_j_to_a _nettle_ecc_j_to_a
 #define ecc_eh_to_a _nettle_ecc_eh_to_a
@@ -91,6 +92,10 @@ 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;
+extern const struct ecc_curve _nettle_gost_gc512a;
+
 #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,
@@ -284,6 +289,11 @@ ecc_hash (const struct ecc_modulo *m,
 	  mp_limb_t *hp,
 	  size_t length, const uint8_t *digest);
 
+void
+gost_hash (const struct ecc_modulo *m,
+	  mp_limb_t *hp,
+	  size_t length, const uint8_t *digest);
+
 /* Converts a point P in affine coordinates into a point R in jacobian
    coordinates. */
 void
@@ -452,6 +462,7 @@ curve448_eh_to_x (mp_limb_t *xp, const mp_limb_t *p,
 #endif
 #define ECC_MUL_M_ITCH(size) (11*(size))
 #define ECC_ECDSA_SIGN_ITCH(size) (12*(size))
+#define ECC_GOSTDSA_SIGN_ITCH(size) (12*(size))
 #define ECC_MOD_RANDOM_ITCH(size) (size)
 #define ECC_HASH_ITCH(size) (1+(size))
 
diff --git a/eccdata.c b/eccdata.c
index d76a42bc..06b6937a 100644
--- a/eccdata.c
+++ b/eccdata.c
@@ -674,6 +674,76 @@ 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, "gost_gc512a"))
+    {
+      ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS,
+			  "ffffffffffffffffffffffffffffffff"
+			  "ffffffffffffffffffffffffffffffff"
+			  "ffffffffffffffffffffffffffffffff"
+			  "fffffffffffffffffffffffffffffdc7",
+			  "e8c2505dedfc86ddc1bd0b2b6667f1da"
+			  "34b82574761cb0e879bd081cfd0b6265"
+			  "ee3cb090f30d27614cb4574010da90dd"
+			  "862ef9d4ebee4761503190785a71c760",
+			  "ffffffffffffffffffffffffffffffff"
+			  "ffffffffffffffffffffffffffffffff"
+			  "27e69532f48d89116ff22b8d4e056060"
+			  "9b4b38abfad2b85dcacdb1411f10b275",
+			  "00000000000000000000000000000000"
+			  "00000000000000000000000000000000"
+			  "00000000000000000000000000000000"
+			  "00000000000000000000000000000003",
+			  "7503cfe87a836ae3a61b8816e25450e6"
+			  "ce5e1c93acf1abc1778064fdcbefa921"
+			  "df1626be4fd036e93d75e6a50e3a41e9"
+			  "8028fe5fc235f5b889a589cb5215f2a4");
+
+      ecc->ref = ecc_alloc (3);
+      ecc_set_str (&ecc->ref[0], /* 2 g */
+		   "3b89dcfc622996ab97a5869dbff15cf51db00954f43a58a5e5f6b0470a132b2f4434bbcd405d2a9516151d2a6a04f2e4375bf48de1fdb21fb982afd9d2ea137c",
+		   "c813c4e2e2e0a8a391774c7903da7a6f14686e98e183e670ee6fb784809a3e92ca209dc631d85b1c7534ed3b37fddf64d854d7e01f91f18bb3fd307591afc051");
+
+      ecc_set_str (&ecc->ref[1], /* 3 g */
+		   "a1ff1ab2712a267eb53935ddb5a567f84db156cc096168a1174291d5f488fba543d2840b4d2dd35d764b2f57b308907aec55cfba10544e8416e134687ccb87c3",
+		   "3cb5c4417ec4637f30374f189bb5b984c41e3a48d7f84fbfa3819e3f333f7eb311d3af7e67c4c16eeacfac2fe94c6dd4c6366f711a4fb6c7125cd7ec518d90d6");
+
+      ecc_set_str (&ecc->ref[2], /* 4 g */
+		   "b7bfb80956c8670031ba191929f64e301d681634236d47a60e571a4bedc0ef257452ef78b5b98dbb3d9f3129d9349433ce2a3a35cb519c91e2d633d7b373ae16",
+		   "3bee95e29eecc5d5ad2beba941abcbf9f1cad478df0fecf614f63aeebef77850da7efdb93de8f3df80bc25eac09239c14175f5c29704ce9a3e383f1b3ec0e929");
+
+    }
   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 +1386,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..a529cf16 100644
--- a/examples/ecc-benchmark.c
+++ b/examples/ecc-benchmark.c
@@ -314,6 +314,8 @@ const struct ecc_curve * const curves[] = {
   &_nettle_secp_384r1,
   &_nettle_curve448,
   &_nettle_secp_521r1,
+  &_nettle_gost_gc256b,
+  &_nettle_gost_gc512a,
 };
 
 #define numberof(x)  (sizeof (x) / sizeof ((x)[0]))
diff --git a/examples/hogweed-benchmark.c b/examples/hogweed-benchmark.c
index 69315211..3d008021 100644
--- a/examples/hogweed-benchmark.c
+++ b/examples/hogweed-benchmark.c
@@ -48,6 +48,7 @@
 #include "dsa.h"
 #include "rsa.h"
 #include "eddsa.h"
+#include "gostdsa.h"
 #include "curve25519.h"
 #include "curve448.h"
 
@@ -591,6 +592,107 @@ bench_eddsa_clear (void *p)
   free (p);
 }
 
+static void *
+bench_gostdsa_init (unsigned size)
+{
+  struct ecdsa_ctx *ctx;
+  const struct ecc_curve *ecc;
+
+  const char *xs;
+  const char *ys;
+  const char *zs;
+  mpz_t x, y, z;
+
+  ctx = xalloc (sizeof(*ctx));
+
+  dsa_signature_init (&ctx->s);
+  knuth_lfib_init (&ctx->lfib, 17);
+
+  switch (size)
+    {
+    case 256:
+      ecc = &_nettle_gost_gc256b;
+      xs = "971566ceda436ee7678f7e07e84ebb7217406c0b4747aa8fd2ab1453c3d0dfba";
+      ys = "ad58736965949f8e59830f8de20fc6c0d177f6ab599874f1e2e24ff71f9ce643";
+      zs = "bfcf1d623e5cdd3032a7c6eabb4a923c46e43d640ffeaaf2c3ed39a8fa399924";
+      ctx->digest = hash_string (&nettle_sha256, "abc");
+      ctx->digest_size = 32;
+      break;
+
+    case 512:
+      ecc = &_nettle_gost_gc512a;
+      xs = "03A36340A95BB5F93D131961B5B1C1B3213DF7FF3B5A30376407E2A65C441BC6"
+	   "D1B34662317083243F007B15A8512B526606D3B172B606DCE86DBD6F82DA3D40";
+      ys = "DEAD76318012FED79507809C89CC44848743640EAC9A3C847DA9082E050760A1"
+	   "0679F4B707ABC1872640AD20D7441F66C7A8B3BFF1B8E11B4A076F0A86749F73";
+      zs = "3FC01CDCD4EC5F972EB482774C41E66DB7F380528DFE9E67992BA05AEE462435"
+	   "757530E641077CE587B976C8EEB48C48FD33FD175F0C7DE6A44E014E6BCB074B";
+      ctx->digest = hash_string (&nettle_sha512, "abc");
+      ctx->digest_size = 64;
+      break;
+
+    default:
+      die ("Internal error.\n");
+    }
+  ecc_point_init (&ctx->pub, ecc);
+  ecc_scalar_init (&ctx->key, ecc);
+
+  mpz_init_set_str (x, xs, 16);
+  mpz_init_set_str (y, ys, 16);
+  mpz_init_set_str (z, zs, 16);
+
+  ecc_point_set (&ctx->pub, x, y);
+  ecc_scalar_set (&ctx->key, z);
+
+  mpz_clear (x);
+  mpz_clear (y);
+  mpz_clear (z);
+
+  gostdsa_sign (&ctx->key,
+		&ctx->lfib, (nettle_random_func *) knuth_lfib_random,
+		ctx->digest_size, ctx->digest,
+		&ctx->s);
+
+  return ctx;
+}
+
+static void
+bench_gostdsa_sign (void *p)
+{
+  struct ecdsa_ctx *ctx = p;
+  struct dsa_signature s;
+
+  dsa_signature_init (&s);
+  gostdsa_sign (&ctx->key,
+		&ctx->lfib, (nettle_random_func *) knuth_lfib_random,
+		ctx->digest_size, ctx->digest,
+		&s);
+  dsa_signature_clear (&s);
+}
+
+static void
+bench_gostdsa_verify (void *p)
+{
+  struct ecdsa_ctx *ctx = p;
+  if (! gostdsa_verify (&ctx->pub,
+			ctx->digest_size, ctx->digest,
+			&ctx->s))
+    die ("Internal error, _gostdsa_verify failed.\n");
+}
+
+static void
+bench_gostdsa_clear (void *p)
+{
+  struct ecdsa_ctx *ctx = p;
+
+  ecc_point_clear (&ctx->pub);
+  ecc_scalar_clear (&ctx->key);
+  dsa_signature_clear (&ctx->s);
+  free (ctx->digest);
+
+  free (ctx);
+}
+
 #if WITH_OPENSSL
 struct openssl_rsa_ctx
 {
@@ -838,6 +940,8 @@ struct alg alg_list[] = {
   { "eddsa", 448, bench_eddsa_init, bench_eddsa_sign, bench_eddsa_verify, bench_eddsa_clear },
   { "curve", 255, bench_curve_init, bench_curve_mul_g, bench_curve_mul, bench_curve_clear},
   { "curve", 448, bench_curve_init, bench_curve_mul_g, bench_curve_mul, bench_curve_clear },
+  { "gostdsa",  256, bench_gostdsa_init, bench_gostdsa_sign, bench_gostdsa_verify, bench_gostdsa_clear },
+  { "gostdsa",  512, bench_gostdsa_init, bench_gostdsa_sign, bench_gostdsa_verify, bench_gostdsa_clear },
 };
 
 #define numberof(x)  (sizeof (x) / sizeof ((x)[0]))
diff --git a/gostdsa-sign.c b/gostdsa-sign.c
new file mode 100644
index 00000000..892c0742
--- /dev/null
+++ b/gostdsa-sign.c
@@ -0,0 +1,74 @@
+/* gostdsa-sign.c
+
+   Copyright (C) 2015 Dmitry Eremin-Solenikov
+   Copyright (C) 2013 Niels Möller
+
+   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 <stdlib.h>
+
+#include "gostdsa.h"
+#include "ecc-internal.h"
+#include "nettle-internal.h"
+
+void
+gostdsa_sign (const struct ecc_scalar *key,
+	    void *random_ctx, nettle_random_func *random,
+	    size_t digest_length,
+	    const uint8_t *digest,
+	    struct dsa_signature *signature)
+{
+  /* At most 936 bytes. */
+  TMP_DECL(k, mp_limb_t, ECC_MAX_SIZE + ECC_GOSTDSA_SIGN_ITCH (ECC_MAX_SIZE));
+  mp_limb_t size = key->ecc->p.size;
+  mp_limb_t *rp = mpz_limbs_write (signature->r, size);
+  mp_limb_t *sp = mpz_limbs_write (signature->s, size);
+
+  TMP_ALLOC (k, size + ECC_GOSTDSA_SIGN_ITCH (size));
+
+  /* Timing reveals the number of rounds through this loop, but the
+     timing is still independent of the secret k finally used. */
+  do
+    {
+      do
+        {
+          ecc_mod_random (&key->ecc->q, k, random_ctx, random, k + size);
+	}
+      while (mpn_zero_p(k, size));
+      ecc_gostdsa_sign (key->ecc, key->p, k, digest_length, digest,
+		   rp, sp, k + size);
+      mpz_limbs_finish (signature->r, size);
+      mpz_limbs_finish (signature->s, size);
+    }
+  while (mpz_sgn (signature->r) == 0 || mpz_sgn (signature->s) == 0);
+}
diff --git a/gostdsa-verify.c b/gostdsa-verify.c
new file mode 100644
index 00000000..7dc1bec1
--- /dev/null
+++ b/gostdsa-verify.c
@@ -0,0 +1,78 @@
+/* gostdsa-verify.c
+
+   Copyright (C) 2015 Dmitry Eremin-Solenikov
+   Copyright (C) 2013 Niels Möller
+
+   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 <stdlib.h>
+
+#include "gostdsa.h"
+
+#include "gmp-glue.h"
+
+int
+gostdsa_verify (const struct ecc_point *pub,
+	      size_t length, const uint8_t *digest,
+	      const struct dsa_signature *signature)
+{
+  mp_limb_t size = ecc_size (pub->ecc);
+  mp_size_t itch = 2*size + ecc_gostdsa_verify_itch (pub->ecc);
+  /* For ECC_MUL_A_WBITS == 0, at most 1512 bytes. With
+     ECC_MUL_A_WBITS == 4, currently needs 67 * ecc->size, at most
+     4824 bytes. Don't use stack allocation for this. */
+  mp_limb_t *scratch;
+  int res;
+
+#define rp scratch
+#define sp (scratch + size)
+#define scratch_out (scratch + 2*size)
+
+  if (mpz_sgn (signature->r) <= 0 || mpz_size (signature->r) > size
+      || mpz_sgn (signature->s) <= 0 || mpz_size (signature->s) > size)
+    return 0;
+
+  scratch = gmp_alloc_limbs (itch);
+
+  mpz_limbs_copy (rp, signature->r, size);
+  mpz_limbs_copy (sp, signature->s, size);
+
+  res = ecc_gostdsa_verify (pub->ecc, pub->p, length, digest, rp, sp, scratch_out);
+
+  gmp_free_limbs (scratch, itch);
+
+  return res;
+#undef rp
+#undef sp
+#undef scratch_out
+}
diff --git a/gostdsa.h b/gostdsa.h
new file mode 100644
index 00000000..c92dfd1e
--- /dev/null
+++ b/gostdsa.h
@@ -0,0 +1,100 @@
+/* gostdsa.h
+
+   Copyright (C) 2015 Dmity Eremin-Solenikov
+   Copyright (C) 2013 Niels Möller
+
+   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/.
+*/
+
+#ifndef NETTLE_GOSTDSA_H_INCLUDED
+#define NETTLE_GOSTDSA_H_INCLUDED
+
+#include "ecc.h"
+#include "dsa.h"
+#include "ecdsa.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* Name mangling */
+#define gostdsa_sign nettle_gostdsa_sign
+#define gostdsa_verify nettle_gostdsa_verify
+#define ecc_gostdsa_sign nettle_ecc_gostdsa_sign
+#define ecc_gostdsa_sign_itch nettle_ecc_gostdsa_sign_itch
+#define ecc_gostdsa_verify nettle_ecc_gostdsa_verify
+#define ecc_gostdsa_verify_itch nettle_ecc_gostdsa_verify_itch
+
+/* Just use ECDSA function for key generation */
+#define gostdsa_generate_keypair ecdsa_generate_keypair
+
+/* High level GOST DSA functions.
+ *
+ * A public key is represented as a struct ecc_point, and a private
+ * key as a struct ecc_scalar. FIXME: Introduce some aliases? */
+void
+gostdsa_sign (const struct ecc_scalar *key,
+	      void *random_ctx, nettle_random_func *random,
+	      size_t digest_length,
+	      const uint8_t *digest,
+	      struct dsa_signature *signature);
+
+int
+gostdsa_verify (const struct ecc_point *pub,
+	        size_t length, const uint8_t *digest,
+	        const struct dsa_signature *signature);
+
+/* Low-level GOSTDSA functions. */
+mp_size_t
+ecc_gostdsa_sign_itch (const struct ecc_curve *ecc);
+
+void
+ecc_gostdsa_sign (const struct ecc_curve *ecc,
+		const mp_limb_t *zp,
+		/* Random nonce, must be invertible mod ecc group
+		   order. */
+		const mp_limb_t *kp,
+		size_t length, const uint8_t *digest,
+		mp_limb_t *rp, mp_limb_t *sp,
+		mp_limb_t *scratch);
+
+mp_size_t
+ecc_gostdsa_verify_itch (const struct ecc_curve *ecc);
+
+int
+ecc_gostdsa_verify (const struct ecc_curve *ecc,
+		  const mp_limb_t *pp, /* Public key */
+		  size_t length, const uint8_t *digest,
+		  const mp_limb_t *rp, const mp_limb_t *sp,
+		  mp_limb_t *scratch);
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* NETTLE_GOSTDSA_H_INCLUDED */
diff --git a/nettle.texinfo b/nettle.texinfo
index 65b36e31..19eb6d34 100644
--- a/nettle.texinfo
+++ b/nettle.texinfo
@@ -115,6 +115,7 @@ Public-key algorithms
 
 * Side-channel silence::
 * ECDSA::
+* GOSTDSA::
 * Curve 25519 and Curve 448::
 
 @end detailmenu
@@ -1062,6 +1063,7 @@ This function also resets the context in the same way as
 
 
 @subsubsection @acronym{GOSTHASH94 and GOSTHASH94CP}
+@cindex GOST hash
 
 The GOST94 or GOST R 34.11-94 hash algorithm is a Soviet-era algorithm 
 used in Russian government standards (see @cite{RFC 4357}).
@@ -4916,6 +4918,7 @@ curve'' is used as a shorthand for the bitsize of the curve's prime
 @menu
 * Side-channel silence::
 * ECDSA::
+* GOSTDSA::
 * Curve 25519 and Curve 448::
 @end menu
 
@@ -4950,7 +4953,7 @@ accesses depend only on the size of the input data and its location in
 memory, not on the actual data bits. This implies a performance penalty
 in several of the building blocks.
 
-@node ECDSA, Curve 25519 and Curve 448, Side-channel silence, Elliptic curves
+@node ECDSA, GOSTDSA, Side-channel silence, Elliptic curves
 @comment  node-name,  next,  previous,  up
 @subsubsection ECDSA
 
@@ -5054,6 +5057,68 @@ random octets and store them at @code{dst}. For advice, see
 @xref{Randomness}.
 @end deftypefun
 
+@node GOSTDSA, Curve 25519 and Curve 448, ECDSA, Elliptic curves
+@comment  node-name,  next,  previous,  up
+@subsubsection GOSTDSA
+@cindex GOST DSA
+
+GOSTDSA (GOST R 34.10-2001, GOST R 34.10-2012) is a variant of the DSA
+(@pxref{DSA}) and ECDSA (@pxref{ECDSA}) digital signature schemes, which works
+over an elliptic curve group. Original documents are written in Russian.
+English translations are provided in @cite{RFC 5832} and @cite{RFC 7091}.
+While technically nothing stops one from using GOSTDSA over any curve, it
+is defined only over several 256 and 512-bit curves.  Like DSA and ECDSA,
+creating a signature requires a unique random nonce (repeating the nonce
+with two different messages reveals the private key, and any leak or bias
+in the generation of the nonce also leaks information about the key).
+
+GOST R 34.10-2001 was defined to use GOST R 34.11-94 hash function
+(GOSTHASH94 and GOSTHASH94CP, @cite{RFC 5831}).  GOST R 34.10-2012 is
+defined to use GOST R 34.11-2012 hash function (Streebog, @cite{RFC
+6986}) of corresponding size (256 or 512) depending on curve size.
+
+Nettle defines GOSTDSA in @file{<nettle/gostdsa.h>}. GOSTDSA reuses ECDSA
+data types (@code{struct ecc_point}, @code{struct ecc_scalar}) to
+represent public and private keys.  Also to generate a new GOSTDSA key
+pair one has to use @code{ecdsa_generate_keypair()} function.
+
+To create and verify GOSTDSA signatures, the following functions are used.
+
+@deftypefun void gostdsa_sign (const struct ecc_scalar *@var{key}, void *@var{random_ctx}, nettle_random_func *@var{random}, size_t @var{digest_length}, const uint8_t *@var{digest}, struct dsa_signature *@var{signature})
+Uses the private key @var{key} to create a signature on @var{digest}.
+@var{random_ctx} and @var{random} is a randomness generator.
+@code{random(random_ctx, length, dst)} should generate @code{length}
+random octets and store them at @code{dst}. The signature is stored in
+@var{signature}, in the same was as for plain DSA.
+@end deftypefun
+
+@deftypefun int gostdsa_verify (const struct ecc_point *@var{pub}, size_t @var{length}, const uint8_t *@var{digest}, const struct dsa_signature *@var{signature})
+Uses the public key @var{pub} to verify that @var{signature} is a valid
+signature for the message digest @var{digest} (of @var{length} octets).
+Returns 1 if the signature is valid, otherwise 0.
+@end deftypefun
+
+For historical reason several curve IDs (OIDs) may correspond to a single
+curve/generator combination. Following list defines correspondence
+between nettle's view on curves and actual identifiers defined in @cite{RFC
+4357} and @cite{RFC 7836}.
+
+@deftypefun {const struct ecc_curve} nettle_get_gost_gc256b(void)
+Returns curve corresponding to following identifiers:
+@itemize
+@item id-GostR3410-2001-CryptoPro-A-ParamSet (@cite{RFC 4357})
+@item id-GostR3410-2001-CryptoPro-XchA-ParamSet (@cite{RFC 4357})
+@item id-tc26-gost-3410-12-256-paramSetB
+@end itemize
+@end deftypefun
+
+@deftypefun {const struct ecc_curve} nettle_get_gost_gc512a(void)
+Returns curve corresponding to following identifiers:
+@itemize
+@item id-tc26-gost-3410-12-512-paramSetA (@cite{RFC 7836})
+@end itemize
+@end deftypefun
+
 @node Curve 25519 and Curve 448, , ECDSA, Elliptic curves
 @comment  node-name,  next,  previous,  up
 @subsubsection Curve25519 and Curve448
diff --git a/testsuite/.gitignore b/testsuite/.gitignore
index 1e2a69a6..be3a4870 100644
--- a/testsuite/.gitignore
+++ b/testsuite/.gitignore
@@ -43,6 +43,9 @@
 /eddsa-sign-test
 /eddsa-verify-test
 /gcm-test
+/gostdsa-keygen-test
+/gostdsa-sign-test
+/gostdsa-verify-test
 /gosthash94-test
 /hkdf-test
 /hmac-test
diff --git a/testsuite/.test-rules.make b/testsuite/.test-rules.make
index 6dbef7e2..9fd11fd6 100644
--- a/testsuite/.test-rules.make
+++ b/testsuite/.test-rules.make
@@ -289,6 +289,15 @@ ed25519-test$(EXEEXT): ed25519-test.$(OBJEXT)
 ed448-test$(EXEEXT): ed448-test.$(OBJEXT)
 	$(LINK) ed448-test.$(OBJEXT) $(TEST_OBJS) -o ed448-test$(EXEEXT)
 
+gostdsa-sign-test$(EXEEXT): gostdsa-sign-test.$(OBJEXT)
+	$(LINK) gostdsa-sign-test.$(OBJEXT) $(TEST_OBJS) -o gostdsa-sign-test$(EXEEXT)
+
+gostdsa-verify-test$(EXEEXT): gostdsa-verify-test.$(OBJEXT)
+	$(LINK) gostdsa-verify-test.$(OBJEXT) $(TEST_OBJS) -o gostdsa-verify-test$(EXEEXT)
+
+gostdsa-keygen-test$(EXEEXT): gostdsa-keygen-test.$(OBJEXT)
+	$(LINK) gostdsa-keygen-test.$(OBJEXT) $(TEST_OBJS) -o gostdsa-keygen-test$(EXEEXT)
+
 sha1-huge-test$(EXEEXT): sha1-huge-test.$(OBJEXT)
 	$(LINK) sha1-huge-test.$(OBJEXT) $(TEST_OBJS) -o sha1-huge-test$(EXEEXT)
 
diff --git a/testsuite/Makefile.in b/testsuite/Makefile.in
index dea6c28d..73a61685 100644
--- a/testsuite/Makefile.in
+++ b/testsuite/Makefile.in
@@ -53,7 +53,9 @@ TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \
 		     ecdsa-sign-test.c ecdsa-verify-test.c \
 		     ecdsa-keygen-test.c ecdh-test.c \
 		     eddsa-compress-test.c eddsa-sign-test.c \
-		     eddsa-verify-test.c ed25519-test.c ed448-test.c
+		     eddsa-verify-test.c ed25519-test.c ed448-test.c \
+		     gostdsa-sign-test.c gostdsa-verify-test.c \
+		     gostdsa-keygen-test.c
 
 TS_SOURCES = $(TS_NETTLE_SOURCES) $(TS_HOGWEED_SOURCES)
 CXX_SOURCES = cxx-test.cxx
diff --git a/testsuite/gostdsa-keygen-test.c b/testsuite/gostdsa-keygen-test.c
new file mode 100644
index 00000000..ebeabc86
--- /dev/null
+++ b/testsuite/gostdsa-keygen-test.c
@@ -0,0 +1,155 @@
+#include "testutils.h"
+#include "gostdsa.h"
+#include "knuth-lfib.h"
+
+/* Check if y^2 = x^3 - 3x + b */
+static int
+ecc_valid_p (struct ecc_point *pub)
+{
+  mpz_t t, x, y;
+  mpz_t lhs, rhs;
+  int res;
+  mp_size_t size;
+
+  size = pub->ecc->p.size;
+
+  /* First check range */
+  if (mpn_cmp (pub->p, pub->ecc->p.m, size) >= 0
+      || mpn_cmp (pub->p + size, pub->ecc->p.m, size) >= 0)
+    return 0;
+
+  mpz_init (lhs);
+  mpz_init (rhs);
+
+  mpz_roinit_n (x, pub->p, size);
+  mpz_roinit_n (y, pub->p + size, size);
+
+  mpz_mul (lhs, y, y);
+
+  if (pub->ecc->p.bit_size == 255)
+    {
+      /* Check that
+	 121666 (1 + x^2 - y^2) = 121665 x^2 y^2 */
+      mpz_t x2;
+      mpz_init (x2);
+      mpz_mul (x2, x, x); /* x^2 */
+      mpz_mul (rhs, x2, lhs); /* x^2 y^2 */
+      mpz_sub (lhs, x2, lhs); /* x^2 - y^2 */
+      mpz_add_ui (lhs, lhs, 1); /* 1 + x^2 - y^2 */
+      mpz_mul_ui (lhs, lhs, 121666);
+      mpz_mul_ui (rhs, rhs, 121665);
+
+      mpz_clear (x2);
+    }
+  else if (pub->ecc->p.bit_size == 448)
+    {
+      /* Check that
+	 x^2 + y^2 = 1 - 39081 x^2 y^2 */
+      mpz_t x2, d;
+      mpz_init (x2);
+      mpz_init_set_ui (d, 39081);
+      mpz_mul (x2, x, x); /* x^2 */
+      mpz_mul (d, d, x2); /* 39081 x^2 */
+      mpz_set_ui (rhs, 1);
+      mpz_submul (rhs, d, lhs); /* 1 - 39081 x^2 y^2 */
+      mpz_add (lhs, x2, lhs);	/* x^2 + y^2 */
+
+      mpz_clear (d);
+      mpz_clear (x2);
+    }
+  else
+    {
+      /* Check y^2 = x^3 - 3 x + b */
+      mpz_mul (rhs, x, x);
+      mpz_sub_ui (rhs, rhs, 3);
+      mpz_mul (rhs, rhs, x);
+      mpz_add (rhs, rhs, mpz_roinit_n (t, pub->ecc->b, size));
+    }
+  res = mpz_congruent_p (lhs, rhs, mpz_roinit_n (t, pub->ecc->p.m, size));
+
+  mpz_clear (lhs);
+  mpz_clear (rhs);
+
+  return res;
+}
+
+void
+test_main (void)
+{
+  unsigned i;
+  struct knuth_lfib_ctx rctx;
+  struct dsa_signature signature;
+
+  struct tstring *digest;
+
+  knuth_lfib_init (&rctx, 4711);
+  dsa_signature_init (&signature);
+
+  digest = SHEX (/* sha256("abc") */
+		 "BA7816BF 8F01CFEA 414140DE 5DAE2223"
+		 "B00361A3 96177A9C B410FF61 F20015AD");
+
+  for (i = 0; ecc_curves[i]; i++)
+    {
+      const struct ecc_curve *ecc = ecc_curves[i];
+      struct ecc_point pub;
+      struct ecc_scalar key;
+
+      if (ecc->p.bit_size == 255 || ecc->p.bit_size == 448)
+	/* Exclude curve25519 and curve448, not supported with GOSTDSA. */
+	continue;
+
+      if (verbose)
+	fprintf (stderr, "Curve %d\n", ecc->p.bit_size);
+
+      ecc_point_init (&pub, ecc);
+      ecc_scalar_init (&key, ecc);
+
+      ecdsa_generate_keypair (&pub, &key,
+			      &rctx,
+			      (nettle_random_func *) knuth_lfib_random);
+
+      if (verbose)
+	{
+	  fprintf (stderr, "Public key:\nx = ");
+	  write_mpn (stderr, 16, pub.p, ecc->p.size);
+	  fprintf (stderr, "\ny = ");
+	  write_mpn (stderr, 16, pub.p + ecc->p.size, ecc->p.size);
+	  fprintf (stderr, "\nPrivate key: ");
+	  write_mpn (stderr, 16, key.p, ecc->p.size);
+	  fprintf (stderr, "\n");
+	}
+      if (!ecc_valid_p (&pub))
+	die ("gostdsa_generate_keypair produced an invalid point.\n");
+
+      gostdsa_sign (&key,
+		   &rctx, (nettle_random_func *) knuth_lfib_random,
+		   digest->length, digest->data,
+		   &signature);
+
+      if (!gostdsa_verify (&pub, digest->length, digest->data,
+			   &signature))
+	die ("gostdsa_verify failed.\n");
+
+      digest->data[3] ^= 17;
+      if (gostdsa_verify (&pub, digest->length, digest->data,
+			  &signature))
+	die ("gostdsa_verify  returned success with invalid digest.\n");
+      digest->data[3] ^= 17;
+
+      mpz_combit (signature.r, 117);
+      if (gostdsa_verify (&pub, digest->length, digest->data,
+			  &signature))
+	die ("gostdsa_verify  returned success with invalid signature.r.\n");
+
+      mpz_combit (signature.r, 117);
+      mpz_combit (signature.s, 93);
+      if (gostdsa_verify (&pub, digest->length, digest->data,
+			  &signature))
+	die ("gostdsa_verify  returned success with invalid signature.s.\n");
+
+      ecc_point_clear (&pub);
+      ecc_scalar_clear (&key);
+    }
+  dsa_signature_clear (&signature);
+}
diff --git a/testsuite/gostdsa-sign-test.c b/testsuite/gostdsa-sign-test.c
new file mode 100644
index 00000000..0e2e0420
--- /dev/null
+++ b/testsuite/gostdsa-sign-test.c
@@ -0,0 +1,88 @@
+#include "testutils.h"
+#include "gostdsa.h"
+
+static void
+test_gostdsa (const struct ecc_curve *ecc,
+	    /* Private key */
+	    const char *sz,
+	    /* Random nonce */
+	    const char *sk,
+	    /* Hash */
+	    const struct tstring *h,
+	    /* Expected signature */
+	    const char *r, const char *s)
+{
+  struct dsa_signature ref;
+  mpz_t z;
+  mpz_t k;
+  mp_limb_t *rp = xalloc_limbs (ecc->p.size);
+  mp_limb_t *sp = xalloc_limbs (ecc->p.size);
+  mp_limb_t *scratch = xalloc_limbs (ecc_gostdsa_sign_itch (ecc));
+
+  dsa_signature_init (&ref);
+
+  mpz_init_set_str (z, sz, 16);
+  mpz_init_set_str (k, sk, 16);
+
+  ecc_gostdsa_sign (ecc, mpz_limbs_read_n (z, ecc->p.size),
+		  mpz_limbs_read_n (k, ecc->p.size),
+		  h->length, h->data, rp, sp, scratch);
+
+  mpz_set_str (ref.r, r, 16);
+  mpz_set_str (ref.s, s, 16);
+
+  if (mpz_limbs_cmp (ref.r, rp, ecc->p.size) != 0
+      || mpz_limbs_cmp (ref.s, sp, ecc->p.size) != 0)
+    {
+      fprintf (stderr, "_gostdsa_sign failed, bit_size = %u\n", ecc->p.bit_size);
+      fprintf (stderr, "r     = ");
+      write_mpn (stderr, 16, rp, ecc->p.size);
+      fprintf (stderr, "\ns     = ");
+      write_mpn (stderr, 16, sp, ecc->p.size);
+      fprintf (stderr, "\nref.r = ");
+      mpz_out_str (stderr, 16, ref.r);
+      fprintf (stderr, "\nref.s = ");
+      mpz_out_str (stderr, 16, ref.s);
+      fprintf (stderr, "\n");
+      abort();
+    }
+
+  free (rp);
+  free (sp);
+  free (scratch);
+
+  dsa_signature_clear (&ref);
+  mpz_clear (k);
+  mpz_clear (z);
+}
+
+void
+test_main (void)
+{
+  test_gostdsa (nettle_get_gost_gc256b(),
+	      "BFCF1D623E5CDD3032A7C6EABB4A923C46E43D640FFEAAF2C3ED39A8FA399924", /* z */
+
+	      "5782C53F110C596F9155D35EBD25A06A89C50391850A8FEFE33B0E270318857C", /* k */
+
+	      SHEX("1C067E20EA6CB183F22EFB0F3C6FD2A4E6A02821CB7A1B17FACD5E1F7AA76F70"), /* h */
+
+	      "E9323A5E88DD87FB7C724383BFFE7CECD4B9FFA2AC33BEEF73A5A1F743404F6B", /* r */
+
+	      "5E5B9B805B01147A8492C4A162643AC615DC777B9174108F3DC276A41F987AF3"); /* s */
+
+  test_gostdsa (nettle_get_gost_gc512a(),
+	      "3FC01CDCD4EC5F972EB482774C41E66DB7F380528DFE9E67992BA05AEE462435"
+	      "757530E641077CE587B976C8EEB48C48FD33FD175F0C7DE6A44E014E6BCB074B", /* z */
+
+	      "72ABB44536656BF1618CE10BF7EADD40582304A51EE4E2A25A0A32CB0E773ABB"
+	      "23B7D8FDD8FA5EEE91B4AE452F2272C86E1E2221215D405F51B5D5015616E1F6", /* k */
+
+	      SHEX("EDC257BED45FDDE4F1457B7F5B19017A8F204184366689D938532CDBAA5CB29A"
+		   "1D369DA57F8B983BE272219BD2C9A4FC57ECF7A77F34EE2E8AA553976A4766C0"), /* h */
+
+	      "891AA75C2A6F3B4DE27E3903F61CBB0F3F85A4E3C62F39A6E4E84A7477679C6E"
+	      "45008DC2774CA2FF64C12C0606FF918CAE3A50115440E9BF2971B627A882A1E8", /* r */
+
+	      "31065479996DDBDEE180AFE22CA3CDC44B45CE4C6C83909D1D3B702922A32441"
+	      "A9E11DCFBEA3D847C06B1A8A38EB1671D6C82FA21B79C99BE2EA809B10DAA5DF"); /* s */
+}
diff --git a/testsuite/gostdsa-verify-test.c b/testsuite/gostdsa-verify-test.c
new file mode 100644
index 00000000..7279f5f4
--- /dev/null
+++ b/testsuite/gostdsa-verify-test.c
@@ -0,0 +1,111 @@
+#include "testutils.h"
+#include "gostdsa.h"
+
+static void
+test_gostdsa (const struct ecc_curve *ecc,
+	    /* Public key */
+	    const char *xs, const char *ys,
+	    /* Hash */
+	    struct tstring *h,
+	    /* Valid signature */
+	    const char *r, const char *s)
+{
+  struct ecc_point pub;
+  struct dsa_signature signature;
+  mpz_t x, y;
+
+  ecc_point_init (&pub, ecc);
+  dsa_signature_init (&signature);
+
+  mpz_init_set_str (x, xs, 16);
+  mpz_init_set_str (y, ys, 16);
+
+  if (!ecc_point_set (&pub, x, y))
+    die ("ecc_point_set failed.\n");
+
+  mpz_set_str (signature.r, r, 16);
+  mpz_set_str (signature.s, s, 16);
+
+  if (!gostdsa_verify (&pub, h->length, h->data, &signature))
+    {
+      fprintf (stderr, "gostdsa_verify failed with valid signature.\n");
+    fail:
+      fprintf (stderr, "bit_size = %u\nx = ", ecc->p.bit_size);
+      mpz_out_str (stderr, 16, x);
+      fprintf (stderr, "\ny = ");
+      mpz_out_str (stderr, 16, y);
+      fprintf (stderr, "\ndigest ");
+      print_hex (h->length, h->data);
+      fprintf (stderr, "r = ");
+      mpz_out_str (stderr, 16, signature.r);
+      fprintf (stderr, "\ns = ");
+      mpz_out_str (stderr, 16, signature.s);
+      fprintf (stderr, "\n");
+      abort();
+    }
+
+  mpz_combit (signature.r, ecc->p.bit_size / 3);
+  if (gostdsa_verify (&pub, h->length, h->data, &signature))
+    {
+      fprintf (stderr, "gostdsa_verify unexpectedly succeeded with invalid signature.\n");
+      goto fail;
+    }
+  mpz_combit (signature.r, ecc->p.bit_size / 3);
+
+  mpz_combit (signature.s, 4*ecc->p.bit_size / 5);
+  if (gostdsa_verify (&pub, h->length, h->data, &signature))
+    {
+      fprintf (stderr, "gostdsa_verify unexpectedly succeeded with invalid signature.\n");
+      goto fail;
+    }
+  mpz_combit (signature.s, 4*ecc->p.bit_size / 5);
+
+  h->data[2*h->length / 3] ^= 0x40;
+  if (gostdsa_verify (&pub, h->length, h->data, &signature))
+    {
+      fprintf (stderr, "gostdsa_verify unexpectedly succeeded with invalid signature.\n");
+      goto fail;
+    }
+  h->data[2*h->length / 3] ^= 0x40;
+  if (!gostdsa_verify (&pub, h->length, h->data, &signature))
+    {
+      fprintf (stderr, "gostdsa_verify failed, internal testsuite error.\n");
+      goto fail;
+    }
+
+  ecc_point_clear (&pub);
+  dsa_signature_clear (&signature);
+  mpz_clear (x);
+  mpz_clear (y);
+}
+
+void
+test_main (void)
+{
+  test_gostdsa (nettle_get_gost_gc256b(),
+	      "971566CEDA436EE7678F7E07E84EBB7217406C0B4747AA8FD2AB1453C3D0DFBA", /* x */
+
+	      "AD58736965949F8E59830F8DE20FC6C0D177F6AB599874F1E2E24FF71F9CE643", /* y */
+
+	      SHEX("1C067E20EA6CB183F22EFB0F3C6FD2A4E6A02821CB7A1B17FACD5E1F7AA76F70"), /* h */
+
+	      "E9323A5E88DD87FB7C724383BFFE7CECD4B9FFA2AC33BEEF73A5A1F743404F6B", /* r */
+
+	      "5E5B9B805B01147A8492C4A162643AC615DC777B9174108F3DC276A41F987AF3"); /* s */
+
+  test_gostdsa (nettle_get_gost_gc512a(),
+	      "03A36340A95BB5F93D131961B5B1C1B3213DF7FF3B5A30376407E2A65C441BC6"
+	      "D1B34662317083243F007B15A8512B526606D3B172B606DCE86DBD6F82DA3D40", /* x */
+
+	      "DEAD76318012FED79507809C89CC44848743640EAC9A3C847DA9082E050760A1"
+	      "0679F4B707ABC1872640AD20D7441F66C7A8B3BFF1B8E11B4A076F0A86749F73", /* y */
+
+	      SHEX("EDC257BED45FDDE4F1457B7F5B19017A8F204184366689D938532CDBAA5CB29A"
+		   "1D369DA57F8B983BE272219BD2C9A4FC57ECF7A77F34EE2E8AA553976A4766C0"), /* h */
+
+	      "891AA75C2A6F3B4DE27E3903F61CBB0F3F85A4E3C62F39A6E4E84A7477679C6E"
+	      "45008DC2774CA2FF64C12C0606FF918CAE3A50115440E9BF2971B627A882A1E8", /* r */
+
+	      "31065479996DDBDEE180AFE22CA3CDC44B45CE4C6C83909D1D3B702922A32441"
+	      "A9E11DCFBEA3D847C06B1A8A38EB1671D6C82FA21B79C99BE2EA809B10DAA5DF"); /* s */
+}
diff --git a/testsuite/testutils.c b/testsuite/testutils.c
index 7772d2b0..61d52d92 100644
--- a/testsuite/testutils.c
+++ b/testsuite/testutils.c
@@ -1677,6 +1677,8 @@ const struct ecc_curve * const ecc_curves[] = {
   &_nettle_secp_521r1,
   &_nettle_curve25519,
   &_nettle_curve448,
+  &_nettle_gost_gc256b,
+  &_nettle_gost_gc512a,
   NULL
 };
 
@@ -1728,7 +1730,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[9][3] = {
     { { "dafebf5828783f2ad35534631588a3f629a70fb16982a888",
 	"dd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab" },
       { "76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da",
@@ -1796,9 +1798,29 @@ test_ecc_mul_a (unsigned curve, unsigned n, const mp_limb_t *p)
 	"e005a8dbd5125cf706cbda7ad43aa6449a4a8d952356c3b9fce43c82ec4e1d58bb3a331bdb6767f0bffa9a68fed02dafb822ac13588ed6fc" },
       { "49dcbc5c6c0cce2c1419a17226f929ea255a09cf4e0891c693fda4be70c74cc301b7bdf1515dd8ba21aee1798949e120e2ce42ac48ba7f30",
 	"d49077e4accde527164b33a5de021b979cb7c02f0457d845c90dc3227b8a5bc1c0d8f97ea1ca9472b5d444285d0d4f5b32e236f86de51839" },
+    },
+    { { "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd95",
+	"726e1b8e1f676325d820afa5bac0d489cad6b0d220dc1c4edd5336636160df83" },
+      { "8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38d2c",
+	"76bcd1ca9a23b041d4d9baf507a6cd821267a94c838768e8486117796b788a51" },
+      { "f7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e4b7",
+	"83ccf17ba6706d73625cc3534c7a2b9d6ec1ee6a9a7e07c10d84b388de59f741" },
+    },
+    { { "3b89dcfc622996ab97a5869dbff15cf51db00954f43a58a5e5f6b0470a132b2f"
+	"4434bbcd405d2a9516151d2a6a04f2e4375bf48de1fdb21fb982afd9d2ea137c",
+	"c813c4e2e2e0a8a391774c7903da7a6f14686e98e183e670ee6fb784809a3e92"
+	"ca209dc631d85b1c7534ed3b37fddf64d854d7e01f91f18bb3fd307591afc051" },
+      { "a1ff1ab2712a267eb53935ddb5a567f84db156cc096168a1174291d5f488fba5"
+	"43d2840b4d2dd35d764b2f57b308907aec55cfba10544e8416e134687ccb87c3",
+	"3cb5c4417ec4637f30374f189bb5b984c41e3a48d7f84fbfa3819e3f333f7eb3"
+	"11d3af7e67c4c16eeacfac2fe94c6dd4c6366f711a4fb6c7125cd7ec518d90d6" },
+      { "b7bfb80956c8670031ba191929f64e301d681634236d47a60e571a4bedc0ef25"
+	"7452ef78b5b98dbb3d9f3129d9349433ce2a3a35cb519c91e2d633d7b373ae16",
+	"3bee95e29eecc5d5ad2beba941abcbf9f1cad478df0fecf614f63aeebef77850"
+	"da7efdb93de8f3df80bc25eac09239c14175f5c29704ce9a3e383f1b3ec0e929" },
     }
   };
-  assert (curve < 7);
+  assert (curve < 9);
   assert (n <= 4);
   if (n == 0)
     {