ecc: Fix a minor flaw in the generation of K.
[libgcrypt.git] / cipher / ecc.c
index ae55f8c..63ee2d0 100644 (file)
@@ -1,22 +1,22 @@
 /* ecc.c  -  Elliptic Curve Cryptography
  Copyright (C) 2007, 2008, 2010, 2011 Free Software Foundation, Inc.
-
-   This file is part of Libgcrypt.
-
-   Libgcrypt 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.
-
-   Libgcrypt 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 this program; if not, write to the Free Software
-   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  USA.  */
* Copyright (C) 2007, 2008, 2010, 2011 Free Software Foundation, Inc.
+ * Copyright (C) 2013 g10 Code GmbH
+ *
+ * This file is part of Libgcrypt.
+ *
+ * Libgcrypt 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.
+ *
+ * Libgcrypt 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 this program; if not, see <http://www.gnu.org/licenses/>.
+ */
 
 /* This code is originally based on the Patch 0.1.6 for the gnupg
    1.4.x branch as retrieved on 2007-03-21 from
   - In mpi/ec.c we use mpi_powm for x^2 mod p: Either implement a
     special case in mpi_powm or check whether mpi_mulm is faster.
 
-  - Decide whether we should hide the mpi_point_t definition.
+  - Split this up into several files.  For example the curve
+    management and gcry_mpi_ec_new are independent of the actual ECDSA
+    implementation.  This will also help to support optimized versions
+    of some curves.
+
 */
 
 
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+#include <errno.h>
 
 #include "g10lib.h"
 #include "mpi.h"
 #include "cipher.h"
+#include "context.h"
+#include "ec-context.h"
+#include "pubkey-internal.h"
 
 /* Definition of a curve.  */
 typedef struct
 {
-  gcry_mpi_t p;   /* Prime specifying the field GF(p).  */
-  gcry_mpi_t a;   /* First coefficient of the Weierstrass equation.  */
-  gcry_mpi_t b;   /* Second coefficient of the Weierstrass equation.  */
-  mpi_point_t G;  /* Base point (generator).  */
-  gcry_mpi_t n;   /* Order of G.  */
+  gcry_mpi_t p;         /* Prime specifying the field GF(p).  */
+  gcry_mpi_t a;         /* First coefficient of the Weierstrass equation.  */
+  gcry_mpi_t b;         /* Second coefficient of the Weierstrass equation.  */
+  mpi_point_struct G;   /* Base point (generator).  */
+  gcry_mpi_t n;         /* Order of G.  */
+  const char *name;     /* Name of the curve or NULL.  */
 } elliptic_curve_t;
 
 
 typedef struct
 {
   elliptic_curve_t E;
-  mpi_point_t Q;  /* Q = [d]G  */
+  mpi_point_struct Q; /* Q = [d]G  */
 } ECC_public_key;
 
 typedef struct
 {
   elliptic_curve_t E;
-  mpi_point_t Q;
+  mpi_point_struct Q;
   gcry_mpi_t d;
 } ECC_secret_key;
 
@@ -95,19 +104,24 @@ static const struct
     { "NIST P-192", "1.2.840.10045.3.1.1" }, /* X9.62 OID  */
     { "NIST P-192", "prime192v1" },          /* X9.62 name.  */
     { "NIST P-192", "secp192r1"  },          /* SECP name.  */
+    { "NIST P-192", "nistp192"   },          /* rfc5656.  */
 
     { "NIST P-224", "secp224r1" },
     { "NIST P-224", "1.3.132.0.33" },        /* SECP OID.  */
+    { "NIST P-224", "nistp224"   },          /* rfc5656.  */
 
     { "NIST P-256", "1.2.840.10045.3.1.7" }, /* From NIST SP 800-78-1.  */
     { "NIST P-256", "prime256v1" },
     { "NIST P-256", "secp256r1"  },
+    { "NIST P-256", "nistp256"   },          /* rfc5656.  */
 
     { "NIST P-384", "secp384r1" },
     { "NIST P-384", "1.3.132.0.34" },
+    { "NIST P-384", "nistp384"   },          /* rfc5656.  */
 
     { "NIST P-521", "secp521r1" },
     { "NIST P-521", "1.3.132.0.35" },
+    { "NIST P-521", "nistp521"   },          /* rfc5656.  */
 
     { "brainpoolP160r1", "1.3.36.3.3.2.8.1.1.1" },
     { "brainpoolP192r1", "1.3.36.3.3.2.8.1.1.3" },
@@ -286,13 +300,12 @@ static void (*progress_cb) (void *, const char*, int, int, int);
 static void *progress_cb_data;
 
 
-#define point_init(a)  _gcry_mpi_ec_point_init ((a))
-#define point_free(a)  _gcry_mpi_ec_point_free ((a))
+#define point_init(a)  _gcry_mpi_point_init ((a))
+#define point_free(a)  _gcry_mpi_point_free_parts ((a))
 
 
 \f
 /* Local prototypes. */
