Remove Algo_Registry usage from public key code.

Instead the key types exposes operations like `create_encryption_op`
which will return the relevant operation if the algorithm supports it.

Changes pubkey.h interface, now RNG is passed at init time.
Blinder previous created its own RNG, now it takes it from app.

73 files changed, 1129 insertions, 437 deletions

diff --git a/src/cli/pubkey.cpp b/src/cli/pubkey.cpp
index 456ebbc8b..7e075202c 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); });
@@ -204,7 +204,7 @@ class PK_Verify final : public Command
          const std::string sig_padding =
             get_arg_or("emsa", algo_default_emsa(key->algo_name())) + "(" + get_arg("hash") + ")";
 
-         Botan::PK_Verifier verifier(*key, sig_padding);
+         Botan::PK_Verifier verifier(*key, rng(), sig_padding);
          this->read_file(get_arg("file"),
                          [&verifier](const uint8_t b[], size_t l) { verifier.update(b, l); });
 
diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index bd087e8e4..8666ff4ab 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,8 +888,8 @@ 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_Verifier ver(key, padding, Botan::IEEE_1363, provider);
+         Botan::PK_Signer   sig(key, rng(), padding, Botan::IEEE_1363, provider);
+         Botan::PK_Verifier ver(key, rng(), padding, Botan::IEEE_1363, provider);
 
          Timer sig_timer(nm, provider, padding + " sign");
          Timer ver_timer(nm, provider, padding + " verify");
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/ocsp.cpp b/src/lib/cert/x509/ocsp.cpp
index 761c5b436..fb6234cc8 100644
--- a/src/lib/cert/x509/ocsp.cpp
+++ b/src/lib/cert/x509/ocsp.cpp
@@ -61,7 +61,8 @@ void check_signature(const std::vector<byte>& tbs_response,
    Signature_Format format =
       (pub_key->message_parts() >= 2) ? DER_SEQUENCE : IEEE_1363;
 
-   PK_Verifier verifier(*pub_key, padding, format);
+   Null_RNG null_rng;
+   PK_Verifier verifier(*pub_key, null_rng, padding, format);
 
    if(!verifier.verify_message(ASN1::put_in_sequence(tbs_response), signature))
       throw Exception("Signature on OCSP response does not verify");
diff --git a/src/lib/cert/x509/x509_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/x509_obj.cpp b/src/lib/cert/x509/x509_obj.cpp
index 983be40b2..25da0155e 100644
--- a/src/lib/cert/x509/x509_obj.cpp
+++ b/src/lib/cert/x509/x509_obj.cpp
@@ -197,7 +197,8 @@ bool X509_Object::check_signature(const Public_Key& pub_key) const
       Signature_Format format =
          (pub_key.message_parts() >= 2) ? DER_SEQUENCE : IEEE_1363;
 
-      PK_Verifier verifier(pub_key, padding, format);
+      Null_RNG null_rng;
+      PK_Verifier verifier(pub_key, null_rng, padding, format);
 
       return verifier.verify_message(tbs_data(), signature());
       }
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..c7bd5774b 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/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..6593ba129 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)
+      {
+      return std::unique_ptr<PK_Ops::Key_Agreement>(new OpenSSL_ECDH_KA_Operation(key, params));
+      }
 
-}
+   return {};
+   }
+
+#endif
 
 }
 
diff --git a/src/lib/prov/openssl/openssl_rsa.cpp b/src/lib/prov/openssl/openssl_rsa.cpp
index ed8f2b0fd..5405ddda1 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>
@@ -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,46 @@ 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)
+   {
+   try
+      {
+      auto pad_info = get_openssl_enc_pad(params);
+      return std::unique_ptr<PK_Ops::Encryption>(
+         new OpenSSL_RSA_Encryption_Operation(key, pad_info.first, pad_info.second));
+      }
+   catch(...) {}
+
+   return {};
+   }
 
-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)
+   {
+   try
+      {
+      auto pad_info = get_openssl_enc_pad(params);
+      return std::unique_ptr<PK_Ops::Decryption>(new OpenSSL_RSA_Decryption_Operation(key, pad_info.first));
+      }
+   catch(...) {}
+
+   return {};
+   }
 
