Snapshot along the way to ECDSA. Code mostly written, except for

ecdsa_verify().  Untested.  Point addition and doubling algorithms are
the ones from libtomcrypt, main point of this commit is to save those
before replacing them with faster algorithms from hyperelliptic.org.

6 files changed, 1561 insertions, 1 deletions

diff --git a/GNUmakefile b/GNUmakefile
index 82ec7ec..6a777cc 100644
--- a/GNUmakefile
+++ b/GNUmakefile
@@ -28,7 +28,7 @@
 INC		= hal.h
 LIB		= libhal.a
 OBJ		= ${IO_OBJ} csprng.o hash.o aes_keywrap.o pbkdf2.o \
-		  modexp.o rsa.o errorstrings.o
+		  modexp.o rsa.o ecdsa.o asn1.o errorstrings.o
 
 IO_OBJ_EIM	= hal_io_eim.o novena-eim.o
 IO_OBJ_I2C 	= hal_io_i2c.o
@@ -49,6 +49,10 @@ ${OBJ}: ${INC}
 ${LIB}: ${OBJ}
 	ar rcs $@ $^
 
+asn1.o rsa.o ecdsa.o: asn1_internal.h
+
+ecdsa.o: ecdsa_curves.h
+
 test: all
 	cd tests; ${MAKE} -k $@
 
