From: Daiki Ueno dueno@redhat.com
This adds the ecdsa_sign_deterministic function that calculates signature without requiring entropy source. Instead, it uses the deterministic construction described in RFC 6979, through _dsa_compute_k.
Signed-off-by: Daiki Ueno dueno@redhat.com --- Makefile.in | 3 +- dsa-sign-deterministic.c | 107 ++++++++++++++++++++++++++++ dsa.h | 12 ++++ testsuite/dsa-test.c | 148 ++++++++++++++++++++++++++++++++++++++- 4 files changed, 268 insertions(+), 2 deletions(-) create mode 100644 dsa-sign-deterministic.c
diff --git a/Makefile.in b/Makefile.in index 5f77b98d..856f9d9e 100644 --- a/Makefile.in +++ b/Makefile.in @@ -187,7 +187,8 @@ hogweed_SOURCES = sexp.c sexp-format.c \ eddsa-hash.c eddsa-pubkey.c eddsa-sign.c eddsa-verify.c \ ed25519-sha512-pubkey.c \ ed25519-sha512-sign.c ed25519-sha512-verify.c \ - dsa-compute-k.c ecdsa-sign-deterministic.c + dsa-compute-k.c ecdsa-sign-deterministic.c \ + dsa-sign-deterministic.c
OPT_SOURCES = fat-x86_64.c fat-arm.c mini-gmp.c
diff --git a/dsa-sign-deterministic.c b/dsa-sign-deterministic.c new file mode 100644 index 00000000..8c75b80f --- /dev/null +++ b/dsa-sign-deterministic.c @@ -0,0 +1,107 @@ +/* dsa-sign-deterministic.c + + Copyright (C) 2002, 2010 Niels Möller + Copyright (C) 2019 Red Hat, Inc. + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <assert.h> +#include <stdlib.h> + +#include "dsa.h" +#include "dsa-internal.h" +#include "dsa-compute-k.h" + +#include "bignum.h" + + +int +dsa_sign_deterministic (const struct dsa_params *params, + const mpz_t x, + void *mac_ctx, + nettle_hash_update_func *set_key, + nettle_hash_update_func *update, + nettle_hash_digest_func *digest, + size_t digest_length, + const uint8_t *digest_message, + struct dsa_signature *signature) +{ + mpz_t k; + mpz_t h; + mpz_t tmp; + int res; + + /* Check that p is odd, so that invalid keys don't result in a crash + inside mpz_powm_sec. */ + if (mpz_even_p (params->p)) + return 0; + + /* Select k, 0<k<q, deterministically */ + mpz_init(k); + _dsa_compute_k (mpz_limbs_write (k, mpz_size (params->q)), + mpz_size (params->q), + mpz_limbs_read (params->q), + mpz_limbs_read (x), + mac_ctx, set_key, update, digest, + digest_length, digest_message); + mpz_limbs_finish (k, mpz_size (params->q)); + + /* Compute r = (g^k (mod p)) (mod q) */ + mpz_init (tmp); + mpz_powm_sec(tmp, params->g, k, params->p); + mpz_fdiv_r(signature->r, tmp, params->q); + + /* Compute hash */ + mpz_init(h); + _dsa_hash (h, mpz_sizeinbase(params->q, 2), digest_length, digest_message); + + /* Compute k^-1 (mod q) */ + if (mpz_invert(k, k, params->q)) + { + /* Compute signature s = k^-1 (h + xr) (mod q) */ + mpz_mul(tmp, signature->r, x); + mpz_fdiv_r(tmp, tmp, params->q); + mpz_add(tmp, tmp, h); + mpz_mul(tmp, tmp, k); + mpz_fdiv_r(signature->s, tmp, params->q); + res = 1; + } + else + /* What do we do now? The key is invalid. */ + res = 0; + + mpz_clear(k); + mpz_clear(h); + mpz_clear(tmp); + + return res; +} diff --git a/dsa.h b/dsa.h index 553ef327..fddaea9d 100644 --- a/dsa.h +++ b/dsa.h @@ -47,6 +47,7 @@ extern "C" { #define dsa_signature_init nettle_dsa_signature_init #define dsa_signature_clear nettle_dsa_signature_clear #define dsa_sign nettle_dsa_sign +#define dsa_sign_deterministic nettle_dsa_sign_deterministic #define dsa_verify nettle_dsa_verify #define dsa_generate_params nettle_dsa_generate_params #define dsa_generate_keypair nettle_dsa_generate_keypair @@ -109,6 +110,17 @@ dsa_sign(const struct dsa_params *params, const uint8_t *digest, struct dsa_signature *signature);
+int +dsa_sign_deterministic (const struct dsa_params *params, + const mpz_t x, + void *mac_ctx, + nettle_hash_update_func *set_key, + nettle_hash_update_func *update, + nettle_hash_digest_func *digest, + size_t digest_length, + const uint8_t *digest_message, + struct dsa_signature *signature); + int dsa_verify(const struct dsa_params *params, const mpz_t y, diff --git a/testsuite/dsa-test.c b/testsuite/dsa-test.c index 9a80c967..dbc8d063 100644 --- a/testsuite/dsa-test.c +++ b/testsuite/dsa-test.c @@ -1,4 +1,57 @@ #include "testutils.h" +#include "hmac.h" +#include "nettle-internal.h" + +static void +test_dsa_sign_deterministic(const struct dsa_params *params, + /* Private key */ + const char *sz, + /* HMAC */ + void *mac_ctx, + nettle_hash_update_func *set_key, + nettle_hash_update_func *update, + nettle_hash_digest_func *digest, + /* Hash */ + const struct tstring *h, + /* Expected signature */ + const char *r, const char *s) +{ + struct dsa_signature ref; + struct dsa_signature signature; + mpz_t z; + + dsa_signature_init (&ref); + dsa_signature_init(&signature); + + mpz_init_set_str (z, sz, 16); + + ASSERT (dsa_sign_deterministic (params, z, + mac_ctx, set_key, update, digest, + h->length, h->data, &signature)); + + mpz_set_str (ref.r, r, 16); + mpz_set_str (ref.s, s, 16); + + if (mpz_cmp (signature.r, ref.r) != 0 + || mpz_cmp (signature.s, ref.s) != 0) + { + fprintf (stderr, "_dsa_sign failed\n"); + fprintf (stderr, "r = "); + mpz_out_str (stderr, 16, signature.r); + fprintf (stderr, "\ns = "); + mpz_out_str (stderr, 16, signature.s); + fprintf (stderr, "\nref.r = "); + mpz_out_str (stderr, 16, ref.r); + fprintf (stderr, "\nref.s = "); + mpz_out_str (stderr, 16, ref.s); + fprintf (stderr, "\n"); + abort(); + } + + dsa_signature_clear (&ref); + dsa_signature_clear (&signature); + mpz_clear (z); +}
void test_main(void) @@ -7,6 +60,13 @@ test_main(void) struct dsa_private_key key; struct dsa_signature signature; struct dsa_params *params = (struct dsa_params *) &pub; + struct hmac_sha256_ctx hmac_sha256; + struct sha256_ctx hash_sha256; + uint8_t digest[NETTLE_MAX_HASH_DIGEST_SIZE]; + + sha256_init (&hash_sha256); + sha256_update (&hash_sha256, 6, (const uint8_t *)"sample"); + sha256_digest (&hash_sha256, SHA256_DIGEST_SIZE, digest);
dsa_public_key_init(&pub); dsa_private_key_init(&key); @@ -877,7 +937,93 @@ test_main(void) "bb7441c122f1dc2f9d0b0bc07f26ba29a35cdf0da846a9d8" "eab405cbf8c8e77f"), &signature); - + + /* Test vectors from RFC 6979 */ + mpz_set_str(pub.p, + "86f5ca03dcfeb225063ff830a0c769b9dd9d6153ad91d7ce" + "27f787c43278b447e6533b86b18bed6e8a48b784a14c252c" + "5be0dbf60b86d6385bd2f12fb763ed8873abfd3f5ba2e0a8" + "c0a59082eac056935e529daf7c610467899c77adedfc846c" + "881870b7b19b2b58f9be0521a17002e3bdd6b86685ee90b3" + "d9a1b02b782b1779", 16); + mpz_set_str(pub.q, + "996f967f6c8e388d9e28d01e205fba957a5698b1", 16); + mpz_set_str(pub.g, + "07b0f92546150b62514bb771e2a0c0ce387f03bda6c56b50" + "5209ff25fd3c133d89bbcd97e904e09114d9a7defdeadfc9" + "078ea544d2e401aeecc40bb9fbbf78fd87995a10a1c27cb7" + "789b594ba7efb5c4326a9fe59a070e136db77175464adca4" + "17be5dce2f40d10a46a3a3943f26ab7fd9c0398ff8c76ee0" + "a56826a8a88f1dbd", 16); + mpz_set_str(pub.y, + "5df5e01ded31d0297e274e1691c192fe5868fef9e19a8477" + "6454b100cf16f65392195a38b90523e2542ee61871c0440c" + "b87c322fc4b4d2ec5e1e7ec766e1be8d4ce935437dc11c3c" + "8fd426338933ebfe739cb3465f4d3668c5e473508253b1e6" + "82f65cbdc4fae93c2ea212390e54905a86e2223170b44eaa" + "7da5dd9ffcfb7f3b", 16); + test_dsa_sign_deterministic (params, + "411602cb19a6ccc34494d79d98ef1e7ed5af25f7", + &hmac_sha256, + (nettle_hash_update_func *)hmac_sha256_set_key, + (nettle_hash_update_func *)hmac_sha256_update, + (nettle_hash_digest_func *)hmac_sha256_digest, + tstring_data (SHA256_DIGEST_SIZE, digest), /* h */ + "81f2f5850be5bc123c43f71a3033e9384611c545", + "4cdd914b65eb6c66a8aaad27299bee6b035f5e89"); + + mpz_set_str(pub.p, + "9db6fb5951b66bb6fe1e140f1d2ce5502374161fd6538df1" + "648218642f0b5c48c8f7a41aadfa187324b87674fa1822b0" + "0f1ecf8136943d7c55757264e5a1a44ffe012e9936e00c1d" + "3e9310b01c7d179805d3058b2a9f4bb6f9716bfe6117c6b5" + "b3cc4d9be341104ad4a80ad6c94e005f4b993e14f091eb51" + "743bf33050c38de235567e1b34c3d6a5c0ceaa1a0f368213" + "c3d19843d0b4b09dcb9fc72d39c8de41f1bf14d4bb4563ca" + "28371621cad3324b6a2d392145bebfac748805236f5ca2fe" + "92b871cd8f9c36d3292b5509ca8caa77a2adfc7bfd77dda6" + "f71125a7456fea153e433256a2261c6a06ed3693797e7995" + "fad5aabbcfbe3eda2741e375404ae25b", 16); + mpz_set_str(pub.q, + "f2c3119374ce76c9356990b465374a17f23f9ed35089bd96" + "9f61c6dde9998c1f", 16); + mpz_set_str(pub.g, + "5c7ff6b06f8f143fe8288433493e4769c4d988ace5be25a0" + "e24809670716c613d7b0cee6932f8faa7c44d2cb24523da5" + "3fbe4f6ec3595892d1aa58c4328a06c46a15662e7eaa703a" + "1decf8bbb2d05dbe2eb956c142a338661d10461c0d135472" + "085057f3494309ffa73c611f78b32adbb5740c361c9f35be" + "90997db2014e2ef5aa61782f52abeb8bd6432c4dd097bc54" + "23b285dafb60dc364e8161f4a2a35aca3a10b1c4d203cc76" + "a470a33afdcbdd92959859abd8b56e1725252d78eac66e71" + "ba9ae3f1dd2487199874393cd4d832186800654760e1e34c" + "09e4d155179f9ec0dc4473f996bdce6eed1cabed8b6f116f" + "7ad9cf505df0f998e34ab27514b0ffe7", 16); + mpz_set_str(pub.y, + "667098c654426c78d7f8201eac6c203ef030d43605032c2f" + "1fa937e5237dbd949f34a0a2564fe126dc8b715c5141802c" + "e0979c8246463c40e6b6bdaa2513fa611728716c2e4fd53b" + "c95b89e69949d96512e873b9c8f8dfd499cc312882561ade" + "cb31f658e934c0c197f2c4d96b05cbad67381e7b768891e4" + "da3843d24d94cdfb5126e9b8bf21e8358ee0e0a30ef13fd6" + "a664c0dce3731f7fb49a4845a4fd8254687972a2d382599c" + "9bac4e0ed7998193078913032558134976410b89d2c171d1" + "23ac35fd977219597aa7d15c1a9a428e59194f75c721ebcb" + "cfae44696a499afa74e04299f132026601638cb87ab79190" + "d4a0986315da8eec6561c938996beadf", 16); + test_dsa_sign_deterministic (params, + "69c7548c21d0dfea6b9a51c9ead4e27c33d3b3f1" + "80316e5bcab92c933f0e4dbc", + &hmac_sha256, + (nettle_hash_update_func *)hmac_sha256_set_key, + (nettle_hash_update_func *)hmac_sha256_update, + (nettle_hash_digest_func *)hmac_sha256_digest, + tstring_data (SHA256_DIGEST_SIZE, digest), /* h */ + "eace8bdbbe353c432a795d9ec556c6d021f7a03f" + "42c36e9bc87e4ac7932cc809", + "7081e175455f9247b812b74583e9e94f9ea79bd6" + "40dc962533b0680793a38d53"); + dsa_public_key_clear(&pub); dsa_private_key_clear(&key); dsa_signature_clear(&signature);