Integrated ECDSA sign and verify functions.

13 files changed, 874 insertions, 7 deletions

diff --git a/ChangeLog b/ChangeLog
index e58e810d..aaa189c9 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,20 @@
 2013-02-18  Niels Möller  <nisse@lysator.liu.se>
 
+	* ecc-point.c: New file, struct ecc_point abstraction.
+	* ecc-scalar.c: New file, struct ecc_scalar abstraction.
+	* ecc-random.c (ecc_modq_random, ecc_scalar_random): New file, new
+	functions.
+	* ecc-hash.c (ecc_hash): New file and function.
+	* ecc-ecdsa-sign.c: New file, low-level signing interface.
+	* ecc-ecdsa-verify.c: New file, low-level ecdsa verify.
+	* ecdsa-sign.c: (ecdsa_sign): New file and function.
+	* ecdsa-verify.c (ecdsa_verify): New file and function.
+	* ecdsa.h: New header file.
+	* ecc.h: Declare ecc_point and ecc_scalar functions.
+	* ecc-internal.h: Added declarations.
+	* Makefile.in (hogweed_SOURCES): Added new source files.
+	(HEADERS): Added ecdsa.h.
+
 	* gmp-glue.c (_mpz_set_mpn): New convenience function.
 	(_mpn_set_base256): New function.
 	(_gmp_alloc_limbs): New function.
diff --git a/Makefile.in b/Makefile.in
index c9fe3f12..958278df 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -130,12 +130,15 @@ hogweed_SOURCES = sexp.c sexp-format.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-a-to-j.c \
 		  ecc-dup-jj.c ecc-add-jja.c ecc-add-jjj.c \
-		  ecc-mul-g.c ecc-mul-a.c
+		  ecc-mul-g.c ecc-mul-a.c ecc-hash.c ecc-random.c \
+		  ecc-point.c ecc-scalar.c \
+		  ecc-ecdsa-sign.c ecdsa-sign.c \
+		  ecc-ecdsa-verify.c ecdsa-verify.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 ecc.h \
+	  des.h des-compat.h dsa.h ecc-curve.h ecc.h ecdsa.h \
 	  gcm.h gosthash94.h hmac.h \
 	  knuth-lfib.h \
 	  macros.h \
