ecc: Fix a minor flaw in the generation of K.
[libgcrypt.git] / cipher / ecc.c
index 4efbef4..63ee2d0 100644 (file)
 
   - 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.
+
+  - 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
@@ -296,7 +306,6 @@ static void *progress_cb_data;
 
 \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,
@@ -414,34 +423,10 @@ 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 at seclevel %d\n",
-               nbits, security_level);
-
-  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)
@@ -491,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);
@@ -543,7 +529,7 @@ generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name,
     }
 
   random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
-  d = gen_k (E.n, random_level);
+  d = _gcry_dsa_gen_k (E.n, random_level);
 
   /* Compute Q.  */
   point_init (&Q);
@@ -558,19 +544,70 @@ 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);
 
@@ -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))
             {
@@ -920,6 +957,27 @@ 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
@@ -1278,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];
@@ -1292,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));
@@ -1312,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;
 }
 
@@ -1689,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