ecc: Change keygrip computation for Ed25519+EdDSA.
authorWerner Koch <wk@gnupg.org>
Mon, 11 Nov 2013 18:14:40 +0000 (19:14 +0100)
committerWerner Koch <wk@gnupg.org>
Mon, 11 Nov 2013 18:15:20 +0000 (19:15 +0100)
* cipher/ecc.c (compute_keygrip): Rework.
* cipher/ecc-eddsa.c (_gcry_ecc_eddsa_ensure_compact): New.
* cipher/ecc-curves.c (_gcry_ecc_update_curve_param): New.
* tests/keygrip.c (key_grips): Add flag param and test cases for
Ed25519.
--

The keygrip for Ed25519+EdDSA has not yet been used - thus it is
possible to change it.  Using the compact representation saves us the
recovering of x from the standard representation.  Compacting is
basically free.

cipher/ecc-common.h
cipher/ecc-curves.c
cipher/ecc-eddsa.c
cipher/ecc.c
tests/keygrip.c

index 93fd449..0cecdc3 100644 (file)
@@ -70,6 +70,12 @@ gpg_err_code_t _gcry_ecc_fill_in_curve (unsigned int nbits,
                                         const char *name,
                                         elliptic_curve_t *curve,
                                         unsigned int *r_nbits);
+gpg_err_code_t _gcry_ecc_update_curve_param (const char *name,
+                                             enum gcry_mpi_ec_models *model,
+                                             enum ecc_dialects *dialect,
+                                             gcry_mpi_t *p, gcry_mpi_t *a,
+                                             gcry_mpi_t *b, gcry_mpi_t *g,
+                                             gcry_mpi_t *n);
 
 const char *_gcry_ecc_get_curve (gcry_sexp_t keyparms,
                                  int iterator,
@@ -103,6 +109,8 @@ gpg_err_code_t _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ctx,
                                             gcry_mpi_t x, gcry_mpi_t y,
                                             unsigned char **r_buffer,
                                             unsigned int *r_buflen);
+gpg_err_code_t _gcry_ecc_eddsa_ensure_compact (gcry_mpi_t value,
+                                               unsigned int nbits);
 gpg_err_code_t _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx,
                                             mpi_point_t result,
                                             unsigned char **r_encpk,
index 98fbf0c..8c63f6c 100644 (file)
@@ -441,6 +441,56 @@ _gcry_ecc_fill_in_curve (unsigned int nbits, const char *name,
 }
 
 
+/* Give the name of the curve NAME, store the curve parameters into P,
+   A, B, G, and N if they pint to NULL value.  Note that G is returned
+   in standard uncompressed format.  Also update MODEL and DIALECT if
+   they are not NULL. */
+gpg_err_code_t
+_gcry_ecc_update_curve_param (const char *name,
+                              enum gcry_mpi_ec_models *model,
+                              enum ecc_dialects *dialect,
+                              gcry_mpi_t *p, gcry_mpi_t *a, gcry_mpi_t *b,
+                              gcry_mpi_t *g, gcry_mpi_t *n)
+{
+  int idx;
+
+  idx = find_domain_parms_idx (name);
+  if (idx < 0)
+    return GPG_ERR_UNKNOWN_CURVE;
+
+  if (g)
+    {
+      char *buf;
+      size_t len;
+
+      len = 4;
+      len += strlen (domain_parms[idx].g_x+2);
+      len += strlen (domain_parms[idx].g_y+2);
+      len++;
+      buf = gcry_malloc (len);
+      if (!buf)
+        return gpg_err_code_from_syserror ();
+      strcpy (stpcpy (stpcpy (buf, "0x04"), domain_parms[idx].g_x+2),
+              domain_parms[idx].g_y+2);
+      *g = scanval (buf);
+      gcry_free (buf);
+    }
+  if (model)
+    *model = domain_parms[idx].model;
+  if (dialect)
+    *dialect = domain_parms[idx].dialect;
+  if (p)
+    *p = scanval (domain_parms[idx].p);
+  if (a)
+    *a = scanval (domain_parms[idx].a);
+  if (b)
+    *b = scanval (domain_parms[idx].b);
+  if (n)
+    *n = scanval (domain_parms[idx].n);
+  return 0;
+}
+
+
 /* Return the name matching the parameters in PKEY.  This works only
    with curves described by the Weierstrass equation. */
 const char *
index d83b7c6..b9e866d 100644 (file)
@@ -136,6 +136,54 @@ _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec,
 }
 
 
