Merge GH #625 Remove static init from PK operations code

Also removes hidden RNG in Blinder (GH #615)

76 files changed, 1350 insertions, 471 deletions

diff --git a/src/cli/pubkey.cpp b/src/cli/pubkey.cpp
index 456ebbc8b..6c0ea8352 100644
--- a/src/cli/pubkey.cpp
+++ b/src/cli/pubkey.cpp
@@ -179,7 +179,7 @@ class PK_Sign final : public Command
          const std::string sig_padding =
             get_arg_or("emsa", algo_default_emsa(key->algo_name())) + "(" + get_arg("hash") + ")";
 
-         Botan::PK_Signer signer(*key, sig_padding);
+         Botan::PK_Signer signer(*key, rng(), sig_padding);
 
          this->read_file(get_arg("file"),
                          [&signer](const uint8_t b[], size_t l) { signer.update(b, l); });
diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index bd087e8e4..d864c5858 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -786,8 +786,8 @@ class Speed final : public Command
          {
          std::vector<uint8_t> plaintext, ciphertext;
 
-         Botan::PK_Encryptor_EME enc(key, padding, provider);
-         Botan::PK_Decryptor_EME dec(key, padding, provider);
+         Botan::PK_Encryptor_EME enc(key, rng(), padding, provider);
+         Botan::PK_Decryptor_EME dec(key, rng(), padding, provider);
 
          Timer enc_timer(nm, provider, padding + " encrypt");
          Timer dec_timer(nm, provider, padding + " decrypt");
@@ -823,8 +823,8 @@ class Speed final : public Command
                        const std::string& kdf,
                        std::chrono::milliseconds msec)
          {
-         Botan::PK_Key_Agreement ka1(key1, kdf, provider);
-         Botan::PK_Key_Agreement ka2(key2, kdf, provider);
+         Botan::PK_Key_Agreement ka1(key1, rng(), kdf, provider);
+         Botan::PK_Key_Agreement ka2(key2, rng(), kdf, provider);
 
          const std::vector<uint8_t> ka1_pub = key1.public_value();
          const std::vector<uint8_t> ka2_pub = key2.public_value();
@@ -851,8 +851,8 @@ class Speed final : public Command
                         const std::string& kdf,
                         std::chrono::milliseconds msec)
          {
-         Botan::PK_KEM_Decryptor dec(key, kdf, provider);
-         Botan::PK_KEM_Encryptor enc(key, kdf, provider);
+         Botan::PK_KEM_Decryptor dec(key, rng(), kdf, provider);
+         Botan::PK_KEM_Encryptor enc(key, rng(), kdf, provider);
 
          Timer kem_enc_timer(nm, provider, "KEM encrypt");
          Timer kem_dec_timer(nm, provider, "KEM decrypt");
@@ -888,7 +888,7 @@ class Speed final : public Command
          {
          std::vector<uint8_t> message, signature, bad_signature;
 
-         Botan::PK_Signer   sig(key, padding, Botan::IEEE_1363, provider);
+         Botan::PK_Signer   sig(key, rng(), padding, Botan::IEEE_1363, provider);
          Botan::PK_Verifier ver(key, padding, Botan::IEEE_1363, provider);
 
          Timer sig_timer(nm, provider, padding + " sign");
diff --git a/src/cli/x509.cpp b/src/cli/x509.cpp
index e65398439..25261a2d1 100644
--- a/src/cli/x509.cpp
+++ b/src/cli/x509.cpp
@@ -47,7 +47,7 @@ class Sign_Cert final : public Command
          if(!key)
             throw CLI_Error("Failed to load key from " + get_arg("ca_key"));
 
-         Botan::X509_CA ca(ca_cert, *key, get_arg("hash"));
+         Botan::X509_CA ca(ca_cert, *key, get_arg("hash"), rng());
 
          Botan::PKCS10_Request req(get_arg("pkcs10_req"));
 
diff --git a/src/lib/cert/x509/x509_ca.cpp b/src/lib/cert/x509/x509_ca.cpp
index 58c6676f4..179d903c4 100644
--- a/src/lib/cert/x509/x509_ca.cpp
+++ b/src/lib/cert/x509/x509_ca.cpp
@@ -26,12 +26,13 @@ namespace Botan {
 */
 X509_CA::X509_CA(const X509_Certificate& c,
                  const Private_Key& key,
-                 const std::string& hash_fn) : m_cert(c)
+                 const std::string& hash_fn,
+                 RandomNumberGenerator& rng) : m_cert(c)
    {
    if(!m_cert.is_CA_cert())
       throw Invalid_Argument("X509_CA: This certificate is not for a CA");
 
-   m_signer = choose_sig_format(key, hash_fn, m_ca_sig_algo);
+   m_signer = choose_sig_format(key, rng, hash_fn, m_ca_sig_algo);
    }
 
 /*
@@ -225,6 +226,7 @@ X509_Certificate X509_CA::ca_certificate() const
 * Choose a signing format for the key
 */
 PK_Signer* choose_sig_format(const Private_Key& key,
+                             RandomNumberGenerator& rng,
                              const std::string& hash_fn,
                              AlgorithmIdentifier& sig_algo)
    {
@@ -258,7 +260,7 @@ PK_Signer* choose_sig_format(const Private_Key& key,
    sig_algo.oid = OIDS::lookup(algo_name + "/" + padding);
    sig_algo.parameters = key.algorithm_identifier().parameters;
 
-   return new PK_Signer(key, padding, format);
+   return new PK_Signer(key, rng, padding, format);
    }
 
 }
diff --git a/src/lib/cert/x509/x509_ca.h b/src/lib/cert/x509/x509_ca.h
index ba3724f5e..218ee0803 100644
--- a/src/lib/cert/x509/x509_ca.h
+++ b/src/lib/cert/x509/x509_ca.h
@@ -14,6 +14,10 @@
 #include <botan/pkcs10.h>
 #include <botan/pubkey.h>
 
+#if defined(BOTAN_HAS_SYSTEM_RNG)
+  #include <botan/system_rng.h>
+#endif
+
 namespace Botan {
 
 /**
@@ -95,7 +99,17 @@ class BOTAN_DLL X509_CA
       */
       X509_CA(const X509_Certificate& ca_certificate,
               const Private_Key& key,
-              const std::string& hash_fn);
+              const std::string& hash_fn,
+              RandomNumberGenerator& rng);
+
+#if defined(BOTAN_HAS_SYSTEM_RNG)
+      BOTAN_DEPRECATED("Use version taking RNG object")
+      X509_CA(const X509_Certificate& ca_certificate,
+              const Private_Key& key,
+              const std::string& hash_fn) :
+         X509_CA(ca_certificate, key, hash_fn, system_rng())
+         {}
+#endif
 
       X509_CA(const X509_CA&) = delete;
       X509_CA& operator=(const X509_CA&) = delete;
@@ -120,6 +134,7 @@ class BOTAN_DLL X509_CA
 * @return A PK_Signer object for generating signatures
 */
 BOTAN_DLL PK_Signer* choose_sig_format(const Private_Key& key,
+                                       RandomNumberGenerator& rng,
                                        const std::string& hash_fn,
                                        AlgorithmIdentifier& alg_id);
 
diff --git a/src/lib/cert/x509/x509self.cpp b/src/lib/cert/x509/x509self.cpp
index 102e24f77..a59632858 100644
--- a/src/lib/cert/x509/x509self.cpp
+++ b/src/lib/cert/x509/x509self.cpp
@@ -50,7 +50,7 @@ X509_Certificate create_self_signed_cert(const X509_Cert_Options& opts,
    AlternativeName subject_alt;
 
    std::vector<byte> pub_key = X509::BER_encode(key);
-   std::unique_ptr<PK_Signer> signer(choose_sig_format(key, hash_fn, sig_algo));
+   std::unique_ptr<PK_Signer> signer(choose_sig_format(key, rng, hash_fn, sig_algo));
    load_info(opts, subject_dn, subject_alt);
 
    Key_Constraints constraints;
@@ -102,7 +102,7 @@ PKCS10_Request create_cert_req(const X509_Cert_Options& opts,
    AlternativeName subject_alt;
 
    std::vector<byte> pub_key = X509::BER_encode(key);
-   std::unique_ptr<PK_Signer> signer(choose_sig_format(key, hash_fn, sig_algo));
+   std::unique_ptr<PK_Signer> signer(choose_sig_format(key, rng, hash_fn, sig_algo));
    load_info(opts, subject_dn, subject_alt);
 
    const size_t PKCS10_VERSION = 0;
diff --git a/src/lib/prov/openssl/openssl.h b/src/lib/prov/openssl/openssl.h
index ebaa2b756..58a7d77dc 100644
--- a/src/lib/prov/openssl/openssl.h
+++ b/src/lib/prov/openssl/openssl.h
@@ -8,9 +8,11 @@
 #ifndef BOTAN_OPENSSL_H__
 #define BOTAN_OPENSSL_H__
 
+#include <botan/internal/pk_ops.h>
 #include <botan/secmem.h>
 #include <botan/exceptn.h>
 #include <memory>
+#include <string>
 
 #include <openssl/err.h>
 
@@ -27,9 +29,50 @@ class OpenSSL_Error : public Exception
 #define BOTAN_OPENSSL_HASH_PRIO  150
 #define BOTAN_OPENSSL_RC4_PRIO   150
 
-#define BOTAN_OPENSSL_RSA_PRIO     90
-#define BOTAN_OPENSSL_ECDSA_PRIO   90
-#define BOTAN_OPENSSL_ECDH_PRIO    90
+/* RSA */
+
+#if defined(BOTAN_HAS_RSA)
+
+class RSA_PublicKey;
+class RSA_PrivateKey;
+
+std::unique_ptr<PK_Ops::Encryption>
+make_openssl_rsa_enc_op(const RSA_PublicKey& key, const std::string& params);
+std::unique_ptr<PK_Ops::Decryption>
+make_openssl_rsa_dec_op(const RSA_PrivateKey& key, const std::string& params);
+
+std::unique_ptr<PK_Ops::Verification>
+make_openssl_rsa_ver_op(const RSA_PublicKey& key, const std::string& params);
+std::unique_ptr<PK_Ops::Signature>
+make_openssl_rsa_sig_op(const RSA_PrivateKey& key, const std::string& params);
+
+#endif
+
+/* ECDSA */
+
+#if defined(BOTAN_HAS_ECDSA)
+
+class ECDSA_PublicKey;
+class ECDSA_PrivateKey;
+
+std::unique_ptr<PK_Ops::Verification>
+make_openssl_ecdsa_ver_op(const ECDSA_PublicKey& key, const std::string& params);
+std::unique_ptr<PK_Ops::Signature>
+make_openssl_ecdsa_sig_op(const ECDSA_PrivateKey& key, const std::string& params);
+
+#endif
+
+/* ECDH */
+
+#if defined(BOTAN_HAS_ECDH)
+
+class ECDH_PrivateKey;
+
+std::unique_ptr<PK_Ops::Key_Agreement>
+make_openssl_ecdh_ka_op(const ECDH_PrivateKey& key, const std::string& params);
+
+#endif
+
 
 }
 
diff --git a/src/lib/prov/openssl/openssl_ec.cpp b/src/lib/prov/openssl/openssl_ec.cpp
index 4378833ec..e127d749b 100644
--- a/src/lib/prov/openssl/openssl_ec.cpp
+++ b/src/lib/prov/openssl/openssl_ec.cpp
@@ -11,7 +11,7 @@
   #include <botan/der_enc.h>
   #include <botan/pkcs8.h>
   #include <botan/oids.h>
-  #include <botan/internal/pk_utils.h>
+  #include <botan/internal/pk_ops_impl.h>
 #endif
 
 #if defined(BOTAN_HAS_ECDSA)
@@ -91,20 +91,6 @@ int OpenSSL_EC_nid_for(const OID& oid)
 class OpenSSL_ECDSA_Verification_Operation : public PK_Ops::Verification_with_EMSA
    {
    public:
-      typedef ECDSA_PublicKey Key_Type;
-
-      static OpenSSL_ECDSA_Verification_Operation* make(const Spec& spec)
-         {
-         if(const ECDSA_PublicKey* ecdsa = dynamic_cast<const ECDSA_PublicKey*>(&spec.key()))
-            {
-            const int nid = OpenSSL_EC_nid_for(ecdsa->domain().get_oid());
-            if(nid > 0)
-               return new OpenSSL_ECDSA_Verification_Operation(*ecdsa, spec.padding(), nid);
-            }
-
-         return nullptr;
-         }
-
       OpenSSL_ECDSA_Verification_Operation(const ECDSA_PublicKey& ecdsa, const std::string& emsa, int nid) :
          PK_Ops::Verification_with_EMSA(emsa), m_ossl_ec(::EC_KEY_new(), ::EC_KEY_free)
          {
@@ -158,20 +144,6 @@ class OpenSSL_ECDSA_Verification_Operation : public PK_Ops::Verification_with_EM
 class OpenSSL_ECDSA_Signing_Operation : public PK_Ops::Signature_with_EMSA
    {
    public:
-      typedef ECDSA_PrivateKey Key_Type;
-
-      static OpenSSL_ECDSA_Signing_Operation* make(const Spec& spec)
-         {
-         if(const ECDSA_PrivateKey* ecdsa = dynamic_cast<const ECDSA_PrivateKey*>(&spec.key()))
-            {
-            const int nid = OpenSSL_EC_nid_for(ecdsa->domain().get_oid());
-            if(nid > 0)
-               return new OpenSSL_ECDSA_Signing_Operation(*ecdsa, spec.padding());
-            }
-
-         return nullptr;
-         }
-
       OpenSSL_ECDSA_Signing_Operation(const ECDSA_PrivateKey& ecdsa, const std::string& emsa) :
          PK_Ops::Signature_with_EMSA(emsa),
          m_ossl_ec(nullptr, ::EC_KEY_free)
@@ -213,35 +185,39 @@ class OpenSSL_ECDSA_Signing_Operation : public PK_Ops::Signature_with_EMSA
       size_t m_order_bits = 0;
    };
 
-BOTAN_REGISTER_TYPE(PK_Ops::Verification, OpenSSL_ECDSA_Verification_Operation, "ECDSA",
-                    OpenSSL_ECDSA_Verification_Operation::make,
-                    "openssl", BOTAN_OPENSSL_ECDSA_PRIO);
+}
+
+std::unique_ptr<PK_Ops::Verification>
+make_openssl_ecdsa_ver_op(const ECDSA_PublicKey& key, const std::string& params)
+   {
+   const int nid = OpenSSL_EC_nid_for(key.domain().get_oid());
+   if(nid > 0)
+      {
+      return std::unique_ptr<PK_Ops::Verification>(new OpenSSL_ECDSA_Verification_Operation(key, params, nid));
+      }
+   return {};
+   }
 
-BOTAN_REGISTER_TYPE(PK_Ops::Signature, OpenSSL_ECDSA_Signing_Operation, "ECDSA",
-                    OpenSSL_ECDSA_Signing_Operation::make,
-                    "openssl", BOTAN_OPENSSL_ECDSA_PRIO);
+std::unique_ptr<PK_Ops::Signature>
+make_openssl_ecdsa_sig_op(const ECDSA_PrivateKey& key, const std::string& params)
+   {
+   const int nid = OpenSSL_EC_nid_for(key.domain().get_oid());
+   if(nid > 0)
+      return std::unique_ptr<PK_Ops::Signature>(new OpenSSL_ECDSA_Signing_Operation(key, params));
+   return {};
+   }
 
 #endif
 
 #if defined(BOTAN_HAS_ECDH) && !defined(OPENSSL_NO_ECDH)
 
+namespace {
+
 class OpenSSL_ECDH_KA_Operation : public PK_Ops::Key_Agreement_with_KDF
    {
    public:
       typedef ECDH_PrivateKey Key_Type;
 
-      static OpenSSL_ECDH_KA_Operation* make(const Spec& spec)
-         {
-         if(const ECDH_PrivateKey* ecdh = dynamic_cast<const ECDH_PrivateKey*>(&spec.key()))
-            {
-            const int nid = OpenSSL_EC_nid_for(ecdh->domain().get_oid());
-            if(nid > 0)
-               return new OpenSSL_ECDH_KA_Operation(*ecdh, spec.padding());
-            }
-
-         return nullptr;
-         }
-
       OpenSSL_ECDH_KA_Operation(const ECDH_PrivateKey& ecdh, const std::string& kdf) :
          PK_Ops::Key_Agreement_with_KDF(kdf), m_ossl_ec(::EC_KEY_new(), ::EC_KEY_free)
          {
@@ -291,13 +267,21 @@ class OpenSSL_ECDH_KA_Operation : public PK_Ops::Key_Agreement_with_KDF
       size_t m_order_bits = 0;
    };
 
-BOTAN_REGISTER_TYPE(PK_Ops::Key_Agreement, OpenSSL_ECDH_KA_Operation, "ECDH",
-                    OpenSSL_ECDH_KA_Operation::make,
-                    "openssl", BOTAN_OPENSSL_ECDH_PRIO);
+}
 
-#endif
+std::unique_ptr<PK_Ops::Key_Agreement>
+make_openssl_ecdh_ka_op(const ECDH_PrivateKey& key, const std::string& params)
+   {
+   const int nid = OpenSSL_EC_nid_for(key.domain().get_oid());
+   if(nid == 0)
+      {
+      throw Lookup_Error("OpenSSL ECDH does not support this curve");
+      }
 
-}
+   return std::unique_ptr<PK_Ops::Key_Agreement>(new OpenSSL_ECDH_KA_Operation(key, params));
+   }
+
+#endif
 
 }
 
diff --git a/src/lib/prov/openssl/openssl_rsa.cpp b/src/lib/prov/openssl/openssl_rsa.cpp
index ed8f2b0fd..ae3f1cce2 100644
--- a/src/lib/prov/openssl/openssl_rsa.cpp
+++ b/src/lib/prov/openssl/openssl_rsa.cpp
@@ -10,7 +10,7 @@
 #if defined(BOTAN_HAS_RSA)
 
 #include <botan/rsa.h>
-#include <botan/internal/pk_utils.h>
+#include <botan/internal/pk_ops_impl.h>
 #include <botan/internal/ct_utils.h>
 
 #include <functional>
@@ -31,7 +31,7 @@ std::pair<int, size_t> get_openssl_enc_pad(const std::string& eme)
       return std::make_pair(RSA_NO_PADDING, 0);
    else if(eme == "EME-PKCS1-v1_5")
       return std::make_pair(RSA_PKCS1_PADDING, 11);
-   else if(eme == "OAEP(SHA-1)")
+   else if(eme == "OAEP(SHA-1)" || eme == "EME1(SHA-1)")
       return std::make_pair(RSA_PKCS1_OAEP_PADDING, 41);
    else
       throw Lookup_Error("OpenSSL RSA does not support EME " + eme);
@@ -42,21 +42,6 @@ class OpenSSL_RSA_Encryption_Operation : public PK_Ops::Encryption
    public:
       typedef RSA_PublicKey Key_Type;
 
-      static OpenSSL_RSA_Encryption_Operation* make(const Spec& spec)
-         {
-         try
-            {
-            if(auto* key = dynamic_cast<const RSA_PublicKey*>(&spec.key()))
-               {
-               auto pad_info = get_openssl_enc_pad(spec.padding());
-               return new OpenSSL_RSA_Encryption_Operation(*key, pad_info.first, pad_info.second);
-               }
-            }
-         catch(...) {}
-
-         return nullptr;
-         }
-
       OpenSSL_RSA_Encryption_Operation(const RSA_PublicKey& rsa, int pad, size_t pad_overhead) :
          m_openssl_rsa(nullptr, ::RSA_free), m_padding(pad)
          {
@@ -113,21 +98,6 @@ class OpenSSL_RSA_Decryption_Operation : public PK_Ops::Decryption
    public:
       typedef RSA_PrivateKey Key_Type;
 
-      static OpenSSL_RSA_Decryption_Operation* make(const Spec& spec)
-         {
-         try
-            {
-            if(auto* key = dynamic_cast<const RSA_PrivateKey*>(&spec.key()))
-               {
-               auto pad_info = get_openssl_enc_pad(spec.padding());
-               return new OpenSSL_RSA_Decryption_Operation(*key, pad_info.first);
-               }
-            }
-         catch(...) {}
-
-         return nullptr;
-         }
-
       OpenSSL_RSA_Decryption_Operation(const RSA_PrivateKey& rsa, int pad) :
          m_openssl_rsa(nullptr, ::RSA_free), m_padding(pad)
          {
@@ -174,16 +144,6 @@ class OpenSSL_RSA_Verification_Operation : public PK_Ops::Verification_with_EMSA
    public:
       typedef RSA_PublicKey Key_Type;
 
-      static OpenSSL_RSA_Verification_Operation* make(const Spec& spec)
-         {
-         if(const RSA_PublicKey* rsa = dynamic_cast<const RSA_PublicKey*>(&spec.key()))
-            {
-            return new OpenSSL_RSA_Verification_Operation(*rsa, spec.padding());
-            }
-
-         return nullptr;
-         }
-
       OpenSSL_RSA_Verification_Operation(const RSA_PublicKey& rsa, const std::string& emsa) :
          PK_Ops::Verification_with_EMSA(emsa),
          m_openssl_rsa(nullptr, ::RSA_free)
@@ -225,16 +185,6 @@ class OpenSSL_RSA_Signing_Operation : public PK_Ops::Signature_with_EMSA
    public:
       typedef RSA_PrivateKey Key_Type;
 
-      static OpenSSL_RSA_Signing_Operation* make(const Spec& spec)
-         {
-         if(const RSA_PrivateKey* rsa = dynamic_cast<const RSA_PrivateKey*>(&spec.key()))
-            {
-            return new OpenSSL_RSA_Signing_Operation(*rsa, spec.padding());
-            }
-
-         return nullptr;
-         }
-
       OpenSSL_RSA_Signing_Operation(const RSA_PrivateKey& rsa, const std::string& emsa) :
          PK_Ops::Signature_with_EMSA(emsa),
          m_openssl_rsa(nullptr, ::RSA_free)
@@ -273,19 +223,34 @@ class OpenSSL_RSA_Signing_Operation : public PK_Ops::Signature_with_EMSA
       std::unique_ptr<RSA, std::function<void (RSA*)>> m_openssl_rsa;
    };
 
-BOTAN_REGISTER_TYPE(PK_Ops::Verification, OpenSSL_RSA_Verification_Operation, "RSA",
-                    OpenSSL_RSA_Verification_Operation::make, "openssl", BOTAN_OPENSSL_RSA_PRIO);
+}
 
-BOTAN_REGISTER_TYPE(PK_Ops::Signature, OpenSSL_RSA_Signing_Operation, "RSA",
-                    OpenSSL_RSA_Signing_Operation::make, "openssl", BOTAN_OPENSSL_RSA_PRIO);
+std::unique_ptr<PK_Ops::Encryption>
+make_openssl_rsa_enc_op(const RSA_PublicKey& key, const std::string& params)
+   {
+   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));
+   }
 
-BOTAN_REGISTER_TYPE(PK_Ops::Encryption, OpenSSL_RSA_Encryption_Operation, "RSA",
-                    OpenSSL_RSA_Encryption_Operation::make, "openssl", BOTAN_OPENSSL_RSA_PRIO);
+std::unique_ptr<PK_Ops::Decryption>
+make_openssl_rsa_dec_op(const RSA_PrivateKey& key, const std::string& params)
+   {
+   auto pad_info = get_openssl_enc_pad(params);
+   return std::unique_ptr<PK_Ops::Decryption>(new OpenSSL_RSA_Decryption_Operation(key, pad_info.first));
+   }
 
-BOTAN_REGISTER_TYPE(PK_Ops::Decryption, OpenSSL_RSA_Decryption_Operation, "RSA",
-                    OpenSSL_RSA_Decryption_Operation::make, "openssl", BOTAN_OPENSSL_RSA_PRIO);
+std::unique_ptr<PK_Ops::Verification>
+make_openssl_rsa_ver_op(const RSA_PublicKey& key, const std::string& params)
+   {
+   return std::unique_ptr<PK_Ops::Verification>(new OpenSSL_RSA_Verification_Operation(key, params));
+   }
 
-}
+std::unique_ptr<PK_Ops::Signature>
+make_openssl_rsa_sig_op(const RSA_PrivateKey& key, const std::string& params)
+   {
+   return std::unique_ptr<PK_Ops::Signature>(new OpenSSL_RSA_Signing_Operation(key, params));
+   }
 
 }
 
