Integrate ecc_mul_g.

14 files changed, 962 insertions, 3 deletions

diff --git a/ChangeLog b/ChangeLog
index fc0a9395..79305a9a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,25 @@
 2013-02-15  Niels Möller  <nisse@lysator.liu.se>
 
+	Integrate ecc_mul_g.
+	* ecc.h: New file.
+	* ecc-j-to-a.c: New file.
+	* ecc-size.c: New file.
+	* ecc-add-jja.c: New file.
+	* ecc-dup-jj.c: New file.
+	* ecc-mul-g.c: New file.
+	* sec-tabselect.c: New file.
+	* Makefile.in (hogweed_SOURCES): Added new files.
+	(HEADERS): Added ecc.h
+	* testsuite/ecc-mul-g-test.c: New file.
+	* testsuite/Makefile.in (TS_HOGWEED_SOURCES): Added
+	ecc-mul-g-test.c.
+	* testsuite/testutils.c (xalloc_limbs): New function.
+	(test_mpn): New function.
+	(test_ecc_point): New function.
+	(test_ecc_mul_a): New function.
+	(test_ecc_mul_j): New function.
+	* testsuite/testutils.h: Corresponding declarations.
+
 	Integrate ECC internals.
 	* ecc-curve.h: New file.
 	* ecc-internal.h: New file.
diff --git a/Makefile.in b/Makefile.in
index b6c46920..0d8df181 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -127,12 +127,14 @@ hogweed_SOURCES = sexp.c sexp-format.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
+		  ecc-192.c ecc-224.c ecc-256.c ecc-384.c ecc-521.c \
+		  ecc-size.c ecc-j-to-a.c ecc-dup-jj.c ecc-add-jja.c \
+		  ecc-mul-g.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 \
-	  des.h des-compat.h dsa.h ecc-curve.h \
+	  des.h des-compat.h dsa.h ecc-curve.h ecc.h \
 	  gcm.h gosthash94.h hmac.h \
 	  knuth-lfib.h \
 	  macros.h \
