Add Curve25519

3 files changed, 153 insertions, 2 deletions

diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c
index 0f622f73..6a90eafc 100644
--- a/cipher/ecc-curves.c
+++ b/cipher/ecc-curves.c
@@ -40,7 +40,7 @@ static const struct
   const char *other; /* Other name. */
 } curve_aliases[] =
   {
-  /*{ "Curve25519", "1.3.6.1.4.1.3029.1.5.1" },*/
+    { "Curve25519", "1.3.6.1.4.1.3029.1.5.1" },
     { "Ed25519",    "1.3.6.1.4.1.11591.15.1" },
 
     { "NIST P-192", "1.2.840.10045.3.1.1" }, /* X9.62 OID  */
@@ -127,6 +127,17 @@ static const ecc_domain_parms_t domain_parms[] =
       "0x216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A",
       "0x6666666666666666666666666666666666666666666666666666666666666658"
     },
+    {
+      /* (y^2 = x^3 + 486662*x^2 + x) */
+      "Curve25519", 256, 0,
+      MPI_EC_MONTGOMERY, ECC_DIALECT_STANDARD,
+      "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED",
+      "0X1DB41",
+      "0x1",
+      "0x1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED",
+      "0x9",
+      "0x20AE19A1B8A086B4E01EDD2C7748D14C923D4D7E6D7C61B229E9C5A27ECED3D9"
+    },
 #if 0 /* No real specs yet found.  */
     {
       /* x^2 + y^2 = 1 + 3617x^2y^2 mod 2^414 - 17 */
diff --git a/mpi/ec.c b/mpi/ec.c
index 4f35de04..c4ac819d 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -1073,6 +1073,35 @@ add_points_edwards (mpi_point_t result,
 }
 
 
+/* PRD = 2 * P1.
+   SUM = P1 + P2.
+   P1 - P2 = DIF  */
+static void
+dup_and_add_montgomery (mpi_point_t prd, mpi_point_t sum,
+                        mpi_point_t p1, mpi_point_t p2, gcry_mpi_t dif_x,
+                        mpi_ec_t ctx)
+{
+  ec_addm (sum->x, p2->x, p2->z, ctx);
+  ec_subm (p2->z, p2->x, p2->z, ctx);
+  ec_addm (prd->x, p1->x, p1->z, ctx);
+  ec_subm (p1->z, p1->x, p1->z, ctx);
+  ec_mulm (p2->x, p1->z, sum->x, ctx);
+  ec_mulm (p2->z, prd->x, p2->z, ctx);
+  ec_pow2 (p1->x, prd->x, ctx);
+  ec_pow2 (p1->z, p1->z, ctx);
+  ec_addm (sum->x, p2->x, p2->z, ctx);
+  ec_subm (p2->z, p2->x, p2->z, ctx);
+  ec_mulm (prd->x, p1->x, p1->z, ctx);
+  ec_subm (p1->z, p1->x, p1->z, ctx);
+  ec_pow2 (sum->x, sum->x, ctx);
+  ec_pow2 (sum->z, p2->z, ctx);
+  ec_mulm (prd->z, p1->z, ctx->a, ctx);	/* ctx->a: (A-2)/4 */
+  ec_mulm (sum->z, sum->z, dif_x, ctx);
+  ec_addm (prd->z, p1->x, prd->z, ctx);
+  ec_mulm (prd->z, prd->z, p1->z, ctx);
+}
+
+
 /* RESULT = P1 + P2 */
 void
 _gcry_mpi_ec_add_points (mpi_point_t result,
@@ -1144,6 +1173,80 @@ _gcry_mpi_ec_mul_point (mpi_point_t result,
         }
       return;
     }
+  else if (ctx->model == MPI_EC_MONTGOMERY)
+    {
+      unsigned int nbits;
+      int j;
+      mpi_point_struct p1_, p2_;
+
+      nbits = mpi_get_nbits (scalar);
+      point_init (&p1);
+      mpi_set_ui (p1.x, 1);
+      p2.x  = mpi_copy (scalar);
+      p2.y = mpi_new (0);
+      p2.z = mpi_new (1);
+      point_init (&p1_);
+      point_init (&p2_);
+
+      for (j=nbits-1; j >= 0; j--)
+	{
+	  mpi_point_t q1, q2;
+	  mpi_point_t sum_n, prd_n;
+
+	  if (mpi_test_bit (scalar, j))
+	    {
+	      q1 = &p2;
+	      q2 = &p1;
+	      sum_n = &p1_;
+	      prd_n = &p2_;
+	    }
+	  else
+	    {
+	      q1 = &p1;
+	      q2 = &p2;
+	      sum_n = &p2_;
+	      prd_n = &p1_;
+	    }
+	  dup_and_add_montgomery (prd_n, sum_n, q1, q2, point->x, ctx);
+
+	  if (--j < 0)
+	    break;
+
+	  if (mpi_test_bit (scalar, j))
+	    {
+	      q1 = &p2_;
+	      q2 = &p1_;
+	      sum_n = &p1;
+	      prd_n = &p2;
+	    }
+	  else
+	    {
+	      q1 = &p1_;
+	      q2 = &p2_;
+	      sum_n = &p2;
+	      prd_n = &p1;
+	    }
+
+	  dup_and_add_montgomery (prd_n, sum_n, q1, q2, point->x, ctx);
+	}
+
+      if ((nbits & 1))
+	{
+	  ec_invm (result->x, p1_.z, ctx);
+	  ec_mulm (result->x, result->x, p1_.x, ctx);
+	}
+      else
+	{
+	  ec_invm (result->x, p1.z, ctx);
+	  ec_mulm (result->x, result->x, p1.x, ctx);
+	}
+
+      point_free (&p1);
+      point_free (&p2);
+      point_free (&p1_);
+      point_free (&p2_);
+      return;
+    }
 
   x1 = mpi_alloc_like (ctx->p);
   y1 = mpi_alloc_like (ctx->p);
diff --git a/tests/curves.c b/tests/curves.c
index 05814527..29654f3f 100644
--- a/tests/curves.c
+++ b/tests/curves.c
@@ -29,7 +29,7 @@
 #include "../src/gcrypt-int.h"
 
 /* Number of curves defined in ../cipger/ecc.c */
-#define N_CURVES 21
+#define N_CURVES 22
 
 /* A real world sample public key.  */
 static char const sample_key_1[] =
@@ -64,6 +64,18 @@ static char const sample_key_2_curve[] = "brainpoolP160r1";
 static unsigned int sample_key_2_nbits = 160;
 
 
+/* Another sample public key.  */
+static char const sample_key_3[] =
+"(public-key\n"
+" (ecdh\n"
+"  (curve Curve25519)\n"
+"  (q #040000000000000000000000000000000000000000000000000000000000000000"
+"        0000000000000000000000000000000000000000000000000000000000000000#)\n"
+"  ))";
+static char const sample_key_3_curve[] = "Curve25519";
+static unsigned int sample_key_3_nbits = 256;
+
+
 /* Program option flags.  */
 static int verbose;
 static int error_count;
@@ -185,6 +197,30 @@ check_get_params (void)
 }
 
 
+static void
+check_montgomery (void)
+{
+  gpg_error_t err;
+  gcry_sexp_t key;
+  const char *name;
+  unsigned int nbits;
+
+  err = gcry_sexp_new (&key, sample_key_3, 0, 1);
+  if (err)
+    die ("parsing s-expression string failed: %s\n", gpg_strerror (err));
+  name = gcry_pk_get_curve (key, 0, &nbits);
+  if (!name)
+    fail ("curve name not found for sample_key_3\n");
+  else if (strcmp (name, sample_key_3_curve))
+    fail ("expected curve name %s but got %s for sample_key_3\n",
+          sample_key_3_curve, name);
+  else if (nbits != sample_key_3_nbits)
+    fail ("expected curve size %u but got %u for sample_key_3\n",
+          sample_key_3_nbits, nbits);
+
+  gcry_sexp_release (key);
+}
+
 int
 main (int argc, char **argv)
 {
@@ -205,6 +241,7 @@ main (int argc, char **argv)
   list_curves ();
   check_matching ();
   check_get_params ();
+  check_montgomery ();
 
   return error_count ? 1 : 0;
 }