ecc: Support the non-standard 0x40 compression flag for EdDSA.

* cipher/ecc.c (ecc_generate): Check the "comp" flag for EdDSA.
* cipher/ecc-eddsa.c (eddsa_encode_x_y): Add arg WITH_PREFIX.
(_gcry_ecc_eddsa_encodepoint): Ditto.
(_gcry_ecc_eddsa_ensure_compact): Handle the 0x40 compression prefix.
(_gcry_ecc_eddsa_decodepoint): Ditto.
* tests/keygrip.c: Check an compresssed with prefix Ed25519 key.
* tests/t-ed25519.inp: Ditto.

8 files changed, 127 insertions, 72 deletions

diff --git a/cipher/ecc-common.h b/cipher/ecc-common.h
index c407c744..f066b4b7 100644
--- a/cipher/ecc-common.h
+++ b/cipher/ecc-common.h
@@ -107,6 +107,7 @@ gpg_err_code_t _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign,
                                           mpi_ec_t ec);
 gpg_err_code_t _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ctx,
                                             gcry_mpi_t x, gcry_mpi_t y,
+                                            int with_prefix,
                                             unsigned char **r_buffer,
                                             unsigned int *r_buflen);
 gpg_err_code_t _gcry_ecc_eddsa_ensure_compact (gcry_mpi_t value,
diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c
index 0f622f73..cd85361d 100644
--- a/cipher/ecc-curves.c
+++ b/cipher/ecc-curves.c
@@ -1146,7 +1146,7 @@ _gcry_ecc_get_mpi (const char *name, mpi_ec_t ec, int copy)
           unsigned char *encpk;
           unsigned int encpklen;
 
-          if (!_gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL,
+          if (!_gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL, 0,
                                             &encpk, &encpklen))
             return mpi_set_opaque (NULL, encpk, encpklen*8);
         }
diff --git a/cipher/ecc-eddsa.c b/cipher/ecc-eddsa.c
index d08a84fc..65024a30 100644
--- a/cipher/ecc-eddsa.c
+++ b/cipher/ecc-eddsa.c
@@ -1,5 +1,5 @@
 /* ecc-eddsa.c  -  Elliptic Curve EdDSA signatures
- * Copyright (C) 2013 g10 Code GmbH
+ * Copyright (C) 2013, 2014 g10 Code GmbH
  *
  * This file is part of Libgcrypt.
  *
@@ -83,35 +83,42 @@ eddsa_encodempi (gcry_mpi_t mpi, unsigned int minlen,
 
 
 /* Encode (X,Y) using the EdDSA scheme.  MINLEN is the required length
-   in bytes for the result.  On success 0 is returned and a malloced
-   buffer with the encoded point is stored at R_BUFFER; the length of
-   this buffer is stored at R_BUFLEN.  */
+   in bytes for the result.  If WITH_PREFIX is set the returned buffer
+   is prefixed with a 0x40 byte.  On success 0 is returned and a
+   malloced buffer with the encoded point is stored at R_BUFFER; the
+   length of this buffer is stored at R_BUFLEN.  */
 static gpg_err_code_t
 eddsa_encode_x_y (gcry_mpi_t x, gcry_mpi_t y, unsigned int minlen,
+                  int with_prefix,
                   unsigned char **r_buffer, unsigned int *r_buflen)
 {
   unsigned char *rawmpi;
   unsigned int rawmpilen;
+  int off = with_prefix? 1:0;
 
-  rawmpi = _gcry_mpi_get_buffer (y, minlen, &rawmpilen, NULL);
+  rawmpi = _gcry_mpi_get_buffer_extra (y, minlen, off?-1:0, &rawmpilen, NULL);
   if (!rawmpi)
     return gpg_err_code_from_syserror ();
   if (mpi_test_bit (x, 0) && rawmpilen)
-    rawmpi[rawmpilen - 1] |= 0x80;  /* Set sign bit.  */
+    rawmpi[off + rawmpilen - 1] |= 0x80;  /* Set sign bit.  */
+  if (off)
+    rawmpi[0] = 0x40;
 
   *r_buffer = rawmpi;
-  *r_buflen = rawmpilen;
+  *r_buflen = rawmpilen + off;
   return 0;
 }
 
 /* Encode POINT using the EdDSA scheme.  X and Y are either scratch
    variables supplied by the caller or NULL.  CTX is the usual
-   context.  On success 0 is returned and a malloced buffer with the
-   encoded point is stored at R_BUFFER; the length of this buffer is
-   stored at R_BUFLEN.  */
+   context.  If WITH_PREFIX is set the returned buffer is prefixed
+   with a 0x40 byte.  On success 0 is returned and a malloced buffer
+   with the encoded point is stored at R_BUFFER; the length of this
+   buffer is stored at R_BUFLEN.  */
 gpg_err_code_t
 _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec,
                              gcry_mpi_t x_in, gcry_mpi_t y_in,
