[PATCH] Curve25519 support
NIIBE Yutaka
gniibe at fsij.org
Wed Apr 23 13:06:13 CEST 2014
Hello,
Here is a patch to support Curve25519. It's not mature, to be
revised, but it works for me with GnuPG (with patch).
I'm posting this now, to share what's going on my side.
In this code, we don't put any information in Y (it's 0), and
it is assumed that only X coordinate will be used by ECDH.
TODO:
It breaks "make check". It fails now.
We need to consider number of bits in Elliptic curve domain parameter.
We have the field, but it's not precise, and it's a kind of UI. We
need precise number of bits so that we can use the information for key
generation.
We need to consider to have cofactor field in Elliptic curve domain
parameter.
We need to consider about cofactor and key handling.
We need to consider ephemeral key generation in libgcrypt
(currently, GnuPG does its own ephemeral key generation).
We need to introduce selective copy routine to avoid branches based on
scalar (which is secret) in _gcry_mpi_ec_add_points.
We need to implement Jivsov's compact representation.
We need to implement _gcry_mpi_ec_curve_point for Montgomery curve.
Also, dup_point_montgomery and add_points_montgomery.
diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c
index 0f622f7..e7dbc17 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",
+ "0x01DB41", /* (A-2)/4 */
+ "0x01",
+ "0x1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED",
+ "0x0000000000000000000000000000000000000000000000000000000000000009",
+ "0x20AE19A1B8A086B4E01EDD2C7748D14C923D4D7E6D7C61B229E9C5A27ECED3D9"
+ },
#if 0 /* No real specs yet found. */
{
/* x^2 + y^2 = 1 + 3617x^2y^2 mod 2^414 - 17 */
@@ -507,9 +518,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-misc.c b/cipher/ecc-misc.c
index 3f284fe..595aa0c 100644
--- a/cipher/ecc-misc.c
+++ b/cipher/ecc-misc.c
@@ -202,8 +202,13 @@ _gcry_ecc_os2ec (mpi_point_t result, gcry_mpi_t value)
}
if (*buf != 4)
{
+ /* x-coordinate only */
+ mpi_set (result->x, value);
+ mpi_clear (result->y);
+ mpi_set_ui (result->z, 1);
+
xfree (buf_memory);
- return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression. */
+ return 0;
}
if ( ((n-1)%2) )
{
diff --git a/cipher/ecc.c b/cipher/ecc.c
index e0be2d4..679aa39 100644
--- a/cipher/ecc.c
+++ b/cipher/ecc.c
@@ -117,7 +117,25 @@ nist_generate_key (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
point_init (&Q);
/* Generate a secret. */
- if (ctx->dialect == ECC_DIALECT_ED25519)
+ /*
+ * FIXME. It should be something like this:
+ *
+ * When the co-factor of the curve is not 1, we guarantee that
+ * scalar value k is multiple of its co-factor to avoid sub-group
+ * attack. Also, we make sure that the most significant bit of k
+ * is 1.
+ *
+ * It works for now as we only have two curves which have co-factor!=1;
+ * Ed25519 and Curve25519.
+ * Note that we need some a way to get number of bits of the curve to
+ * set MSB of k. Currently, E.nbits is not precise for this purpuse.
+ * We also need a way to get co-factor of a curve.
+ *
+ * Currently, we distinguish the two curves by ECC_DIALECT_ED25519
+ * and MPI_EC_MONTGOMERY, which works, but is not that correct.
+ */
+ if (ctx->dialect == ECC_DIALECT_ED25519
+ || E->model == MPI_EC_MONTGOMERY)
{
char *rndbuf;
@@ -156,7 +174,7 @@ nist_generate_key (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
* possibilities without any loss of security. Note that we don't
* do that for Ed25519 so that we do not violate the special
* construction of the secret key. */
- if (E->dialect == ECC_DIALECT_ED25519)
+ if (E->dialect == ECC_DIALECT_ED25519 || E->model == MPI_EC_MONTGOMERY)
point_set (&sk->Q, &Q);
else
{
@@ -227,12 +245,8 @@ static void
test_keys (ECC_secret_key *sk, unsigned int nbits)
{
ECC_public_key pk;
- gcry_mpi_t test = mpi_new (nbits);
+ gcry_mpi_t test;
mpi_point_struct R_;
- gcry_mpi_t c = mpi_new (nbits);
- gcry_mpi_t out = mpi_new (nbits);
- gcry_mpi_t r = mpi_new (nbits);
- gcry_mpi_t s = mpi_new (nbits);
if (DBG_CIPHER)
log_debug ("Testing key.\n");
@@ -243,27 +257,84 @@ test_keys (ECC_secret_key *sk, unsigned int nbits)
point_init (&pk.Q);
point_set (&pk.Q, &sk->Q);
- _gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
+ if (sk->E.model == MPI_EC_MONTGOMERY)
+ /* It's ECDH only. */
+ /* FIXME: see the FIXME comment of nist_generate_key.
+ * Here, we generate ephemeral key, same handling is needed for secret.
+ */
+ {
+ char *rndbuf;
+ gcry_mpi_t x0, x1;
+ mpi_ec_t ec;
+
+ 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);
+
+ 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);
- if (_gcry_ecc_ecdsa_sign (test, sk, r, s, 0, 0) )
- log_fatal ("ECDSA operation: sign failed\n");
+ /* R_ = kQ <=> R_ = kdG */
+ _gcry_mpi_ec_mul_point (&R_, test, &pk.Q, ec);
+ if (_gcry_mpi_ec_get_affine (x0, NULL, &R_, ec))
+ log_fatal ("ecdh: Failed to get affine coordinates for kQ\n");
- if (_gcry_ecc_ecdsa_verify (test, &pk, r, s))
- {
- log_fatal ("ECDSA operation: sign, verify failed\n");
+ /* R_ = kG */
+ _gcry_mpi_ec_mul_point (&R_, test, &pk.E.G, ec);
+ /* R_ = dkG */
+ _gcry_mpi_ec_mul_point (&R_, sk->d, &R_, ec);
+
+ if (_gcry_mpi_ec_get_affine (x1, NULL, &R_, ec))
+ log_fatal ("ecdh: Failed to get affine coordinates for dkG\n");
+
+ if (mpi_cmp (x0, x1))
+ {
+ log_printmpi ("x0 ", x0);
+ log_printmpi ("x1 ", x1);
+ log_fatal ("ECDH test failed.\n");
+ }
+
+ mpi_free (x0);
+ mpi_free (x1);
+ _gcry_mpi_ec_free (ec);
}
+ else
+ {
+ gcry_mpi_t c = mpi_new (nbits);
+ gcry_mpi_t out = mpi_new (nbits);
+ gcry_mpi_t r = mpi_new (nbits);
+ gcry_mpi_t s = mpi_new (nbits);
- if (DBG_CIPHER)
- log_debug ("ECDSA operation: sign, verify ok.\n");
+ test = mpi_new (nbits);
+ _gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
+
+ if (_gcry_ecc_ecdsa_sign (test, sk, r, s, 0, 0) )
+ log_fatal ("ECDSA operation: sign failed\n");
+
+ if (_gcry_ecc_ecdsa_verify (test, &pk, r, s))
+ {
+ log_fatal ("ECDSA operation: sign, verify failed\n");
+ }
+
+ if (DBG_CIPHER)
+ log_debug ("ECDSA operation: sign, verify ok.\n");
+
+ mpi_free (s);
+ mpi_free (r);
+ mpi_free (out);
+ mpi_free (c);
+ }
point_free (&pk.Q);
_gcry_ecc_curve_free (&pk.E);
point_free (&R_);
- mpi_free (s);
- mpi_free (r);
- mpi_free (out);
- mpi_free (c);
mpi_free (test);
}
diff --git a/mpi/ec.c b/mpi/ec.c
index 4f35de0..4fd9e53 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -600,10 +600,13 @@ _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)
+ mpi_set (y, point->y);
}
- return -1;
+ return 0;
case MPI_EC_EDWARDS:
{
@@ -1073,6 +1076,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 +1176,86 @@ _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);
+ 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--)
+ {
+ 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);
+ }
+
+ z1 = mpi_new (0);
+ mpi_clear (result->y);
+ mpi_set_ui (result->z, 1);
+ if ((nbits & 1))
+ {
+ ec_invm (z1, p1_.z, ctx);
+ ec_mulm (result->x, p1_.x, z1, ctx);
+ mpi_clear (result->y);
+ }
+ else
+ {
+ ec_invm (z1, p1.z, ctx);
+ ec_mulm (result->x, p1.x, z1, ctx);
+ }
+
+ 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);
diff --git a/tests/curves.c b/tests/curves.c
index 0581452..977001e 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[] =
diff --git a/tests/keygen.c b/tests/keygen.c
index 4aff9c9..c53246c 100644
--- a/tests/keygen.c
+++ b/tests/keygen.c
@@ -365,7 +365,7 @@ static void
check_ecc_keys (void)
{
const char *curves[] = { "NIST P-521", "NIST P-384", "NIST P-256",
- "Ed25519", NULL };
+ "Ed25519", "Curve25519", NULL };
int testno;
gcry_sexp_t keyparm, key;
int rc;
--
More information about the Gcrypt-devel
mailing list