Move the signature padding schemes to the PK operation classes,

as was previously done with encrypt/decrypt ops.

One feature dropped on the floor here is previously PK_Signer by
default did verification of signatures before releasing them as an
measure against fault attacks. However in addition to being expensive
this turned out to be difficult to implement with the new scheme.

13 files changed, 390 insertions, 360 deletions

diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp
index ca5e93f4e..90cc18fdc 100644
--- a/src/lib/pubkey/dsa/dsa.cpp
+++ b/src/lib/pubkey/dsa/dsa.cpp
@@ -74,11 +74,12 @@ namespace {
 /**
 * Object that can create a DSA signature
 */
-class DSA_Signature_Operation : public PK_Ops::Signature
+class DSA_Signature_Operation : public PK_Ops::Signature_with_EMSA
    {
    public:
       typedef DSA_PrivateKey Key_Type;
       DSA_Signature_Operation(const DSA_PrivateKey& dsa, const std::string& emsa) :
+         PK_Ops::Signature_with_EMSA(emsa),
          q(dsa.group_q()),
          x(dsa.get_x()),
          powermod_g_p(dsa.group_g(), dsa.group_p()),
@@ -91,8 +92,8 @@ class DSA_Signature_Operation : public PK_Ops::Signature
       size_t message_part_size() const override { return q.bytes(); }
       size_t max_input_bits() const override { return q.bits(); }
 
-      secure_vector<byte> sign(const byte msg[], size_t msg_len,
-                              RandomNumberGenerator& rng) override;
+      secure_vector<byte> raw_sign(const byte msg[], size_t msg_len,
+                                   RandomNumberGenerator& rng) override;
    private:
       const BigInt& q;
       const BigInt& x;
@@ -102,8 +103,8 @@ class DSA_Signature_Operation : public PK_Ops::Signature
    };
 
 secure_vector<byte>
-DSA_Signature_Operation::sign(const byte msg[], size_t msg_len,
-                              RandomNumberGenerator&)
+DSA_Signature_Operation::raw_sign(const byte msg[], size_t msg_len,
+                                  RandomNumberGenerator&)
    {
    BigInt i(msg, msg_len);
 
@@ -132,12 +133,13 @@ DSA_Signature_Operation::sign(const byte msg[], size_t msg_len,
 /**
 * Object that can verify a DSA signature
 */
-class DSA_Verification_Operation : public PK_Ops::Verification
+class DSA_Verification_Operation : public PK_Ops::Verification_with_EMSA
    {
    public:
       typedef DSA_PublicKey Key_Type;
       DSA_Verification_Operation(const DSA_PublicKey& dsa,
-                                 const std::string&) :
+                                 const std::string& emsa) :
+         PK_Ops::Verification_with_EMSA(emsa),
          q(dsa.group_q()), y(dsa.get_y())
          {
          powermod_g_p = Fixed_Base_Power_Mod(dsa.group_g(), dsa.group_p());
diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp
index d2ad82b94..2518a14fe 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.cpp
+++ b/src/lib/pubkey/ecdsa/ecdsa.cpp
@@ -32,13 +32,14 @@ namespace {
 /**
 * ECDSA signature operation
 */
-class ECDSA_Signature_Operation : public PK_Ops::Signature
+class ECDSA_Signature_Operation : public PK_Ops::Signature_with_EMSA
    {
    public:
       typedef ECDSA_PrivateKey Key_Type;
 
       ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa,
                                 const std::string& emsa) :
+         PK_Ops::Signature_with_EMSA(emsa),
          base_point(ecdsa.domain().get_base_point()),
          order(ecdsa.domain().get_order()),
          x(ecdsa.private_value()),
@@ -47,12 +48,12 @@ class ECDSA_Signature_Operation : public PK_Ops::Signature
          {
          }
 
-      secure_vector<byte> sign(const byte msg[], size_t msg_len,
-                              RandomNumberGenerator& rng);
+      secure_vector<byte> raw_sign(const byte msg[], size_t msg_len,
+                                   RandomNumberGenerator& rng) override;
 
-      size_t message_parts() const { return 2; }
-      size_t message_part_size() const { return order.bytes(); }
-      size_t max_input_bits() const { return order.bits(); }
+      size_t message_parts() const override { return 2; }
+      size_t message_part_size() const override { return order.bytes(); }
+      size_t max_input_bits() const override { return order.bits(); }
 
    private:
       const PointGFp& base_point;
@@ -63,8 +64,8 @@ class ECDSA_Signature_Operation : public PK_Ops::Signature
    };
 
 secure_vector<byte>
-ECDSA_Signature_Operation::sign(const byte msg[], size_t msg_len,
-                                RandomNumberGenerator&)
+ECDSA_Signature_Operation::raw_sign(const byte msg[], size_t msg_len,
+                                    RandomNumberGenerator&)
    {
    const BigInt m(msg, msg_len);
 
@@ -87,12 +88,13 @@ ECDSA_Signature_Operation::sign(const byte msg[], size_t msg_len,
 /**
 * ECDSA verification operation
 */
-class ECDSA_Verification_Operation : public PK_Ops::Verification
+class ECDSA_Verification_Operation : public PK_Ops::Verification_with_EMSA
    {
    public:
       typedef ECDSA_PublicKey Key_Type;
       ECDSA_Verification_Operation(const ECDSA_PublicKey& ecdsa,
-                                   const std::string&) :
+                                   const std::string& emsa) :
+         PK_Ops::Verification_with_EMSA(emsa),
          m_base_point(ecdsa.domain().get_base_point()),
          m_public_point(ecdsa.public_point()),
          m_order(ecdsa.domain().get_order()),
@@ -101,14 +103,14 @@ class ECDSA_Verification_Operation : public PK_Ops::Verification
          //m_public_point.precompute_multiples();
          }
 
-      size_t message_parts() const { return 2; }
-      size_t message_part_size() const { return m_order.bytes(); }
-      size_t max_input_bits() const { return m_order.bits(); }
+      size_t message_parts() const override { return 2; }
+      size_t message_part_size() const override { return m_order.bytes(); }
+      size_t max_input_bits() const override { return m_order.bits(); }
 
-      bool with_recovery() const { return false; }
+      bool with_recovery() const override { return false; }
 
       bool verify(const byte msg[], size_t msg_len,
-                  const byte sig[], size_t sig_len);
+                  const byte sig[], size_t sig_len) override;
    private:
       const PointGFp& m_base_point;
       const PointGFp& m_public_point;
diff --git a/src/lib/pubkey/gost_3410/gost_3410.cpp b/src/lib/pubkey/gost_3410/gost_3410.cpp
index 497712fd9..8eb711617 100644
--- a/src/lib/pubkey/gost_3410/gost_3410.cpp
+++ b/src/lib/pubkey/gost_3410/gost_3410.cpp
@@ -94,21 +94,23 @@ BigInt decode_le(const byte msg[], size_t msg_len)
 /**
 * GOST-34.10 signature operation
 */
-class GOST_3410_Signature_Operation : public PK_Ops::Signature
+class GOST_3410_Signature_Operation : public PK_Ops::Signature_with_EMSA
    {
    public:
       typedef GOST_3410_PrivateKey Key_Type;
-      GOST_3410_Signature_Operation(const GOST_3410_PrivateKey& gost_3410, const std::string&):
+      GOST_3410_Signature_Operation(const GOST_3410_PrivateKey& gost_3410,
+                                    const std::string& emsa) :
+         PK_Ops::Signature_with_EMSA(emsa),
          base_point(gost_3410.domain().get_base_point()),
          order(gost_3410.domain().get_order()),
          x(gost_3410.private_value()) {}
 
-      size_t message_parts() const { return 2; }
-      size_t message_part_size() const { return order.bytes(); }
-      size_t max_input_bits() const { return order.bits(); }
+      size_t message_parts() const override { return 2; }
+      size_t message_part_size() const override { return order.bytes(); }
+      size_t max_input_bits() const override { return order.bits(); }
 
-      secure_vector<byte> sign(const byte msg[], size_t msg_len,
-                              RandomNumberGenerator& rng);
+      secure_vector<byte> raw_sign(const byte msg[], size_t msg_len,
+                                   RandomNumberGenerator& rng) override;
 
    private:
       const PointGFp& base_point;
@@ -117,8 +119,8 @@ class GOST_3410_Signature_Operation : public PK_Ops::Signature
    };
 
 secure_vector<byte>
-GOST_3410_Signature_Operation::sign(const byte msg[], size_t msg_len,
-                                    RandomNumberGenerator& rng)
+GOST_3410_Signature_Operation::raw_sign(const byte msg[], size_t msg_len,
+                                        RandomNumberGenerator& rng)
    {
    BigInt k;
    do
@@ -150,21 +152,23 @@ GOST_3410_Signature_Operation::sign(const byte msg[], size_t msg_len,
 /**
 * GOST-34.10 verification operation
 */
-class GOST_3410_Verification_Operation : public PK_Ops::Verification
+class GOST_3410_Verification_Operation : public PK_Ops::Verification_with_EMSA
    {
    public:
       typedef GOST_3410_PublicKey Key_Type;
 
-      GOST_3410_Verification_Operation(const GOST_3410_PublicKey& gost, const std::string&) :
+      GOST_3410_Verification_Operation(const GOST_3410_PublicKey& gost,
+                                       const std::string& emsa) :
+         PK_Ops::Verification_with_EMSA(emsa),
          base_point(gost.domain().get_base_point()),
          public_point(gost.public_point()),
          order(gost.domain().get_order()) {}
 
-      size_t message_parts() const { return 2; }
-      size_t message_part_size() const { return order.bytes(); }
-      size_t max_input_bits() const { return order.bits(); }
+      size_t message_parts() const override { return 2; }
+      size_t message_part_size() const override { return order.bytes(); }
+      size_t max_input_bits() const override { return order.bits(); }
 
-      bool with_recovery() const { return false; }
+      bool with_recovery() const override { return false; }
 
       bool verify(const byte msg[], size_t msg_len,
                   const byte sig[], size_t sig_len);
diff --git a/src/lib/pubkey/info.txt b/src/lib/pubkey/info.txt
index 4bb6288f9..055ebc320 100644
--- a/src/lib/pubkey/info.txt
+++ b/src/lib/pubkey/info.txt
@@ -24,6 +24,7 @@ workfactor.h
 <header:internal>
 pk_algs.h
 pk_utils.h
+pk_ops_impl.h
 </header:internal>
 
 <requires>
diff --git a/src/lib/pubkey/nr/nr.cpp b/src/lib/pubkey/nr/nr.cpp
index 6e3a8f0c1..ed90c2345 100644
--- a/src/lib/pubkey/nr/nr.cpp
+++ b/src/lib/pubkey/nr/nr.cpp
@@ -78,11 +78,12 @@ namespace {
 /**
 * Nyberg-Rueppel signature operation
 */
-class NR_Signature_Operation : public PK_Ops::Signature
+class NR_Signature_Operation : public PK_Ops::Signature_with_EMSA
    {
    public:
       typedef NR_PrivateKey Key_Type;
-      NR_Signature_Operation(const NR_PrivateKey& nr, const std::string&) :
+      NR_Signature_Operation(const NR_PrivateKey& nr, const std::string& emsa) :
+         PK_Ops::Signature_with_EMSA(emsa),
          q(nr.group_q()),
          x(nr.get_x()),
          powermod_g_p(nr.group_g(), nr.group_p()),
@@ -90,12 +91,12 @@ class NR_Signature_Operation : public PK_Ops::Signature
          {
          }
 
-      size_t message_parts() const { return 2; }
-      size_t message_part_size() const { return q.bytes(); }
-      size_t max_input_bits() const { return (q.bits() - 1); }
+      size_t message_parts() const override { return 2; }
+      size_t message_part_size() const override { return q.bytes(); }
+      size_t max_input_bits() const override { return (q.bits() - 1); }
 
-      secure_vector<byte> sign(const byte msg[], size_t msg_len,
-                              RandomNumberGenerator& rng);
+      secure_vector<byte> raw_sign(const byte msg[], size_t msg_len,
+                                   RandomNumberGenerator& rng) override;
    private:
       const BigInt& q;
       const BigInt& x;
@@ -104,8 +105,8 @@ class NR_Signature_Operation : public PK_Ops::Signature
    };
 
 secure_vector<byte>
-NR_Signature_Operation::sign(const byte msg[], size_t msg_len,
-                             RandomNumberGenerator& rng)
+NR_Signature_Operation::raw_sign(const byte msg[], size_t msg_len,
+                                 RandomNumberGenerator& rng)
    {
    rng.add_entropy(msg, msg_len);
 
@@ -137,11 +138,12 @@ NR_Signature_Operation::sign(const byte msg[], size_t msg_len,
 /**
 * Nyberg-Rueppel verification operation
 */
-class NR_Verification_Operation : public PK_Ops::Verification
+class NR_Verification_Operation : public PK_Ops::Verification_with_EMSA
    {
    public:
       typedef NR_PublicKey Key_Type;
-      NR_Verification_Operation(const NR_PublicKey& nr, const std::string&) :
+      NR_Verification_Operation(const NR_PublicKey& nr, const std::string& emsa) :
+         PK_Ops::Verification_with_EMSA(emsa),
          q(nr.group_q()), y(nr.get_y())
          {
          powermod_g_p = Fixed_Base_Power_Mod(nr.group_g(), nr.group_p());
@@ -150,13 +152,13 @@ class NR_Verification_Operation : public PK_Ops::Verification
          mod_q = Modular_Reducer(nr.group_q());
          }
 
-      size_t message_parts() const { return 2; }
-      size_t message_part_size() const { return q.bytes(); }
-      size_t max_input_bits() const { return (q.bits() - 1); }
+      size_t message_parts() const override { return 2; }
+      size_t message_part_size() const override { return q.bytes(); }
+      size_t max_input_bits() const override { return (q.bits() - 1); }
 
-      bool with_recovery() const { return true; }
+      bool with_recovery() const override { return true; }
 
-      secure_vector<byte> verify_mr(const byte msg[], size_t msg_len);
+      secure_vector<byte> verify_mr(const byte msg[], size_t msg_len) override;
    private:
       const BigInt& q;
       const BigInt& y;
diff --git a/src/lib/pubkey/pk_ops.cpp b/src/lib/pubkey/pk_ops.cpp
index 718cd3998..f78861b9f 100644
--- a/src/lib/pubkey/pk_ops.cpp
+++ b/src/lib/pubkey/pk_ops.cpp
@@ -5,7 +5,7 @@
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#include <botan/pk_ops.h>
+#include <botan/internal/pk_ops_impl.h>
 #include <botan/eme.h>
 #include <botan/kdf.h>
 #include <botan/emsa.h>
@@ -17,7 +17,7 @@ PK_Ops::Encryption_with_EME::Encryption_with_EME(const std::string& eme)
    {
    m_eme.reset(get_eme(eme));
    if(!m_eme.get())
-      throw std::runtime_error("EME " + eme + " not found");
+      throw Algorithm_Not_Found(eme);
    }
 
 PK_Ops::Encryption_with_EME::~Encryption_with_EME() {}
@@ -44,7 +44,7 @@ PK_Ops::Decryption_with_EME::Decryption_with_EME(const std::string& eme)
    {
    m_eme.reset(get_eme(eme));
    if(!m_eme.get())
-      throw std::runtime_error("EME " + eme + " not found");
+      throw Algorithm_Not_Found(eme);
    }
 
 PK_Ops::Decryption_with_EME::~Decryption_with_EME() {}
@@ -77,4 +77,56 @@ secure_vector<byte> PK_Ops::Key_Agreement_with_KDF::agree(size_t key_len,
    return z;
   }
 
+PK_Ops::Signature_with_EMSA::Signature_with_EMSA(const std::string& emsa)
+   {
+   m_emsa.reset(get_emsa(emsa));
+   if(!m_emsa)
+      throw Algorithm_Not_Found(emsa);
+   }
+
+PK_Ops::Signature_with_EMSA::~Signature_with_EMSA() {}
+
+void PK_Ops::Signature_with_EMSA::update(const byte msg[], size_t msg_len)
+   {
+   m_emsa->update(msg, msg_len);
+   }
+
+secure_vector<byte> PK_Ops::Signature_with_EMSA::sign(RandomNumberGenerator& rng)
+   {
+   const secure_vector<byte> msg = m_emsa->raw_data();
+   const auto padded = m_emsa->encoding_of(msg, this->max_input_bits(), rng);
+   return raw_sign(&padded[0], padded.size(), rng);
+   }
+
+PK_Ops::Verification_with_EMSA::Verification_with_EMSA(const std::string& emsa)
+   {
+   m_emsa.reset(get_emsa(emsa));
+   if(!m_emsa)
+      throw Algorithm_Not_Found(emsa);
+   }
+
+PK_Ops::Verification_with_EMSA::~Verification_with_EMSA() {}
+
+void PK_Ops::Verification_with_EMSA::update(const byte msg[], size_t msg_len)
+   {
+   m_emsa->update(msg, msg_len);
+   }
+
+bool PK_Ops::Verification_with_EMSA::is_valid_signature(const byte sig[], size_t sig_len)
+   {
+   const secure_vector<byte> msg = m_emsa->raw_data();
+
+   if(with_recovery())
+      {
+      secure_vector<byte> output_of_key = verify_mr(sig, sig_len);
+      return m_emsa->verify(output_of_key, msg, max_input_bits());
+      }
+   else
+      {
+      Null_RNG rng;
+      secure_vector<byte> encoded = m_emsa->encoding_of(msg, max_input_bits(), rng);
+      return verify(&encoded[0], encoded.size(), sig, sig_len);
+      }
+   }
+
 }
diff --git a/src/lib/pubkey/pk_ops.h b/src/lib/pubkey/pk_ops.h
index 754bcf82d..3a2a8bdb5 100644
--- a/src/lib/pubkey/pk_ops.h
+++ b/src/lib/pubkey/pk_ops.h
@@ -21,7 +21,7 @@ class EMSA;
 namespace PK_Ops {
 
 template<typename Key>
-struct PK_Spec
+class PK_Spec
    {
    public:
       PK_Spec(const Key& key, const std::string& pad) :
@@ -38,6 +38,9 @@ struct PK_Spec
       const std::string m_pad;
    };
 
+typedef PK_Spec<Public_Key> PK_Spec_Public_Key;
+typedef PK_Spec<Private_Key> PK_Spec_Private_Key;
+
 /**
 * Public key encryption interface
 */
@@ -48,68 +51,53 @@ class BOTAN_DLL Encryption
 
       virtual secure_vector<byte> encrypt(const byte msg[], size_t msg_len, RandomNumberGenerator& rng) = 0;
 
-      typedef PK_Spec<Public_Key> Spec;
+      typedef PK_Spec_Public_Key Spec;
 
       virtual ~Encryption() {}
    };
 
-class BOTAN_DLL Encryption_with_EME : public Encryption
-   {
-   public:
-      size_t max_input_bits() const override;
-
-      secure_vector<byte> encrypt(const byte msg[], size_t msg_len,
-                                  RandomNumberGenerator& rng) override;
-
-      ~Encryption_with_EME();
-   protected:
-      Encryption_with_EME(const std::string& eme);
-   private:
-      virtual size_t max_raw_input_bits() const = 0;
-
-      virtual secure_vector<byte> raw_encrypt(const byte msg[], size_t len,
-                                              RandomNumberGenerator& rng) = 0;
-      std::unique_ptr<EME> m_eme;
-   };
-
 /**
 * Public key decryption interface
 */
 class BOTAN_DLL Decryption
    {
    public:
+      typedef PK_Spec_Private_Key Spec;
+
       virtual size_t max_input_bits() const = 0;
 
       virtual secure_vector<byte> decrypt(const byte msg[],  size_t msg_len) = 0;
 
-      typedef PK_Spec<Private_Key> Spec;
-
       virtual ~Decryption() {}
    };
 
-class BOTAN_DLL Decryption_with_EME : public Decryption
+/**
+* Public key signature verification interface
+*/
+class BOTAN_DLL Verification
    {
    public:
-      size_t max_input_bits() const override;
+      typedef PK_Spec_Public_Key Spec;
 
-      secure_vector<byte> decrypt(const byte msg[], size_t msg_len) override;
+      /*
+      * Add more data to the message currently being signed
+      * @param msg the message
+      * @param msg_len the length of msg in bytes
+      */
+      virtual void update(const byte msg[], size_t msg_len) = 0;
 
-      ~Decryption_with_EME();
-   protected:
-      Decryption_with_EME(const std::string& eme);
-   private:
-      virtual size_t max_raw_input_bits() const = 0;
-      virtual secure_vector<byte> raw_decrypt(const byte msg[], size_t len) = 0;
-      std::unique_ptr<EME> m_eme;
-   };
+      /*
+      * Perform a signature operation
+      * @param rng a random number generator
+      */
+      virtual bool is_valid_signature(const byte sig[], size_t sig_len) = 0;
 
+      /**
+      * Get the maximum message size in bits supported by this public key.
+      * @return maximum message in bits
+      */
+      virtual size_t max_input_bits() const = 0;
 
-/**
-* Public key signature creation interface
-*/
-class BOTAN_DLL Signature
-   {
-   public:
       /**
       * Find out the number of message parts supported by this scheme.
       * @return number of message parts
@@ -122,37 +110,16 @@ class BOTAN_DLL Signature
       */
       virtual size_t message_part_size() const { return 0; }
 
-      /**
-      * Get the maximum message size in bits supported by this public key.
-      * @return maximum message in bits
-      */
-      virtual size_t max_input_bits() const = 0;
-
-      /*
-      * Perform a signature operation
-      * @param msg the message
-      * @param msg_len the length of msg in bytes
-      * @param rng a random number generator
-      */
-      virtual secure_vector<byte> sign(const byte msg[], size_t msg_len,
-                                      RandomNumberGenerator& rng) = 0;
-
-      typedef PK_Spec<Private_Key> Spec;
-
-      virtual ~Signature() {}
+      virtual ~Verification() {}
    };
 
 /**
-* Public key signature verification interface
+* Public key signature creation interface
 */
-class BOTAN_DLL Verification
+class BOTAN_DLL Signature
    {
    public:
-      /**
-      * Get the maximum message size in bits supported by this public key.
-      * @return maximum message in bits
-      */
-      virtual size_t max_input_bits() const = 0;
+      typedef PK_Spec_Private_Key Spec;
 
       /**
       * Find out the number of message parts supported by this scheme.
@@ -166,42 +133,20 @@ class BOTAN_DLL Verification
       */
       virtual size_t message_part_size() const { return 0; }
 
-      /**
-      * @return boolean specifying if this key type supports message
-      * recovery and thus if you need to call verify() or verify_mr()
-      */
-      virtual bool with_recovery() const = 0;
-
       /*
-      * Perform a signature check operation
+      * Add more data to the message currently being signed
       * @param msg the message
       * @param msg_len the length of msg in bytes
-      * @param sig the signature
-      * @param sig_len the length of sig in bytes
-      * @returns if signature is a valid one for message
       */
-      virtual bool verify(const byte[], size_t,
-                          const byte[], size_t)
-         {
-         throw Invalid_State("Message recovery required");
-         }
+      virtual void update(const byte msg[], size_t msg_len) = 0;
 
       /*
-      * Perform a signature operation (with message recovery)
-      * Only call this if with_recovery() returns true
-      * @param msg the message
-      * @param msg_len the length of msg in bytes
-      * @returns recovered message
+      * Perform a signature operation
+      * @param rng a random number generator
       */
-      virtual secure_vector<byte> verify_mr(const byte[],
-                                           size_t)
-         {
-         throw Invalid_State("Message recovery not supported");
-         }
+      virtual secure_vector<byte> sign(RandomNumberGenerator& rng) = 0;
 
-      typedef PK_Spec<Public_Key> Spec;
-
-      virtual ~Verification() {}
+      virtual ~Signature() {}
    };
 
 /**
@@ -210,30 +155,15 @@ class BOTAN_DLL Verification
 class BOTAN_DLL Key_Agreement
    {
    public:
+      typedef PK_Spec_Private_Key Spec;
+
       virtual secure_vector<byte> agree(size_t key_len,
                                         const byte other_key[], size_t other_key_len,
                                         const byte salt[], size_t salt_len) = 0;
 
-      typedef PK_Spec<Private_Key> Spec;
-
       virtual ~Key_Agreement() {}
    };
 
-class BOTAN_DLL Key_Agreement_with_KDF : public Key_Agreement
-   {
-   public:
-      secure_vector<byte> agree(size_t key_len,
-                                const byte other_key[], size_t other_key_len,
-                                const byte salt[], size_t salt_len) override;
-
-   protected:
-      Key_Agreement_with_KDF(const std::string& kdf);
-      ~Key_Agreement_with_KDF();
-   private:
-      virtual secure_vector<byte> raw_agree(const byte w[], size_t w_len) = 0;
-      std::unique_ptr<KDF> m_kdf;
-   };
-
 }
 
 }
diff --git a/src/lib/pubkey/pk_ops_impl.h b/src/lib/pubkey/pk_ops_impl.h
new file mode 100644
index 000000000..f27de4af4
--- /dev/null
+++ b/src/lib/pubkey/pk_ops_impl.h
@@ -0,0 +1,146 @@
+/*
+* (C) 2015 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_PK_OPERATION_IMPL_H__
+#define BOTAN_PK_OPERATION_IMPL_H__
+
+#include <botan/pk_ops.h>
+
+namespace Botan {
+
+namespace PK_Ops {
+
+class Encryption_with_EME : public Encryption
+   {
+   public:
+      size_t max_input_bits() const override;
+
+      secure_vector<byte> encrypt(const byte msg[], size_t msg_len,
+                                  RandomNumberGenerator& rng) override;
+
+      ~Encryption_with_EME();
+   protected:
+      Encryption_with_EME(const std::string& eme);
+   private:
+      virtual size_t max_raw_input_bits() const = 0;
+
+      virtual secure_vector<byte> raw_encrypt(const byte msg[], size_t len,
+                                              RandomNumberGenerator& rng) = 0;
+      std::unique_ptr<EME> m_eme;
+   };
+
+class Decryption_with_EME : public Decryption
+   {
+   public:
+      size_t max_input_bits() const override;
+
+      secure_vector<byte> decrypt(const byte msg[], size_t msg_len) override;
+
+      ~Decryption_with_EME();
+   protected:
+      Decryption_with_EME(const std::string& eme);
+   private:
+      virtual size_t max_raw_input_bits() const = 0;
+      virtual secure_vector<byte> raw_decrypt(const byte msg[], size_t len) = 0;
+      std::unique_ptr<EME> m_eme;
+   };
+
+class Verification_with_EMSA : public Verification
+   {
+   public:
+      void update(const byte msg[], size_t msg_len) override;
+      bool is_valid_signature(const byte sig[], size_t sig_len) override;
+
+      bool do_check(const secure_vector<byte>& msg,
+                    const byte sig[], size_t sig_len);
+
+   protected:
+
+      Verification_with_EMSA(const std::string& emsa);
+      ~Verification_with_EMSA();
+
+      /**
+      * @return boolean specifying if this key type supports message
+      * recovery and thus if you need to call verify() or verify_mr()
+      */
+      virtual bool with_recovery() const = 0;
+
+      /*
+      * Perform a signature check operation
+      * @param msg the message
+      * @param msg_len the length of msg in bytes
+      * @param sig the signature
+      * @param sig_len the length of sig in bytes
+      * @returns if signature is a valid one for message
+      */
+      virtual bool verify(const byte[], size_t,
+                          const byte[], size_t)
+         {
+         throw Invalid_State("Message recovery required");
+         }
+
+      /*
+      * Perform a signature operation (with message recovery)
+      * Only call this if with_recovery() returns true
+      * @param msg the message
+      * @param msg_len the length of msg in bytes
+      * @returns recovered message
+      */
+      virtual secure_vector<byte> verify_mr(const byte[], size_t)
+         {
+         throw Invalid_State("Message recovery not supported");
+         }
+
+   private:
+      std::unique_ptr<EMSA> m_emsa;
+   };
+
+class Signature_with_EMSA : public Signature
+   {
+   public:
+      void update(const byte msg[], size_t msg_len) override;
+
+      secure_vector<byte> sign(RandomNumberGenerator& rng) override;
+   protected:
+      Signature_with_EMSA(const std::string& emsa);
+      ~Signature_with_EMSA();
+   private:
+
+      /**
+      * Get the maximum message size in bits supported by this public key.
+      * @return maximum message in bits
+      */
+      virtual size_t max_input_bits() const = 0;
+
+      bool self_test_signature(const std::vector<byte>& msg,
+                               const std::vector<byte>& sig) const;
+
+      virtual secure_vector<byte> raw_sign(const byte msg[], size_t msg_len,
+                                           RandomNumberGenerator& rng) = 0;
+
+      std::unique_ptr<EMSA> m_emsa;
+   };
+
+class Key_Agreement_with_KDF : public Key_Agreement
+   {
+   public:
+      secure_vector<byte> agree(size_t key_len,
+                                const byte other_key[], size_t other_key_len,
+                                const byte salt[], size_t salt_len) override;
+
+   protected:
+      Key_Agreement_with_KDF(const std::string& kdf);
+      ~Key_Agreement_with_KDF();
+   private:
+      virtual secure_vector<byte> raw_agree(const byte w[], size_t w_len) = 0;
+      std::unique_ptr<KDF> m_kdf;
+   };
+
+}
+
+}
+
+#endif
diff --git a/src/lib/pubkey/pk_utils.h b/src/lib/pubkey/pk_utils.h
index 2d643d862..14c304ac5 100644
--- a/src/lib/pubkey/pk_utils.h
+++ b/src/lib/pubkey/pk_utils.h
@@ -9,7 +9,7 @@
 #define BOTAN_PK_UTILS_H__
 
 #include <botan/internal/algo_registry.h>
-#include <botan/pk_ops.h>
+#include <botan/internal/pk_ops_impl.h>
 #include <botan/numthry.h>
 #include <algorithm>
 
diff --git a/src/lib/pubkey/pubkey.cpp b/src/lib/pubkey/pubkey.cpp
index a2bb44e5c..1d32697f5 100644
--- a/src/lib/pubkey/pubkey.cpp
+++ b/src/lib/pubkey/pubkey.cpp
@@ -5,18 +5,10 @@
 */
 
 #include <botan/pubkey.h>
+#include <botan/internal/algo_registry.h>
 #include <botan/der_enc.h>
 #include <botan/ber_dec.h>
 #include <botan/bigint.h>
-#include <botan/parsing.h>
-#include <botan/internal/algo_registry.h>
-#include <botan/internal/bit_ops.h>
-
-#if defined(BOTAN_HAS_SYSTEM_RNG)
-  #include <botan/system_rng.h>
-#else
-  #include <botan/auto_rng.h>
-#endif
 
 namespace Botan {
 
@@ -73,132 +65,88 @@ SymmetricKey PK_Key_Agreement::derive_key(size_t key_len,
    return m_op->agree(key_len, in, in_len, salt, salt_len);
    }
 
-/*
-* PK_Signer Constructor
-*/
-PK_Signer::PK_Signer(const Private_Key& key,
-                     const std::string& emsa,
-                     Signature_Format format,
-                     Fault_Protection prot)
-   {
-   m_op.reset(get_pk_op<PK_Ops::Signature>(key, emsa));
-
-   if(prot == ENABLE_FAULT_PROTECTION)
-      m_verify_op.reset(get_pk_op<PK_Ops::Verification>(key, emsa));
-
-   if(!m_op || (prot == ENABLE_FAULT_PROTECTION && !m_verify_op))
-      throw Lookup_Error("Signing with " + key.algo_name() + " not supported");
-
-   m_emsa.reset(get_emsa(emsa));
-   m_sig_format = format;
-   }
+namespace {
 
-/*
-* Sign a message
-*/
-std::vector<byte> PK_Signer::sign_message(const byte msg[], size_t length,
-                                           RandomNumberGenerator& rng)
+std::vector<byte> der_encode_signature(const std::vector<byte>& sig, size_t parts)
    {
-   update(msg, length);
-   return signature(rng);
-   }
+   if(sig.size() % parts)
+      throw Encoding_Error("PK_Signer: strange signature size found");
+   const size_t SIZE_OF_PART = sig.size() / parts;
 
-/*
-* Add more to the message to be signed
-*/
-void PK_Signer::update(const byte in[], size_t length)
-   {
-   m_emsa->update(in, length);
+   std::vector<BigInt> sig_parts(parts);
+   for(size_t j = 0; j != sig_parts.size(); ++j)
+      sig_parts[j].binary_decode(&sig[SIZE_OF_PART*j], SIZE_OF_PART);
+
+   return DER_Encoder()
+      .start_cons(SEQUENCE)
+      .encode_list(sig_parts)
+      .end_cons()
+      .get_contents_unlocked();
    }
 
-/*
-* Check the signature we just created, to help prevent fault attacks
-*/
-bool PK_Signer::self_test_signature(const std::vector<byte>& msg,
-                                    const std::vector<byte>& sig) const
+std::vector<byte> der_decode_signature(const byte sig[], size_t len,
+                                       size_t part_size, size_t parts)
    {
-   if(!m_verify_op)
-      return true; // checking disabled, assume ok
+   std::vector<byte> real_sig;
+   BER_Decoder decoder(sig, len);
+   BER_Decoder ber_sig = decoder.start_cons(SEQUENCE);
 
-   if(m_verify_op->with_recovery())
+   size_t count = 0;
+   while(ber_sig.more_items())
       {
-      std::vector<byte> recovered =
-         unlock(m_verify_op->verify_mr(&sig[0], sig.size()));
+      BigInt sig_part;
+      ber_sig.decode(sig_part);
+      real_sig += BigInt::encode_1363(sig_part, part_size);
+      ++count;
+      }
 
-      if(msg.size() > recovered.size())
-         {
-         size_t extra_0s = msg.size() - recovered.size();
+   if(count != parts)
+      throw Decoding_Error("PK_Verifier: signature size invalid");
+   return real_sig;
+   }
 
-         for(size_t i = 0; i != extra_0s; ++i)
-            if(msg[i] != 0)
-               return false;
+}
 
-         return same_mem(&msg[extra_0s], &recovered[0], recovered.size());
-         }
+PK_Signer::PK_Signer(const Private_Key& key,
+                     const std::string& emsa,
+                     Signature_Format format)
+   {
+   m_op.reset(get_pk_op<PK_Ops::Signature>(key, emsa));
+   if(!m_op)
+      throw Lookup_Error("Signing with " + key.algo_name() + "/" + emsa + " not supported");
+   m_sig_format = format;
+   }
 
-      return (recovered == msg);
-      }
-   else
-      return m_verify_op->verify(&msg[0], msg.size(),
-                               &sig[0], sig.size());
+void PK_Signer::update(const byte in[], size_t length)
+   {
+   m_op->update(in, length);
    }
 
-/*
-* Create a signature
-*/
 std::vector<byte> PK_Signer::signature(RandomNumberGenerator& rng)
    {
-   std::vector<byte> encoded = unlock(m_emsa->encoding_of(m_emsa->raw_data(),
-                                                 m_op->max_input_bits(),
-                                                        rng));
-
-   std::vector<byte> plain_sig = unlock(m_op->sign(&encoded[0], encoded.size(), rng));
-
-   BOTAN_ASSERT(self_test_signature(encoded, plain_sig), "Signature was consistent");
+   const std::vector<byte> plain_sig = unlock(m_op->sign(rng));
+   const size_t parts = m_op->message_parts();
 
-   if(m_op->message_parts() == 1 || m_sig_format == IEEE_1363)
+   if(parts == 1 || m_sig_format == IEEE_1363)
       return plain_sig;
-
-   if(m_sig_format == DER_SEQUENCE)
-      {
-      if(plain_sig.size() % m_op->message_parts())
-         throw Encoding_Error("PK_Signer: strange signature size found");
-      const size_t SIZE_OF_PART = plain_sig.size() / m_op->message_parts();
-
-      std::vector<BigInt> sig_parts(m_op->message_parts());
-      for(size_t j = 0; j != sig_parts.size(); ++j)
-         sig_parts[j].binary_decode(&plain_sig[SIZE_OF_PART*j], SIZE_OF_PART);
-
-      return DER_Encoder()
-         .start_cons(SEQUENCE)
-            .encode_list(sig_parts)
-         .end_cons()
-      .get_contents_unlocked();
-      }
+   else if(m_sig_format == DER_SEQUENCE)
+      return der_encode_signature(plain_sig, parts);
    else
       throw Encoding_Error("PK_Signer: Unknown signature format " +
                            std::to_string(m_sig_format));
    }
 
-/*
-* PK_Verifier Constructor
-*/
 PK_Verifier::PK_Verifier(const Public_Key& key,
                          const std::string& emsa_name,
                          Signature_Format format)
    {
    m_op.reset(get_pk_op<PK_Ops::Verification>(key, emsa_name));
-
    if(!m_op)
       throw Lookup_Error("Verification with " + key.algo_name() + " not supported");
 
-   m_emsa.reset(get_emsa(emsa_name));
    m_sig_format = format;
    }
 
-/*
-* Set the signature format
-*/
 void PK_Verifier::set_input_format(Signature_Format format)
    {
    if(m_op->message_parts() == 1 && format != IEEE_1363)
@@ -206,9 +154,6 @@ void PK_Verifier::set_input_format(Signature_Format format)
    m_sig_format = format;
    }
 
-/*
-* Verify a message
-*/
 bool PK_Verifier::verify_message(const byte msg[], size_t msg_length,
                                  const byte sig[], size_t sig_length)
    {
@@ -216,42 +161,25 @@ bool PK_Verifier::verify_message(const byte msg[], size_t msg_length,
    return check_signature(sig, sig_length);
    }
 
-/*
-* Append to the message
-*/
 void PK_Verifier::update(const byte in[], size_t length)
    {
-   m_emsa->update(in, length);
+   m_op->update(in, length);
    }
 
-/*
-* Check a signature
-*/
 bool PK_Verifier::check_signature(const byte sig[], size_t length)
    {
    try {
       if(m_sig_format == IEEE_1363)
-         return validate_signature(m_emsa->raw_data(), sig, length);
+         {
+         return m_op->is_valid_signature(sig, length);
+         }
       else if(m_sig_format == DER_SEQUENCE)
          {
-         BER_Decoder decoder(sig, length);
-         BER_Decoder ber_sig = decoder.start_cons(SEQUENCE);
-
-         size_t count = 0;
-         std::vector<byte> real_sig;
-         while(ber_sig.more_items())
-            {
-            BigInt sig_part;
-            ber_sig.decode(sig_part);
-            real_sig += BigInt::encode_1363(sig_part, m_op->message_part_size());
-            ++count;
-            }
-
-         if(count != m_op->message_parts())
-            throw Decoding_Error("PK_Verifier: signature size invalid");
-
-         return validate_signature(m_emsa->raw_data(),
-                                   &real_sig[0], real_sig.size());
+         std::vector<byte> real_sig = der_decode_signature(sig, length,
+                                                           m_op->message_part_size(),
+                                                           m_op->message_parts());
+
+         return m_op->is_valid_signature(&real_sig[0], real_sig.size());
          }
       else
          throw Decoding_Error("PK_Verifier: Unknown signature format " +
@@ -260,26 +188,4 @@ bool PK_Verifier::check_signature(const byte sig[], size_t length)
    catch(Invalid_Argument) { return false; }
    }
 
-/*
-* Verify a signature
-*/
-bool PK_Verifier::validate_signature(const secure_vector<byte>& msg,
-                                     const byte sig[], size_t sig_len)
-   {
-   if(m_op->with_recovery())
-      {
-      secure_vector<byte> output_of_key = m_op->verify_mr(sig, sig_len);
-      return m_emsa->verify(output_of_key, msg, m_op->max_input_bits());
-      }
-   else
-      {
-      Null_RNG rng;
-
-      secure_vector<byte> encoded =
-         m_emsa->encoding_of(msg, m_op->max_input_bits(), rng);
-
-      return m_op->verify(&encoded[0], encoded.size(), sig, sig_len);
-      }
-   }
-
 }
diff --git a/src/lib/pubkey/pubkey.h b/src/lib/pubkey/pubkey.h
index ffb00979d..54c55c597 100644
--- a/src/lib/pubkey/pubkey.h
+++ b/src/lib/pubkey/pubkey.h
@@ -24,14 +24,6 @@ namespace Botan {
 enum Signature_Format { IEEE_1363, DER_SEQUENCE };
 
 /**
-* Enum marking if protection against fault attacks should be used
-*/
-enum Fault_Protection {
-   ENABLE_FAULT_PROTECTION,
-   DISABLE_FAULT_PROTECTION
-};
-
-/**
 * Public Key Encryptor
 */
 class BOTAN_DLL PK_Encryptor
@@ -136,7 +128,11 @@ class BOTAN_DLL PK_Signer
       * @return signature
       */
       std::vector<byte> sign_message(const byte in[], size_t length,
-                                      RandomNumberGenerator& rng);
+                                     RandomNumberGenerator& rng)
+         {
+         this->update(in, length);
+         return this->signature(rng);
+         }
 
       /**
       * Sign a message.
@@ -191,19 +187,12 @@ class BOTAN_DLL PK_Signer
       * @param emsa the EMSA to use
       * An example would be "EMSA1(SHA-224)".
       * @param format the signature format to use
-      * @param prot says if fault protection should be enabled
       */
       PK_Signer(const Private_Key& key,
                 const std::string& emsa,
-                Signature_Format format = IEEE_1363,
-                Fault_Protection prot = ENABLE_FAULT_PROTECTION);
+                Signature_Format format = IEEE_1363);
    private:
-      bool self_test_signature(const std::vector<byte>& msg,
-                               const std::vector<byte>& sig) const;
-
       std::unique_ptr<PK_Ops::Signature> m_op;
-      std::unique_ptr<PK_Ops::Verification> m_verify_op;
-      std::unique_ptr<EMSA> m_emsa;
       Signature_Format m_sig_format;
    };
 
@@ -299,11 +288,7 @@ class BOTAN_DLL PK_Verifier
                   const std::string& emsa,
                   Signature_Format format = IEEE_1363);
    private:
-      bool validate_signature(const secure_vector<byte>& msg,
-                              const byte sig[], size_t sig_len);
-
       std::unique_ptr<PK_Ops::Verification> m_op;
-      std::unique_ptr<EMSA> m_emsa;
       Signature_Format m_sig_format;
    };
 
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index 464055cd7..13425a46f 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -112,7 +112,7 @@ class RSA_Private_Operation
       Blinder m_blinder;
    };
 
-class RSA_Signature_Operation : public PK_Ops::Signature,
+class RSA_Signature_Operation : public PK_Ops::Signature_with_EMSA,
                                 private RSA_Private_Operation
    {
    public:
@@ -120,20 +120,18 @@ class RSA_Signature_Operation : public PK_Ops::Signature,
 
       size_t max_input_bits() const override { return get_max_input_bits(); };
 
-      RSA_Signature_Operation(const RSA_PrivateKey& rsa, const std::string&) :
+      RSA_Signature_Operation(const RSA_PrivateKey& rsa, const std::string& emsa) :
+         PK_Ops::Signature_with_EMSA(emsa),
          RSA_Private_Operation(rsa)
          {
          }
 
-      secure_vector<byte> sign(const byte msg[], size_t msg_len,
-                              RandomNumberGenerator&) override
+      secure_vector<byte> raw_sign(const byte msg[], size_t msg_len,
+                                   RandomNumberGenerator&) override
          {
-         /* We don't check signatures against powermod_e_n here because
-         PK_Signer checks verification consistency for all signature
-         algorithms.
-         */
          const BigInt m(msg, msg_len);
          const BigInt x = blinded_private_op(m);
+         BOTAN_ASSERT(m == m_powermod_e_n(x), "RSA sign consistency check");
          return BigInt::encode_1363(x, n.bytes());
          }
    };
@@ -161,7 +159,6 @@ class RSA_Decryption_Operation : public PK_Ops::Decryption_with_EME,
          }
    };
 
-
 /**
 * RSA public (encrypt/verify) operation
 */
@@ -208,7 +205,7 @@ class RSA_Encryption_Operation : public PK_Ops::Encryption_with_EME,
          }
    };
 