-static gcry_mpi_t gen_k (gcry_mpi_t p, int security_level);
 static void test_keys (ECC_secret_key * sk, unsigned int nbits);
 static int check_secret_key (ECC_secret_key * sk);
 static gpg_err_code_t sign (gcry_mpi_t input, ECC_secret_key *skey,
@@ -327,7 +340,7 @@ _gcry_register_pk_ecc_progress (void (*cb) (void *, const char *,
 
 /* Set the value from S into D.  */
 static void
-point_set (mpi_point_t *d, mpi_point_t *s)
+point_set (mpi_point_t d, mpi_point_t s)
 {
   mpi_set (d->x, s->x);
   mpi_set (d->y, s->y);
@@ -350,29 +363,6 @@ curve_free (elliptic_curve_t *E)
 
 
 /*
- * Release a PK object.
- */
-static void
-ecc_pk_free (ECC_public_key *pk)
-{
-  point_free (&pk->Q);
-  curve_free (&pk->E);
-}
-
-
-/*
- * Release a SK object.
- */
-static void
-ecc_sk_free (ECC_secret_key *sk)
-{
-  point_free (&sk->Q);
-  curve_free (&sk->E);
-  mpi_free (sk->d);  sk->d = NULL;
-}
-
-
-/*
  * Return a copy of a curve object.
  */
 static elliptic_curve_t
@@ -433,45 +423,26 @@ gen_y_2 (gcry_mpi_t x, elliptic_curve_t *base)
 }
 
 
-/* Generate a random secret scalar k with an order of p
-
-   At the beginning this was identical to the code is in elgamal.c.
-   Later imporved by mmr.   Further simplified by wk.  */
-static gcry_mpi_t
-gen_k (gcry_mpi_t p, int security_level)
-{
-  gcry_mpi_t k;
-  unsigned int nbits;
-
-  nbits = mpi_get_nbits (p);
-  k = mpi_snew (nbits);
-  if (DBG_CIPHER)
-    log_debug ("choosing a random k of %u bits\n", nbits);
-
-  gcry_mpi_randomize (k, nbits, security_level);
-
-  mpi_mod (k, k, p);  /*  k = k mod p  */
-
-  return k;
-}
-
-
 /* Generate the crypto system setup.  This function takes the NAME of
    a curve or the desired number of bits and stores at R_CURVE the
-   parameters of the named curve or those of a suitable curve.  The
-   chosen number of bits is stored on R_NBITS.  */
+   parameters of the named curve or those of a suitable curve.  If
+   R_NBITS is not NULL, the chosen number of bits is stored there.  */
 static gpg_err_code_t
 fill_in_curve (unsigned int nbits, const char *name,
                elliptic_curve_t *curve, unsigned int *r_nbits)
 {
   int idx, aliasno;
+  const char *resname = NULL; /* Set to a found curve name.  */
 
   if (name)
     {
-      /* First check nor native curves.  */
+      /* First check our native curves.  */
       for (idx = 0; domain_parms[idx].desc; idx++)
         if (!strcmp (name, domain_parms[idx].desc))
-          break;
+          {
+            resname = domain_parms[idx].desc;
+            break;
+          }
       /* If not found consult the alias table.  */
       if (!domain_parms[idx].desc)
         {
@@ -483,7 +454,10 @@ fill_in_curve (unsigned int nbits, const char *name,
               for (idx = 0; domain_parms[idx].desc; idx++)
                 if (!strcmp (curve_aliases[aliasno].name,
                              domain_parms[idx].desc))
-                  break;
+                  {
+                    resname = domain_parms[idx].desc;
+                    break;
+                  }
             }
         }
     }
@@ -502,7 +476,8 @@ fill_in_curve (unsigned int nbits, const char *name,
   if (fips_mode () && !domain_parms[idx].fips )
     return GPG_ERR_NOT_SUPPORTED;
 
-  *r_nbits = domain_parms[idx].nbits;
+  if (r_nbits)
+    *r_nbits = domain_parms[idx].nbits;
   curve->p = scanval (domain_parms[idx].p);
   curve->a = scanval (domain_parms[idx].a);
   curve->b = scanval (domain_parms[idx].b);
@@ -510,6 +485,7 @@ fill_in_curve (unsigned int nbits, const char *name,
   curve->G.x = scanval (domain_parms[idx].g_x);
   curve->G.y = scanval (domain_parms[idx].g_y);
   curve->G.z = mpi_alloc_set_ui (1);
+  curve->name = resname;
 
   return 0;
 }
@@ -523,15 +499,18 @@ static gpg_err_code_t
 generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name,
               int transient_key,
               gcry_mpi_t g_x, gcry_mpi_t g_y,
-              gcry_mpi_t q_x, gcry_mpi_t q_y)
+              gcry_mpi_t q_x, gcry_mpi_t q_y,
+              const char **r_usedcurve)
 {
   gpg_err_code_t err;
   elliptic_curve_t E;
   gcry_mpi_t d;
-  mpi_point_t Q;
+  mpi_point_struct Q;
   mpi_ec_t ctx;
   gcry_random_level_t random_level;
 
+  *r_usedcurve = NULL;
+
   err = fill_in_curve (nbits, name, &E, &nbits);
   if (err)
     return err;
@@ -544,18 +523,17 @@ generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name,
       log_mpidump ("ecgen curve  n", E.n);
       log_mpidump ("ecgen curve Gx", E.G.x);
       log_mpidump ("ecgen curve Gy", E.G.y);
-      log_mpidump ("ecgen cyrve Gz", E.G.z);
+      log_mpidump ("ecgen curve Gz", E.G.z);
+      if (E.name)
+        log_debug   ("ecgen curve used: %s\n", E.name);
     }
 
   random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
-  if (DBG_CIPHER)
-    log_debug ("choosing a random x of size %u%s\n", nbits,
-               transient_key? " (transient-key)":"");
-  d = gen_k (E.n, random_level);
+  d = _gcry_dsa_gen_k (E.n, random_level);
 
   /* Compute Q.  */
   point_init (&Q);
-  ctx = _gcry_mpi_ec_init (E.p, E.a);
+  ctx = _gcry_mpi_ec_p_internal_new (E.p, E.a);
   _gcry_mpi_ec_mul_point (&Q, d, &E.G, ctx);
 
   /* Copy the stuff to the key structures. */
@@ -566,24 +544,77 @@ generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name,
   point_set (&sk->E.G, &E.G);
   sk->E.n = mpi_copy (E.n);
   point_init (&sk->Q);
-  point_set (&sk->Q, &Q);
-  sk->d    = mpi_copy (d);
+
+  /* We want the Q=(x,y) be a "compliant key" in terms of the
+   * http://tools.ietf.org/html/draft-jivsov-ecc-compact, which simply
+   * means that we choose either Q=(x,y) or -Q=(x,p-y) such that we
+   * end up with the min(y,p-y) as the y coordinate.  Such a public
+   * key allows the most efficient compression: y can simply be
+   * dropped because we know that it's a minimum of the two
+   * possibilities without any loss of security.  */
+  {
+    gcry_mpi_t x, p_y, y;
+    const unsigned int nbits = mpi_get_nbits (E.p);
+
+    x = mpi_new (nbits);
+    p_y = mpi_new (nbits);
+    y = mpi_new (nbits);
+
+    if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx))
+      log_fatal ("ecgen: Failed to get affine coordinates for Q\n");
+
+    mpi_sub( p_y, E.p, y );    /* p_y = p-y */
+
+    if (mpi_cmp( p_y /*p-y*/, y ) < 0) /* is p-y < p ? */
+      {
+        gcry_mpi_t z = mpi_copy (mpi_const (MPI_C_ONE));
+
+        /* log_mpidump ("ecgen p-y", p_y); */
+        /* log_mpidump ("ecgen y  ", y); */
+        /* log_debug   ("ecgen will replace y with p-y\n"); */
+        /* log_mpidump ("ecgen d before", d); */
+
+        /* We need to end up with -Q; this assures that new Q's y is
+           the smallest one */
+        sk->d = mpi_new (nbits);
+        mpi_sub (sk->d, E.n, d);  /* d = order-d */
+        /* log_mpidump ("ecgen d after ", sk->d); */
+       gcry_mpi_point_set (&sk->Q, x, p_y/*p-y*/, z);  /* Q = -Q */
+        if (DBG_CIPHER)
+          log_debug ("ecgen converted Q to a compliant point\n");
+        mpi_free (z);
+      }
+    else
+      {
+        /* No change is needed exactly 50% of the time: just copy. */
+        sk->d = mpi_copy (d);
+       point_set (&sk->Q, &Q);
+        if (DBG_CIPHER)
+          log_debug ("ecgen didn't need to convert Q to a compliant point\n");
+      }
+    mpi_free (x);
+    mpi_free (p_y);
+    mpi_free (y);
+  }
+
   /* We also return copies of G and Q in affine coordinates if
      requested.  */
   if (g_x && g_y)
     {
       if (_gcry_mpi_ec_get_affine (g_x, g_y, &sk->E.G, ctx))
-        log_fatal ("ecgen: Failed to get affine coordinates\n");
+        log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "G");
     }
   if (q_x && q_y)
     {
       if (_gcry_mpi_ec_get_affine (q_x, q_y, &sk->Q, ctx))
-        log_fatal ("ecgen: Failed to get affine coordinates\n");
+        log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "Q");
     }
   _gcry_mpi_ec_free (ctx);
 
   point_free (&Q);
   mpi_free (d);
