Implement RFC 6979 determinstic signatures for DSA and ECDSA.

Drop the GNU MP engine. Its implementations were potentially faster in
some scenarios but not well protected against side channels.

23 files changed, 85 insertions, 746 deletions

diff --git a/src/lib/engine/core_engine/core_engine.h b/src/lib/engine/core_engine/core_engine.h
index ca660d21b..d12895662 100644
--- a/src/lib/engine/core_engine/core_engine.h
+++ b/src/lib/engine/core_engine/core_engine.h
@@ -23,10 +23,11 @@ class Core_Engine : public Engine
       PK_Ops::Key_Agreement*
          get_key_agreement_op(const Private_Key& key, RandomNumberGenerator& rng) const override;
 
-      PK_Ops::Signature*
-         get_signature_op(const Private_Key& key, RandomNumberGenerator& rng) const override;
+      PK_Ops::Signature* get_signature_op(const Private_Key& key, const std::string& emsa,
+                                          RandomNumberGenerator& rng) const override;
 
-      PK_Ops::Verification* get_verify_op(const Public_Key& key, RandomNumberGenerator& rng) const override;
+      PK_Ops::Verification* get_verify_op(const Public_Key& key, const std::string& emsa,
+                                          RandomNumberGenerator& rng) const override;
 
       PK_Ops::Encryption* get_encryption_op(const Public_Key& key, RandomNumberGenerator& rng) const override;
 
diff --git a/src/lib/engine/core_engine/def_pk_ops.cpp b/src/lib/engine/core_engine/def_pk_ops.cpp
index e99945633..b21877b16 100644
--- a/src/lib/engine/core_engine/def_pk_ops.cpp
+++ b/src/lib/engine/core_engine/def_pk_ops.cpp
@@ -94,7 +94,7 @@ Core_Engine::get_key_agreement_op(const Private_Key& key, RandomNumberGenerator&
    }
 
 PK_Ops::Signature*