diff --git a/src/lib/prov/pkcs11/p11_ecdh.cpp b/src/lib/prov/pkcs11/p11_ecdh.cpp
index de24d6da4..6f88f43d6 100644
--- a/src/lib/prov/pkcs11/p11_ecdh.cpp
+++ b/src/lib/prov/pkcs11/p11_ecdh.cpp
@@ -14,7 +14,7 @@
 #include <botan/ber_dec.h>
 #include <botan/der_enc.h>
 #include <botan/internal/algo_registry.h>
-#include <botan/internal/pk_utils.h>
+#include <botan/internal/pk_ops.h>
 #include <botan/rng.h>
 
 namespace Botan {
@@ -43,26 +43,8 @@ namespace {
 class PKCS11_ECDH_KA_Operation : public PK_Ops::Key_Agreement
    {
    public:
-      typedef PKCS11_EC_PrivateKey Key_Type;
-
-      static PKCS11_ECDH_KA_Operation* make_ecdh(const Spec& spec, bool use_cofactor)
-         {
-         try
-            {
-            if(auto* key = dynamic_cast< const PKCS11_EC_PrivateKey* >(&spec.key()))
-               {
-               return new PKCS11_ECDH_KA_Operation(*key, spec.padding(), use_cofactor);
-               }
-            }
-         catch(...)
-            {
-            }
-
-         return nullptr;
-         }
-
-      PKCS11_ECDH_KA_Operation(const PKCS11_EC_PrivateKey& key, const std::string& kdf, bool use_cofactor)
-         : PK_Ops::Key_Agreement(), m_key(key), m_mechanism(MechanismWrapper::create_ecdh_mechanism(kdf, use_cofactor))
+      PKCS11_ECDH_KA_Operation(const PKCS11_EC_PrivateKey& key, const std::string& params)
+         : PK_Ops::Key_Agreement(), m_key(key), m_mechanism(MechanismWrapper::create_ecdh_mechanism(params))
          {}
 
 
@@ -112,14 +94,16 @@ class PKCS11_ECDH_KA_Operation : public PK_Ops::Key_Agreement
       MechanismWrapper m_mechanism;
    };
 
-Algo_Registry<PK_Ops::Key_Agreement>::Add g_PKCS11_ECDH_KA_Operation_reg("ECDH",
-      std::bind(&PKCS11_ECDH_KA_Operation::make_ecdh, std::placeholders::_1, false), "pkcs11", BOTAN_PKCS11_ECDH_PRIO);
-
-Algo_Registry<PK_Ops::Key_Agreement>::Add g_PKCS11_ECDHC_KA_Operation_reg("ECDHC",
-      std::bind(&PKCS11_ECDH_KA_Operation::make_ecdh, std::placeholders::_1, true), "pkcs11", BOTAN_PKCS11_ECDH_PRIO);
-
 }
 
+std::unique_ptr<PK_Ops::Key_Agreement>
+PKCS11_ECDH_PrivateKey::create_key_agreement_op(RandomNumberGenerator&,
+                                                const std::string& params,
+                                                const std::string& /*provider*/) const
+   {
+   return std::unique_ptr<PK_Ops::Key_Agreement>(new PKCS11_ECDH_KA_Operation(*this, params));
+   }
+
 PKCS11_ECDH_KeyPair generate_ecdh_keypair(Session& session, const EC_PublicKeyGenerationProperties& pub_props,
       const EC_PrivateKeyGenerationProperties& priv_props)
    {
diff --git a/src/lib/prov/pkcs11/p11_ecdh.h b/src/lib/prov/pkcs11/p11_ecdh.h
index 749a00d52..ef9ccb250 100644
--- a/src/lib/prov/pkcs11/p11_ecdh.h
+++ b/src/lib/prov/pkcs11/p11_ecdh.h
@@ -102,6 +102,11 @@ class BOTAN_DLL PKCS11_ECDH_PrivateKey final : public virtual PKCS11_EC_PrivateK
       ECDH_PrivateKey export_key() const;
 
       secure_vector<byte> pkcs8_private_key() const override;
+
+      std::unique_ptr<PK_Ops::Key_Agreement>
+         create_key_agreement_op(RandomNumberGenerator& rng,
+                                 const std::string& params,
+                                 const std::string& provider) const override;
    };
 
 using PKCS11_ECDH_KeyPair = std::pair<PKCS11_ECDH_PublicKey, PKCS11_ECDH_PrivateKey>;
diff --git a/src/lib/prov/pkcs11/p11_ecdsa.cpp b/src/lib/prov/pkcs11/p11_ecdsa.cpp
index 078bc429d..076bb2498 100644
--- a/src/lib/prov/pkcs11/p11_ecdsa.cpp
+++ b/src/lib/prov/pkcs11/p11_ecdsa.cpp
@@ -12,7 +12,7 @@
 
 #include <botan/internal/p11_mechanism.h>
 #include <botan/internal/algo_registry.h>
-#include <botan/internal/pk_utils.h>
+#include <botan/internal/pk_ops.h>
 #include <botan/keypair.h>
 #include <botan/rng.h>
 
@@ -198,13 +198,22 @@ class PKCS11_ECDSA_Verification_Operation : public PK_Ops::Verification
       bool m_initialized = false;
    };
 
-BOTAN_REGISTER_TYPE(PK_Ops::Signature, PKCS11_ECDSA_Signature_Operation, "ECDSA",
-                    (make_pk_op<PK_Ops::Signature, PKCS11_ECDSA_Signature_Operation>), "pkcs11", BOTAN_PKCS11_ECDSA_PRIO);
+}
 
-BOTAN_REGISTER_TYPE(PK_Ops::Verification, PKCS11_ECDSA_Verification_Operation, "ECDSA",
-                    (make_pk_op<PK_Ops::Verification, PKCS11_ECDSA_Verification_Operation>), "pkcs11", BOTAN_PKCS11_ECDSA_PRIO);
+std::unique_ptr<PK_Ops::Verification>
+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
+   {
+   return std::unique_ptr<PK_Ops::Signature>(new PKCS11_ECDSA_Signature_Operation(*this, params));
+   }
 
 PKCS11_ECDSA_KeyPair generate_ecdsa_keypair(Session& session, const EC_PublicKeyGenerationProperties& pub_props,
       const EC_PrivateKeyGenerationProperties& priv_props)
diff --git a/src/lib/prov/pkcs11/p11_ecdsa.h b/src/lib/prov/pkcs11/p11_ecdsa.h
index d3d07a780..aab56f1f2 100644
--- a/src/lib/prov/pkcs11/p11_ecdsa.h
+++ b/src/lib/prov/pkcs11/p11_ecdsa.h
@@ -55,6 +55,10 @@ class BOTAN_DLL PKCS11_ECDSA_PublicKey final : public PKCS11_EC_PublicKey, publi
 
       /// @return the exported ECDSA public key
       ECDSA_PublicKey export_key() const;
+
+      std::unique_ptr<PK_Ops::Verification>
+         create_verification_op(const std::string& params,
+                                const std::string& provider) const override;
    };
 
 /// Represents a PKCS#11 ECDSA private key
@@ -107,6 +111,11 @@ class BOTAN_DLL PKCS11_ECDSA_PrivateKey final : public PKCS11_EC_PrivateKey
       secure_vector<byte> pkcs8_private_key() const override;
 
       bool check_key(RandomNumberGenerator&, bool) const override;
+
+      std::unique_ptr<PK_Ops::Signature>
+         create_signature_op(RandomNumberGenerator& rng,
+                             const std::string& params,
+                             const std::string& provider) const override;
    };
 
 using PKCS11_ECDSA_KeyPair = std::pair<PKCS11_ECDSA_PublicKey, PKCS11_ECDSA_PrivateKey>;
diff --git a/src/lib/prov/pkcs11/p11_mechanism.cpp b/src/lib/prov/pkcs11/p11_mechanism.cpp
index 07ac00770..a4c6e73a7 100644
--- a/src/lib/prov/pkcs11/p11_mechanism.cpp
+++ b/src/lib/prov/pkcs11/p11_mechanism.cpp
@@ -219,8 +219,18 @@ MechanismWrapper MechanismWrapper::create_ecdsa_mechanism(const std::string& has
    return MechanismWrapper(mechanism_type->second);
    }
 
-MechanismWrapper MechanismWrapper::create_ecdh_mechanism(const std::string& kdf_name, bool use_cofactor)
+MechanismWrapper MechanismWrapper::create_ecdh_mechanism(const std::string& params)
    {
+   std::vector<std::string> param_parts = split_on(params, ',');
+
+   if(param_parts.empty() || param_parts.size() > 2)
+      throw Invalid_Argument("PKCS #11 ECDH key derivation bad params " + params);
+
+   const bool use_cofactor =
+      (param_parts[0] == "Cofactor") ||
+      (param_parts.size() == 2 && param_parts[1] == "Cofactor");
+
+   std::string kdf_name = (param_parts[0] == "Cofactor" ? param_parts[1] : param_parts[0]);
    std::string hash = kdf_name;
 
    if(kdf_name != "Raw")
diff --git a/src/lib/prov/pkcs11/p11_mechanism.h b/src/lib/prov/pkcs11/p11_mechanism.h
index 5d8c826ee..0f7b6f07c 100644
--- a/src/lib/prov/pkcs11/p11_mechanism.h
+++ b/src/lib/prov/pkcs11/p11_mechanism.h
@@ -51,10 +51,12 @@ class MechanismWrapper final
 
       /**
       * Creates the CK_MECHANISM data for ECDH key derivation (CKM_ECDH1_DERIVE or CKM_ECDH1_COFACTOR_DERIVE)
-      * @param kdf_name the key derivation function to use. Supported KDFs are Raw and SHA-160 to SHA-512
-      * @param use_cofactor true if the cofactor key derivation mechanism should be used
+      * @param params specifies the key derivation function to use.
+      * Supported KDFs are Raw and SHA-160 to SHA-512.
+      * Params can also include the string "Cofactor" if the cofactor
+      * key derivation mechanism should be used, for example "SHA-512,Cofactor"
       */
-      static MechanismWrapper create_ecdh_mechanism(const std::string& kdf_name, bool use_cofactor);
+      static MechanismWrapper create_ecdh_mechanism(const std::string& params);
 
       /// Sets the salt for the ECDH mechanism parameters
       inline void set_ecdh_salt(const byte salt[], size_t salt_len)
diff --git a/src/lib/prov/pkcs11/p11_rsa.cpp b/src/lib/prov/pkcs11/p11_rsa.cpp
index 9e5675301..c23c8f5f3 100644
--- a/src/lib/prov/pkcs11/p11_rsa.cpp
+++ b/src/lib/prov/pkcs11/p11_rsa.cpp
@@ -11,9 +11,9 @@
 #if defined(BOTAN_HAS_RSA)
 
 #include <botan/internal/p11_mechanism.h>
-#include <botan/pk_ops.h>
+#include <botan/internal/pk_ops.h>
 #include <botan/internal/algo_registry.h>
-#include <botan/internal/pk_utils.h>
+#include <botan/internal/pk_ops.h>
 #include <botan/rng.h>
 #include <botan/blinding.h>
 
@@ -125,14 +125,18 @@ secure_vector<byte> PKCS11_RSA_PrivateKey::pkcs8_private_key() const
 namespace {
 // note:	multiple-part decryption operations (with C_DecryptUpdate/C_DecryptFinal)
 //			are not supported (PK_Ops::Decryption does not provide an `update` method)
-class PKCS11_RSA_Decryption_Operation : public PK_Ops::Decryption
+class PKCS11_RSA_Decryption_Operation final : public PK_Ops::Decryption
    {
    public:
       typedef PKCS11_RSA_PrivateKey Key_Type;
 
-      PKCS11_RSA_Decryption_Operation(const PKCS11_RSA_PrivateKey& key, const std::string& padding)
-         : m_key(key), m_mechanism(MechanismWrapper::create_rsa_crypt_mechanism(padding)), 
-           m_powermod(m_key.get_e(), m_key.get_n()), m_blinder(m_key.get_n(),
+      PKCS11_RSA_Decryption_Operation(const PKCS11_RSA_PrivateKey& key,
+                                      const std::string& padding,
+                                      RandomNumberGenerator& rng)
+         : m_key(key),
+           m_mechanism(MechanismWrapper::create_rsa_crypt_mechanism(padding)),
+           m_powermod(m_key.get_e(), m_key.get_n()),
+           m_blinder(m_key.get_n(), rng,
                      [ this ](const BigInt& k) { return m_powermod(k); },
                      [ this ](const BigInt& k) { return inverse_mod(k, m_key.get_n()); })
          {
@@ -343,19 +347,38 @@ class PKCS11_RSA_Verification_Operation : public PK_Ops::Verification
       MechanismWrapper m_mechanism;
    };
 
-BOTAN_REGISTER_TYPE(PK_Ops::Decryption, PKCS11_RSA_Decryption_Operation, "RSA",
-                    (make_pk_op<PK_Ops::Decryption, PKCS11_RSA_Decryption_Operation>), "pkcs11", BOTAN_PKCS11_RSA_PRIO);
+}
 
-BOTAN_REGISTER_TYPE(PK_Ops::Encryption, PKCS11_RSA_Encryption_Operation, "RSA",
-                    (make_pk_op<PK_Ops::Encryption, PKCS11_RSA_Encryption_Operation>), "pkcs11", BOTAN_PKCS11_RSA_PRIO);
+std::unique_ptr<PK_Ops::Encryption>
+PKCS11_RSA_PublicKey::create_encryption_op(RandomNumberGenerator& /*rng*/,
+                                           const std::string& params,
+                                           const std::string& /*provider*/) const
+   {
+   return std::unique_ptr<PK_Ops::Encryption>(new PKCS11_RSA_Encryption_Operation(*this, params));
+   }
 
-BOTAN_REGISTER_TYPE(PK_Ops::Signature, PKCS11_RSA_Signature_Operation, "RSA",
-                    (make_pk_op<PK_Ops::Signature, PKCS11_RSA_Signature_Operation>), "pkcs11", BOTAN_PKCS11_RSA_PRIO);
+std::unique_ptr<PK_Ops::Verification>
+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));
+   }
 
-BOTAN_REGISTER_TYPE(PK_Ops::Verification, PKCS11_RSA_Verification_Operation, "RSA",
-                    (make_pk_op<PK_Ops::Verification, PKCS11_RSA_Verification_Operation>), "pkcs11", BOTAN_PKCS11_RSA_PRIO);
+std::unique_ptr<PK_Ops::Decryption>
+PKCS11_RSA_PrivateKey::create_decryption_op(RandomNumberGenerator& rng,
+                                            const std::string& params,
+                                            const std::string& /*provider*/) const
+   {
+   return std::unique_ptr<PK_Ops::Decryption>(new PKCS11_RSA_Decryption_Operation(*this, params, rng));
+   }
 
-}
+std::unique_ptr<PK_Ops::Signature>
+PKCS11_RSA_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
+                                           const std::string& params,
+                                           const std::string& /*provider*/) const
+   {
+   return std::unique_ptr<PK_Ops::Signature>(new PKCS11_RSA_Signature_Operation(*this, params));
+   }
 
 PKCS11_RSA_KeyPair generate_rsa_keypair(Session& session, const RSA_PublicKeyGenerationProperties& pub_props,
                                         const RSA_PrivateKeyGenerationProperties& priv_props)
@@ -374,4 +397,5 @@ PKCS11_RSA_KeyPair generate_rsa_keypair(Session& session, const RSA_PublicKeyGen
 
 }
 }
