ecc: Support reading EC point in compressed format for good curves.

* cipher/ecc-curves.c (gcry_ecc_get_curve): Handle G, differently.
* cipher/ecc-misc.c (_gcry_ecc_sec_decodepoint): Support compressed
representation of EC point.  Rename from _gcry_ecc_os2ec.
* cipher/ecc-sm2.c (_gcry_ecc_sm2_decrypt) Follow the change.
* cipher/ecc.c (ecc_decrypt_raw): Likewise.
* mpi/ec.c (_gcry_mpi_ec_set_point): Likewise.
* src/ec-context.h: API change _gcry_ecc_sec_decodepoint from
_gcry_ecc_os2ec.
* tests/basic.c (check_pubkey): Use compressed representation
for two public keys of NIST P192 and NIST P256.

GnuPG-bug-id: 4951
Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>

7 files changed, 102 insertions, 40 deletions

diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c
index f8d561cb..a019e054 100644
--- a/cipher/ecc-curves.c
+++ b/cipher/ecc-curves.c
@@ -34,6 +34,10 @@
 #include "ecc-common.h"
 
 
+static gpg_err_code_t
+point_from_keyparam (gcry_mpi_point_t *r_a,
+                     gcry_sexp_t keyparam, const char *name, mpi_ec_t ec);
+
 /* This tables defines aliases for curve names.  */
 static const struct
 {
@@ -782,7 +786,7 @@ _gcry_ecc_get_curve (gcry_sexp_t keyparms, int iterator, unsigned int *r_nbits)
   gpg_err_code_t rc;
   const char *result = NULL;
   elliptic_curve_t E;
-  gcry_mpi_t mpi_g = NULL;
+  gcry_mpi_point_t G = NULL;
   gcry_mpi_t tmp = NULL;
   int idx;
 
@@ -807,9 +811,8 @@ _gcry_ecc_get_curve (gcry_sexp_t keyparms, int iterator, unsigned int *r_nbits)
   /*
    * Extract the curve parameters..
    */
-  rc = gpg_err_code (sexp_extract_param (keyparms, NULL, "pabgn",
-                                         &E.p, &E.a, &E.b, &mpi_g, &E.n,
-                                         NULL));
+  rc = gpg_err_code (sexp_extract_param (keyparms, NULL, "pabn",
+                                         &E.p, &E.a, &E.b, &E.n, NULL));
   if (rc == GPG_ERR_NO_OBJ)
     {
       /* This might be the second use case of checking whether a
@@ -840,12 +843,12 @@ _gcry_ecc_get_curve (gcry_sexp_t keyparms, int iterator, unsigned int *r_nbits)
   if (rc)
     goto leave;
 
-  if (mpi_g)
-    {
-      _gcry_mpi_point_init (&E.G);
-      if (_gcry_ecc_os2ec (&E.G, mpi_g))
-        goto leave;
-    }
+  rc = point_from_keyparam (&G, keyparms, "g", NULL);
+  if (rc)
+    goto leave;
+
+  _gcry_mpi_point_init (&E.G);
+  _gcry_mpi_point_set (&E.G, G->x, G->y, G->z);
 
   for (idx = 0; domain_parms[idx].desc; idx++)
     {
@@ -886,11 +889,11 @@ _gcry_ecc_get_curve (gcry_sexp_t keyparms, int iterator, unsigned int *r_nbits)
     }
 
  leave:
+  _gcry_mpi_point_release (G);
   _gcry_mpi_release (tmp);
   _gcry_mpi_release (E.p);
   _gcry_mpi_release (E.a);
   _gcry_mpi_release (E.b);
-  _gcry_mpi_release (mpi_g);
   _gcry_mpi_point_free_parts (&E.G);
   _gcry_mpi_release (E.n);
   return result;
diff --git a/cipher/ecc-misc.c b/cipher/ecc-misc.c
index e7ccaff2..6470a83b 100644
--- a/cipher/ecc-misc.c
+++ b/cipher/ecc-misc.c
@@ -157,12 +157,13 @@ _gcry_mpi_ec_ec2os (gcry_mpi_point_t point, mpi_ec_t ec)
 }
 
 
-/* RESULT must have been initialized and is set on success to the
+/* Decode octet string in VALUE into RESULT, in the format defined by SEC 1.
+   RESULT must have been initialized and is set on success to the
    point given by VALUE.  */
-gcry_err_code_t
-_gcry_ecc_os2ec (mpi_point_t result, gcry_mpi_t value)
+gpg_err_code_t
+_gcry_ecc_sec_decodepoint  (gcry_mpi_t value, mpi_ec_t ec, mpi_point_t result)
 {
-  gcry_err_code_t rc;
+  gpg_err_code_t rc;
   size_t n;
   const unsigned char *buf;
   unsigned char *buf_memory;
@@ -196,29 +197,88 @@ _gcry_ecc_os2ec (mpi_point_t result, gcry_mpi_t value)
       xfree (buf_memory);
       return GPG_ERR_INV_OBJ;
     }
-  if (*buf != 4)
+
+  if (*buf == 2 || *buf == 3)
     {
+      gcry_mpi_t x3;
+      gcry_mpi_t t;
+      gcry_mpi_t p1_4;
+      int y_bit = (*buf == 3);
+
+      if (!mpi_test_bit (ec->p, 1))
+        {
+          xfree (buf_memory);
+          return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression.  */
+        }
+
+      n = n - 1;
+      rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL);
       xfree (buf_memory);
-      return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression.  */
+      if (rc)
+        return rc;
+
+      /*
+       * Recover Y.  The Weierstrass curve: y^2 = x^3 + a*x + b
+       */
+
+      x3 = mpi_new (0);
+      t = mpi_new (0);
+      p1_4 = mpi_new (0);
+      y = mpi_new (0);
+
+      /* Compute right hand side.  */
+      mpi_powm (x3, x, mpi_const (MPI_C_THREE), ec->p);
+      mpi_mul (t, ec->a, x);
+      mpi_mod (t, t, ec->p);
+      mpi_add (t, t, ec->b);
+      mpi_mod (t, t, ec->p);
+      mpi_add (t, t, x3);
+      mpi_mod (t, t, ec->p);
+
+      /*
+       * When p mod 4 = 3, modular square root of A can be computed by
+       * A^((p+1)/4) mod p
+       */
+
+      /* Compute (p+1)/4 into p1_4 */
+      mpi_rshift (p1_4, ec->p, 2);
+      _gcry_mpi_add_ui (p1_4, p1_4, 1);
+
+      mpi_powm (y, t, p1_4, ec->p);
+
+      if (y_bit != mpi_test_bit (y, 0))
+        mpi_sub (y, ec->p, y);
+
+      mpi_free (p1_4);
+      mpi_free (t);
+      mpi_free (x3);
     }
-  if ( ((n-1)%2) )
+  else if (*buf == 4)
     {
+      if ( ((n-1)%2) )
+        {
+          xfree (buf_memory);
+          return GPG_ERR_INV_OBJ;
+        }
+      n = (n-1)/2;
+      rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL);
+      if (rc)
+        {
+          xfree (buf_memory);
+          return rc;
+        }
+      rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL);
       xfree (buf_memory);