-Core_Engine::get_signature_op(const Private_Key& key, RandomNumberGenerator& rng) const
+Core_Engine::get_signature_op(const Private_Key& key, const std::string& emsa, RandomNumberGenerator& rng) const
    {
 #if defined(BOTAN_HAS_RSA)
    if(const RSA_PrivateKey* s = dynamic_cast<const RSA_PrivateKey*>(&key))
@@ -108,12 +108,12 @@ Core_Engine::get_signature_op(const Private_Key& key, RandomNumberGenerator& rng
 
 #if defined(BOTAN_HAS_DSA)
    if(const DSA_PrivateKey* s = dynamic_cast<const DSA_PrivateKey*>(&key))
-      return new DSA_Signature_Operation(*s);
+      return new DSA_Signature_Operation(*s, emsa);
 #endif
 
 #if defined(BOTAN_HAS_ECDSA)
    if(const ECDSA_PrivateKey* s = dynamic_cast<const ECDSA_PrivateKey*>(&key))
-      return new ECDSA_Signature_Operation(*s);
+      return new ECDSA_Signature_Operation(*s, emsa);
 #endif
 
 #if defined(BOTAN_HAS_GOST_34_10_2001)
@@ -131,7 +131,7 @@ Core_Engine::get_signature_op(const Private_Key& key, RandomNumberGenerator& rng
    }
 
 PK_Ops::Verification*
-Core_Engine::get_verify_op(const Public_Key& key, RandomNumberGenerator&) const
+Core_Engine::get_verify_op(const Public_Key& key, const std::string& emsa, RandomNumberGenerator&) const
    {
 #if defined(BOTAN_HAS_RSA)
    if(const RSA_PublicKey* s = dynamic_cast<const RSA_PublicKey*>(&key))
diff --git a/src/lib/engine/dyn_engine/dyn_engine.h b/src/lib/engine/dyn_engine/dyn_engine.h
index 39e13ab36..a9671b5b5 100644
--- a/src/lib/engine/dyn_engine/dyn_engine.h
+++ b/src/lib/engine/dyn_engine/dyn_engine.h
@@ -82,15 +82,15 @@ class BOTAN_DLL Dynamically_Loaded_Engine : public Engine
          }
 
       PK_Ops::Signature*
-         get_signature_op(const Private_Key& key, RandomNumberGenerator& rng) const override
+         get_signature_op(const Private_Key& key, const std::string& emsa, RandomNumberGenerator& rng) const override
          {
-         return engine->get_signature_op(key, rng);
+         return engine->get_signature_op(key, emsa, rng);
          }
 
       PK_Ops::Verification*
-         get_verify_op(const Public_Key& key, RandomNumberGenerator& rng) const override
+         get_verify_op(const Public_Key& key, const std::string& emsa, RandomNumberGenerator& rng) const override
          {
-         return engine->get_verify_op(key, rng);
+         return engine->get_verify_op(key, emsa, rng);
          }
 
       PK_Ops::Encryption*
diff --git a/src/lib/engine/engine.cpp b/src/lib/engine/engine.cpp
index a50f1e7b2..bfb08ec91 100644
--- a/src/lib/engine/engine.cpp
+++ b/src/lib/engine/engine.cpp
@@ -65,13 +65,13 @@ Engine::get_key_agreement_op(const Private_Key&, RandomNumberGenerator&) const
    }
 
 PK_Ops::Signature*
-Engine::get_signature_op(const Private_Key&, RandomNumberGenerator&) const
+Engine::get_signature_op(const Private_Key&, const std::string&, RandomNumberGenerator&) const
    {
    return nullptr;
    }
 
 PK_Ops::Verification*
-Engine::get_verify_op(const Public_Key&, RandomNumberGenerator&) const
+Engine::get_verify_op(const Public_Key&, const std::string&, RandomNumberGenerator&) const
    {
    return nullptr;
    }
diff --git a/src/lib/engine/engine.h b/src/lib/engine/engine.h
index a03a6e1ec..9774a941f 100644
--- a/src/lib/engine/engine.h
+++ b/src/lib/engine/engine.h
@@ -118,7 +118,7 @@ class BOTAN_DLL Engine
       * @return newly allocated operator object, or NULL
       */
       virtual PK_Ops::Signature*
-         get_signature_op(const Private_Key& key, RandomNumberGenerator& rng) const;
+         get_signature_op(const Private_Key& key, const std::string& hash, RandomNumberGenerator& rng) const;
 
       /**
       * Return a new operator object for this key, if possible
@@ -126,7 +126,7 @@ class BOTAN_DLL Engine
       * @return newly allocated operator object, or NULL
       */
       virtual PK_Ops::Verification*
-         get_verify_op(const Public_Key& key, RandomNumberGenerator& rng) const;
+         get_verify_op(const Public_Key& key, const std::string& hash, RandomNumberGenerator& rng) const;
 
       /**
       * Return a new operator object for this key, if possible
diff --git a/src/lib/engine/gnump/gmp_mem.cpp b/src/lib/engine/gnump/gmp_mem.cpp
deleted file mode 100644
index b5a5a303e..000000000
--- a/src/lib/engine/gnump/gmp_mem.cpp
+++ /dev/null
@@ -1,83 +0,0 @@
-/*
-* GNU MP Memory Handlers
-* (C) 1999-2010 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#include <botan/internal/gnump_engine.h>
-#include <cstring>
-#include <atomic>
-#include <gmp.h>
-
-namespace Botan {
-
-namespace {
-
-/*
-* For keeping track of existing GMP_Engines and only
-* resetting the memory when none are in use.
-*/
-std::atomic<size_t> gmp_alloc_refcnt(0);
-
-/*
-* Allocation Function for GNU MP
-*/
-void* gmp_malloc(size_t n)
-   {
-   // Maintain alignment, mlock goes for sizeof(T) alignment
-   if(n % 8 == 0)
-      return secure_allocator<u64bit>().allocate(n / 8);
-   else if(n % 4 == 0)
-      return secure_allocator<u32bit>().allocate(n / 4);
-   else if(n % 2 == 0)
-      return secure_allocator<u16bit>().allocate(n / 2);
-
-   return secure_allocator<byte>().allocate(n);
-   }
-
-/*
-* Deallocation Function for GNU MP
-*/
-void gmp_free(void* ptr, size_t n)
-   {
-   secure_allocator<byte>().deallocate(static_cast<byte*>(ptr), n);
-   }
-
-/*
-* Reallocation Function for GNU MP
-*/
-void* gmp_realloc(void* ptr, size_t old_n, size_t new_n)
-   {
-   void* new_buf = gmp_malloc(new_n);
-   std::memcpy(new_buf, ptr, std::min(old_n, new_n));
-   gmp_free(ptr, old_n);
-   return new_buf;
-   }
-
-}
-
-/*
-* GMP_Engine Constructor
-*/
-GMP_Engine::GMP_Engine()
-   {
-   /*
-   if(gmp_alloc_refcnt == 0)
-      mp_set_memory_functions(gmp_malloc, gmp_realloc, gmp_free);
-
-   gmp_alloc_refcnt++;
-   */
-   }
-
-GMP_Engine::~GMP_Engine()
-   {
-   /*
-   --gmp_alloc_refcnt;
-
-   if(gmp_alloc_refcnt == 0)
-      mp_set_memory_functions(NULL, NULL, NULL);
-   */
-   }
-
-}
diff --git a/src/lib/engine/gnump/gmp_powm.cpp b/src/lib/engine/gnump/gmp_powm.cpp
deleted file mode 100644
index 70c2b2f5e..000000000
--- a/src/lib/engine/gnump/gmp_powm.cpp
+++ /dev/null
@@ -1,53 +0,0 @@
-/*
-* GMP Modular Exponentiation
-* (C) 1999-2007 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#include <botan/internal/gnump_engine.h>
-#include <botan/internal/gmp_wrap.h>
-
-namespace Botan {
-
-namespace {
-
-/*
-* GMP Modular Exponentiator
-*/
-class GMP_Modular_Exponentiator : public Modular_Exponentiator
-   {
-   public:
-      void set_base(const BigInt& b) { base = b; }
-      void set_exponent(const BigInt& e) { exp = e; }
-      BigInt execute() const;
-      Modular_Exponentiator* copy() const
-         { return new GMP_Modular_Exponentiator(*this); }
-
-      GMP_Modular_Exponentiator(const BigInt& n) : mod(n) {}
-   private:
-      GMP_MPZ base, exp, mod;
-   };
-
-/*
-* Compute the result
-*/
-BigInt GMP_Modular_Exponentiator::execute() const
-   {
-   GMP_MPZ r;
-   mpz_powm(r.value, base.value, exp.value, mod.value);
-   return r.to_bigint();
-   }
-
-}
-
-/*
-* Return the GMP-based modular exponentiator
-*/
-Modular_Exponentiator* GMP_Engine::mod_exp(const BigInt& n,
-                                           Power_Mod::Usage_Hints) const
-   {
-   return new GMP_Modular_Exponentiator(n);
-   }
-
-}
diff --git a/src/lib/engine/gnump/gmp_wrap.cpp b/src/lib/engine/gnump/gmp_wrap.cpp
deleted file mode 100644
index 974593d02..000000000
--- a/src/lib/engine/gnump/gmp_wrap.cpp
+++ /dev/null
@@ -1,101 +0,0 @@
-/*
-* GMP Wrapper
-* (C) 1999-2007 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#include <botan/internal/gmp_wrap.h>
-
-#define GNU_MP_VERSION_CODE_FOR(a,b,c) ((a << 16) | (b << 8) | (c))
-
-#define GNU_MP_VERSION_CODE \
-   GNU_MP_VERSION_CODE_FOR(__GNU_MP_VERSION, __GNU_MP_VERSION_MINOR, \
-                           __GNU_MP_VERSION_PATCHLEVEL)
-
-#if GNU_MP_VERSION_CODE < GNU_MP_VERSION_CODE_FOR(4,1,0)
-  #error Your GNU MP install is too old, upgrade to 4.1 or later
-#endif
-
-namespace Botan {
-
-/*
-* GMP_MPZ Constructor
-*/
-GMP_MPZ::GMP_MPZ(const BigInt& in)
-   {
-   mpz_init(value);
-   if(in != 0)
-      mpz_import(value, in.sig_words(), -1, sizeof(word), 0, 0, in.data());
-   }
-
-/*
-* GMP_MPZ Constructor
-*/
-GMP_MPZ::GMP_MPZ(const byte in[], size_t length)
-   {
-   mpz_init(value);
-   mpz_import(value, length, 1, 1, 0, 0, in);
-   }
-
-/*
-* GMP_MPZ Copy Constructor
-*/
-GMP_MPZ::GMP_MPZ(const GMP_MPZ& other)
-   {
-   mpz_init_set(value, other.value);
-   }
-
-/*
-* GMP_MPZ Destructor
-*/
-GMP_MPZ::~GMP_MPZ()
-   {
-   mpz_clear(value);
-   }
-
-/*
-* GMP_MPZ Assignment Operator
-*/
-GMP_MPZ& GMP_MPZ::operator=(const GMP_MPZ& other)
-   {
-   mpz_set(value, other.value);
-   return (*this);
-   }
-
-/*
-* Export the mpz_t as a bytestring
-*/
-void GMP_MPZ::encode(byte out[], size_t length) const
-   {
-   size_t dummy = 0;
-   mpz_export(out + (length - bytes()), &dummy, 1, 1, 0, 0, value);
-   }
-
-/*
-* Return the number of significant bytes
-*/
-size_t GMP_MPZ::bytes() const
-   {
-   return ((mpz_sizeinbase(value, 2) + 7) / 8);
-   }
-
-/*
-* GMP to BigInt Conversions
-*/
-BigInt GMP_MPZ::to_bigint() const
-   {
-   BigInt out(BigInt::Positive, (bytes() + sizeof(word) - 1) / sizeof(word));
-   size_t dummy = 0;
-
-   word* reg = out.mutable_data();
-
-   mpz_export(reg, &dummy, -1, sizeof(word), 0, 0, value);
-
-   if(mpz_sgn(value) < 0)
-      out.flip_sign();
-
-   return out;
-   }
-
-}
diff --git a/src/lib/engine/gnump/gmp_wrap.h b/src/lib/engine/gnump/gmp_wrap.h
deleted file mode 100644
index 291d65a01..000000000
--- a/src/lib/engine/gnump/gmp_wrap.h
+++ /dev/null
@@ -1,41 +0,0 @@
-/*
-* GMP MPZ Wrapper
-* (C) 1999-2007 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#ifndef BOTAN_GMP_MPZ_WRAP_H__
-#define BOTAN_GMP_MPZ_WRAP_H__
-
-#include <botan/bigint.h>
-#include <gmp.h>
-
-namespace Botan {
-
-/**
-* Lightweight GMP mpz_t wrapper. For internal use only.
-*/
-class GMP_MPZ
-   {
-   public:
-      mpz_t value;
-
-      BigInt to_bigint() const;
-      void encode(byte[], size_t) const;
-      size_t bytes() const;
-
-      secure_vector<byte> to_bytes() const
-         { return BigInt::encode_locked(to_bigint()); }
-
-      GMP_MPZ& operator=(const GMP_MPZ&);
-
-      GMP_MPZ(const GMP_MPZ&);
-      GMP_MPZ(const BigInt& = 0);
-      GMP_MPZ(const byte[], size_t);
-      ~GMP_MPZ();
-   };
-
-}
-
-#endif
diff --git a/src/lib/engine/gnump/gnump_engine.h b/src/lib/engine/gnump/gnump_engine.h
deleted file mode 100644
index ccc723514..000000000
--- a/src/lib/engine/gnump/gnump_engine.h
+++ /dev/null
@@ -1,44 +0,0 @@
-/*
-* GMP Engine
-* (C) 1999-2007 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#ifndef BOTAN_ENGINE_GMP_H__
-#define BOTAN_ENGINE_GMP_H__
-
-#include <botan/engine.h>
-
-namespace Botan {
-
-/**
-* Engine using GNU MP
-*/
-class GMP_Engine : public Engine
-   {
-   public:
-      GMP_Engine();
-      ~GMP_Engine();
-
-      std::string provider_name() const override { return "gmp"; }
-
-      PK_Ops::Key_Agreement*
-      get_key_agreement_op(const Private_Key& key, RandomNumberGenerator&) const override;
-
-      PK_Ops::Signature*
-      get_signature_op(const Private_Key& key, RandomNumberGenerator&) const override;
-
-      PK_Ops::Verification* get_verify_op(const Public_Key& key, RandomNumberGenerator&) const override;
-
-      PK_Ops::Encryption* get_encryption_op(const Public_Key& key, RandomNumberGenerator&) const override;
-
-      PK_Ops::Decryption* get_decryption_op(const Private_Key& key, RandomNumberGenerator&) const override;
-
-      Modular_Exponentiator* mod_exp(const BigInt&,
-                                     Power_Mod::Usage_Hints) const override;
-   };
-
-}
-
-#endif
diff --git a/src/lib/engine/gnump/gnump_pk.cpp b/src/lib/engine/gnump/gnump_pk.cpp
deleted file mode 100644
index 29e172d47..000000000
--- a/src/lib/engine/gnump/gnump_pk.cpp
+++ /dev/null
@@ -1,338 +0,0 @@
-/*
-* GnuMP PK operations
-* (C) 1999-2010 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#include <botan/internal/gnump_engine.h>
-#include <botan/internal/gmp_wrap.h>
-#include <gmp.h>
-
-/* GnuMP 5.0 and later have a side-channel resistent powm */
-#if defined(HAVE_MPZ_POWM_SEC)
-   #undef mpz_powm
-   #define mpz_powm mpz_powm_sec
-#endif
-
-#if defined(BOTAN_HAS_RSA)
-  #include <botan/rsa.h>
-#endif
-
-#if defined(BOTAN_HAS_DSA)
-  #include <botan/dsa.h>
-#endif
-
-#if defined(BOTAN_HAS_DIFFIE_HELLMAN)
-  #include <botan/dh.h>
-#endif
-
-namespace Botan {
-
-namespace {
-
-#if defined(BOTAN_HAS_DIFFIE_HELLMAN)
-class GMP_DH_KA_Operation : public PK_Ops::Key_Agreement
-   {
-   public:
-      GMP_DH_KA_Operation(const DH_PrivateKey& dh) :
-         x(dh.get_x()), p(dh.group_p()) {}
-
-      secure_vector<byte> agree(const byte w[], size_t w_len)
-         {
-         GMP_MPZ z(w, w_len);
-         mpz_powm(z.value, z.value, x.value, p.value);
-         return z.to_bytes();
-         }
-
-   private:
-      GMP_MPZ x, p;
-   };
-#endif
-
-#if defined(BOTAN_HAS_DSA)
-
-class GMP_DSA_Signature_Operation : public PK_Ops::Signature
-   {
-   public:
-      GMP_DSA_Signature_Operation(const DSA_PrivateKey& dsa) :
-         x(dsa.get_x()),
-         p(dsa.group_p()),
-         q(dsa.group_q()),
-         g(dsa.group_g()),
-         q_bits(dsa.group_q().bits()) {}
-
-      size_t message_parts() const { return 2; }
-      size_t message_part_size() const { return (q_bits + 7) / 8; }
-      size_t max_input_bits() const { return q_bits; }
-
-      secure_vector<byte> sign(const byte msg[], size_t msg_len,
-                              RandomNumberGenerator& rng);
-   private:
-      const GMP_MPZ x, p, q, g;
-      size_t q_bits;
-   };
-
-secure_vector<byte>
-GMP_DSA_Signature_Operation::sign(const byte msg[], size_t msg_len,
-                                  RandomNumberGenerator& rng)
-   {
-   const size_t q_bytes = (q_bits + 7) / 8;
-
-   rng.add_entropy(msg, msg_len);
-
-   BigInt k_bn;
-   do
-      k_bn.randomize(rng, q_bits);
-   while(k_bn >= q.to_bigint());
-
-   GMP_MPZ i(msg, msg_len);
-   GMP_MPZ k(k_bn);
-
-   GMP_MPZ r;
-   mpz_powm(r.value, g.value, k.value, p.value);
-   mpz_mod(r.value, r.value, q.value);
-
-   mpz_invert(k.value, k.value, q.value);
-
-   GMP_MPZ s;
-   mpz_mul(s.value, x.value, r.value);
-   mpz_add(s.value, s.value, i.value);
-   mpz_mul(s.value, s.value, k.value);
-   mpz_mod(s.value, s.value, q.value);
-
-   if(mpz_cmp_ui(r.value, 0) == 0 || mpz_cmp_ui(s.value, 0) == 0)
-      throw Internal_Error("GMP_DSA_Op::sign: r or s was zero");
-
-   secure_vector<byte> output(2*q_bytes);
-   r.encode(&output[0], q_bytes);
-   s.encode(&output[q_bytes], q_bytes);
-   return output;
-   }
-
-class GMP_DSA_Verification_Operation : public PK_Ops::Verification
-   {
-   public:
-      GMP_DSA_Verification_Operation(const DSA_PublicKey& dsa) :
-         y(dsa.get_y()),
-         p(dsa.group_p()),
-         q(dsa.group_q()),
-         g(dsa.group_g()),
-         q_bits(dsa.group_q().bits()) {}
-
-      size_t message_parts() const { return 2; }
-      size_t message_part_size() const { return (q_bits + 7) / 8; }
-      size_t max_input_bits() const { return q_bits; }
-
-      bool with_recovery() const { return false; }
-
-      bool verify(const byte msg[], size_t msg_len,
-                  const byte sig[], size_t sig_len);
-   private:
-      const GMP_MPZ y, p, q, g;
-      size_t q_bits;
-   };
-
-bool GMP_DSA_Verification_Operation::verify(const byte msg[], size_t msg_len,
-                                            const byte sig[], size_t sig_len)
-   {
-   const size_t q_bytes = q.bytes();
-
-   if(sig_len != 2*q_bytes || msg_len > q_bytes)
-      return false;
-
-   GMP_MPZ r(sig, q_bytes);
-   GMP_MPZ s(sig + q_bytes, q_bytes);
-   GMP_MPZ i(msg, msg_len);
-
-   if(mpz_cmp_ui(r.value, 0) <= 0 || mpz_cmp(r.value, q.value) >= 0)
-      return false;
-   if(mpz_cmp_ui(s.value, 0) <= 0 || mpz_cmp(s.value, q.value) >= 0)
-      return false;
-
-   if(mpz_invert(s.value, s.value, q.value) == 0)
-      return false;
-
-   GMP_MPZ si;
-   mpz_mul(si.value, s.value, i.value);
-   mpz_mod(si.value, si.value, q.value);
-   mpz_powm(si.value, g.value, si.value, p.value);
-
-   GMP_MPZ sr;
-   mpz_mul(sr.value, s.value, r.value);
-   mpz_mod(sr.value, sr.value, q.value);
-   mpz_powm(sr.value, y.value, sr.value, p.value);
-
-   mpz_mul(si.value, si.value, sr.value);
-   mpz_mod(si.value, si.value, p.value);
-   mpz_mod(si.value, si.value, q.value);
-
-   if(mpz_cmp(si.value, r.value) == 0)
-      return true;
-   return false;
-   }
-
-#endif
-
-#if defined(BOTAN_HAS_RSA)
-
-class GMP_RSA_Private_Operation : public PK_Ops::Signature,
-                                  public PK_Ops::Decryption
-   {
-   public:
-      GMP_RSA_Private_Operation(const RSA_PrivateKey& rsa) :
-         mod(rsa.get_n()),
-         p(rsa.get_p()),
-         q(rsa.get_q()),
-         d1(rsa.get_d1()),
-         d2(rsa.get_d2()),
-         c(rsa.get_c()),
-         n_bits(rsa.get_n().bits())
-         {}
-
-      size_t max_input_bits() const { return (n_bits - 1); }
-
-      secure_vector<byte> sign(const byte msg[], size_t msg_len,
-                              RandomNumberGenerator&)
-         {
-         BigInt m(msg, msg_len);
-         BigInt x = private_op(m);
-         return BigInt::encode_1363(x, (n_bits + 7) / 8);
-         }
-
-      secure_vector<byte> decrypt(const byte msg[], size_t msg_len)
-         {
-         BigInt m(msg, msg_len);
-         return BigInt::encode_locked(private_op(m));
-         }
-
-   private:
-      BigInt private_op(const BigInt& m) const;
-
-      GMP_MPZ mod, p, q, d1, d2, c;
-      size_t n_bits;
-   };
-
-BigInt GMP_RSA_Private_Operation::private_op(const BigInt& m) const
-   {
-   GMP_MPZ j1, j2, h(m);
-
-   mpz_powm(j1.value, h.value, d1.value, p.value);
-   mpz_powm(j2.value, h.value, d2.value, q.value);
-   mpz_sub(h.value, j1.value, j2.value);
-   mpz_mul(h.value, h.value, c.value);
-   mpz_mod(h.value, h.value, p.value);
-   mpz_mul(h.value, h.value, q.value);
-   mpz_add(h.value, h.value, j2.value);
-   return h.to_bigint();
-   }
-
-class GMP_RSA_Public_Operation : public PK_Ops::Verification,
-                                 public PK_Ops::Encryption
-   {
-   public:
-      GMP_RSA_Public_Operation(const RSA_PublicKey& rsa) :
-         n(rsa.get_n()), e(rsa.get_e()), mod(rsa.get_n())
-         {}
-
-      size_t max_input_bits() const { return (n.bits() - 1); }
-      bool with_recovery() const { return true; }
-
-      secure_vector<byte> encrypt(const byte msg[], size_t msg_len,
-                                 RandomNumberGenerator&)
-         {
-         BigInt m(msg, msg_len);
-         return BigInt::encode_1363(public_op(m), n.bytes());
-         }
-
-      secure_vector<byte> verify_mr(const byte msg[], size_t msg_len)
-         {
-         BigInt m(msg, msg_len);
-         return BigInt::encode_locked(public_op(m));
-         }
-
-   private:
-      BigInt public_op(const BigInt& m) const
-         {
-         if(m >= n)
-            throw Invalid_Argument("RSA public op - input is too large");
-
-         GMP_MPZ m_gmp(m);
-         mpz_powm(m_gmp.value, m_gmp.value, e.value, mod.value);
-         return m_gmp.to_bigint();
-         }
-
-      const BigInt& n;
-      const GMP_MPZ e, mod;
-   };
-
-#endif
-
-}
-
-PK_Ops::Key_Agreement*
-GMP_Engine::get_key_agreement_op(const Private_Key& key, RandomNumberGenerator&) const
-   {
-#if defined(BOTAN_HAS_DIFFIE_HELLMAN)
-   if(const DH_PrivateKey* dh = dynamic_cast<const DH_PrivateKey*>(&key))
-      return new GMP_DH_KA_Operation(*dh);
-#endif
-
-   return nullptr;
-   }
-
-PK_Ops::Signature*
-GMP_Engine::get_signature_op(const Private_Key& key, RandomNumberGenerator&) const
-   {
-#if defined(BOTAN_HAS_RSA)
-   if(const RSA_PrivateKey* s = dynamic_cast<const RSA_PrivateKey*>(&key))
-      return new GMP_RSA_Private_Operation(*s);
-#endif
-
-#if defined(BOTAN_HAS_DSA)
-   if(const DSA_PrivateKey* s = dynamic_cast<const DSA_PrivateKey*>(&key))
-      return new GMP_DSA_Signature_Operation(*s);
-#endif
-
-   return nullptr;
-   }
-
-PK_Ops::Verification*
-GMP_Engine::get_verify_op(const Public_Key& key, RandomNumberGenerator&) const
-   {
-#if defined(BOTAN_HAS_RSA)
-   if(const RSA_PublicKey* s = dynamic_cast<const RSA_PublicKey*>(&key))
-      return new GMP_RSA_Public_Operation(*s);
-#endif
-
-#if defined(BOTAN_HAS_DSA)
-   if(const DSA_PublicKey* s = dynamic_cast<const DSA_PublicKey*>(&key))
-      return new GMP_DSA_Verification_Operation(*s);
-#endif
-
-   return nullptr;
-   }
-
-PK_Ops::Encryption*
-GMP_Engine::get_encryption_op(const Public_Key& key, RandomNumberGenerator&) const
-   {
-#if defined(BOTAN_HAS_RSA)
-   if(const RSA_PublicKey* s = dynamic_cast<const RSA_PublicKey*>(&key))
-      return new GMP_RSA_Public_Operation(*s);
-#endif
-
-   return nullptr;
-   }
-
-PK_Ops::Decryption*
-GMP_Engine::get_decryption_op(const Private_Key& key, RandomNumberGenerator&) const
-   {
-#if defined(BOTAN_HAS_RSA)
-   if(const RSA_PrivateKey* s = dynamic_cast<const RSA_PrivateKey*>(&key))
-      return new GMP_RSA_Private_Operation(*s);
-#endif
-
-   return nullptr;
-   }
-
-}
diff --git a/src/lib/engine/gnump/info.txt b/src/lib/engine/gnump/info.txt
deleted file mode 100644
index ad03339e4..000000000
--- a/src/lib/engine/gnump/info.txt
+++ /dev/null
@@ -1,23 +0,0 @@
-define ENGINE_GNU_MP 20131128
-
-load_on request
-
-<libs>
-all -> gmp
-</libs>
-
-<header:internal>
-gnump_engine.h
-gmp_wrap.h
-</header:internal>
-
-<source>
-gmp_mem.cpp
-gmp_powm.cpp
-gmp_wrap.cpp
-gnump_pk.cpp
-</source>
-
-<requires>
-bigint
-</requires>
diff --git a/src/lib/engine/openssl/openssl_engine.h b/src/lib/engine/openssl/openssl_engine.h
index 90f315c00..5c0d1511d 100644
--- a/src/lib/engine/openssl/openssl_engine.h
+++ b/src/lib/engine/openssl/openssl_engine.h
@@ -23,10 +23,11 @@ class OpenSSL_Engine : public Engine
       PK_Ops::Key_Agreement*
          get_key_agreement_op(const Private_Key& key, RandomNumberGenerator& rng) const override;
 
