Revert PK_Verifier change (don't require RNG there).

Verification is deterministic and public, so really no RNG is ever needed.

Change provider handling - accepts "base", "openssl", or empty, otherwise
throws a Provider_Not_Found exception.

36 files changed, 208 insertions, 166 deletions

diff --git a/src/lib/cert/x509/ocsp.cpp b/src/lib/cert/x509/ocsp.cpp
index fb6234cc8..761c5b436 100644
--- a/src/lib/cert/x509/ocsp.cpp
+++ b/src/lib/cert/x509/ocsp.cpp
@@ -61,8 +61,7 @@ void check_signature(const std::vector<byte>& tbs_response,
    Signature_Format format =
       (pub_key->message_parts() >= 2) ? DER_SEQUENCE : IEEE_1363;
 
-   Null_RNG null_rng;
-   PK_Verifier verifier(*pub_key, null_rng, padding, format);
+   PK_Verifier verifier(*pub_key, padding, format);
 
    if(!verifier.verify_message(ASN1::put_in_sequence(tbs_response), signature))
       throw Exception("Signature on OCSP response does not verify");
diff --git a/src/lib/cert/x509/x509_obj.cpp b/src/lib/cert/x509/x509_obj.cpp
index 25da0155e..983be40b2 100644
--- a/src/lib/cert/x509/x509_obj.cpp
+++ b/src/lib/cert/x509/x509_obj.cpp
@@ -197,8 +197,7 @@ bool X509_Object::check_signature(const Public_Key& pub_key) const
       Signature_Format format =
          (pub_key.message_parts() >= 2) ? DER_SEQUENCE : IEEE_1363;
 
-      Null_RNG null_rng;
-      PK_Verifier verifier(pub_key, null_rng, padding, format);
+      PK_Verifier verifier(pub_key, padding, format);
 
       return verifier.verify_message(tbs_data(), signature());
       }
diff --git a/src/lib/prov/openssl/openssl_rsa.cpp b/src/lib/prov/openssl/openssl_rsa.cpp
index 5405ddda1..defa566f0 100644
--- a/src/lib/prov/openssl/openssl_rsa.cpp
+++ b/src/lib/prov/openssl/openssl_rsa.cpp
@@ -228,28 +228,16 @@ class OpenSSL_RSA_Signing_Operation : public PK_Ops::Signature_with_EMSA
 std::unique_ptr<PK_Ops::Encryption>
 make_openssl_rsa_enc_op(const RSA_PublicKey& key, const std::string& params)
    {
-   try
-      {
-      auto pad_info = get_openssl_enc_pad(params);
-      return std::unique_ptr<PK_Ops::Encryption>(
-         new OpenSSL_RSA_Encryption_Operation(key, pad_info.first, pad_info.second));
-      }
-   catch(...) {}
-
-   return {};
+   auto pad_info = get_openssl_enc_pad(params);
+   return std::unique_ptr<PK_Ops::Encryption>(
+      new OpenSSL_RSA_Encryption_Operation(key, pad_info.first, pad_info.second));
    }
 
 std::unique_ptr<PK_Ops::Decryption>
 make_openssl_rsa_dec_op(const RSA_PrivateKey& key, const std::string& params)
    {
-   try
-      {
-      auto pad_info = get_openssl_enc_pad(params);
-      return std::unique_ptr<PK_Ops::Decryption>(new OpenSSL_RSA_Decryption_Operation(key, pad_info.first));
-      }
-   catch(...) {}
-
-   return {};
+   auto pad_info = get_openssl_enc_pad(params);
+   return std::unique_ptr<PK_Ops::Decryption>(new OpenSSL_RSA_Decryption_Operation(key, pad_info.first));
    }
 
 std::unique_ptr<PK_Ops::Verification>
diff --git a/src/lib/prov/pkcs11/p11_ecdsa.cpp b/src/lib/prov/pkcs11/p11_ecdsa.cpp
index 9e21a3701..c406fe553 100644
--- a/src/lib/prov/pkcs11/p11_ecdsa.cpp
+++ b/src/lib/prov/pkcs11/p11_ecdsa.cpp
@@ -201,17 +201,16 @@ class PKCS11_ECDSA_Verification_Operation : public PK_Ops::Verification
 }
 
 std::unique_ptr<PK_Ops::Verification>
-PKCS11_ECDSA_PublicKey::create_verification_op(RandomNumberGenerator& rng,
-                                        const std::string& params,
-                                        const std::string& provider) const
+PKCS11_ECDSA_PublicKey::create_verification_op(const std::string& params,
+                                               const std::string& /*provider*/) const
    {
    return std::unique_ptr<PK_Ops::Verification>(new PKCS11_ECDSA_Verification_Operation(*this, params));
    }
 
 std::unique_ptr<PK_Ops::Signature>
-PKCS11_ECDSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
-                                      const std::string& params,
-                                      const std::string& provider) const
+PKCS11_ECDSA_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
+                                             const std::string& params,
+                                             const std::string& /*provider*/) const
    {
    return std::unique_ptr<PK_Ops::Signature>(new PKCS11_ECDSA_Signature_Operation(*this, params));
    }