+/* Make sure that the opaque MPI VALUE is in compact EdDSA format.
+   This function updates MPI if needed.  */
+gpg_err_code_t
+_gcry_ecc_eddsa_ensure_compact (gcry_mpi_t value, unsigned int nbits)
+{
+  gpg_err_code_t rc;
+  const unsigned char *buf;
+  unsigned int rawmpilen;
+  gcry_mpi_t x, y;
+  unsigned char *enc;
+  unsigned int enclen;
+
+  if (!mpi_is_opaque (value))
+    return GPG_ERR_INV_OBJ;
+  buf = gcry_mpi_get_opaque (value, &rawmpilen);
+  if (!buf)
+    return GPG_ERR_INV_OBJ;
+  rawmpilen = (rawmpilen + 7)/8;
+
+  /* Check whether the public key has been given in standard
+     uncompressed format.  In this case extract y and compress.  */
+  if (rawmpilen > 1 && buf[0] == 0x04 && (rawmpilen%2))
+    {
+      rc = gcry_mpi_scan (&x, GCRYMPI_FMT_STD,
+                          buf+1, (rawmpilen-1)/2, NULL);
+      if (rc)
+        return rc;
+      rc = gcry_mpi_scan (&y, GCRYMPI_FMT_STD,
+                          buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2, NULL);
+      if (rc)
+        {
+          mpi_free (x);
+          return rc;
+        }
+
+      rc = eddsa_encode_x_y (x, y, nbits/8, &enc, &enclen);
+      mpi_free (x);
+      mpi_free (y);
+      if (rc)
+        return rc;
+
+      gcry_mpi_set_opaque (value, enc, 8*enclen);
+    }
+
+  return 0;
+}
+
+
 /* Recover X from Y and SIGN (which actually is a parity bit).  */
 gpg_err_code_t
 _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec)
index d62f555..b9af185 100644 (file)
@@ -1428,65 +1428,87 @@ ecc_get_nbits (gcry_sexp_t parms)
 
 /* See rsa.c for a description of this function.  */
 static gpg_err_code_t
-compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
+compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparms)
 {
 #define N_COMPONENTS 6
   static const char names[N_COMPONENTS+1] = "pabgnq";
-  gpg_err_code_t ec = 0;
+  gpg_err_code_t rc;
   gcry_sexp_t l1;
   gcry_mpi_t values[N_COMPONENTS];
   int idx;
+  char *curvename = NULL;
+  int flags = 0;
+  enum gcry_mpi_ec_models model = 0;
+  enum ecc_dialects dialect = 0;
 
-  /* Clear the values for easier error cleanup.  */
+  /* Clear the values first.  */
   for (idx=0; idx < N_COMPONENTS; idx++)
     values[idx] = NULL;
 
-  /* Fill values with all provided parameters.  */
-  for (idx=0; idx < N_COMPONENTS; idx++)
+
+  /* Look for flags. */
+  l1 = gcry_sexp_find_token (keyparms, "flags", 0);
+  if (l1)
     {
-      l1 = gcry_sexp_find_token (keyparam, names+idx, 1);
-      if (l1)
-        {
-          values[idx] = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
-         gcry_sexp_release (l1);
-         if (!values[idx])
-            {
-              ec = GPG_ERR_INV_OBJ;
-              goto leave;
-            }
-       }
+      rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL);
+      if (rc)
+        goto leave;
+    }
+
+  /* Extract the parameters.  */
+  if ((flags & PUBKEY_FLAG_PARAM))
+    {
+      if ((flags & PUBKEY_FLAG_EDDSA))
+        rc = _gcry_sexp_extract_param (keyparms, NULL, "p?a?b?g?n?/q",
+                                       &values[0], &values[1], &values[2],
+                                       &values[3], &values[4], &values[5],
+                                       NULL);
+      else
+        rc = _gcry_sexp_extract_param (keyparms, NULL, "p?a?b?g?n?q",
+                                       &values[0], &values[1], &values[2],
+                                       &values[3], &values[4], &values[5],
+                                       NULL);
+    }
+  else
+    {
+      if ((flags & PUBKEY_FLAG_EDDSA))
+        rc = _gcry_sexp_extract_param (keyparms, NULL, "/q",
+                                       &values[5], NULL);
+      else
+        rc = _gcry_sexp_extract_param (keyparms, NULL, "q",
+                                       &values[5], NULL);
     }
+  if (rc)
+    goto leave;
 
   /* Check whether a curve parameter is available and use that to fill
      in missing values.  */