-      PK_Ops::Signature*
-         get_signature_op(const Private_Key& key, RandomNumberGenerator& rng) const override;
+      PK_Ops::Signature* get_signature_op(const Private_Key& key, const std::string& emsa,
+                                          RandomNumberGenerator& rng) const override;
 
-      PK_Ops::Verification* get_verify_op(const Public_Key& key, RandomNumberGenerator& rng) const override;
+      PK_Ops::Verification* get_verify_op(const Public_Key& key, const std::string& emsa,
+                                          RandomNumberGenerator& rng) const override;
 
       PK_Ops::Encryption* get_encryption_op(const Public_Key& key, RandomNumberGenerator& rng) const override;
 
diff --git a/src/lib/engine/openssl/ossl_pk.cpp b/src/lib/engine/openssl/ossl_pk.cpp
index cbe03d7b3..b489ad454 100644
--- a/src/lib/engine/openssl/ossl_pk.cpp
+++ b/src/lib/engine/openssl/ossl_pk.cpp
@@ -282,7 +282,7 @@ OpenSSL_Engine::get_key_agreement_op(const Private_Key& key, RandomNumberGenerat
    }
 
 PK_Ops::Signature*
-OpenSSL_Engine::get_signature_op(const Private_Key& key, RandomNumberGenerator&) const
+OpenSSL_Engine::get_signature_op(const Private_Key& key, const std::string&, RandomNumberGenerator&) const
    {
 #if defined(BOTAN_HAS_RSA)
    if(const RSA_PrivateKey* s = dynamic_cast<const RSA_PrivateKey*>(&key))
@@ -298,7 +298,7 @@ OpenSSL_Engine::get_signature_op(const Private_Key& key, RandomNumberGenerator&)
    }
 
 PK_Ops::Verification*