diff --git a/src/lib/prov/pkcs11/p11_ecdsa.h b/src/lib/prov/pkcs11/p11_ecdsa.h
index d391ce0b9..aab56f1f2 100644
--- a/src/lib/prov/pkcs11/p11_ecdsa.h
+++ b/src/lib/prov/pkcs11/p11_ecdsa.h
@@ -57,8 +57,7 @@ class BOTAN_DLL PKCS11_ECDSA_PublicKey final : public PKCS11_EC_PublicKey, publi
       ECDSA_PublicKey export_key() const;
 
       std::unique_ptr<PK_Ops::Verification>
-         create_verification_op(RandomNumberGenerator& rng,
-                                const std::string& params,
+         create_verification_op(const std::string& params,
                                 const std::string& provider) const override;
    };
 
diff --git a/src/lib/prov/pkcs11/p11_rsa.cpp b/src/lib/prov/pkcs11/p11_rsa.cpp
index 18965fd95..c048d9d22 100644
--- a/src/lib/prov/pkcs11/p11_rsa.cpp
+++ b/src/lib/prov/pkcs11/p11_rsa.cpp
@@ -358,8 +358,7 @@ PKCS11_RSA_PublicKey::create_encryption_op(RandomNumberGenerator& /*rng*/,
    }
 
 std::unique_ptr<PK_Ops::Verification>
-PKCS11_RSA_PublicKey::create_verification_op(RandomNumberGenerator& /*rng*/,
-                                             const std::string& params,
+PKCS11_RSA_PublicKey::create_verification_op(const std::string& params,
                                              const std::string& /*provider*/) const
    {
    return std::unique_ptr<PK_Ops::Verification>(new PKCS11_RSA_Verification_Operation(*this, params));
diff --git a/src/lib/prov/pkcs11/p11_rsa.h b/src/lib/prov/pkcs11/p11_rsa.h
index 6a085a7d7..6d80e45a7 100644
--- a/src/lib/prov/pkcs11/p11_rsa.h
+++ b/src/lib/prov/pkcs11/p11_rsa.h
@@ -90,8 +90,7 @@ class BOTAN_DLL PKCS11_RSA_PublicKey final : public RSA_PublicKey,
                               const std::string& provider) const override;
 
       std::unique_ptr<PK_Ops::Verification>
-         create_verification_op(RandomNumberGenerator& rng,
-                                const std::string& params,
+         create_verification_op(const std::string& params,
                                 const std::string& provider) const override;
    };
 
diff --git a/src/lib/prov/tpm/tpm.cpp b/src/lib/prov/tpm/tpm.cpp
index 73eb063ce..20334d75d 100644
--- a/src/lib/prov/tpm/tpm.cpp
+++ b/src/lib/prov/tpm/tpm.cpp
@@ -443,9 +443,9 @@ class TPM_Signing_Operation : public PK_Ops::Signature
 }
 
 std::unique_ptr<PK_Ops::Signature>
-TPM_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
+TPM_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
                                     const std::string& params,
-                                    const std::string& provider) const
+                                    const std::string& /*provider*/) const
    {
    return std::unique_ptr<PK_Ops::Signature>(new TPM_Signing_Operation(*this, params));
    }
diff --git a/src/lib/pubkey/curve25519/curve25519.cpp b/src/lib/pubkey/curve25519/curve25519.cpp
index b1dfc59a1..02ee516de 100644
--- a/src/lib/pubkey/curve25519/curve25519.cpp
+++ b/src/lib/pubkey/curve25519/curve25519.cpp
@@ -139,9 +139,11 @@ class Curve25519_KA_Operation : public PK_Ops::Key_Agreement_with_KDF
 std::unique_ptr<PK_Ops::Key_Agreement>
 Curve25519_PrivateKey::create_key_agreement_op(RandomNumberGenerator& /*rng*/,
                                                const std::string& params,
-                                               const std::string& /*provider*/) const
+                                               const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::Key_Agreement>(new Curve25519_KA_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Key_Agreement>(new Curve25519_KA_Operation(*this, params));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 }
diff --git a/src/lib/pubkey/dh/dh.cpp b/src/lib/pubkey/dh/dh.cpp
index 3cd47c581..19ead1b11 100644
--- a/src/lib/pubkey/dh/dh.cpp
+++ b/src/lib/pubkey/dh/dh.cpp
@@ -129,9 +129,11 @@ secure_vector<byte> DH_KA_Operation::raw_agree(const byte w[], size_t w_len)
 std::unique_ptr<PK_Ops::Key_Agreement>
 DH_PrivateKey::create_key_agreement_op(RandomNumberGenerator& rng,
                                        const std::string& params,
-                                       const std::string& /*provider*/) const
+                                       const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::Key_Agreement>(new DH_KA_Operation(*this, params, rng));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Key_Agreement>(new DH_KA_Operation(*this, params, rng));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 }
diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp
index 00d7b77d7..15dc45373 100644
--- a/src/lib/pubkey/dsa/dsa.cpp
+++ b/src/lib/pubkey/dsa/dsa.cpp
@@ -198,19 +198,22 @@ bool DSA_Verification_Operation::verify(const byte msg[], size_t msg_len,
 }
 
 std::unique_ptr<PK_Ops::Verification>
