more montgomery

6 files changed, 163 insertions, 35 deletions

diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c
index f4945e51..e7dbc17e 100644
--- a/cipher/ecc-curves.c
+++ b/cipher/ecc-curves.c
@@ -135,7 +135,7 @@ static const ecc_domain_parms_t domain_parms[] =
       "0x01DB41",
       "0x01",
       "0x1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED",
-      "0x09",
+      "0x0000000000000000000000000000000000000000000000000000000000000009",
       "0x20AE19A1B8A086B4E01EDD2C7748D14C923D4D7E6D7C61B229E9C5A27ECED3D9"
     },
 #if 0 /* No real specs yet found.  */
diff --git a/cipher/ecc-misc.c b/cipher/ecc-misc.c
index 3f284fe2..595aa0c3 100644
--- a/cipher/ecc-misc.c
+++ b/cipher/ecc-misc.c
@@ -202,8 +202,13 @@ _gcry_ecc_os2ec (mpi_point_t result, gcry_mpi_t value)
     }
   if (*buf != 4)
     {
+      /* x-coordinate only */
+      mpi_set (result->x, value);
+      mpi_clear (result->y);
+      mpi_set_ui (result->z, 1);
+
       xfree (buf_memory);
-      return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression.  */
+      return 0;
     }
   if ( ((n-1)%2) )
     {
diff --git a/cipher/ecc.c b/cipher/ecc.c
index e0be2d4f..6a60785f 100644
--- a/cipher/ecc.c
+++ b/cipher/ecc.c
@@ -117,7 +117,25 @@ nist_generate_key (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
   point_init (&Q);
 
   /* Generate a secret.  */
-  if (ctx->dialect == ECC_DIALECT_ED25519)
+  /*
+   * FIXME.  It should be something like this:
+   *
+   *   When the co-factor of the curve is not 1, we guarantee that
+   *   scalar value k is multiple of its co-factor to avoid sub-group
+   *   attack.  Also, we make sure that the most significant bit of k
+   *   is 1.
+   *
+   * It works for now as we only have two curves which have co-factor!=1;
+   * Ed25519 and Curve25519.
+   * Note that we need some a way to get number of bits of the curve to
+   * set MSB of k.  Currently, E.nbits is not precise for this purpuse.
+   * We also need a way to get co-factor of a curve.
+   *
+   * Currently, we distinguish the two curves by ECC_DIALECT_ED25519
+   * and MPI_EC_MONTGOMERY, which works, but is not that correct.
+   */
+  if (ctx->dialect == ECC_DIALECT_ED25519
+      || E->model == MPI_EC_MONTGOMERY)
     {
       char *rndbuf;
 
@@ -156,7 +174,7 @@ nist_generate_key (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
    * possibilities without any loss of security.  Note that we don't
    * do that for Ed25519 so that we do not violate the special
    * construction of the secret key.  */
-  if (E->dialect == ECC_DIALECT_ED25519)
+  if (E->dialect == ECC_DIALECT_ED25519 || E->model == MPI_EC_MONTGOMERY)
     point_set (&sk->Q, &Q);
   else
     {
@@ -227,12 +245,8 @@ static void
 test_keys (ECC_secret_key *sk, unsigned int nbits)
 {
   ECC_public_key pk;
-  gcry_mpi_t test = mpi_new (nbits);
+  gcry_mpi_t test;
   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);
-  gcry_mpi_t s = mpi_new (nbits);
 
   if (DBG_CIPHER)
     log_debug ("Testing key.\n");
@@ -243,27 +257,82 @@ test_keys (ECC_secret_key *sk, unsigned int nbits)
   point_init (&pk.Q);
   point_set (&pk.Q, &sk->Q);
 
-  _gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
+  if (sk->E.model == MPI_EC_MONTGOMERY)
+    /* It's ECDH only. */
+    /* FIXME: see the FIXME comment of nist_generate_key.
+     * Here, we generate ephemeral key, same handling is needed for secret.
+     */
+    {
+      char *rndbuf;
+      gcry_mpi_t x0, x1;
+      mpi_ec_t ec;
+
+      test = mpi_new (256);
+      rndbuf = _gcry_random_bytes (32, GCRY_WEAK_RANDOM);
+      rndbuf[0] &= 0x7f;  /* Clear bit 255. */
+      rndbuf[0] |= 0x40;  /* Set bit 254.   */
+      rndbuf[31] &= 0xf8; /* Clear bits 2..0 so that d mod 8 == 0  */
+      _gcry_mpi_set_buffer (test, rndbuf, 32, 0);
+      xfree (rndbuf);
+
+      ec = _gcry_mpi_ec_p_internal_new (pk.E.model, pk.E.dialect, 0,
+                                        pk.E.p, pk.E.a, pk.E.b);
+      x0 = mpi_new (0);
+      x1 = mpi_new (0);
 
-  if (_gcry_ecc_ecdsa_sign (test, sk, r, s, 0, 0) )
-    log_fatal ("ECDSA operation: sign failed\n");
+      /* R_ = kQ  <=>  R_ = kdG  */
+      _gcry_mpi_ec_mul_point (&R_, test, &pk.Q, ec);
+      if (_gcry_mpi_ec_get_affine (x0, NULL, &R_, ec))
+          log_fatal ("ecdh: Failed to get affine coordinates for kQ\n");
 
-  if (_gcry_ecc_ecdsa_verify (test, &pk, r, s))
-    {
-      log_fatal ("ECDSA operation: sign, verify failed\n");
+      /* R_ = kG */
+      _gcry_mpi_ec_mul_point (&R_, test, &pk.E.G, ec);
+      /* R_ = dkG */
+      _gcry_mpi_ec_mul_point (&R_, sk->d, &R_, ec);
+
+      if (_gcry_mpi_ec_get_affine (x1, NULL, &R_, ec))
+        log_fatal ("ecdh: Failed to get affine coordinates for dkG\n");
+
+      if (mpi_cmp (x0, x1))
+        {
+          log_fatal ("ECDH test failed.\n");
+        }
+
+      mpi_free (x0);
+      mpi_free (x1);
+      _gcry_mpi_ec_free (ec);
     }
+  else
+    {
+      gcry_mpi_t c = mpi_new (nbits);
+      gcry_mpi_t out = mpi_new (nbits);
+      gcry_mpi_t r = mpi_new (nbits);
+      gcry_mpi_t s = mpi_new (nbits);
 
-  if (DBG_CIPHER)
-    log_debug ("ECDSA operation: sign, verify ok.\n");
+      test = mpi_new (nbits);
+      _gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
+
+      if (_gcry_ecc_ecdsa_sign (test, sk, r, s, 0, 0) )
+        log_fatal ("ECDSA operation: sign failed\n");
+
+      if (_gcry_ecc_ecdsa_verify (test, &pk, r, s))
+        {
+          log_fatal ("ECDSA operation: sign, verify failed\n");
+        }
+
+      if (DBG_CIPHER)
+        log_debug ("ECDSA operation: sign, verify ok.\n");
+
+      mpi_free (s);
+      mpi_free (r);
+      mpi_free (out);
+      mpi_free (c);
+    }
 
   point_free (&pk.Q);
   _gcry_ecc_curve_free (&pk.E);
 
   point_free (&R_);
-  mpi_free (s);
-  mpi_free (r);
-  mpi_free (out);
-  mpi_free (c);
   mpi_free (test);
 }
 
diff --git a/mpi/ec.c b/mpi/ec.c
index 1257bbe2..ae2d6fa4 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -600,15 +600,11 @@ _gcry_mpi_ec_get_affine (gcry_mpi_t x, gcry_mpi_t y, mpi_point_t point,
 
     case MPI_EC_MONTGOMERY:
       {
-        gcry_mpi_t z1;
-
-        z1 = mpi_new (0);
-        ec_invm (z1, point->z, ctx);  /* z1 = z^(-1) mod p  */
-
         if (x)
-          ec_mulm (x, point->x, z1, ctx);
+          mpi_set (x, point->x);
 
-        mpi_free (z1);
+        if (y)
+          mpi_set (y, point->y);
       }
       return 0;
 
@@ -1238,19 +1234,22 @@ _gcry_mpi_ec_mul_point (mpi_point_t result,
           dup_and_add_montgomery (prd_n, sum_n, q1, q2, point->x, ctx);
         }
 
+      z1 = mpi_new (0);
+      mpi_clear (result->y);
+      mpi_set_ui (result->z, 1);
       if ((nbits & 1))
         {
-          mpi_snatch (result->x, p1_.x);
-          mpi_snatch (result->z, p1_.z);
-          p1_.x = p1_.z = NULL;
+          ec_invm (z1, p1_.z, ctx);
+          ec_mulm (result->x, p1_.x, z1, ctx);
+          mpi_clear (result->y);
         }
       else
         {
-          mpi_snatch (result->x, p1.x);
-          mpi_snatch (result->z, p1.z);
-          p1.x = p1.z = NULL;
+          ec_invm (z1, p1.z, ctx);
+          ec_mulm (result->x, p1.x, z1, ctx);
         }
 
+      mpi_free (z1);
       point_free (&p1);
       point_free (&p2);
       point_free (&p1_);
diff --git a/tests/curves.c b/tests/curves.c
index 29654f3f..5dc9d6d8 100644
--- a/tests/curves.c
+++ b/tests/curves.c
@@ -205,6 +205,11 @@ check_montgomery (void)
   const char *name;
   unsigned int nbits;
 
+  gcry_ctx_t ctx;
+  gcry_mpi_point_t G, Q;
+  gcry_mpi_t d;
+  gcry_mpi_t x, y, z;
+
   err = gcry_sexp_new (&key, sample_key_3, 0, 1);
   if (err)
     die ("parsing s-expression string failed: %s\n", gpg_strerror (err));
@@ -219,6 +224,56 @@ check_montgomery (void)
           sample_key_3_nbits, nbits);
 
   gcry_sexp_release (key);
+
+  Q = gcry_mpi_point_new (0);
+
+  err = gcry_mpi_ec_new (&ctx, NULL, "Curve25519");
+  if (err)
+    fail ("can't create ec context: %s\n", gpg_strerror (err));
+
+#if 0
+  d = hex2mpi ("40000000000000000000000000000000"
+               "00000000000000000000000000000000");
+  G = gcry_mpi_ec_get_point ("g", ctx, 1);
+  if (!G)
+    fail ("can't get basepoint of the curve: %s\n", gpg_strerror (err));
+#else
+  d = hex2mpi ("7d74fb61db3100e11e4d4ae171daf820688f3bcfa631565272a998b8f4e8c290");
+  {
+    gcry_mpi_t gx;
+    gx = hex2mpi ("3dc16d73d4222d12eb54623c85f3fb5ebdab33c1bd5865780654f1b0ed696ddf");
+
+    G = gcry_mpi_point_new (0);
+    gcry_mpi_point_snatch_set (G, gx, NULL, NULL);
+  }
+#endif
+
+  gcry_mpi_ec_mul (Q, d, G, ctx);
+
+  x = gcry_mpi_new (0);
+  y = gcry_mpi_new (0);
+  z = gcry_mpi_new (0);
+
+  gcry_mpi_point_get (x, y, z, Q);
+
+  print_mpi ("Q.x", x);
+  print_mpi ("Q.y", y);
+  print_mpi ("Q.z", z);
+
+  if (gcry_mpi_ec_get_affine (x, NULL, Q, ctx))
+    fail ("failed to get affine coordinates\n");
+
+  print_mpi ("q.x", x);
+  /* 16B53A046DEEDD81ED6B0D470CE46DD9B5FAC6124F3D22358AA7CD2911FCFABC */
+
+  gcry_mpi_release (z);
+  gcry_mpi_release (y);
+  gcry_mpi_release (x);
+
+  gcry_mpi_point_release (Q);
+  gcry_mpi_release (d);
+  gcry_mpi_point_release (G);
+  gcry_ctx_release (ctx);
 }
 
 int
diff --git a/tests/keygen.c b/tests/keygen.c
index 4aff9c96..c53246c9 100644
--- a/tests/keygen.c
+++ b/tests/keygen.c
@@ -365,7 +365,7 @@ static void
 check_ecc_keys (void)
 {
   const char *curves[] = { "NIST P-521", "NIST P-384", "NIST P-256",
-                           "Ed25519", NULL };
+                           "Ed25519", "Curve25519", NULL };
   int testno;
   gcry_sexp_t keyparm, key;
   int rc;