[PATCH] Curve25519 patch revised
NIIBE Yutaka
gniibe at fsij.org
Thu Jun 19 07:58:35 CEST 2014
Hello,
Here is a revised patch for Curve25519 support. With
mpi_swap_conditional, it's getting to constant-time.
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",
+ "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..6a60785 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,82 @@ 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_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..f2dd0f0 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,79 @@ _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;
+
+ 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;
+
+ sw = mpi_test_bit (scalar, j);
+ q1 = &p1;
+ q2 = &p2;
+ mpi_swap_conditional (q1->x, q2->x, sw);
+ mpi_swap_conditional (q1->y, q2->y, sw);
+ mpi_swap_conditional (q1->z, q2->z, sw);
+ dup_and_add_montgomery (&p1_, &p2_, q1, q2, point->x, ctx);
+ mpi_swap_conditional (p1_.x, p2_.x, sw);
+ mpi_swap_conditional (p1_.y, p2_.y, sw);
+ mpi_swap_conditional (p1_.z, p2_.z, sw);
+
+ if (--j < 0)
+ break;
+
+ sw = mpi_test_bit (scalar, j);
+ q1 = &p1_;
+ q2 = &p2_;
+ mpi_swap_conditional (q1->x, q2->x, sw);
+ mpi_swap_conditional (q1->y, q2->y, sw);
+ mpi_swap_conditional (q1->z, q2->z, sw);
+ dup_and_add_montgomery (&p1, &p2, q1, q2, point->x, ctx);
+ mpi_swap_conditional (p1.x, p2.x, sw);
+ mpi_swap_conditional (p1.y, p2.y, sw);
+ mpi_swap_conditional (p1.z, p2.z, sw);
+ }
+
+ z1 = mpi_new (0);
+ mpi_clear (result->y);
+ sw = (nbits & 1);
+ mpi_swap_conditional (p1.x, p1_.x, sw);
+ mpi_swap_conditional (p1.y, p1_.y, sw);
+ mpi_swap_conditional (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);
@@ -1266,8 +1371,12 @@ _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
}
break;
case MPI_EC_MONTGOMERY:
+#if 0
log_fatal ("%s: %s not yet supported\n",
"_gcry_mpi_ec_curve_point", "Montgomery");
+#else
+ res = 1;
+#endif
break;
case MPI_EC_EDWARDS:
{
diff --git a/tests/curves.c b/tests/curves.c
index 0581452..ae699d4 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;
@@ -91,6 +103,42 @@ die (const char *format, ...)
}
+static gcry_mpi_t
+hex2mpi (const char *string)
+{
+ gpg_error_t err;
+ gcry_mpi_t val;
+
+ err = gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
+ if (err)
+ die ("hex2mpi '%s' failed: %s\n", string, gpg_strerror (err));
+ return val;
+}
+
+
+/* Print an MPI S-expression. */
+static void
+print_mpi (const char *name, gcry_mpi_t a)
+{
+ gcry_error_t err;
+ unsigned char *buf;
+ int writerr = 0;
+
+ err = gcry_mpi_aprint (GCRYMPI_FMT_HEX, &buf, NULL, a);
+ if (err)
+ die ("gcry_mpi_aprint failed: %s\n", gcry_strerror (err));
+
+ printf (" (%s #%s#)\n", name, buf);
+ if (ferror (stdout))
+ writerr++;
+ if (!writerr && fflush (stdout) == EOF)
+ writerr++;
+ if (writerr)
+ die ("writing output failed\n");
+ gcry_free (buf);
+}
+
+
static void
list_curves (void)
{
@@ -185,6 +233,85 @@ check_get_params (void)
}
+static void
+check_montgomery (void)
+{
+ gpg_error_t err;
+ gcry_sexp_t key;
+ const char *name;
+ unsigned int nbits;
+
+ gcry_ctx_t ctx;
+ gcry_mpi_point_t G, Q;
+ gcry_mpi_t d;
+ gcry_mpi_t x, y, z;
+
+ 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);
+
+ Q = gcry_mpi_point_new (0);
+
+ err = gcry_mpi_ec_new (&ctx, NULL, "Curve25519");
+ if (err)
+ fail ("can't create ec context: %s\n", gpg_strerror (err));
+
+#if 0
+ d = hex2mpi ("40000000000000000000000000000000"
+ "00000000000000000000000000000000");
+ G = gcry_mpi_ec_get_point ("g", ctx, 1);
+ if (!G)
+ fail ("can't get basepoint of the curve: %s\n", gpg_strerror (err));
+#else
+ d = hex2mpi ("7d74fb61db3100e11e4d4ae171daf820688f3bcfa631565272a998b8f4e8c290");
+ {
+ gcry_mpi_t gx;
+ gx = hex2mpi ("3dc16d73d4222d12eb54623c85f3fb5ebdab33c1bd5865780654f1b0ed696ddf");
+
+ G = gcry_mpi_point_new (0);
+ gcry_mpi_point_snatch_set (G, gx, NULL, NULL);
+ }
+#endif
+
+ gcry_mpi_ec_mul (Q, d, G, ctx);
+
+ x = gcry_mpi_new (0);
+ y = gcry_mpi_new (0);
+ z = gcry_mpi_new (0);
+
+ gcry_mpi_point_get (x, y, z, Q);
+
+ print_mpi ("Q.x", x);
+ print_mpi ("Q.y", y);
+ print_mpi ("Q.z", z);
+
+ if (gcry_mpi_ec_get_affine (x, NULL, Q, ctx))
+ fail ("failed to get affine coordinates\n");
+
+ print_mpi ("q.x", x);
+ /* 16B53A046DEEDD81ED6B0D470CE46DD9B5FAC6124F3D22358AA7CD2911FCFABC */
+
+ gcry_mpi_release (z);
+ gcry_mpi_release (y);
+ gcry_mpi_release (x);
+
+ gcry_mpi_point_release (Q);
+ gcry_mpi_release (d);
+ gcry_mpi_point_release (G);
+ gcry_ctx_release (ctx);
+}
+
int
main (int argc, char **argv)
{
@@ -205,6 +332,7 @@ main (int argc, char **argv)
list_curves ();
check_matching ();
check_get_params ();
+ check_montgomery ();
return error_count ? 1 : 0;
}
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