+
 #endif
diff --git a/src/lib/prov/pkcs11/p11_rsa.h b/src/lib/prov/pkcs11/p11_rsa.h
index 2739cf3e5..6d80e45a7 100644
--- a/src/lib/prov/pkcs11/p11_rsa.h
+++ b/src/lib/prov/pkcs11/p11_rsa.h
@@ -83,6 +83,15 @@ class BOTAN_DLL PKCS11_RSA_PublicKey final : public RSA_PublicKey,
       * @param pubkey_props the attributes of the public key
       */
       PKCS11_RSA_PublicKey(Session& session, const RSA_PublicKeyImportProperties& pubkey_props);
+
+      std::unique_ptr<PK_Ops::Encryption>
+         create_encryption_op(RandomNumberGenerator& rng,
+                              const std::string& params,
+                              const std::string& provider) const override;
+
+      std::unique_ptr<PK_Ops::Verification>
+         create_verification_op(const std::string& params,
+                                const std::string& provider) const override;
    };
 
 /// Properties for importing a PKCS#11 RSA private key
@@ -192,6 +201,16 @@ class BOTAN_DLL PKCS11_RSA_PrivateKey final : public Private_Key,
       RSA_PrivateKey export_key() const;
 
       secure_vector<byte> pkcs8_private_key() const override;
+
+      std::unique_ptr<PK_Ops::Decryption>
+         create_decryption_op(RandomNumberGenerator& rng,
+                              const std::string& params,
+                              const std::string& provider) const override;
+
+      std::unique_ptr<PK_Ops::Signature>
+         create_signature_op(RandomNumberGenerator& rng,
+                             const std::string& params,
+                             const std::string& provider) const override;
    };
 
 using PKCS11_RSA_KeyPair = std::pair<PKCS11_RSA_PublicKey, PKCS11_RSA_PrivateKey>;
diff --git a/src/lib/prov/tpm/tpm.cpp b/src/lib/prov/tpm/tpm.cpp
index c0b265b98..7604a9be0 100644
--- a/src/lib/prov/tpm/tpm.cpp
+++ b/src/lib/prov/tpm/tpm.cpp
@@ -11,7 +11,7 @@
 #include <botan/hash_id.h>
 #include <botan/der_enc.h>
 #include <botan/workfactor.h>
-#include <botan/internal/pk_utils.h>
+#include <botan/internal/pk_ops.h>
 #include <sstream>
 
 #include <tss/platform.h>
@@ -386,18 +386,6 @@ namespace {
 class TPM_Signing_Operation : public PK_Ops::Signature
    {
    public:
-      static TPM_Signing_Operation* make(const Spec& spec)
-         {
-         if(auto* key = dynamic_cast<const TPM_PrivateKey*>(&spec.key()))
-            {
-            const std::string padding = spec.padding();
-            const std::string hash = "SHA-256"; // TODO
-            return new TPM_Signing_Operation(*key, hash);
-            }
-
-         return nullptr;
-         }
-
       TPM_Signing_Operation(const TPM_PrivateKey& key,
                             const std::string& hash_name) :
          m_key(key),
@@ -454,7 +442,12 @@ class TPM_Signing_Operation : public PK_Ops::Signature
 
 }
 
-BOTAN_REGISTER_TYPE(PK_Ops::Signature, TPM_Signing_Operation, "RSA",
-                    TPM_Signing_Operation::make, "tpm", 100);
+std::unique_ptr<PK_Ops::Signature>
+TPM_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
+                                    const std::string& params,
+                                    const std::string& /*provider*/) const
+   {
+   return std::unique_ptr<PK_Ops::Signature>(new TPM_Signing_Operation(*this, params));
+   }
 
 }
diff --git a/src/lib/prov/tpm/tpm.h b/src/lib/prov/tpm/tpm.h
index b8093518c..413896df1 100644
--- a/src/lib/prov/tpm/tpm.h
+++ b/src/lib/prov/tpm/tpm.h
@@ -162,6 +162,11 @@ class BOTAN_DLL TPM_PrivateKey : public Private_Key
 
       std::string algo_name() const override { return "RSA"; } // ???
 
+      std::unique_ptr<PK_Ops::Signature>
+         create_signature_op(RandomNumberGenerator& rng,
+                             const std::string& params,
+                             const std::string& provider) const override;
+
    private:
       BigInt get_n() const;
       BigInt get_e() const;
diff --git a/src/lib/pubkey/blinding.cpp b/src/lib/pubkey/blinding.cpp
index b20a30fa1..47436bcb0 100644
--- a/src/lib/pubkey/blinding.cpp
+++ b/src/lib/pubkey/blinding.cpp
@@ -8,25 +8,21 @@
 #include <botan/blinding.h>
 #include <botan/numthry.h>
 
-#if defined(BOTAN_HAS_SYSTEM_RNG)
-  #include <botan/system_rng.h>
-#else
-  #include <botan/auto_rng.h>
-#endif
-
 namespace Botan {
 
 Blinder::Blinder(const BigInt& modulus,
+                 RandomNumberGenerator& rng,
                  std::function<BigInt (const BigInt&)> fwd,
                  std::function<BigInt (const BigInt&)> inv) :
-      m_reducer{Modular_Reducer(modulus)}, m_rng{}, m_fwd_fn(fwd), m_inv_fn(inv), m_modulus_bits{modulus.bits()}, m_e{}, m_d{}, m_counter{}
+      m_reducer(modulus),
+      m_rng(rng),
+      m_fwd_fn(fwd),
+      m_inv_fn(inv),
+      m_modulus_bits(modulus.bits()),
+      m_e{},
+      m_d{},
+      m_counter{}
    {
-#if defined(BOTAN_HAS_SYSTEM_RNG)
-   m_rng.reset(new System_RNG);
-#else
-   m_rng.reset(new AutoSeeded_RNG);
-#endif
-
    const BigInt k = blinding_nonce();
    m_e = m_fwd_fn(k);
    m_d = m_inv_fn(k);
@@ -34,7 +30,7 @@ Blinder::Blinder(const BigInt& modulus,
 
 BigInt Blinder::blinding_nonce() const
    {
-   return BigInt(*m_rng, m_modulus_bits - 1);
+   return BigInt(m_rng, m_modulus_bits - 1);
    }
 
 BigInt Blinder::blind(const BigInt& i) const
@@ -44,11 +40,12 @@ BigInt Blinder::blind(const BigInt& i) const
 
    ++m_counter;
 
-   if(BOTAN_BLINDING_REINIT_INTERVAL > 0 && (m_counter % BOTAN_BLINDING_REINIT_INTERVAL == 0))
+   if((BOTAN_BLINDING_REINIT_INTERVAL > 0) && (m_counter > BOTAN_BLINDING_REINIT_INTERVAL))
       {
       const BigInt k = blinding_nonce();
       m_e = m_fwd_fn(k);
       m_d = m_inv_fn(k);
+      m_counter = 0;
       }
    else
       {
diff --git a/src/lib/pubkey/blinding.h b/src/lib/pubkey/blinding.h
index c1999feb7..a6b266807 100644
--- a/src/lib/pubkey/blinding.h
+++ b/src/lib/pubkey/blinding.h
@@ -26,11 +26,8 @@ class BOTAN_DLL Blinder
 
       BigInt unblind(const BigInt& x) const;
 
-      bool initialized() const { return m_reducer.initialized(); }
-
-      Blinder() {}
-
       Blinder(const BigInt& modulus,
+              RandomNumberGenerator& rng,
               std::function<BigInt (const BigInt&)> fwd_func,
               std::function<BigInt (const BigInt&)> inv_func);
 
@@ -42,7 +39,7 @@ class BOTAN_DLL Blinder
       BigInt blinding_nonce() const;
 
       Modular_Reducer m_reducer;
-      std::unique_ptr<RandomNumberGenerator> m_rng;
+      RandomNumberGenerator& m_rng;
       std::function<BigInt (const BigInt&)> m_fwd_fn;
       std::function<BigInt (const BigInt&)> m_inv_fn;
       size_t m_modulus_bits = 0;
diff --git a/src/lib/pubkey/curve25519/curve25519.cpp b/src/lib/pubkey/curve25519/curve25519.cpp
index aa0646d04..02ee516de 100644
--- a/src/lib/pubkey/curve25519/curve25519.cpp
+++ b/src/lib/pubkey/curve25519/curve25519.cpp
@@ -5,8 +5,8 @@
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#include <botan/internal/pk_utils.h>
 #include <botan/curve25519.h>
+#include <botan/internal/pk_ops_impl.h>
 #include <botan/ber_dec.h>
 #include <botan/der_enc.h>
 
@@ -134,9 +134,16 @@ class Curve25519_KA_Operation : public PK_Ops::Key_Agreement_with_KDF
       const Curve25519_PrivateKey& m_key;
    };
 
-BOTAN_REGISTER_PK_KEY_AGREE_OP("Curve25519", Curve25519_KA_Operation);
-
 }
 
+std::unique_ptr<PK_Ops::Key_Agreement>
+Curve25519_PrivateKey::create_key_agreement_op(RandomNumberGenerator& /*rng*/,
+                                               const std::string& params,
+                                               const std::string& provider) const
+   {
+   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/curve25519/curve25519.h b/src/lib/pubkey/curve25519/curve25519.h
index 9d2868d6d..fe39d9dd6 100644
--- a/src/lib/pubkey/curve25519/curve25519.h
+++ b/src/lib/pubkey/curve25519/curve25519.h
@@ -33,6 +33,7 @@ class BOTAN_DLL Curve25519_PublicKey : public virtual Public_Key
                            const secure_vector<byte>& key_bits);
 
       explicit Curve25519_PublicKey(const secure_vector<byte>& pub) : m_public(pub) {}
+
    protected:
       Curve25519_PublicKey() {}
       secure_vector<byte> m_public;
@@ -60,6 +61,12 @@ class BOTAN_DLL Curve25519_PrivateKey : public Curve25519_PublicKey,
       secure_vector<byte> pkcs8_private_key() const override;
 
       bool check_key(RandomNumberGenerator& rng, bool strong) const override;
+
+      std::unique_ptr<PK_Ops::Key_Agreement>
+         create_key_agreement_op(RandomNumberGenerator& rng,
+                                 const std::string& params,
+                                 const std::string& provider) const override;
+
    private:
       secure_vector<byte> m_private;
    };
diff --git a/src/lib/pubkey/dh/dh.cpp b/src/lib/pubkey/dh/dh.cpp
index 8ed79aa3d..19ead1b11 100644
--- a/src/lib/pubkey/dh/dh.cpp
+++ b/src/lib/pubkey/dh/dh.cpp
@@ -1,12 +1,12 @@
 /*
 * Diffie-Hellman
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2007,2016 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#include <botan/internal/pk_utils.h>
 #include <botan/dh.h>
+#include <botan/internal/pk_ops_impl.h>
 #include <botan/workfactor.h>
 #include <botan/pow_mod.h>
 #include <botan/blinding.h>
@@ -41,7 +41,7 @@ DH_PrivateKey::DH_PrivateKey(RandomNumberGenerator& rng,
    m_group = grp;
    m_x = x_arg;
 
-   if(m_x == 0)
+   if(generate)
       {
       const BigInt& p = group_p();
       m_x.randomize(rng, dl_exponent_size(p.bits()));
@@ -93,7 +93,16 @@ class DH_KA_Operation : public PK_Ops::Key_Agreement_with_KDF
    {
    public:
       typedef DH_PrivateKey Key_Type;
-      DH_KA_Operation(const DH_PrivateKey& key, const std::string& kdf);
+
+      DH_KA_Operation(const DH_PrivateKey& key, const std::string& kdf, RandomNumberGenerator& rng) :
+         PK_Ops::Key_Agreement_with_KDF(kdf),
+         m_p(key.group_p()),
+         m_powermod_x_p(key.get_x(), m_p),
+         m_blinder(m_p,
+                   rng,
+                   [](const BigInt& k) { return k; },
+                   [this](const BigInt& k) { return m_powermod_x_p(inverse_mod(k, m_p)); })
+         {}
 
       secure_vector<byte> raw_agree(const byte w[], size_t w_len) override;
    private:
@@ -103,16 +112,6 @@ class DH_KA_Operation : public PK_Ops::Key_Agreement_with_KDF
       Blinder m_blinder;
    };
 
-DH_KA_Operation::DH_KA_Operation(const DH_PrivateKey& dh, const std::string& kdf) :
-   PK_Ops::Key_Agreement_with_KDF(kdf),
-   m_p(dh.group_p()),
-   m_powermod_x_p(dh.get_x(), m_p),
-   m_blinder(m_p,
-             [](const BigInt& k) { return k; },
-             [this](const BigInt& k) { return m_powermod_x_p(inverse_mod(k, m_p)); })
-   {
-   }
-
 secure_vector<byte> DH_KA_Operation::raw_agree(const byte w[], size_t w_len)
    {
    BigInt input = BigInt::decode(w, w_len);
@@ -127,6 +126,14 @@ secure_vector<byte> DH_KA_Operation::raw_agree(const byte w[], size_t w_len)
 
 }
 
-BOTAN_REGISTER_PK_KEY_AGREE_OP("DH", DH_KA_Operation);
+std::unique_ptr<PK_Ops::Key_Agreement>
+DH_PrivateKey::create_key_agreement_op(RandomNumberGenerator& rng,
+                                       const std::string& params,
+                                       const std::string& provider) const
+   {
+   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/dh/dh.h b/src/lib/pubkey/dh/dh.h
index 9911453fb..d15bc5eb3 100644
--- a/src/lib/pubkey/dh/dh.h
+++ b/src/lib/pubkey/dh/dh.h
@@ -67,6 +67,11 @@ class BOTAN_DLL DH_PrivateKey : public DH_PublicKey,
       */
       DH_PrivateKey(RandomNumberGenerator& rng, const DL_Group& grp,
                     const BigInt& x = 0);
+
+      std::unique_ptr<PK_Ops::Key_Agreement>
+         create_key_agreement_op(RandomNumberGenerator& rng,
+                                 const std::string& params,
+                                 const std::string& provider) const override;
    };
 
 }
diff --git a/src/lib/pubkey/dlies/dlies.cpp b/src/lib/pubkey/dlies/dlies.cpp
index 9666a1c23..09f24adb7 100644
--- a/src/lib/pubkey/dlies/dlies.cpp
+++ b/src/lib/pubkey/dlies/dlies.cpp
@@ -12,14 +12,16 @@
 namespace Botan {
 
 DLIES_Encryptor::DLIES_Encryptor(const DH_PrivateKey& own_priv_key,
+                                 RandomNumberGenerator& rng,
                                  KDF* kdf,
                                  MessageAuthenticationCode* mac,
                                  size_t mac_key_length) :
-   DLIES_Encryptor(own_priv_key, kdf, nullptr, 0, mac, mac_key_length)
+   DLIES_Encryptor(own_priv_key, rng, kdf, nullptr, 0, mac, mac_key_length)
    {
    }
 
 DLIES_Encryptor::DLIES_Encryptor(const DH_PrivateKey& own_priv_key,
+                                 RandomNumberGenerator& rng,
                                  KDF* kdf,
                                  Cipher_Mode* cipher,
                                  size_t cipher_key_len,
@@ -27,7 +29,7 @@ DLIES_Encryptor::DLIES_Encryptor(const DH_PrivateKey& own_priv_key,
                                  size_t mac_key_length) :
    m_other_pub_key(),
    m_own_pub_key(own_priv_key.public_value()),
-   m_ka(own_priv_key, "Raw"),
+   m_ka(own_priv_key, rng, "Raw"),
    m_kdf(kdf),
    m_cipher(cipher),
    m_cipher_key_len(cipher_key_len),
@@ -111,13 +113,14 @@ size_t DLIES_Encryptor::maximum_input_size() const
    }
 
 DLIES_Decryptor::DLIES_Decryptor(const DH_PrivateKey& own_priv_key,
+                                 RandomNumberGenerator& rng,
                                  KDF* kdf,
                                  Cipher_Mode* cipher,
                                  size_t cipher_key_len,
                                  MessageAuthenticationCode* mac,
                                  size_t mac_key_length) :
    m_pub_key_size(own_priv_key.public_value().size()),
-   m_ka(own_priv_key, "Raw"),
+   m_ka(own_priv_key, rng, "Raw"),
    m_kdf(kdf),
    m_cipher(cipher),
    m_cipher_key_len(cipher_key_len),
@@ -130,10 +133,11 @@ DLIES_Decryptor::DLIES_Decryptor(const DH_PrivateKey& own_priv_key,
    }
 
 DLIES_Decryptor::DLIES_Decryptor(const DH_PrivateKey& own_priv_key,
+                                 RandomNumberGenerator& rng,
                                  KDF* kdf,
                                  MessageAuthenticationCode* mac,
                                  size_t mac_key_length) :
-   DLIES_Decryptor(own_priv_key, kdf, nullptr, 0, mac, mac_key_length)
+   DLIES_Decryptor(own_priv_key, rng, kdf, nullptr, 0, mac, mac_key_length)
    {}
 
 secure_vector<byte> DLIES_Decryptor::do_decrypt(byte& valid_mask,
diff --git a/src/lib/pubkey/dlies/dlies.h b/src/lib/pubkey/dlies/dlies.h
index 5f7251d03..f6bf9c6dd 100644
--- a/src/lib/pubkey/dlies/dlies.h
+++ b/src/lib/pubkey/dlies/dlies.h
@@ -34,6 +34,7 @@ class BOTAN_DLL DLIES_Encryptor : public PK_Encryptor
       * output = (ephemeral) public key + ciphertext + tag
       */
       DLIES_Encryptor(const DH_PrivateKey& own_priv_key,
+                      RandomNumberGenerator& rng,
                       KDF* kdf,
                       MessageAuthenticationCode* mac,
                       size_t mac_key_len = 20);
@@ -51,6 +52,7 @@ class BOTAN_DLL DLIES_Encryptor : public PK_Encryptor
       * output = (ephemeral) public key + ciphertext + tag
       */
       DLIES_Encryptor(const DH_PrivateKey& own_priv_key,
+                      RandomNumberGenerator& rng,
                       KDF* kdf,
                       Cipher_Mode* cipher,
                       size_t cipher_key_len,
@@ -103,6 +105,7 @@ class BOTAN_DLL DLIES_Decryptor : public PK_Decryptor
       * input = (ephemeral) public key + ciphertext + tag
       */
       DLIES_Decryptor(const DH_PrivateKey& own_priv_key,
+                      RandomNumberGenerator& rng,
                       KDF* kdf,
                       MessageAuthenticationCode* mac,
                       size_t mac_key_len = 20);
@@ -120,6 +123,7 @@ class BOTAN_DLL DLIES_Decryptor : public PK_Decryptor
       * input = (ephemeral) public key + ciphertext + tag
       */
       DLIES_Decryptor(const DH_PrivateKey& own_priv_key,
+                      RandomNumberGenerator& rng,
                       KDF* kdf,
                       Cipher_Mode* cipher,
                       size_t cipher_key_len,
diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp
index 399756b1a..15dc45373 100644
--- a/src/lib/pubkey/dsa/dsa.cpp
+++ b/src/lib/pubkey/dsa/dsa.cpp
@@ -1,20 +1,22 @@
 /*
 * DSA
-* (C) 1999-2010,2014 Jack Lloyd
+* (C) 1999-2010,2014,2016 Jack Lloyd
 * (C) 2016 René Korthaus
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#include <botan/internal/pk_utils.h>
 #include <botan/dsa.h>
 #include <botan/keypair.h>
 #include <botan/pow_mod.h>
 #include <botan/reducer.h>
+#include <botan/internal/pk_ops_impl.h>
+
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
-  #include <botan/rfc6979.h>
   #include <botan/emsa.h>
+  #include <botan/rfc6979.h>
 #endif
+
 #include <future>
 
 namespace Botan {
@@ -193,9 +195,25 @@ bool DSA_Verification_Operation::verify(const byte msg[], size_t msg_len,
    return (m_mod_q.reduce(s) == r);
    }
 
-BOTAN_REGISTER_PK_SIGNATURE_OP("DSA", DSA_Signature_Operation);
-BOTAN_REGISTER_PK_VERIFY_OP("DSA", DSA_Verification_Operation);
-
 }
 
+std::unique_ptr<PK_Ops::Verification>
+DSA_PublicKey::create_verification_op(const std::string& params,
+                                      const std::string& provider) const
+   {
+   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*/,
+                                    const std::string& params,
+                                    const std::string& provider) const
+   {
+   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 2653c9229..57c7b7c5c 100644
--- a/src/lib/pubkey/dsa/dsa.h
+++ b/src/lib/pubkey/dsa/dsa.h
@@ -32,6 +32,10 @@ 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(const std::string& params,
+                                const std::string& provider) const override;
    protected:
       DSA_PublicKey() {}
    };
@@ -52,6 +56,11 @@ class BOTAN_DLL DSA_PrivateKey : public DSA_PublicKey,
                      const BigInt& private_key = 0);
 
       bool check_key(RandomNumberGenerator& rng, bool strong) const override;
+
+      std::unique_ptr<PK_Ops::Signature>
+         create_signature_op(RandomNumberGenerator& rng,
+                             const std::string& params,
+                             const std::string& provider) const override;
    };
 
 }