diff --git a/ecc-add-jja.c b/ecc-add-jja.c
new file mode 100644
index 00000000..f358e8ba
--- /dev/null
+++ b/ecc-add-jja.c
@@ -0,0 +1,122 @@
+/* ecc-dup-jj.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.h"
+#include "ecc-internal.h"
+
+/* NOTE: Behaviour for corner cases:
+
+   + p = 0   ==>  r = 0 (invalid except if also q = 0)
+
+   + q = 0   ==>  r = invalid
+
+   + p = -q  ==>  r = 0, correct!
+
+   + p = q   ==>  r = 0, invalid
+*/
+
+mp_size_t
+ecc_add_jja_itch (const struct ecc_curve *ecc)
+{
+  return ECC_ADD_JJA_ITCH (ecc->size);
+}
+
+void
+ecc_add_jja (const struct ecc_curve *ecc,
+	     mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
+	     mp_limb_t *scratch)
+{
+  /* Formulas, from djb,
+     http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b):
+
+     Computation		Operation	Live variables
+     
+      ZZ = Z_1^2		sqr		ZZ
+      H = X_2*ZZ - X_1		mul (djb: U_2)	ZZ, H
+      HH = H^2			sqr		ZZ, H, HH
+      ZZZ = ZZ*Z_1		mul		ZZ, H, HH, ZZZ
+      Z_3 = (Z_1+H)^2-ZZ-HH	sqr		H, HH, ZZZ
+      W = 2 (Y_2*ZZZ - Y_1)	mul (djb: S_2)	H, HH, W
+      I = 4*HH					H, W, I
+      J = H*I			mul		W, I, J
+      V = X_1*I			mul		W, J, V
+      X_3 = W^2-J-2*V		sqr		W, J, V
+      Y_3 = W*(V-X_3)-2*Y_1*J	mul, mul
+  */
+#define zz  scratch
+#define h  (scratch + ecc->size)
+#define hh (scratch + 2*ecc->size)
+#define w  (scratch + 3*ecc->size)
+#define j  (scratch + 4*ecc->size)
+#define v   scratch
+
+#define x1  p
+#define y1 (p + ecc->size)
+#define z1 (p + 2*ecc->size)
+#define x2  q
+#define y2 (q + ecc->size)
+
+  /* zz */
+  ecc_modp_sqr (ecc, zz, z1);
+  /* h*/
+  ecc_modp_mul (ecc, h, x2, zz);
+  ecc_modp_sub (ecc, h, h, x1);
+  /* hh */
+  ecc_modp_sqr (ecc, hh, h);
+  /* Do z^3 early, store at w. */
+  ecc_modp_mul (ecc, w, zz, z1);
+  /* z_3, use j area for scratch */
+  ecc_modp_add (ecc, r + 2*ecc->size, p + 2*ecc->size, h);
+  ecc_modp_sqr (ecc, j, r + 2*ecc->size);
+  ecc_modp_sub (ecc, j, j, zz);
+  ecc_modp_sub (ecc, r + 2*ecc->size, j, hh);
+  
+  /* w */
+  ecc_modp_mul (ecc, j, y2, w);
+  ecc_modp_sub (ecc, w, j, y1);
+  ecc_modp_mul_1 (ecc, w, w, 2);
+  
+  /* i replaces hh, j */
+  ecc_modp_mul_1 (ecc, hh, hh, 4);
+  ecc_modp_mul (ecc, j, hh, h);
+
+  /* v */
+  ecc_modp_mul (ecc, v, x1, hh);
+
+  /* x_3, use (h, hh) as sqratch */  
+  ecc_modp_sqr (ecc, h, w);
+  ecc_modp_sub (ecc, r, h, j);
+  ecc_modp_submul_1 (ecc, r, v, 2);
+
+  /* y_3, use (h, hh) as sqratch */
+  ecc_modp_mul (ecc, h, y1, j); /* frees j */
+  ecc_modp_sub (ecc, r + ecc->size, v, r);
+  ecc_modp_mul (ecc, j, r + ecc->size, w);
+  ecc_modp_submul_1 (ecc, j, h, 2);
+  mpn_copyi (r + ecc->size, j, ecc->size);
+}
diff --git a/ecc-dup-jj.c b/ecc-dup-jj.c
new file mode 100644
index 00000000..3c850d70
--- /dev/null
+++ b/ecc-dup-jj.c
@@ -0,0 +1,107 @@
+/* ecc-dup-jj.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.h"
+#include "ecc-internal.h"
+
+/* NOTE: Behaviour for corner cases:
+
+   + p = 0  ==>  r = 0, correct!
+*/
+mp_size_t
+ecc_dup_jj_itch (const struct ecc_curve *ecc)
+{
+  return ECC_DUP_JJ_ITCH (ecc->size);
+}
+
+void
+ecc_dup_jj (const struct ecc_curve *ecc,
+	    mp_limb_t *r, const mp_limb_t *p,
+	    mp_limb_t *scratch)
+{
+  /* Formulas (from djb,
+     http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b):
+
+     Computation			Operation	Live variables
+     delta = z^2			sqr		delta
+     gamma = y^2			sqr		delta, gamma
+     z' = (y+z)^2-gamma-delta		sqr		delta, gamma
+     alpha = 3*(x-delta)*(x+delta)	mul		gamma, beta, alpha
+     beta = x*gamma			mul		gamma, beta, alpha
+     x' = alpha^2-8*beta		sqr		gamma, beta, alpha
+     y' = alpha*(4*beta-x')-8*gamma^2	mul, sqr
+  */
+
+#define delta  scratch
+#define gamma (scratch + ecc->size)
+#define beta  (scratch + 2*ecc->size)
+#define g2    (scratch + 3*ecc->size)
+#define sum   (scratch + 4*ecc->size)
+#define alpha  scratch /* Overlap delta */
+  
+#define xp p
+#define yp (p + ecc->size)
+#define zp (p + 2*ecc->size)
+  
+  /* delta */
+  ecc_modp_sqr (ecc, delta, zp);
+
+  /* gamma */
+  ecc_modp_sqr (ecc, gamma, yp);
+
+  /* z'. Can use beta area as scratch. */
+  ecc_modp_add (ecc, r + 2*ecc->size, yp, zp);
+  ecc_modp_sqr (ecc, beta, r + 2*ecc->size);
+  ecc_modp_sub (ecc, beta, beta, gamma);
+  ecc_modp_sub (ecc, r + 2*ecc->size, beta, delta);
+  
+  /* alpha. Can use beta area as scratch, and overwrite delta. */
+  ecc_modp_add (ecc, sum, xp, delta);
+  ecc_modp_sub (ecc, delta, xp, delta);
+  ecc_modp_mul (ecc, beta, sum, delta);
+  ecc_modp_mul_1 (ecc, alpha, beta, 3);
+
+  /* beta */
+  ecc_modp_mul (ecc, beta, xp, gamma);
+
+  /* Do gamma^2 and 4*beta early, to get them out of the way. We can
+     then use the old area at gamma as scratch. */
+  ecc_modp_sqr (ecc, g2, gamma);
+  ecc_modp_mul_1 (ecc, sum, beta, 4);
+  
+  /* x' */
+  ecc_modp_sqr (ecc, gamma, alpha);   /* Overwrites gamma and beta */
+  ecc_modp_submul_1 (ecc, gamma, sum, 2);
+  mpn_copyi (r, gamma, ecc->size);
+
+  /* y' */
+  ecc_modp_sub (ecc, sum, sum, r);
+  ecc_modp_mul (ecc, gamma, sum, alpha);
+  ecc_modp_submul_1 (ecc, gamma, g2, 8);
+  mpn_copyi (r + ecc->size, gamma, ecc->size);
+}
diff --git a/ecc-j-to-a.c b/ecc-j-to-a.c
new file mode 100644
index 00000000..ae56bbaf
--- /dev/null
+++ b/ecc-j-to-a.c
@@ -0,0 +1,115 @@
+/* ecc-j-to-a.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.h"
+#include "ecc-internal.h"
+
+mp_size_t
+ecc_j_to_a_itch (const struct ecc_curve *ecc)
+{
+  /* Needs 2*ecc->size + scratch for ecc_modq_inv */
+  return ECC_J_TO_A_ITCH (ecc->size);
+}
+
+void
+ecc_j_to_a (const struct ecc_curve *ecc,
+	    int flags,
+	    mp_limb_t *r, const mp_limb_t *p,
+	    mp_limb_t *scratch)
+{
+#define izp   scratch
+#define up   (scratch + ecc->size)
+#define iz2p (scratch + ecc->size)
+#define iz3p (scratch + 2*ecc->size)
+#define tp    scratch
+
+  mp_limb_t cy;
+
+  if (ecc->use_redc)
+    {
+      /* Set v = (r_z / B^2)^-1,
+
+	 r_x = p_x v^2 / B^3 =  ((v/B * v)/B * p_x)/B
+	 r_y = p_y v^3 / B^4 = (((v/B * v)/B * v)/B * p_x)/B
+
+	 Skip the first redc, if we want to stay in Montgomery
+	 representation.
+      */
+
+      mpn_copyi (up, p + 2*ecc->size, ecc->size);
+      mpn_zero (up + ecc->size, ecc->size);
+      ecc->redc (ecc, up);
+      mpn_zero (up + ecc->size, ecc->size);
+      ecc->redc (ecc, up);
+
+      ecc_modp_inv (ecc, izp, up, up + ecc->size);
+
+      if (flags & 1)
+	{
+	  /* Divide this common factor by B */
+	  mpn_copyi (iz3p, izp, ecc->size);
+	  mpn_zero (iz3p + ecc->size, ecc->size);
+	  ecc->redc (ecc, iz3p);
+      
+	  ecc_modp_mul (ecc, iz2p, izp, iz3p);
+	}
+      else
+	ecc_modp_sqr (ecc, iz2p, izp);	
+    }
+  else
+    {
+      /* Set s = p_z^{-1}, r_x = p_x s^2, r_y = p_y s^3 */
+
+      mpn_copyi (up, p+2*ecc->size, ecc->size); /* p_z */
+      ecc_modp_inv (ecc, izp, up, up + ecc->size);
+
+      ecc_modp_sqr (ecc, iz2p, izp);
+    }
+
+  ecc_modp_mul (ecc, iz3p, iz2p, p);
+  /* ecc_modp (and ecc_modp_mul) may return a value up to 2p - 1, so
+     do a conditional subtraction. */
+  cy = mpn_sub_n (r, iz3p, ecc->p, ecc->size);
+  cnd_copy (cy, r, iz3p, ecc->size);
+
+  if (flags & 2)
+    /* Skip y coordinate */
+    return;
+
+  ecc_modp_mul (ecc, iz3p, iz2p, izp);
+  ecc_modp_mul (ecc, tp, iz3p, p + ecc->size);
+  /* And a similar subtraction. */
+  cy = mpn_sub_n (r + ecc->size, tp, ecc->p, ecc->size);
+  cnd_copy (cy, r + ecc->size, tp, ecc->size);
+
+#undef izp
+#undef up
+#undef iz2p
+#undef iz3p
+#undef tp
+}
diff --git a/ecc-mul-g.c b/ecc-mul-g.c
new file mode 100644
index 00000000..e202e26b
--- /dev/null
+++ b/ecc-mul-g.c
@@ -0,0 +1,103 @@
+/* ecc-mul-g.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.h"
+#include "ecc-internal.h"
+
+mp_size_t
+ecc_mul_g_itch (const struct ecc_curve *ecc)
+{
+  /* Needs 3*ecc->size + scratch for ecc_add_jja. */
+  return ECC_MUL_G_ITCH (ecc->size);
+}
+
+void
+ecc_mul_g (const struct ecc_curve *ecc, mp_limb_t *r,
+	   const mp_limb_t *np, mp_limb_t *scratch)
+{
+  /* Scratch need determined by the ecc_add_jja call. Current total is
+     9 * ecc->size, at most 648 bytes. */
+#define tp scratch
+#define scratch_out (scratch + 3*ecc->size)
+
+  unsigned k, c;
+  unsigned i, j;
+  unsigned bit_rows;
+
+  int is_zero;
+
+  k = ecc->pippenger_k;
+  c = ecc->pippenger_c;
+
+  bit_rows = (ecc->bit_size + k - 1) / k;
+  
+  mpn_zero (r, 3*ecc->size);
+  
+  for (i = k, is_zero = 1; i-- > 0; )
+    {
+      ecc_dup_jj (ecc, r, r, scratch);
+      for (j = 0; j * c < bit_rows; j++)
+	{
+	  unsigned bits;
+	  mp_bitcnt_t bit_index;
+	  
+	  /* Extract c bits from n, stride k, starting at i + kcj,
+	     ending at i + k (cj + c - 1)*/
+	  for (bits = 0, bit_index = i + k*(c*j+c); bit_index > i + k*c*j; )
+	    {
+	      mp_size_t limb_index;
+	      unsigned shift;
+	      
+	      bit_index -= k;
+
+	      limb_index = bit_index / GMP_NUMB_BITS;
+	      if (limb_index >= ecc->size)
+		continue;
+
+	      shift = bit_index % GMP_NUMB_BITS;
+	      bits = (bits << 1) | ((np[limb_index] >> shift) & 1);
+	    }
+	  sec_tabselect (tp, 2*ecc->size,
+			 (ecc->pippenger_table
+			  + (2*ecc->size * (mp_size_t) j << c)),
+			 1<<c, bits);
+	  cnd_copy (is_zero, r, tp, 2*ecc->size);
+	  cnd_copy (is_zero, r + 2*ecc->size, ecc->unit, ecc->size);
+	  
+	  ecc_add_jja (ecc, tp, r, tp, scratch_out);
+	  /* Use the sum when valid. ecc_add_jja produced garbage if
+	     is_zero != 0 or bits == 0, . */	  
+	  cnd_copy (bits & (is_zero - 1), r, tp, 3*ecc->size);
+	  is_zero &= (bits == 0);
+	}
+    }
+#undef tp
+#undef scratch_out
+}
diff --git a/ecc-size.c b/ecc-size.c
new file mode 100644
index 00000000..c829d460
--- /dev/null
+++ b/ecc-size.c
@@ -0,0 +1,48 @@
+/* ecc-size.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.h"
+#include "ecc-internal.h"
+
+mp_size_t
+ecc_size (const struct ecc_curve *ecc)
+{
+  return ecc->size;
+}
+
+mp_size_t
+ecc_size_a (const struct ecc_curve *ecc)
+{
+  return 2*ecc->size;
+}
+
+mp_size_t
+ecc_size_j (const struct ecc_curve *ecc)
+{
+  return 3*ecc->size;
+}
diff --git a/ecc.h b/ecc.h
new file mode 100644
index 00000000..c65a23ba
--- /dev/null
+++ b/ecc.h
@@ -0,0 +1,191 @@
+/* ecc.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_H_INCLUDED
+#define NETTLE_ECC_H_INCLUDED
+
+#include <stdint.h>
+
+#include <gmp.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* Name mangling */
+#define ecc_size nettle_ecc_size
+#define ecc_size_a nettle_ecc_size_a
+#define ecc_size_j nettle_ecc_size_j
+#define ecc_a_to_a_itch nettle_ecc_a_to_a_itch
+#define ecc_a_to_a nettle_ecc_a_to_a
+#define ecc_a_to_j nettle_ecc_a_to_j
+#define ecc_j_to_a_itch nettle_ecc_j_to_a_itch
+#define ecc_j_to_a nettle_ecc_j_to_a
+#define ecc_dup_ja_itch nettle_ecc_dup_ja_itch
+#define ecc_dup_ja nettle_ecc_dup_ja
+#define ecc_dup_jj_itch nettle_ecc_dup_jj_itch
+#define ecc_dup_jj nettle_ecc_dup_jj
+#define ecc_add_jja_itch nettle_ecc_add_jja_itch
+#define ecc_add_jja nettle_ecc_add_jja
+#define ecc_add_jjj_itch nettle_ecc_add_jjj_itch
+#define ecc_add_jjj nettle_ecc_add_jjj
+#define ecc_mul_g_itch nettle_ecc_mul_g_itch
+#define ecc_mul_g nettle_ecc_mul_g
+#define ecc_mul_a_itch nettle_ecc_mul_a_itch
+#define ecc_mul_a nettle_ecc_mul_a
+
+struct ecc_curve;
+
+/* Points on a curve are represented as arrays of mp_limb_t. For some
+   curves, point coordinates are represented in montgomery form. We
+   use either affine coordinates x,y, or Jacobian coordinates X, Y, Z,
+   where x = X/Z^2 and y = X/Z^2.
+
+   Since we use additive notation for the groups, the infinity point
+   on the curve is denoted 0. The infinity point can be represented
+   with x = y = 0 in affine coordinates, and Z = 0 in Jacobian
+   coordinates. However, note that most of the ECC functions do *not*
+   support infinity as an input or output.
+*/
+
+/* FIXME: Also provided some compile time constants? */
+
+/* Returns the size of a single coordinate. */
+mp_size_t
+ecc_size (const struct ecc_curve *ecc);
+
+/* Size of a point, using affine coordinates x, y. */
+mp_size_t
+ecc_size_a (const struct ecc_curve *ecc);
+
+/* Size of a point, using jacobian coordinates X, Y and Z. */
+mp_size_t
+ecc_size_j (const struct ecc_curve *ecc);
+
+/* FIXME: Rename the low-level (and side-channel silent) functions to
+   _ecc_*, and provide public ecc_* functions which handle the
+   infinity points properly? */
+
+/* Converts the affine coordinates of a point into montgomery form, if
+   used for this curve. */
+mp_size_t
+ecc_a_to_a_itch (const struct ecc_curve *ecc);
+void
+ecc_a_to_a (const struct ecc_curve *ecc,
+	    mp_limb_t *r, const mp_limb_t *p,
+	    mp_limb_t *scratch);
+
+/* Converts a point P in affine coordinates into a point R in jacobian
+   coordinates. If INITIAL is non-zero, and the curve uses montgomery
+   coordinates, also convert coordinates to montgomery form. */
+void
+ecc_a_to_j (const struct ecc_curve *ecc,
+	    int initial,
+	    mp_limb_t *r, const mp_limb_t *p);
+
+/* Converts a point P in jacobian coordinates into a point R in affine
+   coordinates. If FLAGS has bit 0 set, and the curve uses montgomery
+   coordinates, also undo the montgomery conversion. If flags has bit
+   1 set, produce x coordinate only. */
+mp_size_t
+ecc_j_to_a_itch (const struct ecc_curve *ecc);
+void
+ecc_j_to_a (const struct ecc_curve *ecc,
+	    int flags,
+	    mp_limb_t *r, const mp_limb_t *p,
+	    mp_limb_t *scratch);
+
+/* Group operations */
+
+
+/* Point doubling, with jacobian output and affine input. Corner
+   cases: Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */
+mp_size_t
+ecc_dup_ja_itch (const struct ecc_curve *ecc);
+void
+ecc_dup_ja (const struct ecc_curve *ecc,
+	    mp_limb_t *r, const mp_limb_t *p,
+	    mp_limb_t *scratch);
+
+/* Point doubling, with jacobian input and output. Corner cases:
+   Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */
+mp_size_t
+ecc_dup_jj_itch (const struct ecc_curve *ecc);
+void
+ecc_dup_jj (const struct ecc_curve *ecc,
+	    mp_limb_t *r, const mp_limb_t *p,
+	    mp_limb_t *scratch);
+
+
+/* Point addition, with jacobian output, one jacobian input and one
+   affine input. Corner cases: Fails for the cases
+
+     P = Q != 0                       Duplication of non-zero point
+     P = 0, Q != 0 or P != 0, Q = 0   One input zero
+   
+     Correctly gives R = 0 if P = Q = 0 or P = -Q. */
+mp_size_t
+ecc_add_jja_itch (const struct ecc_curve *ecc);
+void
+ecc_add_jja (const struct ecc_curve *ecc,
+	     mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
+	     mp_limb_t *scratch);
+
+/* Point addition with Jacobian input and output. */
+mp_size_t
+ecc_add_jjj_itch (const struct ecc_curve *ecc);
+void
+ecc_add_jjj (const struct ecc_curve *ecc,
+	     mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
+	     mp_limb_t *scratch);
+
+
+/* Computes N * the group generator. N is an array of ecc_size()
+   limbs. It must be in the range 0 < N < group order, then R != 0,
+   and the algorithm can work without any intermediate values getting
+   to zero. */ 
+mp_size_t
+ecc_mul_g_itch (const struct ecc_curve *ecc);
+void
+ecc_mul_g (const struct ecc_curve *ecc, mp_limb_t *r,
+	   const mp_limb_t *np, mp_limb_t *scratch);
+
+/* Computes N * P. The scalar N is the same as for ecc_mul_g. P is a
+   non-zero point on the curve, in affine coordinates. Pass a non-zero
+   INITIAL if the point coordinates have not previously been converted
+   to Montgomery representation. Output R is a non-zero point, in
+   Jacobian coordinates. */
+mp_size_t
+ecc_mul_a_itch (const struct ecc_curve *ecc);
+void
+ecc_mul_a (const struct ecc_curve *ecc,
+	   int initial, mp_limb_t *r,
+	   const mp_limb_t *np, const mp_limb_t *p,
+	   mp_limb_t *scratch);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* NETTLE_ECC_H_INCLUDED */
diff --git a/sec-tabselect.c b/sec-tabselect.c
new file mode 100644
index 00000000..f9e3c8c5
--- /dev/null
+++ b/sec-tabselect.c
@@ -0,0 +1,53 @@
+/* sec-tabselect.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"
+
+/* Copy the k'th element of the table out tn elements, each of size
+   rn. Always read complete table. Similar to gmp's mpn_tabselect. */
+/* FIXME: Should we need to volatile declare anything? */
+void
+sec_tabselect (mp_limb_t *rp, mp_size_t rn,
+	       const mp_limb_t *table, unsigned tn,
+	       unsigned k)
+{
+  const mp_limb_t *end = table + tn * rn;
+  const mp_limb_t *p;
+  mp_size_t i;
+  
+  assert (k < tn);
+  mpn_zero (rp, rn);
+  for (p = table; p < end; p += rn, k--)
+    {
+      mp_limb_t mask = - (mp_limb_t) (k == 0);
+      for (i = 0; i < rn; i++)
+	rp[i] += mask & p[i];
+    }
+}
diff --git a/testsuite/.test-rules.make b/testsuite/.test-rules.make
index 0f5cb568..5d877316 100644
--- a/testsuite/.test-rules.make
+++ b/testsuite/.test-rules.make
@@ -169,6 +169,9 @@ ecc-modinv-test$(EXEEXT): ecc-modinv-test.$(OBJEXT)
 ecc-redc-test$(EXEEXT): ecc-redc-test.$(OBJEXT)
 	$(LINK) ecc-redc-test.$(OBJEXT) $(TEST_OBJS) -o ecc-redc-test$(EXEEXT)
 
