ecc: Improve Montgomery curve implementation.

* cipher/ecc-curves.c (_gcry_ecc_fill_in_curve): Support
MPI_EC_MONTGOMERY.
* cipher/ecc.c (test_ecdh_only_keys): New.
(nist_generate_key): Call test_ecdh_only_keys for MPI_EC_MONTGOMERY.
(check_secret_key): Handle Montgomery curve of x-coordinate only.
* mpi/ec.c (_gcry_mpi_ec_mul_point): Resize points before the loop.
Simplify, using pointers of Q1, Q2, PRD, and SUM.
--

3 files changed, 113 insertions, 22 deletions

diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c
index fd47c1dc..9975bb42 100644
--- a/cipher/ecc-curves.c
+++ b/cipher/ecc-curves.c
@@ -530,9 +530,8 @@ _gcry_ecc_fill_in_curve (unsigned int nbits, const char *name,
     {
     case MPI_EC_WEIERSTRASS:
     case MPI_EC_EDWARDS:
-      break;
     case MPI_EC_MONTGOMERY:
-      return GPG_ERR_NOT_SUPPORTED;
+      break;
     default:
       return GPG_ERR_BUG;
     }
diff --git a/cipher/ecc.c b/cipher/ecc.c
index 8bdbd565..2f5e401f 100644
--- a/cipher/ecc.c
+++ b/cipher/ecc.c
@@ -81,6 +81,7 @@ static void *progress_cb_data;
 
 /* Local prototypes. */
 static void test_keys (ECC_secret_key * sk, unsigned int nbits);
+static void test_ecdh_only_keys (ECC_secret_key * sk, unsigned int nbits);
 static unsigned int ecc_get_nbits (gcry_sexp_t parms);
 
 
@@ -209,7 +210,10 @@ nist_generate_key (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
 
   point_free (&Q);
   /* Now we can test our keys (this should never fail!).  */
-  test_keys (sk, nbits - 64);
+  if (sk->E.model != MPI_EC_MONTGOMERY)
+    test_keys (sk, nbits - 64);
+  else
+    test_ecdh_only_keys (sk, nbits - 64);
 
   return 0;
 }
@@ -266,6 +270,80 @@ test_keys (ECC_secret_key *sk, unsigned int nbits)
 }
 
 
+static void
+test_ecdh_only_keys (ECC_secret_key *sk, unsigned int nbits)
+{
+  ECC_public_key pk;
+  gcry_mpi_t test;
+  mpi_point_struct R_;
+  gcry_mpi_t x0, x1;
+  mpi_ec_t ec;
+
+  if (DBG_CIPHER)
+    log_debug ("Testing key.\n");
+
+  point_init (&R_);
+
+  pk.E = _gcry_ecc_curve_copy (sk->E);
+  point_init (&pk.Q);
+  point_set (&pk.Q, &sk->Q);
+
+  if (sk->E.dialect == ECC_DIALECT_ED25519)
+    {
+      char *rndbuf;
+
+      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);
+    }
+  else
+    {
+      test = mpi_new (nbits);
+      _gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
+    }
+
+  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);
+
+  /* R_ = hkQ  <=>  R_ = hkdG  */
+  _gcry_mpi_ec_mul_point (&R_, test, &pk.Q, ec);
+  if (sk->E.dialect != ECC_DIALECT_ED25519)
+    _gcry_mpi_ec_mul_point (&R_, ec->h, &R_, ec);
+  if (_gcry_mpi_ec_get_affine (x0, NULL, &R_, ec))
+    log_fatal ("ecdh: Failed to get affine coordinates for hkQ\n");
+
+  _gcry_mpi_ec_mul_point (&R_, test, &pk.E.G, ec);
+  _gcry_mpi_ec_mul_point (&R_, sk->d, &R_, ec);
+  /* R_ = hdkG */
+  if (sk->E.dialect != ECC_DIALECT_ED25519)
+    _gcry_mpi_ec_mul_point (&R_, ec->h, &R_, ec);
+
+  if (_gcry_mpi_ec_get_affine (x1, NULL, &R_, ec))
+    log_fatal ("ecdh: Failed to get affine coordinates for hdkG\n");
+
+  if (mpi_cmp (x0, x1))
+    {
+      log_fatal ("ECDH test failed.\n");
+    }
+
+  mpi_free (x0);
+  mpi_free (x1);
+  _gcry_mpi_ec_free (ec);
+
+  point_free (&pk.Q);
+  _gcry_ecc_curve_free (&pk.E);
+
+  point_free (&R_);
+  mpi_free (test);
+}
+
+
 /*
  * To check the validity of the value, recalculate the correspondence
  * between the public value and the secret one.
@@ -281,7 +359,10 @@ check_secret_key (ECC_secret_key *sk, mpi_ec_t ec, int flags)
 
   point_init (&Q);
   x1 = mpi_new (0);
-  y1 = mpi_new (0);
+  if (ec->model == MPI_EC_MONTGOMERY)
+    y1 = NULL;
+  else
+    y1 = mpi_new (0);
 
   /* G in E(F_p) */
   if (!_gcry_mpi_ec_curve_point (&sk->E.G, ec))