-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..8d8d79db7 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/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..9e21a3701 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/pk_ops.h>
 #include <botan/keypair.h>
 #include <botan/rng.h>
 
@@ -198,13 +198,23 @@ 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(RandomNumberGenerator& rng,
+                                        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..d391ce0b9 100644
--- a/src/lib/prov/pkcs11/p11_ecdsa.h
+++ b/src/lib/prov/pkcs11/p11_ecdsa.h
@@ -55,6 +55,11 @@ 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(RandomNumberGenerator& rng,
+                                const std::string& params,
+                                const std::string& provider) const override;
    };
 
 /// Represents a PKCS#11 ECDSA private key
@@ -107,6 +112,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..18965fd95 100644
--- a/src/lib/prov/pkcs11/p11_rsa.cpp
+++ b/src/lib/prov/pkcs11/p11_rsa.cpp
@@ -13,7 +13,7 @@
 #include <botan/internal/p11_mechanism.h>
 #include <botan/pk_ops.h>
 #include <botan/internal/algo_registry.h>
-#include <botan/internal/pk_utils.h>
+#include <botan/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,39 @@ 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(RandomNumberGenerator& /*rng*/,
+                                             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 +398,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..6a085a7d7 100644
--- a/src/lib/prov/pkcs11/p11_rsa.h
+++ b/src/lib/prov/pkcs11/p11_rsa.h
@@ -83,6 +83,16 @@ 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(RandomNumberGenerator& rng,
+                                const std::string& params,
+                                const std::string& provider) const override;
    };
 
 /// Properties for importing a PKCS#11 RSA private key
@@ -192,6 +202,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..73eb063ce 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/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..b1dfc59a1 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,14 @@ 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
+   {
+   return std::unique_ptr<PK_Ops::Key_Agreement>(new Curve25519_KA_Operation(*this, params));
+   }
 
 }
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..3cd47c581 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,12 @@ 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
+   {
+   return std::unique_ptr<PK_Ops::Key_Agreement>(new DH_KA_Operation(*this, params, rng));
+   }
 
 }
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..00d7b77d7 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,22 @@ 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(RandomNumberGenerator& rng,
+                                      const std::string& params,
+                                      const std::string& provider) const
+   {
+   return std::unique_ptr<PK_Ops::Verification>(new DSA_Verification_Operation(*this, params));
+   }
+
+std::unique_ptr<PK_Ops::Signature>
+DSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
+                                    const std::string& params,
+                                    const std::string& provider) const
+   {
+   return std::unique_ptr<PK_Ops::Signature>(new DSA_Signature_Operation(*this, params));
+   }
+
 }
diff --git a/src/lib/pubkey/dsa/dsa.h b/src/lib/pubkey/dsa/dsa.h
index 2653c9229..d8cd61df5 100644
--- a/src/lib/pubkey/dsa/dsa.h
+++ b/src/lib/pubkey/dsa/dsa.h
@@ -32,6 +32,11 @@ class BOTAN_DLL DSA_PublicKey : public virtual DL_Scheme_PublicKey
          }
 
       DSA_PublicKey(const DL_Group& group, const BigInt& y);
+
+      std::unique_ptr<PK_Ops::Verification>
+         create_verification_op(RandomNumberGenerator& rng,
+                                const std::string& params,
+                                const std::string& provider) const override;
    protected:
       DSA_PublicKey() {}
    };
@@ -52,6 +57,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;
    };
 
 }