+ecc-mul-g-test$(EXEEXT): ecc-mul-g-test.$(OBJEXT)
+	$(LINK) ecc-mul-g-test.$(OBJEXT) $(TEST_OBJS) -o ecc-mul-g-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 cdfa766b..32f2e9b4 100644
--- a/testsuite/Makefile.in
+++ b/testsuite/Makefile.in
@@ -35,7 +35,8 @@ TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \
 		     pkcs1-test.c \
 		     rsa-test.c rsa-encrypt-test.c rsa-keygen-test.c \
 		     dsa-test.c dsa-keygen-test.c \
-		     ecc-mod-test.c ecc-modinv-test.c ecc-redc-test.c
+		     ecc-mod-test.c ecc-modinv-test.c ecc-redc-test.c \
+		     ecc-mul-g-test.c
 
 TS_SOURCES = $(TS_NETTLE_SOURCES) $(TS_HOGWEED_SOURCES)
 CXX_SOURCES = cxx-test.cxx
diff --git a/testsuite/ecc-mul-g-test.c b/testsuite/ecc-mul-g-test.c
new file mode 100644
index 00000000..3c2e63ca
--- /dev/null
+++ b/testsuite/ecc-mul-g-test.c
@@ -0,0 +1,58 @@
+#include "testutils.h"
+
+void
+test_main (void)
+{
+  gmp_randstate_t state;
+  mpz_t r;
+  unsigned i;
+
+  gmp_randinit_default (state);
+  mpz_init (r);
+  
+  for (i = 0; ecc_curves[i]; i++)
+    {
+      const struct ecc_curve *ecc = ecc_curves[i];
+      mp_size_t size= ecc_size (ecc);
+      mp_limb_t *p = xalloc_limbs (ecc_size_j (ecc));
+      mp_limb_t *q = xalloc_limbs (ecc_size_j (ecc));
+      mp_limb_t *n = xalloc_limbs (size);
+      mp_limb_t *scratch = xalloc_limbs (ecc_mul_g_itch (ecc));
+      
+      mpn_zero (n, size);
+
+      n[0] = 1;
+      ecc_mul_g (ecc, p, n, scratch);
+      ecc_j_to_a (ecc, 1, p, p, scratch);
+
+      if (mpn_cmp (p, ecc->g, 2*size != 0))
+	{
+	  fprintf (stderr, "ecc_mul_g with n = 1 failed.\n");
+	  abort ();
+	}
+
+      for (n[0] = 2; n[0] <= 4; n[0]++)
+	{
+	  ecc_mul_g (ecc, p, n, scratch);
+	  test_ecc_mul_j (i, n[0], p);
+	}
+
+      /* (order - 1) * g = - g */
+      mpn_sub_1 (n, ecc->q, size, 1);
+      ecc_mul_g (ecc, p, n, scratch);
+      ecc_j_to_a (ecc, 1, p, p, scratch);
+      mpn_sub_n (p + size, ecc->p, p + size, size);
+      if (mpn_cmp (p, ecc->g, 2*size) != 0)
+	{
+	  fprintf (stderr, "ecc_mul_g with n = order - 1 failed.\n");
+	  abort ();
+	}
+
+      free (n);
+      free (p);
+      free (q);
+      free (scratch);
+    }
+  mpz_clear (r); 
+  gmp_randclear (state);
+}
diff --git a/testsuite/testutils.c b/testsuite/testutils.c
index 60614a0e..14d5df29 100644
--- a/testsuite/testutils.c
+++ b/testsuite/testutils.c
@@ -8,6 +8,7 @@
 #include "macros.h"
 #include "nettle-internal.h"
 
