From ff26efb1c4b8530024dc9b42d75e39536ece6e11 Mon Sep 17 00:00:00 2001
From: lloyd <lloyd@randombit.net>
Date: Thu, 12 Mar 2015 11:48:27 +0000
Subject: Externalize the state of a RFC 6979 nonce computation.

This lets you amortize quite a few memory allocations (RNG, various
BigInts, etc) over many nonce generations.

Change generate_rfc6979_nonce to just instantiate one of these states,
call the function once, and return. This doesn't have any additional
overhead versus the previous implementation of this function.

Fix HMAC_DRBG to correctly reset its state to its starting position
when you call clear() on it.
---
 src/lib/pubkey/rfc6979/rfc6979.cpp | 53 +++++++++++++++++++++++---------------
 src/lib/pubkey/rfc6979/rfc6979.h   | 24 ++++++++++++++++-
 2 files changed, 55 insertions(+), 22 deletions(-)

(limited to 'src/lib/pubkey/rfc6979')

diff --git a/src/lib/pubkey/rfc6979/rfc6979.cpp b/src/lib/pubkey/rfc6979/rfc6979.cpp
index 3bd723d6d..58cdbaa1b 100644
--- a/src/lib/pubkey/rfc6979/rfc6979.cpp
+++ b/src/lib/pubkey/rfc6979/rfc6979.cpp
@@ -1,6 +1,6 @@
 /*
 * RFC 6979 Deterministic Nonce Generator
-* (C) 2014 Jack Lloyd
+* (C) 2014,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -25,32 +25,43 @@ std::string hash_for_deterministic_signature(const std::string& emsa)
    return "SHA-512"; // safe default if nothing we understand
    }
 
-BigInt generate_rfc6979_nonce(const BigInt& x,
-                              const BigInt& q,
-                              const BigInt& h,
-                              const std::string& hash)
+RFC6979_Nonce_Generator::RFC6979_Nonce_Generator(const std::string& hash,
+                                                 const BigInt& order,
+                                                 const BigInt& x) :
+   m_order(order),
+   m_qlen(m_order.bits()),
+   m_rlen(m_qlen / 8 + (m_qlen % 8 ? 1 : 0)),
+   m_hmac_drbg(new HMAC_DRBG(make_message_auth("HMAC(" + hash + ")").release())),
+   m_rng_in(m_rlen * 2),
+   m_rng_out(m_rlen)
    {
-   HMAC_DRBG rng(make_message_auth("HMAC(" + hash + ")").release(), nullptr);
-
-   const size_t qlen = q.bits();
-   const size_t rlen = qlen / 8 + (qlen % 8 ? 1 : 0);
-
-   secure_vector<byte> input = BigInt::encode_1363(x, rlen);
-
-   input += BigInt::encode_1363(h, rlen);
-
-   rng.add_entropy(&input[0], input.size());
-
-   BigInt k;
+   BigInt::encode_1363(&m_rng_in[0], m_rlen, x);
+   }
 
-   secure_vector<byte> kbits(rlen);
+const BigInt& RFC6979_Nonce_Generator::nonce_for(const BigInt& m)
+   {
+   BigInt::encode_1363(&m_rng_in[m_rlen], m_rlen, m);
+   m_hmac_drbg->clear();
+   m_hmac_drbg->add_entropy(&m_rng_in[0], m_rng_in.size());
 
-   while(k == 0 || k >= q)
+   do
       {
-      rng.randomize(&kbits[0], kbits.size());
-      k = BigInt::decode(kbits) >> (8*rlen - qlen);
+      m_hmac_drbg->randomize(&m_rng_out[0], m_rng_out.size());
+      m_k.binary_decode(&m_rng_out[0], m_rng_out.size());
+      m_k >>= (8*m_rlen - m_qlen);
       }
+   while(m_k == 0 || m_k >= m_order);
 
+   return m_k;
+   }
+
+BigInt generate_rfc6979_nonce(const BigInt& x,
+                              const BigInt& q,
+                              const BigInt& h,
+                              const std::string& hash)
+   {
+   RFC6979_Nonce_Generator gen(hash, q, x);
+   BigInt k = gen.nonce_for(h);
    return k;
    }
 
diff --git a/src/lib/pubkey/rfc6979/rfc6979.h b/src/lib/pubkey/rfc6979/rfc6979.h
index 8e2940578..5b3dee8ef 100644
--- a/src/lib/pubkey/rfc6979/rfc6979.h
+++ b/src/lib/pubkey/rfc6979/rfc6979.h
@@ -1,6 +1,6 @@
 /*
 * RFC 6979 Deterministic Nonce Generator
-* (C) 2014 Jack Lloyd
+* (C) 2014,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -10,9 +10,31 @@
 
 #include <botan/bigint.h>
 #include <string>
+#include <memory>
 
 namespace Botan {
 
+class RandomNumberGenerator;
+
+class BOTAN_DLL RFC6979_Nonce_Generator
+   {
+   public:
+      /**
+      * Note: keeps persistent reference to order
+      */
+      RFC6979_Nonce_Generator(const std::string& hash,
+                              const BigInt& order,
+                              const BigInt& x);
+
+      const BigInt& nonce_for(const BigInt& m);
+   private:
+      const BigInt& m_order;
+      BigInt m_k;
+      size_t m_qlen, m_rlen;
+      std::unique_ptr<RandomNumberGenerator> m_hmac_drbg;
+      secure_vector<byte> m_rng_in, m_rng_out;
+   };
+
 /**
 * @param x the secret (EC)DSA key
 * @param q the group order
-- 
cgit v1.2.3