diff --git a/src/lib/pubkey/ecdh/ecdh.cpp b/src/lib/pubkey/ecdh/ecdh.cpp
index 55e215bc1..a4791e15e 100644
--- a/src/lib/pubkey/ecdh/ecdh.cpp
+++ b/src/lib/pubkey/ecdh/ecdh.cpp
@@ -7,8 +7,12 @@
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#include <botan/internal/pk_utils.h>
 #include <botan/ecdh.h>
+#include <botan/internal/pk_ops_impl.h>
+
+#if defined(BOTAN_HAS_OPENSSL)
+  #include <botan/internal/openssl.h>
+#endif
 
 namespace Botan {
 
@@ -35,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());
@@ -47,6 +52,31 @@ class ECDH_KA_Operation : public PK_Ops::Key_Agreement_with_KDF
 
 }
 
-BOTAN_REGISTER_PK_KEY_AGREE_OP("ECDH", ECDH_KA_Operation);
+std::unique_ptr<PK_Ops::Key_Agreement>
+ECDH_PrivateKey::create_key_agreement_op(RandomNumberGenerator& /*rng*/,
+                                         const std::string& params,
+                                         const std::string& provider) const
+   {
+#if defined(BOTAN_HAS_OPENSSL)
+   if(provider == "openssl" || provider.empty())
+      {
+      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
+
+   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/ecdh/ecdh.h b/src/lib/pubkey/ecdh/ecdh.h
index bdd9ea047..5b6ec7261 100644
--- a/src/lib/pubkey/ecdh/ecdh.h
+++ b/src/lib/pubkey/ecdh/ecdh.h
@@ -94,6 +94,11 @@ class BOTAN_DLL ECDH_PrivateKey : public ECDH_PublicKey,
 
       std::vector<byte> public_value(PointGFp::Compression_Type type) const
          { return ECDH_PublicKey::public_value(type); }
+
+      std::unique_ptr<PK_Ops::Key_Agreement>
+         create_key_agreement_op(RandomNumberGenerator& rng,
+                                 const std::string& params,
+                                 const std::string& provider) const override;
    };
 
 }
diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp
index 264a36963..f93fcc7a5 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.cpp
+++ b/src/lib/pubkey/ecdsa/ecdsa.cpp
@@ -2,18 +2,24 @@
 * ECDSA implemenation
 * (C) 2007 Manuel Hartl, FlexSecure GmbH
 *     2007 Falko Strenzke, FlexSecure GmbH
-*     2008-2010,2015 Jack Lloyd
+*     2008-2010,2015,2016 Jack Lloyd
 *     2016 René Korthaus
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#include <botan/internal/pk_utils.h>
 #include <botan/ecdsa.h>
+#include <botan/internal/pk_ops_impl.h>
 #include <botan/keypair.h>
+#include <botan/reducer.h>
+#include <botan/emsa.h>
+
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
   #include <botan/rfc6979.h>
-  #include <botan/emsa.h>
+#endif
+
+#if defined(BOTAN_HAS_OPENSSL)
+  #include <botan/internal/openssl.h>
 #endif
 
 namespace Botan {
@@ -150,9 +156,57 @@ bool ECDSA_Verification_Operation::verify(const byte msg[], size_t msg_len,
    return (v == r);
    }
 
-BOTAN_REGISTER_PK_SIGNATURE_OP("ECDSA", ECDSA_Signature_Operation);
-BOTAN_REGISTER_PK_VERIFY_OP("ECDSA", ECDSA_Verification_Operation);
-
 }
 
+std::unique_ptr<PK_Ops::Verification>
+ECDSA_PublicKey::create_verification_op(const std::string& params,
+                                        const std::string& provider) const
+   {
+#if defined(BOTAN_HAS_OPENSSL)
+   if(provider == "openssl" || provider.empty())
+      {
+      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
+
+   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*/,
+                                      const std::string& params,
+                                      const std::string& provider) const
+   {
+#if defined(BOTAN_HAS_OPENSSL)
+   if(provider == "openssl" || provider.empty())
+      {
+      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
+
+   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 eed09afe6..d9dcacd06 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.h
+++ b/src/lib/pubkey/ecdsa/ecdsa.h
@@ -53,6 +53,9 @@ class BOTAN_DLL ECDSA_PublicKey : public virtual EC_PublicKey
       size_t message_part_size() const override
          { return domain().get_order().bytes(); }
 
+      std::unique_ptr<PK_Ops::Verification>
+         create_verification_op(const std::string& params,
+                                const std::string& provider) const override;
    protected:
       ECDSA_PublicKey() {}
    };
@@ -86,6 +89,11 @@ class BOTAN_DLL ECDSA_PrivateKey : public ECDSA_PublicKey,
          EC_PrivateKey(rng, domain, x) {}
 
       bool check_key(RandomNumberGenerator& rng, bool) const override;
+
+      std::unique_ptr<PK_Ops::Signature>
+         create_signature_op(RandomNumberGenerator& rng,
+                             const std::string& params,
+                             const std::string& provider) const override;
    };
 
 }
diff --git a/src/lib/pubkey/ecgdsa/ecgdsa.cpp b/src/lib/pubkey/ecgdsa/ecgdsa.cpp
index 30ea32817..136f2159a 100644
--- a/src/lib/pubkey/ecgdsa/ecgdsa.cpp
+++ b/src/lib/pubkey/ecgdsa/ecgdsa.cpp
@@ -5,9 +5,10 @@
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#include <botan/internal/pk_utils.h>
 #include <botan/ecgdsa.h>
 #include <botan/keypair.h>
+#include <botan/reducer.h>
+#include <botan/internal/pk_ops_impl.h>
 
 namespace Botan {
 
@@ -137,9 +138,25 @@ bool ECGDSA_Verification_Operation::verify(const byte msg[], size_t msg_len,
    return (v == r);
    }
 
-BOTAN_REGISTER_PK_SIGNATURE_OP("ECGDSA", ECGDSA_Signature_Operation);
-BOTAN_REGISTER_PK_VERIFY_OP("ECGDSA", ECGDSA_Verification_Operation);
-
 }
 
+std::unique_ptr<PK_Ops::Verification>
+ECGDSA_PublicKey::create_verification_op(const std::string& params,
+                                         const std::string& provider) const
+   {
+   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*/,
+                                       const std::string& params,
+                                       const std::string& provider) const
+   {
+   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 518adeeab..203e8d0a8 100644
--- a/src/lib/pubkey/ecgdsa/ecgdsa.h
+++ b/src/lib/pubkey/ecgdsa/ecgdsa.h
@@ -51,6 +51,9 @@ class BOTAN_DLL ECGDSA_PublicKey : public virtual EC_PublicKey
       size_t message_part_size() const override
          { return domain().get_order().bytes(); }
 
+      std::unique_ptr<PK_Ops::Verification>
+         create_verification_op(const std::string& params,
+                                const std::string& provider) const override;
    protected:
       ECGDSA_PublicKey() {}
    };
@@ -84,6 +87,11 @@ class BOTAN_DLL ECGDSA_PrivateKey : public ECGDSA_PublicKey,
          EC_PrivateKey(rng, domain, x, true) {}
 
       bool check_key(RandomNumberGenerator& rng, bool) const override;
+
+      std::unique_ptr<PK_Ops::Signature>
+         create_signature_op(RandomNumberGenerator& rng,
+                             const std::string& params,
+                             const std::string& provider) const override;
    };
 
 }
diff --git a/src/lib/pubkey/ecies/ecies.cpp b/src/lib/pubkey/ecies/ecies.cpp
index d44d14803..ba7140bd0 100644
--- a/src/lib/pubkey/ecies/ecies.cpp
+++ b/src/lib/pubkey/ecies/ecies.cpp
@@ -10,7 +10,7 @@
 #include <botan/cipher_mode.h>
 
 #include <botan/internal/ct_utils.h>
-#include <botan/internal/pk_utils.h>
+#include <botan/internal/pk_ops_impl.h>
 
 namespace Botan {
 
@@ -45,6 +45,11 @@ class ECIES_PrivateKey : public EC_PrivateKey, public PK_Key_Agreement_Key
          return m_key.max_input_bits();
          }
 
+      std::unique_ptr<PK_Ops::Key_Agreement>
+         create_key_agreement_op(RandomNumberGenerator& rng,
+                                 const std::string& params,
+                                 const std::string& provider) const override;
+
    private:
       ECDH_PrivateKey m_key;
    };
@@ -55,9 +60,7 @@ class ECIES_PrivateKey : public EC_PrivateKey, public PK_Key_Agreement_Key
 class ECIES_ECDH_KA_Operation : public PK_Ops::Key_Agreement_with_KDF
    {
    public:
-      typedef ECIES_PrivateKey Key_Type;
-
-      ECIES_ECDH_KA_Operation(const ECIES_PrivateKey& private_key, const std::string&) :
+      ECIES_ECDH_KA_Operation(const ECIES_PrivateKey& private_key) :
          PK_Ops::Key_Agreement_with_KDF("Raw"),
          m_key(private_key)
          {
@@ -76,6 +79,14 @@ class ECIES_ECDH_KA_Operation : public PK_Ops::Key_Agreement_with_KDF
       ECIES_PrivateKey m_key;
    };
 
+std::unique_ptr<PK_Ops::Key_Agreement>
+ECIES_PrivateKey::create_key_agreement_op(RandomNumberGenerator& /*rng*/,
+                                          const std::string& /*params*/,
+                                          const std::string& /*provider*/) const
+   {
+   return std::unique_ptr<PK_Ops::Key_Agreement>(new ECIES_ECDH_KA_Operation(*this));
+   }
+
 /**
 * Creates a PK_Key_Agreement instance for the given key and ecies_params
 * Returns either ECIES_ECDH_KA_Operation or the default implementation for the given key,
@@ -85,8 +96,10 @@ class ECIES_ECDH_KA_Operation : public PK_Ops::Key_Agreement_with_KDF
 * @param for_encryption disable cofactor mode if the secret will be used for encryption
 * (according to ISO 18033 cofactor mode is only used during decryption)
 */
-PK_Key_Agreement create_key_agreement(const PK_Key_Agreement_Key& private_key, const ECIES_KA_Params& ecies_params,
-                                      bool for_encryption)
+PK_Key_Agreement create_key_agreement(const PK_Key_Agreement_Key& private_key,
+                                      const ECIES_KA_Params& ecies_params,
+                                      bool for_encryption,
+                                      RandomNumberGenerator& rng)
    {
    const ECDH_PrivateKey* ecdh_key = dynamic_cast<const ECDH_PrivateKey*>(&private_key);
 
@@ -103,18 +116,18 @@ PK_Key_Agreement create_key_agreement(const PK_Key_Agreement_Key& private_key, c
    if(ecdh_key && (for_encryption || !ecies_params.cofactor_mode()))
       {
       // ECDH_KA_Operation uses cofactor mode: use own key agreement method if cofactor should not be used.
-      return PK_Key_Agreement(ECIES_PrivateKey(*ecdh_key), "Raw");
+      return PK_Key_Agreement(ECIES_PrivateKey(*ecdh_key), rng, "Raw");
       }
 
-   return PK_Key_Agreement(private_key, "Raw");		// use default implementation
+   return PK_Key_Agreement(private_key, rng, "Raw");		// use default implementation
    }
 }
 
-BOTAN_REGISTER_PK_KEY_AGREE_OP("ECIES", ECIES_ECDH_KA_Operation);
-
-ECIES_KA_Operation::ECIES_KA_Operation(const PK_Key_Agreement_Key& private_key, const ECIES_KA_Params& ecies_params,
-                                       bool for_encryption) :
-   m_ka(create_key_agreement(private_key, ecies_params, for_encryption)),
+ECIES_KA_Operation::ECIES_KA_Operation(const PK_Key_Agreement_Key& private_key,
+                                       const ECIES_KA_Params& ecies_params,
+                                       bool for_encryption,
+                                       RandomNumberGenerator& rng) :
+   m_ka(create_key_agreement(private_key, ecies_params, for_encryption, rng)),
    m_params(ecies_params)
    {
    }
@@ -231,8 +244,10 @@ std::unique_ptr<Cipher_Mode> ECIES_System_Params::create_cipher(Botan::Cipher_Di
 /*
 * ECIES_Encryptor Constructor
 */
-ECIES_Encryptor::ECIES_Encryptor(const PK_Key_Agreement_Key& private_key, const ECIES_System_Params& ecies_params) :
-   m_ka(private_key, ecies_params, true),
+ECIES_Encryptor::ECIES_Encryptor(const PK_Key_Agreement_Key& private_key,
+                                 const ECIES_System_Params& ecies_params,
+                                 RandomNumberGenerator& rng) :
+   m_ka(private_key, ecies_params, true, rng),
    m_params(ecies_params),
    m_eph_public_key_bin(private_key.public_value()),	// returns the uncompressed public key, see conversion below
    m_iv(),
@@ -252,7 +267,7 @@ ECIES_Encryptor::ECIES_Encryptor(const PK_Key_Agreement_Key& private_key, const
 * ECIES_Encryptor Constructor
 */
 ECIES_Encryptor::ECIES_Encryptor(RandomNumberGenerator& rng, const ECIES_System_Params& ecies_params) :
-   ECIES_Encryptor(ECDH_PrivateKey(rng, ecies_params.domain()), ecies_params)
+   ECIES_Encryptor(ECDH_PrivateKey(rng, ecies_params.domain()), ecies_params, rng)
    {
    }
 
@@ -302,8 +317,10 @@ std::vector<byte> ECIES_Encryptor::enc(const byte data[], size_t length, RandomN
    }
 
 
-ECIES_Decryptor::ECIES_Decryptor(const PK_Key_Agreement_Key& key, const ECIES_System_Params& ecies_params) :
-   m_ka(key, ecies_params, false),
+ECIES_Decryptor::ECIES_Decryptor(const PK_Key_Agreement_Key& key,
+                                 const ECIES_System_Params& ecies_params,
+                                 RandomNumberGenerator& rng) :
+   m_ka(key, ecies_params, false, rng),
    m_params(ecies_params),
    m_iv(),
    m_label()
diff --git a/src/lib/pubkey/ecies/ecies.h b/src/lib/pubkey/ecies/ecies.h
index 0bc0bf76e..6b9eba31d 100644
--- a/src/lib/pubkey/ecies/ecies.h
+++ b/src/lib/pubkey/ecies/ecies.h
@@ -184,8 +184,10 @@ class BOTAN_DLL ECIES_KA_Operation
       * @param for_encryption disable cofactor mode if the secret will be used for encryption
       * (according to ISO 18033 cofactor mode is only used during decryption)
       */
-      ECIES_KA_Operation(const PK_Key_Agreement_Key& private_key, const ECIES_KA_Params& ecies_params,
-                         bool for_encryption);
+      ECIES_KA_Operation(const PK_Key_Agreement_Key& private_key,
+                         const ECIES_KA_Params& ecies_params,
+                         bool for_encryption,
+                         RandomNumberGenerator& rng);
 
       /**
       * Performs a key agreement with the provided keys and derives the secret from the result
@@ -211,7 +213,9 @@ class BOTAN_DLL ECIES_Encryptor : public PK_Encryptor
       * @param private_key the (ephemeral) private key which is used for the key agreement
       * @param ecies_params settings for ecies
       */
-      ECIES_Encryptor(const PK_Key_Agreement_Key& private_key, const ECIES_System_Params& ecies_params);
+      ECIES_Encryptor(const PK_Key_Agreement_Key& private_key,
+                      const ECIES_System_Params& ecies_params,
+                      RandomNumberGenerator& rng);
 
       /**
       * Creates an ephemeral private key which is used for the key agreement
@@ -265,7 +269,9 @@ class BOTAN_DLL ECIES_Decryptor : public PK_Decryptor
       * @param private_key the private key which is used for the key agreement
       * @param ecies_params settings for ecies
       */
-      ECIES_Decryptor(const PK_Key_Agreement_Key& private_key, const ECIES_System_Params& ecies_params);
+      ECIES_Decryptor(const PK_Key_Agreement_Key& private_key,
+                      const ECIES_System_Params& ecies_params,
+                      RandomNumberGenerator& rng);
 
       /// Set the initialization vector for the data encryption method
       inline void set_initialization_vector(const InitializationVector& iv)
diff --git a/src/lib/pubkey/ecies/info.txt b/src/lib/pubkey/ecies/info.txt
index 12776f8c2..fb35e7b97 100644
--- a/src/lib/pubkey/ecies/info.txt
+++ b/src/lib/pubkey/ecies/info.txt
@@ -5,4 +5,4 @@ kdf
 mac
 ecdh
 modes
-</requires>
\ No newline at end of file
+</requires>
diff --git a/src/lib/pubkey/eckcdsa/eckcdsa.cpp b/src/lib/pubkey/eckcdsa/eckcdsa.cpp
index 5ca89675c..5375d047a 100644
--- a/src/lib/pubkey/eckcdsa/eckcdsa.cpp
+++ b/src/lib/pubkey/eckcdsa/eckcdsa.cpp
@@ -5,9 +5,10 @@
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#include <botan/internal/pk_utils.h>
 #include <botan/eckcdsa.h>
+#include <botan/internal/pk_ops_impl.h>
 #include <botan/keypair.h>
+#include <botan/reducer.h>
 #include <botan/emsa.h>
 #include <botan/hash.h>
 
@@ -192,9 +193,25 @@ bool ECKCDSA_Verification_Operation::verify(const byte msg[], size_t,
    return (v == r);
    }
 
-BOTAN_REGISTER_PK_SIGNATURE_OP("ECKCDSA", ECKCDSA_Signature_Operation);
-BOTAN_REGISTER_PK_VERIFY_OP("ECKCDSA", ECKCDSA_Verification_Operation);
-
 }
 
+std::unique_ptr<PK_Ops::Verification>
+ECKCDSA_PublicKey::create_verification_op(const std::string& params,
+                                         const std::string& provider) const
+   {
+   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
+   {
+   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 b85c4025e..09ee34ed5 100644
--- a/src/lib/pubkey/eckcdsa/eckcdsa.h
+++ b/src/lib/pubkey/eckcdsa/eckcdsa.h
@@ -51,6 +51,9 @@ class BOTAN_DLL ECKCDSA_PublicKey : public virtual EC_PublicKey
       size_t message_part_size() const override
          { return domain().get_order().bytes(); }
 
+      std::unique_ptr<PK_Ops::Verification>
+         create_verification_op(const std::string& params,
+                                const std::string& provider) const override;
    protected:
       ECKCDSA_PublicKey() {}
    };
@@ -84,6 +87,11 @@ class BOTAN_DLL ECKCDSA_PrivateKey : public ECKCDSA_PublicKey,
          EC_PrivateKey(rng, domain, x, true) {}
 
       bool check_key(RandomNumberGenerator& rng, bool) const override;
+
+      std::unique_ptr<PK_Ops::Signature>
+         create_signature_op(RandomNumberGenerator& rng,
+                             const std::string& params,
+                             const std::string& provider) const override;
    };
 
 }
diff --git a/src/lib/pubkey/elgamal/elgamal.cpp b/src/lib/pubkey/elgamal/elgamal.cpp
index 37dfe89cf..046c2c3f6 100644
--- a/src/lib/pubkey/elgamal/elgamal.cpp
+++ b/src/lib/pubkey/elgamal/elgamal.cpp
@@ -5,8 +5,8 @@
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#include <botan/internal/pk_utils.h>
 #include <botan/elgamal.h>
+#include <botan/internal/pk_ops_impl.h>
 #include <botan/keypair.h>
 #include <botan/reducer.h>
 #include <botan/blinding.h>
@@ -134,7 +134,9 @@ class ElGamal_Decryption_Operation : public PK_Ops::Decryption_with_EME
       size_t max_raw_input_bits() const override
          { return m_mod_p.get_modulus().bits() - 1; }
 
-      ElGamal_Decryption_Operation(const ElGamal_PrivateKey& key, const std::string& eme);
+      ElGamal_Decryption_Operation(const ElGamal_PrivateKey& key,
+                                   const std::string& eme,
+                                   RandomNumberGenerator& rng);
 
       secure_vector<byte> raw_decrypt(const byte msg[], size_t msg_len) override;
    private:
@@ -144,13 +146,15 @@ class ElGamal_Decryption_Operation : public PK_Ops::Decryption_with_EME
    };
 
 ElGamal_Decryption_Operation::ElGamal_Decryption_Operation(const ElGamal_PrivateKey& key,
-                                                           const std::string& eme) :
+                                                           const std::string& eme,
+                                                           RandomNumberGenerator& rng) :
    PK_Ops::Decryption_with_EME(eme),
    m_powermod_x_p(Fixed_Exponent_Power_Mod(key.get_x(), key.group_p())),
    m_mod_p(Modular_Reducer(key.group_p())),
    m_blinder(key.group_p(),
-           [](const BigInt& k) { return k; },
-           [this](const BigInt& k) { return m_powermod_x_p(k); })
+             rng,
+             [](const BigInt& k) { return k; },
+             [this](const BigInt& k) { return m_powermod_x_p(k); })
    {
    }
 
