New program eccdata, and Makefile rules to use it.

1 files changed, 878 insertions, 0 deletions

diff --git a/eccdata.c b/eccdata.c
new file mode 100644
index 00000000..ea922b5d
--- /dev/null
+++ b/eccdata.c
@@ -0,0 +1,878 @@
+/* eccdata.c */
+
+/* Generate 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. */
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <gmp.h>
+
+/* Affine coordinates, for simplicity. Infinity point represented as x
+   == y == 0. */
+struct ecc_point
+{
+  mpz_t x;
+  mpz_t y;
+};
+
+/* Represents an elliptic curve of the form
+
+     y^2 = x^3 - 3x + b (mod p)
+*/
+struct ecc_curve
+{
+  unsigned bit_size;
+  unsigned pippenger_k;
+  unsigned pippenger_c;
+
+  /* Prime */
+  mpz_t p;
+  mpz_t b;
+
+  /* Curve order */
+  mpz_t q;
+  struct ecc_point g;
+
+  /* Table for pippenger's algorithm.
+     Element
+
+       i 2^c + j_0 + j_1 2 + j_2 2^2 + ... + j_{c-1} 2^{c-1}
+
+     holds
+
+       2^{ikc} ( j_0 + j_1 2^k + j_2 2^{2k} + ... + j_{c-1} 2^{(c-1)k}) g
+   */
+  mp_size_t table_size;
+  struct ecc_point *table;
+
+  /* If non-NULL, holds 2g, 3g, 4g */
+  struct ecc_point *ref;
+};
+
+static void
+ecc_init (struct ecc_point *p)
+{
+  mpz_init (p->x);
+  mpz_init (p->y);
+}
+
+static void
+ecc_clear (struct ecc_point *p)
+{
+  mpz_clear (p->x);
+  mpz_clear (p->y);
+}
+
+static int
+ecc_zero_p (const struct ecc_point *p)
+{
+  return mpz_sgn (p->x) == 0 && mpz_sgn (p->y) == 0;
+}
+
+static int
+ecc_equal_p (const struct ecc_point *p, const struct ecc_point *q)
+{
+  return mpz_cmp (p->x, q->x) == 0 && mpz_cmp (p->y, q->y) == 0;
+}
+
+static void
+ecc_set_zero (struct ecc_point *r)
+{
+  mpz_set_ui (r->x, 0);
+  mpz_set_ui (r->y, 0);
+}
+
+static void
+ecc_set (struct ecc_point *r, const struct ecc_point *p)
+{
+  mpz_set (r->x, p->x);
+  mpz_set (r->y, p->y);
+}
+
+static void
+ecc_dup (const struct ecc_curve *ecc,
+	 struct ecc_point *r, const struct ecc_point *p)
+{
+  if (ecc_zero_p (p))
+    ecc_set_zero (r);
+
+  else
+    {
+      mpz_t m, t, x, y;
+  
+      mpz_init (m);
+      mpz_init (t);
+      mpz_init (x);
+      mpz_init (y);
+
+      /* m = (2 y)^-1 */
+      mpz_mul_ui (m, p->y, 2);
+      mpz_invert (m, m, ecc->p);
+
+      /* t = 3 (x^2 - 1) * m */
+      mpz_mul (t, p->x, p->x);
+      mpz_mod (t, t, ecc->p);
+      mpz_sub_ui (t, t, 1);
+      mpz_mul_ui (t, t, 3);
+      mpz_mul (t, t, m);
+
+      /* x' = t^2 - 2 x */
+      mpz_mul (x, t, t);
+      mpz_submul_ui (x, p->x, 2);
+      mpz_mod (x, x, ecc->p);
+
+      /* y' = (x - x') * t - y */
+      mpz_sub (y, p->x, x);
+      mpz_mul (y, y, t);
+      mpz_sub (y, y, p->y);
+      mpz_mod (y, y, ecc->p);
+
+      mpz_swap (x, r->x);
+      mpz_swap (y, r->y);
+  
+      mpz_clear (m);
+      mpz_clear (t);
+      mpz_clear (x);
+      mpz_clear (y);
+    }
+}
+
+static void
+ecc_add (const struct ecc_curve *ecc,
+	 struct ecc_point *r, const struct ecc_point *p, const struct ecc_point *q)
+{
+  if (ecc_zero_p (p))
+    ecc_set (r, q);
+
+  else if (ecc_zero_p (q))
+    ecc_set (r, p);
+
+  else if (mpz_cmp (p->x, q->x) == 0)
+    {
+      if (mpz_cmp (p->y, q->y) == 0)
+	ecc_dup (ecc, r, p);
+      else
+	ecc_set_zero (r);
+    }
+  else
+    {
+      mpz_t s, t, x, y;
+      mpz_init (s);
+      mpz_init (t);
+      mpz_init (x);
+      mpz_init (y);
+
+      /* t = (q_y - p_y) / (q_x - p_x) */
+      mpz_sub (t, q->x, p->x);
+      mpz_invert (t, t, ecc->p);
+      mpz_sub (s, q->y, p->y);
+      mpz_mul (t, t, s);
+      mpz_mod (t, t, ecc->p);
+
+      /* x' = t^2 - p_x - q_x */
+      mpz_mul (x, t, t);
+      mpz_sub (x, x, p->x);
+      mpz_sub (x, x, q->x);
+      mpz_mod (x, x, ecc->p);
+
+      /* y' = (x - x') * t - y */
+      mpz_sub (y, p->x, x);
+      mpz_mul (y, y, t);
+      mpz_sub (y, y, p->y);
+      mpz_mod (y, y, ecc->p);
+
+      mpz_swap (x, r->x);
+      mpz_swap (y, r->y);
+
+      mpz_clear (s);
+      mpz_clear (t);
+      mpz_clear (x);
+      mpz_clear (y);
+    }
+}
+
+static void 
+ecc_mul_binary (const struct ecc_curve *ecc,
+		struct ecc_point *r, const mpz_t n, const struct ecc_point *p)
+{
+  mp_bitcnt_t k;
+
+  assert (r != p);
+  assert (mpz_sgn (n) > 0);
+
+  ecc_set (r, p);
+
+  /* Index of highest one bit */
+  for (k = mpz_sizeinbase (n, 2) - 1; k-- > 0; )
+    {
+      ecc_dup (ecc, r, r);
+      if (mpz_tstbit (n, k))
+	ecc_add (ecc, r, r, p);
+    }  
+}
+
+static struct ecc_point *
+ecc_alloc (size_t n)
+{
+  struct ecc_point *p = malloc (n * sizeof(*p));
+  size_t i;
+
+  if (!p)
+    {
+      fprintf (stderr, "Virtual memory exhausted.\n");
+      exit (EXIT_FAILURE);
+    }
+  for (i = 0; i < n; i++)
+    ecc_init (&p[i]);
+
+  return p;
+}
+
+static void
+ecc_set_str (struct ecc_point *p,
+	     const char *x, const char *y)
+{
+  mpz_set_str (p->x, x, 16);
+  mpz_set_str (p->y, y, 16);  
+}
+
+static void
+ecc_curve_init_str (struct ecc_curve *ecc,
+		    const char *p, const char *b, const char *q,
+		    const char *gx, const char *gy)
+{
+  mpz_init_set_str (ecc->p, p, 16);
+  mpz_init_set_str (ecc->b, b, 16);
+  mpz_init_set_str (ecc->q, q, 16);
+  ecc_init (&ecc->g);
+  ecc_set_str (&ecc->g, gx, gy);
+
+  ecc->pippenger_k = 0;
+  ecc->pippenger_c = 0;
+  ecc->table = NULL;
+
+  ecc->ref = NULL;
+}
+
+static void
+ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size)
+{
+  switch (bit_size)
+    {
+    case 192:      
+      ecc_curve_init_str (ecc,
+			  /* p = 2^{192} - 2^{64} - 1 */
+			  "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE"
+			  "FFFFFFFFFFFFFFFF",
+
+			  "64210519e59c80e70fa7e9ab72243049"
+			  "feb8deecc146b9b1", 
+
+			  "ffffffffffffffffffffffff99def836"
+			  "146bc9b1b4d22831",
+
+			  "188da80eb03090f67cbf20eb43a18800"
+			  "f4ff0afd82ff1012",
+
+			  "07192b95ffc8da78631011ed6b24cdd5"
+			  "73f977a11e794811");
+      ecc->ref = ecc_alloc (3);
+      ecc_set_str (&ecc->ref[0], /* 2 g */
+		   "dafebf5828783f2ad35534631588a3f629a70fb16982a888",
+		   "dd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab");
+      
+      ecc_set_str (&ecc->ref[1], /* 3 g */
+		   "76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da",
+		   "782c37e372ba4520aa62e0fed121d49ef3b543660cfd05fd");
+
+      ecc_set_str (&ecc->ref[2], /* 4 g */
+		   "35433907297cc378b0015703374729d7a4fe46647084e4ba",
+		   "a2649984f2135c301ea3acb0776cd4f125389b311db3be32");
+
+      break;
+    case 224:
+      ecc_curve_init_str (ecc,
+			  /* p = 2^{224} - 2^{96} + 1 */
+			  "ffffffffffffffffffffffffffffffff"
+			  "000000000000000000000001",
+
+			  "b4050a850c04b3abf54132565044b0b7"
+			  "d7bfd8ba270b39432355ffb4",
+
+			  "ffffffffffffffffffffffffffff16a2"
+			  "e0b8f03e13dd29455c5c2a3d",
+
+			  "b70e0cbd6bb4bf7f321390b94a03c1d3"
+			  "56c21122343280d6115c1d21",
+
+			  "bd376388b5f723fb4c22dfe6cd4375a0"
+			  "5a07476444d5819985007e34");
+
+      ecc->ref = ecc_alloc (3);
+      ecc_set_str (&ecc->ref[0], /* 2 g */
+		   "706a46dc76dcb76798e60e6d89474788d16dc18032d268fd1a704fa6",
+		   "1c2b76a7bc25e7702a704fa986892849fca629487acf3709d2e4e8bb");
+      
+      ecc_set_str (&ecc->ref[1], /* 3 g */
+		   "df1b1d66a551d0d31eff822558b9d2cc75c2180279fe0d08fd896d04",
+		   "a3f7f03cadd0be444c0aa56830130ddf77d317344e1af3591981a925");
+
+      ecc_set_str (&ecc->ref[2], /* 4 g */
+		   "ae99feebb5d26945b54892092a8aee02912930fa41cd114e40447301",
+		   "482580a0ec5bc47e88bc8c378632cd196cb3fa058a7114eb03054c9");
+
+      break;
+    case 256:
+      ecc_curve_init_str (ecc,
+			  /* p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1 */
+			  "FFFFFFFF000000010000000000000000"
+			  "00000000FFFFFFFFFFFFFFFFFFFFFFFF",
+
+			  "5AC635D8AA3A93E7B3EBBD55769886BC"
+			  "651D06B0CC53B0F63BCE3C3E27D2604B",
+
+			  "FFFFFFFF00000000FFFFFFFFFFFFFFFF"
+			  "BCE6FAADA7179E84F3B9CAC2FC632551",
+
+			  "6B17D1F2E12C4247F8BCE6E563A440F2"
+			  "77037D812DEB33A0F4A13945D898C296",
+
+			  "4FE342E2FE1A7F9B8EE7EB4A7C0F9E16"
+			  "2BCE33576B315ECECBB6406837BF51F5");
+
+      ecc->ref = ecc_alloc (3);
+      ecc_set_str (&ecc->ref[0], /* 2 g */
+		   "7cf27b188d034f7e8a52380304b51ac3c08969e277f21b35a60b48fc47669978",
+		   "7775510db8ed040293d9ac69f7430dbba7dade63ce982299e04b79d227873d1");
+      
+      ecc_set_str (&ecc->ref[1], /* 3 g */
+		   "5ecbe4d1a6330a44c8f7ef951d4bf165e6c6b721efada985fb41661bc6e7fd6c",
+		   "8734640c4998ff7e374b06ce1a64a2ecd82ab036384fb83d9a79b127a27d5032");
+
+      ecc_set_str (&ecc->ref[2], /* 4 g */
+		   "e2534a3532d08fbba02dde659ee62bd0031fe2db785596ef509302446b030852",
+		   "e0f1575a4c633cc719dfee5fda862d764efc96c3f30ee0055c42c23f184ed8c6");
+
+      break;
+    case 384:
+      ecc_curve_init_str (ecc,
+			  /* p = 2^{384} - 2^{128} - 2^{96} + 2^{32} - 1 */
+			  "ffffffffffffffffffffffffffffffff"
+			  "fffffffffffffffffffffffffffffffe"
+			  "ffffffff0000000000000000ffffffff",
+			  
+			  "b3312fa7e23ee7e4988e056be3f82d19"
+			  "181d9c6efe8141120314088f5013875a"
+			  "c656398d8a2ed19d2a85c8edd3ec2aef",
+			  
+			  "ffffffffffffffffffffffffffffffff"
+			  "ffffffffffffffffc7634d81f4372ddf"
+			  "581a0db248b0a77aecec196accc52973",
+			  
+			  "aa87ca22be8b05378eb1c71ef320ad74"
+			  "6e1d3b628ba79b9859f741e082542a38"
+			  "5502f25dbf55296c3a545e3872760ab7",
+			  
+			  "3617de4a96262c6f5d9e98bf9292dc29"
+			  "f8f41dbd289a147ce9da3113b5f0b8c0"
+			  "0a60b1ce1d7e819d7a431d7c90ea0e5f");
+
+      ecc->ref = ecc_alloc (3);
+      ecc_set_str (&ecc->ref[0], /* 2 g */
+		   "8d999057ba3d2d969260045c55b97f089025959a6f434d651d207d19fb96e9e4fe0e86ebe0e64f85b96a9c75295df61",
+		   "8e80f1fa5b1b3cedb7bfe8dffd6dba74b275d875bc6cc43e904e505f256ab4255ffd43e94d39e22d61501e700a940e80");
+
+      ecc_set_str (&ecc->ref[1], /* 3 g */
+		   "77a41d4606ffa1464793c7e5fdc7d98cb9d3910202dcd06bea4f240d3566da6b408bbae5026580d02d7e5c70500c831",
+		   "c995f7ca0b0c42837d0bbe9602a9fc998520b41c85115aa5f7684c0edc111eacc24abd6be4b5d298b65f28600a2f1df1");
+
+      ecc_set_str (&ecc->ref[2], /* 4 g */
+		   "138251cd52ac9298c1c8aad977321deb97e709bd0b4ca0aca55dc8ad51dcfc9d1589a1597e3a5120e1efd631c63e1835",
+		   "cacae29869a62e1631e8a28181ab56616dc45d918abc09f3ab0e63cf792aa4dced7387be37bba569549f1c02b270ed67");
+
+      break;
+    case 521:
+      ecc_curve_init_str (ecc,			  
+			  "1ff" /* p = 2^{521} - 1 */
+			  "ffffffffffffffffffffffffffffffff"
+			  "ffffffffffffffffffffffffffffffff"
+			  "ffffffffffffffffffffffffffffffff"
+			  "ffffffffffffffffffffffffffffffff",
+
+			  "051"
+			  "953eb9618e1c9a1f929a21a0b68540ee"
+			  "a2da725b99b315f3b8b489918ef109e1"
+			  "56193951ec7e937b1652c0bd3bb1bf07"
+			  "3573df883d2c34f1ef451fd46b503f00",
+
+			  "1ff"
+			  "ffffffffffffffffffffffffffffffff"
+			  "fffffffffffffffffffffffffffffffa"
+			  "51868783bf2f966b7fcc0148f709a5d0"
+			  "3bb5c9b8899c47aebb6fb71e91386409",
+
+			  "c6"
+			  "858e06b70404e9cd9e3ecb662395b442"
+			  "9c648139053fb521f828af606b4d3dba"
+			  "a14b5e77efe75928fe1dc127a2ffa8de"
+			  "3348b3c1856a429bf97e7e31c2e5bd66",
+
+			  "118"
+			  "39296a789a3bc0045c8a5fb42c7d1bd9"
+			  "98f54449579b446817afbd17273e662c"
+			  "97ee72995ef42640c550b9013fad0761"
+			  "353c7086a272c24088be94769fd16650");
+
+      ecc->ref = ecc_alloc (3);
+      ecc_set_str (&ecc->ref[0], /* 2 g */
+		   "433c219024277e7e682fcb288148c282747403279b1ccc06352c6e5505d769be97b3b204da6ef55507aa104a3a35c5af41cf2fa364d60fd967f43e3933ba6d783d",
+		   "f4bb8cc7f86db26700a7f3eceeeed3f0b5c6b5107c4da97740ab21a29906c42dbbb3e377de9f251f6b93937fa99a3248f4eafcbe95edc0f4f71be356d661f41b02");
+      
+      ecc_set_str (&ecc->ref[1], /* 3 g */
+		   "1a73d352443de29195dd91d6a64b5959479b52a6e5b123d9ab9e5ad7a112d7a8dd1ad3f164a3a4832051da6bd16b59fe21baeb490862c32ea05a5919d2ede37ad7d",
+		   "13e9b03b97dfa62ddd9979f86c6cab814f2f1557fa82a9d0317d2f8ab1fa355ceec2e2dd4cf8dc575b02d5aced1dec3c70cf105c9bc93a590425f588ca1ee86c0e5");
+
+      ecc_set_str (&ecc->ref[2], /* 4 g */
+		   "35b5df64ae2ac204c354b483487c9070cdc61c891c5ff39afc06c5d55541d3ceac8659e24afe3d0750e8b88e9f078af066a1d5025b08e5a5e2fbc87412871902f3",
+		   "82096f84261279d2b673e0178eb0b4abb65521aef6e6e32e1b5ae63fe2f19907f279f283e54ba385405224f750a95b85eebb7faef04699d1d9e21f47fc346e4d0d");
+
+      break;
+    default:
+      fprintf (stderr, "No known curve for size %d\n", bit_size);
+      exit(EXIT_FAILURE);     
+    }
+  ecc->bit_size = bit_size;
+}
+
+static void
+ecc_pippenger_precompute (struct ecc_curve *ecc, unsigned k, unsigned c)
+{
+  unsigned p = (ecc->bit_size + k-1) / k;
+  unsigned M = (p + c-1)/c;
+  unsigned i, j;
+
+  ecc->pippenger_k = k;
+  ecc->pippenger_c = c;
+  ecc->table_size = M << c;
+  ecc->table = ecc_alloc (ecc->table_size);
+  
+  /* Compute the first 2^c entries */
+  ecc_set_zero (&ecc->table[0]);
+  ecc_set (&ecc->table[1], &ecc->g);
+
+  for (j = 2; j < (1U<<c); j <<= 1)
+    {
+      /* T[j] = 2^k T[j/2] */
+      ecc_dup (ecc, &ecc->table[j], &ecc->table[j/2]);
+      for (i = 1; i < k; i++)
+	ecc_dup (ecc, &ecc->table[j], &ecc->table[j]);
+
+      for (i = 1; i < j; i++)
+	ecc_add (ecc, &ecc->table[j + i], &ecc->table[j], &ecc->table[i]);
+    }
+  for (j = 1<<c; j < ecc->table_size; j++)
+    {
+      /* T[j] = 2^{kc} T[j-2^c] */
+      ecc_dup (ecc, &ecc->table[j], &ecc->table[j - (1<<c)]);
+      for (i = 1; i < k*c; i++)
+	ecc_dup (ecc, &ecc->table[j], &ecc->table[j]);
+    }
+}
+
+static void
+ecc_mul_pippenger (const struct ecc_curve *ecc,
+		   struct ecc_point *r, const mpz_t n_input)
+{
+  mpz_t n;
+  unsigned k, c;
+  unsigned i, j;
+  unsigned bit_rows;
+
+  mpz_init (n);
+  
+  mpz_mod (n, n_input, ecc->q);
+  ecc_set_zero (r);
+
+  k = ecc->pippenger_k;
+  c = ecc->pippenger_c;
+
+  bit_rows = (ecc->bit_size + k - 1) / k;
+
+  for (i = k; i-- > 0; )
+    {
+      ecc_dup (ecc, r, r);
+      for (j = 0; j * c < bit_rows; j++)
+	{
+	  unsigned bits;
+	  mp_size_t bit_index;
+	  
+	  /* Extract c bits of the exponent, 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; )
+	    {
+	      bit_index -= k;
+	      bits = (bits << 1) | mpz_tstbit (n, bit_index);
+	    }
+
+	  ecc_add (ecc, r, r, &ecc->table[(j << c) | bits]);
+	}
+    }
+  mpz_clear (n);
+}
+
+#define ASSERT_EQUAL(p, q) do {						\
+    if (!ecc_equal_p (p, q))						\
+      {									\
+	fprintf (stderr, "%s:%d: ASSERT_EQUAL (%s, %s) failed.\n",	\
+		 __FILE__, __LINE__, #p, #q);				\
+	gmp_fprintf (stderr, "p = (%Zx,\n     %Zx)\n", (p)->x, (p)->y); \
+	gmp_fprintf (stderr, "q = (%Zx,\n     %Zx)\n", (q)->x, (q)->y); \
+	abort();							\
+      }									\
+  } while (0)
+
+#define ASSERT_ZERO(p) do {						\
+    if (!ecc_zero_p (p))						\
+      {									\
+	fprintf (stderr, "%s:%d: ASSERT_ZERO (%s) failed.\n",		\
+		 __FILE__, __LINE__, #p);				\
+	gmp_fprintf (stderr, "p = (%Zx,\n     %Zx)\n", (p)->x, (p)->y); \
+	abort();							\
+      }									\
+  } while (0)
+
+static void
+ecc_curve_check (const struct ecc_curve *ecc)
+{
+  struct ecc_point p, q;
+  mpz_t n;
+
+  ecc_init (&p);
+  ecc_init (&q);
+  mpz_init (n);
+
+  ecc_dup (ecc, &p, &ecc->g);
+  if (ecc->ref)
+    ASSERT_EQUAL (&p, &ecc->ref[0]);
+  else
+    gmp_fprintf (stderr, "g2 = %Zx\n     %Zx\n", p.x, p.y);
+
+  ecc_add (ecc, &q, &p, &ecc->g);
+  if (ecc->ref)
+    ASSERT_EQUAL (&q, &ecc->ref[1]);
+  else
+    gmp_fprintf (stderr, "g3 = %Zx\n     %Zx\n", q.x, q.y);
+
+  ecc_add (ecc, &q, &q, &ecc->g);
+  if (ecc->ref)
+    ASSERT_EQUAL (&q, &ecc->ref[2]);
+  else
+    gmp_fprintf (stderr, "g4 = %Zx\n     %Zx\n", q.x, q.y);
+
+  ecc_dup (ecc, &q, &p);
+  if (ecc->ref)
+    ASSERT_EQUAL (&q, &ecc->ref[2]);
+  else
+    gmp_fprintf (stderr, "g4 = %Zx\n     %Zx\n", q.x, q.y);
+
+  ecc_mul_binary (ecc, &p, ecc->q, &ecc->g);
+  ASSERT_ZERO (&p);
+
+  ecc_mul_pippenger (ecc, &q, ecc->q);
+  ASSERT_ZERO (&q);
+
+  ecc_clear (&p);
+  ecc_clear (&q);
+  mpz_clear (n);
+}
+
+static void
+output_digits (const mpz_t x,
+	       unsigned size, unsigned bits_per_limb)
+{  
+  mpz_t t;
+  mpz_t mask;
+  mpz_t limb;
+  unsigned i;
+  const char *suffix;
+
+  mpz_init (t);
+  mpz_init (mask);
+  mpz_init (limb);
+
+  mpz_setbit (mask, bits_per_limb);
+  mpz_sub_ui (mask, mask, 1);
+
+  suffix = bits_per_limb > 32 ? "ULL" : "UL";
+
+  mpz_init_set (t, x);
+
+  for (i = 0; i < size; i++)
+    {
+      if ( (i % 8) == 0)
+	printf("\n ");
+      
+      mpz_and (limb, mask, t);
+      gmp_printf (" 0x%Zx%s,", limb, suffix);
+      mpz_tdiv_q_2exp (t, t, bits_per_limb);
+    }
+
+  mpz_clear (t);
+  mpz_clear (mask);
+  mpz_clear (limb);
+}
+
+static void
+output_bignum (const char *name, const mpz_t x,
+	       unsigned size, unsigned bits_per_limb)
+{  
+  printf ("static const mp_limb_t %s[%d] = {", name, size);
+  output_digits (x, size, bits_per_limb);
+  printf("\n};\n");
+}
+
+static void
+output_point (const char *name, const struct ecc_point *p,
+	      unsigned size, unsigned bits_per_limb)
+{
+  if (name)
+    printf("static const mp_limb_t %s[%u] = {", name, 2*size);
+
+  output_digits (p->x, size, bits_per_limb);
+  output_digits (p->y, size, bits_per_limb);
+
+  if (name)
+    printf("\n};\n");
+}
+
+static void
+output_point_redc (const char *name, const struct ecc_curve *ecc,
+		   const struct ecc_point *p,
+		   unsigned size, unsigned bits_per_limb)
+{
+  mpz_t t;
+  mpz_init (t);
+
+  if (name)
+    printf("static const mp_limb_t %s[%u] = {", name, 2*size);
+    
+  mpz_mul_2exp (t, p->x, size * bits_per_limb);
+  mpz_mod (t, t, ecc->p);
+      
+  output_digits (t, size, bits_per_limb);
+
+  mpz_mul_2exp (t, p->y, size * bits_per_limb);
+  mpz_mod (t, t, ecc->p);
+      
+  output_digits (t, size, bits_per_limb);
+
+  if (name)
+    printf("\n};\n");
+
+  mpz_clear (t);
+}
+
+static unsigned
+output_modulo (const char *name, const mpz_t x,
+	       unsigned size, unsigned bits_per_limb)
+{
+  mpz_t mod;
+  unsigned bits;
+
+  mpz_init (mod);
+
+  mpz_setbit (mod, bits_per_limb * size);
+  mpz_mod (mod, mod, x);
+
+  bits = mpz_sizeinbase (mod, 2);
+  assert (bits <= size * bits_per_limb - 32);
+
+  output_bignum (name, mod, size, bits_per_limb);
+  
+  mpz_clear (mod);
+  return bits;
+}
+
+static void
+output_curve (const struct ecc_curve *ecc, unsigned bits_per_limb)
+{
+  unsigned limb_size = (ecc->bit_size + bits_per_limb - 1)/bits_per_limb;
+  unsigned i;
+  unsigned bits;
+  int redc_limbs;
+  mpz_t t;
+
+  mpz_init (t);
+
+  printf ("/* For NULL. */\n#include <stddef.h>\n");
+
+  printf ("#define ECC_LIMB_SIZE %u\n", limb_size);
+  printf ("#define ECC_PIPPENGER_K %u\n", ecc->pippenger_k);
+  printf ("#define ECC_PIPPENGER_C %u\n", ecc->pippenger_c);
+
+  output_bignum ("ecc_p", ecc->p, limb_size, bits_per_limb);
+  output_bignum ("ecc_b", ecc->b, limb_size, bits_per_limb);
+  output_bignum ("ecc_q", ecc->q, limb_size, bits_per_limb);
+  output_point ("ecc_g", &ecc->g, limb_size, bits_per_limb);
+  output_point_redc ("ecc_redc_g", ecc, &ecc->g, limb_size, bits_per_limb);
+  
+  bits = output_modulo ("ecc_Bmodp", ecc->p, limb_size, bits_per_limb);
+  printf ("#define ECC_BMODP_SIZE %u\n",
+	  (bits + bits_per_limb - 1) / bits_per_limb);
+  bits = output_modulo ("ecc_Bmodq", ecc->q, limb_size, bits_per_limb);
+  printf ("#define ECC_BMODQ_SIZE %u\n",
+	  (bits + bits_per_limb - 1) / bits_per_limb);
+
+  if (ecc->bit_size < limb_size * bits_per_limb)
+    {
+      int shift;
+
+      mpz_set_ui (t, 0);
+      mpz_setbit (t, ecc->bit_size);
+      mpz_sub (t, t, ecc->p);      
+      output_bignum ("ecc_Bmodp_shifted", t, limb_size, bits_per_limb);
+
+      shift = limb_size * bits_per_limb - ecc->bit_size;
+      if (shift > 0)
+	{
+	  /* Check condition for reducing hi limbs. If s is the
+	     normalization shift and n is the bit size (so that s + n
+	     = limb_size * bite_per_limb), then we need
+
+	       (2^n - 1) + (2^s - 1) (2^n - p) < 2p
+
+	     or equivalently,
+
+	       2^s (2^n - p) <= p
+
+	     To a allow a carry limb to be added in at the same time,
+	     substitute s+1 for s.
+	  */
+	  /* FIXME: For ecdsa verify, we actually need the stricter
+	     inequality < 2 q. */
+	  mpz_mul_2exp (t, t, shift + 1);
+	  if (mpz_cmp (t, ecc->p) > 0)
+	    {
+	      fprintf (stderr, "Reduction condition failed for %u-bit curve.\n",
+		       ecc->bit_size);
+	      exit (EXIT_FAILURE);
+	    }
+	}
+      mpz_set_ui (t, 0);
+      mpz_setbit (t, ecc->bit_size);
+      mpz_sub (t, t, ecc->q);      
+      output_bignum ("ecc_Bmodq_shifted", t, limb_size, bits_per_limb);      
+    }
+  else
+    {
+      printf ("#define ecc_Bmodp_shifted ecc_Bmodp\n");
+      printf ("#define ecc_Bmodq_shifted ecc_Bmodq\n");
+    }
+
+  mpz_add_ui (t, ecc->p, 1);
+  mpz_fdiv_q_2exp (t, t, 1);
+  output_bignum ("ecc_pp1h", t, limb_size, bits_per_limb);      
+
+  mpz_add_ui (t, ecc->q, 1);
+  mpz_fdiv_q_2exp (t, t, 1);
+  output_bignum ("ecc_qp1h", t, limb_size, bits_per_limb);  
+  
+  /* Trailing zeros in p+1 correspond to trailing ones in p. */
+  redc_limbs = mpz_scan0 (ecc->p, 0) / bits_per_limb;
+  if (redc_limbs > 0)
+    {
+      mpz_add_ui (t, ecc->p, 1);
+      mpz_fdiv_q_2exp (t, t, redc_limbs * bits_per_limb);
+      output_bignum ("ecc_redc_ppm1", t, limb_size - redc_limbs, bits_per_limb);
+    }
+  else
+    {    
+      /* Trailing zeros in p-1 correspond to zeros just above the low
+	 bit of p */
+      redc_limbs = mpz_scan1 (ecc->p, 1) / bits_per_limb;
+      if (redc_limbs > 0)
+	{
+	  printf ("#define ecc_redc_ppm1 (ecc_p + %d)\n",
+		  redc_limbs);
+	  redc_limbs = -redc_limbs;
+	}
+      else
+	printf ("#define ecc_redc_ppm1 NULL\n");
+    }
+  printf ("#define ECC_REDC_SIZE %d\n", redc_limbs);
+
+  printf ("#if USE_REDC\n");
+  printf ("#define ecc_unit ecc_Bmodp\n");
+
+  printf ("static const mp_limb_t ecc_table[%lu] = {",
+	 (unsigned long) (2*ecc->table_size * limb_size));
+  for (i = 0; i < ecc->table_size; i++)
+    output_point_redc (NULL, ecc, &ecc->table[i], limb_size, bits_per_limb);
+
+  printf("\n};\n");
+
+  printf ("#else\n");
+
+  mpz_init_set_ui (t, 1);
+  output_bignum ("ecc_unit", t, limb_size, bits_per_limb);
+  
+  printf ("static const mp_limb_t ecc_table[%lu] = {",
+	 (unsigned long) (2*ecc->table_size * limb_size));
+  for (i = 0; i < ecc->table_size; i++)
+    output_point (NULL, &ecc->table[i], limb_size, bits_per_limb);
+
+  printf("\n};\n");
+  printf ("#endif\n");
+  
+  mpz_clear (t);
+}
+
+int
+main (int argc, char **argv)
+{
+  struct ecc_curve ecc;
+
+  if (argc < 4)
+    {
+      fprintf (stderr, "Usage: %s CURVE-BITS K C [BITS-PER-LIMB]\n", argv[0]);
+      return EXIT_FAILURE;
+    }
+
+  ecc_curve_init (&ecc, atoi(argv[1]));
+
+  ecc_pippenger_precompute (&ecc, atoi(argv[2]), atoi(argv[3]));
+
+  fprintf (stderr, "Table size: %lu entries\n",
+	   (unsigned long) ecc.table_size);
+
+  ecc_curve_check (&ecc);
+
+  if (argc > 4)
+    output_curve (&ecc, atoi(argv[4]));
+
+  return EXIT_SUCCESS;
+}