+#include <assert.h>
 #include <ctype.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -628,6 +629,12 @@ mpz_togglebit (mpz_t x, unsigned long int bit)
 
 #if WITH_HOGWEED
 
+mp_limb_t *
+xalloc_limbs (mp_size_t n)
+{
+  return xalloc (n * sizeof (mp_limb_t));
+}
+
 #define SIGN(key, hash, msg, signature) do {		\
   hash##_update(&hash, LDATA(msg));		\
   ASSERT(rsa_##hash##_sign(key, &hash, signature));	\
@@ -1095,5 +1102,124 @@ const struct ecc_curve * const ecc_curves[] = {
   NULL
 };
 
+static int
+test_mpn (const char *ref, const mp_limb_t *xp, mp_size_t n)
+{
+  mpz_t r;
+  int res;
+
+  mpz_init_set_str (r, ref, 16);
+  while (n > 0 && xp[n-1] == 0)
+    n--;
+  
+  res = (_mpz_cmp_limbs (r, xp, n) == 0);
+  mpz_clear (r);
+  return res;
+}
+
+struct ecc_ref_point
+{
+  const char *x;
+  const char *y;
+};
+
+static void
+test_ecc_point (const struct ecc_curve *ecc,
+		const struct ecc_ref_point *ref,
+		const mp_limb_t *p)
+{
+  if (! (test_mpn (ref->x, p, ecc->size)
+	 && test_mpn (ref->y, p + ecc->size, ecc->size) ))
+    {
+      gmp_fprintf (stderr, "Incorrect point!\n"
+		   "got: x = %Nx\n"
+		   "     y = %Nx\n"
+		   "ref: x = %s\n"
+		   "     y = %s\n",
+		   p, ecc->size, p + ecc->size, ecc->size,
+		   ref->x, ref->y);
+      abort();
+    }
+}
+
+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[5][3] = {
+    { { "dafebf5828783f2ad35534631588a3f629a70fb16982a888",
+	"dd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab" },
+      { "76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da",
+	"782c37e372ba4520aa62e0fed121d49ef3b543660cfd05fd" },
+      { "35433907297cc378b0015703374729d7a4fe46647084e4ba",
+	"a2649984f2135c301ea3acb0776cd4f125389b311db3be32" }
+    },
+    { { "706a46dc76dcb76798e60e6d89474788d16dc18032d268fd1a704fa6",
+	"1c2b76a7bc25e7702a704fa986892849fca629487acf3709d2e4e8bb" },
+      { "df1b1d66a551d0d31eff822558b9d2cc75c2180279fe0d08fd896d04",
+	"a3f7f03cadd0be444c0aa56830130ddf77d317344e1af3591981a925" },
+      { "ae99feebb5d26945b54892092a8aee02912930fa41cd114e40447301",
+	"482580a0ec5bc47e88bc8c378632cd196cb3fa058a7114eb03054c9" },
+    },
+    { { "7cf27b188d034f7e8a52380304b51ac3c08969e277f21b35a60b48fc47669978",
+	"7775510db8ed040293d9ac69f7430dbba7dade63ce982299e04b79d227873d1" },
+      { "5ecbe4d1a6330a44c8f7ef951d4bf165e6c6b721efada985fb41661bc6e7fd6c",
+	"8734640c4998ff7e374b06ce1a64a2ecd82ab036384fb83d9a79b127a27d5032" },
+      { "e2534a3532d08fbba02dde659ee62bd0031fe2db785596ef509302446b030852",
+	"e0f1575a4c633cc719dfee5fda862d764efc96c3f30ee0055c42c23f184ed8c6" },
+    },
+    { { "8d999057ba3d2d969260045c55b97f089025959a6f434d651d207d19fb96e9e"
+	"4fe0e86ebe0e64f85b96a9c75295df61",
+	"8e80f1fa5b1b3cedb7bfe8dffd6dba74b275d875bc6cc43e904e505f256ab425"
+	"5ffd43e94d39e22d61501e700a940e80" },
+      { "77a41d4606ffa1464793c7e5fdc7d98cb9d3910202dcd06bea4f240d3566da6"
+	"b408bbae5026580d02d7e5c70500c831",
+	"c995f7ca0b0c42837d0bbe9602a9fc998520b41c85115aa5f7684c0edc111eac"
+	"c24abd6be4b5d298b65f28600a2f1df1" },
+      { "138251cd52ac9298c1c8aad977321deb97e709bd0b4ca0aca55dc8ad51dcfc9d"
+	"1589a1597e3a5120e1efd631c63e1835",
+	"cacae29869a62e1631e8a28181ab56616dc45d918abc09f3ab0e63cf792aa4dc"
+	"ed7387be37bba569549f1c02b270ed67" },
+    },
+    { { "43"
+	"3c219024277e7e682fcb288148c282747403279b1ccc06352c6e5505d769be97"
+	"b3b204da6ef55507aa104a3a35c5af41cf2fa364d60fd967f43e3933ba6d783d",
+	"f4"
+	"bb8cc7f86db26700a7f3eceeeed3f0b5c6b5107c4da97740ab21a29906c42dbb"
+	"b3e377de9f251f6b93937fa99a3248f4eafcbe95edc0f4f71be356d661f41b02"
+      },
+      { "1a7"
+	"3d352443de29195dd91d6a64b5959479b52a6e5b123d9ab9e5ad7a112d7a8dd1"
+	"ad3f164a3a4832051da6bd16b59fe21baeb490862c32ea05a5919d2ede37ad7d",
+	"13e"
+	"9b03b97dfa62ddd9979f86c6cab814f2f1557fa82a9d0317d2f8ab1fa355ceec"
+	"2e2dd4cf8dc575b02d5aced1dec3c70cf105c9bc93a590425f588ca1ee86c0e5" },
+      { "35"
+	"b5df64ae2ac204c354b483487c9070cdc61c891c5ff39afc06c5d55541d3ceac"
+	"8659e24afe3d0750e8b88e9f078af066a1d5025b08e5a5e2fbc87412871902f3",
+	"82"
+	"096f84261279d2b673e0178eb0b4abb65521aef6e6e32e1b5ae63fe2f19907f2"
+	"79f283e54ba385405224f750a95b85eebb7faef04699d1d9e21f47fc346e4d0d" },
+    }
+  };
+  assert (curve < 5);
+  assert (n >= 2 && n <= 4);
+  test_ecc_point (ecc_curves[curve], &ref[curve][n-2], p);
+}
+
+void
+test_ecc_mul_j (unsigned curve, unsigned n, const mp_limb_t *p)
+{
+  const struct ecc_curve *ecc = ecc_curves[curve];
+  mp_limb_t *np = xalloc_limbs (ecc_size_a (ecc));
+  mp_limb_t *scratch = xalloc_limbs (ecc_j_to_a_itch(ecc));
+  ecc_j_to_a (ecc, 1, np, p, scratch);
+
+  test_ecc_mul_a (curve, n, np);
+
+  free (np);
+  free (scratch);
+}
+
 #endif /* WITH_HOGWEED */
 
diff --git a/testsuite/testutils.h b/testsuite/testutils.h
index ed57b33e..14aa794d 100644
--- a/testsuite/testutils.h
+++ b/testsuite/testutils.h
@@ -19,6 +19,7 @@
 # include "rsa.h"
 # include "dsa.h"
 # include "ecc-curve.h"
+# include "ecc.h"
 # include "ecc-internal.h"
 # include "gmp-glue.h"
 #endif
@@ -150,6 +151,9 @@ test_armor(const struct nettle_armor *armor,
            const uint8_t *ascii);
 
 #if WITH_HOGWEED
+mp_limb_t *
+xalloc_limbs (mp_size_t n);
+
 void
 test_rsa_set_key_1(struct rsa_public_key *pub,
 		   struct rsa_private_key *key);
@@ -195,6 +199,12 @@ test_dsa_key(struct dsa_public_key *pub,
 
 extern const struct ecc_curve * const ecc_curves[];
 
+void
+test_ecc_mul_a (unsigned curve, unsigned n, const mp_limb_t *p);
+
+void
+test_ecc_mul_j (unsigned curve, unsigned n, const mp_limb_t *p);
+
 #endif /* WITH_HOGWEED */
   
 /* LDATA needs to handle NUL characters. */