diff options
author | Werner Koch <wk@gnupg.org> | 2013-10-23 14:08:29 +0200 |
---|---|---|
committer | Werner Koch <wk@gnupg.org> | 2013-10-23 14:08:29 +0200 |
commit | 164eb8c85d773ef4f0939115ec45f5e4b47c1700 (patch) | |
tree | 5051b857c0d076627db8be12d5038e07758c2429 /cipher/ecc.c | |
parent | 45f6e6268bfdc4b608beaba6b7086b2286e33c71 (diff) | |
download | libgcrypt-164eb8c85d773ef4f0939115ec45f5e4b47c1700.tar.gz |
ecc: Refactor ecc.c
* cipher/ecc-ecdsa.c, cipher/ecc-eddsa.c, cipher/ecc-gost.c: New.
* cipher/Makefile.am (EXTRA_libcipher_la_SOURCES): Add new files.
* configure.ac (GCRYPT_PUBKEY_CIPHERS): Add new files.
* cipher/ecc.c (point_init, point_free): Move to ecc-common.h.
(sign_ecdsa): Move to ecc-ecdsa.c as _gcry_ecc_ecdsa_sign.
(verify_ecdsa): Move to ecc-ecdsa.c as _gcry_ecc_ecdsa_verify.
(sign_gost): Move to ecc-gots.c as _gcry_ecc_gost_sign.
(verify_gost): Move to ecc-gost.c as _gcry_ecc_gost_verify.
(sign_eddsa): Move to ecc-eddsa.c as _gcry_ecc_eddsa_sign.
(verify_eddsa): Move to ecc-eddsa.c as _gcry_ecc_eddsa_verify.
(eddsa_generate_key): Move to ecc-eddsa.c as _gcry_ecc_eddsa_genkey.
(reverse_buffer): Move to ecc-eddsa.c.
(eddsa_encodempi, eddsa_encode_x_y): Ditto.
(_gcry_ecc_eddsa_encodepoint, _gcry_ecc_eddsa_decodepoint): Ditto.
--
This change should make it easier to add new ECC algorithms.
Signed-off-by: Werner Koch <wk@gnupg.org>
Diffstat (limited to 'cipher/ecc.c')
-rw-r--r-- | cipher/ecc.c | 1077 |
1 files changed, 12 insertions, 1065 deletions
diff --git a/cipher/ecc.c b/cipher/ecc.c index 27747182..dca04234 100644 --- a/cipher/ecc.c +++ b/cipher/ecc.c @@ -81,19 +81,10 @@ static void (*progress_cb) (void *, const char*, int, int, int); static void *progress_cb_data; -#define point_init(a) _gcry_mpi_point_init ((a)) -#define point_free(a) _gcry_mpi_point_free_parts ((a)) - /* Local prototypes. */ static void test_keys (ECC_secret_key * sk, unsigned int nbits); static int check_secret_key (ECC_secret_key * sk); -static gpg_err_code_t sign_ecdsa (gcry_mpi_t input, ECC_secret_key *skey, - gcry_mpi_t r, gcry_mpi_t s, - int flags, int hashalgo); -static gpg_err_code_t verify_ecdsa (gcry_mpi_t input, ECC_public_key *pkey, - gcry_mpi_t r, gcry_mpi_t s); - static gcry_mpi_t gen_y_2 (gcry_mpi_t x, elliptic_curve_t * base); static unsigned int ecc_get_nbits (gcry_sexp_t parms); @@ -261,10 +252,10 @@ test_keys (ECC_secret_key *sk, unsigned int nbits) gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM); - if (sign_ecdsa (test, sk, r, s, 0, 0) ) + if (_gcry_ecc_ecdsa_sign (test, sk, r, s, 0, 0) ) log_fatal ("ECDSA operation: sign failed\n"); - if (verify_ecdsa (test, &pk, r, s)) + if (_gcry_ecc_ecdsa_verify (test, &pk, r, s)) { log_fatal ("ECDSA operation: sign, verify failed\n"); } @@ -389,1052 +380,6 @@ check_secret_key (ECC_secret_key * sk) } -/* Compute an ECDSA signature. - * Return the signature struct (r,s) from the message hash. The caller - * must have allocated R and S. - */ -static gpg_err_code_t -sign_ecdsa (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s, - int flags, int hashalgo) -{ - gpg_err_code_t err = 0; - int extraloops = 0; - gcry_mpi_t k, dr, sum, k_1, x; - mpi_point_struct I; - gcry_mpi_t hash; - const void *abuf; - unsigned int abits, qbits; - mpi_ec_t ctx; - - if (DBG_CIPHER) - log_mpidump ("ecdsa sign hash ", input ); - - qbits = mpi_get_nbits (skey->E.n); - - /* Convert the INPUT into an MPI if needed. */ - if (mpi_is_opaque (input)) - { - abuf = gcry_mpi_get_opaque (input, &abits); - err = gpg_err_code (gcry_mpi_scan (&hash, GCRYMPI_FMT_USG, - abuf, (abits+7)/8, NULL)); - if (err) - return err; - if (abits > qbits) - gcry_mpi_rshift (hash, hash, abits - qbits); - } - else - hash = input; - - - k = NULL; - dr = mpi_alloc (0); - sum = mpi_alloc (0); - k_1 = mpi_alloc (0); - x = mpi_alloc (0); - point_init (&I); - - ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect, - skey->E.p, skey->E.a, skey->E.b); - - /* Two loops to avoid R or S are zero. This is more of a joke than - a real demand because the probability of them being zero is less - than any hardware failure. Some specs however require it. */ - do - { - do - { - mpi_free (k); - k = NULL; - if ((flags & PUBKEY_FLAG_RFC6979) && hashalgo) - { - /* Use Pornin's method for deterministic DSA. If this - flag is set, it is expected that HASH is an opaque - MPI with the to be signed hash. That hash is also - used as h1 from 3.2.a. */ - if (!mpi_is_opaque (input)) - { - err = GPG_ERR_CONFLICT; - goto leave; - } - - abuf = gcry_mpi_get_opaque (input, &abits); - err = _gcry_dsa_gen_rfc6979_k (&k, skey->E.n, skey->d, - abuf, (abits+7)/8, - hashalgo, extraloops); - if (err) - goto leave; - extraloops++; - } - else - k = _gcry_dsa_gen_k (skey->E.n, GCRY_STRONG_RANDOM); - - _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx); - if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx)) - { - if (DBG_CIPHER) - log_debug ("ecc sign: Failed to get affine coordinates\n"); - err = GPG_ERR_BAD_SIGNATURE; - goto leave; - } - mpi_mod (r, x, skey->E.n); /* r = x mod n */ - } - while (!mpi_cmp_ui (r, 0)); - - mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n */ - mpi_addm (sum, hash, dr, skey->E.n); /* sum = hash + (d*r) mod n */ - mpi_invm (k_1, k, skey->E.n); /* k_1 = k^(-1) mod n */ - mpi_mulm (s, k_1, sum, skey->E.n); /* s = k^(-1)*(hash+(d*r)) mod n */ - } - while (!mpi_cmp_ui (s, 0)); - - if (DBG_CIPHER) - { - log_mpidump ("ecdsa sign result r ", r); - log_mpidump ("ecdsa sign result s ", s); - } - - leave: - _gcry_mpi_ec_free (ctx); - point_free (&I); - mpi_free (x); - mpi_free (k_1); - mpi_free (sum); - mpi_free (dr); - mpi_free (k); - - if (hash != input) - mpi_free (hash); - - return err; -} - - -/* Verify an ECDSA signature. - * Check if R and S verifies INPUT. - */ -static gpg_err_code_t -verify_ecdsa (gcry_mpi_t input, ECC_public_key *pkey, - gcry_mpi_t r, gcry_mpi_t s) -{ - gpg_err_code_t err = 0; - gcry_mpi_t h, h1, h2, x; - mpi_point_struct Q, Q1, Q2; - mpi_ec_t ctx; - - if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) ) - return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < r < n failed. */ - if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) ) - return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < s < n failed. */ - - h = mpi_alloc (0); - h1 = mpi_alloc (0); - h2 = mpi_alloc (0); - x = mpi_alloc (0); - point_init (&Q); - point_init (&Q1); - point_init (&Q2); - - ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect, - pkey->E.p, pkey->E.a, pkey->E.b); - - /* h = s^(-1) (mod n) */ - mpi_invm (h, s, pkey->E.n); - /* h1 = hash * s^(-1) (mod n) */ - mpi_mulm (h1, input, h, pkey->E.n); - /* Q1 = [ hash * s^(-1) ]G */ - _gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx); - /* h2 = r * s^(-1) (mod n) */ - mpi_mulm (h2, r, h, pkey->E.n); - /* Q2 = [ r * s^(-1) ]Q */ - _gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx); - /* Q = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */ - _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx); - - if (!mpi_cmp_ui (Q.z, 0)) - { - if (DBG_CIPHER) - log_debug ("ecc verify: Rejected\n"); - err = GPG_ERR_BAD_SIGNATURE; - goto leave; - } - if (_gcry_mpi_ec_get_affine (x, NULL, &Q, ctx)) - { - if (DBG_CIPHER) - log_debug ("ecc verify: Failed to get affine coordinates\n"); - err = GPG_ERR_BAD_SIGNATURE; - goto leave; - } - mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */ - if (mpi_cmp (x, r)) /* x != r */ - { - if (DBG_CIPHER) - { - log_mpidump (" x", x); - log_mpidump (" r", r); - log_mpidump (" s", s); - } - err = GPG_ERR_BAD_SIGNATURE; - goto leave; - } - - leave: - _gcry_mpi_ec_free (ctx); - point_free (&Q2); - point_free (&Q1); - point_free (&Q); - mpi_free (x); - mpi_free (h2); - mpi_free (h1); - mpi_free (h); - return err; -} - -/* Compute an GOST R 34.10-01/-12 signature. - * Return the signature struct (r,s) from the message hash. The caller - * must have allocated R and S. - */ -static gpg_err_code_t -sign_gost (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s) -{ - gpg_err_code_t err = 0; - gcry_mpi_t k, dr, sum, ke, x, e; - mpi_point_struct I; - gcry_mpi_t hash; - const void *abuf; - unsigned int abits, qbits; - mpi_ec_t ctx; - - if (DBG_CIPHER) - log_mpidump ("gost sign hash ", input ); - - qbits = mpi_get_nbits (skey->E.n); - - /* Convert the INPUT into an MPI if needed. */ - if (mpi_is_opaque (input)) - { - abuf = gcry_mpi_get_opaque (input, &abits); - err = gpg_err_code (gcry_mpi_scan (&hash, GCRYMPI_FMT_USG, - abuf, (abits+7)/8, NULL)); - if (err) - return err; - if (abits > qbits) - gcry_mpi_rshift (hash, hash, abits - qbits); - } - else - hash = input; - - - k = NULL; - dr = mpi_alloc (0); - sum = mpi_alloc (0); - ke = mpi_alloc (0); - e = mpi_alloc (0); - x = mpi_alloc (0); - point_init (&I); - - ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect, - skey->E.p, skey->E.a, skey->E.b); - - mpi_mod (e, input, skey->E.n); /* e = hash mod n */ - - if (!mpi_cmp_ui (e, 0)) - mpi_set_ui (e, 1); - - /* Two loops to avoid R or S are zero. This is more of a joke than - a real demand because the probability of them being zero is less - than any hardware failure. Some specs however require it. */ - do - { - do - { - mpi_free (k); - k = _gcry_dsa_gen_k (skey->E.n, GCRY_STRONG_RANDOM); - - _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx); - if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx)) - { - if (DBG_CIPHER) - log_debug ("ecc sign: Failed to get affine coordinates\n"); - err = GPG_ERR_BAD_SIGNATURE; - goto leave; - } - mpi_mod (r, x, skey->E.n); /* r = x mod n */ - } - while (!mpi_cmp_ui (r, 0)); - mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n */ - mpi_mulm (ke, k, e, skey->E.n); /* ke = k*e mod n */ - mpi_addm (s, ke, dr, skey->E.n); /* sum = (k*e+ d*r) mod n */ - } - while (!mpi_cmp_ui (s, 0)); - - if (DBG_CIPHER) - { - log_mpidump ("gost sign result r ", r); - log_mpidump ("gost sign result s ", s); - } - - leave: - _gcry_mpi_ec_free (ctx); - point_free (&I); - mpi_free (x); - mpi_free (e); - mpi_free (ke); - mpi_free (sum); - mpi_free (dr); - mpi_free (k); - - if (hash != input) - mpi_free (hash); - - return err; -} - -/* Verify a GOST R 34.10-01/-12 signature. - * Check if R and S verifies INPUT. - */ -static gpg_err_code_t -verify_gost (gcry_mpi_t input, ECC_public_key *pkey, - gcry_mpi_t r, gcry_mpi_t s) -{ - gpg_err_code_t err = 0; - gcry_mpi_t e, x, z1, z2, v, rv, zero; - mpi_point_struct Q, Q1, Q2; - mpi_ec_t ctx; - - if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) ) - return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < r < n failed. */ - if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) ) - return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < s < n failed. */ - - x = mpi_alloc (0); - e = mpi_alloc (0); - z1 = mpi_alloc (0); - z2 = mpi_alloc (0); - v = mpi_alloc (0); - rv = mpi_alloc (0); - zero = mpi_alloc (0); - - point_init (&Q); - point_init (&Q1); - point_init (&Q2); - - ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect, - pkey->E.p, pkey->E.a, pkey->E.b); - - mpi_mod (e, input, pkey->E.n); /* e = hash mod n */ - if (!mpi_cmp_ui (e, 0)) - mpi_set_ui (e, 1); - mpi_invm (v, e, pkey->E.n); /* v = e^(-1) (mod n) */ - mpi_mulm (z1, s, v, pkey->E.n); /* z1 = s*v (mod n) */ - mpi_mulm (rv, r, v, pkey->E.n); /* rv = s*v (mod n) */ - mpi_subm (z2, zero, rv, pkey->E.n); /* z2 = -r*v (mod n) */ - - _gcry_mpi_ec_mul_point (&Q1, z1, &pkey->E.G, ctx); -/* log_mpidump ("Q1.x", Q1.x); */ -/* log_mpidump ("Q1.y", Q1.y); */ -/* log_mpidump ("Q1.z", Q1.z); */ - _gcry_mpi_ec_mul_point (&Q2, z2, &pkey->Q, ctx); -/* log_mpidump ("Q2.x", Q2.x); */ -/* log_mpidump ("Q2.y", Q2.y); */ -/* log_mpidump ("Q2.z", Q2.z); */ - _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx); -/* log_mpidump (" Q.x", Q.x); */ -/* log_mpidump (" Q.y", Q.y); */ -/* log_mpidump (" Q.z", Q.z); */ - - if (!mpi_cmp_ui (Q.z, 0)) - { - if (DBG_CIPHER) - log_debug ("ecc verify: Rejected\n"); - err = GPG_ERR_BAD_SIGNATURE; - goto leave; - } - if (_gcry_mpi_ec_get_affine (x, NULL, &Q, ctx)) - { - if (DBG_CIPHER) - log_debug ("ecc verify: Failed to get affine coordinates\n"); - err = GPG_ERR_BAD_SIGNATURE; - goto leave; - } - mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */ - if (mpi_cmp (x, r)) /* x != r */ - { - if (DBG_CIPHER) - { - log_mpidump (" x", x); - log_mpidump (" r", r); - log_mpidump (" s", s); - log_debug ("ecc verify: Not verified\n"); - } - err = GPG_ERR_BAD_SIGNATURE; - goto leave; - } - if (DBG_CIPHER) - log_debug ("ecc verify: Accepted\n"); - - leave: - _gcry_mpi_ec_free (ctx); - point_free (&Q2); - point_free (&Q1); - point_free (&Q); - mpi_free (zero); - mpi_free (rv); - mpi_free (v); - mpi_free (z2); - mpi_free (z1); - mpi_free (x); - mpi_free (e); - return err; -} - - -static void -reverse_buffer (unsigned char *buffer, unsigned int length) -{ - unsigned int tmp, i; - - for (i=0; i < length/2; i++) - { - tmp = buffer[i]; - buffer[i] = buffer[length-1-i]; - buffer[length-1-i] = tmp; - } -} - - -/* Encode MPI using the EdDSA scheme. MINLEN specifies the required - length of the buffer in bytes. On success 0 is returned an 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_encodempi (gcry_mpi_t mpi, unsigned int minlen, - unsigned char **r_buffer, unsigned int *r_buflen) -{ - unsigned char *rawmpi; - unsigned int rawmpilen; - - rawmpi = _gcry_mpi_get_buffer (mpi, minlen, &rawmpilen, NULL); - if (!rawmpi) - return gpg_err_code_from_syserror (); - - *r_buffer = rawmpi; - *r_buflen = rawmpilen; - return 0; -} - - -/* 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. */ -static gpg_err_code_t -eddsa_encode_x_y (gcry_mpi_t x, gcry_mpi_t y, unsigned int minlen, - unsigned char **r_buffer, unsigned int *r_buflen) -{ - unsigned char *rawmpi; - unsigned int rawmpilen; - - rawmpi = _gcry_mpi_get_buffer (y, minlen, &rawmpilen, NULL); - if (!rawmpi) - return gpg_err_code_from_syserror (); - if (mpi_test_bit (x, 0) && rawmpilen) - rawmpi[rawmpilen - 1] |= 0x80; /* Set sign bit. */ - - *r_buffer = rawmpi; - *r_buflen = rawmpilen; - 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. */ -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, - unsigned char **r_buffer, unsigned int *r_buflen) -{ - gpg_err_code_t rc; - gcry_mpi_t x, y; - - x = x_in? x_in : mpi_new (0); - y = y_in? y_in : mpi_new (0); - - if (_gcry_mpi_ec_get_affine (x, y, point, ec)) - { - log_error ("eddsa_encodepoint: Failed to get affine coordinates\n"); - rc = GPG_ERR_INTERNAL; - } - else - rc = eddsa_encode_x_y (x, y, ec->nbits/8, r_buffer, r_buflen); - - if (!x_in) - mpi_free (x); - if (!y_in) - mpi_free (y); - return rc; -} - - -/* Decode the EdDSA style encoded PK and set it into RESULT. CTX is - 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 received 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, - unsigned char **r_encpk, unsigned int *r_encpklen) -{ - gpg_err_code_t rc; - unsigned char *rawmpi; - unsigned int rawmpilen; - gcry_mpi_t yy, t, x, p1, p2, p3; - int sign; - - if (mpi_is_opaque (pk)) - { - const unsigned char *buf; - - buf = gcry_mpi_get_opaque (pk, &rawmpilen); - if (!buf) - 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)) - { - gcry_mpi_t 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) - { - mpi_free (x); - return rc; - } - - if (r_encpk) - { - rc = eddsa_encode_x_y (x, y, ctx->nbits/8, 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; - } - - /* EdDSA compressed point. */ - rawmpi = gcry_malloc (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 EdDSA format here. */ - rawmpi = _gcry_mpi_get_buffer (pk, ctx->nbits/8, &rawmpilen, NULL); - if (!rawmpi) - return gpg_err_code_from_syserror (); - } - - if (rawmpilen) - { - sign = !!(rawmpi[0] & 0x80); - rawmpi[0] &= 0x7f; - } - else - sign = 0; - _gcry_mpi_set_buffer (result->y, rawmpi, rawmpilen, 0); - if (r_encpk) - { - /* Revert to little endian. */ - if (sign && rawmpilen) - rawmpi[0] |= 0x80; - reverse_buffer (rawmpi, rawmpilen); - *r_encpk = rawmpi; - if (r_encpklen) - *r_encpklen = rawmpilen; - } - else - gcry_free (rawmpi); - - /* Now recover X. */ - /* t = (y^2-1) · ((b*y^2+1)^{p-2} mod p) */ - x = mpi_new (0); - yy = mpi_new (0); - mpi_mul (yy, result->y, result->y); - t = mpi_copy (yy); - mpi_mul (t, t, ctx->b); - mpi_add_ui (t, t, 1); - p2 = mpi_copy (ctx->p); - mpi_sub_ui (p2, p2, 2); - mpi_powm (t, t, p2, ctx->p); - - mpi_sub_ui (yy, yy, 1); - mpi_mul (t, yy, t); - - /* x = t^{(p+3)/8} mod p */ - p3 = mpi_copy (ctx->p); - mpi_add_ui (p3, p3, 3); - mpi_fdiv_q (p3, p3, mpi_const (MPI_C_EIGHT)); - mpi_powm (x, t, p3, ctx->p); - - /* (x^2 - t) % p != 0 ? x = (x*(2^{(p-1)/4} mod p)) % p */ - mpi_mul (yy, x, x); - mpi_subm (yy, yy, t, ctx->p); - if (mpi_cmp_ui (yy, 0)) - { - p1 = mpi_copy (ctx->p); - mpi_sub_ui (p1, p1, 1); - mpi_fdiv_q (p1, p1, mpi_const (MPI_C_FOUR)); - mpi_powm (yy, mpi_const (MPI_C_TWO), p1, ctx->p); - mpi_mulm (x, x, yy, ctx->p); - } - else - p1 = NULL; - - /* is_odd(x) ? x = p-x */ - if (mpi_test_bit (x, 0)) - mpi_sub (x, ctx->p, x); - - /* lowbit(x) != highbit(input) ? x = p-x */ - if (mpi_test_bit (x, 0) != sign) - mpi_sub (x, ctx->p, x); - - mpi_set (result->x, x); - mpi_set_ui (result->z, 1); - - gcry_mpi_release (x); - gcry_mpi_release (yy); - gcry_mpi_release (t); - gcry_mpi_release (p3); - gcry_mpi_release (p2); - gcry_mpi_release (p1); - - return 0; -} - - -/* Ed25519 version of the key generation. */ -static gpg_err_code_t -eddsa_generate_key (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx, - gcry_random_level_t random_level) -{ - gpg_err_code_t rc; - int b = 256/8; /* The only size we currently support. */ - gcry_mpi_t a, x, y; - mpi_point_struct Q; - char *dbuf; - size_t dlen; - gcry_buffer_t hvec[1]; - unsigned char *hash_d = NULL; - - point_init (&Q); - memset (hvec, 0, sizeof hvec); - - a = mpi_snew (0); - x = mpi_new (0); - y = mpi_new (0); - - /* Generate a secret. */ - hash_d = gcry_malloc_secure (2*b); - if (!hash_d) - { - rc = gpg_error_from_syserror (); - goto leave; - } - dlen = b; - dbuf = gcry_random_bytes_secure (dlen, random_level); - - /* Compute the A value. */ - hvec[0].data = dbuf; - hvec[0].len = dlen; - rc = _gcry_md_hash_buffers (GCRY_MD_SHA512, 0, hash_d, hvec, 1); - if (rc) - goto leave; - sk->d = _gcry_mpi_set_opaque (NULL, dbuf, dlen*8); - dbuf = NULL; - reverse_buffer (hash_d, 32); /* Only the first half of the hash. */ - hash_d[0] = (hash_d[0] & 0x7f) | 0x40; - hash_d[31] &= 0xf8; - _gcry_mpi_set_buffer (a, hash_d, 32, 0); - gcry_free (hash_d); hash_d = NULL; - /* log_printmpi ("ecgen a", a); */ - - /* Compute Q. */ - _gcry_mpi_ec_mul_point (&Q, a, &E->G, ctx); - if (DBG_CIPHER) - log_printpnt ("ecgen pk", &Q, ctx); - - /* Copy the stuff to the key structures. */ - sk->E.model = E->model; - sk->E.dialect = E->dialect; - sk->E.p = mpi_copy (E->p); - sk->E.a = mpi_copy (E->a); - sk->E.b = mpi_copy (E->b); - point_init (&sk->E.G); - point_set (&sk->E.G, &E->G); - sk->E.n = mpi_copy (E->n); - point_init (&sk->Q); - point_set (&sk->Q, &Q); - - leave: - gcry_mpi_release (a); - gcry_mpi_release (x); - gcry_mpi_release (y); - gcry_free (hash_d); - return rc; -} - - -/* Compute an EdDSA signature. See: - * [ed25519] 23pp. (PDF) Daniel J. Bernstein, Niels Duif, Tanja - * Lange, Peter Schwabe, Bo-Yin Yang. High-speed high-security - * signatures. Journal of Cryptographic Engineering 2 (2012), 77-89. - * Document ID: a1a62a2f76d23f65d622484ddd09caf8. - * URL: http://cr.yp.to/papers.html#ed25519. Date: 2011.09.26. - * - * Despite that this function requires the specification of a hash - * algorithm, we only support what has been specified by the paper. - * This may change in the future. Note that we don't check the used - * curve; the user is responsible to use Ed25519. - * - * Return the signature struct (r,s) from the message hash. The caller - * must have allocated R_R and S. - */ -static gpg_err_code_t -sign_eddsa (gcry_mpi_t input, ECC_secret_key *skey, - gcry_mpi_t r_r, gcry_mpi_t s, int hashalgo, gcry_mpi_t pk) -{ - int rc; - mpi_ec_t ctx = NULL; - int b; - unsigned int tmp; - unsigned char *digest; - gcry_buffer_t hvec[3]; - const void *mbuf; - size_t mlen; - unsigned char *rawmpi = NULL; - unsigned int rawmpilen; - unsigned char *encpk = NULL; /* Encoded public key. */ - unsigned int encpklen; - mpi_point_struct I; /* Intermediate value. */ - mpi_point_struct Q; /* Public key. */ - gcry_mpi_t a, x, y, r; - - memset (hvec, 0, sizeof hvec); - - if (!mpi_is_opaque (input)) - return GPG_ERR_INV_DATA; - if (hashalgo != GCRY_MD_SHA512) - return GPG_ERR_DIGEST_ALGO; - - /* Initialize some helpers. */ - point_init (&I); - point_init (&Q); - a = mpi_snew (0); - x = mpi_new (0); - y = mpi_new (0); - r = mpi_new (0); - ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect, - skey->E.p, skey->E.a, skey->E.b); - b = (ctx->nbits+7)/8; - if (b != 256/8) - return GPG_ERR_INTERNAL; /* We only support 256 bit. */ - - digest = gcry_calloc_secure (2, b); - if (!digest) - { - rc = gpg_err_code_from_syserror (); - goto leave; - } - - /* Hash the secret key. We clear DIGEST so we can use it as input - to left pad the key with zeroes for hashing. */ - rawmpi = _gcry_mpi_get_buffer (skey->d, 0, &rawmpilen, NULL); - if (!rawmpi) - { - rc = gpg_err_code_from_syserror (); - goto leave; - } - hvec[0].data = digest; - hvec[0].off = 0; - hvec[0].len = b > rawmpilen? b - rawmpilen : 0; - hvec[1].data = rawmpi; - hvec[1].off = 0; - hvec[1].len = rawmpilen; - rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2); - gcry_free (rawmpi); rawmpi = NULL; - if (rc) - goto leave; - - /* Compute the A value (this modifies DIGEST). */ - reverse_buffer (digest, 32); /* Only the first half of the hash. */ - digest[0] = (digest[0] & 0x7f) | 0x40; - digest[31] &= 0xf8; - _gcry_mpi_set_buffer (a, digest, 32, 0); - - /* Compute the public key if it has not been supplied as optional - parameter. */ - if (pk) - { - rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q, &encpk, &encpklen); - if (rc) - goto leave; - if (DBG_CIPHER) - log_printhex ("* e_pk", encpk, encpklen); - if (!_gcry_mpi_ec_curve_point (&Q, ctx)) - { - rc = GPG_ERR_BROKEN_PUBKEY; - goto leave; - } - } - else - { - _gcry_mpi_ec_mul_point (&Q, a, &skey->E.G, ctx); - rc = _gcry_ecc_eddsa_encodepoint (&Q, ctx, x, y, &encpk, &encpklen); - if (rc) - goto leave; - if (DBG_CIPHER) - log_printhex (" e_pk", encpk, encpklen); - } - - /* Compute R. */ - mbuf = gcry_mpi_get_opaque (input, &tmp); - mlen = (tmp +7)/8; - if (DBG_CIPHER) - log_printhex (" m", mbuf, mlen); - - hvec[0].data = digest; - hvec[0].off = 32; - hvec[0].len = 32; - hvec[1].data = (char*)mbuf; - hvec[1].len = mlen; - rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2); - if (rc) - goto leave; - reverse_buffer (digest, 64); - if (DBG_CIPHER) - log_printhex (" r", digest, 64); - _gcry_mpi_set_buffer (r, digest, 64, 0); - _gcry_mpi_ec_mul_point (&I, r, &skey->E.G, ctx); - if (DBG_CIPHER) - log_printpnt (" r", &I, ctx); - - /* Convert R into affine coordinates and apply encoding. */ - rc = _gcry_ecc_eddsa_encodepoint (&I, ctx, x, y, &rawmpi, &rawmpilen); - if (rc) - goto leave; - if (DBG_CIPHER) - log_printhex (" e_r", rawmpi, rawmpilen); - - /* S = r + a * H(encodepoint(R) + encodepoint(pk) + m) mod n */ - hvec[0].data = rawmpi; /* (this is R) */ - hvec[0].off = 0; - hvec[0].len = rawmpilen; - hvec[1].data = encpk; - hvec[1].off = 0; - hvec[1].len = encpklen; - hvec[2].data = (char*)mbuf; - hvec[2].off = 0; - hvec[2].len = mlen; - rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3); - if (rc) - goto leave; - - /* No more need for RAWMPI thus we now transfer it to R_R. */ - gcry_mpi_set_opaque (r_r, rawmpi, rawmpilen*8); - rawmpi = NULL; - - reverse_buffer (digest, 64); - if (DBG_CIPHER) - log_printhex (" H(R+)", digest, 64); - _gcry_mpi_set_buffer (s, digest, 64, 0); - mpi_mulm (s, s, a, skey->E.n); - mpi_addm (s, s, r, skey->E.n); - rc = eddsa_encodempi (s, b, &rawmpi, &rawmpilen); - if (rc) - goto leave; - if (DBG_CIPHER) - log_printhex (" e_s", rawmpi, rawmpilen); - gcry_mpi_set_opaque (s, rawmpi, rawmpilen*8); - rawmpi = NULL; - - rc = 0; - - leave: - gcry_mpi_release (a); - gcry_mpi_release (x); - gcry_mpi_release (y); - gcry_mpi_release (r); - gcry_free (digest); - _gcry_mpi_ec_free (ctx); - point_free (&I); - point_free (&Q); - gcry_free (encpk); - gcry_free (rawmpi); - return rc; -} - - -/* Verify an EdDSA signature. See sign_eddsa for the reference. - * Check if R_IN and S_IN verifies INPUT. PKEY has the curve - * parameters and PK is the EdDSA style encoded public key. - */ -static gpg_err_code_t -verify_eddsa (gcry_mpi_t input, ECC_public_key *pkey, - gcry_mpi_t r_in, gcry_mpi_t s_in, int hashalgo, gcry_mpi_t pk) -{ - int rc; - mpi_ec_t ctx = NULL; - int b; - unsigned int tmp; - mpi_point_struct Q; /* Public key. */ - unsigned char *encpk = NULL; /* Encoded public key. */ - unsigned int encpklen; - const void *mbuf, *rbuf; - unsigned char *tbuf = NULL; - size_t mlen, rlen; - unsigned int tlen; - unsigned char digest[64]; - gcry_buffer_t hvec[3]; - gcry_mpi_t h, s; - mpi_point_struct Ia, Ib; - - if (!mpi_is_opaque (input) || !mpi_is_opaque (r_in) || !mpi_is_opaque (s_in)) - return GPG_ERR_INV_DATA; - if (hashalgo != GCRY_MD_SHA512) - return GPG_ERR_DIGEST_ALGO; - - point_init (&Q); - point_init (&Ia); - point_init (&Ib); - h = mpi_new (0); - s = mpi_new (0); - - ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect, - pkey->E.p, pkey->E.a, pkey->E.b); - b = ctx->nbits/8; - if (b != 256/8) - return GPG_ERR_INTERNAL; /* We only support 256 bit. */ - - /* Decode and check the public key. */ - rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q, &encpk, &encpklen); - if (rc) - goto leave; - if (!_gcry_mpi_ec_curve_point (&Q, ctx)) - { - rc = GPG_ERR_BROKEN_PUBKEY; - goto leave; - } - if (DBG_CIPHER) - log_printhex (" e_pk", encpk, encpklen); - if (encpklen != b) - { - rc = GPG_ERR_INV_LENGTH; - goto leave; - } - - /* Convert the other input parameters. */ - mbuf = gcry_mpi_get_opaque (input, &tmp); - mlen = (tmp +7)/8; - if (DBG_CIPHER) - log_printhex (" m", mbuf, mlen); - rbuf = gcry_mpi_get_opaque (r_in, &tmp); - rlen = (tmp +7)/8; - if (DBG_CIPHER) - log_printhex (" r", rbuf, rlen); - if (rlen != b) - { - rc = GPG_ERR_INV_LENGTH; - goto leave; - } - - /* h = H(encodepoint(R) + encodepoint(pk) + m) */ - hvec[0].data = (char*)rbuf; - hvec[0].off = 0; - hvec[0].len = rlen; - hvec[1].data = encpk; - hvec[1].off = 0; - hvec[1].len = encpklen; - hvec[2].data = (char*)mbuf; - hvec[2].off = 0; - hvec[2].len = mlen; - rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3); - if (rc) - goto leave; - reverse_buffer (digest, 64); - if (DBG_CIPHER) - log_printhex (" H(R+)", digest, 64); - _gcry_mpi_set_buffer (h, digest, 64, 0); - - /* According to the paper the best way for verification is: - encodepoint(sG - h·Q) = encodepoint(r) - because we don't need to decode R. */ - { - void *sbuf; - unsigned int slen; - - sbuf = _gcry_mpi_get_opaque_copy (s_in, &tmp); - slen = (tmp +7)/8; - reverse_buffer (sbuf, slen); - if (DBG_CIPHER) - log_printhex (" s", sbuf, slen); - _gcry_mpi_set_buffer (s, sbuf, slen, 0); - gcry_free (sbuf); - if (slen != b) - { - rc = GPG_ERR_INV_LENGTH; - goto leave; - } - } - - _gcry_mpi_ec_mul_point (&Ia, s, &pkey->E.G, ctx); - _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); - if (rc) - goto leave; - if (tlen != rlen || memcmp (tbuf, rbuf, tlen)) - { - rc = GPG_ERR_BAD_SIGNATURE; - goto leave; - } - - rc = 0; - - leave: - gcry_free (encpk); - gcry_free (tbuf); - _gcry_mpi_ec_free (ctx); - gcry_mpi_release (s); - gcry_mpi_release (h); - point_free (&Ia); - point_free (&Ib); - point_free (&Q); - return rc; -} - - /********************************************* ************** interface ****************** @@ -1540,7 +485,7 @@ ecc_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey) rc = nist_generate_key (&sk, &E, ctx, random_level, nbits); } else - rc = eddsa_generate_key (&sk, &E, ctx, random_level); + rc = _gcry_ecc_eddsa_genkey (&sk, &E, ctx, random_level); break; default: rc = GPG_ERR_INTERNAL; @@ -1830,21 +775,22 @@ ecc_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms) if ((ctx.flags & PUBKEY_FLAG_EDDSA)) { /* EdDSA requires the public key. */ - rc = sign_eddsa (data, &sk, sig_r, sig_s, ctx.hash_algo, mpi_q); + rc = _gcry_ecc_eddsa_sign (data, &sk, sig_r, sig_s, ctx.hash_algo, mpi_q); if (!rc) rc = gcry_sexp_build (r_sig, NULL, "(sig-val(eddsa(r%M)(s%M)))", sig_r, sig_s); } else if ((ctx.flags & PUBKEY_FLAG_GOST)) { - rc = sign_gost (data, &sk, sig_r, sig_s); + rc = _gcry_ecc_gost_sign (data, &sk, sig_r, sig_s); if (!rc) rc = gcry_sexp_build (r_sig, NULL, "(sig-val(gost(r%M)(s%M)))", sig_r, sig_s); } else { - rc = sign_ecdsa (data, &sk, sig_r, sig_s, ctx.flags, ctx.hash_algo); + rc = _gcry_ecc_ecdsa_sign (data, &sk, sig_r, sig_s, + ctx.flags, ctx.hash_algo); if (!rc) rc = gcry_sexp_build (r_sig, NULL, "(sig-val(ecdsa(r%M)(s%M)))", sig_r, sig_s); @@ -1990,7 +936,8 @@ ecc_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms) */ if ((sigflags & PUBKEY_FLAG_EDDSA)) { - rc = verify_eddsa (data, &pk, sig_r, sig_s, ctx.hash_algo, mpi_q); + rc = _gcry_ecc_eddsa_verify (data, &pk, sig_r, sig_s, + ctx.hash_algo, mpi_q); } else if ((sigflags & PUBKEY_FLAG_GOST)) { @@ -1999,7 +946,7 @@ ecc_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms) if (rc) goto leave; - rc = verify_gost (data, &pk, sig_r, sig_s); + rc = _gcry_ecc_gost_verify (data, &pk, sig_r, sig_s); } else { @@ -2024,12 +971,12 @@ ecc_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms) if (abits > qbits) gcry_mpi_rshift (a, a, abits - qbits); - rc = verify_ecdsa (a, &pk, sig_r, sig_s); + rc = _gcry_ecc_ecdsa_verify (a, &pk, sig_r, sig_s); gcry_mpi_release (a); } } else - rc = verify_ecdsa (data, &pk, sig_r, sig_s); + rc = _gcry_ecc_ecdsa_verify (data, &pk, sig_r, sig_s); } leave: |