diff --git a/src/lib/pubkey/ecdh/ecdh.cpp b/src/lib/pubkey/ecdh/ecdh.cpp
index 55e215bc1..79c63da8c 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 {
 
@@ -47,6 +51,22 @@ 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")
+      {
+      std::unique_ptr<PK_Ops::Key_Agreement> res = make_openssl_ecdh_ka_op(*this, params);
+      if(res)
+         return res;
+      }
+#endif
+
+   return std::unique_ptr<PK_Ops::Key_Agreement>(new ECDH_KA_Operation(*this, params));
+   }
+
 
 }
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..6a81ababf 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,39 @@ 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(RandomNumberGenerator& rng,
+                                        const std::string& params,
+                                        const std::string& provider) const
+   {
+#if defined(BOTAN_HAS_OPENSSL)
+   if(provider == "openssl")
+      {
+      std::unique_ptr<PK_Ops::Verification> res = make_openssl_ecdsa_ver_op(*this, params);
+      if(res)
+         return res;
+      }
+#endif
+   return std::unique_ptr<PK_Ops::Verification>(new ECDSA_Verification_Operation(*this, params));
+   }
+
+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")
+      {
+      std::unique_ptr<PK_Ops::Signature> res = make_openssl_ecdsa_sig_op(*this, params);
+      if(res)
+         return res;
+      }
+#endif
+
+   return std::unique_ptr<PK_Ops::Signature>(new ECDSA_Signature_Operation(*this, params));
+   }
+
 }
diff --git a/src/lib/pubkey/ecdsa/ecdsa.h b/src/lib/pubkey/ecdsa/ecdsa.h
index eed09afe6..9a55fbe48 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.h
+++ b/src/lib/pubkey/ecdsa/ecdsa.h
@@ -53,6 +53,10 @@ 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(RandomNumberGenerator& rng,
+                                const std::string& params,
+                                const std::string& provider) const override;
    protected:
       ECDSA_PublicKey() {}
    };
@@ -86,6 +90,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;
    };
 
 }
diff --git a/src/lib/pubkey/ecgdsa/ecgdsa.cpp b/src/lib/pubkey/ecgdsa/ecgdsa.cpp
index 30ea32817..b112a4466 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,22 @@ 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(RandomNumberGenerator& rng,
+                                         const std::string& params,
+                                         const std::string& provider) const
+   {
+   return std::unique_ptr<PK_Ops::Verification>(new ECGDSA_Verification_Operation(*this, params));
+   }
+
+std::unique_ptr<PK_Ops::Signature>
+ECGDSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
+                                       const std::string& params,
+                                       const std::string& provider) const
+   {
+   return std::unique_ptr<PK_Ops::Signature>(new ECGDSA_Signature_Operation(*this, params));
+   }
+
 }
diff --git a/src/lib/pubkey/ecgdsa/ecgdsa.h b/src/lib/pubkey/ecgdsa/ecgdsa.h
index 518adeeab..ec9180ee5 100644
--- a/src/lib/pubkey/ecgdsa/ecgdsa.h
+++ b/src/lib/pubkey/ecgdsa/ecgdsa.h
@@ -51,6 +51,10 @@ 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(RandomNumberGenerator& rng,
+                                const std::string& params,
+                                const std::string& provider) const override;
    protected:
       ECGDSA_PublicKey() {}
    };
@@ -84,6 +88,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;
    };
 
 }
diff --git a/src/lib/pubkey/ecies/ecies.cpp b/src/lib/pubkey/ecies/ecies.cpp
index d44d14803..d2e453bdf 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,
@@ -110,8 +121,6 @@ PK_Key_Agreement create_key_agreement(const PK_Key_Agreement_Key& private_key, c
    }
 }
 
-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)),
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..e61ceaa19 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,22 @@ 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(RandomNumberGenerator& rng,
+                                         const std::string& params,
+                                         const std::string& provider) const
+   {
+   return std::unique_ptr<PK_Ops::Verification>(new ECKCDSA_Verification_Operation(*this, params));
+   }
+
+std::unique_ptr<PK_Ops::Signature>
+ECKCDSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
+                                       const std::string& params,
+                                       const std::string& provider) const
+   {
+   return std::unique_ptr<PK_Ops::Signature>(new ECKCDSA_Signature_Operation(*this, params));
+   }
+
 }
diff --git a/src/lib/pubkey/eckcdsa/eckcdsa.h b/src/lib/pubkey/eckcdsa/eckcdsa.h
index b85c4025e..f8514776b 100644
--- a/src/lib/pubkey/eckcdsa/eckcdsa.h
+++ b/src/lib/pubkey/eckcdsa/eckcdsa.h
@@ -51,6 +51,10 @@ 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(RandomNumberGenerator& rng,
+                                const std::string& params,
+                                const std::string& provider) const override;
    protected:
       ECKCDSA_PublicKey() {}
    };
