From a2b17d3639b7abb55decb67afbf8561a544c1cd7 Mon Sep 17 00:00:00 2001 From: NIIBE Yutaka Date: Fri, 18 Apr 2014 18:38:15 +0900 Subject: Add Curve25519 --- cipher/ecc-curves.c | 13 ++++++- mpi/ec.c | 103 ++++++++++++++++++++++++++++++++++++++++++++++++++++ tests/curves.c | 39 +++++++++++++++++++- 3 files changed, 153 insertions(+), 2 deletions(-) diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c index 0f622f73..6a90eafc 100644 --- a/cipher/ecc-curves.c +++ b/cipher/ecc-curves.c @@ -40,7 +40,7 @@ static const struct const char *other; /* Other name. */ } curve_aliases[] = { - /*{ "Curve25519", "1.3.6.1.4.1.3029.1.5.1" },*/ + { "Curve25519", "1.3.6.1.4.1.3029.1.5.1" }, { "Ed25519", "1.3.6.1.4.1.11591.15.1" }, { "NIST P-192", "1.2.840.10045.3.1.1" }, /* X9.62 OID */ @@ -127,6 +127,17 @@ static const ecc_domain_parms_t domain_parms[] = "0x216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A", "0x6666666666666666666666666666666666666666666666666666666666666658" }, + { + /* (y^2 = x^3 + 486662*x^2 + x) */ + "Curve25519", 256, 0, + MPI_EC_MONTGOMERY, ECC_DIALECT_STANDARD, + "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED", + "0X1DB41", + "0x1", + "0x1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED", + "0x9", + "0x20AE19A1B8A086B4E01EDD2C7748D14C923D4D7E6D7C61B229E9C5A27ECED3D9" + }, #if 0 /* No real specs yet found. */ { /* x^2 + y^2 = 1 + 3617x^2y^2 mod 2^414 - 17 */ diff --git a/mpi/ec.c b/mpi/ec.c index 4f35de04..c4ac819d 100644 --- a/mpi/ec.c +++ b/mpi/ec.c @@ -1073,6 +1073,35 @@ add_points_edwards (mpi_point_t result, } +/* PRD = 2 * P1. + SUM = P1 + P2. + P1 - P2 = DIF */ +static void +dup_and_add_montgomery (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, @@ -1144,6 +1173,80 @@ _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_; + + nbits = mpi_get_nbits (scalar); + point_init (&p1); + mpi_set_ui (p1.x, 1); + p2.x = mpi_copy (scalar); + p2.y = mpi_new (0); + p2.z = mpi_new (1); + point_init (&p1_); + point_init (&p2_); + + for (j=nbits-1; j >= 0; j--) + { + mpi_point_t q1, q2; + mpi_point_t sum_n, prd_n; + + if (mpi_test_bit (scalar, j)) + { + q1 = &p2; + q2 = &p1; + sum_n = &p1_; + prd_n = &p2_; + } + else + { + q1 = &p1; + q2 = &p2; + sum_n = &p2_; + prd_n = &p1_; + } + dup_and_add_montgomery (prd_n, sum_n, q1, q2, point->x, ctx); + + if (--j < 0) + break; + + if (mpi_test_bit (scalar, j)) + { + q1 = &p2_; + q2 = &p1_; + sum_n = &p1; + prd_n = &p2; + } + else + { + q1 = &p1_; + q2 = &p2_; + sum_n = &p2; + prd_n = &p1; + } + + dup_and_add_montgomery (prd_n, sum_n, q1, q2, point->x, ctx); + } + + if ((nbits & 1)) + { + ec_invm (result->x, p1_.z, ctx); + ec_mulm (result->x, result->x, p1_.x, ctx); + } + else + { + ec_invm (result->x, p1.z, ctx); + ec_mulm (result->x, result->x, p1.x, ctx); + } + + 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); diff --git a/tests/curves.c b/tests/curves.c index 05814527..29654f3f 100644 --- a/tests/curves.c +++ b/tests/curves.c @@ -29,7 +29,7 @@ #include "../src/gcrypt-int.h" /* Number of curves defined in ../cipger/ecc.c */ -#define N_CURVES 21 +#define N_CURVES 22 /* A real world sample public key. */ static char const sample_key_1[] = @@ -64,6 +64,18 @@ static char const sample_key_2_curve[] = "brainpoolP160r1"; static unsigned int sample_key_2_nbits = 160; +/* Another sample public key. */ +static char const sample_key_3[] = +"(public-key\n" +" (ecdh\n" +" (curve Curve25519)\n" +" (q #040000000000000000000000000000000000000000000000000000000000000000" +" 0000000000000000000000000000000000000000000000000000000000000000#)\n" +" ))"; +static char const sample_key_3_curve[] = "Curve25519"; +static unsigned int sample_key_3_nbits = 256; + + /* Program option flags. */ static int verbose; static int error_count; @@ -185,6 +197,30 @@ check_get_params (void) } +static void +check_montgomery (void) +{ + gpg_error_t err; + gcry_sexp_t key; + const char *name; + unsigned int nbits; + + err = gcry_sexp_new (&key, sample_key_3, 0, 1); + if (err) + die ("parsing s-expression string failed: %s\n", gpg_strerror (err)); + name = gcry_pk_get_curve (key, 0, &nbits); + if (!name) + fail ("curve name not found for sample_key_3\n"); + else if (strcmp (name, sample_key_3_curve)) + fail ("expected curve name %s but got %s for sample_key_3\n", + sample_key_3_curve, name); + else if (nbits != sample_key_3_nbits) + fail ("expected curve size %u but got %u for sample_key_3\n", + sample_key_3_nbits, nbits); + + gcry_sexp_release (key); +} + int main (int argc, char **argv) { @@ -205,6 +241,7 @@ main (int argc, char **argv) list_curves (); check_matching (); check_get_params (); + check_montgomery (); return error_count ? 1 : 0; } -- cgit v1.2.1