[PATCH] ecc: support Montgomery curve for gcry_mpi_ec_add_points
NIIBE Yutaka
gniibe at fsij.org
Fri Aug 8 04:22:18 CEST 2014
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);
--
More information about the Gcrypt-devel
mailing list