[PATCH] ecc: support Montgomery curve for gcry_mpi_ec_add_points

[NIIBE Yutaka]

Here is a patch to support Montgomery curve for gcry_mpi_ec_mul_point.

Only x-coordinate is valid for this curve.

OK to commit?

diff --git a/mpi/ec.c b/mpi/ec.c
index 737f12c..2dc97aa 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -601,10 +601,17 @@ _gcry_mpi_ec_get_affine (gcry_mpi_t x, gcry_mpi_t y, mpi_point_t point,
 
     case MPI_EC_MONTGOMERY:
       {
-        log_fatal ("%s: %s not yet supported\n",
-                   "_gcry_mpi_ec_get_affine", "Montgomery");
+        if (x)
+          mpi_set (x, point->x);
+
+        if (y)
+          {
+            log_fatal ("%s: Getting Y-coordinate on %s is not supported\n",
+                       "_gcry_mpi_ec_get_affine", "Montgomery");
+            return -1;
+          }
       }
-      return -1;
+      return 0;
 
     case MPI_EC_EDWARDS:
       {
@@ -1074,6 +1081,35 @@ add_points_edwards (mpi_point_t result,
 }
 

+/* Compute a step of Montgomery Ladder (only use X and Z in the point).
+   Inputs:  P1, P2, and x-coordinate of DIF = P1 - P1.
+   Outputs: PRD = 2 * P1 and  SUM = P1 + P2. */
+static void
+montgomery_ladder (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,
@@ -1145,6 +1181,72 @@ _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_;
+      unsigned long sw;
+
+      /* Compute scalar point multiplication with Montgomery Ladder.
+         Note that we don't use Y-coordinate in the points at all.
+         RESULT->Y will be filled by zero.  */
+
+      nbits = mpi_get_nbits (scalar);
+      point_init (&p1);
+      point_init (&p2);
+      point_init (&p1_);
+      point_init (&p2_);
+      mpi_set_ui (p1.x, 1);
+      mpi_free (p2.x);
+      p2.x  = mpi_copy (point->x);
+      mpi_set_ui (p2.z, 1);
+
+      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;
+
+          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);
+        }
+
+      z1 = mpi_new (0);
+      mpi_clear (result->y);
+      sw = (nbits & 1);
+      mpi_swap_cond (p1.x, p1_.x, sw);
+      mpi_swap_cond (p1.z, p1_.z, sw);
+
+      if (p1.z->nlimbs == 0)
+        {
+          mpi_set_ui (result->x, 1);
+          mpi_set_ui (result->z, 0);
+        }
+      else
+        {
+          ec_invm (z1, p1.z, ctx);
+          ec_mulm (result->x, p1.x, z1, ctx);
+          mpi_set_ui (result->z, 1);
+        }
+
+      mpi_free (z1);
+      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);
--