diff --git a/ecc-ecdsa-sign.c b/ecc-ecdsa-sign.c
new file mode 100644
index 00000000..e85c325c
--- /dev/null
+++ b/ecc-ecdsa-sign.c
@@ -0,0 +1,97 @@
+/* ecc-ecdsa-sign.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 <stdlib.h>
+
+#include "ecdsa.h"
+#include "ecc-internal.h"
+
+/* Low-level ECDSA signing */
+
+mp_size_t
+ecc_ecdsa_sign_itch (const struct ecc_curve *ecc)
+{
+  /* Needs 3*ecc->size + scratch for ecc_mul_g. */
+  return ECC_ECDSA_SIGN_ITCH (ecc->size);
+}
+
+/* NOTE: Caller should check if r or s is zero. */
+void
+ecc_ecdsa_sign (const struct ecc_curve *ecc,
+		const mp_limb_t *zp,
+		/* Random nonce, must be invertible mod ecc group
+		   order. */
+		const mp_limb_t *kp,
+		unsigned length, const uint8_t *digest,
+		mp_limb_t *rp, mp_limb_t *sp,
+		mp_limb_t *scratch)
+{
+  mp_limb_t cy;
+#define P	    scratch
+#define kinv	    scratch                /* Needs 5*ecc->size for computation */
+#define hp	    (scratch  + ecc->size) /* NOTE: ecc->size + 1 limbs! */
+#define tp	    (scratch + 2*ecc->size)
+  /* Procedure, according to RFC 6090, "KT-I". q denotes the group
+     order.
+
+     1. k <-- uniformly random, 0 < k < q
+
+     2. R <-- (r_x, r_y) = k g
+
+     3. s1 <-- r_x mod q
+
+     4. s2 <-- (h + z*s1)/k mod q.
+  */
+
+  ecc_mul_g (ecc, P, kp, P + 3*ecc->size);
+  /* x coordinate only */
+  ecc_j_to_a (ecc, 3, rp, P, P + 3*ecc->size);
+
+  /* We need to reduce x coordinate mod ecc->q. It should already
+     be < 2*ecc->q, so one subtraction should suffice. */
+  cy = mpn_sub_n (scratch, rp, ecc->q, ecc->size);
+  cnd_copy (cy == 0, rp, scratch, ecc->size);
+
+  /* Invert k, uses 5 * ecc->size including scratch */
+  mpn_copyi (hp, kp, ecc->size);
+  ecc_modq_inv (ecc, kinv, hp, tp);
+  
+  /* Process hash digest */
+  ecc_hash (ecc, hp, length, digest);
+
+  ecc_modq_mul (ecc, tp, zp, rp);
+  ecc_modq_add (ecc, hp, hp, tp);
+  ecc_modq_mul (ecc, tp, hp, kinv);
+
+  mpn_copyi (sp, tp, ecc->size);
+#undef P
+#undef hp
+#undef kinv
+#undef tp
+}
diff --git a/ecc-ecdsa-verify.c b/ecc-ecdsa-verify.c
new file mode 100644
index 00000000..57bbb9b3
--- /dev/null
+++ b/ecc-ecdsa-verify.c
@@ -0,0 +1,150 @@
+/* ecc-ecdsa-verify.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 <stdlib.h>
+
+#include "ecdsa.h"
+#include "ecc-internal.h"
+
+/* Low-level ECDSA verify */
+
+static int
+zero_p (const mp_limb_t *xp, mp_size_t n)
+{
+  while (n > 0)
+    if (xp[--n] > 0)
+      return 0;
+  return 1;
+}
+
+static int
+ecdsa_in_range (const struct ecc_curve *ecc, const mp_limb_t *xp)
+{
+  return !zero_p (xp, ecc->size)
+    && mpn_cmp (xp, ecc->q, ecc->size) < 0;
+}
+
+mp_size_t
+ecc_ecdsa_verify_itch (const struct ecc_curve *ecc)
+{
+  /* Largest storage need is for the ecc_mul_a call, 6 * ecc->size +
+     ECC_MUL_A_ITCH (size) */
+  return ECC_ECDSA_VERIFY_ITCH (ecc->size);
+}
+
+/* FIXME: Use faster primitives, not requiring side-channel silence. */
+int
+ecc_ecdsa_verify (const struct ecc_curve *ecc,
+		  const mp_limb_t *pp, /* Public key */
+		  unsigned length, const uint8_t *digest,
+		  const mp_limb_t *rp, const mp_limb_t *sp,
+		  mp_limb_t *scratch)
+{
+  /* Procedure, according to RFC 6090, "KT-I". q denotes the group
+     order.
+
+     1. Check 0 < r, s < q.
+
+     2. s' <-- s^{-1}  (mod q)
+
+     3. u1  <-- h * s' (mod q)
+
+     4. u2  <-- r * s' (mod q)
+
+     5. R = u1 G + u2 Y
+
+     6. Signature is valid if R_x = r (mod q).
+  */
+
+#define P2 scratch
+#define P1 (scratch + 3*ecc->size)
+#define sinv (scratch + 3*ecc->size)
+#define u2 (scratch + 4*ecc->size)
+#define hp (scratch + 4*ecc->size)
+#define u1 (scratch + 6*ecc->size)
+
+  if (! (ecdsa_in_range (ecc, rp)
+	 && ecdsa_in_range (ecc, sp)))
+    return 0;
+
+  /* FIXME: Micro optimizations: Either simultaneous multiplication.
+     Or convert to projective coordinates (can be done without
+     division, I think), and write an ecc_add_ppp. */
+  
+  /* Compute sinv, use P2 as scratch */
+  mpn_copyi (sinv + ecc->size, sp, ecc->size);
+  ecc_modq_inv (ecc, sinv, sinv + ecc->size, P2);
+
+  /* u2 = r / s, P2 = u2 * Y */
+  ecc_modq_mul (ecc, u2, rp, sinv);
+
+   /* Total storage: 5*ecc->size + ECC_MUL_A_ITCH (ecc->size) */
+  ecc_mul_a (ecc, 1, P2, u2, pp, u2 + ecc->size);
+
+  /* u1 = h / s, P1 = u1 * G */
+  ecc_hash (ecc, hp, length, digest);
+  ecc_modq_mul (ecc, u1, hp, sinv);
+
+  /* u = 0 can happen only if h = 0 or h = q, which is extremely
+     unlikely. */
+  if (!zero_p (u1, ecc->size))
+    {
+      /* Total storage: 6*ecc->size + ECC_MUL_G_ITCH (ecc->size) */
+      ecc_mul_g (ecc, P1, u1, u1 + ecc->size);
+
+      /* NOTE: ecc_add_jjj and/or ecc_j_to_a will produce garbage in
+	 case u1 G = +/- u2 V. However, anyone who gets his or her
+	 hands on a signature where this happens during verification,
+	 can also get the private key as z = +/- u1 / u_2 (mod q). And
+	 then it doesn't matter very much if verification of
+	 signatures with that key succeeds or fails.
+
+	 u1 G = - u2 V can never happen for a correctly generated
+	 signature, since it implies k = 0.
+
+	 u1 G = u2 V is possible, if we are unlucky enough to get h /
+	 s_1 = z. Hitting that is about as unlikely as finding the
+	 private key by guessing.
+       */
+      /* Total storage: 6*ecc->size + ECC_ADD_JJJ_ITCH (ecc->size) */
+      ecc_add_jjj (ecc, P1, P1, P2, u1);
+    }
+  ecc_j_to_a (ecc, 3, P2, P1, u1);
+
+  if (mpn_cmp (P2, ecc->q, ecc->size) >= 0)
+    mpn_sub_n (P2, P2, ecc->q, ecc->size);
+
+  return (mpn_cmp (rp, P2, ecc->size) == 0);
+#undef P2
+#undef P1
+#undef sinv
+#undef u2
+#undef hp
+#undef u1
+}
diff --git a/ecc-hash.c b/ecc-hash.c
new file mode 100644
index 00000000..0de3c187
--- /dev/null
+++ b/ecc-hash.c
@@ -0,0 +1,55 @@
+/* ecdsa-hash.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"
+#include "gmp-glue.h"
+
+/* Convert hash value to an integer. If the digest is larger than
+   the ecc bit size, then we must truncate it and use the leftmost
+   bits. */
+
+/* NOTE: We don't considered the hash value to be secret, so it's ok
+   if the running time of this conversion depends on h.
+
+   Requires ecc->size + 1 limbs, the extra limb may be needed for
+   unusual limb sizes.
+*/
+void
+ecc_hash (const struct ecc_curve *ecc,
+	  mp_limb_t *hp,
+	  unsigned length, const uint8_t *digest)
+{
+  if (length > ((unsigned) ecc->bit_size + 7) / 8)
+    length = (ecc->bit_size + 7) / 8;
+
+  _mpn_set_base256 (hp, ecc->size + 1, digest, length);
+
+  if (8 * length > ecc->bit_size)
+    /* We got a few extra bits, at the low end. Discard them. */
+    mpn_rshift (hp, hp, ecc->size + 1, 8*length - ecc->bit_size);
+}
diff --git a/ecc-internal.h b/ecc-internal.h
index a6b3fae4..0df8c9e1 100644
--- a/ecc-internal.h
+++ b/ecc-internal.h
@@ -27,6 +27,7 @@
 
 #include <gmp.h>
 