@@ -177,9 +181,26 @@ ElGamal_Decryption_Operation::raw_decrypt(const byte msg[], size_t msg_len)
    return BigInt::encode_1363(m_blinder.unblind(r), p_bytes);
    }
 
-BOTAN_REGISTER_PK_ENCRYPTION_OP("ElGamal", ElGamal_Encryption_Operation);
-BOTAN_REGISTER_PK_DECRYPTION_OP("ElGamal", ElGamal_Decryption_Operation);
-
 }
 
+std::unique_ptr<PK_Ops::Encryption>
+ElGamal_PublicKey::create_encryption_op(RandomNumberGenerator& /*rng*/,
+                                        const std::string& params,
+                                        const std::string& provider) const
+   {
+   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
+   {
+   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/elgamal/elgamal.h b/src/lib/pubkey/elgamal/elgamal.h
index 9f287158d..8ca4facc2 100644
--- a/src/lib/pubkey/elgamal/elgamal.h
+++ b/src/lib/pubkey/elgamal/elgamal.h
@@ -29,6 +29,12 @@ class BOTAN_DLL ElGamal_PublicKey : public virtual DL_Scheme_PublicKey
          {}
 
       ElGamal_PublicKey(const DL_Group& group, const BigInt& y);
+
+      std::unique_ptr<PK_Ops::Encryption>
+         create_encryption_op(RandomNumberGenerator& rng,
+                              const std::string& params,
+                              const std::string& provider) const override;
+
    protected:
       ElGamal_PublicKey() {}
    };
@@ -49,6 +55,11 @@ class BOTAN_DLL ElGamal_PrivateKey : public ElGamal_PublicKey,
       ElGamal_PrivateKey(RandomNumberGenerator& rng,
                          const DL_Group& group,
                          const BigInt& priv_key = 0);
+
+      std::unique_ptr<PK_Ops::Decryption>
+         create_decryption_op(RandomNumberGenerator& rng,
+                              const std::string& params,
+                              const std::string& provider) const override;
    };
 
 }
diff --git a/src/lib/pubkey/gost_3410/gost_3410.cpp b/src/lib/pubkey/gost_3410/gost_3410.cpp
index 51db47619..7fde29bc5 100644
--- a/src/lib/pubkey/gost_3410/gost_3410.cpp
+++ b/src/lib/pubkey/gost_3410/gost_3410.cpp
@@ -7,8 +7,9 @@
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#include <botan/internal/pk_utils.h>
 #include <botan/gost_3410.h>
+#include <botan/internal/pk_ops_impl.h>
+#include <botan/reducer.h>
 #include <botan/der_enc.h>
 #include <botan/ber_dec.h>
 
@@ -212,7 +213,23 @@ bool GOST_3410_Verification_Operation::verify(const byte msg[], size_t msg_len,
 
 }
 
-BOTAN_REGISTER_PK_SIGNATURE_OP("GOST-34.10", GOST_3410_Signature_Operation);
-BOTAN_REGISTER_PK_VERIFY_OP("GOST-34.10", GOST_3410_Verification_Operation);
+std::unique_ptr<PK_Ops::Verification>
+GOST_3410_PublicKey::create_verification_op(const std::string& params,
+                                            const std::string& provider) const
+   {
+   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*/,
+                                          const std::string& params,
+                                          const std::string& provider) const
+   {
+   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 62a627c37..cca811896 100644
--- a/src/lib/pubkey/gost_3410/gost_3410.h
+++ b/src/lib/pubkey/gost_3410/gost_3410.h
@@ -59,6 +59,10 @@ class BOTAN_DLL GOST_3410_PublicKey : public virtual EC_PublicKey
       size_t message_part_size() const override
          { return domain().get_order().bytes(); }
 
+      std::unique_ptr<PK_Ops::Verification>
+         create_verification_op(const std::string& params,
+                                const std::string& provider) const override;
+
    protected:
       GOST_3410_PublicKey() {}
    };
@@ -88,6 +92,11 @@ class BOTAN_DLL GOST_3410_PrivateKey : public GOST_3410_PublicKey,
 
       AlgorithmIdentifier pkcs8_algorithm_identifier() const override
          { return EC_PublicKey::algorithm_identifier(); }
+
+      std::unique_ptr<PK_Ops::Signature>
+         create_signature_op(RandomNumberGenerator& rng,
+                             const std::string& params,
+                             const std::string& provider) const override;
    };
 
 }
diff --git a/src/lib/pubkey/info.txt b/src/lib/pubkey/info.txt
index 10eb12567..0e799f372 100644
--- a/src/lib/pubkey/info.txt
+++ b/src/lib/pubkey/info.txt
@@ -14,16 +14,16 @@ x509_key.cpp
 <header:public>
 blinding.h
 pk_keys.h
-pk_ops.h
+pk_ops_fwd.h
 pkcs8.h
 pubkey.h
-x509_key.h
 workfactor.h
+x509_key.h
 </header:public>
 
 <header:internal>
 pk_algs.h
-pk_utils.h
+pk_ops.h
 pk_ops_impl.h
 </header:internal>
 