-class RSA_Verify_Operation : public PK_Ops::Verification,
+class RSA_Verify_Operation : public PK_Ops::Verification_with_EMSA,
                              private RSA_Public_Operation
    {
    public:
@@ -216,7 +213,8 @@ class RSA_Verify_Operation : public PK_Ops::Verification,
 
       size_t max_input_bits() const override { return get_max_input_bits(); };
 
-      RSA_Verify_Operation(const RSA_PublicKey& rsa, const std::string&) :
+      RSA_Verify_Operation(const RSA_PublicKey& rsa, const std::string& emsa) :
+         PK_Ops::Verification_with_EMSA(emsa),
          RSA_Public_Operation(rsa)
          {
          }
diff --git a/src/lib/pubkey/rw/rw.cpp b/src/lib/pubkey/rw/rw.cpp
index 32ba398b0..b706d6730 100644
--- a/src/lib/pubkey/rw/rw.cpp
+++ b/src/lib/pubkey/rw/rw.cpp
@@ -67,13 +67,14 @@ namespace {
 /**
 * Rabin-Williams Signature Operation
 */
-class RW_Signature_Operation : public PK_Ops::Signature
+class RW_Signature_Operation : public PK_Ops::Signature_with_EMSA
    {
    public:
       typedef RW_PrivateKey Key_Type;
 
       RW_Signature_Operation(const RW_PrivateKey& rw,
-                             const std::string&) :
+                             const std::string& emsa) :
+         PK_Ops::Signature_with_EMSA(emsa),
          n(rw.get_n()),
          e(rw.get_e()),
          q(rw.get_q()),
@@ -87,10 +88,10 @@ class RW_Signature_Operation : public PK_Ops::Signature
          {
          }
 
-      size_t max_input_bits() const { return (n.bits() - 1); }
+      size_t max_input_bits() const override { return (n.bits() - 1); }
 
-      secure_vector<byte> sign(const byte msg[], size_t msg_len,
-                              RandomNumberGenerator& rng);
+      secure_vector<byte> raw_sign(const byte msg[], size_t msg_len,
+                                   RandomNumberGenerator& rng) override;
    private:
       const BigInt& n;
       const BigInt& e;
@@ -103,8 +104,8 @@ class RW_Signature_Operation : public PK_Ops::Signature
    };
 
 secure_vector<byte>
-RW_Signature_Operation::sign(const byte msg[], size_t msg_len,
-                             RandomNumberGenerator&)
+RW_Signature_Operation::raw_sign(const byte msg[], size_t msg_len,
+                                 RandomNumberGenerator&)
    {
    BigInt i(msg, msg_len);
 
@@ -130,12 +131,13 @@ RW_Signature_Operation::sign(const byte msg[], size_t msg_len,
 /**
 * Rabin-Williams Verification Operation
 */
-class RW_Verification_Operation : public PK_Ops::Verification
+class RW_Verification_Operation : public PK_Ops::Verification_with_EMSA
    {
    public:
       typedef RW_PublicKey Key_Type;
 
-      RW_Verification_Operation(const RW_PublicKey& rw, const std::string&) :
+      RW_Verification_Operation(const RW_PublicKey& rw, const std::string& emsa) :
+         PK_Ops::Verification_with_EMSA(emsa),
          n(rw.get_n()), powermod_e_n(rw.get_e(), rw.get_n())
          {}