@@ -84,6 +88,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;
    };
 
 }
diff --git a/src/lib/pubkey/elgamal/elgamal.cpp b/src/lib/pubkey/elgamal/elgamal.cpp
index 37dfe89cf..fbbd09226 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,22 @@ 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
+   {
+   return std::unique_ptr<PK_Ops::Encryption>(new ElGamal_Encryption_Operation(*this, params));
+   }
+
+std::unique_ptr<PK_Ops::Decryption>
+ElGamal_PrivateKey::create_decryption_op(RandomNumberGenerator& rng,
+                                         const std::string& params,
+                                         const std::string& /*provider*/) const
+   {
+   return std::unique_ptr<PK_Ops::Decryption>(new ElGamal_Decryption_Operation(*this, params, rng));
+   }
+
 }
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..c37c8c845 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,20 @@ 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(RandomNumberGenerator& rng,
+                                            const std::string& params,
+                                            const std::string& provider) const
+   {
+   return std::unique_ptr<PK_Ops::Verification>(new GOST_3410_Verification_Operation(*this, params));
+   }
+
+std::unique_ptr<PK_Ops::Signature>
+GOST_3410_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
+                                          const std::string& params,
+                                          const std::string& provider) const
+   {
+   return std::unique_ptr<PK_Ops::Signature>(new GOST_3410_Signature_Operation(*this, params));
+   }
 
 }
diff --git a/src/lib/pubkey/gost_3410/gost_3410.h b/src/lib/pubkey/gost_3410/gost_3410.h
index 62a627c37..9d79f48d7 100644
--- a/src/lib/pubkey/gost_3410/gost_3410.h
+++ b/src/lib/pubkey/gost_3410/gost_3410.h
@@ -59,6 +59,11 @@ 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(RandomNumberGenerator& rng,
+                                const std::string& params,
+                                const std::string& provider) const override;
+
    protected:
       GOST_3410_PublicKey() {}
    };
@@ -88,6 +93,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;
    };
 
 }
diff --git a/src/lib/pubkey/info.txt b/src/lib/pubkey/info.txt
index 10eb12567..393e089e2 100644
--- a/src/lib/pubkey/info.txt
+++ b/src/lib/pubkey/info.txt
@@ -23,7 +23,6 @@ workfactor.h
 
 <header:internal>
 pk_algs.h
-pk_utils.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..6ea514d34 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,8 +48,8 @@ bool signature_consistency_check(RandomNumberGenerator& rng,
                                  const Private_Key& key,
                                  const std::string& padding)
    {
-   PK_Signer signer(key, padding);
-   PK_Verifier verifier(key, padding);
+   PK_Signer signer(key, rng, padding);
+   PK_Verifier verifier(key, rng, padding);
 
    std::vector<byte> message = unlock(rng.random_vec(16));
 
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..b5eed5a38 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,24 @@ 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
+   {
+   return std::unique_ptr<PK_Ops::KEM_Encryption>(new MCE_KEM_Encryptor(*this, params));
+   }
+
+std::unique_ptr<PK_Ops::KEM_Decryption>
+McEliece_PrivateKey::create_kem_decryption_op(RandomNumberGenerator& /*rng*/,
+                                              const std::string& params,
+                                              const std::string& /*provider*/) const
+   {
+   return std::unique_ptr<PK_Ops::KEM_Decryption>(new MCE_KEM_Decryptor(*this, params));
+   }
+
 }
 
 
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..ff57d88cc 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/pk_ops.h>
 #include <botan/der_enc.h>
 #include <botan/oids.h>
 #include <botan/hash.h>
