[git] GCRYPT - branch, master, updated. libgcrypt-1.6.0-105-g34bb55e
by NIIBE Yutaka
cvs at cvs.gnupg.org
Tue Aug 12 03:11:55 CEST 2014
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "The GNU crypto library".
The branch, master has been updated
via 34bb55ee36df3aca3ebca88f8b61c786cd0c0701 (commit)
from e6d354865bf8f3d4c1bb5e8157a76fdd442cff41 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit 34bb55ee36df3aca3ebca88f8b61c786cd0c0701
Author: NIIBE Yutaka <gniibe at fsij.org>
Date: Tue Aug 12 10:03:39 2014 +0900
ecc: Support Montgomery curve for gcry_mpi_ec_mul_point.
* mpi/ec.c (_gcry_mpi_ec_get_affine): Support Montgomery curve.
(montgomery_ladder): New.
(_gcry_mpi_ec_mul_point): Implemention using montgomery_ladder.
(_gcry_mpi_ec_curve_point): Check x-coordinate is valid.
--
Given Montgomery curve: b * y^2 == x^3 + a * x^2 + x
CTX->A has (a-2)/4 and CTX->B has b^-1
Note that _gcry_mpi_ec_add_points is not supported for this curve.
diff --git a/mpi/ec.c b/mpi/ec.c
index 737f12c..a55291a 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);
@@ -1243,15 +1345,15 @@ _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
y = mpi_new (0);
w = mpi_new (0);
- if (_gcry_mpi_ec_get_affine (x, y, point, ctx))
- return 0;
-
switch (ctx->model)
{
case MPI_EC_WEIERSTRASS:
{
gcry_mpi_t xxx = mpi_new (0);
+ if (_gcry_mpi_ec_get_affine (x, y, point, ctx))
+ return 0;
+
/* y^2 == x^3 + a·x + b */
ec_pow2 (y, y, ctx);
@@ -1267,11 +1369,40 @@ _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
}
break;
case MPI_EC_MONTGOMERY:
- log_fatal ("%s: %s not yet supported\n",
- "_gcry_mpi_ec_curve_point", "Montgomery");
+ {
+#define xx y
+ /* With Montgomery curve, only X-coordinate is valid. */
+ if (_gcry_mpi_ec_get_affine (x, NULL, point, ctx))
+ return 0;
+
+ /* The equation is: b * y^2 == x^3 + a · x^2 + x */
+ /* We check if right hand is quadratic residue or not by
+ Euler's criterion. */
+ /* CTX->A has (a-2)/4 and CTX->B has b^-1 */
+ ec_mulm (w, ctx->a, mpi_const (MPI_C_FOUR), ctx);
+ ec_addm (w, w, mpi_const (MPI_C_TWO), ctx);
+ ec_mulm (w, w, x, ctx);
+ ec_pow2 (xx, x, ctx);
+ ec_addm (w, w, xx, ctx);
+ ec_addm (w, w, mpi_const (MPI_C_ONE), ctx);
+ ec_mulm (w, w, x, ctx);
+ ec_mulm (w, w, ctx->b, ctx);
+#undef xx
+ /* Compute Euler's criterion: w^(p-1)/2 */
+#define p_minus1 y
+ ec_subm (p_minus1, ctx->p, mpi_const (MPI_C_ONE), ctx);
+ mpi_rshift (p_minus1, p_minus1, 1);
+ ec_powm (w, w, p_minus1, ctx);
+
+ res = mpi_cmp_ui (w, 1);
+#undef p_minus1
+ }
break;
case MPI_EC_EDWARDS:
{
+ if (_gcry_mpi_ec_get_affine (x, y, point, ctx))
+ return 0;
+
/* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */
ec_pow2 (x, x, ctx);
ec_pow2 (y, y, ctx);
-----------------------------------------------------------------------
Summary of changes:
mpi/ec.c | 147 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----
1 file changed, 139 insertions(+), 8 deletions(-)
hooks/post-receive
--
The GNU crypto library
http://git.gnupg.org
_______________________________________________
Gnupg-commits mailing list
Gnupg-commits at gnupg.org
http://lists.gnupg.org/mailman/listinfo/gnupg-commits
More information about the Gcrypt-devel
mailing list