+
+  *r_usedcurve = E.name;
   curve_free (&E);
 
   /* Now we can test our keys (this should never fail!).  */
@@ -604,7 +635,7 @@ test_keys (ECC_secret_key *sk, unsigned int nbits)
 {
   ECC_public_key pk;
   gcry_mpi_t test = mpi_new (nbits);
-  mpi_point_t R_;
+  mpi_point_struct R_;
   gcry_mpi_t c = mpi_new (nbits);
   gcry_mpi_t out = mpi_new (nbits);
   gcry_mpi_t r = mpi_new (nbits);
@@ -632,7 +663,8 @@ test_keys (ECC_secret_key *sk, unsigned int nbits)
   if (DBG_CIPHER)
     log_debug ("ECDSA operation: sign, verify ok.\n");
 
-  ecc_pk_free (&pk);
+  point_free (&pk.Q);
+  curve_free (&pk.E);
 
   point_free (&R_);
   mpi_free (s);
@@ -650,47 +682,48 @@ test_keys (ECC_secret_key *sk, unsigned int nbits)
 static int
 check_secret_key (ECC_secret_key * sk)
 {
-  mpi_point_t Q;
-  gcry_mpi_t y_2, y2 = mpi_alloc (0);
-  mpi_ec_t ctx;
+  int rc = 1;
+  mpi_point_struct Q;
+  gcry_mpi_t y_2, y2;
+  mpi_ec_t ctx = NULL;
+
+  point_init (&Q);
 
   /* ?primarity test of 'p' */
   /*  (...) //!! */
   /* G in E(F_p) */
   y_2 = gen_y_2 (sk->E.G.x, &sk->E);   /*  y^2=x^3+a*x+b */
+  y2 = mpi_alloc (0);
   mpi_mulm (y2, sk->E.G.y, sk->E.G.y, sk->E.p);      /*  y^2=y*y */
   if (mpi_cmp (y_2, y2))
     {
       if (DBG_CIPHER)
         log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n");
-      return (1);
+      goto leave;
     }
   /* G != PaI */
   if (!mpi_cmp_ui (sk->E.G.z, 0))
     {
       if (DBG_CIPHER)
         log_debug ("Bad check: 'G' cannot be Point at Infinity!\n");
-      return (1);
+      goto leave;
     }
 
-  point_init (&Q);
-  ctx = _gcry_mpi_ec_init (sk->E.p, sk->E.a);
+  ctx = _gcry_mpi_ec_p_internal_new (sk->E.p, sk->E.a);
+
   _gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ctx);
   if (mpi_cmp_ui (Q.z, 0))
     {
       if (DBG_CIPHER)
         log_debug ("check_secret_key: E is not a curve of order n\n");
-      point_free (&Q);
-      _gcry_mpi_ec_free (ctx);
-      return 1;
+      goto leave;
     }
   /* pubkey cannot be PaI */
   if (!mpi_cmp_ui (sk->Q.z, 0))
     {
       if (DBG_CIPHER)
         log_debug ("Bad check: Q can not be a Point at Infinity!\n");
-      _gcry_mpi_ec_free (ctx);
-      return (1);
+      goto leave;
     }
   /* pubkey = [d]G over E */
   _gcry_mpi_ec_mul_point (&Q, sk->d, &sk->E.G, ctx);
@@ -699,12 +732,16 @@ check_secret_key (ECC_secret_key * sk)
       if (DBG_CIPHER)
         log_debug
           ("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
-      _gcry_mpi_ec_free (ctx);
-      return (1);
+      goto leave;
     }
+  rc = 0; /* Okay.  */
+
+ leave:
   _gcry_mpi_ec_free (ctx);
+  mpi_free (y2);
+  mpi_free (y_2);
   point_free (&Q);
-  return 0;
+  return rc;
 }
 
 
