Integrated ECC internals.

26 files changed, 2103 insertions, 8 deletions

diff --git a/ChangeLog b/ChangeLog
index 59208081..fc0a9395 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,35 @@
 2013-02-15  Niels Möller  <nisse@lysator.liu.se>
 
+	Integrate ECC internals.
+	* ecc-curve.h: New file.
+	* ecc-internal.h: New file.
+	* cnd-copy.c: New file.
+	* ecc-192.c: New file.
+	* ecc-224.c: New file.
+	* ecc-256.c: New file.
+	* ecc-384.c: New file.
+	* ecc-521.c: New file.
+	* ecc-generic-modp.c: New file.
+	* ecc-generic-modq.c: New file.
+	* ecc-generic-redc.c: New file.
+	* ecc-mod.c: New file.
+	* ecc-modp.c: New file.
+	* ecc-modq.c: New file.
+	* sec-add-1.c: New file.
+	* sec-modinv.c: New file.
+	* sec-sub-1.c: New file.
+	* Makefile.in (hogweed_SOURCES): Added new files.
+	(HEADERS): Added ecc-curve.h.
+	(DISTFILES): Added ecc-internal.h.
+	* testsuite/ecc-mod-test.c: New file.
+	* testsuite/ecc-modinv-test.c: New file.
+	* testsuite/ecc-redc-test.c: New file.
+	* testsuite/testutils.c (ecc_curves): New constant array.
+	* testsuite/testutils.h: Include ecc-related headers. Declare
+	ecc_curves array.
+	* testsuite/Makefile.in (TS_HOGWEED_SOURCES): Added ecc-mod-test.c
+	ecc-modinv-test.c ecc-redc-test.c.
+
 	* gmp-glue.c: New file, mpn <-> mpz conversions.
 	* gmp-glue.h: New file.
 	* Makefile.in: Added to hogweed_SOURCES and DISTFILES, respectively.
diff --git a/Makefile.in b/Makefile.in
index 7d219d50..b6c46920 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -123,21 +123,24 @@ hogweed_SOURCES = sexp.c sexp-format.c \
 		  dsa2sexp.c sexp2dsa.c \
 		  pgp-encode.c rsa2openpgp.c \
 		  der-iterator.c der2rsa.c der2dsa.c \
-		  gmp-glue.c
+		  sec-add-1.c sec-sub-1.c sec-modinv.c sec-tabselect.c \
+		  gmp-glue.c cnd-copy.c \
+		  ecc-mod.c ecc-generic-modp.c ecc-generic-modq.c \
+		  ecc-modp.c ecc-modq.c ecc-generic-redc.c \
+		  ecc-192.c ecc-224.c ecc-256.c ecc-384.c ecc-521.c
 
 HEADERS = aes.h arcfour.h arctwo.h asn1.h bignum.h blowfish.h \
 	  base16.h base64.h buffer.h camellia.h cast128.h \
-	  cbc.h ctr.h gcm.h \
-	  des.h des-compat.h dsa.h \
-	  hmac.h \
-	  pbkdf2.h \
+	  cbc.h ctr.h \
+	  des.h des-compat.h dsa.h ecc-curve.h \
+	  gcm.h gosthash94.h hmac.h \
 	  knuth-lfib.h \
 	  macros.h \
 	  md2.h md4.h \
-	  gosthash94.h \
 	  md5.h md5-compat.h \
 	  memxor.h \
 	  nettle-meta.h nettle-types.h \
+	  pbkdf2.h \
 	  pgp.h pkcs1.h realloc.h ripemd160.h rsa.h rsa-compat.h \
 	  salsa20.h sexp.h \
 	  serpent.h sha.h sha1.h sha2.h sha3.h twofish.h \
@@ -160,7 +163,7 @@ DISTFILES = $(SOURCES) $(HEADERS) getopt.h .bootstrap run-tests \
 	aes-internal.h camellia-internal.h serpent-internal.h \
 	cast128_sboxes.h desinfo.h desCode.h \
 	nettle-internal.h nettle-write.h prime-list.h \
-	gmp-glue.h \
+	gmp-glue.h ecc-internal.h \
 	asm.m4 \
 	nettle.texinfo nettle.info nettle.html nettle.pdf sha-example.c
 