@@ -78,4 +79,60 @@ 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(RandomNumberGenerator& /*rng*/,
+                                   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..9de884103 100644
--- a/src/lib/pubkey/pk_keys.h
+++ b/src/lib/pubkey/pk_keys.h
@@ -15,6 +15,20 @@
 
 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.
 */
@@ -82,6 +96,42 @@ class BOTAN_DLL Public_Key
       */
       virtual std::vector<byte> x509_subject_public_key() const = 0;
 
+      /**
+      * 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;
+
+      /**
+      * 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;
+
+      /**
+      * Return a verification operation for this key/params or throw
+      *
+      * @param rng a random number generator. The PK_Op may maintain a
+      * reference to the RNG and use it many times. The rng must outlive
+      * any operations which reference it.
+      */
+      virtual std::unique_ptr<PK_Ops::Verification>
+         create_verification_op(RandomNumberGenerator& rng,
+                                const std::string& params,
+                                const std::string& provider) const;
+
       virtual ~Public_Key() {}
    protected:
       /**
@@ -113,6 +163,55 @@ class BOTAN_DLL Private_Key : public virtual Public_Key
        * @return Hash of the PKCS #8 encoding for this key object
        */
       std::string fingerprint(const std::string& alg = "SHA") const;
+
+      /**
+      * 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;
+
+      /**
+      * 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;
+
+      /**
+      * 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;
+
+      /**
+      * 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 +241,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_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..51869326a 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/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,10 +84,12 @@ 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);
    }
 
 std::vector<byte>
@@ -124,10 +103,13 @@ 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);
    }
 
 secure_vector<byte> PK_Decryptor_EME::do_decrypt(byte& valid_mask,
@@ -137,10 +119,12 @@ 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);
    }
 
 void PK_KEM_Encryptor::encrypt(secure_vector<byte>& out_encapsulated_key,
@@ -159,10 +143,12 @@ 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);
    }
 
 secure_vector<byte> PK_KEM_Decryptor::decrypt(const byte encap_key[],
@@ -177,10 +163,12 @@ 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);
    }
 
 SymmetricKey PK_Key_Agreement::derive_key(size_t key_len,
@@ -234,11 +222,13 @@ 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;
    }
 
@@ -262,11 +252,13 @@ std::vector<byte> PK_Signer::signature(RandomNumberGenerator& rng)
    }
 
 PK_Verifier::PK_Verifier(const Public_Key& key,
-                         const std::string& emsa_name,
+                         RandomNumberGenerator& rng,
+                         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(rng, emsa, provider);
+   BOTAN_ASSERT_NONNULL(m_op);
    m_sig_format = format;
    }
 
diff --git a/src/lib/pubkey/pubkey.h b/src/lib/pubkey/pubkey.h
index 26cbb1790..18b5d0f9b 100644
--- a/src/lib/pubkey/pubkey.h
+++ b/src/lib/pubkey/pubkey.h
@@ -16,6 +16,11 @@
 #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 {
 
 /**
@@ -165,10 +170,28 @@ 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
+
       /**
       * Sign a message all in one go
       * @param in the message to sign as a byte array
@@ -258,10 +281,27 @@ class BOTAN_DLL PK_Verifier
       * @param format the signature format to use
       */
       PK_Verifier(const Public_Key& pub_key,
+                  RandomNumberGenerator& rng,
                   const std::string& emsa,
                   Signature_Format format = IEEE_1363,
                   const std::string& provider = "");
 
+#if defined(BOTAN_PUBKEY_INCLUDE_DEPRECATED_CONSTRUCTORS)
+      /**
+      * Construct a PK Verifier.
+      * @param pub_key the public key to verify against
+      * @param emsa the EMSA to use (eg "EMSA3(SHA-1)")
+      * @param format the signature format to use
+      */
+      BOTAN_DEPRECATED("Use constructor taking a RNG object")
+      PK_Verifier(const Public_Key& pub_key,
+                  const std::string& emsa,
+                  Signature_Format format = IEEE_1363,
+                  const std::string& provider = "") :
+         PK_Verifier(pub_key, system_rng(), emsa, format, provider)
+         {}
+#endif
+
       /**
       * Verify a signature.
       * @param msg the message that the signature belongs to, as a byte array
@@ -364,9 +404,25 @@ 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
+
       /*
       * Perform Key Agreement Operation
       * @param key_len the desired key output size
@@ -444,12 +500,27 @@ class BOTAN_DLL PK_Encryptor_EME : public PK_Encryptor
 
       /**
       * 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
+
    private:
       std::vector<byte> enc(const byte[], size_t,
                              RandomNumberGenerator& rng) const override;
@@ -465,12 +536,29 @@ class BOTAN_DLL PK_Decryptor_EME : 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
+
    private:
       secure_vector<byte> do_decrypt(byte& valid_mask,
                                      const byte in[],
@@ -483,9 +571,18 @@ class BOTAN_DLL PK_KEM_Encryptor
    {
    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
+
       void encrypt(secure_vector<byte>& out_encapsulated_key,
                    secure_vector<byte>& out_shared_key,
                    size_t desired_shared_key_len,
@@ -528,9 +625,19 @@ class BOTAN_DLL PK_KEM_Decryptor
    {
    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
+
       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..c8d1e7afc 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,90 @@ 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")
+      {
+      std::unique_ptr<PK_Ops::Encryption> res = make_openssl_rsa_enc_op(*this, params);
+      if(res)
+         return res;
+      }
+#endif
 
-BOTAN_REGISTER_PK_SIGNATURE_OP("RSA", RSA_Signature_Operation);
-BOTAN_REGISTER_PK_VERIFY_OP("RSA", RSA_Verify_Operation);
+   return std::unique_ptr<PK_Ops::Encryption>(new RSA_Encryption_Operation(*this, params));
+   }
 
-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
+   {
+   return std::unique_ptr<PK_Ops::KEM_Encryption>(new RSA_KEM_Encryption_Operation(*this, params));
+   }
 
-}
+std::unique_ptr<PK_Ops::Verification>
+RSA_PublicKey::create_verification_op(RandomNumberGenerator& rng,
+                                      const std::string& params,
+                                      const std::string& provider) const
+   {
+#if defined(BOTAN_HAS_OPENSSL)
+   if(provider == "openssl")
+      {
+      std::unique_ptr<PK_Ops::Verification> res = make_openssl_rsa_ver_op(*this, params);
+      if(res)
+         return res;
+      }
+#endif
+
+   return std::unique_ptr<PK_Ops::Verification>(new RSA_Verify_Operation(*this, params));
+   }
+
+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")
+      {
+      std::unique_ptr<PK_Ops::Decryption> res = make_openssl_rsa_dec_op(*this, params);
+      if(res)
+         return res;
+      }
+#endif
+
+   return std::unique_ptr<PK_Ops::Decryption>(new RSA_Decryption_Operation(*this, params, rng));
+   }
+
+std::unique_ptr<PK_Ops::KEM_Decryption>
+RSA_PrivateKey::create_kem_decryption_op(RandomNumberGenerator& rng,
+                                         const std::string& params,
+                                         const std::string& /*provider*/) const
+   {
+   return std::unique_ptr<PK_Ops::KEM_Decryption>(new RSA_KEM_Decryption_Operation(*this, params, rng));
+   }
+
+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")
+      {
+      std::unique_ptr<PK_Ops::Signature> res = make_openssl_rsa_sig_op(*this, params);
+      if(res)
+         return res;
+      }
+#endif
+
+   return std::unique_ptr<PK_Ops::Signature>(new RSA_Signature_Operation(*this, params, rng));
+   }
 
 }