diff --git a/asn1.c b/asn1.c
new file mode 100644
index 0000000..f4b3610
--- /dev/null
+++ b/asn1.c
@@ -0,0 +1,206 @@
+/*
+ * asn1.c
+ * ------
+ * Minimal ASN.1 implementation in support of Cryptech libhal.
+ *
+ * The functions in this module are not intended to be part of the
+ * public API.  Rather, these are utility functions used by more than
+ * one module within the library, which would otherwise have to be
+ * duplicated.  The main reason for keeping these private is to avoid
+ * having the public API depend on any details of the underlying
+ * bignum implementation (currently libtfm, but that might change).
+ *
+ * As of this writing, the ASN.1 support we need is quite minimal, so,
+ * rather than attempting to clean all the unecessary cruft out of a
+ * general purpose ASN.1 implementation, we hand code the very small
+ * number of data types we need.  At some point this will probably
+ * become impractical, at which point we might want to look into using
+ * something like the asn1c compiler.
+ *
+ * Authors: Rob Austein
+ * Copyright (c) 2015, SUNET
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <stddef.h>
+#include <string.h>
+#include <assert.h>
+
+#include "hal.h"
+
+#include "asn1_internal.h"
+
+/*
+ * Encode tag and length fields of an ASN.1 object.  If der is NULL,
+ * just return the size that would be encoded.
+ */
+
+hal_error_t hal_asn1_encode_header(const uint8_t tag,
+				   const size_t value_len,
+				   uint8_t *der, size_t *der_len, const size_t der_max)
+{
+  size_t header_len = 2;	/* Shortest encoding is one octet each for tag and length */
+
+  if (value_len >= 128)		/* Add octets for longer length encoding as needed */
+    for (size_t n = value_len; n > 0; n >>= 8)
+      ++header_len;
+
+  if (der_len != NULL)
+    *der_len = header_len;
+
+  if (der == NULL)		/* If caller just wanted the length, we're done */
+    return HAL_OK;
+
+  /*
+   * Make sure there's enough room for header + value, then encode.
+   */
+
+  if (value_len + header_len > der_max)
+    return HAL_ERROR_RESULT_TOO_LONG;
+
+  if (value_len < 128) {
+    *der = (uint8_t) value_len;
+  }
+
+  else {
+    *der = 0x80 | (uint8_t) (header_len -= 2);
+    for (size_t n = value_len; n > 0 && header_len > 0; n >>= 8)
+      der[header_len--] = (uint8_t) (n & 0xFF);
+  }
+
+  return HAL_OK;
+}
+
+/*
+ * Encode an unsigned ASN.1 INTEGER from a libtfm bignum.  If der is
+ * NULL, just return the length of what we would have encoded.
+ */
+
+hal_error_t hal_asn1_encode_integer(fp_int *bn,
+				    uint8_t *der, size_t *der_len, const size_t der_max)
+{
+  if (bn == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  /*
+   * We only handle unsigned INTEGERs, so we need to pad data with a
+   * leading zero if the most significant bit is set, to avoid
+   * flipping the ASN.1 sign bit.  Conveniently, this also handles the
+   * difference between libtfm's and ASN.1's encoding of zero.
+   */
+
+  if (fp_cmp_d(bn, 0) == FP_LT)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  const int leading_zero = fp_iszero(bn) || (fp_count_bits(bn) & 7) == 0;
+  const size_t vlen = fp_unsigned_bin_size(bn) + leading_zero;
+  hal_error_t err;
+  size_t hlen;
+
+  if ((err = hal_asn1_encode_header(ASN1_INTEGER, vlen, der, &hlen, der_max)) != HAL_OK)
+    return err;
+
+  if (der_len != NULL)
+    *der_len = hlen + vlen;
+
+  if (der == NULL)
+    return HAL_OK;
+
+  if (hlen + vlen > der_max)
+    return HAL_ERROR_RESULT_TOO_LONG;
+
+  der += hlen;
+  if (leading_zero)
+    *der++ = 0x00;
+  fp_to_unsigned_bin(bn, der);
+
+  return HAL_OK;
+}
+
+
+hal_error_t hal_asn1_decode_header(const uint8_t tag,
+				   const uint8_t * const der, size_t der_max,
+				   size_t *hlen, size_t *vlen)
+{
+  assert(der != NULL && hlen != NULL && vlen != NULL);
+
+  if (der_max < 2 || der[0] != tag)
+    return HAL_ERROR_ASN1_PARSE_FAILED;
+
+  if ((der[1] & 0x80) == 0) {
+    *hlen = 2;
+    *vlen = der[1];
+  }
+
+  else {
+    *hlen = 2 + (der[1] & 0x7F);
+    *vlen = 0;
+
+    if (*hlen > der_max)
+      return HAL_ERROR_ASN1_PARSE_FAILED;
+
+    for (size_t i = 2; i < *hlen; i++)
+      *vlen = (*vlen << 8) + der[i];
+  }
+
+  if (*hlen + *vlen > der_max)
+    return HAL_ERROR_ASN1_PARSE_FAILED;
+
+  return HAL_OK;
+}
+
+hal_error_t hal_asn1_decode_integer(fp_int *bn,
+				    const uint8_t * const der, size_t *der_len, const size_t der_max)
+{
+  if (bn == NULL || der == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  hal_error_t err;
+  size_t hlen, vlen;
+
+  if ((err = hal_asn1_decode_header(ASN1_INTEGER, der, der_max, &hlen, &vlen)) != HAL_OK)
+    return err;
+
+  if (der_len != NULL)
+    *der_len = hlen + vlen;
+
+  if (vlen < 1 || (der[hlen] & 0x80) != 0x00)
+    return HAL_ERROR_ASN1_PARSE_FAILED;
+
+  fp_init(bn);
+  fp_read_unsigned_bin(bn, (uint8_t *) der + hlen, vlen);
+  return HAL_OK;
+}
+
+/*
+ * Local variables:
+ * indent-tabs-mode: nil
+ * End:
+ */
diff --git a/asn1_internal.h b/asn1_internal.h
new file mode 100644
index 0000000..9d5ab4d
--- /dev/null
+++ b/asn1_internal.h
@@ -0,0 +1,91 @@
+/*
+ * asn1.h
+ * ------
+ * Library internal header file for ASN.1 routines.
+ *
+ * These functions are not part of the public libhal API.
+ *
+ * More than 20 years after it was written, the best simple
+ * introduction to ASN.1 is still Burt Kalski's "A Layman's Guide to a
+ * Subset of ASN.1, BER, and DER".  Ask your nearest search engine.
+ *
+ * Authors: Rob Austein
+ * Copyright (c) 2015, SUNET
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef _HAL_ASN1_H_
+#define _HAL_ASN1_H_
+
+#include <stdint.h>
+#include <stdlib.h>
+
+#include <tfm.h>
+
+#define ASN1_UNIVERSAL          0x00
+#define ASN1_APPLICATION        0x40
+#define ASN1_CONTEXT_SPECIFIC   0x80
+#define ASN1_PRIVATE            0xC0
+
+#define ASN1_PRIMITIVE          0x00
+#define ASN1_CONSTRUCTED        0x20
+
+#define ASN1_TAG_MASK           0x1F
+
+#define ASN1_INTEGER            (ASN1_PRIMITIVE   | 0x02)
+#define ASN1_BIT_STRING         (ASN1_PRIMITIVE   | 0x03)
+#define ASN1_OCTET_STRING       (ASN1_PRIMITIVE   | 0x04)
+#define ASN1_NULL               (ASN1_PRIMITIVE   | 0x05)
+#define ASN1_OBJECT_IDENTIFIER  (ASN1_PRIMITIVE   | 0x06)
+#define ASN1_SEQUENCE           (ASN1_CONSTRUCTED | 0x10)
+#define ASN1_SET                (ASN1_CONSTRUCTED | 0x11)
+
+#define ASN1_EXPLICIT_CONTEXT   (ASN1_CONTEXT_SPECIFIC | ASN1_CONSTRUCTED)
+#define ASN1_EXPLICIT_0         (ASN1_EXPLICIT_CONTEXT + 0)
+#define ASN1_EXPLICIT_1         (ASN1_EXPLICIT_CONTEXT + 1)
+
+extern hal_error_t hal_asn1_encode_header(const uint8_t tag,
+                                          const size_t value_len,
+                                          uint8_t *der, size_t *der_len, const size_t der_max);
+
+extern hal_error_t hal_asn1_decode_header(const uint8_t tag,
+                                          const uint8_t * const der, size_t der_max,
+                                          size_t *hlen, size_t *vlen);
+
+extern hal_error_t hal_asn1_encode_integer(fp_int *bn,
+                                           uint8_t *der, size_t *der_len, const size_t der_max);
+
+extern hal_error_t hal_asn1_decode_integer(fp_int *bn,
+                                           const uint8_t * const der, size_t *der_len, const size_t der_max);
+
+#endif /* _HAL_ASN1_H_ */
+
+/*
+ * Local variables:
+ * indent-tabs-mode: nil
+ * End:
+ */
diff --git a/ecdsa.c b/ecdsa.c
new file mode 100644
index 0000000..49893de
--- /dev/null
+++ b/ecdsa.c
@@ -0,0 +1,1105 @@
+/*
+ * ecdsa.c
+ * -------
+ * Basic ECDSA functions.
+ *
+ * At some point we may want to refactor this to separate
+ * functionality that appiles to all elliptic curve cryptography from
+ * functions specific to ECDSA over the NIST Suite B prime curves, but
+ * it's simplest to keep this all in one place initially.
+ *
+ * Much of the code in this module is based, at least loosely, on Tom
+ * St Denis's libtomcrypt code.  
+ *
+ * Authors: Rob Austein
+ * Copyright (c) 2015, SUNET
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/*
+ * We use "Tom's Fast Math" library for our bignum implementation.
+ * This particular implementation has a couple of nice features:
+ *
+ * - The code is relatively readable, thus reviewable.
+ *
+ * - The bignum representation doesn't use dynamic memory, which
+ *   simplifies things for us.
+ *
+ * The price tag for not using dynamic memory is that libtfm has to be
+ * configured to know about the largest bignum one wants it to be able
+ * to support at compile time.  This should not be a serious problem.
+ *
+ * We use a lot of one-element arrays (fp_int[1] instead of plain
+ * fp_int) to avoid having to prefix every use of an fp_int with "&".
+ *
+ * Unfortunately, libtfm is bad about const-ification, but we want to
+ * hide that from our users, so our public API uses const as
+ * appropriate and we use inline functions to remove const constraints
+ * in a relatively type-safe manner before calling libtom.
+ */
+
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <stddef.h>
+#include <string.h>
+#include <assert.h>
+
+#include "hal.h"
+#include <tfm.h>
+#include "asn1_internal.h"
+
+/*
+ * Whether we want debug output.
+ */
+
+static int debug = 0;
+
+void hal_ecdsa_set_debug(const int onoff)
+{
+  debug = onoff;
+}
+
+/*
+ * ECDSA curve descriptor.  We only deal with named curves; at the
+ * moment, we only deal with NIST prime curves where the elliptic
+ * curve's "a" parameter is always -3 and its "h" value (order of
+ * elliptic curve group divided by order of base point) is always 1.
+ *
+ * Since the Montgomery parameters we need for the point arithmetic
+ * depend only on the underlying field prime, we precompute them when
+ * we load the curve and store them in the field descriptor, even
+ * though they aren't really curve parameters per se.
+ *
+ * For similar reasons, we also include the ASN.1 OBJECT IDENTIFIERs
+ * used to name these curves.
+ */
+
+typedef struct {
+  fp_int q[1];                          /* Modulus of underlying prime field */
+  fp_int b[1];                          /* Curve's "b" parameter */
+  fp_int Gx[1];                         /* x component of base point G */
+  fp_int Gy[1];                         /* y component of base point G */
+  fp_int n[1];                          /* Order of base point G */
+  fp_int mu[1];                         /* Montgomery normalization factor */
+  fp_digit rho;                         /* Montgomery reduction value */
+  const uint8_t *oid;                   /* OBJECT IDENTIFIER */
+  size_t oid_len;                       /* Length of OBJECT IDENTIFIER */
+} ecdsa_curve_t;
+
+/*
+ * ECDSA key implementation.  This structure type is private to this
+ * module, anything else that needs to touch one of these just gets a
+ * typed opaque pointer.  We do, however, export the size, so that we
+ * can make memory allocation the caller's problem.
+ *
+ * EC points are stored in Jacobian format such that (x, y, z) =>
+ * (x/z**2, y/z**3, 1) when interpretted as affine coordinates.
+ */
+
+typedef struct {
+  fp_int x[1], y[1], z[1];
+} ec_point_t;
+
+struct hal_ecdsa_key {
+  hal_ecdsa_key_type_t type;            /* Public or private is */
+  hal_ecdsa_curve_t curve;              /* Curve descriptor */
+  ec_point_t Q[1];                      /* Public key */
+  fp_int d[1];                          /* Private key */
+};
+
+const size_t hal_ecdsa_key_t_size = sizeof(struct hal_ecdsa_key);
+
+/*
+ * Error handling.
+ */
+
+#define lose(_code_) do { err = _code_; goto fail; } while (0)
+
+/*
+ * Functions to strip const qualifiers from arguments to libtfm calls
+ * in a relatively type-safe manner.
+ */
+
+static inline fp_int *unconst_fp_int(const fp_int * const arg)
+{
+  return (fp_int *) arg;
+}
+
+static inline uint8_t *unconst_uint8_t(const uint8_t * const arg)
+{
+  return (uint8_t *) arg;
+}
+
+/*
+ * We can't (usefully) initialize fp_int variables at compile time, so
+ * instead we load all the curve parameters the first time anything
+ * asks for any of them.
+ */
+
+static const ecdsa_curve_t * const get_curve(const hal_ecdsa_curve_t curve)
+{
+  static ecdsa_curve_t curve_p256, curve_p384, curve_p521;
+  static int initialized = 0;
+
+  if (!initialized) {
+
+#include "ecdsa_curves.h"
+
+    fp_read_unsigned_bin(curve_p256.q,  unconst_uint8_t(p256_q),  sizeof(p256_q));
+    fp_read_unsigned_bin(curve_p256.b,  unconst_uint8_t(p256_b),  sizeof(p256_b));
+    fp_read_unsigned_bin(curve_p256.Gx, unconst_uint8_t(p256_Gx), sizeof(p256_Gx));
+    fp_read_unsigned_bin(curve_p256.Gy, unconst_uint8_t(p256_Gy), sizeof(p256_Gy));
+    fp_read_unsigned_bin(curve_p256.n,  unconst_uint8_t(p256_n),  sizeof(p256_n));
+    if (fp_montgomery_setup(curve_p256.q, &curve_p256.rho) != FP_OKAY)
+      return NULL;
+    fp_zero(curve_p256.mu);
+    fp_montgomery_calc_normalization(curve_p256.mu, curve_p256.q);
+    curve_p256.oid = p256_oid;
+    curve_p256.oid_len = sizeof(p256_oid);
+
+    fp_read_unsigned_bin(curve_p384.q,  unconst_uint8_t(p384_q),  sizeof(p384_q));
+    fp_read_unsigned_bin(curve_p384.b,  unconst_uint8_t(p384_b),  sizeof(p384_b));
+    fp_read_unsigned_bin(curve_p384.Gx, unconst_uint8_t(p384_Gx), sizeof(p384_Gx));
+    fp_read_unsigned_bin(curve_p384.Gy, unconst_uint8_t(p384_Gy), sizeof(p384_Gy));
+    fp_read_unsigned_bin(curve_p384.n,  unconst_uint8_t(p384_n),  sizeof(p384_n));
+    if (fp_montgomery_setup(curve_p384.q, &curve_p384.rho) != FP_OKAY)
+      return NULL;
+    fp_zero(curve_p384.mu);
+    fp_montgomery_calc_normalization(curve_p384.mu, curve_p384.q);
+    curve_p384.oid = p384_oid;
+    curve_p384.oid_len = sizeof(p384_oid);
+
+    fp_read_unsigned_bin(curve_p521.q,  unconst_uint8_t(p521_q),  sizeof(p521_q));
+    fp_read_unsigned_bin(curve_p521.b,  unconst_uint8_t(p521_b),  sizeof(p521_b));
+    fp_read_unsigned_bin(curve_p521.Gx, unconst_uint8_t(p521_Gx), sizeof(p521_Gx));
+    fp_read_unsigned_bin(curve_p521.Gy, unconst_uint8_t(p521_Gy), sizeof(p521_Gy));
+    fp_read_unsigned_bin(curve_p521.n,  unconst_uint8_t(p521_n),  sizeof(p521_n));
+    if (fp_montgomery_setup(curve_p521.q, &curve_p521.rho) != FP_OKAY)
+      return NULL;
+    fp_zero(curve_p521.mu);
+    fp_montgomery_calc_normalization(curve_p521.mu, curve_p521.q);
+    curve_p521.oid = p521_oid;
+    curve_p521.oid_len = sizeof(p521_oid);
+
+    initialized = 1;
+  }
+
+  switch (curve) {
+  case HAL_ECDSA_CURVE_P256: return &curve_p256;
+  case HAL_ECDSA_CURVE_P384: return &curve_p384;
+  case HAL_ECDSA_CURVE_P521: return &curve_p521;
+  default:                   return NULL;
+  }
+}
+
+/*
+ * Test whether two points are equal: x and z coordinates identical, y
+ * coordinates either identical or negated.
+ */
+
+static inline int point_equal(const ec_point_t * const P,
+                              const ec_point_t * const Q,
+                              const ecdsa_curve_t * const curve)
+{
+  assert(P != NULL && Q != NULL && curve != NULL);
+
+  if (fp_cmp(unconst_fp_int(P->x), unconst_fp_int(Q->x)) != FP_EQ ||
+      fp_cmp(unconst_fp_int(P->z), unconst_fp_int(Q->z)) != FP_EQ)
+    return 0;
+
+  if (fp_cmp(unconst_fp_int(P->y), unconst_fp_int(Q->y)) == FP_EQ)
+    return 1;
+
+  fp_int Qy_neg[1];
+
+  fp_sub(unconst_fp_int(curve->q), unconst_fp_int(Q->y), Qy_neg);
+
+  const int result = fp_cmp(unconst_fp_int(P->y), Qy_neg) == FP_EQ;
+
+  fp_zero(Qy_neg);
+
+  return result;
+}
+
+/*
+ * Finite field operations (hence "ff_").  These are basically just
+ * the usual bignum operations, constrained by the field modulus.
+ *
+ * All of these are operations in the field underlying the specified
+ * curve, and assume that operands are already in Montgomery form.
+ *
+ * Several of these are written a bit oddly, in an attempt to make
+ * them run in constant time.  Be warned that an optimizing compiler
+ * may be clever enough to defeat this.  In the long run, the real
+ * solution is probably to perform these field operations in Verilog.
+ */
+
+static inline void ff_add(const ecdsa_curve_t * const curve,
+                          const fp_int * const a,
+                          const fp_int * const b,
+                          fp_int *c)
+{
+  fp_int t[2][1];
+  memset(t, 0, sizeof(t));
+  fp_add(unconst_fp_int(a), unconst_fp_int(b), t[0]);
+  fp_sub(t[0], unconst_fp_int(curve->q), t[1]);
+  fp_copy(t[fp_cmp(t[0], unconst_fp_int(curve->q)) != FP_LT], c);
+  memset(t, 0, sizeof(t));
+}
+
+static inline void ff_sub(const ecdsa_curve_t * const curve,
+                          const fp_int * const a, 
+                          const fp_int * const b,
+                          fp_int *c)
+{
+  fp_int t[2][1];
+  memset(t, 0, sizeof(t));
+  fp_sub(unconst_fp_int(a), unconst_fp_int(b), t[0]);
+  fp_add(t[0], unconst_fp_int(curve->q), t[1]);
+  fp_copy(t[fp_cmp_d(c, 0) == FP_LT], c);
+  memset(t, 0, sizeof(t));
+}
+
+static inline void ff_div2(const ecdsa_curve_t * const curve,
+                           const fp_int * const a, 
+                           fp_int *b)
+{
+  fp_int t[2][1];
+  memset(t, 0, sizeof(t));
+  fp_copy(unconst_fp_int(a), t[0]);
+  fp_add(t[0], unconst_fp_int(curve->q), t[1]);
+  fp_div_2(t[fp_isodd(unconst_fp_int(a))], b);
+  memset(t, 0, sizeof(t));
+}
+
+static inline void ff_mul(const ecdsa_curve_t * const curve,
+                          const fp_int * const a,
+                          const fp_int * const b,
+                          fp_int *c)
+{
+  fp_mul(unconst_fp_int(a), unconst_fp_int(b), c);
+  fp_montgomery_reduce(c, unconst_fp_int(curve->q), curve->rho);
+}
+
+static inline void ff_sqr(const ecdsa_curve_t * const curve,
+                          const fp_int * const a,
+                          fp_int *b)
+{
+  fp_sqr(unconst_fp_int(a), b);
+  fp_montgomery_reduce(b, unconst_fp_int(curve->q), curve->rho);
+}
+
+#warning Change point arithmetic algorithms?
+/*
+ * The point doubling and addition algorithms we use here are from
+ * libtomcrypt.  The formula database at hyperelliptic.org lists
+ * faster algorithms satisfying the same preconditions, perhaps we
+ * should use those instead?
+ *
+ * Labels in the following refer to entries on the page:
+ *  http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html
+ *
+ * The libtomcrypt doubling algorithm looks like a trivial variation
+ * on dbl-2004-hmv.  We might want to use dbl-2001-b instead.
+ *
+ * The libtomcrypt addition algorithm doesn't match up exactly with
+ * any listed algorithm, but I suspect it's a variation on
+ * add-1998-cmo-2.  We might want to use add-2007-bl instead.
+ *
+ * There are faster algorithms listed, but all of them appear to
+ * require whacking one or both points back into affine
+ * representation, which has its own costs, so, at least for now, it'd
+ * probably be best to stick with algorithms that don't require this.
+ */
+
+/**
+ * Double an EC point.
+ * @param P             The point to double
+ * @param R             [out] The destination of the double
+ * @param curve         The curve parameters structure
+ *
+ * Algorithm is a minor variation on algorithm 3.21 from Guide to
+ * Elliptic Curve Cryptography.
+ */
+
+static inline void point_double(const ec_point_t * const P,
+                                ec_point_t *R,
+                                const ecdsa_curve_t * const curve)
+{
+  assert(P != NULL && R != NULL && curve != NULL);
+
+  fp_int t1[1]; fp_init(t1); 
+  fp_int t2[1]; fp_init(t2);
+
+  if (P != R)
+    *R = *P;
+
+  ff_sqr  (curve,  R->z,  t1);                /* t1 = Pz ** 2                                   */
+  ff_sub  (curve,  R->x,  t1,    t2);         /* t2 = Px - Pz ** 2                              */
+  ff_add  (curve,  R->x,  t1,    t1);         /* t1 = Px + Pz ** 2                              */
+  ff_mul  (curve,  t1,    t2,    t2);         /* t2 = 1 * (Px - Pz ** 2) * (Px + Pz ** 2)       */
+  ff_add  (curve,  t2,    t2,    t1);         /* t1 = 2 * (Px - Pz ** 2) * (Px + Pz ** 2)       */
+  ff_add  (curve,  t1,    t2,    t1);         /* t1 = 3 * (Px - Pz ** 2) * (Px + Pz ** 2) = A   */
+
+  ff_add  (curve,  R->y,  R->y,  R->y);       /* Ry = 2 * Py = B                                */
+  ff_mul  (curve,  R->z,  R->y,  R->z);       /* Rz = B * Pz                                    */
+
+  ff_sqr  (curve,  R->y,  R->y);              /* Ry = B ** 2 = C                                */
+  ff_sqr  (curve,  R->y,  t2);                /* t2 = C ** 2                                    */
+  ff_div2 (curve,  t2,    t2);                /* t2 = C ** 2 / 2                                */
+  ff_mul  (curve,  R->y,  R->x,  R->y);       /* Ry = C * Px = D                                */
+
+  ff_sqr  (curve,  t1,    R->x);              /* Rx = A ** 2                                    */
+  ff_sub  (curve,  R->x,  R->y,  R->x);       /* Rx = A ** 2 - D                                */
+  ff_sub  (curve,  R->x,  R->y,  R->x);       /* Rx = A ** 2 - 2 * D                            */
+
+  ff_sub  (curve,  R->y,  R->x,  R->y);       /* Ry = D - Rx                                    */
+  ff_mul  (curve,  R->y,  t1,    R->y);       /* Ry = (D - Rx) * A                              */
+  ff_sub  (curve,  R->y,  t2,    R->y);       /* Ry = (D - Rx) * A - C ** 2 / 2                 */
+
+  fp_zero(t1); fp_zero(t2);
+}
+
+/**
+ * Add two EC points
+ * @param P             The point to add
+ * @param Q             The point to add
+ * @param R             [out] The destination of the double
+ * @param curve         The curve parameters structure
+*/
+
+static inline void point_add(const ec_point_t * const P,
+                             const ec_point_t * const Q,
+                             ec_point_t *R,
+                             const ecdsa_curve_t * const curve)
+{
+  assert(P != NULL && Q != NULL && R != NULL && curve != NULL);
+
+  if (point_equal(P, Q, curve))
+    return point_double(P, R, curve);
+
+  fp_int t1[1]; fp_init(t1);
+  fp_int t2[1]; fp_init(t2);
+
+  if (P != R)
+    *R = *P;
+
+  /*
+   * Operations marked {@} are no-ops when Q.z == 1, but probably
+   * don't save us enough in the long run for optimizing them out to
+   * be worth even a low-probability risk of a timing channel attack.
+   */
+
+  ff_sqr  (curve,  Q->z,   t1);                      /* t1 = z' ** 2       {@} */
+  ff_mul  (curve,  t1,     R->x,   R->x);            /* x  = x  *  z' ** 2 {@} */
+  ff_mul  (curve,  Q->z,   t1,     t1);              /* t1 = z' ** 3       {@} */
+  ff_mul  (curve,  t1,     R->y,   R->y);            /* y  = y  *  z' ** 3 {@} */
+
+  ff_sqr  (curve,  R->z,  t1);                       /* t1 = z  * z  */
+  ff_mul  (curve,  Q->x,  t1,    t2);                /* t2 = x' * t1 */
+  ff_mul  (curve,  R->z,  t1,    t1);                /* t1 = z  * t1 */
+  ff_mul  (curve,  Q->y,  t1,    t1);                /* t1 = y' * t1 */
+
+  ff_sub  (curve,  R->y,  t1,    R->y);              /* y  = y  - t1 */
+  ff_add  (curve,  t1,    t1,    t1);                /* t1 = 2  * t1 */
+  ff_add  (curve,  t1,    R->y,  t1);                /* t1 = y  + t1 */
+  ff_sub  (curve,  R->x,  t2,    R->x);              /* x  = x  - t2 */
+  ff_add  (curve,  t2,    t2,    t2);                /* t2 = 2  * t2 */
+  ff_add  (curve,  t2,    R->x,  t2);                /* t2 = x  + t2 */
+
+  ff_mul  (curve,  R->z,  Q->z,  R->z);              /* z  = z * z' {@} */
+
+  ff_mul  (curve,  R->z,  R->x,  R->z);              /* z  = z  * x  */
+
+  ff_mul  (curve,  t1,    R->x,  t1);                /* t1 = t1 * x  */
+  ff_sqr  (curve,  R->x,  R->x);                     /* x  = x  * x  */
+  ff_mul  (curve,  t2,    R->x,  t2);                /* t2 = t2 * x  */
+  ff_mul  (curve,  t1,    R->x,  t1);                /* t1 = t1 * x  */
+
+  ff_sqr  (curve,  R->y,  R->x);                     /* x  = y  * y  */
+  ff_sub  (curve,  R->x,  t2,    R->x);              /* x  = x  - t2 */
+
+  ff_sub  (curve,  t2,    R->x,  t2);                /* t2 = t2 - x  */
+  ff_sub  (curve,  t2,    R->x,  t2);                /* t2 = t2 - x  */
+  ff_mul  (curve,  t2,    R->y,  t2);                /* t2 = t2 * y  */
+  ff_sub  (curve,  t2,    t1,    R->y);              /* y  = t2 - t1 */
+  ff_div2 (curve,  R->y,  R->y);                     /* y  = y  / 2  */
+
+  fp_zero(t1); fp_zero(t2);
+}
+
+/**
+ * Map a projective jacbobian point back to affine space
+ * @param P        [in/out] The point to map
+ * @param curve    The curve parameters structure
+ */
+
+static inline hal_error_t point_to_affine(ec_point_t *P,
+                                          const ecdsa_curve_t * const curve)
+{
+  assert(P != NULL && curve != NULL);
+
+  hal_error_t err = HAL_ERROR_IMPOSSIBLE;
+
+  fp_int t1[1]; fp_init(t1);
+  fp_int t2[1]; fp_init(t2);
+
+  fp_int * const q = unconst_fp_int(curve->q);
+
+  fp_montgomery_reduce(P->z, q, curve->rho);
+
+  if (fp_invmod (P->z,   q, t1) != FP_OKAY ||    /* t1 = 1 / z    */
+      fp_sqrmod (t1,     q, t2) != FP_OKAY ||    /* t2 = 1 / z**2 */
+      fp_mulmod (t1, t2, q, t1) != FP_OKAY)      /* t1 = 1 / z**3 */
+    goto fail;
+
+  fp_mul (P->x,  t2,  P->x);                     /* x = x / z**2 */
+  fp_mul (P->y,  t1,  P->y);                     /* y = y / z**3 */
+  fp_set (P->z,  1);                             /* z = 1        */
+
+  fp_montgomery_reduce(P->x, q, curve->rho);
+  fp_montgomery_reduce(P->y, q, curve->rho);
+
+  err = HAL_OK;
+
+ fail:
+  fp_zero(t1);
+  fp_zero(t2);
+  return err;
+}
+
+/**
+ * Perform a point multiplication.
+ * @param k             The scalar to multiply by
+ * @param P             The base point
+ * @param R             [out] Destination for kP
+ * @param curve         Curve parameters
+ * @param map           Boolean whether to map back to affine (1: map, 0: leave projective)
+ * @return HAL_OK on success
+ *
+ * This implementation uses the "Montgomery Ladder" approach, which is
+ * relatively robust against timing channel attacks if nothing else
+ * goes wrong, but many other things can indeed go wrong.
+ */
+
+static hal_error_t point_scalar_multiply(const fp_int * const k,
+                                         const ec_point_t * const P,
+                                         ec_point_t *R,
+                                         const ecdsa_curve_t * const curve,
+                                         const int map)
+{
+  assert(k != NULL && P != NULL && R != NULL &&  curve != NULL);
+
+  if (fp_iszero(k))
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  /*
+   * Convert to Montgomery form and initialize table.  Initial values:
+   *
+   * M[0] = 1P
+   * M[1] = 2P
+   * M[2] = don't care, only used for timing-attack resistance
+   */
+
+  ec_point_t M[3][1];
+  memset(M, 0, sizeof(M));
+
+  if (fp_mulmod(unconst_fp_int(P->x), unconst_fp_int(curve->mu), unconst_fp_int(curve->q), M[0]->x) != FP_OKAY ||
+      fp_mulmod(unconst_fp_int(P->y), unconst_fp_int(curve->mu), unconst_fp_int(curve->q), M[0]->y) != FP_OKAY ||
+      fp_mulmod(unconst_fp_int(P->z), unconst_fp_int(curve->mu), unconst_fp_int(curve->q), M[0]->z) != FP_OKAY) {
+    memset(M, 0, sizeof(M));
+    return HAL_ERROR_IMPOSSIBLE;
+  }
+
+  point_double(M[0], M[1], curve);
+
+  /*
+   * Walk down bits of the scalar, performing dummy operations to mask
+   * timing while hunting for the most significant bit.
+   */
+
+  int dummy_mode = 1;
+
+  for (int digit_index = k->used - 1; digit_index >= 0; digit_index--) {
+
+    fp_digit digit = k->dp[digit_index];
+
+    for (int bits_left = DIGIT_BIT; bits_left > 0; bits_left--) {
+
+      const int bit = (digit >> (DIGIT_BIT - 1)) & 1;
+      digit <<= 1;
+
+      if (dummy_mode) {
+        point_add    (M[0], M[1], M[2], curve);
+        point_double (M[1], M[2],       curve);
+        dummy_mode = !bit;                              /* Dummy until we find MSB */
+      }
+
+      else {
+        point_add    (M[0],   M[1],  M[bit^1], curve);
+        point_double (M[bit], M[bit],          curve);
+      }
+    }
+  }
+
+  /*
+   * Copy result out, map back to affine if requested, then done.
+   */
+
+  *R = *M[0];
+  hal_error_t err = map ? point_to_affine(R, curve) : HAL_OK;
+  memset(M, 0, sizeof(M));
+  return err;
+}
+
+/*
+ * Pick a random point on the curve, return random scalar and
+ * resulting point.
+ */
+
+static hal_error_t point_pick_random(const ecdsa_curve_t * const curve,
+                                     fp_int *k,
+                                     ec_point_t *P)
+{
+  hal_error_t err;
+
+  assert(curve != NULL && k != NULL && P != NULL);
+
+  /*
+   * Pick a random scalar corresponding to a point on the curve.  Per
+   * the NSA (gulp) Suite B guidelines, we ask the CSPRNG for 64 more
+   * bits than we need, which should be enough to mask any bias
+   * induced by the modular reduction.
+   *
+   * We're picking a point out of the subgroup generated by the base
+   * point on the elliptic curve, so the modulus for this calculation
+   * is order of the base point.
+   *
+   * Zero is an excluded value, but the chance of a non-broken CSPRNG
+   * returning zero is so low that it would almost certainly indicate
+   * an undiagnosed bug in the CSPRNG.
+   */
+  uint8_t k_buf[fp_unsigned_bin_size(unconst_fp_int(curve->n)) + 8];
+
+  do {
+    if ((err = hal_get_random(k_buf, sizeof(k_buf))) != HAL_OK)
+      return err;
+    fp_read_unsigned_bin(k, k_buf, sizeof(k_buf));
+    if (fp_iszero(k) || fp_mod(k, unconst_fp_int(curve->n), k) != FP_OKAY)
+      return HAL_ERROR_IMPOSSIBLE;
+  } while (fp_iszero(k));
+
+  memset(k_buf, 0, sizeof(k_buf));
+
+  /*
+   * Calculate P = kG and return.
+   */
+
+  fp_copy(curve->Gx, P->x);
+  fp_copy(curve->Gy, P->y);
+  fp_set(P->z, 1);
+
+  return point_scalar_multiply(k, P, P, curve, 1);
+}
+
+/*
+ * Test whether a point really is on a particular curve (sometimes
+ * called "validation when applied to a public key").
+ */
+
+static int point_is_on_curve(const ec_point_t * const P,
+                             const ecdsa_curve_t * const curve)
+{
+  assert(P != NULL && curve != NULL);
+
+  fp_int t1[1]; fp_init(t1); 
+  fp_int t2[1]; fp_init(t2);
+
+  /*
+   * Compute y**2 - x**3 + 3*x.
+   */
+
+  fp_sqr(unconst_fp_int(P->y), t1);             /* t1 = y**2 */
+  fp_sqr(unconst_fp_int(P->x), t2);             /* t2 = x**2 */
+  if (fp_mod(t2, unconst_fp_int(curve->q), t2) != FP_OKAY)
+    return 0;
+  fp_mul(unconst_fp_int(P->x), t2, t2);         /* t2 = x**3 */
+  fp_sub(t1, t2, t1);                           /* t1 = y**2 - x**3 */
+  fp_add(t1, unconst_fp_int(P->x), t1);         /* t1 = y**2 - x**3 + 1*x */
+  fp_add(t1, unconst_fp_int(P->x), t1);         /* t1 = y**2 - x**3 + 2*x */
+  fp_add(t1, unconst_fp_int(P->x), t1);         /* t1 = y**2 - x**3 + 3*x */
+
+  /*
+   * Normalize and test whether computed value matches b.
+   */
+
+  if (fp_mod(t1, unconst_fp_int(curve->q), t1) != FP_OKAY)
+    return 0;
+  while (fp_cmp_d(t1, 0) == FP_LT)
+    fp_add(t1, unconst_fp_int(curve->q), t1);
+  while (fp_cmp(t1, unconst_fp_int(curve->q)) != FP_LT)
+    fp_sub(t1, unconst_fp_int(curve->q), t1);
+
+  return fp_cmp(t1, unconst_fp_int(curve->b)) == FP_EQ;
+}
+
+/*
+ * Generate a new ECDSA key.
+ */
+
+hal_error_t hal_ecdsa_key_gen(hal_ecdsa_key_t **key_,
+                              void *keybuf, const size_t keybuf_len,
+                              const hal_ecdsa_curve_t curve_)
+{
+  const ecdsa_curve_t * const curve = get_curve(curve_);
+  hal_ecdsa_key_t *key = keybuf;
+  hal_error_t err;
+
+  if (key_ == NULL || key == NULL || keybuf_len < sizeof(*key) || curve == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  memset(keybuf, 0, keybuf_len);
+
+  key->type = HAL_ECDSA_PRIVATE;
+  key->curve = curve_;
+
+  if ((err = point_pick_random(curve, key->d, key->Q)) != HAL_OK)
+    return err;
+
+  assert(point_is_on_curve(key->Q, curve));
+
+  *key_ = key;
+  return HAL_OK;
+}
+
+/*
+ * Extract key type (public or private).
+ */
+
+hal_error_t hal_ecdsa_key_get_type(const hal_ecdsa_key_t * const key,
+                                   hal_ecdsa_key_type_t *key_type)
+{
+  if (key == NULL || key_type == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  *key_type = key->type;
+  return HAL_OK;
+}
+
+/*
+ * Extract name of curve underlying a key.
+ */
+
+hal_error_t hal_ecdsa_key_get_curve(const hal_ecdsa_key_t * const key,
+                                    hal_ecdsa_curve_t *curve)
+{
+  if (key == NULL || curve == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  *curve = key->curve;
+  return HAL_OK;
+}
+
+/*
+ * Extract public key components.
+ */
+
+hal_error_t hal_ecdsa_key_get_public(const hal_ecdsa_key_t * const key,
+                                     uint8_t *x, size_t *x_len, const size_t x_max,
+                                     uint8_t *y, size_t *y_len, const size_t y_max)
+{
+  if (key == NULL || (x_len == NULL && x != NULL) || (y_len == NULL && y != NULL))
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  if (x_len != NULL)
+    *x_len = fp_unsigned_bin_size(unconst_fp_int(key->Q->x));
+
+  if (y_len != NULL)
+    *y_len = fp_unsigned_bin_size(unconst_fp_int(key->Q->y));
+
+  if ((x != NULL && *x_len > x_max) ||
+      (y != NULL && *y_len > y_max))
+    return HAL_ERROR_RESULT_TOO_LONG;
+
+  if (x != NULL)
+    fp_to_unsigned_bin(unconst_fp_int(key->Q->x), x);
+
+  if (y != NULL)
+    fp_to_unsigned_bin(unconst_fp_int(key->Q->y), y);
+
+  return HAL_OK;
+}
+
+/*
+ * Clear a key.
+ */
+
+void hal_ecdsa_key_clear(hal_ecdsa_key_t *key)
+{
+  if (key != NULL)
+    memset(key, 0, sizeof(*key));
+}
+
+/*
+ * Load a public key from components, and validate that the public key
+ * really is on the named curve.
+ */
+
+hal_error_t hal_ecdsa_key_load_public(hal_ecdsa_key_t **key_,
+                                      void *keybuf, const size_t keybuf_len,
+                                      const hal_ecdsa_curve_t curve_,
+                                      const uint8_t * const x, const size_t x_len,
+                                      const uint8_t * const y, const size_t y_len)
+{
+  const ecdsa_curve_t * const curve = get_curve(curve_);
+  hal_ecdsa_key_t *key = keybuf;
+
+  if (key_ == NULL || key == NULL || keybuf_len < sizeof(*key) || curve == NULL || x == NULL || y == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  memset(keybuf, 0, keybuf_len);
+
+  key->type = HAL_ECDSA_PUBLIC;
+  key->curve = curve_;
+
+  fp_read_unsigned_bin(key->Q->x, unconst_uint8_t(x), x_len);
+  fp_read_unsigned_bin(key->Q->y, unconst_uint8_t(y), y_len);
+  fp_set(key->Q->z, 1);
+
+  if (!point_is_on_curve(key->Q, curve))
+    return HAL_ERROR_KEY_NOT_ON_CURVE;
+
+  *key_ = key;
+
+  return HAL_OK;
+}
+
+/*
+ * Load a private key from components.
+ *
+ * For extra paranoia, we could check Q == dG.
+ */
+
+hal_error_t hal_ecdsa_key_load_private(hal_ecdsa_key_t **key_,
+                                       void *keybuf, const size_t keybuf_len,
+                                       const hal_ecdsa_curve_t curve_,
+                                       const uint8_t * const x, const size_t x_len,
+                                       const uint8_t * const y, const size_t y_len,
+                                       const uint8_t * const d, const size_t d_len)
+{
+  hal_ecdsa_key_t *key = keybuf;
+  hal_error_t err;
+
+  if (d == NULL)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  if ((err = hal_ecdsa_key_load_public(key_, keybuf, keybuf_len, curve_, x, x_len, y, y_len)) != HAL_OK)
+    return err;
+
+  key->type = HAL_ECDSA_PRIVATE;
+  fp_read_unsigned_bin(key->d, unconst_uint8_t(d), d_len);
+  return HAL_OK;
+}
+
+/*
+ * Write private key in RFC 5915 ASN.1 DER format.
+ */
+
+hal_error_t hal_ecdsa_key_to_der(const hal_ecdsa_key_t * const key,
+                                 uint8_t *der, size_t *der_len, const size_t der_max)
+{
+  if (key == NULL || key->type != HAL_ECDSA_PRIVATE)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  const ecdsa_curve_t * const curve = get_curve(key->curve);
+  if (curve == NULL)
+    return HAL_ERROR_IMPOSSIBLE;
+
+  const size_t q_len  = fp_unsigned_bin_size(unconst_fp_int(curve->q));
+  const size_t d_len  = fp_unsigned_bin_size(unconst_fp_int(key->d));
+  const size_t Qx_len = fp_unsigned_bin_size(unconst_fp_int(key->Q->x));
+  const size_t Qy_len = fp_unsigned_bin_size(unconst_fp_int(key->Q->y));
+  assert(q_len >= d_len && q_len >= Qx_len && q_len >= Qy_len);
+
+  fp_int version[1];
+  fp_set(version, 1);
+
+  hal_error_t err;
+
+  size_t version_len, hlen, hlen2, hlen3, hlen4;
+
+  if ((err = hal_asn1_encode_integer(version,                           NULL, &version_len, 0)) != HAL_OK ||
+      (err = hal_asn1_encode_header(ASN1_OCTET_STRING, q_len,           NULL, &hlen2,       0)) != HAL_OK ||
+      (err = hal_asn1_encode_header(ASN1_EXPLICIT_0,   curve->oid_len,  NULL, &hlen3,       0)) != HAL_OK ||
+      (err = hal_asn1_encode_header(ASN1_EXPLICIT_1,   (q_len + 1) * 2, NULL, &hlen4,       0)) != HAL_OK)
+    return err;
+  
+  const size_t vlen = (version_len    +
+                       hlen2 + q_len +
+                       hlen3 + curve->oid_len +
+                       hlen4  + (q_len + 1) * 2);
+
+  if ((err = hal_asn1_encode_header(ASN1_SEQUENCE, vlen, der, &hlen, der_max)) != HAL_OK)
+    return err;
+
+  if (der_len != NULL)
+    *der_len = hlen + vlen;
+
+  if (der == NULL)
+    return HAL_OK;
+
+  uint8_t *d = der + hlen;
+  memset(d, 0, vlen);
+
+  if ((err = hal_asn1_encode_integer(version, d, NULL, der + der_max - d)) != HAL_OK)
+    return err;
+  d += version_len;
+
+  if ((err = hal_asn1_encode_header(ASN1_OCTET_STRING, q_len, d, NULL, der + der_max - d)) != HAL_OK)
+    return err;
+  d += hlen2;
+  fp_to_unsigned_bin(unconst_fp_int(key->d), d + q_len - d_len);
+  d += q_len;
+
+  if ((err = hal_asn1_encode_header(ASN1_EXPLICIT_0, curve->oid_len, d, NULL, der + der_max - d)) != HAL_OK)
+    return err;
+  d += hlen3;
+  memcpy(d, curve->oid, curve->oid_len);
+  d += curve->oid_len;
+
+  if ((err = hal_asn1_encode_header(ASN1_EXPLICIT_1, (q_len + 1) * 2, d, NULL, der + der_max - d)) != HAL_OK)
+    return err;
+  d += hlen4;
+  *d++ = 0x00;
+  *d++ = 0x04;
+  fp_to_unsigned_bin(unconst_fp_int(key->d), d + q_len - Qx_len);
+  d += q_len;
+  fp_to_unsigned_bin(unconst_fp_int(key->d), d + q_len - Qy_len);
+  d += q_len;
+
+  assert(d == der + der_max);
+
+  return HAL_OK;
+}
+
+size_t hal_ecdsa_key_to_der_len(const hal_ecdsa_key_t * const key)
+{
+  size_t len;
+  return hal_ecdsa_key_to_der(key, NULL, &len, 0) == HAL_OK ? len : 0;
+}
+
+/*
+ * Read private key in RFC 5915 ASN.1 DER format.
+ */
+
+hal_error_t hal_ecdsa_key_from_der(hal_ecdsa_key_t **key_,
+                                   void *keybuf, const size_t keybuf_len,
+                                   const uint8_t * const der, const size_t der_len)
+{
+  hal_ecdsa_key_t *key = keybuf;
+
+  if (key_ == NULL || key == NULL || keybuf_len < sizeof(*key))
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  memset(keybuf, 0, keybuf_len);
+  key->type = HAL_ECDSA_PRIVATE;
+
+  size_t hlen, vlen;
+  hal_error_t err;
+
+  if ((err = hal_asn1_decode_header(ASN1_SEQUENCE, der, der_len, &hlen, &vlen)) != HAL_OK)
+    return err;
+
+  const uint8_t * const der_end = der + hlen + vlen;
+  const uint8_t *d = der + hlen;
+  const ecdsa_curve_t *curve = NULL;
+  fp_int version[1];
+
+  if ((err = hal_asn1_decode_integer(version, d, &hlen, vlen)) != HAL_OK)
+    goto fail;
+  if (fp_cmp_d(version, 1) != FP_EQ)
+    lose(HAL_ERROR_ASN1_PARSE_FAILED);
+  d += hlen;
+
+  if ((err = hal_asn1_decode_header(ASN1_OCTET_STRING, d, der_end - d, &hlen, &vlen)) != HAL_OK)
+    return err;
+  d += hlen;
+  fp_read_unsigned_bin(key->d, unconst_uint8_t(d), vlen);
+  d += vlen;
+
+  if ((err = hal_asn1_decode_header(ASN1_EXPLICIT_0, d, der_end - d, &hlen, &vlen)) != HAL_OK)
+    return err;
+  d += hlen;
+  for (key->curve = (hal_ecdsa_curve_t) 0; (curve = get_curve(key->curve)) != NULL; key->curve++)
+    if (vlen == curve->oid_len && memcmp(d, curve->oid, vlen) == 0)
+      break;
+  if (curve == NULL)
+    lose(HAL_ERROR_ASN1_PARSE_FAILED);
+  d += vlen;
+  
+  if ((err = hal_asn1_decode_header(ASN1_EXPLICIT_1, d, der_end - d, &hlen, &vlen)) != HAL_OK)
+    return err;
+  d += hlen;
+  if (vlen < 4 || (vlen & 1) != 0 || *d++ != 0x00 || *d++ != 0x04)
+    lose(HAL_ERROR_ASN1_PARSE_FAILED);
+  vlen = vlen/2 - 1;
+  fp_read_unsigned_bin(key->Q->x, unconst_uint8_t(d), vlen);
+  d += vlen;
+  fp_read_unsigned_bin(key->Q->x, unconst_uint8_t(d), vlen);
+  d += vlen;
+
+  if (d != der_end)
+    lose(HAL_ERROR_ASN1_PARSE_FAILED);
+
+  return HAL_OK;
+
+ fail:
+  memset(keybuf, 0, keybuf_len);
+  return err;
+}
+
+hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key,
+                           const hal_hash_descriptor_t * const hash_descriptor,
+                           const uint8_t * const input, const size_t input_len,
+                           uint8_t *output, size_t *output_len, const size_t output_max)
+{
+  if (key == NULL || hash_descriptor == NULL || input == NULL ||
+      output == NULL || output_len == NULL || key->type != HAL_ECDSA_PRIVATE)
+    return HAL_ERROR_BAD_ARGUMENTS;
+
+  const ecdsa_curve_t * const curve = get_curve(key->curve);
+  if (curve == NULL)
+    return HAL_ERROR_IMPOSSIBLE;
+
+  fp_int k[1]; fp_init(k);
+  fp_int r[1]; fp_init(r);
+  fp_int s[1]; fp_init(s);
+  fp_int e[1]; fp_init(e);
+
+  fp_int * const n = unconst_fp_int(curve->n);
+  fp_int * const d = unconst_fp_int(key->d);
+
+  ec_point_t R[1];
+  memset(R, 0, sizeof(R));
+
+  hal_error_t err;
+
+#warning Should we be hashing here, or should API have caller do it?  What does PKCS 11 do for ECDSA?
+
+  /*
+   * Hash the input and load result into e.
+   */
+
+  {
+    uint8_t statebuf[hash_descriptor->hash_state_length];
+    uint8_t hashbuf[hash_descriptor->digest_length];
+    hal_hash_state_t state = { NULL };
+
+    if ((err = hal_hash_initialize(hash_descriptor, &state,
+                                   statebuf, sizeof(statebuf)))    != HAL_OK ||
+        (err = hal_hash_update(state, input, input_len))           != HAL_OK ||
+        (err = hal_hash_finalize(state, hashbuf, sizeof(hashbuf))) != HAL_OK)
+      return err;
+
+    fp_read_unsigned_bin(e, hashbuf, sizeof(hashbuf));
+  }
+
+  do {
+
+    /*
+     * Pick random curve point R, then calculate r = R.x % n.
+     * If r == 0, we can't use this point, so go try again.
+     */
+
+    if ((err = point_pick_random(curve, k, R)) != HAL_OK)
+      goto fail;
+
+    assert(point_is_on_curve(R, curve));
+
+    if (fp_mod(R->x, n, r) != FP_OKAY)
+      lose(HAL_ERROR_IMPOSSIBLE);
+
+    if (fp_iszero(r))
+      continue;
+
+    /*
+     * Calculate s = ((e + dr)/k) % n.
+     * If s == 0, we can't use this point, so go try again.
+     */
+
+    if (fp_mulmod (d, r, n, s) != FP_OKAY)
+      lose(HAL_ERROR_IMPOSSIBLE);
+
+    fp_add        (e, s, s);
+
+    if (fp_mod    (s, n, s)    != FP_OKAY ||
+        fp_invmod (k, n, k)    != FP_OKAY ||
+        fp_mulmod (s, k, n, s) != FP_OKAY)
+      lose(HAL_ERROR_IMPOSSIBLE);
+
+  } while (fp_iszero(s));
+
+  /*
+   * Final signature is ASN.1 DER encoding of SEQUENCE { INTEGER r, INTEGER s }.
+   */
+
+  size_t r_len, s_len;
+
+  if ((err = hal_asn1_encode_integer(r, NULL, &r_len, 0)) != HAL_OK ||
+      (err = hal_asn1_encode_integer(s, NULL, &s_len, 0)) != HAL_OK ||
+      (err = hal_asn1_encode_header(ASN1_SEQUENCE, r_len + s_len, output, output_len, output_max)) != HAL_OK)
+    goto fail;
+
+  uint8_t * const r_out = output + *output_len;
+  uint8_t * const s_out = r_out + r_len;
+  output_len += r_len + s_len;
+  assert(*output_len <= output_max);
+
+  if ((err = hal_asn1_encode_integer(r, r_out, NULL, output_max - (r_out - output))) != HAL_OK ||
+      (err = hal_asn1_encode_integer(s, s_out, NULL, output_max - (s_out - output))) != HAL_OK)
+    goto fail;
+
+  err = HAL_OK;
+
+ fail:
+  fp_zero(k); fp_zero(r); fp_zero(s); fp_zero(e);
+  memset(R, 0, sizeof(R));
+  return err;
+}
+
+hal_error_t hal_ecdsa_verify(const hal_ecdsa_key_t * const key,
+                             const hal_hash_descriptor_t * const hash_descriptor,
+                             const uint8_t * const input, const size_t input_len)
+{
+}
+
+/*
+ * Local variables:
+ * indent-tabs-mode: nil
+ * End:
+ */
diff --git a/ecdsa_curves.h b/ecdsa_curves.h
new file mode 100644
index 0000000..80896ec
--- /dev/null
+++ b/ecdsa_curves.h
@@ -0,0 +1,92 @@
+/*
+ * ecdsa_curves.h
+ * --------------
+ * Curve parameters for NIST P-256, P-384, and P-521 curves.
+ *
+ * At some point we may want to replace this file with one generated
+ * by a Python script, to make it easier to check the curve parameters.
+ *
+ * Authors: Rob Austein
+ * Copyright (c) 2015, SUNET
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+static const uint8_t p256_q[]  = { 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+				   0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF };
+static const uint8_t p256_b[]  = { 0x5A, 0xC6, 0x35, 0xD8, 0xAA, 0x3A, 0x93, 0xE7, 0xB3, 0xEB, 0xBD, 0x55, 0x76, 0x98, 0x86, 0xBC,
+				   0x65, 0x1D, 0x06, 0xB0, 0xCC, 0x53, 0xB0, 0xF6, 0x3B, 0xCE, 0x3C, 0x3E, 0x27, 0xD2, 0x60, 0x4B };
+static const uint8_t p256_Gx[] = { 0x6B, 0x17, 0xD1, 0xF2, 0xE1, 0x2C, 0x42, 0x47, 0xF8, 0xBC, 0xE6, 0xE5, 0x63, 0xA4, 0x40, 0xF2,
+				   0x77, 0x03, 0x7D, 0x81, 0x2D, 0xEB, 0x33, 0xA0, 0xF4, 0xA1, 0x39, 0x45, 0xD8, 0x98, 0xC2, 0x96 };
+static const uint8_t p256_Gy[] = { 0x4F, 0xE3, 0x42, 0xE2, 0xFE, 0x1A, 0x7F, 0x9B, 0x8E, 0xE7, 0xEB, 0x4A, 0x7C, 0x0F, 0x9E, 0x16,
+				   0x2B, 0xCE, 0x33, 0x57, 0x6B, 0x31, 0x5E, 0xCE, 0xCB, 0xB6, 0x40, 0x68, 0x37, 0xBF, 0x51, 0xF5 };
+static const uint8_t p256_n[]  = { 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
+				   0xBC, 0xE6, 0xFA, 0xAD, 0xA7, 0x17, 0x9E, 0x84, 0xF3, 0xB9, 0xCA, 0xC2, 0xFC, 0x63, 0x25, 0x51 };
+static const uint8_t p256_oid[] = { 0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07 };
+
+static const uint8_t p384_q[]  = { 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
+				   0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE,
+				   0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF };
+static const uint8_t p384_b[]  = { 0xB3, 0x31, 0x2F, 0xA7, 0xE2, 0x3E, 0xE7, 0xE4, 0x98, 0x8E, 0x05, 0x6B, 0xE3, 0xF8, 0x2D, 0x19,
+				   0x18, 0x1D, 0x9C, 0x6E, 0xFE, 0x81, 0x41, 0x12, 0x03, 0x14, 0x08, 0x8F, 0x50, 0x13, 0x87, 0x5A,
+				   0xC6, 0x56, 0x39, 0x8D, 0x8A, 0x2E, 0xD1, 0x9D, 0x2A, 0x85, 0xC8, 0xED, 0xD3, 0xEC, 0x2A, 0xEF };
+static const uint8_t p384_Gx[] = { 0xAA, 0x87, 0xCA, 0x22, 0xBE, 0x8B, 0x05, 0x37, 0x8E, 0xB1, 0xC7, 0x1E, 0xF3, 0x20, 0xAD, 0x74,
+				   0x6E, 0x1D, 0x3B, 0x62, 0x8B, 0xA7, 0x9B, 0x98, 0x59, 0xF7, 0x41, 0xE0, 0x82, 0x54, 0x2A, 0x38,
+				   0x55, 0x02, 0xF2, 0x5D, 0xBF, 0x55, 0x29, 0x6C, 0x3A, 0x54, 0x5E, 0x38, 0x72, 0x76, 0x0A, 0xB7 };
+static const uint8_t p384_Gy[] = { 0x36, 0x17, 0xDE, 0x4A, 0x96, 0x26, 0x2C, 0x6F, 0x5D, 0x9E, 0x98, 0xBF, 0x92, 0x92, 0xDC, 0x29,
+				   0xF8, 0xF4, 0x1D, 0xBD, 0x28, 0x9A, 0x14, 0x7C, 0xE9, 0xDA, 0x31, 0x13, 0xB5, 0xF0, 0xB8, 0xC0,
+				   0x0A, 0x60, 0xB1, 0xCE, 0x1D, 0x7E, 0x81, 0x9D, 0x7A, 0x43, 0x1D, 0x7C, 0x90, 0xEA, 0x0E, 0x5F };
+static const uint8_t p384_n[]  = { 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
+				   0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xC7, 0x63, 0x4D, 0x81, 0xF4, 0x37, 0x2D, 0xDF,
+				   0x58, 0x1A, 0x0D, 0xB2, 0x48, 0xB0, 0xA7, 0x7A, 0xEC, 0xEC, 0x19, 0x6A, 0xCC, 0xC5, 0x29, 0x73 };
+static const uint8_t p384_oid[] = { 0x2b, 0x81, 0x04, 0x00, 0x22 };
+
+static const uint8_t p521_q[]  = { 0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
+				   0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
+				   0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
+				   0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
+				   0xFF, 0xFF };
+static const uint8_t p521_b[]  = { 0x00, 0x51, 0x95, 0x3E, 0xB9, 0x61, 0x8E, 0x1C, 0x9A, 0x1F, 0x92, 0x9A, 0x21, 0xA0, 0xB6, 0x85,
+				   0x40, 0xEE, 0xA2, 0xDA, 0x72, 0x5B, 0x99, 0xB3, 0x15, 0xF3, 0xB8, 0xB4, 0x89, 0x91, 0x8E, 0xF1,
+				   0x09, 0xE1, 0x56, 0x19, 0x39, 0x51, 0xEC, 0x7E, 0x93, 0x7B, 0x16, 0x52, 0xC0, 0xBD, 0x3B, 0xB1,
+				   0xBF, 0x07, 0x35, 0x73, 0xDF, 0x88, 0x3D, 0x2C, 0x34, 0xF1, 0xEF, 0x45, 0x1F, 0xD4, 0x6B, 0x50,
+				   0x3F, 0x00 };
+static const uint8_t p521_Gx[] = { 0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
+				   0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
+				   0xFF, 0xFA, 0x51, 0x86, 0x87, 0x83, 0xBF, 0x2F, 0x96, 0x6B, 0x7F, 0xCC, 0x01, 0x48, 0xF7, 0x09,
+				   0xA5, 0xD0, 0x3B, 0xB5, 0xC9, 0xB8, 0x89, 0x9C, 0x47, 0xAE, 0xBB, 0x6F, 0xB7, 0x1E, 0x91, 0x38,
+				   0x64, 0x09 };
+static const uint8_t p521_Gy[] = { 0x00, 0xC6, 0x85, 0x8E, 0x06, 0xB7, 0x04, 0x04, 0xE9, 0xCD, 0x9E, 0x3E, 0xCB, 0x66, 0x23, 0x95,
+				   0xB4, 0x42, 0x9C, 0x64, 0x81, 0x39, 0x05, 0x3F, 0xB5, 0x21, 0xF8, 0x28, 0xAF, 0x60, 0x6B, 0x4D,
+				   0x3D, 0xBA, 0xA1, 0x4B, 0x5E, 0x77, 0xEF, 0xE7, 0x59, 0x28, 0xFE, 0x1D, 0xC1, 0x27, 0xA2, 0xFF,
+				   0xA8, 0xDE, 0x33, 0x48, 0xB3, 0xC1, 0x85, 0x6A, 0x42, 0x9B, 0xF9, 0x7E, 0x7E, 0x31, 0xC2, 0xE5,
+				   0xBD, 0x66 };
+static const uint8_t p521_n[]  = { 0x01, 0x18, 0x39, 0x29, 0x6A, 0x78, 0x9A, 0x3B, 0xC0, 0x04, 0x5C, 0x8A, 0x5F, 0xB4, 0x2C, 0x7D,
+				   0x1B, 0xD9, 0x98, 0xF5, 0x44, 0x49, 0x57, 0x9B, 0x44, 0x68, 0x17, 0xAF, 0xBD, 0x17, 0x27, 0x3E,
+				   0x66, 0x2C, 0x97, 0xEE, 0x72, 0x99, 0x5E, 0xF4, 0x26, 0x40, 0xC5, 0x50, 0xB9, 0x01, 0x3F, 0xAD,
+				   0x07, 0x61, 0x35, 0x3C, 0x70, 0x86, 0xA2, 0x72, 0xC2, 0x40, 0x88, 0xBE, 0x94, 0x76, 0x9F, 0xD1,
+				   0x66, 0x50 };
+static const uint8_t p521_oid[] = { 0x2b, 0x81, 0x04, 0x00, 0x23 };
diff --git a/hal.h b/hal.h
index 8b731d4..9e7bd67 100644
--- a/hal.h
+++ b/hal.h
@@ -446,6 +446,7 @@
   DEFINE_HAL_ERROR(HAL_ERROR_ALLOCATION_FAILURE,        "Memory allocation failed")                     \
   DEFINE_HAL_ERROR(HAL_ERROR_RESULT_TOO_LONG,           "Result too long for buffer")                   \
   DEFINE_HAL_ERROR(HAL_ERROR_ASN1_PARSE_FAILED,         "ASN.1 parse failed")                           \
+  DEFINE_HAL_ERROR(HAL_ERROR_KEY_NOT_ON_CURVE,          "EC key is not on its purported curve")         \
   END_OF_HAL_ERROR_LIST
 
 /* Marker to forestall silly line continuation errors */
@@ -671,6 +672,67 @@ extern hal_error_t hal_rsa_key_from_der(hal_rsa_key_t *key,
                                         void *keybuf, const size_t keybuf_len,
                                         const uint8_t * const der, const size_t der_len);
 
+/*
+ * ECDSA.
+ */
+
+typedef enum { HAL_ECDSA_PRIVATE, HAL_ECDSA_PUBLIC } hal_ecdsa_key_type_t;
+
+typedef enum { HAL_ECDSA_CURVE_P256, HAL_ECDSA_CURVE_P384, HAL_ECDSA_CURVE_P521 } hal_ecdsa_curve_t;
+
+typedef struct hal_ecdsa_key hal_ecdsa_key_t;
+
+extern const size_t hal_ecdsa_key_t_size;
+
+extern void hal_ecdsa_set_debug(const int onoff);
+
+extern hal_error_t hal_ecdsa_key_load_private(hal_ecdsa_key_t **key,
+                                              void *keybuf, const size_t keybuf_len,
+                                              const hal_ecdsa_curve_t curve,
+                                              const uint8_t * const x, const size_t x_len,
+                                              const uint8_t * const y, const size_t y_len,
+                                              const uint8_t * const d, const size_t d_len);
+
+extern hal_error_t hal_ecdsa_key_load_public(hal_ecdsa_key_t **key,
+                                             void *keybuf, const size_t keybuf_len,
+                                             const hal_ecdsa_curve_t curve,
+                                             const uint8_t * const x, const size_t x_len,
+                                             const uint8_t * const y, const size_t y_len);
+
+extern hal_error_t hal_ecdsa_key_get_type(const hal_ecdsa_key_t * const key,
+                                          hal_ecdsa_key_type_t *key_type);
+
+extern hal_error_t hal_ecdsa_key_get_curve(const hal_ecdsa_key_t * const key,
+                                           hal_ecdsa_curve_t *curve);
+
+extern hal_error_t hal_ecdsa_key_get_public(const hal_ecdsa_key_t * const key,
+                                            uint8_t *x, size_t *x_len, const size_t x_max,
+                                            uint8_t *y, size_t *y_len, const size_t y_max);
+
+extern void hal_ecdsa_key_clear(hal_ecdsa_key_t *key);
+
+extern hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key,
+                                  const hal_hash_descriptor_t * const hash_descriptor,
+                                  const uint8_t * const input, const size_t input_len,
+                                  uint8_t *output, size_t *output_len, const size_t output_max);
+
+extern hal_error_t hal_ecdsa_verify(const hal_ecdsa_key_t * const key,
+                                    const hal_hash_descriptor_t * const hash_descriptor,
+                                    const uint8_t * const input, const size_t input_len);
+
+extern hal_error_t hal_ecdsa_key_gen(hal_ecdsa_key_t **key,
+                                     void *keybuf, const size_t keybuf_len,
+                                     const hal_ecdsa_curve_t curve);
+
+extern hal_error_t hal_ecdsa_key_to_der(const hal_ecdsa_key_t * const key,
+                                        uint8_t *der, size_t *der_len, const size_t der_max);
+
+extern size_t hal_ecdsa_key_to_der_len(const hal_ecdsa_key_t * const key);
+
+extern hal_error_t hal_ecdsa_key_from_der(hal_ecdsa_key_t **key,
+                                          void *keybuf, const size_t keybuf_len,
+                                          const uint8_t * const der, const size_t der_len);
+
 #endif /* _HAL_H_ */
 
 /*