[PATCH] ecc: Improve Montgomery curve implementation
NIIBE Yutaka
gniibe at fsij.org
Wed Nov 19 08:39:58 CET 2014
Here is the change for Montgomery curve implementation. I forgot to
submit this change in August.
Adding test_ecdh_only_keys is needed when we will support encryption
by Curve25519 in future.
The changes in _gcry_mpi_ec_mul_point are to make sure resizing the
MPI representation of points, and code clean up.
OK to commit?
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.
--
diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c
index fd47c1d..9975bb4 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 8bdbd56..2f5e401 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 80f3b22..0b7c7a7 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_);
--
More information about the Gcrypt-devel
mailing list