-DSA_PublicKey::create_verification_op(RandomNumberGenerator& rng,
-                                      const std::string& params,
+DSA_PublicKey::create_verification_op(const std::string& params,
                                       const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::Verification>(new DSA_Verification_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Verification>(new DSA_Verification_Operation(*this, params));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 std::unique_ptr<PK_Ops::Signature>
-DSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
+DSA_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
                                     const std::string& params,
                                     const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::Signature>(new DSA_Signature_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Signature>(new DSA_Signature_Operation(*this, params));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 }
diff --git a/src/lib/pubkey/dsa/dsa.h b/src/lib/pubkey/dsa/dsa.h
index d8cd61df5..57c7b7c5c 100644
--- a/src/lib/pubkey/dsa/dsa.h
+++ b/src/lib/pubkey/dsa/dsa.h
@@ -34,8 +34,7 @@ class BOTAN_DLL DSA_PublicKey : public virtual DL_Scheme_PublicKey
       DSA_PublicKey(const DL_Group& group, const BigInt& y);
 
       std::unique_ptr<PK_Ops::Verification>
-         create_verification_op(RandomNumberGenerator& rng,
-                                const std::string& params,
+         create_verification_op(const std::string& params,
                                 const std::string& provider) const override;
    protected:
       DSA_PublicKey() {}
@@ -61,7 +60,7 @@ class BOTAN_DLL DSA_PrivateKey : public DSA_PublicKey,
       std::unique_ptr<PK_Ops::Signature>
          create_signature_op(RandomNumberGenerator& rng,
                              const std::string& params,
-                             const std::string& provider) const;
+                             const std::string& provider) const override;
    };
 
 }
diff --git a/src/lib/pubkey/ecdh/ecdh.cpp b/src/lib/pubkey/ecdh/ecdh.cpp
index 79c63da8c..a4791e15e 100644
--- a/src/lib/pubkey/ecdh/ecdh.cpp
+++ b/src/lib/pubkey/ecdh/ecdh.cpp
@@ -39,6 +39,7 @@ class ECDH_KA_Operation : public PK_Ops::Key_Agreement_with_KDF
       secure_vector<byte> raw_agree(const byte w[], size_t w_len) override
          {
          PointGFp point = OS2ECP(w, w_len, m_curve);
+         // TODO: add blinding
          PointGFp S = (m_cofactor * point) * m_l_times_priv;
          BOTAN_ASSERT(S.on_the_curve(), "ECDH agreed value was on the curve");
          return BigInt::encode_1363(S.get_affine_x(), m_curve.get_p().bytes());
@@ -57,15 +58,24 @@ ECDH_PrivateKey::create_key_agreement_op(RandomNumberGenerator& /*rng*/,
                                          const std::string& provider) const
    {
 #if defined(BOTAN_HAS_OPENSSL)
-   if(provider == "openssl")
+   if(provider == "openssl" || provider.empty())
       {
-      std::unique_ptr<PK_Ops::Key_Agreement> res = make_openssl_ecdh_ka_op(*this, params);
-      if(res)
-         return res;
+      try
+         {
+         return make_openssl_ecdh_ka_op(*this, params);
+         }
+      catch(Exception& e)
+         {
+         if(provider == "openssl")
+            throw Exception("OpenSSL ECDH refused key or params", e.what());
+         }
       }
 #endif
 
-   return std::unique_ptr<PK_Ops::Key_Agreement>(new ECDH_KA_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Key_Agreement>(new ECDH_KA_Operation(*this, params));
+
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 
diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp
index 6a81ababf..f93fcc7a5 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.cpp
+++ b/src/lib/pubkey/ecdsa/ecdsa.cpp
@@ -159,36 +159,54 @@ bool ECDSA_Verification_Operation::verify(const byte msg[], size_t msg_len,
 }
 
 std::unique_ptr<PK_Ops::Verification>
-ECDSA_PublicKey::create_verification_op(RandomNumberGenerator& rng,
-                                        const std::string& params,
+ECDSA_PublicKey::create_verification_op(const std::string& params,
                                         const std::string& provider) const
    {
 #if defined(BOTAN_HAS_OPENSSL)
-   if(provider == "openssl")
+   if(provider == "openssl" || provider.empty())
       {
-      std::unique_ptr<PK_Ops::Verification> res = make_openssl_ecdsa_ver_op(*this, params);
-      if(res)
-         return res;
+      try
+         {
+         return make_openssl_ecdsa_ver_op(*this, params);
+         }
+      catch(Exception& e)
+         {
+         if(provider == "openssl")
+            throw Exception("OpenSSL provider refused ECDSA pubkey", e.what());
+         }
       }
 #endif
-   return std::unique_ptr<PK_Ops::Verification>(new ECDSA_Verification_Operation(*this, params));
+
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Verification>(new ECDSA_Verification_Operation(*this, params));
+
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 std::unique_ptr<PK_Ops::Signature>
-ECDSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
+ECDSA_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
                                       const std::string& params,
                                       const std::string& provider) const
    {
 #if defined(BOTAN_HAS_OPENSSL)
-   if(provider == "openssl")
+   if(provider == "openssl" || provider.empty())
       {
-      std::unique_ptr<PK_Ops::Signature> res = make_openssl_ecdsa_sig_op(*this, params);
-      if(res)
-         return res;
+      try
+         {
+         return make_openssl_ecdsa_sig_op(*this, params);
+         }
+      catch(Exception& e)
+         {
+         if(provider == "openssl")
+            throw Exception("OpenSSL provider refused ECDSA privkey", e.what());
+         }
       }
 #endif
 
-   return std::unique_ptr<PK_Ops::Signature>(new ECDSA_Signature_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Signature>(new ECDSA_Signature_Operation(*this, params));
+
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 }
diff --git a/src/lib/pubkey/ecdsa/ecdsa.h b/src/lib/pubkey/ecdsa/ecdsa.h
index 9a55fbe48..d9dcacd06 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.h
+++ b/src/lib/pubkey/ecdsa/ecdsa.h
@@ -54,8 +54,7 @@ class BOTAN_DLL ECDSA_PublicKey : public virtual EC_PublicKey
          { return domain().get_order().bytes(); }
 
       std::unique_ptr<PK_Ops::Verification>
-         create_verification_op(RandomNumberGenerator& rng,
-                                const std::string& params,
+         create_verification_op(const std::string& params,
                                 const std::string& provider) const override;
    protected:
       ECDSA_PublicKey() {}
@@ -94,7 +93,7 @@ class BOTAN_DLL ECDSA_PrivateKey : public ECDSA_PublicKey,
       std::unique_ptr<PK_Ops::Signature>
          create_signature_op(RandomNumberGenerator& rng,
                              const std::string& params,
-                             const std::string& provider) const;
+                             const std::string& provider) const override;
    };
 
 }
diff --git a/src/lib/pubkey/ecgdsa/ecgdsa.cpp b/src/lib/pubkey/ecgdsa/ecgdsa.cpp
index b112a4466..136f2159a 100644
--- a/src/lib/pubkey/ecgdsa/ecgdsa.cpp
+++ b/src/lib/pubkey/ecgdsa/ecgdsa.cpp
@@ -141,19 +141,22 @@ bool ECGDSA_Verification_Operation::verify(const byte msg[], size_t msg_len,
 }
 
 std::unique_ptr<PK_Ops::Verification>
-ECGDSA_PublicKey::create_verification_op(RandomNumberGenerator& rng,
-                                         const std::string& params,
+ECGDSA_PublicKey::create_verification_op(const std::string& params,
                                          const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::Verification>(new ECGDSA_Verification_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Verification>(new ECGDSA_Verification_Operation(*this, params));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 std::unique_ptr<PK_Ops::Signature>
-ECGDSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
+ECGDSA_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
                                        const std::string& params,
                                        const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::Signature>(new ECGDSA_Signature_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Signature>(new ECGDSA_Signature_Operation(*this, params));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 }
diff --git a/src/lib/pubkey/ecgdsa/ecgdsa.h b/src/lib/pubkey/ecgdsa/ecgdsa.h
index ec9180ee5..203e8d0a8 100644
--- a/src/lib/pubkey/ecgdsa/ecgdsa.h
+++ b/src/lib/pubkey/ecgdsa/ecgdsa.h
@@ -52,8 +52,7 @@ class BOTAN_DLL ECGDSA_PublicKey : public virtual EC_PublicKey
          { return domain().get_order().bytes(); }
 
       std::unique_ptr<PK_Ops::Verification>
-         create_verification_op(RandomNumberGenerator& rng,
-                                const std::string& params,
+         create_verification_op(const std::string& params,
                                 const std::string& provider) const override;
    protected:
       ECGDSA_PublicKey() {}
@@ -92,7 +91,7 @@ class BOTAN_DLL ECGDSA_PrivateKey : public ECGDSA_PublicKey,
       std::unique_ptr<PK_Ops::Signature>
          create_signature_op(RandomNumberGenerator& rng,
                              const std::string& params,
-                             const std::string& provider) const;
+                             const std::string& provider) const override;
    };
 
 }
diff --git a/src/lib/pubkey/eckcdsa/eckcdsa.cpp b/src/lib/pubkey/eckcdsa/eckcdsa.cpp
index e61ceaa19..5375d047a 100644
--- a/src/lib/pubkey/eckcdsa/eckcdsa.cpp
+++ b/src/lib/pubkey/eckcdsa/eckcdsa.cpp
@@ -196,19 +196,22 @@ bool ECKCDSA_Verification_Operation::verify(const byte msg[], size_t,
 }
 
 std::unique_ptr<PK_Ops::Verification>
-ECKCDSA_PublicKey::create_verification_op(RandomNumberGenerator& rng,
-                                         const std::string& params,
+ECKCDSA_PublicKey::create_verification_op(const std::string& params,
                                          const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::Verification>(new ECKCDSA_Verification_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Verification>(new ECKCDSA_Verification_Operation(*this, params));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 std::unique_ptr<PK_Ops::Signature>
-ECKCDSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
-                                       const std::string& params,
-                                       const std::string& provider) const
+ECKCDSA_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
+                                        const std::string& params,
+                                        const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::Signature>(new ECKCDSA_Signature_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Signature>(new ECKCDSA_Signature_Operation(*this, params));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 }
diff --git a/src/lib/pubkey/eckcdsa/eckcdsa.h b/src/lib/pubkey/eckcdsa/eckcdsa.h
index f8514776b..09ee34ed5 100644
--- a/src/lib/pubkey/eckcdsa/eckcdsa.h
+++ b/src/lib/pubkey/eckcdsa/eckcdsa.h
@@ -52,8 +52,7 @@ class BOTAN_DLL ECKCDSA_PublicKey : public virtual EC_PublicKey
          { return domain().get_order().bytes(); }
 
       std::unique_ptr<PK_Ops::Verification>
-         create_verification_op(RandomNumberGenerator& rng,
-                                const std::string& params,
+         create_verification_op(const std::string& params,
                                 const std::string& provider) const override;
    protected:
       ECKCDSA_PublicKey() {}
@@ -92,7 +91,7 @@ class BOTAN_DLL ECKCDSA_PrivateKey : public ECKCDSA_PublicKey,
       std::unique_ptr<PK_Ops::Signature>
          create_signature_op(RandomNumberGenerator& rng,
                              const std::string& params,
-                             const std::string& provider) const;
+                             const std::string& provider) const override;
    };
 
 }
diff --git a/src/lib/pubkey/elgamal/elgamal.cpp b/src/lib/pubkey/elgamal/elgamal.cpp
index fbbd09226..046c2c3f6 100644
--- a/src/lib/pubkey/elgamal/elgamal.cpp
+++ b/src/lib/pubkey/elgamal/elgamal.cpp
@@ -186,17 +186,21 @@ ElGamal_Decryption_Operation::raw_decrypt(const byte msg[], size_t msg_len)
 std::unique_ptr<PK_Ops::Encryption>
 ElGamal_PublicKey::create_encryption_op(RandomNumberGenerator& /*rng*/,
                                         const std::string& params,
-                                        const std::string& /*provider*/) const
+                                        const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::Encryption>(new ElGamal_Encryption_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Encryption>(new ElGamal_Encryption_Operation(*this, params));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 std::unique_ptr<PK_Ops::Decryption>
 ElGamal_PrivateKey::create_decryption_op(RandomNumberGenerator& rng,
                                          const std::string& params,
-                                         const std::string& /*provider*/) const
+                                         const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::Decryption>(new ElGamal_Decryption_Operation(*this, params, rng));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Decryption>(new ElGamal_Decryption_Operation(*this, params, rng));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 }
diff --git a/src/lib/pubkey/gost_3410/gost_3410.cpp b/src/lib/pubkey/gost_3410/gost_3410.cpp
index c37c8c845..7fde29bc5 100644
--- a/src/lib/pubkey/gost_3410/gost_3410.cpp
+++ b/src/lib/pubkey/gost_3410/gost_3410.cpp
@@ -214,19 +214,22 @@ bool GOST_3410_Verification_Operation::verify(const byte msg[], size_t msg_len,
 }
 
 std::unique_ptr<PK_Ops::Verification>
-GOST_3410_PublicKey::create_verification_op(RandomNumberGenerator& rng,
-                                            const std::string& params,
+GOST_3410_PublicKey::create_verification_op(const std::string& params,
                                             const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::Verification>(new GOST_3410_Verification_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Verification>(new GOST_3410_Verification_Operation(*this, params));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 std::unique_ptr<PK_Ops::Signature>
-GOST_3410_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
+GOST_3410_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
                                           const std::string& params,
                                           const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::Signature>(new GOST_3410_Signature_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Signature>(new GOST_3410_Signature_Operation(*this, params));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 }
diff --git a/src/lib/pubkey/gost_3410/gost_3410.h b/src/lib/pubkey/gost_3410/gost_3410.h
index 9d79f48d7..cca811896 100644
--- a/src/lib/pubkey/gost_3410/gost_3410.h
+++ b/src/lib/pubkey/gost_3410/gost_3410.h
@@ -60,8 +60,7 @@ class BOTAN_DLL GOST_3410_PublicKey : public virtual EC_PublicKey
          { return domain().get_order().bytes(); }
 
       std::unique_ptr<PK_Ops::Verification>
-         create_verification_op(RandomNumberGenerator& rng,
-                                const std::string& params,
+         create_verification_op(const std::string& params,
                                 const std::string& provider) const override;
 
    protected:
@@ -97,7 +96,7 @@ class BOTAN_DLL GOST_3410_PrivateKey : public GOST_3410_PublicKey,
       std::unique_ptr<PK_Ops::Signature>
          create_signature_op(RandomNumberGenerator& rng,
                              const std::string& params,
-                             const std::string& provider) const;
+                             const std::string& provider) const override;
    };
 
 }
diff --git a/src/lib/pubkey/keypair/keypair.cpp b/src/lib/pubkey/keypair/keypair.cpp
index 6ea514d34..2efd40b6e 100644
--- a/src/lib/pubkey/keypair/keypair.cpp
+++ b/src/lib/pubkey/keypair/keypair.cpp
@@ -49,7 +49,7 @@ bool signature_consistency_check(RandomNumberGenerator& rng,
                                  const std::string& padding)
    {
    PK_Signer signer(key, rng, padding);
-   PK_Verifier verifier(key, rng, padding);
+   PK_Verifier verifier(key, padding);
 
    std::vector<byte> message = unlock(rng.random_vec(16));
 
diff --git a/src/lib/pubkey/mce/mceliece_key.cpp b/src/lib/pubkey/mce/mceliece_key.cpp
index b5eed5a38..c65322348 100644
--- a/src/lib/pubkey/mce/mceliece_key.cpp
+++ b/src/lib/pubkey/mce/mceliece_key.cpp
@@ -356,17 +356,21 @@ class MCE_KEM_Decryptor : public PK_Ops::KEM_Decryption_with_KDF
 std::unique_ptr<PK_Ops::KEM_Encryption>
 McEliece_PublicKey::create_kem_encryption_op(RandomNumberGenerator& /*rng*/,
                                              const std::string& params,
-                                             const std::string& /*provider*/) const
+                                             const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::KEM_Encryption>(new MCE_KEM_Encryptor(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::KEM_Encryption>(new MCE_KEM_Encryptor(*this, params));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 std::unique_ptr<PK_Ops::KEM_Decryption>
 McEliece_PrivateKey::create_kem_decryption_op(RandomNumberGenerator& /*rng*/,
                                               const std::string& params,
-                                              const std::string& /*provider*/) const
+                                              const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::KEM_Decryption>(new MCE_KEM_Decryptor(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::KEM_Decryption>(new MCE_KEM_Decryptor(*this, params));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 }
diff --git a/src/lib/pubkey/pk_keys.cpp b/src/lib/pubkey/pk_keys.cpp
index ff57d88cc..21b56ed81 100644
--- a/src/lib/pubkey/pk_keys.cpp
+++ b/src/lib/pubkey/pk_keys.cpp
@@ -96,8 +96,7 @@ Public_Key::create_kem_encryption_op(RandomNumberGenerator& /*rng*/,
    }
 
 std::unique_ptr<PK_Ops::Verification>
-Public_Key::create_verification_op(RandomNumberGenerator& /*rng*/,
-                                   const std::string& /*params*/,
+Public_Key::create_verification_op(const std::string& /*params*/,
                                    const std::string& /*provider*/) const
    {
    throw Lookup_Error(algo_name() + " does not support verification");
diff --git a/src/lib/pubkey/pk_keys.h b/src/lib/pubkey/pk_keys.h
index 9de884103..13d94c085 100644
--- a/src/lib/pubkey/pk_keys.h
+++ b/src/lib/pubkey/pk_keys.h
@@ -122,14 +122,9 @@ class BOTAN_DLL Public_Key
 
       /**
       * Return a verification operation for this key/params or throw
-      *
-      * @param rng a random number generator. The PK_Op may maintain a
-      * reference to the RNG and use it many times. The rng must outlive
-      * any operations which reference it.
       */
       virtual std::unique_ptr<PK_Ops::Verification>
-         create_verification_op(RandomNumberGenerator& rng,
-                                const std::string& params,
+         create_verification_op(const std::string& params,
                                 const std::string& provider) const;
 
       virtual ~Public_Key() {}
diff --git a/src/lib/pubkey/pubkey.cpp b/src/lib/pubkey/pubkey.cpp
index 51869326a..fa5777bde 100644
--- a/src/lib/pubkey/pubkey.cpp
+++ b/src/lib/pubkey/pubkey.cpp
@@ -252,12 +252,11 @@ std::vector<byte> PK_Signer::signature(RandomNumberGenerator& rng)
    }
 
 PK_Verifier::PK_Verifier(const Public_Key& key,
-                         RandomNumberGenerator& rng,
                          const std::string& emsa,
                          Signature_Format format,
                          const std::string& provider)
    {
-   m_op = key.create_verification_op(rng, emsa, provider);
+   m_op = key.create_verification_op(emsa, provider);
    BOTAN_ASSERT_NONNULL(m_op);
    m_sig_format = format;
    }
diff --git a/src/lib/pubkey/pubkey.h b/src/lib/pubkey/pubkey.h
index 18b5d0f9b..077796a5d 100644
--- a/src/lib/pubkey/pubkey.h
+++ b/src/lib/pubkey/pubkey.h
@@ -281,27 +281,10 @@ class BOTAN_DLL PK_Verifier
       * @param format the signature format to use
       */
       PK_Verifier(const Public_Key& pub_key,
-                  RandomNumberGenerator& rng,
                   const std::string& emsa,
                   Signature_Format format = IEEE_1363,
                   const std::string& provider = "");
 
-#if defined(BOTAN_PUBKEY_INCLUDE_DEPRECATED_CONSTRUCTORS)
-      /**
-      * Construct a PK Verifier.
-      * @param pub_key the public key to verify against
-      * @param emsa the EMSA to use (eg "EMSA3(SHA-1)")
-      * @param format the signature format to use
-      */
-      BOTAN_DEPRECATED("Use constructor taking a RNG object")
-      PK_Verifier(const Public_Key& pub_key,
-                  const std::string& emsa,
-                  Signature_Format format = IEEE_1363,
-                  const std::string& provider = "") :
-         PK_Verifier(pub_key, system_rng(), emsa, format, provider)
-         {}
-#endif
-
       /**
       * Verify a signature.
       * @param msg the message that the signature belongs to, as a byte array
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index c8d1e7afc..b40f485e3 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -406,37 +406,51 @@ class RSA_KEM_Encryption_Operation : public PK_Ops::KEM_Encryption_with_KDF,
 }
 
 std::unique_ptr<PK_Ops::Encryption>
-RSA_PublicKey::create_encryption_op(RandomNumberGenerator& rng,
+RSA_PublicKey::create_encryption_op(RandomNumberGenerator& /*rng*/,
                                     const std::string& params,
                                     const std::string& provider) const
    {
 #if defined(BOTAN_HAS_OPENSSL)
-   if(provider == "openssl")
+   if(provider == "openssl" || provider.empty())
       {
-      std::unique_ptr<PK_Ops::Encryption> res = make_openssl_rsa_enc_op(*this, params);
-      if(res)
-         return res;
+      try
+         {
+         return make_openssl_rsa_enc_op(*this, params);
+         }
+      catch(Exception& e)
+         {
+         /*
+         * If OpenSSL for some reason could not handle this (eg due to OAEP params),
+         * throw if openssl was specifically requested but otherwise just fall back
+         * to the normal version.
+         */
+         if(provider == "openssl")
+            throw Exception("OpenSSL RSA provider rejected key:", e.what());
+         }
       }
 #endif
 
-   return std::unique_ptr<PK_Ops::Encryption>(new RSA_Encryption_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Encryption>(new RSA_Encryption_Operation(*this, params));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 std::unique_ptr<PK_Ops::KEM_Encryption>
-RSA_PublicKey::create_kem_encryption_op(RandomNumberGenerator& rng,
+RSA_PublicKey::create_kem_encryption_op(RandomNumberGenerator& /*rng*/,
                                         const std::string& params,
-                                        const std::string& /*provider*/) const
+                                        const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::KEM_Encryption>(new RSA_KEM_Encryption_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::KEM_Encryption>(new RSA_KEM_Encryption_Operation(*this, params));
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 std::unique_ptr<PK_Ops::Verification>
-RSA_PublicKey::create_verification_op(RandomNumberGenerator& rng,
-                                      const std::string& params,
+RSA_PublicKey::create_verification_op(const std::string& params,
                                       const std::string& provider) const
    {
 #if defined(BOTAN_HAS_OPENSSL)
-   if(provider == "openssl")
+   if(provider == "openssl" || provider.empty())
       {
       std::unique_ptr<PK_Ops::Verification> res = make_openssl_rsa_ver_op(*this, params);
       if(res)
@@ -444,7 +458,10 @@ RSA_PublicKey::create_verification_op(RandomNumberGenerator& rng,
       }
 #endif
 
-   return std::unique_ptr<PK_Ops::Verification>(new RSA_Verify_Operation(*this, params));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Verification>(new RSA_Verify_Operation(*this, params));
+
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 std::unique_ptr<PK_Ops::Decryption>
@@ -453,23 +470,35 @@ RSA_PrivateKey::create_decryption_op(RandomNumberGenerator& rng,
                                      const std::string& provider) const
    {
 #if defined(BOTAN_HAS_OPENSSL)
-   if(provider == "openssl")
+   if(provider == "openssl" || provider.empty())
       {
-      std::unique_ptr<PK_Ops::Decryption> res = make_openssl_rsa_dec_op(*this, params);
-      if(res)
-         return res;
+      try
+         {
+         return make_openssl_rsa_dec_op(*this, params);
+         }
+      catch(Exception& e)
+         {
+         if(provider == "openssl")
+            throw Exception("OpenSSL RSA provider rejected key:", e.what());
+         }
       }
 #endif
 
-   return std::unique_ptr<PK_Ops::Decryption>(new RSA_Decryption_Operation(*this, params, rng));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Decryption>(new RSA_Decryption_Operation(*this, params, rng));
+
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 std::unique_ptr<PK_Ops::KEM_Decryption>
 RSA_PrivateKey::create_kem_decryption_op(RandomNumberGenerator& rng,
                                          const std::string& params,
-                                         const std::string& /*provider*/) const
+                                         const std::string& provider) const
    {
-   return std::unique_ptr<PK_Ops::KEM_Decryption>(new RSA_KEM_Decryption_Operation(*this, params, rng));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::KEM_Decryption>(new RSA_KEM_Decryption_Operation(*this, params, rng));
+
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 std::unique_ptr<PK_Ops::Signature>
@@ -478,7 +507,7 @@ RSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
                                     const std::string& provider) const
    {
 #if defined(BOTAN_HAS_OPENSSL)
-   if(provider == "openssl")
+   if(provider == "openssl" || provider.empty())
       {
       std::unique_ptr<PK_Ops::Signature> res = make_openssl_rsa_sig_op(*this, params);
       if(res)
@@ -486,7 +515,10 @@ RSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
       }
 #endif
 
-   return std::unique_ptr<PK_Ops::Signature>(new RSA_Signature_Operation(*this, params, rng));
+   if(provider == "base" || provider.empty())
+      return std::unique_ptr<PK_Ops::Signature>(new RSA_Signature_Operation(*this, params, rng));
+
+   throw Provider_Not_Found(algo_name(), provider);
    }
 
 }
diff --git a/src/lib/pubkey/rsa/rsa.h b/src/lib/pubkey/rsa/rsa.h
index 203a3a323..ddfd23b05 100644
--- a/src/lib/pubkey/rsa/rsa.h
+++ b/src/lib/pubkey/rsa/rsa.h
@@ -63,8 +63,7 @@ class BOTAN_DLL RSA_PublicKey : public virtual Public_Key
                                   const std::string& provider) const override;
 
       std::unique_ptr<PK_Ops::Verification>
-         create_verification_op(RandomNumberGenerator& rng,
-                                const std::string& params,
+         create_verification_op(const std::string& params,
                                 const std::string& provider) const override;
 
    protected:
diff --git a/src/lib/tls/msg_cert_verify.cpp b/src/lib/tls/msg_cert_verify.cpp
index cc162f8a0..ac8fa97fd 100644
--- a/src/lib/tls/msg_cert_verify.cpp
+++ b/src/lib/tls/msg_cert_verify.cpp
@@ -78,8 +78,7 @@ std::vector<byte> Certificate_Verify::serialize() const
 */
 bool Certificate_Verify::verify(const X509_Certificate& cert,
                                 const Handshake_State& state,
-                                const Policy& policy,
-                                RandomNumberGenerator& rng) const
+                                const Policy& policy) const
    {
    std::unique_ptr<Public_Key> key(cert.subject_public_key());
 
@@ -89,7 +88,7 @@ bool Certificate_Verify::verify(const X509_Certificate& cert,
       state.parse_sig_format(*key.get(), m_hash_algo, m_sig_algo,
                              true, policy);
 
-   PK_Verifier verifier(*key, rng, format.first, format.second);
+   PK_Verifier verifier(*key, format.first, format.second);
 
    return verifier.verify_message(state.hash().get_contents(), m_signature);
    }
diff --git a/src/lib/tls/msg_server_kex.cpp b/src/lib/tls/msg_server_kex.cpp
index 3df23955b..325e5d1b0 100644
--- a/src/lib/tls/msg_server_kex.cpp
+++ b/src/lib/tls/msg_server_kex.cpp
@@ -237,8 +237,7 @@ std::vector<byte> Server_Key_Exchange::serialize() const
 */
 bool Server_Key_Exchange::verify(const Public_Key& server_key,
                                  const Handshake_State& state,
-                                 const Policy& policy,
-                                 RandomNumberGenerator& rng) const
+                                 const Policy& policy) const
    {
    policy.check_peer_key_acceptable(server_key);
 
@@ -246,7 +245,7 @@ bool Server_Key_Exchange::verify(const Public_Key& server_key,
       state.parse_sig_format(server_key, m_hash_algo, m_sig_algo,
                              false, policy);
 
-   PK_Verifier verifier(server_key, rng, format.first, format.second);
+   PK_Verifier verifier(server_key, format.first, format.second);
 
    verifier.update(state.client_hello()->random());
    verifier.update(state.server_hello()->random());
diff --git a/src/lib/tls/tls_client.cpp b/src/lib/tls/tls_client.cpp
index 6bfbdc008..0e72b9a28 100644
--- a/src/lib/tls/tls_client.cpp
+++ b/src/lib/tls/tls_client.cpp
@@ -415,7 +415,7 @@ void Client::process_handshake_msg(const Handshake_State* active_state,
          {
          const Public_Key& server_key = state.get_server_public_Key();
 
-         if(!state.server_kex()->verify(server_key, state, policy(), rng()))
+         if(!state.server_kex()->verify(server_key, state, policy()))
             {
             throw TLS_Exception(Alert::DECRYPT_ERROR,
                                 "Bad signature on server key exchange");
diff --git a/src/lib/tls/tls_messages.h b/src/lib/tls/tls_messages.h
index 76421bf4a..25228c865 100644
--- a/src/lib/tls/tls_messages.h
+++ b/src/lib/tls/tls_messages.h
@@ -482,8 +482,7 @@ class BOTAN_DLL Certificate_Verify final : public Handshake_Message
       */
       bool verify(const X509_Certificate& cert,
                   const Handshake_State& state,
-                  const Policy& policy,
-                  RandomNumberGenerator& rng) const;
+                  const Policy& policy) const;
 
       Certificate_Verify(Handshake_IO& io,
                          Handshake_State& state,
@@ -552,8 +551,7 @@ class Server_Key_Exchange final : public Handshake_Message
 
       bool verify(const Public_Key& server_key,
                   const Handshake_State& state,
-                  const Policy& policy,
-                  RandomNumberGenerator& rng) const;
+                  const Policy& policy) const;
 
       // Only valid for certain kex types
       const Private_Key& server_kex_key() const;
diff --git a/src/lib/tls/tls_server.cpp b/src/lib/tls/tls_server.cpp
index 510a30421..82e7fad75 100644
--- a/src/lib/tls/tls_server.cpp
+++ b/src/lib/tls/tls_server.cpp
@@ -509,7 +509,7 @@ void Server::process_certificate_verify_msg(Server_Handshake_State& pending_stat
         pending_state.client_certs()->cert_chain();
 
     const bool sig_valid =
-       pending_state.client_verify()->verify ( client_certs[0], pending_state, policy(), rng() );
+       pending_state.client_verify()->verify ( client_certs[0], pending_state, policy() );
 
     pending_state.hash().update ( pending_state.handshake_io().format ( contents, type ) );
 
diff --git a/src/lib/utils/exceptn.h b/src/lib/utils/exceptn.h
index a3cb11f81..bfde49002 100644
--- a/src/lib/utils/exceptn.h
+++ b/src/lib/utils/exceptn.h
@@ -148,6 +148,16 @@ struct BOTAN_DLL No_Provider_Found : public Exception
    };
 
 /**
+* Provider_Not_Found is thrown when a specific provider was requested
+* but that provider is not available.
+*/
+struct BOTAN_DLL Provider_Not_Found : public Lookup_Error
+   {
+   Provider_Not_Found(const std::string& algo, const std::string& provider) :
+      Lookup_Error("Could not find provider '" + provider + "' for " + algo) {}
+   };
+
+/**
 * Invalid_Algorithm_Name Exception
 */
 struct BOTAN_DLL Invalid_Algorithm_Name : public Invalid_Argument