Implemented ecc_mul_g_eh. Untested.

5 files changed, 126 insertions, 0 deletions

diff --git a/ChangeLog b/ChangeLog
index 0f159f44..b3d42e12 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2014-07-18  Niels Möller  <nisse@lysator.liu.se>
+
+	* ecc-mul-g-eh.c (ecc_mul_g_eh, ecc_mul_g_eh_itch): New file and
+	functions. Untested.
+	* ecc.h (ecc_mul_g_eh_itch): Declare new functions.
+	* ecc-internal.h (ECC_MUL_G_EH_ITCH): New macro.
+	* Makefile.in (hogweed_SOURCES): Added ecc-mul-g-eh.c.
+
 2014-07-17  Niels Möller  <nisse@lysator.liu.se>
 
 	* ecc-add-eh.c (ecc_add_eh): Reduce scratch need.
diff --git a/Makefile.in b/Makefile.in
index 9a91aec3..bcabbf44 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -168,6 +168,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \
 		  ecc-size.c ecc-j-to-a.c ecc-a-to-j.c \
 		  ecc-dup-jj.c ecc-add-jja.c ecc-add-jjj.c \
 		  ecc-dup-eh.c ecc-add-eh.c ecc-add-ehh.c ecc-eh-to-a.c \
+		  ecc-mul-g-eh.c \
 		  ecc-mul-g.c ecc-mul-a.c ecc-hash.c ecc-random.c \
 		  ecc-point.c ecc-scalar.c ecc-point-mul.c ecc-point-mul-g.c \
 		  ecc-ecdsa-sign.c ecdsa-sign.c \
diff --git a/ecc-internal.h b/ecc-internal.h
index 78d05302..c0272b91 100644
--- a/ecc-internal.h
+++ b/ecc-internal.h
@@ -245,6 +245,7 @@ sec_modinv (mp_limb_t *vp, mp_limb_t *ap, mp_size_t n,
 #define ECC_ADD_EH_ITCH(size) (6*(size))
 #define ECC_ADD_EHH_ITCH(size) (9*(size))
 #define ECC_MUL_G_ITCH(size) (9*(size))
+#define ECC_MUL_G_EH_ITCH(size) (9*(size))
 #if ECC_MUL_A_WBITS == 0
 #define ECC_MUL_A_ITCH(size) (12*(size))
 #else
diff --git a/ecc-mul-g-eh.c b/ecc-mul-g-eh.c
new file mode 100644
index 00000000..4242479c
--- /dev/null
+++ b/ecc-mul-g-eh.c
@@ -0,0 +1,108 @@
+/* ecc-mul-g-eh.c
+
+   Copyright (C) 2013, 2014 Niels Möller
+
+   This file is part of GNU Nettle.
+
+   GNU Nettle is free software: you can redistribute it and/or
+   modify it under the terms of either:
+
+     * the GNU Lesser General Public License as published by the Free
+       Software Foundation; either version 3 of the License, or (at your
+       option) any later version.
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at your
+       option) any later version.
+
+   or both in parallel, as here.
+
+   GNU Nettle is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see http://www.gnu.org/licenses/.
+*/
+
+/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "ecc.h"
+#include "ecc-internal.h"
+
+mp_size_t
+ecc_mul_g_eh_itch (const struct ecc_curve *ecc)
+{
+  /* Needs 3*ecc->size + scratch for ecc_add_jja. */
+  return ECC_MUL_G_EH_ITCH (ecc->size);
+}
+
+void
+ecc_mul_g_eh (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_eh 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;
+
+  k = ecc->pippenger_k;
+  c = ecc->pippenger_c;
+
+  bit_rows = (ecc->bit_size + k - 1) / k;
+
+  /* x = 0, y = 1, z = 1 */
+  mpn_zero (r, 3*ecc->size);
+  r[ecc->size] = r[2*ecc->size] = 1;
+
+  for (i = k; i-- > 0; )
+    {
+      ecc_dup_eh (ecc, r, r, scratch);
+      for (j = 0; j * c < bit_rows; j++)
+	{
+	  unsigned bits;
+	  /* Avoid the mp_bitcnt_t type for compatibility with older GMP
+	     versions. */
+	  unsigned 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);
+
+	  ecc_add_eh (ecc, r, r, tp, scratch_out);
+	}
+    }
+#undef tp
+#undef scratch_out
+}
diff --git a/ecc.h b/ecc.h
index df9013aa..e786da53 100644
--- a/ecc.h
+++ b/ecc.h
@@ -79,6 +79,8 @@ extern "C" {
 #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
+#define ecc_mul_g_eh_itch nettle_ecc_mul_g_eh_itch
+#define ecc_mul_g_eh nettle_ecc_mul_g_eh
 
 struct ecc_curve;
 
@@ -284,6 +286,12 @@ ecc_mul_a (const struct ecc_curve *ecc,
 	   const mp_limb_t *np, const mp_limb_t *p,
 	   mp_limb_t *scratch);
 
+mp_size_t
+ecc_mul_g_eh_itch (const struct ecc_curve *ecc);
+void
+ecc_mul_g_eh (const struct ecc_curve *ecc, mp_limb_t *r,
+	      const mp_limb_t *np, mp_limb_t *scratch);
+
 #ifdef __cplusplus
 }
 #endif