diff --git a/src/lib/pubkey/keypair/keypair.cpp b/src/lib/pubkey/keypair/keypair.cpp
index 0f5a48541..2efd40b6e 100644
--- a/src/lib/pubkey/keypair/keypair.cpp
+++ b/src/lib/pubkey/keypair/keypair.cpp
@@ -19,8 +19,8 @@ bool encryption_consistency_check(RandomNumberGenerator& rng,
                                   const Private_Key& key,
                                   const std::string& padding)
    {
-   PK_Encryptor_EME encryptor(key, padding);
-   PK_Decryptor_EME decryptor(key, padding);
+   PK_Encryptor_EME encryptor(key, rng, padding);
+   PK_Decryptor_EME decryptor(key, rng, padding);
 
    /*
    Weird corner case, if the key is too small to encrypt anything at
@@ -48,7 +48,7 @@ bool signature_consistency_check(RandomNumberGenerator& rng,
                                  const Private_Key& key,
                                  const std::string& padding)
    {
-   PK_Signer signer(key, padding);
+   PK_Signer signer(key, rng, padding);
    PK_Verifier verifier(key, padding);
 
    std::vector<byte> message = unlock(rng.random_vec(16));
diff --git a/src/lib/pubkey/mce/mce_internal.h b/src/lib/pubkey/mce/mce_internal.h
index d35479080..526552944 100644
--- a/src/lib/pubkey/mce/mce_internal.h
+++ b/src/lib/pubkey/mce/mce_internal.h
@@ -14,7 +14,7 @@
 
 #include <botan/secmem.h>
 #include <botan/types.h>
-#include <botan/pk_ops.h>
+#include <botan/internal/pk_ops.h>
 #include <botan/mceliece.h>
 
 namespace Botan {
diff --git a/src/lib/pubkey/mce/mceliece.h b/src/lib/pubkey/mce/mceliece.h
index 311f0f253..c8b2606c5 100644
--- a/src/lib/pubkey/mce/mceliece.h
+++ b/src/lib/pubkey/mce/mceliece.h
@@ -58,6 +58,11 @@ class BOTAN_DLL McEliece_PublicKey : public virtual Public_Key
       bool operator==(const McEliece_PublicKey& other) const;
       bool operator!=(const McEliece_PublicKey& other) const { return !(*this == other); }
 
+      std::unique_ptr<PK_Ops::KEM_Encryption>
+         create_kem_encryption_op(RandomNumberGenerator& rng,
+                                  const std::string& params,
+                                  const std::string& provider) const override;
+
    protected:
       McEliece_PublicKey() : m_t(0), m_code_length(0) {}
 
@@ -115,6 +120,10 @@ class BOTAN_DLL McEliece_PrivateKey : public virtual McEliece_PublicKey,
 
       bool operator!=(const McEliece_PrivateKey& other) const { return !(*this == other); }
 
+      std::unique_ptr<PK_Ops::KEM_Decryption>
+         create_kem_decryption_op(RandomNumberGenerator& rng,
+                                  const std::string& params,
+                                  const std::string& provider) const override;
    private:
       polyn_gf2m m_g;
       std::vector<polyn_gf2m> m_sqrtmod;
diff --git a/src/lib/pubkey/mce/mceliece_key.cpp b/src/lib/pubkey/mce/mceliece_key.cpp
index 455d1f381..c65322348 100644
--- a/src/lib/pubkey/mce/mceliece_key.cpp
+++ b/src/lib/pubkey/mce/mceliece_key.cpp
@@ -15,7 +15,6 @@
 #include <botan/internal/bit_ops.h>
 #include <botan/internal/code_based_util.h>
 #include <botan/internal/pk_ops_impl.h>
-#include <botan/internal/pk_utils.h>
 #include <botan/der_enc.h>
 #include <botan/ber_dec.h>
 
@@ -352,11 +351,28 @@ class MCE_KEM_Decryptor : public PK_Ops::KEM_Decryption_with_KDF
       const McEliece_PrivateKey& m_key;
    };
 
-BOTAN_REGISTER_PK_KEM_ENCRYPTION_OP("McEliece", MCE_KEM_Encryptor);
-BOTAN_REGISTER_PK_KEM_DECRYPTION_OP("McEliece", MCE_KEM_Decryptor);
-
 }
 
+std::unique_ptr<PK_Ops::KEM_Encryption>
+McEliece_PublicKey::create_kem_encryption_op(RandomNumberGenerator& /*rng*/,
+                                             const std::string& params,
+                                             const std::string& provider) const
+   {
+   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
+   {
+   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/mceies/mceies.cpp b/src/lib/pubkey/mceies/mceies.cpp
index 95042e529..253e9ddee 100644
--- a/src/lib/pubkey/mceies/mceies.cpp
+++ b/src/lib/pubkey/mceies/mceies.cpp
@@ -36,7 +36,7 @@ mceies_encrypt(const McEliece_PublicKey& pubkey,
                RandomNumberGenerator& rng,
                const std::string& algo)
    {
-   PK_KEM_Encryptor kem_op(pubkey, "KDF1(SHA-512)");
+   PK_KEM_Encryptor kem_op(pubkey, rng, "KDF1(SHA-512)");
 
    secure_vector<byte> mce_ciphertext, mce_key;
    kem_op.encrypt(mce_ciphertext, mce_key, 64, rng);
@@ -74,7 +74,8 @@ mceies_decrypt(const McEliece_PrivateKey& privkey,
    {
    try
       {
-      PK_KEM_Decryptor kem_op(privkey, "KDF1(SHA-512)");
+      Null_RNG null_rng;
+      PK_KEM_Decryptor kem_op(privkey, null_rng, "KDF1(SHA-512)");
 
       const size_t mce_code_bytes = (privkey.get_code_length() + 7) / 8;
 
diff --git a/src/lib/pubkey/pk_keys.cpp b/src/lib/pubkey/pk_keys.cpp
index 9597ed08d..2c846d623 100644
--- a/src/lib/pubkey/pk_keys.cpp
+++ b/src/lib/pubkey/pk_keys.cpp
@@ -6,6 +6,7 @@
 */
 
 #include <botan/pk_keys.h>
+#include <botan/internal/pk_ops.h>
 #include <botan/der_enc.h>
 #include <botan/oids.h>
 #include <botan/hash.h>
@@ -78,4 +79,59 @@ std::string Private_Key::fingerprint(const std::string& alg) const
    return formatted_print;
    }
 
+std::unique_ptr<PK_Ops::Encryption>
+Public_Key::create_encryption_op(RandomNumberGenerator& /*rng*/,
+                                 const std::string& /*params*/,
+                                 const std::string& /*provider*/) const
+   {
+   throw Lookup_Error(algo_name() + " does not support encryption");
+   }
+
+std::unique_ptr<PK_Ops::KEM_Encryption>
+Public_Key::create_kem_encryption_op(RandomNumberGenerator& /*rng*/,
+                                     const std::string& /*params*/,
+                                     const std::string& /*provider*/) const
+   {
+   throw Lookup_Error(algo_name() + " does not support KEM encryption");
+   }
+
+std::unique_ptr<PK_Ops::Verification>
+Public_Key::create_verification_op(const std::string& /*params*/,
+                                   const std::string& /*provider*/) const
+   {
+   throw Lookup_Error(algo_name() + " does not support verification");
+   }
+
+std::unique_ptr<PK_Ops::Decryption>
+Private_Key::create_decryption_op(RandomNumberGenerator& /*rng*/,
+                                  const std::string& /*params*/,
+                                  const std::string& /*provider*/) const
+   {
+   throw Lookup_Error(algo_name() + " does not support decryption");
+   }
+
+std::unique_ptr<PK_Ops::KEM_Decryption>
+Private_Key::create_kem_decryption_op(RandomNumberGenerator& /*rng*/,
+                                      const std::string& /*params*/,
+                                      const std::string& /*provider*/) const
+   {
+   throw Lookup_Error(algo_name() + " does not support KEM decryption");
+   }
+
+std::unique_ptr<PK_Ops::Signature>
+Private_Key::create_signature_op(RandomNumberGenerator& /*rng*/,
+                                 const std::string& /*params*/,
+                                 const std::string& /*provider*/) const
+   {
+   throw Lookup_Error(algo_name() + " does not support signatures");
+   }
+
+std::unique_ptr<PK_Ops::Key_Agreement>
+Private_Key::create_key_agreement_op(RandomNumberGenerator& /*rng*/,
+                                     const std::string& /*params*/,
+                                     const std::string& /*provider*/) const
+   {
+   throw Lookup_Error(algo_name() + " does not support key agreement");
+   }
+
 }
diff --git a/src/lib/pubkey/pk_keys.h b/src/lib/pubkey/pk_keys.h
index 1a3047a57..5521f5b2c 100644
--- a/src/lib/pubkey/pk_keys.h
+++ b/src/lib/pubkey/pk_keys.h
@@ -15,12 +15,28 @@
 
 namespace Botan {
 
+class RandomNumberGenerator;
+
+namespace PK_Ops {
+
+class Encryption;
+class Decryption;
+class Key_Agreement;
+class KEM_Encryption;
+class KEM_Decryption;
+class Verification;
+class Signature;
+
+}
+
 /**
 * Public Key Base Class.
 */
 class BOTAN_DLL Public_Key
    {
    public:
+      virtual ~Public_Key() {}
+
       /**
       * Get the name of the underlying public key scheme.
       * @return name of the public key scheme
@@ -82,7 +98,48 @@ class BOTAN_DLL Public_Key
       */
       virtual std::vector<byte> x509_subject_public_key() const = 0;
 
-      virtual ~Public_Key() {}
+      // Internal or non-public declarations follow
+
+      /**
+      * This is an internal library function exposed on key types.
+      * In almost all cases applications should use wrappers in pubkey.h
+      *
+      * Return an encryption 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::Encryption>
+         create_encryption_op(RandomNumberGenerator& rng,
+                              const std::string& params,
+                              const std::string& provider) const;
+
+      /**
+      * This is an internal library function exposed on key types.
+      * In almost all cases applications should use wrappers in pubkey.h
+      *
+      * Return a KEM encryption 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::KEM_Encryption>
+         create_kem_encryption_op(RandomNumberGenerator& rng,
+                                  const std::string& params,
+                                  const std::string& provider) const;
+
+      /**
+      * This is an internal library function exposed on key types.
+      * In almost all cases applications should use wrappers in pubkey.h
+      *
+      * Return a verification operation for this key/params or throw
+      */
+      virtual std::unique_ptr<PK_Ops::Verification>
+         create_verification_op(const std::string& params,
+                                const std::string& provider) const;
+
    protected:
       /**
       * Self-test after loading a key
@@ -109,10 +166,73 @@ class BOTAN_DLL Private_Key : public virtual Public_Key
       virtual AlgorithmIdentifier pkcs8_algorithm_identifier() const
          { return algorithm_identifier(); }
 
+      // Internal or non-public declarations follow
+
       /**
        * @return Hash of the PKCS #8 encoding for this key object
        */
       std::string fingerprint(const std::string& alg = "SHA") const;
+
+      /**
+      * This is an internal library function exposed on key types.
+      * In almost all cases applications should use wrappers in pubkey.h
+      *
+      * Return an decryption 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::Decryption>
+         create_decryption_op(RandomNumberGenerator& rng,
+                              const std::string& params,
+                              const std::string& provider) const;
+
+      /**
+      * This is an internal library function exposed on key types.
+      * In almost all cases applications should use wrappers in pubkey.h
+      *
+      * Return a KEM decryption 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::KEM_Decryption>
+         create_kem_decryption_op(RandomNumberGenerator& rng,
+                                  const std::string& params,
+                                  const std::string& provider) const;
+
+      /**
+      * This is an internal library function exposed on key types.
+      * In almost all cases applications should use wrappers in pubkey.h
+      *
+      * Return a signature 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::Signature>
+         create_signature_op(RandomNumberGenerator& rng,
+                             const std::string& params,
+                             const std::string& provider) const;
+
+      /**
+      * This is an internal library function exposed on key types.
+      * In almost all cases applications should use wrappers in pubkey.h
+      *
+      * Return a key agreement 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::Key_Agreement>
+         create_key_agreement_op(RandomNumberGenerator& rng,
+                                 const std::string& params,
+                                 const std::string& provider) const;
+
    protected:
       /**
       * Self-test after loading a key
@@ -142,7 +262,8 @@ class BOTAN_DLL PK_Key_Agreement_Key : public virtual Private_Key
    };
 
 /*
-* Typedefs
+* Old compat typedefs
+* TODO: remove these?
 */
 typedef PK_Key_Agreement_Key PK_KA_Key;
 typedef Public_Key X509_PublicKey;
diff --git a/src/lib/pubkey/pk_ops_fwd.h b/src/lib/pubkey/pk_ops_fwd.h
new file mode 100644
index 000000000..16c2124fb
--- /dev/null
+++ b/src/lib/pubkey/pk_ops_fwd.h
@@ -0,0 +1,27 @@
+/*
+* PK Operation Types Forward Decls
+* (C) 2016 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_PK_OPERATIONS_FWD_H__
+#define BOTAN_PK_OPERATIONS_FWD_H__
+
+namespace Botan {
+
+namespace PK_Ops {
+
+class Encryption;
+class Decryption;
+class Verification;
+class Signature;
+class Key_Agreement;
+class KEM_Encryption;
+class KEM_Decryption;
+
+}
+
+}
+
+#endif
diff --git a/src/lib/pubkey/pk_ops_impl.h b/src/lib/pubkey/pk_ops_impl.h
index 9d02de5e5..5fe5623e7 100644
--- a/src/lib/pubkey/pk_ops_impl.h
+++ b/src/lib/pubkey/pk_ops_impl.h
@@ -7,7 +7,7 @@
 #ifndef BOTAN_PK_OPERATION_IMPL_H__
 #define BOTAN_PK_OPERATION_IMPL_H__
 
-#include <botan/pk_ops.h>
+#include <botan/internal/pk_ops.h>
 
 namespace Botan {
 
diff --git a/src/lib/pubkey/pk_utils.h b/src/lib/pubkey/pk_utils.h
deleted file mode 100644
index 04a0bf5ca..000000000
--- a/src/lib/pubkey/pk_utils.h
+++ /dev/null
@@ -1,40 +0,0 @@
-/*
-* Public Key Algos Utility Header
-* (C) 2015 Jack Lloyd
-*
-* Botan is released under the Simplified BSD License (see license.txt)
-*/
-
-#ifndef BOTAN_PK_UTILS_H__
-#define BOTAN_PK_UTILS_H__
-
-#include <botan/internal/algo_registry.h>
-#include <botan/internal/pk_ops_impl.h>
-#include <botan/numthry.h>
-#include <botan/reducer.h>
-#include <algorithm>
-
-namespace Botan {
-
-template<typename OP, typename T>
-OP* make_pk_op(const typename T::Spec& spec)
-   {
-   if(auto* key = dynamic_cast<const typename T::Key_Type*>(&spec.key()))
-      return new T(*key, spec.padding());
-   return nullptr;
-   }
-
-#define BOTAN_REGISTER_PK_OP(T, NAME, TYPE) BOTAN_REGISTER_NAMED_T(T, NAME, TYPE, (make_pk_op<T, TYPE>))
-
-#define BOTAN_REGISTER_PK_ENCRYPTION_OP(NAME, TYPE) BOTAN_REGISTER_PK_OP(PK_Ops::Encryption, NAME, TYPE)
-#define BOTAN_REGISTER_PK_DECRYPTION_OP(NAME, TYPE) BOTAN_REGISTER_PK_OP(PK_Ops::Decryption, NAME, TYPE)
-#define BOTAN_REGISTER_PK_SIGNATURE_OP(NAME, TYPE) BOTAN_REGISTER_PK_OP(PK_Ops::Signature, NAME, TYPE)
-#define BOTAN_REGISTER_PK_VERIFY_OP(NAME, TYPE) BOTAN_REGISTER_PK_OP(PK_Ops::Verification, NAME, TYPE)
-#define BOTAN_REGISTER_PK_KEY_AGREE_OP(NAME, TYPE) BOTAN_REGISTER_PK_OP(PK_Ops::Key_Agreement, NAME, TYPE)
-
-#define BOTAN_REGISTER_PK_KEM_ENCRYPTION_OP(NAME, TYPE) BOTAN_REGISTER_PK_OP(PK_Ops::KEM_Encryption, NAME, TYPE)
-#define BOTAN_REGISTER_PK_KEM_DECRYPTION_OP(NAME, TYPE) BOTAN_REGISTER_PK_OP(PK_Ops::KEM_Decryption, NAME, TYPE)
-
-}
-
-#endif
diff --git a/src/lib/pubkey/pubkey.cpp b/src/lib/pubkey/pubkey.cpp
index 8b24ee983..178eca282 100644
--- a/src/lib/pubkey/pubkey.cpp
+++ b/src/lib/pubkey/pubkey.cpp
@@ -8,29 +8,11 @@
 #include <botan/der_enc.h>
 #include <botan/ber_dec.h>
 #include <botan/bigint.h>
-#include <botan/internal/algo_registry.h>
+#include <botan/internal/pk_ops.h>
 #include <botan/internal/ct_utils.h>
 
 namespace Botan {
 
-namespace {
-
-template<typename T, typename Key>
-T* get_pk_op(const std::string& what, const Key& key, const std::string& pad,
-             const std::string& provider = "")
-   {
-   if(T* p = Algo_Registry<T>::global_registry().make(typename T::Spec(key, pad), provider))
-      return p;
-
-   const std::string err = what + " with " + key.algo_name() + "/" + pad + " not supported";
-   if(!provider.empty())
-      throw Lookup_Error(err + " with provider " + provider);
-   else
-      throw Lookup_Error(err);
-   }
-
-}
-
 secure_vector<byte> PK_Decryptor::decrypt(const byte in[], size_t length) const
    {
    byte valid_mask = 0;
@@ -54,8 +36,6 @@ PK_Decryptor::decrypt_or_random(const byte in[],
    {
    const secure_vector<byte> fake_pms = rng.random_vec(expected_pt_len);
 
-   //CT::poison(in, length);
-
    byte valid_mask = 0;
    secure_vector<byte> decoded = do_decrypt(valid_mask, in, length);
 
@@ -90,9 +70,6 @@ PK_Decryptor::decrypt_or_random(const byte in[],
                             /*from1*/fake_pms.data(),
                             expected_pt_len);
 
-   //CT::unpoison(in, length);
-   //CT::unpoison(decoded.data(), decoded.size());
-
    return decoded;
    }
 
@@ -107,12 +84,16 @@ PK_Decryptor::decrypt_or_random(const byte in[],
    }
 
 PK_Encryptor_EME::PK_Encryptor_EME(const Public_Key& key,
+                                   RandomNumberGenerator& rng,
                                    const std::string& padding,
                                    const std::string& provider)
    {
-   m_op.reset(get_pk_op<PK_Ops::Encryption>("Encryption", key, padding, provider));
+   m_op = key.create_encryption_op(rng, padding, provider);
+   BOTAN_ASSERT_NONNULL(m_op);
    }
 
+PK_Encryptor_EME::~PK_Encryptor_EME() { /* for unique_ptr */ }
+
 std::vector<byte>
 PK_Encryptor_EME::enc(const byte in[], size_t length, RandomNumberGenerator& rng) const
    {
@@ -124,12 +105,17 @@ size_t PK_Encryptor_EME::maximum_input_size() const
    return m_op->max_input_bits() / 8;
    }
 
-PK_Decryptor_EME::PK_Decryptor_EME(const Private_Key& key, const std::string& padding,
+PK_Decryptor_EME::PK_Decryptor_EME(const Private_Key& key,
+                                   RandomNumberGenerator& rng,
+                                   const std::string& padding,
                                    const std::string& provider)
    {
-   m_op.reset(get_pk_op<PK_Ops::Decryption>("Decryption", key, padding, provider));
+   m_op = key.create_decryption_op(rng, padding, provider);
+   BOTAN_ASSERT_NONNULL(m_op);
    }
 
+PK_Decryptor_EME::~PK_Decryptor_EME() { /* for unique_ptr */ }
+
 secure_vector<byte> PK_Decryptor_EME::do_decrypt(byte& valid_mask,
                                                  const byte in[], size_t in_len) const
    {
@@ -137,12 +123,16 @@ secure_vector<byte> PK_Decryptor_EME::do_decrypt(byte& valid_mask,
    }
 
 PK_KEM_Encryptor::PK_KEM_Encryptor(const Public_Key& key,
+                                   RandomNumberGenerator& rng,
                                    const std::string& param,
                                    const std::string& provider)
    {
-   m_op.reset(get_pk_op<PK_Ops::KEM_Encryption>("KEM", key, param, provider));
+   m_op = key.create_kem_encryption_op(rng, param, provider);
+   BOTAN_ASSERT_NONNULL(m_op);
    }
 
+PK_KEM_Encryptor::~PK_KEM_Encryptor() { /* for unique_ptr */ }
+
 void PK_KEM_Encryptor::encrypt(secure_vector<byte>& out_encapsulated_key,
                                secure_vector<byte>& out_shared_key,
                                size_t desired_shared_key_len,
@@ -159,12 +149,16 @@ void PK_KEM_Encryptor::encrypt(secure_vector<byte>& out_encapsulated_key,
    }
 
 PK_KEM_Decryptor::PK_KEM_Decryptor(const Private_Key& key,
+                                   RandomNumberGenerator& rng,
                                    const std::string& param,
                                    const std::string& provider)
    {
-   m_op.reset(get_pk_op<PK_Ops::KEM_Decryption>("KEM", key, param, provider));
+   m_op = key.create_kem_decryption_op(rng, param, provider);
+   BOTAN_ASSERT_NONNULL(m_op);
    }
 
+PK_KEM_Decryptor::~PK_KEM_Decryptor() { /* for unique_ptr */ }
+
 secure_vector<byte> PK_KEM_Decryptor::decrypt(const byte encap_key[],
                                               size_t encap_key_len,
                                               size_t desired_shared_key_len,
@@ -177,12 +171,29 @@ secure_vector<byte> PK_KEM_Decryptor::decrypt(const byte encap_key[],
    }
 
 PK_Key_Agreement::PK_Key_Agreement(const Private_Key& key,
+                                   RandomNumberGenerator& rng,
                                    const std::string& kdf,
                                    const std::string& provider)
    {
-   m_op.reset(get_pk_op<PK_Ops::Key_Agreement>("Key agreement", key, kdf, provider));
+   m_op = key.create_key_agreement_op(rng, kdf, provider);
+   BOTAN_ASSERT_NONNULL(m_op);
+   }
+
+PK_Key_Agreement::~PK_Key_Agreement() { /* for unique_ptr */ }
+
+PK_Key_Agreement& PK_Key_Agreement::operator=(PK_Key_Agreement&& other)
+   {
+   if(this != &other)
+      {
+      m_op = std::move(other.m_op);
+      }
+   return (*this);
    }
 
+PK_Key_Agreement::PK_Key_Agreement(PK_Key_Agreement&& other) :
+   m_op(std::move(other.m_op))
+   {}
+
 SymmetricKey PK_Key_Agreement::derive_key(size_t key_len,
                                           const byte in[], size_t in_len,
                                           const byte salt[],
@@ -234,14 +245,18 @@ std::vector<byte> der_decode_signature(const byte sig[], size_t len,
 }
 
 PK_Signer::PK_Signer(const Private_Key& key,
+                     RandomNumberGenerator& rng,
                      const std::string& emsa,
                      Signature_Format format,
                      const std::string& provider)
    {
-   m_op.reset(get_pk_op<PK_Ops::Signature>("Signing", key, emsa, provider));
+   m_op = key.create_signature_op(rng, emsa, provider);
+   BOTAN_ASSERT_NONNULL(m_op);
    m_sig_format = format;
    }
 
+PK_Signer::~PK_Signer() { /* for unique_ptr */ }
+
 void PK_Signer::update(const byte in[], size_t length)
    {
    m_op->update(in, length);
@@ -262,14 +277,17 @@ std::vector<byte> PK_Signer::signature(RandomNumberGenerator& rng)
    }
 
 PK_Verifier::PK_Verifier(const Public_Key& key,
-                         const std::string& emsa_name,
+                         const std::string& emsa,
                          Signature_Format format,
                          const std::string& provider)
    {
-   m_op.reset(get_pk_op<PK_Ops::Verification>("Verification", key, emsa_name, provider));
+   m_op = key.create_verification_op(emsa, provider);
+   BOTAN_ASSERT_NONNULL(m_op);
    m_sig_format = format;
    }
 
+PK_Verifier::~PK_Verifier() { /* for unique_ptr */ }
+
 void PK_Verifier::set_input_format(Signature_Format format)
    {
    if(m_op->message_parts() == 1 && format != IEEE_1363)
diff --git a/src/lib/pubkey/pubkey.h b/src/lib/pubkey/pubkey.h
index 26cbb1790..94332c8f0 100644
--- a/src/lib/pubkey/pubkey.h
+++ b/src/lib/pubkey/pubkey.h
@@ -9,13 +9,18 @@
 #define BOTAN_PUBKEY_H__
 
 #include <botan/pk_keys.h>
-#include <botan/pk_ops.h>
+#include <botan/pk_ops_fwd.h>
 #include <botan/symkey.h>
 #include <botan/rng.h>
 #include <botan/eme.h>
 #include <botan/emsa.h>
 #include <botan/kdf.h>
 
+#if defined(BOTAN_HAS_SYSTEM_RNG)
+  #include <botan/system_rng.h>
+  #define BOTAN_PUBKEY_INCLUDE_DEPRECATED_CONSTRUCTORS
+#endif
+
 namespace Botan {
 
 /**
@@ -66,7 +71,6 @@ class BOTAN_DLL PK_Encryptor
       virtual ~PK_Encryptor() {}
 
       PK_Encryptor(const PK_Encryptor&) = delete;
-
       PK_Encryptor& operator=(const PK_Encryptor&) = delete;
 
    private:
@@ -153,7 +157,7 @@ class BOTAN_DLL PK_Decryptor
 * messages. Use multiple calls update() to process large messages and
 * generate the signature by finally calling signature().
 */
-class BOTAN_DLL PK_Signer
+class BOTAN_DLL PK_Signer final
    {
    public:
 
@@ -165,10 +169,33 @@ class BOTAN_DLL PK_Signer
       * @param format the signature format to use
       */
       PK_Signer(const Private_Key& 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 Signer.
+      * @param key the key to use inside this signer
+      * @param emsa the EMSA to use
+      * An example would be "EMSA1(SHA-224)".
+      * @param format the signature format to use
+      */
+      BOTAN_DEPRECATED("Use constructor taking a RNG object")
+      PK_Signer(const Private_Key& key,
+                const std::string& emsa,
+                Signature_Format format = IEEE_1363,
+                const std::string& provider = "") :
+         PK_Signer(key, system_rng(), emsa, format, provider)
+         {}
+#endif
+
+      ~PK_Signer();
+
+      PK_Signer(const PK_Signer&) = delete;
+      PK_Signer& operator=(const PK_Signer&) = delete;
+
       /**
       * Sign a message all in one go
       * @param in the message to sign as a byte array
@@ -248,7 +275,7 @@ class BOTAN_DLL PK_Signer
 * messages. Use multiple calls update() to process large messages and
 * verify the signature by finally calling check_signature().
 */
-class BOTAN_DLL PK_Verifier
+class BOTAN_DLL PK_Verifier final
    {
    public:
       /**
@@ -262,6 +289,11 @@ class BOTAN_DLL PK_Verifier
                   Signature_Format format = IEEE_1363,
                   const std::string& provider = "");
 
+      ~PK_Verifier();
+
+      PK_Verifier& operator=(const PK_Verifier&) = delete;
+      PK_Verifier(const PK_Verifier&) = delete;
+
       /**
       * Verify a signature.
       * @param msg the message that the signature belongs to, as a byte array
@@ -353,7 +385,7 @@ class BOTAN_DLL PK_Verifier
 /**
 * Key used for key agreement
 */
-class BOTAN_DLL PK_Key_Agreement
+class BOTAN_DLL PK_Key_Agreement final
    {
    public:
 
@@ -364,9 +396,34 @@ class BOTAN_DLL PK_Key_Agreement
       * @param provider the algo provider to use (or empty for default)
       */
       PK_Key_Agreement(const Private_Key& key,
+                       RandomNumberGenerator& rng,
                        const std::string& kdf,
                        const std::string& provider = "");
 
+#if defined(BOTAN_PUBKEY_INCLUDE_DEPRECATED_CONSTRUCTORS)
+      /**
+      * Construct a PK Key Agreement.
+      * @param key the key to use
+      * @param kdf name of the KDF to use (or 'Raw' for no KDF)
+      * @param provider the algo provider to use (or empty for default)
+      */
+      BOTAN_DEPRECATED("Use constructor taking a RNG object")
+      PK_Key_Agreement(const Private_Key& key,
+                       const std::string& kdf,
+                       const std::string& provider = "") :
+         PK_Key_Agreement(key, system_rng(), kdf, provider)
+         {}
+#endif
+
+      ~PK_Key_Agreement();
+
+      // For ECIES
+      PK_Key_Agreement& operator=(PK_Key_Agreement&&);
+      PK_Key_Agreement(PK_Key_Agreement&&);
+
+      PK_Key_Agreement& operator=(const PK_Key_Agreement&) = delete;
+      PK_Key_Agreement(const PK_Key_Agreement&) = delete;
+
       /*
       * Perform Key Agreement Operation
       * @param key_len the desired key output size
@@ -437,19 +494,38 @@ class BOTAN_DLL PK_Key_Agreement
 * Encryption using a standard message recovery algorithm like RSA or
 * ElGamal, paired with an encoding scheme like OAEP.
 */
-class BOTAN_DLL PK_Encryptor_EME : public PK_Encryptor
+class BOTAN_DLL PK_Encryptor_EME final : public PK_Encryptor
    {
    public:
       size_t maximum_input_size() const override;
 
       /**
       * Construct an instance.
-      * @param key the key to use inside the decryptor
+      * @param key the key to use inside the encryptor
       * @param padding the message encoding scheme to use (eg "OAEP(SHA-256)")
       */
       PK_Encryptor_EME(const Public_Key& key,
+                       RandomNumberGenerator& rng,
                        const std::string& padding,
                        const std::string& provider = "");
+
+#if defined(BOTAN_PUBKEY_INCLUDE_DEPRECATED_CONSTRUCTORS)
+      /**
+      * Construct an instance.
+      * @param key the key to use inside the encryptor
+      * @param padding the message encoding scheme to use (eg "OAEP(SHA-256)")
+      */
+      BOTAN_DEPRECATED("Use constructor taking a RNG object")
+      PK_Encryptor_EME(const Public_Key& key,
+                       const std::string& padding,
+                       const std::string& provider = "") :
+         PK_Encryptor_EME(key, system_rng(), padding, provider) {}
+#endif
+
+      ~PK_Encryptor_EME();
+
+      PK_Encryptor_EME& operator=(const PK_Encryptor_EME&) = delete;
+      PK_Encryptor_EME(const PK_Encryptor_EME&) = delete;
    private:
       std::vector<byte> enc(const byte[], size_t,
                              RandomNumberGenerator& rng) const override;
@@ -460,17 +536,37 @@ class BOTAN_DLL PK_Encryptor_EME : public PK_Encryptor
 /**
 * Decryption with an MR algorithm and an EME.
 */
-class BOTAN_DLL PK_Decryptor_EME : public PK_Decryptor
+class BOTAN_DLL PK_Decryptor_EME final : public PK_Decryptor
    {
    public:
      /**
       * Construct an instance.
-      * @param key the key to use inside the encryptor
+      * @param key the key to use inside the decryptor
       * @param eme the EME to use
+      * @param provider
       */
       PK_Decryptor_EME(const Private_Key& key,
+                       RandomNumberGenerator& rng,
                        const std::string& eme,
                        const std::string& provider = "");
+
+
+#if defined(BOTAN_PUBKEY_INCLUDE_DEPRECATED_CONSTRUCTORS)
+      /**
+      * Construct an instance.
+      * @param key the key to use inside the decryptor
+      * @param padding the message encoding scheme to use (eg "OAEP(SHA-256)")
+      */
+      BOTAN_DEPRECATED("Use constructor taking a RNG object")
+      PK_Decryptor_EME(const Private_Key& key,
+                       const std::string& eme,
+                       const std::string& provider = "") :
+         PK_Decryptor_EME(key, system_rng(), eme, provider) {}
+#endif
+
+      ~PK_Decryptor_EME();
+      PK_Decryptor_EME& operator=(const PK_Decryptor_EME&) = delete;
+      PK_Decryptor_EME(const PK_Decryptor_EME&) = delete;
    private:
       secure_vector<byte> do_decrypt(byte& valid_mask,
                                      const byte in[],
@@ -479,13 +575,27 @@ class BOTAN_DLL PK_Decryptor_EME : public PK_Decryptor
       std::unique_ptr<PK_Ops::Decryption> m_op;
    };
 
-class BOTAN_DLL PK_KEM_Encryptor
+class BOTAN_DLL PK_KEM_Encryptor final
    {
    public:
       PK_KEM_Encryptor(const Public_Key& key,
+                       RandomNumberGenerator& rng,
                        const std::string& kem_param = "",
                        const std::string& provider = "");
 
+#if defined(BOTAN_PUBKEY_INCLUDE_DEPRECATED_CONSTRUCTORS)
+      BOTAN_DEPRECATED("Use constructor taking a RNG object")
+      PK_KEM_Encryptor(const Public_Key& key,
+                       const std::string& kem_param = "",
+                       const std::string& provider = "") :
+         PK_KEM_Encryptor(key, system_rng(), kem_param, provider) {}
+#endif
+
+      ~PK_KEM_Encryptor();
+
+      PK_KEM_Encryptor& operator=(const PK_KEM_Encryptor&) = delete;
+      PK_KEM_Encryptor(const PK_KEM_Encryptor&) = delete;
+
       void encrypt(secure_vector<byte>& out_encapsulated_key,
                    secure_vector<byte>& out_shared_key,
                    size_t desired_shared_key_len,
@@ -524,13 +634,27 @@ class BOTAN_DLL PK_KEM_Encryptor
       std::unique_ptr<PK_Ops::KEM_Encryption> m_op;
    };
 
-class BOTAN_DLL PK_KEM_Decryptor
+class BOTAN_DLL PK_KEM_Decryptor final
    {
    public:
       PK_KEM_Decryptor(const Private_Key& key,
+                       RandomNumberGenerator& rng,
                        const std::string& kem_param = "",
                        const std::string& provider = "");
 
+#if defined(BOTAN_PUBKEY_INCLUDE_DEPRECATED_CONSTRUCTORS)
+      BOTAN_DEPRECATED("Use constructor taking a RNG object")
+      PK_KEM_Decryptor(const Private_Key& key,
+                       const std::string& kem_param = "",
+                       const std::string& provider = "") :
+         PK_KEM_Decryptor(key, system_rng(), kem_param, provider)
+         {}
+#endif
+
+      ~PK_KEM_Decryptor();
+      PK_KEM_Decryptor& operator=(const PK_KEM_Decryptor&) = delete;
+      PK_KEM_Decryptor(const PK_KEM_Decryptor&) = delete;
+
       secure_vector<byte> decrypt(const byte encap_key[],
                                   size_t encap_key_len,
                                   size_t desired_shared_key_len,
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index 7f72ba210..b40f485e3 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -5,8 +5,8 @@
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#include <botan/internal/pk_utils.h>
 #include <botan/rsa.h>
+#include <botan/internal/pk_ops_impl.h>
 #include <botan/parsing.h>
 #include <botan/keypair.h>
 #include <botan/blinding.h>
@@ -16,6 +16,10 @@
 #include <botan/ber_dec.h>
 #include <future>
 
+#if defined(BOTAN_HAS_OPENSSL)
+  #include <botan/internal/openssl.h>
+#endif
+
 namespace Botan {
 
 size_t RSA_PublicKey::estimated_strength() const
@@ -189,7 +193,7 @@ class RSA_Private_Operation
    protected:
       size_t get_max_input_bits() const { return (m_n.bits() - 1); }
 
-      explicit RSA_Private_Operation(const RSA_PrivateKey& rsa) :
+      explicit RSA_Private_Operation(const RSA_PrivateKey& rsa, RandomNumberGenerator& rng) :
          m_n(rsa.get_n()),
          m_q(rsa.get_q()),
          m_c(rsa.get_c()),
@@ -198,6 +202,7 @@ class RSA_Private_Operation
          m_powermod_d2_q(rsa.get_d2(), rsa.get_q()),
          m_mod_p(rsa.get_p()),
          m_blinder(m_n,
+                   rng,
                    [this](const BigInt& k) { return m_powermod_e_n(k); },
                    [this](const BigInt& k) { return inverse_mod(k, m_n); })
          {
@@ -238,9 +243,9 @@ class RSA_Signature_Operation : public PK_Ops::Signature_with_EMSA,
 
       size_t max_input_bits() const override { return get_max_input_bits(); };
 
-      RSA_Signature_Operation(const RSA_PrivateKey& rsa, const std::string& emsa) :
+      RSA_Signature_Operation(const RSA_PrivateKey& rsa, const std::string& emsa, RandomNumberGenerator& rng) :
          PK_Ops::Signature_with_EMSA(emsa),
-         RSA_Private_Operation(rsa)
+         RSA_Private_Operation(rsa, rng)
          {
          }
 
@@ -263,9 +268,9 @@ class RSA_Decryption_Operation : public PK_Ops::Decryption_with_EME,
 
       size_t max_raw_input_bits() const override { return get_max_input_bits(); };
 
-      RSA_Decryption_Operation(const RSA_PrivateKey& rsa, const std::string& eme) :
+      RSA_Decryption_Operation(const RSA_PrivateKey& rsa, const std::string& eme, RandomNumberGenerator& rng) :
          PK_Ops::Decryption_with_EME(eme),
-         RSA_Private_Operation(rsa)
+         RSA_Private_Operation(rsa, rng)
          {
          }
 
@@ -286,9 +291,10 @@ class RSA_KEM_Decryption_Operation : public PK_Ops::KEM_Decryption_with_KDF,
       typedef RSA_PrivateKey Key_Type;
 
       RSA_KEM_Decryption_Operation(const RSA_PrivateKey& key,
-                                   const std::string& kdf) :
+                                   const std::string& kdf,
+                                   RandomNumberGenerator& rng) :
          PK_Ops::KEM_Decryption_with_KDF(kdf),
-         RSA_Private_Operation(key)
+         RSA_Private_Operation(key, rng)
          {}
 
       secure_vector<byte>
@@ -397,16 +403,122 @@ class RSA_KEM_Encryption_Operation : public PK_Ops::KEM_Encryption_with_KDF,
          }
    };
 
+}
 
-BOTAN_REGISTER_PK_ENCRYPTION_OP("RSA", RSA_Encryption_Operation);
-BOTAN_REGISTER_PK_DECRYPTION_OP("RSA", RSA_Decryption_Operation);
+std::unique_ptr<PK_Ops::Encryption>
+RSA_PublicKey::create_encryption_op(RandomNumberGenerator& /*rng*/,
+                                    const std::string& params,
+                                    const std::string& provider) const
+   {
+#if defined(BOTAN_HAS_OPENSSL)
+   if(provider == "openssl" || provider.empty())
+      {
+      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
 
-BOTAN_REGISTER_PK_SIGNATURE_OP("RSA", RSA_Signature_Operation);
-BOTAN_REGISTER_PK_VERIFY_OP("RSA", RSA_Verify_Operation);
+   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);
+   }
 
-BOTAN_REGISTER_PK_KEM_ENCRYPTION_OP("RSA", RSA_KEM_Encryption_Operation);
-BOTAN_REGISTER_PK_KEM_DECRYPTION_OP("RSA", RSA_KEM_Decryption_Operation);
+std::unique_ptr<PK_Ops::KEM_Encryption>
+RSA_PublicKey::create_kem_encryption_op(RandomNumberGenerator& /*rng*/,
+                                        const std::string& params,
+                                        const std::string& provider) const
+   {
+   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(const std::string& params,
+                                      const std::string& provider) const
+   {
+#if defined(BOTAN_HAS_OPENSSL)
+   if(provider == "openssl" || provider.empty())
+      {
+      std::unique_ptr<PK_Ops::Verification> res = make_openssl_rsa_ver_op(*this, params);
+      if(res)
+         return res;
+      }
+#endif
+
+   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>
+RSA_PrivateKey::create_decryption_op(RandomNumberGenerator& rng,
+                                     const std::string& params,
+                                     const std::string& provider) const
+   {
+#if defined(BOTAN_HAS_OPENSSL)
+   if(provider == "openssl" || provider.empty())
+      {
+      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
+
+   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
+   {
+   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>
+RSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
+                                    const std::string& params,
+                                    const std::string& provider) const
+   {
+#if defined(BOTAN_HAS_OPENSSL)
+   if(provider == "openssl" || provider.empty())
+      {
+      std::unique_ptr<PK_Ops::Signature> res = make_openssl_rsa_sig_op(*this, params);
+      if(res)
+         return res;
+      }
+#endif
+
+   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 85bd7ce58..ddfd23b05 100644
--- a/src/lib/pubkey/rsa/rsa.h
+++ b/src/lib/pubkey/rsa/rsa.h
@@ -52,6 +52,20 @@ class BOTAN_DLL RSA_PublicKey : public virtual Public_Key
 
       size_t estimated_strength() const override;
 
+      std::unique_ptr<PK_Ops::Encryption>
+         create_encryption_op(RandomNumberGenerator& rng,
+                              const std::string& params,
+                              const std::string& provider) const override;
+
+      std::unique_ptr<PK_Ops::KEM_Encryption>
+         create_kem_encryption_op(RandomNumberGenerator& rng,
+                                  const std::string& params,
+                                  const std::string& provider) const override;
+
+      std::unique_ptr<PK_Ops::Verification>
+         create_verification_op(const std::string& params,
+                                const std::string& provider) const override;
+
    protected:
       RSA_PublicKey() {}
 
@@ -119,6 +133,22 @@ class BOTAN_DLL RSA_PrivateKey : public Private_Key, public RSA_PublicKey
       const BigInt& get_d2() const { return m_d2; }
 
       secure_vector<byte> pkcs8_private_key() const override;
+
+      std::unique_ptr<PK_Ops::Decryption>
+         create_decryption_op(RandomNumberGenerator& rng,
+                              const std::string& params,
+                              const std::string& provider) const override;
+
+      std::unique_ptr<PK_Ops::KEM_Decryption>
+         create_kem_decryption_op(RandomNumberGenerator& rng,
+                                  const std::string& params,
+                                  const std::string& provider) const override;
+
+      std::unique_ptr<PK_Ops::Signature>
+         create_signature_op(RandomNumberGenerator& rng,
+                             const std::string& params,
+                             const std::string& provider) const override;
+
    private:
       BigInt m_d, m_p, m_q, m_d1, m_d2, m_c;
    };
diff --git a/src/lib/tls/msg_cert_verify.cpp b/src/lib/tls/msg_cert_verify.cpp
index 6b59e703f..ac8fa97fd 100644
--- a/src/lib/tls/msg_cert_verify.cpp
+++ b/src/lib/tls/msg_cert_verify.cpp
@@ -28,7 +28,7 @@ Certificate_Verify::Certificate_Verify(Handshake_IO& io,
    std::pair<std::string, Signature_Format> format =
       state.choose_sig_format(*priv_key, m_hash_algo, m_sig_algo, true, policy);
 
-   PK_Signer signer(*priv_key, format.first, format.second);
+   PK_Signer signer(*priv_key, rng, format.first, format.second);
 
    m_signature = signer.sign_message(state.hash().get_contents(), rng);
 
diff --git a/src/lib/tls/msg_client_kex.cpp b/src/lib/tls/msg_client_kex.cpp
index 0eceadb3b..02ebcc2c8 100644
--- a/src/lib/tls/msg_client_kex.cpp
+++ b/src/lib/tls/msg_client_kex.cpp
@@ -114,7 +114,7 @@ Client_Key_Exchange::Client_Key_Exchange(Handshake_IO& io,
 
          DH_PrivateKey priv_key(rng, group);
 
-         PK_Key_Agreement ka(priv_key, "Raw");
+         PK_Key_Agreement ka(priv_key, rng, "Raw");
 
          secure_vector<byte> dh_secret = CT::strip_leading_zeros(
             ka.derive_key(0, counterparty_key.public_value()).bits_of());
@@ -159,7 +159,7 @@ Client_Key_Exchange::Client_Key_Exchange(Handshake_IO& io,
          
          ECDH_PrivateKey priv_key(rng, group);
 
-         PK_Key_Agreement ka(priv_key, "Raw");
+         PK_Key_Agreement ka(priv_key, rng, "Raw");
 
          secure_vector<byte> ecdh_secret =
             ka.derive_key(0, counterparty_key.public_value()).bits_of();
@@ -232,7 +232,7 @@ Client_Key_Exchange::Client_Key_Exchange(Handshake_IO& io,
          m_pre_master[0] = offered_version.major_version();
          m_pre_master[1] = offered_version.minor_version();
 
-         PK_Encryptor_EME encryptor(*rsa_pub, "PKCS1v15");
+         PK_Encryptor_EME encryptor(*rsa_pub, rng, "PKCS1v15");
 
          const std::vector<byte> encrypted_key = encryptor.encrypt(m_pre_master, rng);
 
@@ -273,7 +273,7 @@ Client_Key_Exchange::Client_Key_Exchange(const std::vector<byte>& contents,
       TLS_Data_Reader reader("ClientKeyExchange", contents);
       const std::vector<byte> encrypted_pre_master = reader.get_range<byte>(2, 0, 65535);
 
-      PK_Decryptor_EME decryptor(*server_rsa_kex_key, "PKCS1v15");
+      PK_Decryptor_EME decryptor(*server_rsa_kex_key, rng, "PKCS1v15");
 
       const byte client_major = state.client_hello()->version().major_version();
       const byte client_minor = state.client_hello()->version().minor_version();
@@ -350,7 +350,7 @@ Client_Key_Exchange::Client_Key_Exchange(const std::vector<byte>& contents,
 
          try
             {
-            PK_Key_Agreement ka(*ka_key, "Raw");
+            PK_Key_Agreement ka(*ka_key, rng, "Raw");
 
             std::vector<byte> client_pubkey;
 
diff --git a/src/lib/tls/msg_server_kex.cpp b/src/lib/tls/msg_server_kex.cpp
index 33b980ba9..325e5d1b0 100644
--- a/src/lib/tls/msg_server_kex.cpp
+++ b/src/lib/tls/msg_server_kex.cpp
@@ -133,7 +133,7 @@ Server_Key_Exchange::Server_Key_Exchange(Handshake_IO& io,
       std::pair<std::string, Signature_Format> format =
          state.choose_sig_format(*signing_key, m_hash_algo, m_sig_algo, false, policy);
 
-      PK_Signer signer(*signing_key, format.first, format.second);
+      PK_Signer signer(*signing_key, rng, format.first, format.second);
 
       signer.update(state.client_hello()->random());
       signer.update(state.server_hello()->random());
diff --git a/src/lib/tls/tls_server.cpp b/src/lib/tls/tls_server.cpp
index 1676ef659..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() );
+       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
diff --git a/src/tests/main.cpp b/src/tests/main.cpp
index b771d9614..d80049d53 100644
--- a/src/tests/main.cpp
+++ b/src/tests/main.cpp
@@ -312,14 +312,29 @@ int main(int argc, char* argv[])
                                              BOTAN_VERSION_MINOR,
                                              BOTAN_VERSION_PATCH);
 
-   std::unique_ptr<Botan_CLI::Command> cmd(Botan_CLI::Command::get_cmd("test"));
+   try
+      {
+      std::unique_ptr<Botan_CLI::Command> cmd(Botan_CLI::Command::get_cmd("test"));
 
-   if(!cmd)
+      if(!cmd)
+         {
+         std::cout << "Unable to retrieve testing helper (program bug)\n"; // WTF
+         return 1;
+         }
+
+      std::vector<std::string> args(argv + 1, argv + argc);
+      return cmd->run(args);
+      }
+   catch(Botan::Exception& e)
       {
-      std::cout << "Unable to retrieve testing helper (program bug)\n"; // WTF
-      return 1;
+      std::cout << "Exiting with library exception " << e.what() << std::endl;
+      }
+   catch(std::exception& e)
+      {
+      std::cout << "Exiting with std exception " << e.what() << std::endl;
+      }
+   catch(...)
+      {
+      std::cout << "Exiting with unknown exception\n";
       }
-
-   std::vector<std::string> args(argv + 1, argv + argc);
-   return cmd->run(args);
    }
diff --git a/src/tests/test_c25519.cpp b/src/tests/test_c25519.cpp
index 67e2104c3..fcf63a0be 100644
--- a/src/tests/test_c25519.cpp
+++ b/src/tests/test_c25519.cpp
@@ -83,8 +83,8 @@ class Curve25519_Roundtrip_Test : public Test
 
             if(a_pub_key && b_pub_key)
                {
-               Botan::PK_Key_Agreement a_ka(*a_priv, "KDF2(SHA-256)");
-               Botan::PK_Key_Agreement b_ka(*b_priv, "KDF2(SHA-256)");
+               Botan::PK_Key_Agreement a_ka(*a_priv, Test::rng(), "KDF2(SHA-256)");
+               Botan::PK_Key_Agreement b_ka(*b_priv, Test::rng(), "KDF2(SHA-256)");
 
                const std::string context = "shared context value";
                Botan::SymmetricKey a_key = a_ka.derive_key(32, b_pub_key->public_value(), context);
diff --git a/src/tests/test_dh.cpp b/src/tests/test_dh.cpp
index e82ce522a..8724d92fb 100644
--- a/src/tests/test_dh.cpp
+++ b/src/tests/test_dh.cpp
@@ -66,7 +66,7 @@ class Diffie_Hellman_KAT_Tests : public PK_Key_Agreement_Test
          const Botan::BigInt x("46205663093589612668746163860870963912226379131190812163519349848291472898748");
          std::unique_ptr<Private_Key> privkey(new DH_PrivateKey(Test::rng(), grp, x));
 
-         std::unique_ptr<PK_Key_Agreement> kas(new PK_Key_Agreement(*privkey, "Raw"));
+         std::unique_ptr<PK_Key_Agreement> kas(new PK_Key_Agreement(*privkey, rng(), "Raw"));
 
          result.test_throws("agreement input too big", [&kas]()
             {
diff --git a/src/tests/test_dlies.cpp b/src/tests/test_dlies.cpp
index 2aa9b9b70..4ef3bc2ed 100644
--- a/src/tests/test_dlies.cpp
+++ b/src/tests/test_dlies.cpp
@@ -76,8 +76,8 @@ class DLIES_KAT_Tests : public Text_Based_Test
          Botan::DH_PrivateKey from(Test::rng(), domain, x1);
          Botan::DH_PrivateKey to(Test::rng(), domain, x2);
 
-         Botan::DLIES_Encryptor encryptor(from, kdf->clone(), enc.release(), cipher_key_len, mac->clone(), mac_key_len);
-         Botan::DLIES_Decryptor decryptor(to, kdf.release(), dec.release(), cipher_key_len, mac.release(), mac_key_len);
+         Botan::DLIES_Encryptor encryptor(from, Test::rng(), kdf->clone(), enc.release(), cipher_key_len, mac->clone(), mac_key_len);
+         Botan::DLIES_Decryptor decryptor(to, Test::rng(), kdf.release(), dec.release(), cipher_key_len, mac.release(), mac_key_len);
 
          if(!iv.empty())
             {
@@ -133,7 +133,7 @@ Test::Result test_xor()
             continue;
             }
 
-         Botan::DLIES_Encryptor encryptor(alice, kdf->clone(), mac->clone(), mac_key_len);
+         Botan::DLIES_Encryptor encryptor(alice, Test::rng(), kdf->clone(), mac->clone(), mac_key_len);
 
          // negative test: other pub key not set
          Botan::secure_vector<byte> plaintext = Test::rng().random_vec(32);
@@ -146,7 +146,7 @@ Test::Result test_xor()
          encryptor.set_other_key(bob.public_value());
          std::vector<byte> ciphertext = encryptor.encrypt(plaintext, Test::rng());
 
-         Botan::DLIES_Decryptor decryptor(bob, kdf->clone(), mac->clone(), mac_key_len);
+         Botan::DLIES_Decryptor decryptor(bob, Test::rng(), kdf->clone(), mac->clone(), mac_key_len);
 
          // negative test: ciphertext too short
          result.test_throws("ciphertext too short", [ &decryptor ]()
diff --git a/src/tests/test_ecies.cpp b/src/tests/test_ecies.cpp
index dea9b6266..0cbc5c2b4 100644
--- a/src/tests/test_ecies.cpp
+++ b/src/tests/test_ecies.cpp
@@ -54,9 +54,9 @@ void check_encrypt_decrypt(Test::Result& result, const Botan::ECDH_PrivateKey& p
                            const Botan::InitializationVector& iv, const std::string& label,
                            const std::vector<byte>& plaintext, const std::vector<byte>& ciphertext)
    {
-   Botan::ECIES_Encryptor ecies_enc(private_key, ecies_params);
+   Botan::ECIES_Encryptor ecies_enc(private_key, ecies_params, Test::rng());
    ecies_enc.set_other_key(other_private_key.public_point());
-   Botan::ECIES_Decryptor ecies_dec(other_private_key, ecies_params);
+   Botan::ECIES_Decryptor ecies_dec(other_private_key, ecies_params, Test::rng());
    if(!iv.bits_of().empty())
       {
       ecies_enc.set_initialization_vector(iv);
@@ -150,7 +150,7 @@ class ECIES_ISO_Tests : public Text_Based_Test
          // test secret derivation: ISO 18033 test vectors use KDF1 from ISO 18033
          // no cofactor-/oldcofactor-/singlehash-/check-mode and 128 byte secret length
          Botan::ECIES_KA_Params ka_params(eph_private_key.domain(), "KDF1-18033(SHA-1)", 128, compression_type, Flags::NONE);
-         const Botan::ECIES_KA_Operation ka(eph_private_key, ka_params, true);
+         const Botan::ECIES_KA_Operation ka(eph_private_key, ka_params, true, Test::rng());
          const Botan::SymmetricKey secret_key = ka.derive_secret(eph_public_key_bin, other_public_key_point);
          result.test_eq("derived secret key", secret_key.bits_of(), k);
 
@@ -266,7 +266,7 @@ Test::Result test_other_key_not_set()
          "HMAC(SHA-512)", 20, Botan::PointGFp::Compression_Type::COMPRESSED,
          flags);
 
-   Botan::ECIES_Encryptor ecies_enc(private_key, ecies_params);
+   Botan::ECIES_Encryptor ecies_enc(private_key, ecies_params, Test::rng());
 
    result.test_throws("encrypt not possible without setting other public key", [ &ecies_enc ]()
       {
@@ -291,7 +291,7 @@ Test::Result test_kdf_not_found()
          "HMAC(SHA-512)", 20, Botan::PointGFp::Compression_Type::COMPRESSED,
          flags);
 
-   Botan::ECIES_Encryptor ecies_enc(private_key, ecies_params);
+   Botan::ECIES_Encryptor ecies_enc(private_key, ecies_params, Test::rng());
 
    result.test_throws("kdf not found", [ &ecies_enc ]()
       {
@@ -316,7 +316,7 @@ Test::Result test_mac_not_found()
          "XYZMAC(SHA-512)", 20, Botan::PointGFp::Compression_Type::COMPRESSED,
          flags);
 
-   Botan::ECIES_Encryptor ecies_enc(private_key, ecies_params);
+   Botan::ECIES_Encryptor ecies_enc(private_key, ecies_params, Test::rng());
 
    result.test_throws("mac not found", [ &ecies_enc ]()
       {
@@ -341,7 +341,7 @@ Test::Result test_cipher_not_found()
          "HMAC(SHA-512)", 20, Botan::PointGFp::Compression_Type::COMPRESSED,
          flags);
 
-   Botan::ECIES_Encryptor ecies_enc(private_key, ecies_params);
+   Botan::ECIES_Encryptor ecies_enc(private_key, ecies_params, Test::rng());
 
    result.test_throws("cipher not found", [ &ecies_enc ]()
       {
@@ -409,7 +409,7 @@ Test::Result test_ciphertext_too_short()
    const Botan::ECIES_System_Params ecies_params(private_key.domain(), "KDF1-18033(SHA-512)", "AES-256/CBC", 32,
          "HMAC(SHA-512)", 16);
 
-   Botan::ECIES_Decryptor ecies_dec(other_private_key, ecies_params);
+   Botan::ECIES_Decryptor ecies_dec(other_private_key, ecies_params, Test::rng());
 
    result.test_throws("ciphertext too short", [ &ecies_dec ]()
       {
diff --git a/src/tests/test_mceliece.cpp b/src/tests/test_mceliece.cpp
index 5e3501b3e..0ffed8176 100644
--- a/src/tests/test_mceliece.cpp
+++ b/src/tests/test_mceliece.cpp
@@ -81,8 +81,8 @@ class McEliece_Keygen_Encrypt_Test : public Text_Based_Test
 
          try
             {
-            Botan::PK_KEM_Encryptor kem_enc(mce_priv, "KDF1(SHA-512)");
-            Botan::PK_KEM_Decryptor kem_dec(mce_priv, "KDF1(SHA-512)");
+            Botan::PK_KEM_Encryptor kem_enc(mce_priv, Test::rng(), "KDF1(SHA-512)");
+            Botan::PK_KEM_Decryptor kem_dec(mce_priv, Test::rng(), "KDF1(SHA-512)");
 
             Botan::secure_vector<byte> encap_key, prod_shared_key;
             kem_enc.encrypt(encap_key, prod_shared_key, 64, rng);
@@ -180,8 +180,8 @@ class McEliece_Tests : public Test
          {
          Test::Result result("McEliece KEM");
 
-         Botan::PK_KEM_Encryptor enc_op(pk, "KDF2(SHA-256)");
-         Botan::PK_KEM_Decryptor dec_op(sk, "KDF2(SHA-256)");
+         Botan::PK_KEM_Encryptor enc_op(pk, Test::rng(), "KDF2(SHA-256)");
+         Botan::PK_KEM_Decryptor dec_op(sk, Test::rng(), "KDF2(SHA-256)");
 
          for(size_t i = 0; i <= Test::soak_level(); i++)
             {
diff --git a/src/tests/test_pubkey.cpp b/src/tests/test_pubkey.cpp
index c7bd8f932..745b18614 100644
--- a/src/tests/test_pubkey.cpp
+++ b/src/tests/test_pubkey.cpp
@@ -102,7 +102,7 @@ PK_Signature_Generation_Test::run_one_test(const std::string&, const VarMap& var
 
       try
          {
-         signer.reset(new Botan::PK_Signer(*privkey, padding, Botan::IEEE_1363, sign_provider));
+         signer.reset(new Botan::PK_Signer(*privkey, Test::rng(), padding, Botan::IEEE_1363, sign_provider));
          }
       catch(Botan::Lookup_Error&)
          {
@@ -216,11 +216,14 @@ PK_Encryption_Decryption_Test::run_one_test(const std::string&, const VarMap& va
 
       try
          {
-         encryptor.reset(new Botan::PK_Encryptor_EME(*pubkey, padding, enc_provider));
+         encryptor.reset(new Botan::PK_Encryptor_EME(*pubkey, Test::rng(),padding, enc_provider));
+         }
+      catch(Botan::Provider_Not_Found&)
+         {
+         continue;
          }
       catch(Botan::Lookup_Error&)
          {
-         //result.test_note("Skipping encryption with provider " + enc_provider);
          continue;
          }
 
@@ -245,11 +248,14 @@ PK_Encryption_Decryption_Test::run_one_test(const std::string&, const VarMap& va
 
          try
             {
-            decryptor.reset(new Botan::PK_Decryptor_EME(*privkey, padding, dec_provider));
+            decryptor.reset(new Botan::PK_Decryptor_EME(*privkey, Test::rng(), padding, dec_provider));
+            }
+         catch(Botan::Provider_Not_Found&)
+            {
+            continue;
             }
          catch(Botan::Lookup_Error&)
             {
-            //result.test_note("Skipping decryption with provider " + dec_provider);
             continue;
             }
 
@@ -285,7 +291,12 @@ Test::Result PK_KEM_Test::run_one_test(const std::string&, const VarMap& vars)
    std::unique_ptr<Botan::PK_KEM_Encryptor> enc;
    try
       {
-      enc.reset(new Botan::PK_KEM_Encryptor(pubkey, kdf));
+      enc.reset(new Botan::PK_KEM_Encryptor(pubkey, Test::rng(), kdf));
+      }
+   catch(Botan::Provider_Not_Found& e)
+      {
+      result.test_note("Skipping test", e.what());
+      return result;
       }
    catch(Botan::Lookup_Error&)
       {
@@ -308,10 +319,16 @@ Test::Result PK_KEM_Test::run_one_test(const std::string&, const VarMap& vars)
    std::unique_ptr<Botan::PK_KEM_Decryptor> dec;
    try
       {
-      dec.reset(new Botan::PK_KEM_Decryptor(*privkey, kdf));
+      dec.reset(new Botan::PK_KEM_Decryptor(*privkey, Test::rng(), kdf));
       }
-   catch(Botan::Lookup_Error&)
+   catch(Botan::Provider_Not_Found& e)
       {
+      result.test_note("Skipping test", e.what());
+      return result;
+      }
+   catch(Botan::Lookup_Error& e)
+      {
+      result.test_note("Skipping test", e.what());
       return result;
       }
 
@@ -346,9 +363,12 @@ Test::Result PK_Key_Agreement_Test::run_one_test(const std::string& header, cons
 
       try
          {
-         kas.reset(new Botan::PK_Key_Agreement(*privkey, kdf, provider));
+         kas.reset(new Botan::PK_Key_Agreement(*privkey, Test::rng(), kdf, provider));
          result.test_eq(provider, "agreement", kas->derive_key(key_len, pubkey).bits_of(), shared);
          }
+      catch(Botan::Provider_Not_Found&)
+         {
+         }
       catch(Botan::Lookup_Error&)
          {
          //result.test_note("Skipping key agreement with with " + provider);
diff --git a/src/tests/tests.cpp b/src/tests/tests.cpp
index 1bb8b7303..13094f5dc 100644
--- a/src/tests/tests.cpp
+++ b/src/tests/tests.cpp
@@ -867,8 +867,16 @@ std::vector<Test::Result> Text_Based_Test::run()
          }
       }
 
-   std::vector<Test::Result> final_tests = run_final_tests();
-   results.insert(results.end(), final_tests.begin(), final_tests.end());
+   try
+      {
+      std::vector<Test::Result> final_tests = run_final_tests();
+      results.insert(results.end(), final_tests.begin(), final_tests.end());
+      }
+   catch(std::exception& e)
+      {
+      results.push_back(Test::Result::Failure(header_or_name,
+                                              "run_final_tests exception " + std::string(e.what())));
+      }
 
    return results;
    }
diff --git a/src/tests/unit_ecdh.cpp b/src/tests/unit_ecdh.cpp
index 40a10203a..83935a898 100644
--- a/src/tests/unit_ecdh.cpp
+++ b/src/tests/unit_ecdh.cpp
@@ -49,8 +49,8 @@ class ECDH_Unit_Tests : public Test
                Botan::ECDH_PrivateKey private_a(Test::rng(), dom_pars);
                Botan::ECDH_PrivateKey private_b(Test::rng(), dom_pars);
 
-               Botan::PK_Key_Agreement ka(private_a, "KDF2(SHA-512)");
-               Botan::PK_Key_Agreement kb(private_b, "KDF2(SHA-512)");
+               Botan::PK_Key_Agreement ka(private_a, Test::rng(), "KDF2(SHA-512)");
+               Botan::PK_Key_Agreement kb(private_b, Test::rng(), "KDF2(SHA-512)");
 
                Botan::SymmetricKey alice_key = ka.derive_key(32, private_b.public_value());
                Botan::SymmetricKey bob_key = kb.derive_key(32, private_a.public_value());
diff --git a/src/tests/unit_ecdsa.cpp b/src/tests/unit_ecdsa.cpp
index 421323fda..268e5cce0 100644
--- a/src/tests/unit_ecdsa.cpp
+++ b/src/tests/unit_ecdsa.cpp
@@ -58,7 +58,7 @@ Test::Result test_hash_larger_than_n()
       return result;
       }
 
-   Botan::PK_Signer pk_signer_160(priv_key, "EMSA1(SHA-1)");
+   Botan::PK_Signer pk_signer_160(priv_key, Test::rng(), "EMSA1(SHA-1)");
    Botan::PK_Verifier pk_verifier_160(priv_key, "EMSA1(SHA-1)");
 
    // Verify we can sign and verify with SHA-160
@@ -66,7 +66,7 @@ Test::Result test_hash_larger_than_n()
    result.test_eq("message verifies", pk_verifier_160.verify_message(message, signature_160), true);
 
    // Verify we can sign and verify with SHA-224
-   Botan::PK_Signer pk_signer(priv_key, "EMSA1(SHA-224)");
+   Botan::PK_Signer pk_signer(priv_key, Test::rng(), "EMSA1(SHA-224)");
    std::vector<byte> signature = pk_signer.sign_message(message, Test::rng());
    Botan::PK_Verifier pk_verifier(priv_key, "EMSA1(SHA-224)");
    result.test_eq("message verifies", pk_verifier.verify_message(message, signature), true);
@@ -122,7 +122,7 @@ Test::Result test_sign_then_ver()
    Botan::EC_Group dom_pars(Botan::OID("1.3.132.0.8"));
    Botan::ECDSA_PrivateKey ecdsa(Test::rng(), dom_pars);
 
-   Botan::PK_Signer signer(ecdsa, "EMSA1(SHA-256)");
+   Botan::PK_Signer signer(ecdsa, Test::rng(), "EMSA1(SHA-256)");
 
    auto msg = Botan::hex_decode("12345678901234567890abcdef12");
    std::vector<byte> sig = signer.sign_message(msg, Test::rng());
@@ -144,7 +144,7 @@ Test::Result test_ec_sign()
       {
       Botan::EC_Group dom_pars(Botan::OID("1.3.132.0.8"));
       Botan::ECDSA_PrivateKey priv_key(Test::rng(), dom_pars);
-      Botan::PK_Signer signer(priv_key, "EMSA1(SHA-224)");
+      Botan::PK_Signer signer(priv_key, Test::rng(), "EMSA1(SHA-224)");
       Botan::PK_Verifier verifier(priv_key, "EMSA1(SHA-224)");
 
       for(size_t i = 0; i != 256; ++i)
@@ -197,7 +197,7 @@ Test::Result test_ecdsa_create_save_load()
       Botan::EC_Group dom_pars(Botan::OID("1.3.132.0.8"));
       Botan::ECDSA_PrivateKey key(Test::rng(), dom_pars);
 
-      Botan::PK_Signer signer(key, "EMSA1(SHA-256)");
+      Botan::PK_Signer signer(key, Test::rng(), "EMSA1(SHA-256)");
       msg_signature = signer.sign_message(msg, Test::rng());
 
       ecc_private_key_pem = Botan::PKCS8::PEM_encode(key);
@@ -260,7 +260,7 @@ Test::Result test_read_pkcs8()
       Botan::ECDSA_PrivateKey* ecdsa_nodp = dynamic_cast<Botan::ECDSA_PrivateKey*>(loaded_key_nodp.get());
       result.confirm("key loaded", ecdsa_nodp);
 
-      Botan::PK_Signer signer(*ecdsa_nodp, "EMSA1(SHA-256)");
+      Botan::PK_Signer signer(*ecdsa_nodp, Test::rng(), "EMSA1(SHA-256)");
       Botan::PK_Verifier verifier(*ecdsa_nodp, "EMSA1(SHA-256)");
 
       std::vector<byte> signature_nodp = signer.sign_message(msg, Test::rng());
@@ -327,7 +327,7 @@ Test::Result test_curve_registry()
          Botan::EC_Group dom_pars(oid);
          Botan::ECDSA_PrivateKey ecdsa(Test::rng(), dom_pars);
 
-         Botan::PK_Signer signer(ecdsa, "EMSA1(SHA-256)");
+         Botan::PK_Signer signer(ecdsa, Test::rng(), "EMSA1(SHA-256)");
          Botan::PK_Verifier verifier(ecdsa, "EMSA1(SHA-256)");
 
          auto msg = Botan::hex_decode("12345678901234567890abcdef12");
diff --git a/src/tests/unit_tls.cpp b/src/tests/unit_tls.cpp
index f869f426b..28abe2d42 100644
--- a/src/tests/unit_tls.cpp
+++ b/src/tests/unit_tls.cpp
@@ -145,7 +145,7 @@ Botan::Credentials_Manager* create_creds(Botan::RandomNumberGenerator& rng,
                                                             "SHA-256",
                                                             rng);
 
-   Botan::X509_CA ca(ca_cert, *ca_key, "SHA-256");
+   Botan::X509_CA ca(ca_cert, *ca_key, "SHA-256", Test::rng());
 
    auto now = std::chrono::system_clock::now();
    Botan::X509_Time start_time(now);
@@ -326,7 +326,7 @@ Test::Result test_tls_handshake(Botan::TLS::Protocol_Version offer_version,
                if(client->is_active() && client_sent.empty())
                   {
                   // Choose random application data to send
-                  const size_t c_len = 1 + (static_cast<size_t>(rng.next_byte()) << 4) ^ rng.next_byte();
+                  const size_t c_len = 1 + ((static_cast<size_t>(rng.next_byte()) << 4) ^ rng.next_byte());
                   client_sent = unlock(rng.random_vec(c_len));
 
                   size_t sent_so_far = 0;
@@ -345,7 +345,7 @@ Test::Result test_tls_handshake(Botan::TLS::Protocol_Version offer_version,
                   {
                   result.test_eq("server->protocol", server->next_protocol(), "test/3");
 
-                  const size_t s_len = 1 + (static_cast<size_t>(rng.next_byte()) << 4) ^ rng.next_byte();
+                  const size_t s_len = 1 + ((static_cast<size_t>(rng.next_byte()) << 4) ^ rng.next_byte());
                   server_sent = unlock(rng.random_vec(s_len));
 
                   size_t sent_so_far = 0;
diff --git a/src/tests/unit_x509.cpp b/src/tests/unit_x509.cpp
index 4313e1373..26545bbdf 100644
--- a/src/tests/unit_x509.cpp
+++ b/src/tests/unit_x509.cpp
@@ -289,7 +289,7 @@ Test::Result test_x509_cert(const std::string& sig_algo, const std::string& hash
                                    Test::rng());
 
    /* Create the CA object */
-   Botan::X509_CA ca(ca_cert, *ca_key, hash_fn);
+   Botan::X509_CA ca(ca_cert, *ca_key, hash_fn, Test::rng());
 
    /* Sign the requests to create the certs */
    Botan::X509_Certificate user1_cert =
@@ -408,7 +408,7 @@ Test::Result test_usage(const std::string& sig_algo, const std::string& hash_fn
                                            Test::rng());
 
    /* Create the CA object */
-   Botan::X509_CA ca(ca_cert, *ca_key, hash_fn);
+   Botan::X509_CA ca(ca_cert, *ca_key, hash_fn, Test::rng());
 
    std::unique_ptr<Botan::Private_Key> user1_key(make_a_private_key(sig_algo));
 
@@ -496,7 +496,7 @@ Test::Result test_self_issued(const std::string& sig_algo, const std::string& ha
                                            Test::rng());
 
    /* Create the CA object */
-   Botan::X509_CA ca(ca_cert, *ca_key, hash_fn);
+   Botan::X509_CA ca(ca_cert, *ca_key, hash_fn, Test::rng());
 
    std::unique_ptr<Botan::Private_Key> user_key(make_a_private_key(sig_algo));