diff --git a/cnd-copy.c b/cnd-copy.c
new file mode 100644
index 00000000..002e44ea
--- /dev/null
+++ b/cnd-copy.c
@@ -0,0 +1,42 @@
+/* cnd-copy.c */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "ecc-internal.h"
+
+void
+cnd_copy (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n)
+{
+  mp_limb_t mask, keep;
+  mp_size_t i;
+
+  mask = -(mp_limb_t) (cnd !=0);
+  keep = ~mask;
+
+  for (i = 0; i < n; i++)
+    rp[i] = (rp[i] & keep) + (ap[i] & mask);
+}
diff --git a/ecc-192.c b/ecc-192.c
new file mode 100644
index 00000000..e379a99b
--- /dev/null
+++ b/ecc-192.c
@@ -0,0 +1,124 @@
+/* ecc-192.c */
+
+/* Compile time constant (but machine dependent) tables. */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "ecc-internal.h"
+
+#define USE_REDC 0
+
+#include "ecc-192.h"
+
+/* Use that p = 2^{192} - 2^64 - 1, to eliminate 128 bits at a time. */
+
+#if GMP_NUMB_BITS == 32
+/* p is 6 limbs, p = B^6 - B^2 - 1 */
+static void
+ecc_192_modp (const struct ecc_curve *ecc UNUSED, mp_limb_t *rp)
+{
+  mp_limb_t cy;
+
+  /* Reduce from 12 to 9 limbs (top limb small)*/
+  cy = mpn_add_n (rp + 2, rp + 2, rp + 8, 4);
+  cy = sec_add_1 (rp + 6, rp + 6, 2, cy);
+  cy += mpn_add_n (rp + 4, rp + 4, rp + 8, 4);
+  assert (cy <= 2);
+
+  rp[8] = cy;
+
+  /* Reduce from 9 to 6 limbs */
+  cy = mpn_add_n (rp, rp, rp + 6, 3);
+  cy = sec_add_1 (rp + 3, rp + 3, 2, cy);
+  cy += mpn_add_n (rp + 2, rp + 2, rp + 6, 3);
+  cy = sec_add_1 (rp + 5, rp + 5, 1, cy);
+  
+  assert (cy <= 1);
+  cy = cnd_add_n (cy, rp, ecc_Bmodp, 3);
+  assert (cy == 0);  
+}
+#elif GMP_NUMB_BITS == 64
+/* p is 3 limbs, p = B^3 - B - 1 */
+static void
+ecc_192_modp (const struct ecc_curve *ecc UNUSED, mp_limb_t *rp)
+{
+  mp_limb_t cy;
+
+  /* Reduce from 6 to 5 limbs (top limb small)*/
+  cy = mpn_add_n (rp + 1, rp + 1, rp + 4, 2);
+  cy = sec_add_1 (rp + 3, rp + 3, 1, cy);
+  cy += mpn_add_n (rp + 2, rp + 2, rp + 4, 2);
+  assert (cy <= 2);
+
+  rp[4] = cy;
+
+  /* Reduce from 5 to 4 limbs (high limb small) */
+  cy = mpn_add_n (rp, rp, rp + 3, 2);
+  cy = sec_add_1 (rp + 2, rp + 2, 1, cy);
+  cy += mpn_add_n (rp + 1, rp + 1, rp + 3, 2);
+
+  assert (cy <= 1);
+  cy = cnd_add_n (cy, rp, ecc_Bmodp, 3);
+  assert (cy == 0);  
+}
+  
+#else
+#define ecc_192_modp ecc_generoc_modp
+#endif
+
+const struct ecc_curve nettle_secp_192r1 =
+{
+  192,
+  ECC_LIMB_SIZE,
+  ECC_BMODP_SIZE,
+  ECC_BMODQ_SIZE,
+  USE_REDC,
+  ECC_REDC_SIZE,
+  ECC_PIPPENGER_K,
+  ECC_PIPPENGER_C,
+  ecc_p,
+  ecc_b,
+  ecc_q,
+  ecc_g,
+  ecc_redc_g,
+  ecc_192_modp,
+  ecc_generic_redc,
+  ecc_192_modp,
+  ecc_generic_modq,
+  ecc_Bmodp,
+  ecc_Bmodp_shifted,
+  ecc_pp1h,
+  ecc_redc_ppm1,
+  ecc_unit,
+  ecc_Bmodq,
+  ecc_Bmodq_shifted,
+  ecc_qp1h,
+  ecc_table
+};
+
diff --git a/ecc-224.c b/ecc-224.c
new file mode 100644
index 00000000..07e30893
--- /dev/null
+++ b/ecc-224.c
@@ -0,0 +1,65 @@
+/* ecc-224.c.c */
+
+/* Compile time constant (but machine dependent) tables. */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "ecc-internal.h"
+
+#define USE_REDC (ECC_REDC_SIZE != 0)
+
+#include "ecc-224.h"
+
+const struct ecc_curve nettle_secp_224r1 =
+{
+  224,
+  ECC_LIMB_SIZE,    
+  ECC_BMODP_SIZE,
+  ECC_BMODQ_SIZE,
+  USE_REDC,
+  ECC_REDC_SIZE,
+  ECC_PIPPENGER_K,
+  ECC_PIPPENGER_C,
+  ecc_p,
+  ecc_b,
+  ecc_q,
+  ecc_g,
+  ecc_redc_g,
+  ecc_generic_modp,
+  ecc_generic_redc,
+  USE_REDC ? ecc_generic_redc : ecc_generic_modp,
+  ecc_generic_modq,
+  ecc_Bmodp,
+  ecc_Bmodp_shifted,
+  ecc_pp1h,
+  ecc_redc_ppm1,
+  ecc_unit,
+  ecc_Bmodq,
+  ecc_Bmodq_shifted,
+  ecc_qp1h,
+  ecc_table
+};
diff --git a/ecc-256.c b/ecc-256.c
new file mode 100644
index 00000000..56e356e4
--- /dev/null
+++ b/ecc-256.c
@@ -0,0 +1,228 @@
+/* ecc-256.c.c */
+
+/* Compile time constant (but machine dependent) tables. */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "ecc-internal.h"
+
+#define USE_REDC (ECC_REDC_SIZE != 0)
+
+#include "ecc-256.h"
+
+#if ECC_BMODP_SIZE < ECC_LIMB_SIZE
+#define ecc_256_modp ecc_generic_modp
+#define ecc_256_modq ecc_generic_modq
+#elif GMP_NUMB_BITS == 64
+
+static void
+ecc_256_modp (const struct ecc_curve *ecc, mp_limb_t *rp)
+{
+  mp_limb_t u1, u0;
+  mp_size_t n;
+
+  n = 2*ecc->size;
+  u1 = rp[--n];
+  u0 = rp[n-1];
+
+  /* This is not particularly fast, but should work well with assembly implementation. */
+  for (; n >= ecc->size; n--)
+    {
+      mp_limb_t q2, q1, q0, t, cy;
+
+      /* <q2, q1, q0> = v * u1 + <u1,u0>, with v = 2^32 - 1:
+
+	   +---+---+
+	   | u1| u0|
+	   +---+---+
+	       |-u1|
+	     +-+-+-+
+	     | u1|
+       +---+-+-+-+-+
+       | q2| q1| q0|
+       +---+---+---+
+      */
+      q1 = u1 - (u1 > u0);
+      q0 = u0 - u1;
+      t = u1 << 32;
+      q0 += t;
+      t = (u1 >> 32) + (q0 < t) + 1;
+      q1 += t;
+      q2 = q1 < t;
+
+      /* Compute candidate remainder */
+      u1 = u0 + (q1 << 32) - q1;
+      t = -(mp_limb_t) (u1 > q0);
+      u1 -= t & 0xffffffff;
+      q1 += t;
+      q2 += t + (q1 < t);
+
+      assert (q2 < 2);
+
+      /* We multiply by two low limbs of p, 2^96 - 1, so we could use
+	 shifts rather than mul. */
+      t = mpn_submul_1 (rp + n - 4, ecc->p, 2, q1);
+      t += cnd_sub_n (q2, rp + n - 3, ecc->p, 1);
+      t += (-q2) & 0xffffffff;
+
+      u0 = rp[n-2];
+      cy = (u0 < t);
+      u0 -= t;
+      t = (u1 < cy);
+      u1 -= cy;
+      u1 += cnd_add_n (t, rp + n - 4, ecc->p, 3);
+      u1 -= (-t) & 0xffffffff;
+    }
+  rp[2] = u0;
+  rp[3] = u1;
+}
+
+static void
+ecc_256_modq (const struct ecc_curve *ecc, mp_limb_t *rp)
+{
+  mp_limb_t u2, u1, u0;
+  mp_size_t n;
+
+  n = 2*ecc->size;
+  u2 = rp[--n];
+  u1 = rp[n-1];
+
+  /* This is not particularly fast, but should work well with assembly implementation. */
+  for (; n >= ecc->size; n--)
+    {
+      mp_limb_t q2, q1, q0, t, c1, c0;
+
+      u0 = rp[n-2];
+      
+      /* <q2, q1, q0> = v * u2 + <u2,u1>, same method as above.
+
+	   +---+---+
+	   | u2| u1|
+	   +---+---+
+	       |-u2|
+	     +-+-+-+
+	     | u2|
+       +---+-+-+-+-+
+       | q2| q1| q0|
+       +---+---+---+
+      */
+      q1 = u2 - (u2 > u1);
+      q0 = u1 - u2;
+      t = u2 << 32;
+      q0 += t;
+      t = (u2 >> 32) + (q0 < t) + 1;
+      q1 += t;
+      q2 = q1 < t;
+
+      /* Compute candidate remainder, <u1, u0> - <q2, q1> * (2^128 - 2^96 + 2^64 - 1)
+         <u1, u0> + 2^64 q2 + (2^96 - 2^64 + 1) q1 (mod 2^128)
+
+	   +---+---+
+	   | u1| u0|
+	   +---+---+
+	   | q2| q1|
+	   +---+---+
+	   |-q1|
+	 +-+-+-+
+	 | q1|
+       --+-+-+-+---+
+           | u2| u1|
+	   +---+---+
+      */	 
+      u2 = u1 + q2 - q1;
+      u1 = u0 + q1;
+      u2 += (u1 < q1);
+      u2 += (q1 << 32);
+
+      t = -(mp_limb_t) (u2 >= q0);
+      q1 += t;
+      q2 += t + (q1 < t);
+      u1 += t;
+      u2 += (t << 32) + (u1 < t);
+
+      assert (q2 < 2);
+
+      c0 = cnd_sub_n (q2, rp + n - 3, ecc->q, 1);
+      c0 += (-q2) & ecc->q[1];
+      t = mpn_submul_1 (rp + n - 4, ecc->q, 2, q1);
+      c0 += t;
+      c1 = c0 < t;
+      
+      /* Construct underflow condition. */
+      c1 += (u1 < c0);
+      t = - (mp_limb_t) (u2 < c1);
+
+      u1 -= c0;
+      u2 -= c1;
+
+      /* Conditional add of p */
+      u1 += t;
+      u2 += (t<<32) + (u0 < t);
+
+      t = cnd_add_n (t, rp + n - 4, ecc->q, 2);
+      u1 += t;
+      u2 += (u1 < t);
+    }
+  rp[2] = u1;
+  rp[3] = u2;
+}
+      
+#else
+#error Unsupported parameters
+#endif
+
+const struct ecc_curve nettle_secp_256r1 =
+{
+  256,
+  ECC_LIMB_SIZE,    
+  ECC_BMODP_SIZE,
+  ECC_BMODQ_SIZE,
+  USE_REDC,
+  ECC_REDC_SIZE,
+  ECC_PIPPENGER_K,
+  ECC_PIPPENGER_C,
+  ecc_p,
+  ecc_b,
+  ecc_q,
+  ecc_g,
+  ecc_redc_g,
+  ecc_256_modp,
+  ecc_generic_redc,
+  USE_REDC ? ecc_generic_redc : ecc_generic_modp,
+  ecc_256_modq,
+  ecc_Bmodp,
+  ecc_Bmodp_shifted,
+  ecc_pp1h,
+  ecc_redc_ppm1,
+  ecc_unit,
+  ecc_Bmodq,
+  ecc_Bmodq_shifted,
+  ecc_qp1h,
+  ecc_table
+};
diff --git a/ecc-384.c b/ecc-384.c
new file mode 100644
index 00000000..3c49e0ec
--- /dev/null
+++ b/ecc-384.c
@@ -0,0 +1,163 @@
+/* ecc-384.c.c */
+
+/* Compile time constant (but machine dependent) tables. */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "ecc-internal.h"
+
+#define USE_REDC 0
+
+#include "ecc-384.h"
+
+/* Use that 2^{384} = 2^{128} + 2^{96} - 2^{32} + 1, and eliminate 256
+   bits at a time.
+
+   We can get carry == 2 in the first iteration, and I think *only* in
+   the first iteration. */
+
+#if GMP_NUMB_BITS == 32
+/* p is 12 limbs, and B^12 - p = B^4 + B^3 - B + 1. We can eliminate
+   almost 8 at a time. Do only 7, to avoid additional carry
+   propagation, followed by 5. */
+static void
+ecc_384_modp (const struct ecc_curve *ecc, mp_limb_t *rp)
+{
+  mp_limb_t cy, bw;
+
+  /* Reduce from 24 to 17 limbs. */
+  cy = mpn_add_n (rp + 4, rp + 4, rp + 16, 8);
+  cy = sec_add_1 (rp + 12, rp + 12, 3, cy);
+
+  bw = mpn_sub_n (rp + 5, rp + 5, rp + 16, 8);
+  bw = sub_1_sec (rp + 13, rp + 13, 3, bw);
+
+  cy += mpn_add_n (rp + 7, rp + 7, rp + 16, 8);
+  cy = sec_add_1 (rp + 15, rp + 15, 1, cy);
+
+  cy += mpn_add_n (rp + 8, rp + 8, rp + 16, 8);
+  assert (bw <= cy);
+  cy -= bw;
+
+  assert (cy <= 2);  
+  rp[16] = cy;
+
+  /* Reduce from 17 to 12 limbs */
+  cy = mpn_add_n (rp, rp, rp + 12, 5);
+  cy = sec_add_1 (rp + 5, rp + 5, 3, cy);
+  
+  bw = mpn_sub_n (rp + 1, rp + 1, rp + 12, 5);
+  bw = sub_1_sec (rp + 6, rp + 6, 6, bw);
+  
+  cy += mpn_add_n (rp + 3, rp + 3, rp + 12, 5);
+  cy = sec_add_1 (rp + 8, rp + 8, 1, cy);
+
+  cy += mpn_add_n (rp + 4, rp + 4, rp + 12, 5);
+  cy = sec_add_1 (rp + 9, rp + 9, 3, cy);
+
+  assert (cy >= bw);
+  cy -= bw;
+  assert (cy <= 1);
+  cy = cnd_add_n (cy, rp, ecc->Bmodp, ECC_LIMB_SIZE);
+  assert (cy == 0);
+}
+#elif GMP_NUMB_BITS == 64
+/* p is 6 limbs, and B^6 - p = B^2 + 2^32 (B - 1) + 1. Eliminate 3
+   (almost 4) limbs at a time. */
+static void
+ecc_384_modp (const struct ecc_curve *ecc, mp_limb_t *rp)
+{
+  mp_limb_t tp[6];
+  mp_limb_t cy;
+
+  /* Reduce from 12 to 9 limbs */
+  tp[0] = 0; /* FIXME: Could use mpn_sub_nc */
+  mpn_copyi (tp + 1, rp + 8, 3);
+  tp[4] = rp[11] - mpn_sub_n (tp, tp, rp + 8, 4);
+  tp[5] = mpn_lshift (tp, tp, 5, 32);
+
+  cy = mpn_add_n (rp + 2, rp + 2, rp + 8, 4);
+  cy = sec_add_1 (rp + 6, rp + 6, 2, cy);
+
+  cy += mpn_add_n (rp + 2, rp + 2, tp, 6);
+  cy += mpn_add_n (rp + 4, rp + 4, rp + 8, 4);
+
+  assert (cy <= 2);
+  rp[8] = cy;
+
+  /* Reduce from 9 to 6 limbs */
+  tp[0] = 0;
+  mpn_copyi (tp + 1, rp + 6, 2);
+  tp[3] = rp[8] -= mpn_sub_n (tp, tp, rp + 6, 3);
+  tp[4] = mpn_lshift (tp, tp, 4, 32);
+
+  cy = mpn_add_n (rp, rp, rp + 6, 3);
+  cy = sec_add_1 (rp + 3, rp + 3, 2, cy);
+  cy += mpn_add_n (rp, rp, tp, 5);
+  cy += mpn_add_n (rp + 2, rp + 2, rp + 6, 3);
+
+  cy = sec_add_1 (rp + 5, rp + 5, 1, cy);
+  assert (cy <= 1);
+
+  cy = cnd_add_n (cy, rp, ecc->Bmodp, ECC_LIMB_SIZE);
+  assert (cy == 0);  
+}
+#else
+#define ecc_384_modp ecc_generic_modp
+#endif
+  
+const struct ecc_curve nettle_secp_384r1 =
+{
+  384,
+  ECC_LIMB_SIZE,    
+  ECC_BMODP_SIZE,
+  ECC_BMODQ_SIZE,
+  USE_REDC,
+  ECC_REDC_SIZE,
+  ECC_PIPPENGER_K,
+  ECC_PIPPENGER_C,
+  ecc_p,
+  ecc_b,
+  ecc_q,
+  ecc_g,
+  ecc_redc_g,
+  ecc_384_modp,
+  ECC_REDC_SIZE != 0 ? ecc_generic_redc : NULL,
+  ecc_384_modp,
+  ecc_generic_modq,
+  ecc_Bmodp,
+  ecc_Bmodp_shifted,
+  ecc_pp1h,
+  ecc_redc_ppm1,
+  ecc_unit,
+  ecc_Bmodq,
+  ecc_Bmodq_shifted,
+  ecc_qp1h,
+  ecc_table
+};
diff --git a/ecc-521.c b/ecc-521.c
new file mode 100644
index 00000000..ec3f7ceb
--- /dev/null
+++ b/ecc-521.c
@@ -0,0 +1,89 @@
+/* ecc-521.c.c */
+
+/* Compile time constant (but machine dependent) tables. */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "ecc-internal.h"
+
+#define USE_REDC 0
+
+#include "ecc-521.h"
+
+#define B_SHIFT (521 % GMP_NUMB_BITS)
+#define BMODP_SHIFT (GMP_NUMB_BITS - B_SHIFT)
+#define BMODP ((mp_limb_t) 1 << BMODP_SHIFT)
+
+/* Result may be *slightly* larger than 2^521 */
+static void
+ecc_521_modp (const struct ecc_curve *ecc UNUSED, mp_limb_t *rp)
+{
+  /* FIXME: Should use mpn_addlsh_n_ip1 */
+  mp_limb_t hi;
+  /* Reduce from 2*ECC_LIMB_SIZE to ECC_LIMB_SIZE + 1 */
+  rp[ECC_LIMB_SIZE]
+    = mpn_addmul_1 (rp, rp + ECC_LIMB_SIZE, ECC_LIMB_SIZE, BMODP);
+  hi = mpn_addmul_1 (rp, rp + ECC_LIMB_SIZE, 1, BMODP);
+  hi = sec_add_1 (rp + 1, rp + 1, ECC_LIMB_SIZE - 1, hi);
+
+  /* Combine hi with top bits, and add in. */
+  hi = (hi << BMODP_SHIFT) | (rp[ECC_LIMB_SIZE-1] >> B_SHIFT);
+  rp[ECC_LIMB_SIZE-1] = (rp[ECC_LIMB_SIZE-1]
+			 & (((mp_limb_t) 1 << B_SHIFT)-1))
+    + sec_add_1 (rp, rp, ECC_LIMB_SIZE - 1, hi);
+}
+
+const struct ecc_curve nettle_secp_521r1 =
+{
+  521,
+  ECC_LIMB_SIZE,    
+  ECC_BMODP_SIZE,
+  ECC_BMODQ_SIZE,
+  USE_REDC,
+  ECC_REDC_SIZE,
+  ECC_PIPPENGER_K,
+  ECC_PIPPENGER_C,
+  ecc_p,
+  ecc_b,
+  ecc_q,
+  ecc_g,
+  ecc_redc_g,
+  ecc_521_modp,
+  ecc_generic_redc,
+  ecc_521_modp,
+  ecc_generic_modq,
+  ecc_Bmodp,
+  ecc_Bmodp_shifted,
+  ecc_pp1h,
+  ecc_redc_ppm1,
+  ecc_unit,
+  ecc_Bmodq,
+  ecc_Bmodq_shifted,
+  ecc_qp1h,
+  ecc_table
+};
+
diff --git a/ecc-curve.h b/ecc-curve.h
new file mode 100644
index 00000000..e6f8aa67
--- /dev/null
+++ b/ecc-curve.h
@@ -0,0 +1,45 @@
+/* ecc-curve.h */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#ifndef NETTLE_ECC_CURVE_H_INCLUDED
+#define NETTLE_ECC_CURVE_H_INCLUDED
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* The contets of this struct is internal. */
+struct ecc_curve;
+
+extern const struct ecc_curve nettle_secp_192r1;
+extern const struct ecc_curve nettle_secp_224r1;
+extern const struct ecc_curve nettle_secp_256r1;
+extern const struct ecc_curve nettle_secp_384r1;
+extern const struct ecc_curve nettle_secp_521r1;
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* NETTLE_ECC_CURVE_H_INCLUDED */
diff --git a/ecc-generic-modp.c b/ecc-generic-modp.c
new file mode 100644
index 00000000..dd557553
--- /dev/null
+++ b/ecc-generic-modp.c
@@ -0,0 +1,41 @@
+/* ecc-generic-modp.c */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "ecc-internal.h"
+
+void
+ecc_generic_modp (const struct ecc_curve *ecc, mp_limb_t *rp)
+{
+  assert (ecc->Bmodp_size < ecc->size);
+  
+  ecc_mod (rp, 2*ecc->size, ecc->size, ecc->Bmodp, ecc->Bmodp_size,
+	   ecc->Bmodp_shifted,
+	   ecc->size * GMP_NUMB_BITS - ecc->bit_size);
+}
diff --git a/ecc-generic-modq.c b/ecc-generic-modq.c
new file mode 100644
index 00000000..3fd3879f
--- /dev/null
+++ b/ecc-generic-modq.c
@@ -0,0 +1,41 @@
+/* ecc-generic-modq.c */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "ecc-internal.h"
+
+void
+ecc_generic_modq (const struct ecc_curve *ecc, mp_limb_t *rp)
+{
+  assert (ecc->Bmodq_size < ecc->size);
+
+  ecc_mod (rp, 2*ecc->size, ecc->size, ecc->Bmodq, ecc->Bmodq_size,
+	   ecc->Bmodq_shifted,
+	   ecc->size * GMP_NUMB_BITS - ecc->bit_size);
+}
diff --git a/ecc-generic-redc.c b/ecc-generic-redc.c
new file mode 100644
index 00000000..1b120b5e
--- /dev/null
+++ b/ecc-generic-redc.c
@@ -0,0 +1,85 @@
+/* ecc-generic-redc.c */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "ecc-internal.h"
+
+void
+ecc_generic_redc (const struct ecc_curve *ecc, mp_limb_t *rp)
+{
+  unsigned i;
+  mp_limb_t hi, cy;
+  unsigned shift = ecc->size * GMP_NUMB_BITS - ecc->bit_size;
+  mp_size_t k = ecc->redc_size;
+  
+  assert (k != 0);
+  if (k > 0)    
+    {
+      /* Use that 1 = p + 1, and that at least one low limb of p + 1 is zero. */
+      for (i = 0; i < ecc->size; i++)
+	rp[i] = mpn_addmul_1 (rp + i + k,
+			      ecc->redc_ppm1, ecc->size - k, rp[i]);
+      hi = mpn_add_n (rp, rp, rp + ecc->size, ecc->size);
+      if (shift > 0)
+	{
+	  hi = (hi << shift) | (rp[ecc->size - 1] >> (GMP_NUMB_BITS - shift));
+	  rp[ecc->size - 1] = (rp[ecc->size - 1]
+			       & (((mp_limb_t) 1 << (GMP_NUMB_BITS - shift)) - 1))
+	    + mpn_addmul_1 (rp, ecc->Bmodp_shifted, ecc->size-1, hi);
+	  
+	}
+      else
+	{
+	  cy = cnd_sub_n (hi, rp, ecc->p, ecc->size);
+	  assert (cy == hi);      
+	}
+    }
+  else
+    {
+      /* Use that 1 = - (p - 1), and that at least one low limb of p -
+	 1 is zero. */
+      k = -k;
+      for (i = 0; i < ecc->size; i++)
+	rp[i] = mpn_submul_1 (rp + i + k,
+			      ecc->redc_ppm1, ecc->size - k, rp[i]);
+      hi = mpn_sub_n (rp, rp + ecc->size, rp, ecc->size);
+      cy = cnd_add_n (hi, rp, ecc->p, ecc->size);
+      assert (cy == hi);
+
+      if (shift > 0)
+	{
+	  /* Result is always < 2p, provided that
+	     2^shift * Bmodp_shifted <= p */
+	  hi = (rp[ecc->size - 1] >> (GMP_NUMB_BITS - shift));
+	  rp[ecc->size - 1] = (rp[ecc->size - 1]
+			       & (((mp_limb_t) 1 << (GMP_NUMB_BITS - shift)) - 1))
+	    + mpn_addmul_1 (rp, ecc->Bmodp_shifted, ecc->size-1, hi);
+	}
+    }
+}
diff --git a/ecc-internal.h b/ecc-internal.h
new file mode 100644
index 00000000..a6b3fae4
--- /dev/null
+++ b/ecc-internal.h
@@ -0,0 +1,235 @@
+/* ecc-internal.h */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#ifndef NETTLE_ECC_INTERNAL_H_INCLUDED
+#define NETTLE_ECC_INTERNAL_H_INCLUDED
+
+#include <gmp.h>
+
+#include "ecc-curve.h"
+
+/* Name mangling */
+#define ecc_generic_modp _nettle_ecc_generic_modp
+#define ecc_generic_redc _nettle_ecc_generic_redc
+#define ecc_generic_modq _nettle_ecc_generic_modq
+#define ecc_modp_add _nettle_ecc_modp_add
+#define ecc_modp_sub _nettle_ecc_modp_sub
+#define ecc_modp_sub_1 _nettle_ecc_modp_sub_1
+#define ecc_modp_mul_1 _nettle_ecc_modp_mul_1
+#define ecc_modp_addmul_1 _nettle_ecc_modp_addmul_1
+#define ecc_modp_submul_1 _nettle_ecc_modp_submul_1
+#define ecc_modp_mul _nettle_ecc_modp_mul
+#define ecc_modp_sqr _nettle_ecc_modp_sqr
+#define ecc_modp_inv _nettle_ecc_modp_inv
+#define ecc_modq_mul _nettle_ecc_modq_mul
+#define ecc_modq_add _nettle_ecc_modq_add
+#define ecc_modq_inv _nettle_ecc_modq_inv
+#define ecc_mod _nettle_ecc_mod 
+#define cnd_copy _nettle_cnd_copy
+#define sec_add_1 _nettle_sec_add_1
+#define sec_sub_1 _nettle_sec_sub_1
+#define sec_tabselect _nettle_sec_tabselect
+#define sec_modinv _nettle_sec_modinv
+
+/* Window size for ecc_mul_a. Using 4 bits seems like a good choice,
+   for both Intel x86_64 and ARM Cortex A9. For the larger curves, of
+   384 and 521 bits, we could improve seepd by a few percent if we go
+   up to 5 bits, but I don't think that's worth doubling the
+   storage. */
+#define ECC_MUL_A_WBITS 4
+
+/* Reduces from 2*ecc->size to ecc->size. */
+/* Required to return a result < 2q. This property is inherited by
+   modp_mul and modp_add. */
+typedef void ecc_mod_func (const struct ecc_curve *ecc, mp_limb_t *rp);
+
+/* Represents an elliptic curve of the form
+
+     y^2 = x^3 - 3x + b (mod p)
+*/
+struct ecc_curve
+{
+  unsigned short bit_size;
+  /* Limb size of elements in the base field, size of a point is
+     2*size in affine coordinates and 3*size in jacobian
+     coordinates. */
+  unsigned short size;
+  unsigned short Bmodp_size;
+  unsigned short Bmodq_size;
+  unsigned short use_redc;
+  /* +k if p+1 has k low zero limbs, -k if p-1 has k low zero
+     limbs. */
+  short redc_size;
+  unsigned short pippenger_k;
+  unsigned short pippenger_c;
+
+  /* The prime p. */
+  const mp_limb_t *p;
+  const mp_limb_t *b;
+  /* Group order. */
+  const mp_limb_t *q;
+  /* Generator, x coordinate followed by y (affine coordinates). */
+  const mp_limb_t *g;
+  /* Generator with coordinates in Montgomery form. */
+  const mp_limb_t *redc_g;
+
+  ecc_mod_func *modp;
+  ecc_mod_func *redc;
+  ecc_mod_func *reduce;
+  ecc_mod_func *modq;
+
+  /* B^size mod p. Expected to have at least 32 leading zeros
+     (equality for secp_256r1). */
+  const mp_limb_t *Bmodp;
+  /* 2^{bit_size} - p, same value as above, but shifted. */
+  const mp_limb_t *Bmodp_shifted;
+  /* (p+1)/2 */
+  const mp_limb_t *pp1h;
+  /* p +/- 1, for redc, excluding |redc_size| low limbs. */
+  const mp_limb_t *redc_ppm1;
+  /* For redc, same as Bmodp, otherwise 1. */
+  const mp_limb_t *unit;
+
+  /* Similarly, B^size mod q */
+  const mp_limb_t *Bmodq;
+  /* 2^{bit_size} - q, same value as above, but shifted. */
+  const mp_limb_t *Bmodq_shifted;
+  /* (q+1)/2 */
+  const mp_limb_t *qp1h;
+  
+  /* Tables for multiplying by the generator, size determined by k and
+     c. The first 2^c entries are defined by
+
+       T[  j_0 +   j_1 2 +     ... + j_{c-1} 2^{c-1} ]
+         = j_0 g + j_1 2^k g + ... + j_{c-1} 2^{k(c-1)} g
+
+     The following entries differ by powers of 2^{kc},
+
+       T[i] = 2^{kc} T[i-2^c]
+  */  
+  const mp_limb_t *pippenger_table;
+};
+
+/* In-place reduction. */
+ecc_mod_func ecc_generic_modp;
+ecc_mod_func ecc_generic_redc;
+ecc_mod_func ecc_generic_modq;
+
+
+void
+ecc_modp_add (const struct ecc_curve *ecc, mp_limb_t *rp,
+	      const mp_limb_t *ap, const mp_limb_t *bp);
+void
+ecc_modp_sub (const struct ecc_curve *ecc, mp_limb_t *rp,
+	      const mp_limb_t *ap, const mp_limb_t *bp);
+
+void
+ecc_modp_sub_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
+		const mp_limb_t *ap, mp_limb_t b);
+
+void
+ecc_modp_mul_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
+		const mp_limb_t *ap, const mp_limb_t b);
+
+void
+ecc_modp_addmul_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
+		   const mp_limb_t *ap, mp_limb_t b);
+void
+ecc_modp_submul_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
+		   const mp_limb_t *ap, mp_limb_t b);
+
+/* NOTE: mul and sqr needs 2*ecc->size limbs at rp */
+void
+ecc_modp_mul (const struct ecc_curve *ecc, mp_limb_t *rp,
+	      const mp_limb_t *ap, const mp_limb_t *bp);
+
+void
+ecc_modp_sqr (const struct ecc_curve *ecc, mp_limb_t *rp,
+	      const mp_limb_t *ap);
+
+void
+ecc_modp_inv (const struct ecc_curve *ecc, mp_limb_t *rp, mp_limb_t *ap,
+	      mp_limb_t *scratch);
+
+/* mod q operations. */
+void
+ecc_modq_mul (const struct ecc_curve *ecc, mp_limb_t *rp,
+	      const mp_limb_t *ap, const mp_limb_t *bp);
+void
+ecc_modq_add (const struct ecc_curve *ecc, mp_limb_t *rp,
+	      const mp_limb_t *ap, const mp_limb_t *bp);
+
+void
+ecc_modq_inv (const struct ecc_curve *ecc, mp_limb_t *rp, mp_limb_t *ap,
+	      mp_limb_t *scratch);
+
+void
+ecc_mod (mp_limb_t *rp, mp_size_t rn, mp_size_t mn,
+	 const mp_limb_t *bp, mp_size_t bn,
+	 const mp_limb_t *b_shifted, unsigned shift);
+
+#define cnd_add_n(cnd, rp, ap, n)		\
+  mpn_addmul_1 ((rp), (ap), (n), (cnd) != 0)
+
+#define cnd_sub_n(cnd, rp, ap, n)		\
+  mpn_submul_1 ((rp), (ap), (n), (cnd) != 0)
+
+void
+cnd_copy (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n);
+
+mp_limb_t
+sec_add_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b);
+
+mp_limb_t
+sec_sub_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b);
+
+void
+sec_tabselect (mp_limb_t *rp, mp_size_t rn,
+	       const mp_limb_t *table, unsigned tn,
+	       unsigned k);
+
+void
+sec_modinv (mp_limb_t *vp, mp_limb_t *ap, mp_size_t n,
+	    const mp_limb_t *mp, const mp_limb_t *mp1h, mp_size_t bit_size,
+	    mp_limb_t *scratch);
+
+/* Current scratch needs: */
+#define ECC_MODINV_ITCH(size) (3*(size))
+#define ECC_J_TO_A_ITCH(size) (5*(size))
+#define ECC_DUP_JA_ITCH(size) (5*(size))
+#define ECC_DUP_JJ_ITCH(size) (5*(size))
+#define ECC_ADD_JJA_ITCH(size) (6*(size))
+#define ECC_ADD_JJJ_ITCH(size) (8*(size))
+#define ECC_MUL_G_ITCH(size) (9*(size))
+#if ECC_MUL_A_WBITS == 0
+#define ECC_MUL_A_ITCH(size) (12*(size))
+#else
+#define ECC_MUL_A_ITCH(size) \
+  (((3 << ECC_MUL_A_WBITS) + 11) * (size))
+#endif
+#define _ECDSA_SIGN_ITCH(size) (12*(size))
+#define _ECDSA_VERIFY_ITCH(size) \
+  (6*(size) + ECC_MUL_A_ITCH ((size)))
+
+#endif /* NETTLE_ECC_INTERNAL_H_INCLUDED */
diff --git a/ecc-mod.c b/ecc-mod.c
new file mode 100644
index 00000000..1d2f4232
--- /dev/null
+++ b/ecc-mod.c
@@ -0,0 +1,102 @@
+/* ecc-mod.c */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "ecc-internal.h"
+
+/* Computes r mod m, where m is of size mn. bp holds B^mn mod m, as mn
+   limbs, but the upper mn - bn libms are zero. */
+void
+ecc_mod (mp_limb_t *rp, mp_size_t rn, mp_size_t mn,
+	 const mp_limb_t *bp, mp_size_t bn,
+	 const mp_limb_t *b_shifted, unsigned shift)
+{
+  mp_limb_t hi;
+  mp_size_t sn = mn - bn;
+  mp_size_t i;
+
+  assert (sn > 0);
+
+  /* FIXME: Could use mpn_addmul_2. */
+  /* Eliminate sn = mn - bn limbs at a time */
+  if (bp[bn-1] < ((mp_limb_t) 1 << (GMP_NUMB_BITS - 1)))
+    {
+      /* Multiply sn + 1 limbs at a time, so we get a mn+1 limb
+	 product. Then we can absorb the carry in the high limb */
+      while (rn > 2 * mn - bn)
+	{
+	  rn -= sn;
+
+	  for (i = 0; i <= sn; i++)
+	    rp[rn+i-1] = mpn_addmul_1 (rp + rn - mn - 1 + i, bp, bn, rp[rn+i-1]);
+	  rp[rn-1] = rp[rn+sn-1]
+	    + mpn_add_n (rp + rn - sn - 1, rp + rn - sn - 1, rp + rn - 1, sn);
+	}
+      goto final_limbs;
+    }
+  else
+    {
+      while (rn >= 2 * mn - bn)
+	{
+	  rn -= sn;
+
+	  for (i = 0; i < sn; i++)
+	    rp[rn+i] = mpn_addmul_1 (rp + rn - mn + i, bp, bn, rp[rn+i]);
+				     
+	  hi = mpn_add_n (rp + rn - sn, rp + rn - sn, rp + rn, sn);
+	  hi = cnd_add_n (hi, rp + rn - mn, bp, mn);
+	  assert (hi == 0);
+	}
+    }
+
+  if (rn > mn)
+    {
+    final_limbs:
+      sn = rn - mn;
+      
+      for (i = 0; i < sn; i++)
+	rp[mn+i] = mpn_addmul_1 (rp + i, bp, bn, rp[mn+i]);
+
+      hi = mpn_add_n (rp + bn, rp + bn, rp + mn, sn);
+      hi = sec_add_1 (rp + bn + sn, rp + bn + sn, mn - bn - sn, hi);
+    }
+
+  if (shift > 0)
+    {
+      /* Combine hi with top bits, add in */
+      hi = (hi << shift) | (rp[mn-1] >> (GMP_NUMB_BITS - shift));
+      rp[mn-1] = (rp[mn-1] & (((mp_limb_t) 1 << (GMP_NUMB_BITS - shift)) - 1))
+	+ mpn_addmul_1 (rp, b_shifted, mn-1, hi);
+    }
+  else
+    {
+      hi = cnd_add_n (hi, rp, bp, mn);
+      assert (hi == 0);
+    }
+}
diff --git a/ecc-modp.c b/ecc-modp.c
new file mode 100644
index 00000000..ce7de7c8
--- /dev/null
+++ b/ecc-modp.c
@@ -0,0 +1,142 @@
+/* ecc-modp.c */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "ecc-internal.h"
+
+/* Routines for modp arithmetic. All values are ecc->size limbs, but
+   not necessarily < p. */
+
+void
+ecc_modp_add (const struct ecc_curve *ecc, mp_limb_t *rp,
+	      const mp_limb_t *ap, const mp_limb_t *bp)
+{
+  mp_limb_t cy;
+  cy = mpn_add_n (rp, ap, bp, ecc->size);
+  cy = cnd_add_n (cy, rp, ecc->Bmodp, ecc->size);
+  cy = cnd_add_n (cy, rp, ecc->Bmodp, ecc->size);
+  assert (cy == 0);  
+}
+
+void
+ecc_modp_sub (const struct ecc_curve *ecc, mp_limb_t *rp,
+	      const mp_limb_t *ap, const mp_limb_t *bp)
+{
+  mp_limb_t cy;
+  cy = mpn_sub_n (rp, ap, bp, ecc->size);
+  cy = cnd_sub_n (cy, rp, ecc->Bmodp, ecc->size);
+  cy = cnd_sub_n (cy, rp, ecc->Bmodp, ecc->size);
+  assert (cy == 0);  
+}
+
+void
+ecc_modp_sub_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
+		const mp_limb_t *ap, mp_limb_t b)
+{
+  mp_size_t i;
+
+  for (i = 0; i < ecc->size; i++)
+    {
+      mp_limb_t cy = ap[i] < b;
+      rp[i] = ap[i] - b;
+      b = cy;
+    }
+  b = cnd_sub_n (b, rp, ecc->Bmodp, ecc->size);
+  assert (b == 0);    
+}
+
+void
+ecc_modp_mul_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
+		const mp_limb_t *ap, mp_limb_t b)
+{
+  mp_limb_t hi;
+
+  assert (b <= 0xffffffff);
+  hi = mpn_mul_1 (rp, ap, ecc->size, b);
+  hi = mpn_addmul_1 (rp, ecc->Bmodp, ecc->size, hi);
+  assert (hi <= 1);
+  hi = cnd_add_n (hi, rp, ecc->Bmodp, ecc->size);
+  /* Sufficient if b < B^size / p */
+  assert (hi == 0);
+}
+
+void
+ecc_modp_addmul_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
+		   const mp_limb_t *ap, mp_limb_t b)
+{
+  mp_limb_t hi;
+
+  assert (b <= 0xffffffff);
+  hi = mpn_addmul_1 (rp, ap, ecc->size, b);
+  hi = mpn_addmul_1 (rp, ecc->Bmodp, ecc->size, hi);
+  assert (hi <= 1);
+  hi = cnd_add_n (hi, rp, ecc->Bmodp, ecc->size);
+  /* Sufficient roughly if b < B^size / p */
+  assert (hi == 0);
+}
+  
+void
+ecc_modp_submul_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
+		   const mp_limb_t *ap, mp_limb_t b)
+{
+  mp_limb_t hi;
+
+  assert (b <= 0xffffffff);
+  hi = mpn_submul_1 (rp, ap, ecc->size, b);
+  hi = mpn_submul_1 (rp, ecc->Bmodp, ecc->size, hi);
+  assert (hi <= 1);
+  hi = cnd_sub_n (hi, rp, ecc->Bmodp, ecc->size);
+  /* Sufficient roughly if b < B^size / p */
+  assert (hi == 0);
+}
+
+/* NOTE: mul and sqr needs 2*ecc->size limbs at rp */
+void
+ecc_modp_mul (const struct ecc_curve *ecc, mp_limb_t *rp,
+	      const mp_limb_t *ap, const mp_limb_t *bp)
+{
+  mpn_mul_n (rp, ap, bp, ecc->size);
+  ecc->reduce (ecc, rp);
+}
+
+void
+ecc_modp_sqr (const struct ecc_curve *ecc, mp_limb_t *rp,
+	      const mp_limb_t *ap)
+{
+  mpn_sqr (rp, ap, ecc->size);
+  ecc->reduce (ecc, rp);
+}
+
+void
+ecc_modp_inv (const struct ecc_curve *ecc, mp_limb_t *rp, mp_limb_t *ap,
+	      mp_limb_t *scratch)
+{
+  sec_modinv (rp, ap, ecc->size, ecc->p, ecc->pp1h, ecc->bit_size, scratch);
+}
+
diff --git a/ecc-modq.c b/ecc-modq.c
new file mode 100644
index 00000000..80a719a5
--- /dev/null
+++ b/ecc-modq.c
@@ -0,0 +1,59 @@
+/* ecc-modq.c */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "ecc-internal.h"
+
+/* Arithmetic mod q, the group order. */
+
+void
+ecc_modq_add (const struct ecc_curve *ecc, mp_limb_t *rp,
+	      const mp_limb_t *ap, const mp_limb_t *bp)
+{
+  mp_limb_t cy;
+  cy = mpn_add_n (rp, ap, bp, ecc->size);
+  cy = cnd_add_n (cy, rp, ecc->Bmodq, ecc->size);
+  cy = cnd_add_n (cy, rp, ecc->Bmodq, ecc->size);
+  assert (cy == 0);  
+}
+
+void
+ecc_modq_mul (const struct ecc_curve *ecc, mp_limb_t *rp,
+	      const mp_limb_t *ap, const mp_limb_t *bp)
+{
+  mpn_mul_n (rp, ap, bp, ecc->size);
+  ecc->modq (ecc, rp);
+}
+
+void
+ecc_modq_inv (const struct ecc_curve *ecc, mp_limb_t *rp, mp_limb_t *ap,
+	      mp_limb_t *scratch)
+{
+  sec_modinv (rp, ap, ecc->size, ecc->q, ecc->qp1h, ecc->bit_size, scratch);
+}
diff --git a/sec-add-1.c b/sec-add-1.c
new file mode 100644
index 00000000..7e7b4433
--- /dev/null
+++ b/sec-add-1.c
@@ -0,0 +1,42 @@
+/* sec-add-1.c */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "ecc-internal.h"
+
+mp_limb_t
+sec_add_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b)
+{
+  mp_size_t i;
+  for (i = 0; i < n; i++)
+    {
+      mp_limb_t r = ap[i] + b;
+      b = (r < b);
+      rp[i] = r;
+    }
+  return b;
+}
diff --git a/sec-modinv.c b/sec-modinv.c
new file mode 100644
index 00000000..f674a8fb
--- /dev/null
+++ b/sec-modinv.c
@@ -0,0 +1,170 @@
+/* sec-modinv.c */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "ecc-internal.h"
+
+static void
+cnd_neg (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n)
+{
+  mp_limb_t cy = (cnd != 0);
+  mp_limb_t mask = -cy;
+  mp_size_t i;
+
+  for (i = 0; i < n; i++)
+    {
+      mp_limb_t r = (ap[i] ^ mask) + cy;
+      cy = r < cy;
+      rp[i] = r;
+    }
+}
+
+static void
+cnd_swap (int cnd, mp_limb_t *ap, mp_limb_t *bp, mp_size_t n)
+{
+  mp_limb_t mask = - (mp_limb_t) (cnd != 0);
+  mp_size_t i;
+  for (i = 0; i < n; i++)
+    {
+      mp_limb_t a, b, t;
+      a = ap[i];
+      b = bp[i];
+      t = (a ^ b) & mask;
+      ap[i] = a ^ t;
+      bp[i] = b ^ t;
+    }
+}
+
+/* Compute a^{-1} mod m, with running time depending only on the size.
+   Also needs (m+1)/2, and m must be odd. */
+void
+sec_modinv (mp_limb_t *vp, mp_limb_t *ap, mp_size_t n,
+	    const mp_limb_t *mp, const mp_limb_t *mp1h, mp_size_t bit_size,
+	    mp_limb_t *scratch)
+{
+#define bp scratch
+#define dp (scratch + n)
+#define up (scratch + 2*n)
+
+  mp_bitcnt_t i;
+
+  /* Maintain
+
+       a = u * orig_a (mod m)
+       b = v * orig_a (mod m)
+
+     and b odd at all times. Initially,
+
+       a = a_orig, u = 1
+       b = m,      v = 0
+     */
+
+  assert (ap != vp);
+
+  up[0] = 1;
+  mpn_zero (up+1, n - 1);
+  mpn_copyi (bp, mp, n);
+  mpn_zero (vp, n);
+
+  for (i = bit_size + GMP_NUMB_BITS * n; i-- > 0; )
+    {
+      mp_limb_t odd, swap, cy;
+      
+      /* Always maintain b odd. The logic of the iteration is as
+	 follows. For a, b:
+
+	   odd = a & 1
+	   a -= odd * b
+	   if (underflow from a-b)
+	     {
+	       b += a, assigns old a
+	       a = B^n-a
+	     }
+	   
+	   a /= 2
+
+	 For u, v:
+
+	   if (underflow from a - b)
+	     swap u, v
+	   u -= odd * v
+	   if (underflow from u - v)
+	     u += m
+
+	   u /= 2
+	   if (a one bit was shifted out)
+	     u += (m+1)/2
+
+	 As long as a > 0, the quantity
+
+	   (bitsize of a) + (bitsize of b)
+
+	 is reduced by at least one bit per iteration, hence after
+         (bit_size of orig_a) + (bit_size of m) - 1 iterations we
+         surely have a = 0. Then b = gcd(orig_a, m) and if b = 1 then
+         also v = orig_a^{-1} (mod m)
+      */
+
+      assert (bp[0] & 1);
+      odd = ap[0] & 1;
+
+      /* Which variant is fastest depends on the speed of the various
+	 cnd_* functions. Assembly implementation would help. */
+#if 1
+      swap = cnd_sub_n (odd, ap, bp, n);
+      cnd_add_n (swap, bp, ap, n);
+      cnd_neg (swap, ap, ap, n);
+#else
+      swap = odd & mpn_sub_n (dp, ap, bp, n);
+      cnd_copy (swap, bp, ap, n);
+      cnd_neg (swap, dp, dp, n);
+      cnd_copy (odd, ap, dp, n);
+#endif
+
+#if 1
+      cnd_swap (swap, up, vp, n);
+      cy = cnd_sub_n (odd, up, vp, n);
+      cy -= cnd_add_n (cy, up, mp, n);
+#else
+      cy = cnd_sub_n (odd, up, vp, n);
+      cnd_add_n (swap, vp, up, n);
+      cnd_neg (swap, up, up, n);
+      cnd_add_n (cy ^ swap, up, mp, n);
+#endif
+      cy = mpn_rshift (ap, ap, n, 1);
+      assert (cy == 0);
+      cy = mpn_rshift (up, up, n, 1);
+      cy = cnd_add_n (cy, up, mp1h, n);
+      assert (cy == 0);
+    }
+  assert ( (ap[0] | ap[n-1]) == 0);
+#undef bp
+#undef dp
+#undef up
+}
diff --git a/sec-sub-1.c b/sec-sub-1.c
new file mode 100644
index 00000000..1aa04d04
--- /dev/null
+++ b/sec-sub-1.c
@@ -0,0 +1,43 @@
+/* sec-add-1.c */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *  
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ * 
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "ecc-internal.h"
+
+mp_limb_t
+sec_sub_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b)
+{
+  mp_size_t i;
+  for (i = 0; i < n; i++)
+    {
+      mp_limb_t a;
+      a = ap[i];
+      rp[i] = a - b;
+      b = a < b;
+    }
+  return b;
+}
diff --git a/testsuite/.test-rules.make b/testsuite/.test-rules.make
index 93f1f943..0f5cb568 100644
--- a/testsuite/.test-rules.make
+++ b/testsuite/.test-rules.make
@@ -160,6 +160,15 @@ dsa-test$(EXEEXT): dsa-test.$(OBJEXT)
 dsa-keygen-test$(EXEEXT): dsa-keygen-test.$(OBJEXT)
 	$(LINK) dsa-keygen-test.$(OBJEXT) $(TEST_OBJS) -o dsa-keygen-test$(EXEEXT)
 