@@ -717,7 +754,7 @@ sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s)
 {
   gpg_err_code_t err = 0;
   gcry_mpi_t k, dr, sum, k_1, x;
-  mpi_point_t I;
+  mpi_point_struct I;
   mpi_ec_t ctx;
 
   if (DBG_CIPHER)
@@ -733,7 +770,7 @@ sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s)
   mpi_set_ui (s, 0);
   mpi_set_ui (r, 0);
 
-  ctx = _gcry_mpi_ec_init (skey->E.p, skey->E.a);
+  ctx = _gcry_mpi_ec_p_internal_new (skey->E.p, skey->E.a);
 
   while (!mpi_cmp_ui (s, 0)) /* s == 0 */
     {
@@ -744,7 +781,7 @@ sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s)
              do_while because we want to keep the value of R even if S
              has to be recomputed.  */
           mpi_free (k);
-          k = gen_k (skey->E.n, GCRY_STRONG_RANDOM);
+          k = _gcry_dsa_gen_k (skey->E.n, GCRY_STRONG_RANDOM);
           _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx);
           if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
             {
@@ -788,7 +825,7 @@ verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s)
 {
   gpg_err_code_t err = 0;
   gcry_mpi_t h, h1, h2, x, y;
-  mpi_point_t Q, Q1, Q2;
+  mpi_point_struct Q, Q1, Q2;
   mpi_ec_t ctx;
 
   if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
@@ -805,7 +842,7 @@ verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s)
   point_init (&Q1);
   point_init (&Q2);
 
-  ctx = _gcry_mpi_ec_init (pkey->E.p, pkey->E.a);
+  ctx = _gcry_mpi_ec_p_internal_new (pkey->E.p, pkey->E.a);
 
   /* h  = s^(-1) (mod n) */
   mpi_invm (h, s, pkey->E.n);
@@ -851,11 +888,11 @@ verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s)
     {
       if (DBG_CIPHER)
         {
-          log_mpidump ("   x", x);
-          log_mpidump ("   y", y);
-          log_mpidump ("   r", r);
-          log_mpidump ("   s", s);
-          log_debug ("ecc verify: Not verified (x != y)\n");
+          log_mpidump ("     x", x);
+          log_mpidump ("     y", y);
+          log_mpidump ("     r", r);
+          log_mpidump ("     s", s);
+          log_debug ("ecc verify: Not verified\n");
         }
       err = GPG_ERR_BAD_SIGNATURE;
       goto leave;
@@ -920,10 +957,31 @@ ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p)
 }
 
 
