From 4556f9b19c024f16bdf542da7173395c0741b91d Mon Sep 17 00:00:00 2001 From: Werner Koch Date: Thu, 24 Jul 2014 12:30:32 +0200 Subject: ecc: Support the non-standard 0x40 compression flag for EdDSA. * cipher/ecc.c (ecc_generate): Check the "comp" flag for EdDSA. * cipher/ecc-eddsa.c (eddsa_encode_x_y): Add arg WITH_PREFIX. (_gcry_ecc_eddsa_encodepoint): Ditto. (_gcry_ecc_eddsa_ensure_compact): Handle the 0x40 compression prefix. (_gcry_ecc_eddsa_decodepoint): Ditto. * tests/keygrip.c: Check an compresssed with prefix Ed25519 key. * tests/t-ed25519.inp: Ditto. --- cipher/ecc-common.h | 1 + cipher/ecc-curves.c | 2 +- cipher/ecc-eddsa.c | 152 +++++++++++++++++++++++++++++++--------------------- cipher/ecc.c | 11 ++-- doc/gcrypt.texi | 12 +++-- tests/keygrip.c | 11 ++++ tests/t-ed25519.c | 2 +- tests/t-ed25519.inp | 8 +++ 8 files changed, 127 insertions(+), 72 deletions(-) diff --git a/cipher/ecc-common.h b/cipher/ecc-common.h index c407c744..f066b4b7 100644 --- a/cipher/ecc-common.h +++ b/cipher/ecc-common.h @@ -107,6 +107,7 @@ gpg_err_code_t _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec); gpg_err_code_t _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ctx, gcry_mpi_t x, gcry_mpi_t y, + int with_prefix, unsigned char **r_buffer, unsigned int *r_buflen); gpg_err_code_t _gcry_ecc_eddsa_ensure_compact (gcry_mpi_t value, diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c index 0f622f73..cd85361d 100644 --- a/cipher/ecc-curves.c +++ b/cipher/ecc-curves.c @@ -1146,7 +1146,7 @@ _gcry_ecc_get_mpi (const char *name, mpi_ec_t ec, int copy) unsigned char *encpk; unsigned int encpklen; - if (!_gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL, + if (!_gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL, 0, &encpk, &encpklen)) return mpi_set_opaque (NULL, encpk, encpklen*8); } diff --git a/cipher/ecc-eddsa.c b/cipher/ecc-eddsa.c index d08a84fc..65024a30 100644 --- a/cipher/ecc-eddsa.c +++ b/cipher/ecc-eddsa.c @@ -1,5 +1,5 @@ /* ecc-eddsa.c - Elliptic Curve EdDSA signatures - * Copyright (C) 2013 g10 Code GmbH + * Copyright (C) 2013, 2014 g10 Code GmbH * * This file is part of Libgcrypt. * @@ -83,35 +83,42 @@ eddsa_encodempi (gcry_mpi_t mpi, unsigned int minlen, /* Encode (X,Y) using the EdDSA scheme. MINLEN is the required length - in bytes for the result. On success 0 is returned and a malloced - buffer with the encoded point is stored at R_BUFFER; the length of - this buffer is stored at R_BUFLEN. */ + in bytes for the result. If WITH_PREFIX is set the returned buffer + is prefixed with a 0x40 byte. On success 0 is returned and a + malloced buffer with the encoded point is stored at R_BUFFER; the + length of this buffer is stored at R_BUFLEN. */ static gpg_err_code_t eddsa_encode_x_y (gcry_mpi_t x, gcry_mpi_t y, unsigned int minlen, + int with_prefix, unsigned char **r_buffer, unsigned int *r_buflen) { unsigned char *rawmpi; unsigned int rawmpilen; + int off = with_prefix? 1:0; - rawmpi = _gcry_mpi_get_buffer (y, minlen, &rawmpilen, NULL); + rawmpi = _gcry_mpi_get_buffer_extra (y, minlen, off?-1:0, &rawmpilen, NULL); if (!rawmpi) return gpg_err_code_from_syserror (); if (mpi_test_bit (x, 0) && rawmpilen) - rawmpi[rawmpilen - 1] |= 0x80; /* Set sign bit. */ + rawmpi[off + rawmpilen - 1] |= 0x80; /* Set sign bit. */ + if (off) + rawmpi[0] = 0x40; *r_buffer = rawmpi; - *r_buflen = rawmpilen; + *r_buflen = rawmpilen + off; return 0; } /* Encode POINT using the EdDSA scheme. X and Y are either scratch variables supplied by the caller or NULL. CTX is the usual - context. On success 0 is returned and a malloced buffer with the - encoded point is stored at R_BUFFER; the length of this buffer is - stored at R_BUFLEN. */ + context. If WITH_PREFIX is set the returned buffer is prefixed + with a 0x40 byte. On success 0 is returned and a malloced buffer + with the encoded point is stored at R_BUFFER; the length of this + buffer is stored at R_BUFLEN. */ gpg_err_code_t _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec, gcry_mpi_t x_in, gcry_mpi_t y_in, + int with_prefix, unsigned char **r_buffer, unsigned int *r_buflen) { gpg_err_code_t rc; @@ -126,7 +133,7 @@ _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec, rc = GPG_ERR_INTERNAL; } else - rc = eddsa_encode_x_y (x, y, ec->nbits/8, r_buffer, r_buflen); + rc = eddsa_encode_x_y (x, y, ec->nbits/8, with_prefix, r_buffer, r_buflen); if (!x_in) mpi_free (x); @@ -155,29 +162,40 @@ _gcry_ecc_eddsa_ensure_compact (gcry_mpi_t value, unsigned int nbits) return GPG_ERR_INV_OBJ; rawmpilen = (rawmpilen + 7)/8; - /* Check whether the public key has been given in standard - uncompressed format. In this case extract y and compress. */ - if (rawmpilen > 1 && buf[0] == 0x04 && (rawmpilen%2)) + if (rawmpilen > 1 && (rawmpilen%2)) { - rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_STD, - buf+1, (rawmpilen-1)/2, NULL); - if (rc) - return rc; - rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_STD, - buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2, NULL); - if (rc) + if (buf[0] == 0x04) { - mpi_free (x); - return rc; - } + /* Buffer is in SEC1 uncompressed format. Extract y and + compress. */ + rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_STD, + buf+1, (rawmpilen-1)/2, NULL); + if (rc) + return rc; + rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_STD, + buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2, NULL); + if (rc) + { + mpi_free (x); + return rc; + } - rc = eddsa_encode_x_y (x, y, nbits/8, &enc, &enclen); - mpi_free (x); - mpi_free (y); - if (rc) - return rc; + rc = eddsa_encode_x_y (x, y, nbits/8, 0, &enc, &enclen); + mpi_free (x); + mpi_free (y); + if (rc) + return rc; - mpi_set_opaque (value, enc, 8*enclen); + mpi_set_opaque (value, enc, 8*enclen); + } + else if (buf[0] == 0x40) + { + /* Buffer is compressed but with our SEC1 alike compression + indicator. Remove that byte. FIXME: We should write and + use a function to manipulate an opaque MPI in place. */ + if (!_gcry_mpi_set_opaque_copy (value, buf + 1, (rawmpilen - 1)*8)) + return gpg_err_code_from_syserror (); + } } return 0; @@ -267,7 +285,7 @@ _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec) the usual curve context. If R_ENCPK is not NULL, the encoded PK is stored at that address; this is a new copy to be released by the caller. In contrast to the supplied PK, this is not an MPI and - thus guarnateed to be properly padded. R_ENCPKLEN receives the + thus guaranteed to be properly padded. R_ENCPKLEN receives the length of that encoded key. */ gpg_err_code_t _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result, @@ -287,40 +305,54 @@ _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result, return GPG_ERR_INV_OBJ; rawmpilen = (rawmpilen + 7)/8; - /* First check whether the public key has been given in standard - uncompressed format. No need to recover x in this case. - Detection is easy: The size of the buffer will be odd and the - first byte be 0x04. */ - if (rawmpilen > 1 && buf[0] == 0x04 && (rawmpilen%2)) + /* Handle compression prefixes. The size of the buffer will be + odd in this case. */ + if (rawmpilen > 1 && (rawmpilen%2)) { - gcry_mpi_t x, y; - - rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_STD, - buf+1, (rawmpilen-1)/2, NULL); - if (rc) - return rc; - rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_STD, - buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2, NULL); - if (rc) + /* First check whether the public key has been given in + standard uncompressed format (SEC1). No need to recover + x in this case. */ + if (buf[0] == 0x04) { - mpi_free (x); - return rc; - } + gcry_mpi_t x, y; - if (r_encpk) - { - rc = eddsa_encode_x_y (x, y, ctx->nbits/8, r_encpk, r_encpklen); + rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_STD, + buf+1, (rawmpilen-1)/2, NULL); + if (rc) + return rc; + rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_STD, + buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2,NULL); if (rc) { mpi_free (x); - mpi_free (y); return rc; } + + if (r_encpk) + { + rc = eddsa_encode_x_y (x, y, ctx->nbits/8, 0, + r_encpk, r_encpklen); + if (rc) + { + mpi_free (x); + mpi_free (y); + return rc; + } + } + mpi_snatch (result->x, x); + mpi_snatch (result->y, y); + mpi_set_ui (result->z, 1); + return 0; + } + + /* Check whether the public key has been prefixed with a 0x40 + byte to explicitly indicate compressed format using a SEC1 + alike prefix byte. This is a Libgcrypt extension. */ + if (buf[0] == 0x40) + { + rawmpilen--; + buf++; } - mpi_snatch (result->x, x); - mpi_snatch (result->y, y); - mpi_set_ui (result->z, 1); - return 0; } /* EdDSA compressed point. */ @@ -334,7 +366,7 @@ _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result, { /* 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 EdDSA format here. */ + 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 (); @@ -582,7 +614,7 @@ _gcry_ecc_eddsa_sign (gcry_mpi_t input, ECC_secret_key *skey, else { _gcry_mpi_ec_mul_point (&Q, a, &skey->E.G, ctx); - rc = _gcry_ecc_eddsa_encodepoint (&Q, ctx, x, y, &encpk, &encpklen); + rc = _gcry_ecc_eddsa_encodepoint (&Q, ctx, x, y, 0, &encpk, &encpklen); if (rc) goto leave; if (DBG_CIPHER) @@ -612,7 +644,7 @@ _gcry_ecc_eddsa_sign (gcry_mpi_t input, ECC_secret_key *skey, log_printpnt (" r", &I, ctx); /* Convert R into affine coordinates and apply encoding. */ - rc = _gcry_ecc_eddsa_encodepoint (&I, ctx, x, y, &rawmpi, &rawmpilen); + rc = _gcry_ecc_eddsa_encodepoint (&I, ctx, x, y, 0, &rawmpi, &rawmpilen); if (rc) goto leave; if (DBG_CIPHER) @@ -784,7 +816,7 @@ _gcry_ecc_eddsa_verify (gcry_mpi_t input, ECC_public_key *pkey, _gcry_mpi_ec_mul_point (&Ib, h, &Q, ctx); _gcry_mpi_neg (Ib.x, Ib.x); _gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ctx); - rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, &tbuf, &tlen); + rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, 0, &tbuf, &tlen); if (rc) goto leave; if (tlen != rlen || memcmp (tbuf, rbuf, tlen)) diff --git a/cipher/ecc.c b/cipher/ecc.c index e0be2d4f..a27d2c60 100644 --- a/cipher/ecc.c +++ b/cipher/ecc.c @@ -35,15 +35,12 @@ verification algorithms. The arithmetic functions have entirely been rewritten and moved to mpi/ec.c. - ECDH encrypt and decrypt code written by Andrey Jivsov, + ECDH encrypt and decrypt code written by Andrey Jivsov. */ /* TODO: - - If we support point compression we need to uncompress before - computing the keygrip - - In mpi/ec.c we use mpi_powm for x^2 mod p: Either implement a special case in mpi_powm or check whether mpi_mulm is faster. @@ -487,7 +484,9 @@ ecc_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey) unsigned char *encpk; unsigned int encpklen; - rc = _gcry_ecc_eddsa_encodepoint (&sk.Q, ctx, x, y, &encpk, &encpklen); + rc = _gcry_ecc_eddsa_encodepoint (&sk.Q, ctx, x, y, + !!(flags & PUBKEY_FLAG_COMP), + &encpk, &encpklen); if (rc) return rc; public = mpi_new (0); @@ -1653,7 +1652,7 @@ _gcry_pk_ecc_get_sexp (gcry_sexp_t *r_sexp, int mode, mpi_ec_t ec) unsigned char *encpk; unsigned int encpklen; - rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL, + rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL, 0, &encpk, &encpklen); if (rc) goto leave; diff --git a/doc/gcrypt.texi b/doc/gcrypt.texi index d59c0958..23efc526 100644 --- a/doc/gcrypt.texi +++ b/doc/gcrypt.texi @@ -2162,7 +2162,9 @@ The private key @math{d} All point values are encoded in standard format; Libgcrypt does in general only support uncompressed points, thus the first byte needs to be @code{0x04}. However ``EdDSA'' describes its own compression -scheme which is used by default. +scheme which is used by default; the non-standard first byte +@code{0x40} may optionally be used to explicit flag the use of the +algorithm’s native compression method. The public key is similar with "private-key" replaced by "public-key" and no @var{d-mpi}. @@ -2232,9 +2234,11 @@ are known: If supported by the algorithm and curve the @code{comp} flag requests that points are returned in compact (compressed) representation. The @code{nocomp} flag requests that points are returned with full -coordinates. The default depends on the the algorithm and curve. -The compact representation requires a small overhead before a point -can be used but halves the size of a to be conveyed public key. +coordinates. The default depends on the the algorithm and curve. The +compact representation requires a small overhead before a point can be +used but halves the size of a to be conveyed public key. If +@code{comp} is used with the ``EdDSA'' algorithm the key generation +prefix the public key with a @code{0x40} byte. @item pkcs1 @cindex PKCS1 diff --git a/tests/keygrip.c b/tests/keygrip.c index 330935db..72960ea3 100644 --- a/tests/keygrip.c +++ b/tests/keygrip.c @@ -175,6 +175,17 @@ static struct "\x9D\xB6\xC6\x4A\x38\x83\x0F\x49\x60\x70" "\x17\x89\x47\x55\x20\xBE\x8C\x82\x1F\x47" }, + { /* Ed25519+EdDSA (with compression prefix) */ + GCRY_PK_ECC, + "(public-key" + " (ecc" + " (curve Ed25519)(flags eddsa)" + " (q #40" + " 773E72848C1FD5F9652B29E2E7AF79571A04990E96F2016BF4E0EC1890C2B7DB#)" + " ))", + "\x9D\xB6\xC6\x4A\x38\x83\x0F\x49\x60\x70" + "\x17\x89\x47\x55\x20\xBE\x8C\x82\x1F\x47" + }, { /* Ed25519+EdDSA (same but uncompressed)*/ GCRY_PK_ECC, "(public-key" diff --git a/tests/t-ed25519.c b/tests/t-ed25519.c index 465a217b..b7f33076 100644 --- a/tests/t-ed25519.c +++ b/tests/t-ed25519.c @@ -32,7 +32,7 @@ #include "stopwatch.h" #define PGM "t-ed25519" -#define N_TESTS 1025 +#define N_TESTS 1026 #define my_isascii(c) (!((c) & 0x80)) #define digitp(p) (*(p) >= '0' && *(p) <= '9') diff --git a/tests/t-ed25519.inp b/tests/t-ed25519.inp index 61387c4b..e13566f8 100644 --- a/tests/t-ed25519.inp +++ b/tests/t-ed25519.inp @@ -6162,3 +6162,11 @@ SK: 9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60 PK: 0455d0e09a2b9d34292297e08d60d0f620c513d47253187c24b12786bd777645ce1a5107f7681a02af2523a6daf372e10e3a0764c9d3fe4bd5b70ab18201985ad7 MSG: SIG: e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e065224901555fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b + +# Now an additional test with the data from test 1 but using an +# compressed prefix. +TST: 1 +SK: 9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60 +PK: 40d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a +MSG: +SIG: e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e065224901555fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b -- cgit v1.2.1