+ecc-mod-test$(EXEEXT): ecc-mod-test.$(OBJEXT)
+	$(LINK) ecc-mod-test.$(OBJEXT) $(TEST_OBJS) -o ecc-mod-test$(EXEEXT)
+
+ecc-modinv-test$(EXEEXT): ecc-modinv-test.$(OBJEXT)
+	$(LINK) ecc-modinv-test.$(OBJEXT) $(TEST_OBJS) -o ecc-modinv-test$(EXEEXT)
+
+ecc-redc-test$(EXEEXT): ecc-redc-test.$(OBJEXT)
+	$(LINK) ecc-redc-test.$(OBJEXT) $(TEST_OBJS) -o ecc-redc-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 71e133f9..cdfa766b 100644
--- a/testsuite/Makefile.in
+++ b/testsuite/Makefile.in
@@ -34,7 +34,8 @@ TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \
 		     bignum-test.c random-prime-test.c \
 		     pkcs1-test.c \
 		     rsa-test.c rsa-encrypt-test.c rsa-keygen-test.c \
-		     dsa-test.c dsa-keygen-test.c
+		     dsa-test.c dsa-keygen-test.c \
+		     ecc-mod-test.c ecc-modinv-test.c ecc-redc-test.c
 
 TS_SOURCES = $(TS_NETTLE_SOURCES) $(TS_HOGWEED_SOURCES)
 CXX_SOURCES = cxx-test.cxx