-  l1 = gcry_sexp_find_token (keyparam, "curve", 5);
+  gcry_sexp_release (l1);
+  l1 = gcry_sexp_find_token (keyparms, "curve", 5);
   if (l1)
     {
-      char *curve;
-      gcry_mpi_t tmpvalues[N_COMPONENTS];
-
-      for (idx = 0; idx < N_COMPONENTS; idx++)
-        tmpvalues[idx] = NULL;
-
-      curve = _gcry_sexp_nth_string (l1, 1);
-      gcry_sexp_release (l1);
-      if (!curve)
+      curvename = gcry_sexp_nth_string (l1, 1);
+      if (curvename)
         {
-          ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */
-          goto leave;
+          rc = _gcry_ecc_update_curve_param (curvename,
+                                             &model, &dialect,
+                                             &values[0], &values[1], &values[2],
+                                             &values[3], &values[4]);
+          if (rc)
+            return rc;
         }
-      ec = _gcry_ecc_get_param (curve, tmpvalues);
-      gcry_free (curve);
-      if (ec)
-        goto leave;
+    }
 
-      for (idx = 0; idx < N_COMPONENTS; idx++)
-        {
-          if (!values[idx])
-            values[idx] = tmpvalues[idx];
-          else
-            mpi_free (tmpvalues[idx]);
-        }
+  /* Guess required fields if a curve parameter has not been given.
+     FIXME: This is a crude hacks.  We need to fix that.  */
+  if (!curvename)
+    {
+      model = ((flags & PUBKEY_FLAG_EDDSA)
+               ? MPI_EC_TWISTEDEDWARDS
+               : MPI_EC_WEIERSTRASS);
+      dialect = ((flags & PUBKEY_FLAG_EDDSA)
+                 ? ECC_DIALECT_ED25519
+                 : ECC_DIALECT_STANDARD);
     }
 
   /* Check that all parameters are known and normalize all MPIs (that
@@ -1495,37 +1517,70 @@ compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
   for (idx = 0; idx < N_COMPONENTS; idx++)
     if (!values[idx])
       {
-        ec = GPG_ERR_NO_OBJ;
+        rc = GPG_ERR_NO_OBJ;
         goto leave;
       }
     else
       _gcry_mpi_normalize (values[idx]);
 
+  /* Uncompress the public key with the exception of EdDSA where
+     compression is the default and we thus compute the keygrip using
+     the compressed version.  Because we don't support any non-eddsa
+     compression, the only thing we need to do is to compress
+     EdDSA.  */
+  if ((flags & PUBKEY_FLAG_EDDSA))
+    {
+      if (dialect == ECC_DIALECT_ED25519)
+        rc = _gcry_ecc_eddsa_ensure_compact (values[5], 256);
+      else
+        rc = GPG_ERR_NOT_IMPLEMENTED;
+      if (rc)
+        goto leave;
+    }
+
   /* Hash them all.  */
   for (idx = 0; idx < N_COMPONENTS; idx++)
     {
       char buf[30];
-      unsigned char *rawmpi;
-      unsigned int rawmpilen;
 
-      rawmpi = _gcry_mpi_get_buffer (values[idx], 0, &rawmpilen, NULL);
-      if (!rawmpi)
+      if (mpi_is_opaque (values[idx]))
         {
-          ec = gpg_err_code_from_syserror ();
-          goto leave;
+          const unsigned char *raw;
+          unsigned int n;
+
+          raw = gcry_mpi_get_opaque (values[idx], &n);
+          n = (n + 7)/8;
+          snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], n);
+          gcry_md_write (md, buf, strlen (buf));
+          gcry_md_write (md, raw, n);
+          gcry_md_write (md, ")", 1);
+        }
+      else
+        {
+          unsigned char *rawmpi;
+          unsigned int rawmpilen;
+
+          rawmpi = _gcry_mpi_get_buffer (values[idx], 0, &rawmpilen, NULL);
+          if (!rawmpi)
+            {
+              rc = gpg_err_code_from_syserror ();
+              goto leave;
+            }
+          snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen);
+          gcry_md_write (md, buf, strlen (buf));
+          gcry_md_write (md, rawmpi, rawmpilen);
+          gcry_md_write (md, ")", 1);
+          gcry_free (rawmpi);
         }
-      snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen);
-      gcry_md_write (md, buf, strlen (buf));
-      gcry_md_write (md, rawmpi, rawmpilen);
-      gcry_md_write (md, ")", 1);
-      gcry_free (rawmpi);
     }
 
  leave:
+  gcry_free (curvename);
+  gcry_sexp_release (l1);
   for (idx = 0; idx < N_COMPONENTS; idx++)
     _gcry_mpi_release (values[idx]);
 