+/* Convert POINT into affine coordinates using the context CTX and
+   return a newly allocated MPI.  If the conversion is not possible
+   NULL is returned.  This function won't print an error message.  */
+gcry_mpi_t
+_gcry_mpi_ec_ec2os (gcry_mpi_point_t point, mpi_ec_t ectx)
+{
+  gcry_mpi_t g_x, g_y, result;
+
+  g_x = mpi_new (0);
+  g_y = mpi_new (0);
+  if (_gcry_mpi_ec_get_affine (g_x, g_y, point, ectx))
+    result = NULL;
+  else
+    result = ec2os (g_x, g_y, ectx->p);
+  mpi_free (g_x);
+  mpi_free (g_y);
+
+  return result;
+}
+
+
 /* RESULT must have been initialized and is set on success to the
    point given by VALUE.  */
 static gcry_error_t
-os2ec (mpi_point_t *result, gcry_mpi_t value)
+os2ec (mpi_point_t result, gcry_mpi_t value)
 {
   gcry_error_t err;
   size_t n;
@@ -992,10 +1050,10 @@ ecc_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
   char *curve_name = NULL;
   gcry_sexp_t l1;
   int transient_key = 0;
+  const char *usedcurve = NULL;
 
   (void)algo;
   (void)evalue;
-  (void)r_extrainfo;
 
   if (genparms)
     {
@@ -1026,10 +1084,13 @@ ecc_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
   g_y = mpi_new (0);
   q_x = mpi_new (0);
   q_y = mpi_new (0);
-  ec = generate_key (&sk, nbits, curve_name, transient_key, g_x, g_y, q_x, q_y);
+  ec = generate_key (&sk, nbits, curve_name, transient_key, g_x, g_y, q_x, q_y,
+                     &usedcurve);
   gcry_free (curve_name);
   if (ec)
     return ec;
+  if (usedcurve)  /* Fixme: No error return checking.  */
+    gcry_sexp_build (r_extrainfo, NULL, "(curve %s)", usedcurve);
 
   skey[0] = sk.E.p;
   skey[1] = sk.E.a;
@@ -1050,7 +1111,7 @@ ecc_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
   /* Make an empty list of factors.  */
   *retfactors = gcry_calloc ( 1, sizeof **retfactors );
   if (!*retfactors)
-    return gpg_err_code_from_syserror ();
+    return gpg_err_code_from_syserror ();  /* Fixme: relase mem?  */
 
   if (DBG_CIPHER)
     {
@@ -1076,7 +1137,7 @@ ecc_generate (int algo, unsigned int nbits, unsigned long evalue,
 }
 
 
-/* Return the parameters of the curve NAME.  */
+/* Return the parameters of the curve NAME in an MPI array.  */
 static gcry_err_code_t
 ecc_get_param (const char *name, gcry_mpi_t *pkey)
 {
@@ -1092,7 +1153,7 @@ ecc_get_param (const char *name, gcry_mpi_t *pkey)
 
   g_x = mpi_new (0);
   g_y = mpi_new (0);
-  ctx = _gcry_mpi_ec_init (E.p, E.a);
+  ctx = _gcry_mpi_ec_p_internal_new (E.p, E.a);
   if (_gcry_mpi_ec_get_affine (g_x, g_y, &E.G, ctx))
     log_fatal ("ecc get param: Failed to get affine coordinates\n");
   _gcry_mpi_ec_free (ctx);
@@ -1112,6 +1173,113 @@ ecc_get_param (const char *name, gcry_mpi_t *pkey)
 }
 
 
+/* Return the parameters of the curve NAME as an S-expression.  */
+static gcry_sexp_t
+ecc_get_param_sexp (const char *name)
+{
+  gcry_mpi_t pkey[6];
+  gcry_sexp_t result;
+  int i;
+
+  if (ecc_get_param (name, pkey))
+    return NULL;
+
+  if (gcry_sexp_build (&result, NULL,
+                       "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)))",
+                       pkey[0], pkey[1], pkey[2], pkey[3], pkey[4]))
+    result = NULL;
+
+  for (i=0; pkey[i]; i++)
+    gcry_mpi_release (pkey[i]);
+
+  return result;
+}
+
+
+/* Return the name matching the parameters in PKEY.  */
+static const char *
+ecc_get_curve (gcry_mpi_t *pkey, int iterator, unsigned int *r_nbits)
+{
+  gpg_err_code_t err;
+  elliptic_curve_t E;
+  int idx;
+  gcry_mpi_t tmp;
+  const char *result = NULL;
+
+  if (r_nbits)
+    *r_nbits = 0;
+
+  if (!pkey)
+    {
+      idx = iterator;
+      if (idx >= 0 && idx < DIM (domain_parms))
+        {
+          result = domain_parms[idx].desc;
+          if (r_nbits)
+            *r_nbits = domain_parms[idx].nbits;
+        }
+      return result;
+    }
+
+  if (!pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4])
+    return NULL;
+
+  E.p = pkey[0];
+  E.a = pkey[1];
+  E.b = pkey[2];
+  point_init (&E.G);
+  err = os2ec (&E.G, pkey[3]);
+  if (err)
+    {
+      point_free (&E.G);
+      return NULL;
+    }
+  E.n = pkey[4];
+
+  for (idx = 0; domain_parms[idx].desc; idx++)
+    {
+      tmp = scanval (domain_parms[idx].p);
+      if (!mpi_cmp (tmp, E.p))
+        {
+          mpi_free (tmp);
+          tmp = scanval (domain_parms[idx].a);
+          if (!mpi_cmp (tmp, E.a))
+            {
+              mpi_free (tmp);
+              tmp = scanval (domain_parms[idx].b);
+              if (!mpi_cmp (tmp, E.b))
+                {
+                  mpi_free (tmp);
+                  tmp = scanval (domain_parms[idx].n);
+                  if (!mpi_cmp (tmp, E.n))
+                    {
+                      mpi_free (tmp);
+                      tmp = scanval (domain_parms[idx].g_x);
+                      if (!mpi_cmp (tmp, E.G.x))
+                        {
+                          mpi_free (tmp);
+                          tmp = scanval (domain_parms[idx].g_y);
+                          if (!mpi_cmp (tmp, E.G.y))
+                            {
+                              result = domain_parms[idx].desc;
+                              if (r_nbits)
+                                *r_nbits = domain_parms[idx].nbits;
+                              break;
+                            }
+                        }
+                    }
+                }
+            }
+        }
+      mpi_free (tmp);
+    }
+
+  point_free (&E.G);
+
+  return result;
+}
+
+
 static gcry_err_code_t
 ecc_check_secret_key (int algo, gcry_mpi_t *skey)
 {
@@ -1168,7 +1336,7 @@ ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
   (void)algo;
 
   if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
-      || !skey[5] || !skey[6] )
+      || !skey[6] )
     return GPG_ERR_BAD_MPI;
 
   sk.E.p = skey[0];
@@ -1182,14 +1350,7 @@ ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
       return err;
     }
   sk.E.n = skey[4];