+                             int with_prefix,
                              unsigned char **r_buffer, unsigned int *r_buflen)
 {
   gpg_err_code_t rc;
@@ -126,7 +133,7 @@ _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec,
       rc = GPG_ERR_INTERNAL;
     }
   else
-    rc = eddsa_encode_x_y (x, y, ec->nbits/8, r_buffer, r_buflen);
+    rc = eddsa_encode_x_y (x, y, ec->nbits/8, with_prefix, r_buffer, r_buflen);
 
   if (!x_in)
     mpi_free (x);
@@ -155,29 +162,40 @@ _gcry_ecc_eddsa_ensure_compact (gcry_mpi_t value, unsigned int nbits)
     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))
+  if (rawmpilen > 1 && (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)
+      if (buf[0] == 0x04)
         {
-          mpi_free (x);
-          return rc;
-        }
+          /* Buffer is in SEC1 uncompressed format.  Extract y and
+             compress.  */
+          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;
+          rc = eddsa_encode_x_y (x, y, nbits/8, 0, &enc, &enclen);
+          mpi_free (x);
+          mpi_free (y);
+          if (rc)
+            return rc;
 
-      mpi_set_opaque (value, enc, 8*enclen);
+          mpi_set_opaque (value, enc, 8*enclen);
+        }
+      else if (buf[0] == 0x40)
+        {
+          /* Buffer is compressed but with our SEC1 alike compression
+             indicator.  Remove that byte.  FIXME: We should write and
+             use a function to manipulate an opaque MPI in place. */
+          if (!_gcry_mpi_set_opaque_copy (value, buf + 1, (rawmpilen - 1)*8))
+            return gpg_err_code_from_syserror ();
+        }
     }
 
   return 0;
@@ -267,7 +285,7 @@ _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec)
    the usual curve context.  If R_ENCPK is not NULL, the encoded PK is
    stored at that address; this is a new copy to be released by the
    caller.  In contrast to the supplied PK, this is not an MPI and
-   thus guarnateed to be properly padded.  R_ENCPKLEN receives the
+   thus guaranteed to be properly padded.  R_ENCPKLEN receives the
    length of that encoded key.  */
 gpg_err_code_t
 _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
@@ -287,40 +305,54 @@ _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
         return GPG_ERR_INV_OBJ;
       rawmpilen = (rawmpilen + 7)/8;
 
-      /* First check whether the public key has been given in standard
-         uncompressed format.  No need to recover x in this case.
-         Detection is easy: The size of the buffer will be odd and the
-         first byte be 0x04.  */
-      if (rawmpilen > 1 && buf[0] == 0x04 && (rawmpilen%2))
+      /* Handle compression prefixes.  The size of the buffer will be
+         odd in this case.  */
+      if (rawmpilen > 1 && (rawmpilen%2))
         {
-          gcry_mpi_t x, y;
-
-          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)
+          /* First check whether the public key has been given in
+             standard uncompressed format (SEC1).  No need to recover
+             x in this case.  */
+          if (buf[0] == 0x04)
             {
-              mpi_free (x);
-              return rc;
-            }
+              gcry_mpi_t x, y;
 
