[EXPERIMENTAL-PATCH] Curve25519 encryption support (updated)
NIIBE Yutaka
gniibe at fsij.org
Wed Jul 8 02:34:24 CEST 2015
Hello,
Here is an update of the patch against current master branch.
This is an experimental patch for Curve25519 encryption support.
Key generation is done with SEXP:
(genkey(ecc(curve Curve25519)(flags eddsa comp)))
Here, I changed the meaning of '(flags eddsa)' a bit. Now, it means
that the key is in DJB format and under DJB processing:
Little endian
Private key: MSB is 0, (MS-1)B is 1, multiple of cofactor
ECDH: Assume a private key conforms this ----^
That is, '(flags eddsa)' also makes sense to Curve25519.
'(flags comp)' is also a bit different now. It means the key comes
with the prefix 0x40 like EdDSA in GnuPG. (Since the computation is
only done with x-coordinate with Curve25519, there would be no way
other than shorter format. So, it is not "compression", but
requesting a prefix.)
Those changes of flags would be confusing and needed to improve.
I tested with modified version of GnuPG 2.1 and Gnuk.
I don't think all possible combinations work. Following is not
implemented/tested, and I don't know about all semantics.
(genkey(ecc(curve Curve25519)))
(genkey(ecc(curve Curve25519)(flags comp)))
(genkey(ecc(curve Curve25519)(flags eddsa)))
Please note that this is highly experimental. The SEXP format is not
yet decided.
diff --git a/cipher/ecc-common.h b/cipher/ecc-common.h
index f0d97ea..6b3b063 100644
--- a/cipher/ecc-common.h
+++ b/cipher/ecc-common.h
@@ -132,6 +132,8 @@ gpg_err_code_t _gcry_ecc_eddsa_verify (gcry_mpi_t input,
ECC_public_key *pk,
gcry_mpi_t r, gcry_mpi_t s,
int hashalgo, gcry_mpi_t pkmpi);
+gpg_err_code_t _gcry_ecc_mont_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx,
+ mpi_point_t result);
/*-- ecc-gost.c --*/
gpg_err_code_t _gcry_ecc_gost_sign (gcry_mpi_t input, ECC_secret_key *skey,
diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c
index 9975bb4..5d855bd 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 */
@@ -129,6 +129,18 @@ static const ecc_domain_parms_t domain_parms[] =
"0x6666666666666666666666666666666666666666666666666666666666666658",
"0x08"
},
+ {
+ /* (y^2 = x^3 + 486662*x^2 + x) */
+ "Curve25519", 256, 0,
+ MPI_EC_MONTGOMERY, ECC_DIALECT_ED25519,
+ "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED",
+ "0x01DB41",
+ "0x01",
+ "0x1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED",
+ "0x0000000000000000000000000000000000000000000000000000000000000009",
+ "0x20AE19A1B8A086B4E01EDD2C7748D14C923D4D7E6D7C61B229E9C5A27ECED3D9",
+ "0x08"
+ },
#if 0 /* No real specs yet found. */
{
/* x^2 + y^2 = 1 + 3617x^2y^2 mod 2^414 - 17 */
diff --git a/cipher/ecc-eddsa.c b/cipher/ecc-eddsa.c
index 4323d8e..72481ba 100644
--- a/cipher/ecc-eddsa.c
+++ b/cipher/ecc-eddsa.c
@@ -400,6 +400,51 @@ _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
}
+gpg_err_code_t
+_gcry_ecc_mont_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result)
+{
+ unsigned char *rawmpi;
+ unsigned int rawmpilen;
+
+ if (mpi_is_opaque (pk))
+ {
+ const unsigned char *buf;
+
+ buf = mpi_get_opaque (pk, &rawmpilen);
+ if (!buf)
+ return GPG_ERR_INV_OBJ;
+ rawmpilen = (rawmpilen + 7)/8;
+
+ if (rawmpilen > 1 && (rawmpilen%2) && buf[0] == 0x40)
+ {
+ rawmpilen--;
+ buf++;
+ }
+
+ rawmpi = xtrymalloc (rawmpilen? rawmpilen:1);
+ if (!rawmpi)
+ return gpg_err_code_from_syserror ();
+ memcpy (rawmpi, buf, rawmpilen);
+ reverse_buffer (rawmpi, rawmpilen);
+ }
+ else
+ {
+ /* Note: Without using an opaque MPI it is not reliable possible
+ to find out whether the public key has been given in
+ uncompressed format. Thus we expect native EdDSA format. */
+ rawmpi = _gcry_mpi_get_buffer (pk, ctx->nbits/8, &rawmpilen, NULL);
+ if (!rawmpi)
+ return gpg_err_code_from_syserror ();
+ }
+
+ _gcry_mpi_set_buffer (result->x, rawmpi, rawmpilen, 0);
+ xfree (rawmpi);
+ mpi_set_ui (result->z, 1);
+
+ return 0;
+}
+
+
/* Compute the A value as used by EdDSA. The caller needs to provide
the context EC and the actual secret D as an MPI. The function
returns a newly allocated 64 byte buffer at r_digest; the first 32
diff --git a/cipher/ecc.c b/cipher/ecc.c
index f5bc50a..de4fdbd 100644
--- a/cipher/ecc.c
+++ b/cipher/ecc.c
@@ -174,7 +174,10 @@ nist_generate_key (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
point_init (&sk->Q);
x = mpi_new (pbits);
- y = mpi_new (pbits);
+ if (r_y == NULL)
+ y = NULL;
+ else
+ y = mpi_new (pbits);
if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx))
log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "Q");
@@ -187,7 +190,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 || r_y == NULL)
point_set (&sk->Q, &Q);
else
{
@@ -231,7 +234,8 @@ nist_generate_key (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
}
*r_x = x;
- *r_y = y;
+ if (r_y)
+ *r_y = y;
point_free (&Q);
/* Now we can test our keys (this should never fail!). */
@@ -307,7 +311,7 @@ test_ecdh_only_keys (ECC_secret_key *sk, unsigned int nbits)
mpi_ec_t ec;
if (DBG_CIPHER)
- log_debug ("Testing key.\n");
+ log_debug ("Testing ECDH only key.\n");
point_init (&R_);
@@ -571,7 +575,9 @@ ecc_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
ctx = _gcry_mpi_ec_p_internal_new (E.model, E.dialect, 0, E.p, E.a, E.b);
- if ((flags & PUBKEY_FLAG_EDDSA))
+ if (E.model == MPI_EC_MONTGOMERY)
+ rc = nist_generate_key (&sk, &E, ctx, flags, nbits, &Qx, NULL);
+ else if ((flags & PUBKEY_FLAG_EDDSA))
rc = _gcry_ecc_eddsa_genkey (&sk, &E, ctx, flags);
else
rc = nist_generate_key (&sk, &E, ctx, flags, nbits, &Qx, &Qy);
@@ -581,18 +587,31 @@ ecc_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
/* Copy data to the result. */
Gx = mpi_new (0);
Gy = mpi_new (0);
- if (_gcry_mpi_ec_get_affine (Gx, Gy, &sk.E.G, ctx))
- log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "G");
- base = _gcry_ecc_ec2os (Gx, Gy, sk.E.p);
if (sk.E.dialect == ECC_DIALECT_ED25519 && !(flags & PUBKEY_FLAG_NOCOMP))
{
unsigned char *encpk;
unsigned int encpklen;
- /* (Gx and Gy are used as scratch variables) */
- rc = _gcry_ecc_eddsa_encodepoint (&sk.Q, ctx, Gx, Gy,
- !!(flags & PUBKEY_FLAG_COMP),
- &encpk, &encpklen);
+ if (E.model != MPI_EC_MONTGOMERY)
+ /* (Gx and Gy are used as scratch variables) */
+ rc = _gcry_ecc_eddsa_encodepoint (&sk.Q, ctx, Gx, Gy,
+ !!(flags & PUBKEY_FLAG_COMP),
+ &encpk, &encpklen);
+ else
+ {
+ int off = !!(flags & PUBKEY_FLAG_COMP);
+
+ encpk = _gcry_mpi_get_buffer_extra (Qx, ctx->nbits/8, off?-1:0,
+ &encpklen, NULL);
+ if (encpk == NULL)
+ rc = gpg_err_code_from_syserror ();
+ else
+ {
+ if (off)
+ encpk[0] = 0x40;
+ encpklen += off;
+ }
+ }
if (rc)
goto leave;
public = mpi_new (0);
@@ -600,6 +619,9 @@ ecc_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
}
else
{
+ if (_gcry_mpi_ec_get_affine (Gx, Gy, &sk.E.G, ctx))
+ log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "G");
+ base = _gcry_ecc_ec2os (Gx, Gy, sk.E.p);
if (!Qx)
{
/* This is the case for a key from _gcry_ecc_eddsa_generate
@@ -1213,6 +1235,18 @@ ecc_encrypt_raw (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
gcry_mpi_t data = NULL;
ECC_public_key pk;
mpi_ec_t ec = NULL;
+ int flags;
+
+ /* Look for flags. */
+ l1 = sexp_find_token (keyparms, "flags", 0);
+ if (l1)
+ {
+ rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL);
+ if (rc)
+ goto leave;
+ }
+ sexp_release (l1);
+ l1 = NULL;
memset (&pk, 0, sizeof pk);
_gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT,
@@ -1236,7 +1270,9 @@ ecc_encrypt_raw (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
/*
* Extract the key.
*/
- rc = sexp_extract_param (keyparms, NULL, "-p?a?b?g?n?h?+q",
+ rc = sexp_extract_param (keyparms, NULL,
+ (flags & PUBKEY_FLAG_EDDSA)?
+ "-p?a?b?g?n?h?/q" : "-p?a?b?g?n?h?+q",
&pk.E.p, &pk.E.a, &pk.E.b, &mpi_g, &pk.E.n, &pk.E.h,
&mpi_q, NULL);
if (rc)
@@ -1288,26 +1324,34 @@ ecc_encrypt_raw (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
goto leave;
}
+ /* Compute the encrypted value. */
+ ec = _gcry_mpi_ec_p_internal_new (pk.E.model, pk.E.dialect, 0,
+ pk.E.p, pk.E.a, pk.E.b);
+
/* Convert the public key. */
if (mpi_q)
{
point_init (&pk.Q);
- rc = _gcry_ecc_os2ec (&pk.Q, mpi_q);
+ if (ec->model == MPI_EC_MONTGOMERY)
+ rc = _gcry_ecc_mont_decodepoint (mpi_q, ec, &pk.Q);
+ else
+ rc = _gcry_ecc_os2ec (&pk.Q, mpi_q);
if (rc)
goto leave;
}
- /* Compute the encrypted value. */
- ec = _gcry_mpi_ec_p_internal_new (pk.E.model, pk.E.dialect, 0,
- pk.E.p, pk.E.a, pk.E.b);
-
/* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so */
{
mpi_point_struct R; /* Result that we return. */
gcry_mpi_t x, y;
+ unsigned char *rawmpi;
+ unsigned int rawmpilen;
x = mpi_new (0);
- y = mpi_new (0);
+ if (ec->model == MPI_EC_MONTGOMERY)
+ y = NULL;
+ else
+ y = mpi_new (0);
point_init (&R);
@@ -1316,14 +1360,38 @@ ecc_encrypt_raw (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
log_fatal ("ecdh: Failed to get affine coordinates for kdG\n");
- mpi_s = _gcry_ecc_ec2os (x, y, pk.E.p);
+ if (y)
+ mpi_s = _gcry_ecc_ec2os (x, y, pk.E.p);
+ else
+ {
+ rawmpi = _gcry_mpi_get_buffer (x, ec->nbits/8, &rawmpilen, NULL);
+ if (!rawmpi)
+ rc = gpg_err_code_from_syserror ();
+ else
+ {
+ mpi_s = mpi_new (0);
+ mpi_set_opaque (mpi_s, rawmpi, rawmpilen*8);
+ }
+ }
/* R = kG */
_gcry_mpi_ec_mul_point (&R, data, &pk.E.G, ec);
if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
log_fatal ("ecdh: Failed to get affine coordinates for kG\n");
- mpi_e = _gcry_ecc_ec2os (x, y, pk.E.p);
+ if (y)
+ mpi_e = _gcry_ecc_ec2os (x, y, pk.E.p);
+ else
+ {
+ rawmpi = _gcry_mpi_get_buffer (x, ec->nbits/8, &rawmpilen, NULL);
+ if (!rawmpi)
+ rc = gpg_err_code_from_syserror ();
+ else
+ {
+ mpi_e = mpi_new (0);
+ mpi_set_opaque (mpi_e, rawmpi, rawmpilen*8);
+ }
+ }
mpi_free (x);
mpi_free (y);
@@ -1331,7 +1399,8 @@ ecc_encrypt_raw (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
point_free (&R);
}
- rc = sexp_build (r_ciph, NULL, "(enc-val(ecdh(s%m)(e%m)))", mpi_s, mpi_e);
+ if (!rc)
+ rc = sexp_build (r_ciph, NULL, "(enc-val(ecdh(s%m)(e%m)))", mpi_s, mpi_e);
leave:
_gcry_mpi_release (pk.E.p);
@@ -1347,6 +1416,7 @@ ecc_encrypt_raw (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
_gcry_mpi_release (mpi_s);
_gcry_mpi_release (mpi_e);
xfree (curvename);
+ sexp_release (l1);
_gcry_mpi_ec_free (ec);
_gcry_pk_util_free_encoding_ctx (&ctx);
if (DBG_CIPHER)
@@ -1376,6 +1446,7 @@ ecc_decrypt_raw (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
mpi_point_struct kG;
mpi_point_struct R;
gcry_mpi_t r = NULL;
+ int flags = 0;
memset (&sk, 0, sizeof sk);
point_init (&kG);
@@ -1384,6 +1455,17 @@ ecc_decrypt_raw (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
_gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT,
ecc_get_nbits (keyparms));
+ /* Look for flags. */
+ l1 = sexp_find_token (keyparms, "flags", 0);
+ if (l1)
+ {
+ rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL);
+ if (rc)
+ goto leave;
+ }
+ sexp_release (l1);
+ l1 = NULL;
+
/*
* Extract the data.
*/
@@ -1457,15 +1539,19 @@ ecc_decrypt_raw (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
}
+ ec = _gcry_mpi_ec_p_internal_new (sk.E.model, sk.E.dialect, 0,
+ sk.E.p, sk.E.a, sk.E.b);
+
/*
* Compute the plaintext.
*/
- rc = _gcry_ecc_os2ec (&kG, data_e);
+ if (ec->model == MPI_EC_MONTGOMERY)
+ rc = _gcry_ecc_mont_decodepoint (data_e, ec, &kG);
+ else
+ rc = _gcry_ecc_os2ec (&kG, data_e);
if (rc)
goto leave;
- ec = _gcry_mpi_ec_p_internal_new (sk.E.model, sk.E.dialect, 0,
- sk.E.p, sk.E.a, sk.E.b);
/* R = dkG */
_gcry_mpi_ec_mul_point (&R, sk.d, &kG, ec);
@@ -1475,12 +1561,30 @@ ecc_decrypt_raw (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
gcry_mpi_t x, y;
x = mpi_new (0);
- y = mpi_new (0);
+ if (ec->model == MPI_EC_MONTGOMERY)
+ y = NULL;
+ else
+ y = mpi_new (0);
if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
log_fatal ("ecdh: Failed to get affine coordinates\n");
- r = _gcry_ecc_ec2os (x, y, sk.E.p);
+ if (y)
+ r = _gcry_ecc_ec2os (x, y, sk.E.p);
+ else
+ {
+ unsigned char *rawmpi;
+ unsigned int rawmpilen;
+
+ rawmpi = _gcry_mpi_get_buffer (x, ec->nbits/8, &rawmpilen, NULL);
+ if (!rawmpi)
+ rc = gpg_err_code_from_syserror ();
+ else
+ {
+ r = mpi_new (0);
+ mpi_set_opaque (r, rawmpi, rawmpilen*8);
+ }
+ }
if (!r)
rc = gpg_err_code_from_syserror ();
else
--
More information about the Gcrypt-devel
mailing list