+#include "nettle-types.h"
 #include "ecc-curve.h"
 
 /* Name mangling */
@@ -45,13 +46,17 @@
 #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 ecc_modq_random _nettle_ecc_modq_random
+#define ecc_mod _nettle_ecc_mod
+#define ecc_hash _nettle_ecc_hash
 #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
 
+#define ECC_MAX_SIZE ((521 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS)
+
 /* Window size for ecc_mul_a. Using 4 bits seems like a good choice,
    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
@@ -185,10 +190,19 @@ ecc_modq_inv (const struct ecc_curve *ecc, mp_limb_t *rp, mp_limb_t *ap,
 	      mp_limb_t *scratch);
 
 void
+ecc_modq_random (const struct ecc_curve *ecc, mp_limb_t *xp,
+		 void *ctx, nettle_random_func *random, 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);
 
+void
+ecc_hash (const struct ecc_curve *ecc,
+	  mp_limb_t *hp,
+	  unsigned length, const uint8_t *digest);
+
 #define cnd_add_n(cnd, rp, ap, n)		\
   mpn_addmul_1 ((rp), (ap), (n), (cnd) != 0)
 
@@ -228,8 +242,10 @@ sec_modinv (mp_limb_t *vp, mp_limb_t *ap, mp_size_t n,
 #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) \
+#define ECC_ECDSA_SIGN_ITCH(size) (12*(size))
+#define ECC_ECDSA_VERIFY_ITCH(size) \
   (6*(size) + ECC_MUL_A_ITCH ((size)))
+#define ECC_MODQ_RANDOM_ITCH(size) (size)
+#define ECC_HASH_ITCH(size) (1+(size))
 
 #endif /* NETTLE_ECC_INTERNAL_H_INCLUDED */