-  return ec;
+  return rc;
 #undef N_COMPONENTS
 }
 
index a89bba8..330935d 100644 (file)
@@ -104,7 +104,7 @@ static struct
     {
       GCRY_PK_ECDSA,
       "(public-key"
-      " (ecdsa"
+      " (ecdsa(flags param)"
       " (p #00FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF#)"
       " (a #00FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC#)"
       " (b #5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B#)"
@@ -116,6 +116,18 @@ static struct
     {
       GCRY_PK_ECDSA,
       "(public-key"
+      " (ecdsa(flags param)"
+      " (p #00FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF#)"
+      " (curve \"NIST P-256\")"
+      " (b #5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B#)"
+      " (g #046B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C2964FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5#)"
+      " (n #00FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551#)"
+      " (q #04C8A4CEC2E9A9BC8E173531A67B0840DF345C32E261ADD780E6D83D56EFADFD5DE872F8B854819B59543CE0B7F822330464FBC4E6324DADDCD9D059554F63B344#)))",
+      "\xE6\xDF\x94\x2D\xBD\x8C\x77\x05\xA3\xDD\x41\x6E\xFC\x04\x01\xDB\x31\x0E\x99\xB6"
+    },
+    {
+      GCRY_PK_ECDSA,
+      "(public-key"
       " (ecdsa"
       " (p #00FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF#)"
       " (curve \"NIST P-256\")"
@@ -132,10 +144,52 @@ static struct
       " (curve secp256r1)"
       " (q #04C8A4CEC2E9A9BC8E173531A67B0840DF345C32E261ADD780E6D83D56EFADFD5DE872F8B854819B59543CE0B7F822330464FBC4E6324DADDCD9D059554F63B344#)))",
       "\xE6\xDF\x94\x2D\xBD\x8C\x77\x05\xA3\xDD\x41\x6E\xFC\x04\x01\xDB\x31\x0E\x99\xB6"
+    },
+    {
+      GCRY_PK_ECC,
+      "(public-key"
+      " (ecc"
+      " (curve secp256r1)"
+      " (q #04C8A4CEC2E9A9BC8E173531A67B0840DF345C32E261ADD780E6D83D56EFADFD5DE872F8B854819B59543CE0B7F822330464FBC4E6324DADDCD9D059554F63B344#)))",
+      "\xE6\xDF\x94\x2D\xBD\x8C\x77\x05\xA3\xDD\x41\x6E\xFC\x04\x01\xDB\x31\x0E\x99\xB6"
+    },
+    { /* Ed25519 standard */
+      GCRY_PK_ECC,
+      "(public-key"
+      " (ecc"
+      " (curve Ed25519)"
+      " (q #04"
+      "     1CC662926E7EFF4982B7FB8B928E61CD74CCDD85277CC57196C3AD20B611085F"
+      "     47BD24842905C049257673B3F5249524E0A41FAA17B25B818D0F97E625F1A1D0#)"
+      "     ))",
+      "\x0C\xCA\xB2\xFD\x48\x9A\x33\x40\x2C\xE8"
+      "\xE0\x4A\x1F\xB2\x45\xEA\x80\x3D\x0A\xF1"
+    },
+    { /* Ed25519+EdDSA */
+      GCRY_PK_ECC,
+      "(public-key"
+      " (ecc"
+      " (curve Ed25519)(flags eddsa)"
+      " (q #773E72848C1FD5F9652B29E2E7AF79571A04990E96F2016BF4E0EC1890C2B7DB#)"
+      " ))",
+      "\x9D\xB6\xC6\x4A\x38\x83\x0F\x49\x60\x70"
+      "\x17\x89\x47\x55\x20\xBE\x8C\x82\x1F\x47"
+    },
+    { /* Ed25519+EdDSA  (same but uncompressed)*/
+      GCRY_PK_ECC,
+      "(public-key"
+      " (ecc"
+      " (curve Ed25519)(flags eddsa)"
+      " (q #04"
+      "     629ad237d1ed04dcd4abe1711dd699a1cf51b1584c4de7a4ef8b8a640180b26f"
+      "     5bb7c29018ece0f46b01f2960e99041a5779afe7e2292b65f9d51f8c84723e77#)"
+      " ))",
+      "\x9D\xB6\xC6\x4A\x38\x83\x0F\x49\x60\x70"
+      "\x17\x89\x47\x55\x20\xBE\x8C\x82\x1F\x47"
     }
-
   };
 
+
 static void
 check (void)
 {