-  point_init (&sk.Q);
-  err = os2ec (&sk.Q, skey[5]);
-  if (err)
-    {
-      point_free (&sk.E.G);
-      point_free (&sk.Q);
-      return err;
-    }
+  /* Note: We don't have any need for Q here.  */
   sk.d = skey[6];
 
   resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
@@ -1202,7 +1363,6 @@ ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
       resarr[0] = NULL; /* Mark array as released.  */
     }
   point_free (&sk.E.G);
-  point_free (&sk.Q);
   return err;
 }
 
@@ -1314,11 +1474,11 @@ ecc_encrypt_raw (int algo, gcry_mpi_t *resarr, gcry_mpi_t k,
       return err;
     }
 
-  ctx = _gcry_mpi_ec_init (pk.E.p, pk.E.a);
+  ctx = _gcry_mpi_ec_p_internal_new (pk.E.p, pk.E.a);
 
   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so */
   {
-    mpi_point_t R;     /* Result that we return.  */
+    mpi_point_struct R;  /* Result that we return.  */
     gcry_mpi_t x, y;
 
     x = mpi_new (0);
@@ -1349,7 +1509,8 @@ ecc_encrypt_raw (int algo, gcry_mpi_t *resarr, gcry_mpi_t k,
   }
 
   _gcry_mpi_ec_free (ctx);
-  ecc_pk_free (&pk);
+  point_free (&pk.E.G);
+  point_free (&pk.Q);
 
   if (!result[0] || !result[1])
     {
@@ -1377,8 +1538,8 @@ ecc_decrypt_raw (int algo, gcry_mpi_t *result, gcry_mpi_t *data,
                  gcry_mpi_t *skey, int flags)
 {
   ECC_secret_key sk;
-  mpi_point_t R;       /* Result that we return.  */
-  mpi_point_t kG;
+  mpi_point_struct R;  /* Result that we return.  */
+  mpi_point_struct kG;
   mpi_ec_t ctx;
   gcry_mpi_t r;
   int err;
@@ -1425,7 +1586,7 @@ ecc_decrypt_raw (int algo, gcry_mpi_t *result, gcry_mpi_t *data,
     }
   sk.d = skey[6];
 
-  ctx = _gcry_mpi_ec_init (sk.E.p, sk.E.a);
+  ctx = _gcry_mpi_ec_p_internal_new (sk.E.p, sk.E.a);
 
   /* R = dkG */
   point_init (&R);
@@ -1450,7 +1611,9 @@ ecc_decrypt_raw (int algo, gcry_mpi_t *result, gcry_mpi_t *data,
 
   point_free (&R);
   _gcry_mpi_ec_free (ctx);
-  ecc_sk_free (&sk) ;
+  point_free (&kG);
+  point_free (&sk.E.G);
+  point_free (&sk.Q);
 
   if (!r)
     return GPG_ERR_ENOMEM;
@@ -1515,6 +1678,7 @@ compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
         tmpvalues[idx] = NULL;
 
       curve = _gcry_sexp_nth_string (l1, 1);
+      gcry_sexp_release (l1);
       if (!curve)
         {
           ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */
@@ -1575,6 +1739,350 @@ compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
 }
 
 
+\f
+/*
+   Low-level API helper functions.
+ */
+
+/* Helper to extract an MPI from key parameters.  */
+static gpg_err_code_t
+mpi_from_keyparam (gcry_mpi_t *r_a, gcry_sexp_t keyparam, const char *name)
+{
+  gcry_err_code_t ec = 0;
+  gcry_sexp_t l1;
+
+  l1 = gcry_sexp_find_token (keyparam, name, 0);
+  if (l1)
+    {
+      *r_a = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
+      gcry_sexp_release (l1);
+      if (!*r_a)
+        ec = GPG_ERR_INV_OBJ;
+    }
+  return ec;
+}
+
+/* Helper to extract a point from key parameters.  If no parameter
+   with NAME is found, the functions tries to find a non-encoded point
+   by appending ".x", ".y" and ".z" to NAME.  ".z" is in this case
+   optional and defaults to 1.  */
+static gpg_err_code_t
+point_from_keyparam (gcry_mpi_point_t *r_a,
+                     gcry_sexp_t keyparam, const char *name)
+{
+  gcry_err_code_t ec;
+  gcry_mpi_t a = NULL;
+  gcry_mpi_point_t point;
+
+  ec = mpi_from_keyparam (&a, keyparam, name);
+  if (ec)
+    return ec;
+
+  if (a)
+    {
+      point = gcry_mpi_point_new (0);
+      ec = os2ec (point, a);
+      mpi_free (a);
+      if (ec)
+        {
+          gcry_mpi_point_release (point);
+          return ec;
+        }
+    }
+  else
+    {
+      char *tmpname;
+      gcry_mpi_t x = NULL;
+      gcry_mpi_t y = NULL;
+      gcry_mpi_t z = NULL;
+
+      tmpname = gcry_malloc (strlen (name) + 2 + 1);
+      if (!tmpname)
+        return gpg_err_code_from_syserror ();
+      strcpy (stpcpy (tmpname, name), ".x");
+      ec = mpi_from_keyparam (&x, keyparam, tmpname);
+      if (ec)
+        {
+          gcry_free (tmpname);
+          return ec;
+        }
+      strcpy (stpcpy (tmpname, name), ".y");
+      ec = mpi_from_keyparam (&y, keyparam, tmpname);
+      if (ec)
+        {
+          mpi_free (x);
+          gcry_free (tmpname);
+          return ec;
+        }
+      strcpy (stpcpy (tmpname, name), ".z");
+      ec = mpi_from_keyparam (&z, keyparam, tmpname);
+      if (ec)
+        {
+          mpi_free (y);
+          mpi_free (x);
+          gcry_free (tmpname);
+          return ec;
+        }
+      if (!z)
+        z = mpi_set_ui (NULL, 1);
+      if (x && y)
+        point = gcry_mpi_point_snatch_set (NULL, x, y, z);
+      else
+        {
+          mpi_free (x);
+          mpi_free (y);
+          mpi_free (z);
+          point = NULL;
+        }
+      gcry_free (tmpname);
+    }
+
+  if (point)
+    *r_a = point;
+  return 0;
+}
+
+
+/* This function creates a new context for elliptic curve operations.
+   Either KEYPARAM or CURVENAME must be given.  If both are given and
+   KEYPARAM has no curve parameter CURVENAME is used to add missing
+   parameters.  On success 0 is returned and the new context stored at
+   R_CTX.  On error NULL is stored at R_CTX and an error code is
+   returned.  The context needs to be released using
+   gcry_ctx_release.  */
+gpg_err_code_t
+_gcry_mpi_ec_new (gcry_ctx_t *r_ctx,
+                  gcry_sexp_t keyparam, const char *curvename)
+{
+  gpg_err_code_t errc;
+  gcry_ctx_t ctx = NULL;
+  gcry_mpi_t p = NULL;
+  gcry_mpi_t a = NULL;
+  gcry_mpi_t b = NULL;
+  gcry_mpi_point_t G = NULL;
+  gcry_mpi_t n = NULL;
+  gcry_mpi_point_t Q = NULL;
+  gcry_mpi_t d = NULL;
+  gcry_sexp_t l1;
+
+  *r_ctx = NULL;
+
+  if (keyparam)
+    {
+      errc = mpi_from_keyparam (&p, keyparam, "p");
+      if (errc)
+        goto leave;
+      errc = mpi_from_keyparam (&a, keyparam, "a");
+      if (errc)
+        goto leave;
+      errc = mpi_from_keyparam (&b, keyparam, "b");
+      if (errc)
+        goto leave;
+      errc = point_from_keyparam (&G, keyparam, "g");
+      if (errc)
+        goto leave;
+      errc = mpi_from_keyparam (&n, keyparam, "n");
+      if (errc)
+        goto leave;
+      errc = point_from_keyparam (&Q, keyparam, "q");
+      if (errc)
+        goto leave;
+      errc = mpi_from_keyparam (&d, keyparam, "d");
+      if (errc)
+        goto leave;
+    }
+
+
+  /* Check whether a curve parameter is available and use that to fill
+     in missing values.  If no curve parameter is available try an
+     optional provided curvename.  If only the curvename has been
+     given use that one. */
+  if (keyparam)
+    l1 = gcry_sexp_find_token (keyparam, "curve", 5);
+  else
+    l1 = NULL;
+  if (l1 || curvename)
+    {
+      char *name;
+      elliptic_curve_t *E;
+
+      if (l1)
+        {
+          name = _gcry_sexp_nth_string (l1, 1);
+          gcry_sexp_release (l1);
+          if (!name)
+            {
+              errc = GPG_ERR_INV_OBJ; /* Name missing or out of core. */
+              goto leave;
+            }
+        }
+      else
+        name = NULL;
+
+      E = gcry_calloc (1, sizeof *E);
+      if (!E)
+        {
+          errc = gpg_err_code_from_syserror ();
+          gcry_free (name);
+          goto leave;
+        }
+
+      errc = fill_in_curve (0, name? name : curvename, E, NULL);
+      gcry_free (name);
+      if (errc)
+        {
+          gcry_free (E);
+          goto leave;
+        }
+
+      if (!p)
+        {
+          p = E->p;
+          E->p = NULL;
+        }
+      if (!a)
+        {
+          a = E->a;
+          E->a = NULL;
+        }
+      if (!b)
+        {
+          b = E->b;
+          E->b = NULL;
+        }
+      if (!G)
+        {
+          G = gcry_mpi_point_snatch_set (NULL, E->G.x, E->G.y, E->G.z);
+          E->G.x = NULL;
+          E->G.y = NULL;
+          E->G.z = NULL;
+        }
+      if (!n)
+        {
+          n = E->n;
+          E->n = NULL;
+        }
+      curve_free (E);
+      gcry_free (E);
+    }
+
+  errc = _gcry_mpi_ec_p_new (&ctx, p, a);
+  if (!errc)
+    {
+      mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
+
+      if (b)
+        {
+          ec->b = b;
+          b = NULL;
+        }
+      if (G)
+        {
+          ec->G = G;
+          G = NULL;
+        }
+      if (n)
+        {
+          ec->n = n;
+          n = NULL;
+        }
+      if (Q)
+        {
+          ec->Q = Q;
+          Q = NULL;
+        }
+      if (d)
+        {
+          ec->d = d;
+          d = NULL;
+        }
+
+      *r_ctx = ctx;
+    }
+
+ leave:
+  mpi_free (p);
+  mpi_free (a);
+  mpi_free (b);
+  gcry_mpi_point_release (G);
+  mpi_free (n);
+  gcry_mpi_point_release (Q);
+  mpi_free (d);
+  return errc;
+}
+
+
+/* This is the wroker function for gcry_pubkey_get_sexp for ECC
+   algorithms.  Note that the caller has already stored NULL at
+   R_SEXP.  */
+gpg_err_code_t
+_gcry_pk_ecc_get_sexp (gcry_sexp_t *r_sexp, int mode, mpi_ec_t ec)
+{
+  gpg_err_code_t rc;
+  gcry_mpi_t mpi_G = NULL;
+  gcry_mpi_t mpi_Q = NULL;
+
+  if (!ec->p || !ec->a || !ec->b || !ec->G || !ec->n)
+    return GPG_ERR_BAD_CRYPT_CTX;
+
+  if (mode == GCRY_PK_GET_SECKEY && !ec->d)
+    return GPG_ERR_NO_SECKEY;
+
+  /* Compute the public point if it is missing.  */
+  if (!ec->Q && ec->d)
+    {
+      ec->Q = gcry_mpi_point_new (0);
+      _gcry_mpi_ec_mul_point (ec->Q, ec->d, ec->G, ec);
+    }
+
+  /* Encode G and Q.  */
+  mpi_G = _gcry_mpi_ec_ec2os (ec->G, ec);
+  if (!mpi_G)
+    {
+      rc = GPG_ERR_BROKEN_PUBKEY;
+      goto leave;
+    }
+  if (!ec->Q)
+    {
+      rc = GPG_ERR_BAD_CRYPT_CTX;
+      goto leave;
+    }
+  mpi_Q = _gcry_mpi_ec_ec2os (ec->Q, ec);
+  if (!mpi_Q)
+    {
+      rc = GPG_ERR_BROKEN_PUBKEY;
+      goto leave;
+    }
+
+  /* Fixme: We should return a curve name instead of the parameters if
+     if know that they match a curve.  */
+
+  if (ec->d && (!mode || mode == GCRY_PK_GET_SECKEY))
+    {
+      /* Let's return a private key. */
+      rc = gpg_err_code
+        (gcry_sexp_build
+         (r_sexp, NULL,
+          "(private-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)(d%m)))",
+          ec->p, ec->a, ec->b, mpi_G, ec->n, mpi_Q, ec->d));
+    }
+  else if (ec->Q)
+    {
+      /* Let's return a public key.  */
+      rc = gpg_err_code
+        (gcry_sexp_build
+         (r_sexp, NULL,
+          "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)))",
+          ec->p, ec->a, ec->b, mpi_G, ec->n, mpi_Q));
+    }
+  else
+    rc = GPG_ERR_BAD_CRYPT_CTX;
+
+ leave:
+  mpi_free (mpi_Q);
+  mpi_free (mpi_G);
+  return rc;
+}
 
 
 \f
@@ -1659,7 +2167,7 @@ gcry_pk_spec_t _gcry_pubkey_spec_ecdsa =
 gcry_pk_spec_t _gcry_pubkey_spec_ecdh =
   {
     "ECDH", ecdh_names,
-    "pabgnq", "pabgnqd", "", "rs", "pabgnq",
+    "pabgnq", "pabgnqd", "se", "", "pabgnq",
     GCRY_PK_USAGE_ENCR,
     ecc_generate,
     ecc_check_secret_key,
@@ -1676,5 +2184,7 @@ pk_extra_spec_t _gcry_pubkey_extraspec_ecdsa =
     run_selftests,
     ecc_generate_ext,
     compute_keygrip,
-    ecc_get_param
+    ecc_get_param,
+    ecc_get_curve,
+    ecc_get_param_sexp
   };