diff --git a/ecc-point.c b/ecc-point.c
new file mode 100644
index 00000000..b26c192e
--- /dev/null
+++ b/ecc-point.c
@@ -0,0 +1,90 @@
+/* ecc-point.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"
+#include "gmp-glue.h"
+
+void
+ecc_point_init (struct ecc_point *p, const struct ecc_curve *ecc)
+{
+  p->ecc = ecc;
+  p->p = _gmp_alloc_limbs (2*ecc->size);
+}
+
+void
+ecc_point_clear (struct ecc_point *p)
+{
+  _gmp_free_limbs (p->p, 2*p->ecc->size);
+}
+
+int
+ecc_point_set (struct ecc_point *p, const mpz_t x, const mpz_t y)
+{
+  mp_size_t size;  
+  mpz_t lhs, rhs;
+  mpz_t t;
+  int res;
+
+  size = p->ecc->size;
+  
+  if (mpz_sgn (x) < 0 || _mpz_cmp_limbs (x, p->ecc->p, size) >= 0
+      || mpz_sgn (y) < 0 || _mpz_cmp_limbs (y, p->ecc->p, size) >= 0)
+    return 0;
+
+  mpz_init (lhs);
+  mpz_init (rhs);
+
+  /* Check that y^2 = x^3 - 3*x + b (mod p) */
+  mpz_mul (lhs, y, y);
+  mpz_mul (rhs, x, x);
+  mpz_sub_ui (rhs, rhs, 3);
+  mpz_mul (rhs, rhs, x);
+  mpz_add (rhs, rhs, _mpz_init_mpn (t, p->ecc->b, size));
+
+  res = mpz_congruent_p (lhs, rhs, _mpz_init_mpn (t, p->ecc->p, size));
+
+  mpz_clear (lhs);
+  mpz_clear (rhs);
+
+  if (!res)
+    return 0;
+
+  _mpz_copy_limbs (p->p, x, size);
+  _mpz_copy_limbs (p->p + size, y, size);
+
+  return 1;
+}
+
+void
+ecc_point_get (const struct ecc_point *p, mpz_t x, mpz_t y)
+{
+  mp_size_t size = p->ecc->size;
+  _mpz_set_mpn (x, p->p, size);
+  _mpz_set_mpn (y, p->p + size, size);
+}
diff --git a/ecc-random.c b/ecc-random.c
new file mode 100644
index 00000000..acffb573
--- /dev/null
+++ b/ecc-random.c
@@ -0,0 +1,90 @@
+/* ecc-random.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"
+#include "gmp-glue.h"
+#include "nettle-internal.h"
+
+static int
+zero_p (const struct ecc_curve *ecc,
+	const mp_limb_t *xp)
+{
+  mp_limb_t t;
+  mp_size_t i;
+
+  for (i = t = 0; i < ecc->size; i++)
+    t |= xp[i];
+
+  return t == 0;
+}
+
+static int
+ecdsa_in_range (const struct ecc_curve *ecc,
+		const mp_limb_t *xp, mp_limb_t *scratch)
+{
+  /* Check if 0 < x < q, with data independent timing. */
+  return !zero_p (ecc, xp)
+    & (mpn_sub_n (scratch, xp, ecc->q, ecc->size) != 0);
+}
+
+void
+ecc_modq_random (const struct ecc_curve *ecc, mp_limb_t *xp,
+		 void *ctx, nettle_random_func *random, mp_limb_t *scratch)
+{
+  uint8_t *buf = (uint8_t *) scratch;
+  unsigned nbytes = (ecc->bit_size + 7)/8;
+
+  /* The bytes ought to fit in the scratch area, unless we have very
+     unusual limb and byte sizes. */
+  assert (nbytes <= ecc->size * sizeof (mp_limb_t));
+
+  do
+    {
+      /* q and p are of the same bitsize. */
+      random (ctx, nbytes, buf);
+      buf[0] &= 0xff >> (nbytes * 8 - ecc->bit_size);
+
+      _mpn_set_base256 (xp, ecc->size, buf, nbytes);
+    }
+  while (!ecdsa_in_range (ecc, xp, scratch));
+}
+
+void
+ecc_scalar_random (struct ecc_scalar *x,
+		   void *random_ctx, nettle_random_func *random)
+{
+  TMP_DECL (scratch, mp_limb_t, ECC_MODQ_RANDOM_ITCH (ECC_MAX_SIZE));
+  TMP_ALLOC (scratch, ECC_MODQ_RANDOM_ITCH (x->ecc->size));
+
+  ecc_modq_random (x->ecc, x->p, random_ctx, random, scratch);
+}
+
+
diff --git a/ecc-scalar.c b/ecc-scalar.c
new file mode 100644
index 00000000..b4c98fde
--- /dev/null
+++ b/ecc-scalar.c
@@ -0,0 +1,62 @@
+/* ecc-scalar.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"
+#include "gmp-glue.h"
+
+void
+ecc_scalar_init (struct ecc_scalar *s, const struct ecc_curve *ecc)
+{
+  s->ecc = ecc;
+  s->p = _gmp_alloc_limbs (ecc->size);
+}
+
+void
+ecc_scalar_clear (struct ecc_scalar *s)
+{
+  _gmp_free_limbs (s->p, s->ecc->size);
+}
+
+int
+ecc_scalar_set (struct ecc_scalar *s, const mpz_t z)
+{
+  mp_size_t size = s->ecc->size;
+
+  if (mpz_sgn (z) <= 0 || _mpz_cmp_limbs (z, s->ecc->q, size) >= 0)
+    return 0;
+
+  _mpz_copy_limbs (s->p, z, size);
+  return 1;
+}
+
+void
+ecc_scalar_get (const struct ecc_scalar *s, mpz_t z)
+{
+  _mpz_set_mpn (z, s->p, s->ecc->size);  
+}
diff --git a/ecc.h b/ecc.h
index c65a23ba..af6c23d6 100644
--- a/ecc.h
+++ b/ecc.h
@@ -25,15 +25,25 @@
 #ifndef NETTLE_ECC_H_INCLUDED
 #define NETTLE_ECC_H_INCLUDED
 
-#include <stdint.h>
-
 #include <gmp.h>
 
+#include "nettle-types.h"
+
 #ifdef __cplusplus
 extern "C" {
 #endif
 
 /* Name mangling */