-OpenSSL_Engine::get_verify_op(const Public_Key& key, RandomNumberGenerator&) const
+OpenSSL_Engine::get_verify_op(const Public_Key& key, const std::string&, RandomNumberGenerator&) const
    {
 #if defined(BOTAN_HAS_RSA)
    if(const RSA_PublicKey* s = dynamic_cast<const RSA_PublicKey*>(&key))
diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp
index c66db52f6..1dc2173da 100644
--- a/src/lib/pubkey/dsa/dsa.cpp
+++ b/src/lib/pubkey/dsa/dsa.cpp
@@ -1,6 +1,6 @@
 /*
 * DSA
-* (C) 1999-2010 Jack Lloyd
+* (C) 1999-2010,2014 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -8,7 +8,9 @@
 #include <botan/dsa.h>
 #include <botan/numthry.h>
 #include <botan/keypair.h>
+#include <botan/rfc6979.h>
 #include <future>
+
 namespace Botan {
 
 /*
@@ -65,11 +67,13 @@ bool DSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
    return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-1)");
    }
 
-DSA_Signature_Operation::DSA_Signature_Operation(const DSA_PrivateKey& dsa) :
+DSA_Signature_Operation::DSA_Signature_Operation(const DSA_PrivateKey& dsa,
+                                                 const std::string& emsa) :
    q(dsa.group_q()),
    x(dsa.get_x()),
    powermod_g_p(dsa.group_g(), dsa.group_p()),
-   mod_q(dsa.group_q())
+   mod_q(dsa.group_q()),
+   m_hash(hash_for_deterministic_signature(emsa))
    {
    }
 
@@ -80,22 +84,22 @@ DSA_Signature_Operation::sign(const byte msg[], size_t msg_len,
    rng.add_entropy(msg, msg_len);
 
    BigInt i(msg, msg_len);
-   BigInt r = 0, s = 0;
-
-   while(r == 0 || s == 0)
-      {
-      BigInt k;
-      do
-         k.randomize(rng, q.bits());
-      while(k >= q);
-
-      auto future_r = std::async(std::launch::async,
-                            [&]() { return mod_q.reduce(powermod_g_p(k)); });
-
-      s = inverse_mod(k, q);
-      r = future_r.get();
-      s = mod_q.multiply(s, mul_add(x, r, i));
-      }
+
+   if(i >= q)
+      i -= q;
+
+   const BigInt k = generate_rfc6979_nonce(x, q, i, m_hash);
+
+   auto future_r = std::async(std::launch::async,
+                              [&]() { return mod_q.reduce(powermod_g_p(k)); });
+
+   BigInt s = inverse_mod(k, q);
+   const BigInt r = future_r.get();
+   s = mod_q.multiply(s, mul_add(x, r, i));
+
+   // With overwhelming probability, a bug rather than actual zero r/s
+   BOTAN_ASSERT(s != 0, "invalid s");
+   BOTAN_ASSERT(r != 0, "invalid r");
 
    secure_vector<byte> output(2*q.bytes());
    r.binary_encode(&output[output.size() / 2 - r.bytes()]);
diff --git a/src/lib/pubkey/dsa/dsa.h b/src/lib/pubkey/dsa/dsa.h
index 7d51cfdd0..19c6c22d6 100644
--- a/src/lib/pubkey/dsa/dsa.h
+++ b/src/lib/pubkey/dsa/dsa.h
@@ -63,7 +63,7 @@ class BOTAN_DLL DSA_PrivateKey : public DSA_PublicKey,
 class BOTAN_DLL DSA_Signature_Operation : public PK_Ops::Signature
    {
    public:
-      DSA_Signature_Operation(const DSA_PrivateKey& dsa);
+      DSA_Signature_Operation(const DSA_PrivateKey& dsa, const std::string& hash);
 
       size_t message_parts() const { return 2; }
       size_t message_part_size() const { return q.bytes(); }
@@ -76,6 +76,7 @@ class BOTAN_DLL DSA_Signature_Operation : public PK_Ops::Signature
       const BigInt& x;
       Fixed_Base_Power_Mod powermod_g_p;
       Modular_Reducer mod_q;
+      std::string m_hash;
    };
 
 /**
diff --git a/src/lib/pubkey/dsa/info.txt b/src/lib/pubkey/dsa/info.txt
index a3f2a1ee4..ad14494a2 100644
--- a/src/lib/pubkey/dsa/info.txt
+++ b/src/lib/pubkey/dsa/info.txt
@@ -6,4 +6,5 @@ dl_group
 keypair
 libstate
 numbertheory
+rfc6979
 </requires>
diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp
index 6ff082649..b83a41e68 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.cpp
+++ b/src/lib/pubkey/ecdsa/ecdsa.cpp
@@ -9,6 +9,7 @@
 
 #include <botan/ecdsa.h>
 #include <botan/keypair.h>
+#include <botan/rfc6979.h>
 
 namespace Botan {
 
@@ -24,37 +25,30 @@ bool ECDSA_PrivateKey::check_key(RandomNumberGenerator& rng,
    return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-1)");
    }
 
-ECDSA_Signature_Operation::ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa) :
+ECDSA_Signature_Operation::ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa, const std::string& emsa) :
    base_point(ecdsa.domain().get_base_point()),
    order(ecdsa.domain().get_order()),
    x(ecdsa.private_value()),
-   mod_order(order)
+   mod_order(order),
+   m_hash(hash_for_deterministic_signature(emsa))
    {
    }
 
 secure_vector<byte>
 ECDSA_Signature_Operation::sign(const byte msg[], size_t msg_len,
-                                RandomNumberGenerator& rng)
+                                RandomNumberGenerator&)
    {
-   rng.add_entropy(msg, msg_len);
+   const BigInt m(msg, msg_len);
 
-   BigInt m(msg, msg_len);
+   const BigInt k = generate_rfc6979_nonce(x, order, m, m_hash);
 
-   BigInt r = 0, s = 0;
+   const PointGFp k_times_P = base_point * k;
+   const BigInt r = mod_order.reduce(k_times_P.get_affine_x());
+   const BigInt s = mod_order.multiply(inverse_mod(k, order), mul_add(x, r, m));
 
-   while(r == 0 || s == 0)
-      {
-      // This contortion is necessary for the tests
-      BigInt k;
-      k.randomize(rng, order.bits());
-
-      while(k >= order)
-         k.randomize(rng, order.bits() - 1);
-
-      PointGFp k_times_P = base_point * k;
-      r = mod_order.reduce(k_times_P.get_affine_x());
-      s = mod_order.multiply(inverse_mod(k, order), mul_add(x, r, m));
-      }
+   // With overwhelming probability, a bug rather than actual zero r/s
+   BOTAN_ASSERT(s != 0, "invalid s");
+   BOTAN_ASSERT(r != 0, "invalid r");
 
    secure_vector<byte> output(2*order.bytes());
    r.binary_encode(&output[output.size() / 2 - r.bytes()]);
diff --git a/src/lib/pubkey/ecdsa/ecdsa.h b/src/lib/pubkey/ecdsa/ecdsa.h
index e37fa1562..40eb9c7a7 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.h
+++ b/src/lib/pubkey/ecdsa/ecdsa.h
@@ -95,7 +95,8 @@ class BOTAN_DLL ECDSA_PrivateKey : public ECDSA_PublicKey,
 class BOTAN_DLL ECDSA_Signature_Operation : public PK_Ops::Signature
    {
    public:
-      ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa);
+      ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa,
+                                const std::string& hash);
 
       secure_vector<byte> sign(const byte msg[], size_t msg_len,
                               RandomNumberGenerator& rng);
@@ -109,6 +110,7 @@ class BOTAN_DLL ECDSA_Signature_Operation : public PK_Ops::Signature
       const BigInt& order;
       const BigInt& x;
       Modular_Reducer mod_order;
+      std::string m_hash;
    };
 
 /**
diff --git a/src/lib/pubkey/ecdsa/info.txt b/src/lib/pubkey/ecdsa/info.txt
index fcf688402..26640328f 100644
--- a/src/lib/pubkey/ecdsa/info.txt
+++ b/src/lib/pubkey/ecdsa/info.txt
@@ -6,4 +6,5 @@ ec_group
 ecc_key
 numbertheory
 rng
+rfc6979
 </requires>
diff --git a/src/lib/pubkey/pubkey.cpp b/src/lib/pubkey/pubkey.cpp
index a2c5cb745..a6fc7b2c9 100644
--- a/src/lib/pubkey/pubkey.cpp
+++ b/src/lib/pubkey/pubkey.cpp
@@ -134,10 +134,10 @@ PK_Signer::PK_Signer(const Private_Key& key,
    while(const Engine* engine = i.next())
       {
       if(!m_op)
-         m_op.reset(engine->get_signature_op(key, rng));
+         m_op.reset(engine->get_signature_op(key, emsa_name, rng));
 
       if(!m_verify_op && prot == ENABLE_FAULT_PROTECTION)
-         m_verify_op.reset(engine->get_verify_op(key, rng));
+         m_verify_op.reset(engine->get_verify_op(key, emsa_name, rng));
 
       if(m_op && (m_verify_op || prot == DISABLE_FAULT_PROTECTION))
          break;
@@ -249,7 +249,7 @@ PK_Verifier::PK_Verifier(const Public_Key& key,
 
    while(const Engine* engine = i.next())
       {
-      m_op.reset(engine->get_verify_op(key, rng));
+      m_op.reset(engine->get_verify_op(key, emsa_name, rng));
       if(m_op)
          break;
       }
diff --git a/src/lib/pubkey/rfc6979/rfc6979.cpp b/src/lib/pubkey/rfc6979/rfc6979.cpp
index 0bad4ecbf..21d6c356a 100644
--- a/src/lib/pubkey/rfc6979/rfc6979.cpp
+++ b/src/lib/pubkey/rfc6979/rfc6979.cpp
@@ -8,9 +8,24 @@
 #include <botan/rfc6979.h>
 #include <botan/hmac_drbg.h>
 #include <botan/libstate.h>
+#include <botan/scan_name.h>
 
 namespace Botan {
 
+std::string hash_for_deterministic_signature(const std::string& emsa)
+   {
+   SCAN_Name emsa_name(emsa);
+
+   if(emsa_name.arg_count() > 0)
+      {
+      const std::string pos_hash = emsa_name.arg(0);
+      if(global_state().algorithm_factory().prototype_hash_function(pos_hash))
+         return pos_hash;
+      }
+
+   return "SHA-512"; // safe default if nothing we understand
+   }
+
 BigInt generate_rfc6979_nonce(const BigInt& x,
                               const BigInt& q,
                               const BigInt& h,
diff --git a/src/lib/pubkey/rfc6979/rfc6979.h b/src/lib/pubkey/rfc6979/rfc6979.h
index 6184d0dbb..6e6073154 100644
--- a/src/lib/pubkey/rfc6979/rfc6979.h
+++ b/src/lib/pubkey/rfc6979/rfc6979.h
@@ -24,6 +24,8 @@ BigInt BOTAN_DLL generate_rfc6979_nonce(const BigInt& x,
                                         const BigInt& h,
                                         const std::string& hash);
 
+std::string hash_for_deterministic_signature(const std::string& emsa);
+
 }
 
 #endif