diff options
author | NIIBE Yutaka <gniibe@fsij.org> | 2014-11-19 15:48:12 +0900 |
---|---|---|
committer | NIIBE Yutaka <gniibe@fsij.org> | 2014-11-19 16:03:51 +0900 |
commit | e6130034506013d6153465a2bedb6fb08a43f74d (patch) | |
tree | bd1a881ffac12ab5c413c84406d7aa4a9fc07acb | |
parent | 95eef21583d8e998efc48f22898c1ae31b77cb48 (diff) | |
download | libgcrypt-e6130034506013d6153465a2bedb6fb08a43f74d.tar.gz |
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.
--
-rw-r--r-- | cipher/ecc-curves.c | 3 | ||||
-rw-r--r-- | cipher/ecc.c | 89 | ||||
-rw-r--r-- | mpi/ec.c | 43 |
3 files changed, 113 insertions, 22 deletions
diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c index fd47c1dc..9975bb42 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 8bdbd565..2f5e401f 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])) { @@ -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_); |