+#define ecc_point_init nettle_ecc_point_init
+#define ecc_point_clear nettle_ecc_point_clear
+#define ecc_point_set nettle_ecc_point_set
+#define ecc_point_get nettle_ecc_point_get
+#define ecc_scalar_init nettle_ecc_scalar_init
+#define ecc_scalar_clear nettle_ecc_scalar_clear
+#define ecc_scalar_set nettle_ecc_scalar_set
+#define ecc_scalar_get nettle_ecc_scalar_get
+#define ecc_scalar_random nettle_ecc_scalar_random
+#define ecc_point_mul nettle_ecc_point_mul
 #define ecc_size nettle_ecc_size
 #define ecc_size_a nettle_ecc_size_a
 #define ecc_size_j nettle_ecc_size_j
@@ -57,6 +67,60 @@ extern "C" {
 
 struct ecc_curve;
 
+/* High level interface, for ECDSA, DH, etc */
+
+/* Represents a point on the ECC curve */
+struct ecc_point
+{
+  const struct ecc_curve *ecc;
+  /* Allocated using the same allocation function as GMP. */
+  mp_limb_t *p;
+};
+
+/* Represents a non-zero scalar, an element of Z_q^*, where q is the
+   group order of the curve. */
+struct ecc_scalar
+{
+  const struct ecc_curve *ecc;
+  /* Allocated using the same allocation function as GMP. */
+  mp_limb_t *p;
+};
+
+void
+ecc_point_init (struct ecc_point *p, const struct ecc_curve *ecc);
+void
+ecc_point_clear (struct ecc_point *p);
+
+/* Fails and returns zero if the point is not on the curve. */
+int
+ecc_point_set (struct ecc_point *p, const mpz_t x, const mpz_t y);
+void
+ecc_point_get (const struct ecc_point *p, mpz_t x, mpz_t y);
+
+void
+ecc_scalar_init (struct ecc_scalar *s, const struct ecc_curve *ecc);
+void
+ecc_scalar_clear (struct ecc_scalar *s);
+
+/* Fails and returns zero if the scalar is not in the proper range. */
+int
+ecc_scalar_set (struct ecc_scalar *s, const mpz_t z);
+void
+ecc_scalar_get (const struct ecc_scalar *s, mpz_t z);
+/* Generates a random scalar, suitable as an ECDSA private key or a
+   ECDH exponent. */
+void
+ecc_scalar_random (struct ecc_scalar *s,
+		   void *random_ctx, nettle_random_func *random);
+
+/* Computes r = n p */
+void
+ecc_point_mul (struct ecc_point *r, const struct ecc_scalar *n,
+	       const struct ecc_point *p);
+
+
+/* Low-level interface */
+  
 /* 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,
diff --git a/ecdsa-sign.c b/ecdsa-sign.c
new file mode 100644
index 00000000..725c39a2
--- /dev/null
+++ b/ecdsa-sign.c
@@ -0,0 +1,63 @@
+/* ecdsa-sign.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 <stdlib.h>
+
+#include "ecdsa.h"
+#include "ecc-internal.h"
+#include "gmp-glue.h"
+#include "nettle-internal.h"
+
+void
+ecdsa_sign (const struct ecc_scalar *key,
+	    void *random_ctx, nettle_random_func *random,
+	    unsigned digest_length,
+	    const uint8_t *digest,
+	    struct dsa_signature *signature)
+{
+  /* At most 936 bytes. */
+  TMP_DECL(k, mp_limb_t, ECC_MAX_SIZE + ECC_ECDSA_SIGN_ITCH (ECC_MAX_SIZE));
+  mp_limb_t size = key->ecc->size;
+  mp_limb_t *rp = _mpz_write_limbs (signature->r, size);
+  mp_limb_t *sp = _mpz_write_limbs (signature->s, size);
+
+  TMP_ALLOC (k, size + ECC_ECDSA_SIGN_ITCH (size));
+
+  /* Timing reveals the number of rounds through this loop, but the
+     timing is still independent of the secret k finally used. */
+  do
+    {
+      ecc_modq_random (key->ecc, k, random_ctx, random, k + size);
+      ecc_ecdsa_sign (key->ecc, key->p, k, digest_length, digest,
+		   rp, sp, k + size);
+      _mpz_done_limbs (signature->r, size);
+      _mpz_done_limbs (signature->s, size);
+    }
+  while (mpz_sgn (signature->r) == 0 || mpz_sgn (signature->s) == 0);
+}
diff --git a/ecdsa-verify.c b/ecdsa-verify.c
new file mode 100644
index 00000000..0fdbe027
--- /dev/null
+++ b/ecdsa-verify.c
@@ -0,0 +1,68 @@
+/* ecc-ecdsa-verify.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 <stdlib.h>
+
+#include "ecdsa.h"
+#include "ecc-internal.h"
+#include "gmp-glue.h"
+
+int
+ecdsa_verify (const struct ecc_point *pub,
+	      unsigned length, const uint8_t *digest,
+	      const struct dsa_signature *signature)
+{
+  mp_limb_t size = pub->ecc->size;
+  mp_size_t itch = 2*size + ECC_ECDSA_VERIFY_ITCH (size);
+  /* For ECC_MUL_A_WBITS == 0, at most 1512 bytes. With
+     ECC_MUL_A_WBITS == 4, currently needs 67 * ecc->size, at most
+     4824 bytes. Don't use stack allocation for this. */
+  mp_limb_t *scratch = _gmp_alloc_limbs (itch);
+  int res;
+
+#define rp scratch
+#define sp (scratch + size)
+#define scratch_out (scratch + 2*size)
+
+  if (mpz_sgn (signature->r) <= 0 || mpz_size (signature->r) > size
+      || mpz_sgn (signature->s) <= 0 || mpz_size (signature->s) > size)
+    return 0;
+  
+  _mpz_copy_limbs (rp, signature->r, size);
+  _mpz_copy_limbs (sp, signature->s, size);
+
+  res = ecc_ecdsa_verify (pub->ecc, pub->p, length, digest, rp, sp, scratch_out);
+
+  _gmp_free_limbs (scratch, itch);
+
+  return res;
+#undef rp
+#undef sp
+#undef scratch_out
+}
diff --git a/ecdsa.h b/ecdsa.h
new file mode 100644
index 00000000..961102e5
--- /dev/null
+++ b/ecdsa.h
@@ -0,0 +1,94 @@
+/* ecdsa.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_ECDSA_H_INCLUDED
+#define NETTLE_ECDSA_H_INCLUDED
+
+#include "ecc.h"
+#include "dsa.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* Name mangling */
+#define ecdsa_sign nettle_ecdsa_sign
+#define ecdsa_verify nettle_ecdsa_verify
+#define ecdsa_generate_keypair nettle_ecdsa_generate_keypair
+#define ecc_ecdsa_sign nettle_ecc_ecdsa_sign
+#define ecc_ecdsa_sign_itch nettle_ecc_ecdsa_sign_itch
+#define ecc_ecdsa_verify nettle_ecc_ecdsa_verify
+#define ecc_ecdsa_verify_itch nettle_ecc_ecdsa_verify_itch
+
+/* High level ECDSA functions.
+ *
+ * A public key is represented as a struct ecc_point, and a private
+ * key as a struct ecc_scalar. FIXME: Introduce some aliases? */
+void
+ecdsa_sign (const struct ecc_scalar *key,
+	    void *random_ctx, nettle_random_func *random,
+	    unsigned digest_length,
+	    const uint8_t *digest,
+	    struct dsa_signature *signature);
+
+int
+ecdsa_verify (const struct ecc_point *pub,
+	      unsigned length, const uint8_t *digest,
+	      const struct dsa_signature *signature);
+
+void
+ecdsa_generate_keypair (struct ecc_point *pub,
+			struct ecc_scalar *key,
+			void *random_ctx, nettle_random_func *random);
+
+/* Low-level ECDSA functions. */
+mp_size_t
+ecc_ecdsa_sign_itch (const struct ecc_curve *ecc);
+
+void
+ecc_ecdsa_sign (const struct ecc_curve *ecc,
+		const mp_limb_t *zp,
+		/* Random nonce, must be invertible mod ecc group
+		   order. */
+		const mp_limb_t *kp,
+		unsigned length, const uint8_t *digest,
+		mp_limb_t *rp, mp_limb_t *sp,
+		mp_limb_t *scratch);
+
+mp_size_t
+ecc_ecdsa_verify_itch (const struct ecc_curve *ecc);
+
+int
+ecc_ecdsa_verify (const struct ecc_curve *ecc,
+		  const mp_limb_t *pp, /* Public key */
+		  unsigned length, const uint8_t *digest,
+		  const mp_limb_t *rp, const mp_limb_t *sp,
+		  mp_limb_t *scratch);
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* NETTLE_ECDSA_H_INCLUDED */