diff --git a/src/lib/pubkey/rsa/rsa.h b/src/lib/pubkey/rsa/rsa.h
index 85bd7ce58..203a3a323 100644
--- a/src/lib/pubkey/rsa/rsa.h
+++ b/src/lib/pubkey/rsa/rsa.h
@@ -52,6 +52,21 @@ 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(RandomNumberGenerator& rng,
+                                const std::string& params,
+                                const std::string& provider) const override;
+
    protected:
       RSA_PublicKey() {}
 
@@ -119,6 +134,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..cc162f8a0 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);
 
@@ -78,7 +78,8 @@ std::vector<byte> Certificate_Verify::serialize() const
 */
 bool Certificate_Verify::verify(const X509_Certificate& cert,
                                 const Handshake_State& state,
-                                const Policy& policy) const
+                                const Policy& policy,
+                                RandomNumberGenerator& rng) const
    {
    std::unique_ptr<Public_Key> key(cert.subject_public_key());
 
@@ -88,7 +89,7 @@ bool Certificate_Verify::verify(const X509_Certificate& cert,
       state.parse_sig_format(*key.get(), m_hash_algo, m_sig_algo,
                              true, policy);
 
-   PK_Verifier verifier(*key, format.first, format.second);
+   PK_Verifier verifier(*key, rng, format.first, format.second);
 
    return verifier.verify_message(state.hash().get_contents(), m_signature);
    }
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..3df23955b 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());
@@ -237,7 +237,8 @@ std::vector<byte> Server_Key_Exchange::serialize() const
 */
 bool Server_Key_Exchange::verify(const Public_Key& server_key,
                                  const Handshake_State& state,
-                                 const Policy& policy) const
+                                 const Policy& policy,
+                                 RandomNumberGenerator& rng) const
    {
    policy.check_peer_key_acceptable(server_key);
 
@@ -245,7 +246,7 @@ bool Server_Key_Exchange::verify(const Public_Key& server_key,
       state.parse_sig_format(server_key, m_hash_algo, m_sig_algo,
                              false, policy);
 
-   PK_Verifier verifier(server_key, format.first, format.second);
+   PK_Verifier verifier(server_key, rng, format.first, format.second);
 
    verifier.update(state.client_hello()->random());
    verifier.update(state.server_hello()->random());
diff --git a/src/lib/tls/tls_client.cpp b/src/lib/tls/tls_client.cpp
index 0e72b9a28..6bfbdc008 100644
--- a/src/lib/tls/tls_client.cpp
+++ b/src/lib/tls/tls_client.cpp
@@ -415,7 +415,7 @@ void Client::process_handshake_msg(const Handshake_State* active_state,
          {
          const Public_Key& server_key = state.get_server_public_Key();
 
-         if(!state.server_kex()->verify(server_key, state, policy()))
+         if(!state.server_kex()->verify(server_key, state, policy(), rng()))
             {
             throw TLS_Exception(Alert::DECRYPT_ERROR,
                                 "Bad signature on server key exchange");
diff --git a/src/lib/tls/tls_messages.h b/src/lib/tls/tls_messages.h
index 25228c865..76421bf4a 100644
--- a/src/lib/tls/tls_messages.h
+++ b/src/lib/tls/tls_messages.h
@@ -482,7 +482,8 @@ class BOTAN_DLL Certificate_Verify final : public Handshake_Message
       */
       bool verify(const X509_Certificate& cert,
                   const Handshake_State& state,
-                  const Policy& policy) const;
+                  const Policy& policy,
+                  RandomNumberGenerator& rng) const;
 
       Certificate_Verify(Handshake_IO& io,
                          Handshake_State& state,
@@ -551,7 +552,8 @@ class Server_Key_Exchange final : public Handshake_Message
 
       bool verify(const Public_Key& server_key,
                   const Handshake_State& state,
-                  const Policy& policy) const;
+                  const Policy& policy,
+                  RandomNumberGenerator& rng) const;
 
       // Only valid for certain kex types
       const Private_Key& server_kex_key() const;
diff --git a/src/lib/tls/tls_server.cpp b/src/lib/tls/tls_server.cpp
index 1676ef659..510a30421 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(), rng() );
 
     pending_state.hash().update ( pending_state.handshake_io().format ( contents, type ) );
 
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_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..04fa6292f 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&)
          {
@@ -130,7 +130,7 @@ PK_Signature_Generation_Test::run_one_test(const std::string&, const VarMap& var
 
          try
             {
-            verifier.reset(new Botan::PK_Verifier(*pubkey, padding, Botan::IEEE_1363, verify_provider));
+            verifier.reset(new Botan::PK_Verifier(*pubkey, Test::rng(), padding, Botan::IEEE_1363, verify_provider));
             }
          catch(Botan::Lookup_Error&)
             {
@@ -168,7 +168,7 @@ PK_Signature_Verification_Test::run_one_test(const std::string&, const VarMap& v
 
       try
          {
-         verifier.reset(new Botan::PK_Verifier(*pubkey, padding, Botan::IEEE_1363, verify_provider));
+         verifier.reset(new Botan::PK_Verifier(*pubkey, Test::rng(), padding, Botan::IEEE_1363, verify_provider));
          result.test_eq("correct signature valid", verifier->verify_message(message, signature), true);
          check_invalid_signatures(result, *verifier, message, signature);
          }
@@ -216,7 +216,7 @@ 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::Lookup_Error&)
          {
@@ -245,7 +245,7 @@ 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::Lookup_Error&)
             {
@@ -285,7 +285,7 @@ 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::Lookup_Error&)
       {
@@ -308,7 +308,7 @@ 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&)
       {
@@ -346,7 +346,7 @@ 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::Lookup_Error&)
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..869ca7716 100644
--- a/src/tests/unit_ecdsa.cpp
+++ b/src/tests/unit_ecdsa.cpp
@@ -58,17 +58,17 @@ Test::Result test_hash_larger_than_n()
       return result;
       }
 
-   Botan::PK_Signer pk_signer_160(priv_key, "EMSA1(SHA-1)");
-   Botan::PK_Verifier pk_verifier_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, Test::rng(), "EMSA1(SHA-1)");
 
    // Verify we can sign and verify with SHA-160
    std::vector<byte> signature_160 = pk_signer_160.sign_message(message, Test::rng());
    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)");
+   Botan::PK_Verifier pk_verifier(priv_key, Test::rng(), "EMSA1(SHA-224)");
    result.test_eq("message verifies", pk_verifier.verify_message(message, signature), true);
 
    return result;
@@ -122,12 +122,12 @@ 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());
 
-   Botan::PK_Verifier verifier(ecdsa, "EMSA1(SHA-256)");
+   Botan::PK_Verifier verifier(ecdsa, Test::rng(), "EMSA1(SHA-256)");
 
    result.confirm("signature verifies", verifier.verify_message(msg, sig));
 
@@ -144,8 +144,8 @@ 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_Verifier verifier(priv_key, "EMSA1(SHA-224)");
+      Botan::PK_Signer signer(priv_key, Test::rng(), "EMSA1(SHA-224)");
+      Botan::PK_Verifier verifier(priv_key, Test::rng(), "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);
@@ -212,7 +212,7 @@ Test::Result test_ecdsa_create_save_load()
    Botan::ECDSA_PrivateKey* loaded_ec_key = dynamic_cast<Botan::ECDSA_PrivateKey*>(loaded_key.get());
    result.confirm("the loaded key could be converted into an ECDSA_PrivateKey", loaded_ec_key);
 
-   Botan::PK_Verifier verifier(*loaded_ec_key, "EMSA1(SHA-256)");
+   Botan::PK_Verifier verifier(*loaded_ec_key, Test::rng(), "EMSA1(SHA-256)");
 
    result.confirm("generated signature valid", verifier.verify_message(msg, msg_signature));
 
@@ -260,8 +260,8 @@ 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_Verifier verifier(*ecdsa_nodp, "EMSA1(SHA-256)");
+      Botan::PK_Signer signer(*ecdsa_nodp, Test::rng(), "EMSA1(SHA-256)");
+      Botan::PK_Verifier verifier(*ecdsa_nodp, Test::rng(), "EMSA1(SHA-256)");
 
       std::vector<byte> signature_nodp = signer.sign_message(msg, Test::rng());
 
@@ -327,8 +327,8 @@ 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_Verifier verifier(ecdsa, "EMSA1(SHA-256)");
+         Botan::PK_Signer signer(ecdsa, Test::rng(), "EMSA1(SHA-256)");
+         Botan::PK_Verifier verifier(ecdsa, Test::rng(), "EMSA1(SHA-256)");
 
          auto msg = Botan::hex_decode("12345678901234567890abcdef12");
          std::vector<byte> sig = signer.sign_message(msg, Test::rng());
diff --git a/src/tests/unit_tls.cpp b/src/tests/unit_tls.cpp
index f869f426b..445077490 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);
diff --git a/src/tests/unit_x509.cpp b/src/tests/unit_x509.cpp
index 4313e1373..35718d90d 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));