-      return GPG_ERR_INV_OBJ;
+      if (rc)
+        {
+          mpi_free (x);
+          return rc;
+        }
     }
-  n = (n-1)/2;
-  rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL);
-  if (rc)
+  else
     {
       xfree (buf_memory);
-      return rc;
-    }
-  rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL);
-  xfree (buf_memory);
-  if (rc)
-    {
-      mpi_free (x);
-      return rc;
+      return GPG_ERR_INV_OBJ;
     }
 
   mpi_set (result->x, x);
diff --git a/cipher/ecc-sm2.c b/cipher/ecc-sm2.c
index a6341132..135c7697 100644
--- a/cipher/ecc-sm2.c
+++ b/cipher/ecc-sm2.c
@@ -282,7 +282,7 @@ _gcry_ecc_sm2_decrypt (gcry_sexp_t *r_plain, gcry_sexp_t data_list, mpi_ec_t ec)
         goto leave_main;
       }
 
-    rc = _gcry_ecc_os2ec (&c1, data_c1);
+    rc = _gcry_ecc_sec_decodepoint (data_c1, ec, &c1);
     if (rc)
       goto leave_main;
 
diff --git a/cipher/ecc.c b/cipher/ecc.c
index 24b6febb..b4672d3d 100644
--- a/cipher/ecc.c
+++ b/cipher/ecc.c
@@ -1147,7 +1147,7 @@ ecc_decrypt_raw (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
   if (ec->model == MPI_EC_MONTGOMERY)
     rc = _gcry_ecc_mont_decodepoint (data_e, ec, &kG);
   else
-    rc = _gcry_ecc_os2ec (&kG, data_e);
+    rc = _gcry_ecc_sec_decodepoint (data_e, ec, &kG);
   if (rc)
     goto leave;
 
diff --git a/mpi/ec.c b/mpi/ec.c
index 0db70c76..659bb5ca 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -1013,7 +1013,7 @@ _gcry_mpi_ec_set_point (const char *name, gcry_mpi_point_t newvalue,
 gpg_err_code_t
 _gcry_mpi_ec_decode_point (mpi_point_t result, gcry_mpi_t value, mpi_ec_t ec)
 {
-  gcry_err_code_t rc;
+  gpg_err_code_t rc;
 
   if (ec
       && (ec->dialect == ECC_DIALECT_ED25519
@@ -1023,7 +1023,7 @@ _gcry_mpi_ec_decode_point (mpi_point_t result, gcry_mpi_t value, mpi_ec_t ec)
   else if (ec && ec->model == MPI_EC_MONTGOMERY)
     rc = _gcry_ecc_mont_decodepoint (value, ec, result);
   else
-    rc = _gcry_ecc_os2ec (result, value);
+    rc = _gcry_ecc_sec_decodepoint (value, ec, result);
 
   return rc;
 }
diff --git a/src/ec-context.h b/src/ec-context.h
index 959d1eb2..d1c64804 100644
--- a/src/ec-context.h
+++ b/src/ec-context.h
@@ -90,7 +90,8 @@ gpg_err_code_t   _gcry_ecc_set_point (const char *name,
                                       gcry_mpi_point_t newvalue, mpi_ec_t ec);
 
 /*-- cipher/ecc-misc.c --*/
-gcry_err_code_t _gcry_ecc_os2ec (mpi_point_t result, gcry_mpi_t value);
+gpg_err_code_t _gcry_ecc_sec_decodepoint (gcry_mpi_t value, mpi_ec_t ec,
+                                          mpi_point_t result);
 gpg_err_code_t _gcry_ecc_mont_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx,
                                            mpi_point_t result);
 
diff --git a/tests/basic.c b/tests/basic.c
index 8ccb9c66..ea13c50a 100644
--- a/tests/basic.c
+++ b/tests/basic.c
@@ -13749,8 +13749,7 @@ check_pubkey (void)
       "(public-key\n"
       " (ecdsa\n"
       "  (curve nistp192)\n"
-      "  (q #048532093BA023F4D55C0424FA3AF9367E05F309DC34CDC3FE"
-      "        C13CA9E617C6C8487BFF6A726E3C4F277913D97117939966#)))\n",
+      "  (q #028532093BA023F4D55C0424FA3AF9367E05F309DC34CDC3FE#)))\n",
 
       "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
       "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00" }
@@ -13827,9 +13826,8 @@ check_pubkey (void)
       "(public-key\n"
       " (ecc\n"
       "  (curve nistp256)\n"
-      "  (q #04D4F6A6738D9B8D3A7075C1E4EE95015FC0C9B7E4272D2B"
-      "      EB6644D3609FC781B71F9A8072F58CB66AE2F89BB1245187"
-      "      3ABF7D91F9E1FBF96BF2F70E73AAC9A283#)))\n",
+      "  (q #03D4F6A6738D9B8D3A7075C1E4EE95015FC0C9B7E4272D2B"
+      "      EB6644D3609FC781B7#)))\n",
 
       "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
       "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00" }