diff --git a/testsuite/ecc-mod-test.c b/testsuite/ecc-mod-test.c
new file mode 100644
index 00000000..3ce82ed4
--- /dev/null
+++ b/testsuite/ecc-mod-test.c
@@ -0,0 +1,115 @@
+#include "testutils.h"
+
+static void
+ref_mod (mp_limb_t *rp, const mp_limb_t *ap, const mp_limb_t *mp, mp_size_t mn)
+{
+  mp_limb_t q[mn + 1];
+  mpn_tdiv_qr (q, rp, 0, ap, 2*mn, mp, mn);
+}
+
+#define MAX_ECC_SIZE (1 + 521 / GMP_NUMB_BITS)
+#define MAX_SIZE (2*MAX_ECC_SIZE)
+#define COUNT 500
+
+void
+test_main (void)
+{
+  gmp_randstate_t state;
+  mp_limb_t a[MAX_SIZE];
+  mp_limb_t m[MAX_SIZE];
+  mp_limb_t ref[MAX_SIZE];
+  unsigned i;
+  mpz_t r;
+
+  gmp_randinit_default (state);
+  
+  mpz_init (r);
+  
+  for (i = 0; ecc_curves[i]; i++)
+    {
+      const struct ecc_curve *ecc = ecc_curves[i];
+      unsigned j;
+      for (j = 0; j < COUNT; j++)
+	{
+	  if (j & 1)
+	    mpz_rrandomb (r, state, 2*ecc->size * GMP_NUMB_BITS);
+	  else
+	    mpz_urandomb (r, state, 2*ecc->size * GMP_NUMB_BITS);
+
+	  _mpz_copy_limbs (a, r, 2*ecc->size);
+
+	  ref_mod (ref, a, ecc->p, ecc->size);
+
+	  mpn_copyi (m, a, 2*ecc->size);
+	  ecc->modp (ecc, m);
+	  if (mpn_cmp (m, ecc->p, ecc->size) >= 0)
+	    mpn_sub_n (m, m, ecc->p, ecc->size);
+
+	  if (mpn_cmp (m, ref, ecc->size))
+	    {
+	      fprintf (stderr, "ecc->modp failed: bit_size = %u\n",
+		       ecc->bit_size);
+	      gmp_fprintf (stderr, "a   = %Nx\n", a, 2*ecc->size);
+	      gmp_fprintf (stderr, "m   = %Nx (bad)\n", m, ecc->size);
+	      gmp_fprintf (stderr, "ref = %Nx\n", ref, ecc->size);
+	      abort ();
+	    }
+
+	  if (ecc->Bmodp_size < ecc->size)
+	    {
+	      mpn_copyi (m, a, 2*ecc->size);
+	      ecc_generic_modp (ecc, m);
+	      if (mpn_cmp (m, ecc->p, ecc->size) >= 0)
+		mpn_sub_n (m, m, ecc->p, ecc->size);
+
+	      if (mpn_cmp (m, ref, ecc->size))
+		{
+		  fprintf (stderr, "ecc_generic_modp failed: bit_size = %u\n",
+			   ecc->bit_size);
+		  gmp_fprintf (stderr, "a   = %Nx\n", a, 2*ecc->size);
+		  gmp_fprintf (stderr, "m   = %Nx (bad)\n", m, ecc->size);
+		  gmp_fprintf (stderr, "ref = %Nx\n", ref, ecc->size);
+		  abort ();
+		}
+	    }
+
+	  ref_mod (ref, a, ecc->q, ecc->size);
+
+	  mpn_copyi (m, a, 2*ecc->size);
+	  ecc->modq (ecc, m);
+	  if (mpn_cmp (m, ecc->q, ecc->size) >= 0)
+	    mpn_sub_n (m, m, ecc->q, ecc->size);
+
+	  if (mpn_cmp (m, ref, ecc->size))
+	    {
+	      fprintf (stderr, "ecc->modq failed: bit_size = %u\n",
+		       ecc->bit_size);
+	      gmp_fprintf (stderr, "a   = %Nx\n", a, 2*ecc->size);
+	      gmp_fprintf (stderr, "m   = %Nx (bad)\n", m, ecc->size);
+	      gmp_fprintf (stderr, "ref = %Nx\n", ref, ecc->size);
+	      abort ();
+	    }
+
+	  if (ecc->Bmodp_size < ecc->size)
+	    {
+	      mpn_copyi (m, a, 2*ecc->size);
+	      ecc_generic_modq (ecc, m);
+	      if (mpn_cmp (m, ecc->q, ecc->size) >= 0)
+		mpn_sub_n (m, m, ecc->q, ecc->size);
+
+	      if (mpn_cmp (m, ref, ecc->size))
+		{
+		  fprintf (stderr, "ecc_generic_modp failed: bit_size = %u\n",
+			   ecc->bit_size);
+		  gmp_fprintf (stderr, "a   = %Nx\n", a, 2*ecc->size);
+		  gmp_fprintf (stderr, "m   = %Nx (bad)\n", m, ecc->size);
+		  gmp_fprintf (stderr, "ref = %Nx\n", ref, ecc->size);
+		  abort ();
+		}
+	    }
+	}
+    }
+
+  mpz_clear (r);
+  gmp_randclear (state);
+}
diff --git a/testsuite/ecc-modinv-test.c b/testsuite/ecc-modinv-test.c
new file mode 100644
index 00000000..b8414e98
--- /dev/null
+++ b/testsuite/ecc-modinv-test.c
@@ -0,0 +1,107 @@
+#include "testutils.h"
+
+static int
+ref_modinv (mp_limb_t *rp, const mp_limb_t *ap, const mp_limb_t *mp, mp_size_t mn)
+{
+  mp_limb_t tp[4*(mn+1)];
+  mp_limb_t *up = tp;
+  mp_limb_t *vp = tp + mn+1;
+  mp_limb_t *gp = tp + 2*(mn+1);
+  mp_limb_t *sp = tp + 3*(mn+1);
+  mp_size_t gn, sn;
+
+  mpn_copyi (up, ap, mn);
+  mpn_copyi (vp, mp, mn);
+  gn = mpn_gcdext (gp, sp, &sn, up, mn, vp, mn);
+  if (gn != 1 || gp[0] != 1)
+    return 0;
+  
+  if (sn < 0)
+    mpn_sub (sp, mp, mn, sp, -sn);
+  else if (sn < mn)
+    /* Zero-pad. */
+    mpn_zero (sp + sn, mn - sn);
+
+  mpn_copyi (rp, sp, mn);
+  return 1;
+}
+
+#define MAX_ECC_SIZE (1 + 521 / GMP_NUMB_BITS)
+#define COUNT 500
+
+void
+test_main (void)
+{
+  gmp_randstate_t state;
+  mp_limb_t a[MAX_ECC_SIZE];
+  mp_limb_t ai[MAX_ECC_SIZE];
+  mp_limb_t ref[MAX_ECC_SIZE];
+  mp_limb_t scratch[ECC_MODINV_ITCH (MAX_ECC_SIZE)];
+  unsigned i;
+  mpz_t r;
+
+  gmp_randinit_default (state);
+  mpz_init (r);
+  
+  for (i = 0; ecc_curves[i]; i++)
+    {
+      const struct ecc_curve *ecc = ecc_curves[i];
+      unsigned j;
+      for (j = 0; j < COUNT; j++)
+	{
+	  if (j & 1)
+	    mpz_rrandomb (r, state, ecc->size * GMP_NUMB_BITS);
+	  else
+	    mpz_urandomb (r, state, ecc->size * GMP_NUMB_BITS);
+
+	  _mpz_copy_limbs (a, r, ecc->size);
+
+	  if (!ref_modinv (ref, a, ecc->p, ecc->size))
+	    {
+	      if (verbose)
+		fprintf (stderr, "Test %u (bit size %u) not invertible.\n",
+			 j, ecc->bit_size);
+	      continue;
+	    }
+	  ecc_modp_inv (ecc, ai, a, scratch);
+	  if (mpn_cmp (ref, ai, ecc->size))
+	    {
+	      fprintf (stderr, "ecc_modp_inv failed (test %u, bit size %u):\n",
+		       j, ecc->bit_size);
+	      gmp_fprintf (stderr, "a = %Zx\n"
+			   "p = %Nx\n"
+			   "t = %Nx (bad)\n"
+			   "r = %Nx\n",
+			   r, ecc->p, ecc->size,
+			   ai, ecc->size,
+			   ref, ecc->size);
+	      abort ();
+	    }
+
+	  _mpz_copy_limbs (a, r, ecc->size);
+
+	  if (!ref_modinv (ref, a, ecc->q, ecc->size))
+	    {
+	      fprintf (stderr, "Test %u (bit size %u) not invertible.\n",
+		       j, ecc->bit_size);
+	      continue;
+	    }
+	  ecc_modq_inv (ecc, ai, a, scratch);
+	  if (mpn_cmp (ref, ai, ecc->size))
+	    {
+	      fprintf (stderr, "ecc_modq_inv failed (test %u, bit size %u):\n",
+		       j, ecc->bit_size);
+	      gmp_fprintf (stderr, "a = %Zx\n"
+			   "p = %Nx\n"
+			   "t = %Nx (bad)\n"
+			   "r = %Nx\n",
+			   r, ecc->p, ecc->size,
+			   ai, ecc->size,
+			   ref, ecc->size);
+	      abort ();
+	    }
+	}
+    }
+  gmp_randclear (state);
+  mpz_clear (r);
+}
diff --git a/testsuite/ecc-redc-test.c b/testsuite/ecc-redc-test.c
new file mode 100644
index 00000000..ac7de74e
--- /dev/null
+++ b/testsuite/ecc-redc-test.c
@@ -0,0 +1,100 @@
+#include "testutils.h"
+
+static void
+ref_redc (mp_limb_t *rp, const mp_limb_t *ap, const mp_limb_t *mp, mp_size_t mn)
+{
+  mpz_t t;
+  mpz_t m, a;
+  mp_size_t an;
+
+  mpz_init (t);
+  mpz_setbit (t, mn * GMP_NUMB_BITS);
+
+  _mpz_init_mpn (m, mp, mn);
+
+  an = 2*mn;
+  while (an > 0 && ap[an-1] == 0)
+    an--;
+
+  _mpz_init_mpn (a, ap, an);
+  
+  mpz_invert (t, t, m);
+  mpz_mul (t, t, a);
+  mpz_mod (t, t, m);
+
+  _mpz_copy_limbs (rp, t, mn);
+
+  mpz_clear (t);
+}
+
+#define MAX_ECC_SIZE (1 + 521 / GMP_NUMB_BITS)
+#define MAX_SIZE (2*MAX_ECC_SIZE)
+#define COUNT 1000
+
+void
+test_main (void)
+{
+  gmp_randstate_t state;
+  mp_limb_t a[MAX_SIZE];
+  mp_limb_t m[MAX_SIZE];
+  mp_limb_t ref[MAX_SIZE];
+  unsigned i;
+  mpz_t r;
+
+  gmp_randinit_default (state);
+  
+  mpz_init (r);
+  
+  for (i = 0; ecc_curves[i]; i++)
+    {
+      const struct ecc_curve *ecc = ecc_curves[i];
+      unsigned j;
+      if (!ecc->redc)
+	continue;
+
+      for (j = 0; j < COUNT; j++)
+	{
+	  if (j & 1)
+	    mpz_rrandomb (r, state, 2*ecc->size * GMP_NUMB_BITS);
+	  else
+	    mpz_urandomb (r, state, 2*ecc->size * GMP_NUMB_BITS);
+
+	  _mpz_copy_limbs (a, r, 2*ecc->size);
+
+	  ref_redc (ref, a, ecc->p, ecc->size);
+
+	  mpn_copyi (m, a, 2*ecc->size);
+	  ecc->redc (ecc, m);
+	  if (mpn_cmp (m, ecc->p, ecc->size) >= 0)
+	    mpn_sub_n (m, m, ecc->p, ecc->size);
+
+	  if (mpn_cmp (m, ref, ecc->size))
+	    {
+	      fprintf (stderr, "ecc->redc failed: bit_size = %u\n",
+		       ecc->bit_size);
+	      gmp_fprintf (stderr, "a   = %Nx\n", a, 2*ecc->size);
+	      gmp_fprintf (stderr, "m   = %Nx (bad)\n", m, ecc->size);
+	      gmp_fprintf (stderr, "ref = %Nx\n", ref, ecc->size);
+	      abort ();
+	    }
+
+	  mpn_copyi (m, a, 2*ecc->size);
+	  ecc_generic_redc (ecc, m);
+	  if (mpn_cmp (m, ecc->p, ecc->size) >= 0)
+	    mpn_sub_n (m, m, ecc->p, ecc->size);
+
+	  if (mpn_cmp (m, ref, ecc->size))
+	    {
+	      fprintf (stderr, "ecc_generic_redc failed: bit_size = %u\n",
+		       ecc->bit_size);
+	      gmp_fprintf (stderr, "a   = %Nx\n", a, 2*ecc->size);
+	      gmp_fprintf (stderr, "m   = %Nx (bad)\n", m, ecc->size);
+	      gmp_fprintf (stderr, "ref = %Nx\n", ref, ecc->size);
+	      abort ();
+	    }
+	}
+    }
+
+  mpz_clear (r);
+  gmp_randclear (state);
+}
diff --git a/testsuite/testutils.c b/testsuite/testutils.c
index c0a75f8f..60614a0e 100644
--- a/testsuite/testutils.c
+++ b/testsuite/testutils.c
@@ -1086,5 +1086,14 @@ test_dsa_key(struct dsa_public_key *pub,
   mpz_clear(t);
 }
 
+const struct ecc_curve * const ecc_curves[] = {
+  &nettle_secp_192r1,
+  &nettle_secp_224r1,
+  &nettle_secp_256r1,
+  &nettle_secp_384r1,
+  &nettle_secp_521r1,
+  NULL
+};
+
 #endif /* WITH_HOGWEED */
 
diff --git a/testsuite/testutils.h b/testsuite/testutils.h
index 7519d65b..ed57b33e 100644
--- a/testsuite/testutils.h
+++ b/testsuite/testutils.h
@@ -18,6 +18,9 @@
 #if WITH_HOGWEED
 # include "rsa.h"
 # include "dsa.h"
+# include "ecc-curve.h"
+# include "ecc-internal.h"
+# include "gmp-glue.h"
 #endif
 
 #include "nettle-meta.h"
@@ -190,6 +193,8 @@ test_dsa_key(struct dsa_public_key *pub,
 	     struct dsa_private_key *key,
 	     unsigned q_size);
 
+extern const struct ecc_curve * const ecc_curves[];
+
 #endif /* WITH_HOGWEED */
   
 /* LDATA needs to handle NUL characters. */