-          if (r_encpk)
-            {
-              rc = eddsa_encode_x_y (x, y, ctx->nbits/8, r_encpk, r_encpklen);
+              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);
-                  mpi_free (y);
                   return rc;
                 }
+
+              if (r_encpk)
+                {
+                  rc = eddsa_encode_x_y (x, y, ctx->nbits/8, 0,
+                                         r_encpk, r_encpklen);
+                  if (rc)
+                    {
+                      mpi_free (x);
+                      mpi_free (y);
+                      return rc;
+                    }
+                }
+              mpi_snatch (result->x, x);
+              mpi_snatch (result->y, y);
+              mpi_set_ui (result->z, 1);
+              return 0;
+            }
+
+          /* Check whether the public key has been prefixed with a 0x40
+             byte to explicitly indicate compressed format using a SEC1
+             alike prefix byte.  This is a Libgcrypt extension.  */
+          if (buf[0] == 0x40)
+            {
+              rawmpilen--;
+              buf++;
             }
-          mpi_snatch (result->x, x);
-          mpi_snatch (result->y, y);
-          mpi_set_ui (result->z, 1);
-          return 0;
         }
 
       /* EdDSA compressed point.  */
@@ -334,7 +366,7 @@ _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
     {
       /* Note: Without using an opaque MPI it is not reliable possible
          to find out whether the public key has been given in
-         uncompressed format.  Thus we expect EdDSA format here.  */
+         uncompressed format.  Thus we expect native EdDSA format.  */
       rawmpi = _gcry_mpi_get_buffer (pk, ctx->nbits/8, &rawmpilen, NULL);
       if (!rawmpi)
         return gpg_err_code_from_syserror ();
@@ -582,7 +614,7 @@ _gcry_ecc_eddsa_sign (gcry_mpi_t input, ECC_secret_key *skey,
   else
     {
       _gcry_mpi_ec_mul_point (&Q, a, &skey->E.G, ctx);
-      rc = _gcry_ecc_eddsa_encodepoint (&Q, ctx, x, y, &encpk, &encpklen);
+      rc = _gcry_ecc_eddsa_encodepoint (&Q, ctx, x, y, 0, &encpk, &encpklen);
       if (rc)
         goto leave;
       if (DBG_CIPHER)
@@ -612,7 +644,7 @@ _gcry_ecc_eddsa_sign (gcry_mpi_t input, ECC_secret_key *skey,
     log_printpnt ("   r", &I, ctx);
 
   /* Convert R into affine coordinates and apply encoding.  */
-  rc = _gcry_ecc_eddsa_encodepoint (&I, ctx, x, y, &rawmpi, &rawmpilen);
+  rc = _gcry_ecc_eddsa_encodepoint (&I, ctx, x, y, 0, &rawmpi, &rawmpilen);
   if (rc)
     goto leave;
   if (DBG_CIPHER)
@@ -784,7 +816,7 @@ _gcry_ecc_eddsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
   _gcry_mpi_ec_mul_point (&Ib, h, &Q, ctx);
   _gcry_mpi_neg (Ib.x, Ib.x);
   _gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ctx);
-  rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, &tbuf, &tlen);
+  rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, 0, &tbuf, &tlen);
   if (rc)
     goto leave;
   if (tlen != rlen || memcmp (tbuf, rbuf, tlen))
diff --git a/cipher/ecc.c b/cipher/ecc.c
index e0be2d4f..a27d2c60 100644
--- a/cipher/ecc.c
+++ b/cipher/ecc.c
@@ -35,15 +35,12 @@
   verification algorithms.  The arithmetic functions have entirely
   been rewritten and moved to mpi/ec.c.
 
-  ECDH encrypt and decrypt code written by Andrey Jivsov,
+  ECDH encrypt and decrypt code written by Andrey Jivsov.
 */
 
 
 /* TODO:
 
-  - If we support point compression we need to uncompress before
-    computing the keygrip
-
   - 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.
 
@@ -487,7 +484,9 @@ ecc_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
       unsigned char *encpk;
       unsigned int encpklen;
 
-      rc = _gcry_ecc_eddsa_encodepoint (&sk.Q, ctx, x, y, &encpk, &encpklen);
+      rc = _gcry_ecc_eddsa_encodepoint (&sk.Q, ctx, x, y,
+                                        !!(flags & PUBKEY_FLAG_COMP),
+                                        &encpk, &encpklen);
       if (rc)
         return rc;
       public = mpi_new (0);
@@ -1653,7 +1652,7 @@ _gcry_pk_ecc_get_sexp (gcry_sexp_t *r_sexp, int mode, mpi_ec_t ec)
       unsigned char *encpk;
       unsigned int encpklen;
 
-      rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL,
+      rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL, 0,
                                         &encpk, &encpklen);
       if (rc)
         goto leave;
diff --git a/doc/gcrypt.texi b/doc/gcrypt.texi
index d59c0958..23efc526 100644
--- a/doc/gcrypt.texi
+++ b/doc/gcrypt.texi
@@ -2162,7 +2162,9 @@ The private key @math{d}
 All point values are encoded in standard format; Libgcrypt does in
 general only support uncompressed points, thus the first byte needs to
 be @code{0x04}.  However ``EdDSA'' describes its own compression
-scheme which is used by default.
+scheme which is used by default; the non-standard first byte
+@code{0x40} may optionally be used to explicit flag the use of the
+algorithm’s native compression method.
 
 The public key is similar with "private-key" replaced by "public-key"
 and no @var{d-mpi}.
@@ -2232,9 +2234,11 @@ are known:
 If supported by the algorithm and curve the @code{comp} flag requests
 that points are returned in compact (compressed) representation.  The
 @code{nocomp} flag requests that points are returned with full
-coordinates.  The default depends on the the algorithm and curve.
-The compact representation requires a small overhead before a point
-can be used but halves the size of a to be conveyed public key.
+coordinates.  The default depends on the the algorithm and curve.  The
+compact representation requires a small overhead before a point can be
+used but halves the size of a to be conveyed public key.  If
+@code{comp} is used with the ``EdDSA'' algorithm the key generation
+prefix the public key with a @code{0x40} byte.
 
 @item pkcs1
 @cindex PKCS1
diff --git a/tests/keygrip.c b/tests/keygrip.c
index 330935db..72960ea3 100644
--- a/tests/keygrip.c
+++ b/tests/keygrip.c
@@ -175,6 +175,17 @@ static struct
       "\x9D\xB6\xC6\x4A\x38\x83\x0F\x49\x60\x70"
       "\x17\x89\x47\x55\x20\xBE\x8C\x82\x1F\x47"
     },
+    { /* Ed25519+EdDSA (with compression prefix) */
+      GCRY_PK_ECC,
+      "(public-key"
+      " (ecc"
+      " (curve Ed25519)(flags eddsa)"
+      " (q #40"
+      "     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"
diff --git a/tests/t-ed25519.c b/tests/t-ed25519.c
index 465a217b..b7f33076 100644
--- a/tests/t-ed25519.c
+++ b/tests/t-ed25519.c
@@ -32,7 +32,7 @@
 #include "stopwatch.h"
 
 #define PGM "t-ed25519"
-#define N_TESTS 1025
+#define N_TESTS 1026
 
 #define my_isascii(c) (!((c) & 0x80))
 #define digitp(p)   (*(p) >= '0' && *(p) <= '9')
diff --git a/tests/t-ed25519.inp b/tests/t-ed25519.inp
index 61387c4b..e13566f8 100644
--- a/tests/t-ed25519.inp
+++ b/tests/t-ed25519.inp
@@ -6162,3 +6162,11 @@ SK:  9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60
 PK:  0455d0e09a2b9d34292297e08d60d0f620c513d47253187c24b12786bd777645ce1a5107f7681a02af2523a6daf372e10e3a0764c9d3fe4bd5b70ab18201985ad7
 MSG:
 SIG: e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e065224901555fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b
+
+# Now an additional test with the data from test 1 but using an
+# compressed prefix.
+TST: 1
+SK:  9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60
+PK:  40d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a
+MSG:
+SIG: e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e065224901555fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b