From: Daiki Ueno <du...@redhat.com>
This adds the _dsa_compute_k function that generates DSA/ECDSA k value
from the private key and the hashed message, according to RFC 6979.
Signed-off-by: Daiki Ueno <du...@redhat.com>
---
Makefile.in | 5 +-
dsa-compute-k.c | 179 +++++++++++++++++++++++++++++++++
dsa-compute-k.h | 63 ++++++++++++
testsuite/.gitignore | 1 +
testsuite/.test-rules.make | 3 +
testsuite/Makefile.in | 3 +-
testsuite/dsa-compute-k-test.c | 127 +++++++++++++++++++++++
7 files changed, 378 insertions(+), 3 deletions(-)
create mode 100644 dsa-compute-k.c
create mode 100644 dsa-compute-k.h
create mode 100644 testsuite/dsa-compute-k-test.c
diff --git a/Makefile.in b/Makefile.in
index b54e64b0..36b2a182 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -187,7 +187,8 @@ hogweed_SOURCES = sexp.c sexp-format.c \
eddsa-compress.c eddsa-decompress.c eddsa-expand.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
+ ed25519-sha512-sign.c ed25519-sha512-verify.c \
+ dsa-compute-k.c
OPT_SOURCES = fat-x86_64.c fat-arm.c mini-gmp.c
@@ -237,7 +238,7 @@ DISTFILES = $(SOURCES) $(HEADERS) getopt.h getopt_int.h \
ctr-internal.h chacha-internal.h sha3-internal.h \
salsa20-internal.h umac-internal.h hogweed-internal.h \
rsa-internal.h pkcs1-internal.h dsa-internal.h eddsa-internal.h \
- gmp-glue.h ecc-internal.h fat-setup.h \
+ gmp-glue.h ecc-internal.h fat-setup.h dsa-compute-k.h \
mini-gmp.h asm.m4 \
nettle.texinfo nettle.info nettle.html nettle.pdf sha-example.c
diff --git a/dsa-compute-k.c b/dsa-compute-k.c
new file mode 100644
index 00000000..105c500b
--- /dev/null
+++ b/dsa-compute-k.c
@@ -0,0 +1,179 @@
+/* dsa-compute-k.c
+
+ Deterministically find k value for ECDSA/DSA (RFC-6979).
+
+ 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 "dsa-compute-k.h"
+
+#include "gmp-glue.h"
+#include "nettle-internal.h"
+#include <string.h>
+#include <stdio.h>
+
+#define MIN(x, y) ((x) < (y) ? (x) : (y))
+#define MAX(x, y) ((x) > (y) ? (x) : (y))
+
+void
+_dsa_compute_k (mp_limb_t *k,
+ mp_size_t qn,
+ const mp_limb_t *q,
+ const mp_limb_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)
+{
+ TMP_DECL(V, uint8_t, NETTLE_MAX_HASH_DIGEST_SIZE);
+ TMP_DECL(K, uint8_t, NETTLE_MAX_HASH_DIGEST_SIZE);
+ TMP_GMP_DECL(xp, uint8_t);
+ TMP_GMP_DECL(hp, uint8_t);
+ TMP_GMP_DECL(tp, uint8_t);
+ TMP_GMP_DECL(h, mp_limb_t);
+ mp_size_t hn = (digest_length + sizeof(mp_limb_t) - 1) / sizeof(mp_limb_t);
+ mp_bitcnt_t q_bits = mpn_sizeinbase (q, qn, 2);
+ mp_bitcnt_t h_bits = digest_length * 8;
+ size_t nbytes = (q_bits + 7) / 8;
+ const uint8_t c0 = 0x00;
+ const uint8_t c1 = 0x01;
+ mp_limb_t cy;
+
+ TMP_ALLOC(V, digest_length);
+ TMP_ALLOC(K, digest_length);
+ TMP_GMP_ALLOC(xp, nbytes);
+ TMP_GMP_ALLOC(hp, nbytes);
+ TMP_GMP_ALLOC(tp, nbytes);
+ TMP_GMP_ALLOC(h, MAX (qn, hn) * sizeof(mp_limb_t));
+
+ /* int2octets(x) */
+ mpn_get_base256 (xp, nbytes, x, qn);
+
+ /* bits2octets(h) */
+ mpn_set_base256 (h, hn, digest_message, digest_length);
+
+ if (hn < qn)
+ /* qlen > blen: add zero bits to the left */
+ mpn_zero (&h[hn], qn - hn);
+ else if (h_bits > q_bits)
+ {
+ /* qlen < blen: keep the leftmost qlen bits. We do this in 2
+ * steps because mpn_rshift only accepts shift count in the
+ * range 1 to mp_bits_per_limb-1.
+ */
+ mp_bitcnt_t shift = h_bits - q_bits;
+
+ if (shift / GMP_LIMB_BITS > 0)
+ {
+ mpn_copyi (h, &h[shift / GMP_LIMB_BITS], qn);
+ hn -= shift / GMP_LIMB_BITS;
+ }
+
+ if (shift % GMP_LIMB_BITS > 0)
+ mpn_rshift (h, h, hn, shift % GMP_LIMB_BITS);
+ }
+
+ cy = mpn_sub_n (h, h, q, qn);
+ cy = cnd_add_n (cy, h, q, qn);
+ mpn_get_base256 (hp, nbytes, h, qn);
+
+ /* Step b */
+ memset (V, c1, digest_length);
+
+ /* Step c */
+ memset (K, c0, digest_length);
+ set_key (mac_ctx, digest_length, K);
+
+ /* Step d */
+ update (mac_ctx, digest_length, V);
+ update (mac_ctx, 1, &c0);
+ update (mac_ctx, nbytes, xp);
+ update (mac_ctx, nbytes, hp);
+ digest (mac_ctx, digest_length, K);
+ set_key (mac_ctx, digest_length, K);
+
+ /* Step e */
+ update (mac_ctx, digest_length, V);
+ digest (mac_ctx, digest_length, V);
+
+ /* Step f */
+ update (mac_ctx, digest_length, V);
+ update (mac_ctx, 1, &c1);
+ update (mac_ctx, nbytes, xp);
+ update (mac_ctx, nbytes, hp);
+ digest (mac_ctx, digest_length, K);
+ set_key (mac_ctx, digest_length, K);
+
+ /* Step g */
+ update (mac_ctx, digest_length, V);
+ digest (mac_ctx, digest_length, V);
+
+ /* Step h */
+ for (;;)
+ {
+ /* Step 1 */
+ size_t tlen = 0;
+
+ /* Step 2 */
+ while (tlen < nbytes)
+ {
+ size_t remaining = MIN(nbytes - tlen, digest_length);
+ update (mac_ctx, digest_length, V);
+ digest (mac_ctx, digest_length, V);
+ memcpy (&tp[tlen], V, remaining);
+ tlen += remaining;
+ }
+
+ /* Step 3 */
+ mpn_set_base256 (k, qn, tp, tlen);
+ if (tlen * 8 > q_bits)
+ mpn_rshift (k, k, qn, tlen * 8 - q_bits);
+ /* Check if k is in [1,q-1] */
+ if (!mpn_zero_p (k, qn) && mpn_cmp (k, q, qn) < 0)
+ break;
+
+ update (mac_ctx, digest_length, V);
+ update (mac_ctx, 1, &c0);
+ digest (mac_ctx, digest_length, K);
+ set_key (mac_ctx, digest_length, K);
+ update (mac_ctx, digest_length, V);
+ digest (mac_ctx, digest_length, V);
+ }
+
+ TMP_GMP_FREE(xp);
+ TMP_GMP_FREE(hp);
+ TMP_GMP_FREE(tp);
+ TMP_GMP_FREE(h);
+}
diff --git a/dsa-compute-k.h b/dsa-compute-k.h
new file mode 100644
index 00000000..3433e2fb
--- /dev/null
+++ b/dsa-compute-k.h
@@ -0,0 +1,63 @@
+/* dsa-compute-k.h
+
+ Deterministically find k value for ECDSA/DSA (RFC-6979).
+
+ 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/.
+*/
+
+#ifndef NETTLE_DSA_COMPUTE_K_H_INCLUDED
+#define NETTLE_DSA_COMPUTE_K_H_INCLUDED
+
+#include "nettle-types.h"
+#include "bignum.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* Namespace mangling */
+#define _dsa_compute_k _nettle_dsa_compute_k
+
+void
+_dsa_compute_k (mp_limb_t *k,
+ mp_size_t qn,
+ const mp_limb_t *q,
+ const mp_limb_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);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* NETTLE_DSA_COMPUTE_K_H_INCLUDED */
diff --git a/testsuite/.gitignore b/testsuite/.gitignore
index 066bcee2..40fbe046 100644
--- a/testsuite/.gitignore
+++ b/testsuite/.gitignore
@@ -22,6 +22,7 @@
/des-test
/des3-test
/dlopen-test
+/dsa-compute-k-test
/dsa-keygen-test
/dsa-test
/eax-test
diff --git a/testsuite/.test-rules.make b/testsuite/.test-rules.make
index efb7df3c..61080010 100644
--- a/testsuite/.test-rules.make
+++ b/testsuite/.test-rules.make
@@ -280,6 +280,9 @@ eddsa-verify-test$(EXEEXT): eddsa-verify-test.$(OBJEXT)
ed25519-test$(EXEEXT): ed25519-test.$(OBJEXT)
$(LINK) ed25519-test.$(OBJEXT) $(TEST_OBJS) -o ed25519-test$(EXEEXT)
+dsa-compute-k-test$(EXEEXT): dsa-compute-k-test.$(OBJEXT)
+ $(LINK) dsa-compute-k-test.$(OBJEXT) $(TEST_OBJS) -o
dsa-compute-k-test$(EXEEXT)
+
sha1-huge-test$(EXEEXT): sha1-huge-test.$(OBJEXT)
$(LINK) sha1-huge-test.$(OBJEXT) $(TEST_OBJS) -o sha1-huge-test$(EXEEXT)
diff --git a/testsuite/Makefile.in b/testsuite/Makefile.in
index f8f85701..e6acd788 100644
--- a/testsuite/Makefile.in
+++ b/testsuite/Makefile.in
@@ -52,7 +52,8 @@ TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \
ecdsa-sign-test.c ecdsa-verify-test.c \
ecdsa-keygen-test.c ecdh-test.c \
eddsa-compress-test.c eddsa-sign-test.c \
- eddsa-verify-test.c ed25519-test.c
+ eddsa-verify-test.c ed25519-test.c \
+ dsa-compute-k-test.c
TS_SOURCES = $(TS_NETTLE_SOURCES) $(TS_HOGWEED_SOURCES)
CXX_SOURCES = cxx-test.cxx
diff --git a/testsuite/dsa-compute-k-test.c b/testsuite/dsa-compute-k-test.c
new file mode 100644
index 00000000..3df9b2e8
--- /dev/null
+++ b/testsuite/dsa-compute-k-test.c
@@ -0,0 +1,127 @@
+#include "testutils.h"
+#include "dsa-compute-k.h"
+#include "hmac.h"
+
+#if HAVE_VALGRIND_MEMCHECK_H
+# include <valgrind/memcheck.h>
+
+static nettle_hash_digest_func *digest_func;
+
+static void
+digest_func_for_test(void *ctx,
+ size_t length, uint8_t *dst)
+{
+ digest_func (ctx, length, dst);
+ VALGRIND_MAKE_MEM_DEFINED (dst, length);
+}
+
+static void
+_dsa_compute_k_for_test (mp_limb_t *k,
+ mp_size_t qn,
+ const mp_limb_t *q,
+ const mp_limb_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)
+{
+ /* Makes valgrind trigger on any branches depending on the input
+ data. */
+ VALGRIND_MAKE_MEM_UNDEFINED (x, qn * sizeof(mp_limb_t));
+ VALGRIND_MAKE_MEM_UNDEFINED (digest_message, digest_length);
+
+ digest_func = digest;
+ _dsa_compute_k (k, qn, q, x, mac_ctx, set_key, update, digest_func_for_test,
+ digest_length, digest_message);
+
+ VALGRIND_MAKE_MEM_DEFINED (x, qn * sizeof(mp_limb_t));
+ VALGRIND_MAKE_MEM_DEFINED (digest_message, digest_length);
+ VALGRIND_MAKE_MEM_DEFINED (k, qn * sizeof(mp_limb_t));
+}
+#else
+#define _dsa_compute_k_test _dsa_compute_k
+#endif
+
+static void
+test_dsa_compute_k(const char *sq,
+ /* Private key */
+ const char *sx,
+ /* 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 k */
+ const char *sk)
+{
+ mpz_t k;
+ mpz_t q;
+ mpz_t x;
+ mpz_t e;
+
+ mpz_init (k);
+ mpz_init_set_str (q, sq, 16);
+ mpz_init_set_str (x, sx, 16);
+ mpz_init_set_str (e, sk, 16);
+
+ _dsa_compute_k_for_test (mpz_limbs_write (k, mpz_size (q)),
+ mpz_size (q), mpz_limbs_read (q), mpz_limbs_read (x),
+ mac_ctx, set_key, update, digest,
+ h->length, h->data);
+
+ mpz_limbs_finish (k, mpz_size (q));
+
+ if (mpz_cmp (e, k) != 0)
+ {
+ fprintf (stderr, "k = ");
+ mpz_out_str (stderr, 16, k);
+ fprintf (stderr, "\n");
+ fprintf (stderr, "e = ");
+ mpz_out_str (stderr, 16, e);
+ fprintf (stderr, "\n");
+ abort ();
+ }
+
+ mpz_clear (q);
+ mpz_clear (x);
+ mpz_clear (k);
+ mpz_clear (e);
+}
+
+void
+test_main (void)
+{
+ struct hmac_sha256_ctx hmac;
+ struct sha256_ctx hash;
+ uint8_t digest[SHA256_DIGEST_SIZE];
+
+ sha256_init (&hash);
+ sha256_update (&hash, 6, (const uint8_t *)"sample");
+ sha256_digest (&hash, sizeof(digest), digest);
+
+ /* Test vectors from RFC 6979 */
+ test_dsa_compute_k ("996f967f6c8e388d9e28d01e205fba957a5698b1",
+ "411602cb19a6ccc34494d79d98ef1e7ed5af25f7",
+ &hmac,
+ (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),
+ "519ba0546d0c39202a7d34d7dfa5e760b318bcfb");
+
+ test_dsa_compute_k ("f2c3119374ce76c9356990b465374a17f23f9ed3"
+ "5089bd969f61c6dde9998c1f",
+ "69c7548c21d0dfea6b9a51c9ead4e27c33d3b3f1"
+ "80316e5bcab92c933f0e4dbc",
+ &hmac,
+ (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),
+ "8926a27c40484216f052f4427cfd5647338b7b39"
+ "39bc6573af4333569d597c52");
+}
--
2.21.0
_______________________________________________
nettle-bugs mailing list
nettle-bugs@lists.lysator.liu.se
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