@@ -338,7 +419,7 @@ check_secret_key (ECC_secret_key *sk, mpi_ec_t ec, int flags)
   else if (!mpi_cmp_ui (sk->Q.z, 1))
     {
       /* Fast path if Q is already in affine coordinates.  */
-      if (mpi_cmp (x1, sk->Q.x) || mpi_cmp (y1, sk->Q.y))
+      if (mpi_cmp (x1, sk->Q.x) || (!y1 && mpi_cmp (y1, sk->Q.y)))
         {
           if (DBG_CIPHER)
             log_debug
@@ -1581,7 +1662,7 @@ compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparms)
       char buf[30];
 
       if (idx == 5)
-	continue;		/* Skip cofactor. */
+        continue;               /* Skip cofactor. */
 
       if (mpi_is_opaque (values[idx]))
         {
diff --git a/mpi/ec.c b/mpi/ec.c
index 80f3b220..0b7c7a71 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -1251,7 +1251,9 @@ _gcry_mpi_ec_mul_point (mpi_point_t result,
       unsigned int nbits;
       int j;
       mpi_point_struct p1_, p2_;
+      mpi_point_t q1, q2, prd, sum;
       unsigned long sw;
+      size_t nlimbs;
 
       /* Compute scalar point multiplication with Montgomery Ladder.
          Note that we don't use Y-coordinate in the points at all.
@@ -1267,27 +1269,35 @@ _gcry_mpi_ec_mul_point (mpi_point_t result,
       p2.x  = mpi_copy (point->x);
       mpi_set_ui (p2.z, 1);
 
+      nlimbs = 2*(nbits+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB+1;
+      mpi_resize (p1.x, nlimbs);
+      mpi_resize (p1.z, nlimbs);
+      mpi_resize (p2.x, nlimbs);
+      mpi_resize (p2.z, nlimbs);
+      mpi_resize (p1_.x, nlimbs);
+      mpi_resize (p1_.z, nlimbs);
+      mpi_resize (p2_.x, nlimbs);
+      mpi_resize (p2_.z, nlimbs);
+
+      q1 = &p1;
+      q2 = &p2;
+      prd = &p1_;
+      sum = &p2_;
+
       for (j=nbits-1; j >= 0; j--)
         {
-          sw = mpi_test_bit (scalar, j);
-          mpi_swap_cond (p1.x, p2.x, sw);
-          mpi_swap_cond (p1.z, p2.z, sw);
-          montgomery_ladder (&p1_, &p2_, &p1, &p2, point->x, ctx);
-          mpi_swap_cond (p1_.x, p2_.x, sw);
-          mpi_swap_cond (p1_.z, p2_.z, sw);
-
-          if (--j < 0)
-            break;
+          mpi_point_t t;
 
           sw = mpi_test_bit (scalar, j);
-          mpi_swap_cond (p1_.x, p2_.x, sw);
-          mpi_swap_cond (p1_.z, p2_.z, sw);
-          montgomery_ladder (&p1, &p2, &p1_, &p2_, point->x, ctx);
-          mpi_swap_cond (p1.x, p2.x, sw);
-          mpi_swap_cond (p1.z, p2.z, sw);
+          mpi_swap_cond (q1->x, q2->x, sw);
+          mpi_swap_cond (q1->z, q2->z, sw);
+          montgomery_ladder (prd, sum, q1, q2, point->x, ctx);
+          mpi_swap_cond (prd->x, sum->x, sw);
+          mpi_swap_cond (prd->z, sum->z, sw);
+          t = q1;  q1 = prd;  prd = t;
+          t = q2;  q2 = sum;  sum = t;
         }
 
-      z1 = mpi_new (0);
       mpi_clear (result->y);
       sw = (nbits & 1);
       mpi_swap_cond (p1.x, p1_.x, sw);
@@ -1300,12 +1310,13 @@ _gcry_mpi_ec_mul_point (mpi_point_t result,
         }
       else
         {
+          z1 = mpi_new (0);
           ec_invm (z1, p1.z, ctx);
           ec_mulm (result->x, p1.x, z1, ctx);
           mpi_set_ui (result->z, 1);
+          mpi_free (z1);
         }
 
-      mpi_free (z1);
       point_free (&p1);
       point_free (&p2);
       point_free (&p1_);