Previously random_integer and friends used the global PRNG object to get

random bits. Now they take a reference to a RandomNumberGenerator object.
This was applied several times out, so now the constructors to private
key objects also take a RandomNumberGenerator& argument. This is also true
for a number of randomized algorithms (Miller-Rabin, for instance).

You can get a reference to the global PRNG with
  global_state().prng_reference()

This is a provisional thing: and warning: it is not thread safe! If this
is a problem instead keep per-thread PRNGs and pass them were needed.

30 files changed, 166 insertions, 108 deletions

diff --git a/checks/bigint.cpp b/checks/bigint.cpp
index 6a4d5ac94..5853e8a73 100644
--- a/checks/bigint.cpp
+++ b/checks/bigint.cpp
@@ -332,7 +332,8 @@ u32bit check_primetest(const std::vector<std::string>& args)
    BigInt n(args[0]);
    bool should_be_prime = (args[1] == "1");
 
-   bool is_prime = Botan::verify_prime(n);
+   bool is_prime = Botan::verify_prime(n,
+                                       global_state().prng_reference());
 
    if(is_prime != should_be_prime)
       {
diff --git a/checks/dolook2.cpp b/checks/dolook2.cpp
index b49d48a5e..1b7123b30 100644
--- a/checks/dolook2.cpp
+++ b/checks/dolook2.cpp
@@ -113,7 +113,7 @@ void RNG_Filter::write(const byte[], u32bit length)
 Filter* lookup_rng(const std::string& algname)
    {
    if(algname == "X9.31-RNG")
-      return new RNG_Filter(new ANSI_X931_RNG);
+      return new RNG_Filter(new ANSI_X931_RNG("AES-256", new Randpool));
    if(algname == "Randpool")
       return new RNG_Filter(new Randpool);
    return 0;
diff --git a/checks/pk.cpp b/checks/pk.cpp
index 5d9417fc6..72e135715 100644
--- a/checks/pk.cpp
+++ b/checks/pk.cpp
@@ -21,6 +21,7 @@
 #include <botan/numthry.h>
 
 #include <botan/x931_rng.h>
+#include <botan/randpool.h>
 #include <botan/libstate.h>
 using namespace Botan;
 
@@ -194,7 +195,7 @@ u32bit do_pk_validation_tests(const std::string& filename)
 
    std::cout << std::endl;
 
-   global_state().set_prng(new ANSI_X931_RNG);
+   global_state().set_prng(new ANSI_X931_RNG("AES-128", new Randpool));
    for(u32bit j = 0; j != 2; j++)
       global_state().seed_prng(true, 384);
 
@@ -249,7 +250,7 @@ void validate_encryption(PK_Encryptor* e, PK_Decryptor* d,
       failure = true;
       }
 
-   global_state().set_prng(new ANSI_X931_RNG);
+   global_state().set_prng(new ANSI_X931_RNG("AES-128", new Randpool));
    for(u32bit j = 0; j != 2; j++)
       global_state().seed_prng(true, 384);
 
@@ -290,7 +291,7 @@ void validate_signature(PK_Verifier* v, PK_Signer* s, const std::string& algo,
       failure = true;
       }
 
-   global_state().set_prng(new ANSI_X931_RNG);
+   global_state().set_prng(new ANSI_X931_RNG("AES-128", new Randpool));
    for(u32bit j = 0; j != 2; j++)
       global_state().seed_prng(true, 384);
 
@@ -661,34 +662,34 @@ void do_pk_keygen_tests()
    /* Putting each key in a block reduces memory pressure, speeds it up */
 #define IF_SIG_KEY(TYPE, BITS)     \
    {                               \
-   TYPE key(BITS);                 \
+   TYPE key(BITS, global_state().prng_reference());      \
    key.check_key(true);            \
    std::cout << '.' << std::flush; \
    }
 
 #define DL_SIG_KEY(TYPE, GROUP)    \
    {                               \
-   TYPE key(DL_Group(GROUP));  \
+   TYPE key(DL_Group(GROUP), global_state().prng_reference());   \
    key.check_key(true);            \
    std::cout << '.' << std::flush; \
    }
 
 #define DL_ENC_KEY(TYPE, GROUP)    \
    {                               \
-   TYPE key(DL_Group(GROUP));  \
+   TYPE key(DL_Group(GROUP), global_state().prng_reference());   \
    key.check_key(true);            \
    std::cout << '.' << std::flush; \
    }
 
 #define DL_KEY(TYPE, GROUP)        \
    {                               \
-   TYPE key(DL_Group(GROUP));  \
+   TYPE key(DL_Group(GROUP), global_state().prng_reference());   \
    key.check_key(true);            \
    std::cout << '.' << std::flush; \
    }
 
-   IF_SIG_KEY(RSA_PrivateKey, 512);
-   IF_SIG_KEY(RW_PrivateKey, 512);
+   IF_SIG_KEY(RSA_PrivateKey, 1024);
+   IF_SIG_KEY(RW_PrivateKey, 1024);
 
    DL_SIG_KEY(DSA_PrivateKey, "dsa/jce/512");
    DL_SIG_KEY(DSA_PrivateKey, "dsa/jce/768");
diff --git a/checks/pk_bench.cpp b/checks/pk_bench.cpp
index 51a454f4a..58d0a2f39 100644
--- a/checks/pk_bench.cpp
+++ b/checks/pk_bench.cpp
@@ -87,7 +87,8 @@ void bench_pk(const std::string& algo, bool html, double seconds)
          {
          const std::string len_str = to_string(keylen[j]);
 
-         DSA_PrivateKey key("dsa/jce/" + len_str);
+         DSA_PrivateKey key("dsa/jce/" + len_str,
+                            global_state().prng_reference());
 
          bench_ver(get_pk_signer(key, "EMSA1(SHA-1)"),
                    get_pk_verifier(key, "EMSA1(SHA-1)"),
@@ -106,7 +107,8 @@ void bench_pk(const std::string& algo, bool html, double seconds)
          {
          const std::string len_str = to_string(keylen[j]);
 
-         DH_PrivateKey key("modp/ietf/" + len_str);
+         DH_PrivateKey key("modp/ietf/" + len_str,
+                           global_state().prng_reference());
 
          bench_kas(get_pk_kas(key, "Raw"), "DH-" + len_str, seconds, html);
          }
@@ -120,7 +122,8 @@ void bench_pk(const std::string& algo, bool html, double seconds)
          {
          const std::string len_str = to_string(keylen[j]);
 
-         ElGamal_PrivateKey key("modp/ietf/" + len_str);
+         ElGamal_PrivateKey key("modp/ietf/" + len_str,
+                                global_state().prng_reference());
 
          bench_enc(get_pk_encryptor(key, "Raw"),
                    "ELG-" + len_str, seconds, html);
@@ -139,7 +142,8 @@ void bench_pk(const std::string& algo, bool html, double seconds)
          {
          const std::string len_str = to_string(keylen[j]);
 
-         NR_PrivateKey key("dsa/jce/" + len_str);
+         NR_PrivateKey key("dsa/jce/" + len_str,
+                           global_state().prng_reference());
 
          bench_ver(get_pk_signer(key, "EMSA1(SHA-1)"),
                    get_pk_verifier(key, "EMSA1(SHA-1)"),
diff --git a/checks/x509.cpp b/checks/x509.cpp
index 6e6dad60c..459f3b62f 100644
--- a/checks/x509.cpp
+++ b/checks/x509.cpp
@@ -6,6 +6,8 @@
 #include <botan/pkcs10.h>
 #include <botan/rsa.h>
 #include <botan/dsa.h>
+
+#include <botan/libstate.h>
 using namespace Botan;
 
 #include <iostream>
@@ -71,7 +73,7 @@ void do_x509_tests()
 
    /* Create the CA's key and self-signed cert */
    std::cout << '.' << std::flush;
-   RSA_PrivateKey ca_key(1024);
+   RSA_PrivateKey ca_key(1024, global_state().prng_reference());
 
    std::cout << '.' << std::flush;
    X509_Certificate ca_cert = X509::create_self_signed_cert(ca_opts(), ca_key);
@@ -79,13 +81,15 @@ void do_x509_tests()
 
    /* Create user #1's key and cert request */
    std::cout << '.' << std::flush;
-   DSA_PrivateKey user1_key(DL_Group("dsa/jce/1024"));
+   DSA_PrivateKey user1_key(DL_Group("dsa/jce/1024"),
+                            global_state().prng_reference());
+
    std::cout << '.' << std::flush;
    PKCS10_Request user1_req = X509::create_cert_req(req_opts1(), user1_key);
 
    /* Create user #2's key and cert request */
    std::cout << '.' << std::flush;
-   RSA_PrivateKey user2_key(768);
+   RSA_PrivateKey user2_key(1024, global_state().prng_reference());
    std::cout << '.' << std::flush;
    PKCS10_Request user2_req = X509::create_cert_req(req_opts2(), user2_key);
 
diff --git a/include/bigint.h b/include/bigint.h
index 36abbb388..5c4a9c997 100644
--- a/include/bigint.h
+++ b/include/bigint.h
@@ -20,7 +20,7 @@ class BOTAN_DLL BigInt
    public:
       enum Base { Octal = 8, Decimal = 10, Hexadecimal = 16, Binary = 256 };
       enum Sign { Negative = 0, Positive = 1 };
-      enum NumberType { Random, Power2 };
+      enum NumberType { Power2 };
 
       struct DivideByZero : public Exception
          { DivideByZero() : Exception("BigInt divide by zero") {} };
@@ -82,7 +82,7 @@ class BOTAN_DLL BigInt
       word operator[](u32bit) const;
       void clear() { reg.clear(); }
 
-      void randomize(u32bit = 0);
+      void randomize(RandomNumberGenerator& rng, u32bit n);
 
       void binary_encode(byte[]) const;
       void binary_decode(const byte[], u32bit);
diff --git a/include/dh.h b/include/dh.h
index c2ee8bd7d..3c55ef8d4 100644
--- a/include/dh.h
+++ b/include/dh.h
@@ -45,7 +45,7 @@ class BOTAN_DLL DH_PrivateKey : public DH_PublicKey,
       MemoryVector<byte> public_value() const;
 
       DH_PrivateKey() {}
-      DH_PrivateKey(const DL_Group&);
+      DH_PrivateKey(const DL_Group&, RandomNumberGenerator&);
       DH_PrivateKey(const DL_Group&, const BigInt&, const BigInt& = 0);
    private:
       void PKCS8_load_hook(bool = false);
diff --git a/include/dl_group.h b/include/dl_group.h
index 9fb242070..010a949ff 100644
--- a/include/dl_group.h
+++ b/include/dl_group.h
@@ -1,6 +1,6 @@
 /*************************************************
 * Discrete Logarithm Group Header File           *
-* (C) 1999-2007 Jack Lloyd                       *
+* (C) 1999-2008 Jack Lloyd                       *
 *************************************************/
 
 #ifndef BOTAN_DL_PARAM_H__
@@ -24,7 +24,7 @@ class BOTAN_DLL DL_Group
       enum Format { ANSI_X9_42, ANSI_X9_57, PKCS_3 };
       enum PrimeType { Strong, Prime_Subgroup, DSA_Kosherizer };
 
-      bool verify_group(bool) const;
+      bool verify_group(RandomNumberGenerator& rng, bool) const;
 
       std::string PEM_encode(Format) const;
       SecureVector<byte> DER_encode(Format) const;
@@ -33,14 +33,18 @@ class BOTAN_DLL DL_Group
 
       DL_Group();
       DL_Group(const std::string&);
-      DL_Group(PrimeType, u32bit, u32bit = 0);
+      DL_Group(RandomNumberGenerator& rng, PrimeType, u32bit, u32bit = 0);
       DL_Group(const MemoryRegion<byte>&, u32bit = 1024, u32bit = 0);
       DL_Group(const BigInt&, const BigInt&);
       DL_Group(const BigInt&, const BigInt&, const BigInt&);
    private:
       static BigInt make_dsa_generator(const BigInt&, const BigInt&);
-      static SecureVector<byte> generate_dsa_primes(BigInt&, BigInt&,
-                                                    u32bit, u32bit);
+
+      static SecureVector<byte>
+         generate_dsa_primes(RandomNumberGenerator& rng,
+                             BigInt& p, BigInt& q,
+                             u32bit pbits, u32bit qbits);
+
       static bool generate_dsa_primes(BigInt&, BigInt&, u32bit, u32bit,
                                       const MemoryRegion<byte>&);
 
diff --git a/include/dsa.h b/include/dsa.h
index 1bb501d27..21941cd29 100644
--- a/include/dsa.h
+++ b/include/dsa.h
@@ -48,7 +48,7 @@ class BOTAN_DLL DSA_PrivateKey : public DSA_PublicKey,
       bool check_key(bool) const;
 
       DSA_PrivateKey() {}
-      DSA_PrivateKey(const DL_Group&);
+      DSA_PrivateKey(const DL_Group&, RandomNumberGenerator& rng);
       DSA_PrivateKey(const DL_Group&, const BigInt&, const BigInt& = 0);
    private:
       void PKCS8_load_hook(bool = false);
diff --git a/include/elgamal.h b/include/elgamal.h
index 3f39d22a7..9a8135d38 100644
--- a/include/elgamal.h
+++ b/include/elgamal.h
@@ -46,7 +46,7 @@ class BOTAN_DLL ElGamal_PrivateKey : public ElGamal_PublicKey,
       bool check_key(bool) const;
 
       ElGamal_PrivateKey() {}
-      ElGamal_PrivateKey(const DL_Group&);
+      ElGamal_PrivateKey(const DL_Group&, RandomNumberGenerator&);
       ElGamal_PrivateKey(const DL_Group&, const BigInt&, const BigInt& = 0);
    private:
       void PKCS8_load_hook(bool = false);
diff --git a/include/libstate.h b/include/libstate.h
index 77a6ce05b..e38acd90a 100644
--- a/include/libstate.h
+++ b/include/libstate.h
@@ -54,6 +54,8 @@ class BOTAN_DLL Library_State
       void add_entropy(EntropySource&, bool);
       u32bit seed_prng(bool, u32bit);
 
+      RandomNumberGenerator& prng_reference() { return (*rng); }
+
       class Config& config() const;
 
       class Mutex* get_mutex() const;
diff --git a/include/nr.h b/include/nr.h
index ef46db0b0..0225af057 100644
--- a/include/nr.h
+++ b/include/nr.h
@@ -48,7 +48,7 @@ class BOTAN_DLL NR_PrivateKey : public NR_PublicKey,
       bool check_key(bool) const;
 
       NR_PrivateKey() {}
-      NR_PrivateKey(const DL_Group&);
+      NR_PrivateKey(const DL_Group&, RandomNumberGenerator& rng);
       NR_PrivateKey(const DL_Group&, const BigInt&, const BigInt& = 0);
    private:
       void PKCS8_load_hook(bool = false);
diff --git a/include/numthry.h b/include/numthry.h
index 44d56601a..6ca06be10 100644
--- a/include/numthry.h
+++ b/include/numthry.h
@@ -6,6 +6,7 @@
 #ifndef BOTAN_NUMBTHRY_H__
 #define BOTAN_NUMBTHRY_H__
 
+#include <botan/base.h>
 #include <botan/bigint.h>
 #include <botan/reducer.h>
 #include <botan/pow_mod.h>
@@ -42,23 +43,31 @@ u32bit BOTAN_DLL low_zero_bits(const BigInt&);
 /*************************************************
 * Primality Testing                              *
 *************************************************/
-bool BOTAN_DLL check_prime(const BigInt&);
-bool BOTAN_DLL is_prime(const BigInt&);
-bool BOTAN_DLL verify_prime(const BigInt&);
+bool BOTAN_DLL check_prime(const BigInt&, RandomNumberGenerator&);
+bool BOTAN_DLL is_prime(const BigInt&, RandomNumberGenerator&);
+bool BOTAN_DLL verify_prime(const BigInt&, RandomNumberGenerator&);
 
 s32bit BOTAN_DLL simple_primality_tests(const BigInt&);
-bool BOTAN_DLL passes_mr_tests(const BigInt&, u32bit = 1);
-bool BOTAN_DLL run_primality_tests(const BigInt&, u32bit = 1);
+
+bool BOTAN_DLL passes_mr_tests(RandomNumberGenerator&,
+                               const BigInt&, u32bit = 1);
+
+bool BOTAN_DLL run_primality_tests(RandomNumberGenerator&,
+                                   const BigInt&, u32bit = 1);
 
 /*************************************************
 * Random Number Generation                       *
 *************************************************/
-BigInt BOTAN_DLL random_integer(u32bit);
-BigInt BOTAN_DLL random_integer(const BigInt&, const BigInt&);
-BigInt BOTAN_DLL random_prime(u32bit, const BigInt& = 1,
+BigInt BOTAN_DLL random_integer(RandomNumberGenerator&, u32bit);
+BigInt BOTAN_DLL random_integer(RandomNumberGenerator&,
+                                const BigInt&, const BigInt&);
+
+BigInt BOTAN_DLL random_prime(RandomNumberGenerator&,
+                              u32bit n, const BigInt& = 1,
                               u32bit = 1, u32bit = 2);
 
-BigInt BOTAN_DLL random_safe_prime(u32bit);
+BigInt BOTAN_DLL random_safe_prime(RandomNumberGenerator&,
+                                   u32bit);
 
 /*************************************************
 * Prime Numbers                                  *
diff --git a/include/rsa.h b/include/rsa.h
index 415bc2af6..54ac50fad 100644
--- a/include/rsa.h
+++ b/include/rsa.h
@@ -46,7 +46,7 @@ class BOTAN_DLL RSA_PrivateKey : public RSA_PublicKey,
       RSA_PrivateKey() {}
       RSA_PrivateKey(const BigInt&, const BigInt&, const BigInt&,
                      const BigInt& = 0, const BigInt& = 0);
-      RSA_PrivateKey(u32bit, u32bit = 65537);
+      RSA_PrivateKey(u32bit, RandomNumberGenerator&, u32bit = 65537);
    private:
       BigInt private_op(const byte[], u32bit) const;
    };
diff --git a/include/rw.h b/include/rw.h
index 896e29545..6ccc2b10d 100644
--- a/include/rw.h
+++ b/include/rw.h
@@ -42,7 +42,7 @@ class BOTAN_DLL RW_PrivateKey : public RW_PublicKey,
       RW_PrivateKey() {}
       RW_PrivateKey(const BigInt&, const BigInt&, const BigInt&,
                     const BigInt& = 0, const BigInt& = 0);
-      RW_PrivateKey(u32bit, u32bit = 2);
+      RW_PrivateKey(u32bit, RandomNumberGenerator& rng, u32bit = 2);
    };
 
 }
diff --git a/src/big_rand.cpp b/src/big_rand.cpp
index 264f5dcb3..5e6ec594b 100644
--- a/src/big_rand.cpp
+++ b/src/big_rand.cpp
@@ -6,7 +6,6 @@
 #include <botan/bigint.h>
 #include <botan/parsing.h>
 #include <botan/numthry.h>
-#include <botan/libstate.h>
 
 namespace Botan {
 
@@ -16,9 +15,8 @@ namespace Botan {
 BigInt::BigInt(NumberType type, u32bit bits)
    {
    set_sign(Positive);
-   if(type == Random && bits)
-      randomize(bits);
-   else if(type == Power2)
+
+   if(type == Power2)
       set_bit(bits);
    else
       throw Invalid_Argument("BigInt(NumberType): Unknown type");
@@ -27,7 +25,8 @@ BigInt::BigInt(NumberType type, u32bit bits)
 /*************************************************
 * Randomize this number                          *
 *************************************************/
-void BigInt::randomize(u32bit bitsize)
+void BigInt::randomize(RandomNumberGenerator& rng,
+                       u32bit bitsize)
    {
    set_sign(Positive);
 
@@ -36,7 +35,7 @@ void BigInt::randomize(u32bit bitsize)
    else
       {
       SecureVector<byte> array((bitsize + 7) / 8);
-      global_state().randomize(array, array.size());
+      rng.randomize(array, array.size());
       if(bitsize % 8)
          array[0] &= 0xFF >> (8 - (bitsize % 8));
       array[0] |= 0x80 >> ((bitsize % 8) ? (8 - bitsize % 8) : 0);
@@ -47,30 +46,32 @@ void BigInt::randomize(u32bit bitsize)
 /*************************************************
 * Generate a random integer                      *
 *************************************************/
-BigInt random_integer(u32bit bits)
+BigInt random_integer(RandomNumberGenerator& rng,
+                      u32bit bits)
    {
    BigInt x;
-   x.randomize(bits);
+   x.randomize(rng, bits);
    return x;
    }
 
 /*************************************************
 * Generate a random integer within given range   *
 *************************************************/
-BigInt random_integer(const BigInt& min, const BigInt& max)
+BigInt random_integer(RandomNumberGenerator& rng,
+                      const BigInt& min, const BigInt& max)
    {
    BigInt range = max - min;
 
    if(range <= 0)
       throw Invalid_Argument("random_integer: invalid min/max values");
 
-   return (min + (random_integer(range.bits() + 2) % range));
+   return (min + (random_integer(rng, range.bits() + 2) % range));
    }
 
 /*************************************************
 * Generate a random safe prime                   *
 *************************************************/
-BigInt random_safe_prime(u32bit bits)
+BigInt random_safe_prime(RandomNumberGenerator& rng, u32bit bits)
    {
    if(bits <= 64)
       throw Invalid_Argument("random_safe_prime: Can't make a prime of " +
@@ -78,8 +79,8 @@ BigInt random_safe_prime(u32bit bits)
 
    BigInt p;
    do
-      p = (random_prime(bits - 1) << 1) + 1;
-   while(!is_prime(p));
+      p = (random_prime(rng, bits - 1) << 1) + 1;
+   while(!is_prime(p, rng));
    return p;
    }
 
diff --git a/src/dh.cpp b/src/dh.cpp
index e78bf802e..bf5ad5b11 100644
--- a/src/dh.cpp
+++ b/src/dh.cpp
@@ -46,12 +46,13 @@ MemoryVector<byte> DH_PublicKey::public_value() const
 /*************************************************
 * Create a DH private key                        *
 *************************************************/
-DH_PrivateKey::DH_PrivateKey(const DL_Group& grp)
+DH_PrivateKey::DH_PrivateKey(const DL_Group& grp,
+                             RandomNumberGenerator& rng)
    {
    group = grp;
 
    const BigInt& p = group_p();
-   x = random_integer(2 * dl_work_factor(p.bits()));
+   x = random_integer(rng, 2 * dl_work_factor(p.bits()));
 
    PKCS8_load_hook(true);
    }
diff --git a/src/dl_algo.cpp b/src/dl_algo.cpp
index 8654122e3..afefe2df3 100644
--- a/src/dl_algo.cpp
+++ b/src/dl_algo.cpp
@@ -7,6 +7,7 @@
 #include <botan/numthry.h>
 #include <botan/der_enc.h>
 #include <botan/ber_dec.h>
+#include <botan/libstate.h>
 
 namespace Botan {
 
@@ -131,7 +132,7 @@ bool DL_Scheme_PublicKey::check_key(bool strong) const
    {
    if(y < 2 || y >= group_p())
       return false;
-   if(!group.verify_group(strong))
+   if(!group.verify_group(global_state().prng_reference(), strong))
       return false;
    return true;
    }
@@ -146,7 +147,7 @@ bool DL_Scheme_PrivateKey::check_key(bool strong) const
 
    if(y < 2 || y >= p || x < 2 || x >= p)
       return false;
-   if(!group.verify_group(strong))
+   if(!group.verify_group(global_state().prng_reference(), strong))
       return false;
 
    if(!strong)
diff --git a/src/dl_group.cpp b/src/dl_group.cpp
index b356b707d..d0b27be0c 100644
--- a/src/dl_group.cpp
+++ b/src/dl_group.cpp
@@ -1,9 +1,10 @@
 /*************************************************
 * Discrete Logarithm Parameters Source File      *
-* (C) 1999-2007 Jack Lloyd                       *
+* (C) 1999-2008 Jack Lloyd                       *
 *************************************************/
 
 #include <botan/dl_group.h>
+#include <botan/libstate.h>
 #include <botan/config.h>
 #include <botan/parsing.h>
 #include <botan/numthry.h>
@@ -40,7 +41,8 @@ DL_Group::DL_Group(const std::string& type)
 /*************************************************
 * DL_Group Constructor                           *
 *************************************************/
-DL_Group::DL_Group(PrimeType type, u32bit pbits, u32bit qbits)
+DL_Group::DL_Group(RandomNumberGenerator& rng,
+                   PrimeType type, u32bit pbits, u32bit qbits)
    {
    if(pbits < 512)
       throw Invalid_Argument("DL_Group: prime size " + to_string(pbits) +
@@ -48,7 +50,7 @@ DL_Group::DL_Group(PrimeType type, u32bit pbits, u32bit qbits)
 
    if(type == Strong)
       {
-      p = random_safe_prime(pbits);
+      p = random_safe_prime(rng, pbits);
       q = (p - 1) / 2;
       g = 2;
       }
@@ -59,18 +61,18 @@ DL_Group::DL_Group(PrimeType type, u32bit pbits, u32bit qbits)
          if(!qbits)
             qbits = 2 * dl_work_factor(pbits);
 
-         q = random_prime(qbits);
+         q = random_prime(rng, qbits);
          BigInt X;
-         while(p.bits() != pbits || !is_prime(p))
+         while(p.bits() != pbits || !is_prime(p, rng))
             {
-            X = random_integer(pbits);
+            X = random_integer(rng, pbits);
             p = X - (X % (2*q) - 1);
             }
          }
       else
          {
          qbits = qbits ? qbits : ((pbits == 1024) ? 160 : 256);
-         generate_dsa_primes(p, q, pbits, qbits);
+         generate_dsa_primes(rng, p, q, pbits, qbits);
          }
 
       g = make_dsa_generator(p, q);
@@ -125,7 +127,7 @@ void DL_Group::initialize(const BigInt& p1, const BigInt& q1, const BigInt& g1)
    g = g1;
    q = q1;
 
-   if(q == 0 && check_prime((p - 1) / 2))
+   if(q == 0 && check_prime((p - 1) / 2, global_state().prng_reference()))
       q = (p - 1) / 2;
 
    initialized = true;
@@ -143,7 +145,8 @@ void DL_Group::init_check() const
 /*************************************************
 * Verify the parameters                          *
 *************************************************/
-bool DL_Group::verify_group(bool strong) const
+bool DL_Group::verify_group(RandomNumberGenerator& rng,
+                            bool strong) const
    {
    init_check();
 
@@ -155,9 +158,9 @@ bool DL_Group::verify_group(bool strong) const
    if(!strong)
       return true;
 
-   if(!check_prime(p))
+   if(!check_prime(p, rng))
       return false;
-   if((q > 0) && !check_prime(q))
+   if((q > 0) && !check_prime(q, rng))
       return false;
    return true;
    }
diff --git a/src/dsa.cpp b/src/dsa.cpp
index 6030bc88a..13ab67374 100644
--- a/src/dsa.cpp
+++ b/src/dsa.cpp
@@ -1,11 +1,12 @@
 /*************************************************
 * DSA Source File                                *
-* (C) 1999-2007 Jack Lloyd                       *
+* (C) 1999-2008 Jack Lloyd                       *
 *************************************************/
 
 #include <botan/dsa.h>
 #include <botan/numthry.h>
 #include <botan/keypair.h>
+#include <botan/libstate.h>
 
 namespace Botan {
 
@@ -56,10 +57,11 @@ u32bit DSA_PublicKey::message_part_size() const
 /*************************************************
 * Create a DSA private key                       *
 *************************************************/
-DSA_PrivateKey::DSA_PrivateKey(const DL_Group& grp)
+DSA_PrivateKey::DSA_PrivateKey(const DL_Group& grp,
+                               RandomNumberGenerator& rng)
    {
    group = grp;
-   x = random_integer(2, group_q() - 1);
+   x = random_integer(rng, 2, group_q() - 1);
 
    PKCS8_load_hook(true);
    }
@@ -101,7 +103,7 @@ SecureVector<byte> DSA_PrivateKey::sign(const byte in[], u32bit length) const
 
    BigInt k;
    do
-      k.randomize(q.bits());
+      k.randomize(global_state().prng_reference(), q.bits());
    while(k >= q);
 
    return core.sign(in, length, k);
diff --git a/src/dsa_gen.cpp b/src/dsa_gen.cpp
index 002af7d96..0e4f5301f 100644
--- a/src/dsa_gen.cpp
+++ b/src/dsa_gen.cpp
@@ -80,7 +80,7 @@ bool DL_Group::generate_dsa_primes(BigInt& p, BigInt& q,
    q.set_bit(qbits-1);
    q.set_bit(0);
 
-   if(!is_prime(q))
+   if(!is_prime(q, global_state().prng_reference()))
       return false;
 
    const u32bit n = (pbits-1) / (HASH_SIZE * 8),
@@ -104,7 +104,8 @@ bool DL_Group::generate_dsa_primes(BigInt& p, BigInt& q,
 
       p = X - (X % (2*q) - 1);
 
-      if(p.bits() == pbits && is_prime(p))
+      if(p.bits() == pbits &&
+         is_prime(p, global_state().prng_reference()))
          return true;
       }
    return false;
@@ -113,14 +114,15 @@ bool DL_Group::generate_dsa_primes(BigInt& p, BigInt& q,
 /*************************************************
 * Generate DSA Primes                            *
 *************************************************/
-SecureVector<byte> DL_Group::generate_dsa_primes(BigInt& p, BigInt& q,
+SecureVector<byte> DL_Group::generate_dsa_primes(RandomNumberGenerator& rng,
+                                                 BigInt& p, BigInt& q,
                                                  u32bit pbits, u32bit qbits)
    {
    SecureVector<byte> seed(qbits/8);
 
    while(true)
       {
-      global_state().randomize(seed, seed.size());
+      rng.randomize(seed, seed.size());
 
       if(generate_dsa_primes(p, q, pbits, qbits, seed))
          return seed;
diff --git a/src/elgamal.cpp b/src/elgamal.cpp
index 65fd22180..bcb8a6cc0 100644
--- a/src/elgamal.cpp
+++ b/src/elgamal.cpp
@@ -7,6 +7,7 @@
 #include <botan/numthry.h>
 #include <botan/keypair.h>
 #include <botan/util.h>
+#include <botan/libstate.h>
 
 namespace Botan {
 
@@ -35,7 +36,10 @@ void ElGamal_PublicKey::X509_load_hook()
 SecureVector<byte> ElGamal_PublicKey::encrypt(const byte in[],
                                               u32bit length) const
    {
-   BigInt k = random_integer(2 * dl_work_factor(group_p().bits()));
+   BigInt k = random_integer(
+      global_state().prng_reference(),
+      2 * dl_work_factor(group_p().bits()));
+
    return core.encrypt(in, length, k);
    }
 
@@ -50,11 +54,12 @@ u32bit ElGamal_PublicKey::max_input_bits() const
 /*************************************************
 * ElGamal_PrivateKey Constructor                 *
 *************************************************/
-ElGamal_PrivateKey::ElGamal_PrivateKey(const DL_Group& grp)
+ElGamal_PrivateKey::ElGamal_PrivateKey(const DL_Group& grp,
+                                       RandomNumberGenerator& rng)
    {
    group = grp;
 
-   x = random_integer(2 * dl_work_factor(group_p().bits()));
+   x = random_integer(rng, 2 * dl_work_factor(group_p().bits()));
 
    PKCS8_load_hook(true);
    }
diff --git a/src/if_algo.cpp b/src/if_algo.cpp
index 895e049d3..b8d8071f4 100644
--- a/src/if_algo.cpp
+++ b/src/if_algo.cpp
@@ -7,6 +7,7 @@
 #include <botan/numthry.h>
 #include <botan/der_enc.h>
 #include <botan/ber_dec.h>
+#include <botan/libstate.h>
 
 namespace Botan {
 
@@ -202,7 +203,8 @@ bool IF_Scheme_PrivateKey::check_key(bool strong) const
 
    if(d1 != d % (p - 1) || d2 != d % (q - 1) || c != inverse_mod(q, p))
       return false;
-   if(!check_prime(p) || !check_prime(q))
+   if(!check_prime(p, global_state().prng_reference()) ||
+      !check_prime(q, global_state().prng_reference()))
       return false;
    return true;
    }
diff --git a/src/make_prm.cpp b/src/make_prm.cpp
index d5f9961af..7d399b825 100644
--- a/src/make_prm.cpp
+++ b/src/make_prm.cpp
@@ -5,7 +5,6 @@
 
 #include <botan/numthry.h>
 #include <botan/parsing.h>
-#include <botan/libstate.h>
 #include <algorithm>
 
 namespace Botan {
@@ -13,7 +12,8 @@ namespace Botan {
 /*************************************************
 * Generate a random prime                        *
 *************************************************/
-BigInt random_prime(u32bit bits, const BigInt& coprime,
+BigInt random_prime(RandomNumberGenerator& rng,
+                    u32bit bits, const BigInt& coprime,
                     u32bit equiv, u32bit modulo)
    {
    if(bits < 48)
@@ -29,7 +29,7 @@ BigInt random_prime(u32bit bits, const BigInt& coprime,
 
    while(true)
       {
-      BigInt p = random_integer(bits);
+      BigInt p = random_integer(rng, bits);
       p.set_bit(bits - 2);
       p.set_bit(0);
 
@@ -61,7 +61,7 @@ BigInt random_prime(u32bit bits, const BigInt& coprime,
 
          if(!passes_sieve || gcd(p - 1, coprime) != 1)
             continue;
-         if(passes_mr_tests(p))
+         if(passes_mr_tests(rng, p))
             return p;
          }
       }
diff --git a/src/nr.cpp b/src/nr.cpp
index 80abbf508..0f911daac 100644
--- a/src/nr.cpp
+++ b/src/nr.cpp
@@ -6,6 +6,7 @@
 #include <botan/nr.h>
 #include <botan/numthry.h>
 #include <botan/keypair.h>
+#include <botan/libstate.h>
 
 namespace Botan {
 
@@ -55,10 +56,11 @@ u32bit NR_PublicKey::message_part_size() const
 /*************************************************
 * Create a NR private key                        *
 *************************************************/
-NR_PrivateKey::NR_PrivateKey(const DL_Group& grp)
+NR_PrivateKey::NR_PrivateKey(const DL_Group& grp,
+                             RandomNumberGenerator& rng)
    {
    group = grp;
-   x = random_integer(2, group_q() - 1);
+   x = random_integer(rng, 2, group_q() - 1);
 
    PKCS8_load_hook(true);
    }
@@ -100,7 +102,7 @@ SecureVector<byte> NR_PrivateKey::sign(const byte in[], u32bit length) const
 
    BigInt k;
    do
-      k.randomize(q.bits());
+      k.randomize(global_state().prng_reference(), q.bits());
    while(k >= q);
 
    return core.sign(in, length, k);
diff --git a/src/numthry.cpp b/src/numthry.cpp
index 01b46c982..f36e2f3fe 100644
--- a/src/numthry.cpp
+++ b/src/numthry.cpp
@@ -209,41 +209,43 @@ s32bit simple_primality_tests(const BigInt& n)
 /*************************************************
 * Fast check of primality                        *
 *************************************************/
-bool check_prime(const BigInt& n)
+bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
    {
-   return run_primality_tests(n, 0);
+   return run_primality_tests(rng, n, 0);
    }
 
 /*************************************************
 * Test for primality                             *
 *************************************************/
-bool is_prime(const BigInt& n)
+bool is_prime(const BigInt& n, RandomNumberGenerator& rng)
    {
-   return run_primality_tests(n, 1);
+   return run_primality_tests(rng, n, 1);
    }
 
 /*************************************************
 * Verify primality                               *
 *************************************************/
-bool verify_prime(const BigInt& n)
+bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
    {
-   return run_primality_tests(n, 2);
+   return run_primality_tests(rng, n, 2);
    }
 
 /*************************************************
 * Verify primality                               *
 *************************************************/
-bool run_primality_tests(const BigInt& n, u32bit level)
+bool run_primality_tests(RandomNumberGenerator& rng,
+                         const BigInt& n, u32bit level)
    {
    s32bit simple_tests = simple_primality_tests(n);
    if(simple_tests) return (simple_tests == 1) ? true : false;
-   return passes_mr_tests(n, level);
+   return passes_mr_tests(rng, n, level);
    }
 
 /*************************************************
 * Test for primaility using Miller-Rabin         *
 *************************************************/
-bool passes_mr_tests(const BigInt& n, u32bit level)
+bool passes_mr_tests(RandomNumberGenerator& rng,
+                     const BigInt& n, u32bit level)
    {
    const u32bit PREF_NONCE_BITS = 40;
 
@@ -267,7 +269,7 @@ bool passes_mr_tests(const BigInt& n, u32bit level)
    BigInt nonce;
    for(u32bit j = 0; j != tests; ++j)
       {
-      if(verify) nonce = random_integer(NONCE_BITS);
+      if(verify) nonce = random_integer(rng, NONCE_BITS);
       else       nonce = PRIMES[j];
 
       if(!mr.passes_test(nonce))
diff --git a/src/pk_core.cpp b/src/pk_core.cpp
index 42abe7196..4c76716f2 100644
--- a/src/pk_core.cpp
+++ b/src/pk_core.cpp
@@ -8,6 +8,7 @@
 #include <botan/engine.h>
 #include <botan/config.h>
 #include <botan/parsing.h>
+#include <botan/libstate.h>
 #include <algorithm>
 
 namespace Botan {
@@ -29,7 +30,8 @@ IF_Core::IF_Core(const BigInt& e, const BigInt& n, const BigInt& d,
 
    if(d != 0)
       {
-      BigInt k = random_integer(std::min(n.bits()-1, BLINDING_BITS));
+      BigInt k = random_integer(global_state().prng_reference(),
+                                std::min(n.bits()-1, BLINDING_BITS));
       if(k != 0)
          blinder = Blinder(power_mod(k, e, n), inverse_mod(k, n), n);
       }
@@ -180,7 +182,8 @@ ELG_Core::ELG_Core(const DL_Group& group, const BigInt& y, const BigInt& x)
       const BigInt& p = group.get_p();
       p_bytes = p.bytes();
 
-      BigInt k = random_integer(std::min(p.bits()-1, BLINDING_BITS));
+      BigInt k = random_integer(global_state().prng_reference(),
+                                std::min(p.bits()-1, BLINDING_BITS));
       if(k != 0)
          blinder = Blinder(k, power_mod(k, x, p), p);
       }
@@ -242,7 +245,8 @@ DH_Core::DH_Core(const DL_Group& group, const BigInt& x)
    op = Engine_Core::dh_op(group, x);
 
    const BigInt& p = group.get_p();
-   BigInt k = random_integer(std::min(p.bits()-1, BLINDING_BITS));
+   BigInt k = random_integer(global_state().prng_reference(),
+                             std::min(p.bits()-1, BLINDING_BITS));
    if(k != 0)
       blinder = Blinder(k, power_mod(inverse_mod(k, p), x, p), p);
    }
diff --git a/src/rsa.cpp b/src/rsa.cpp
index 6ddcd2415..e438c8b92 100644
--- a/src/rsa.cpp
+++ b/src/rsa.cpp
@@ -51,7 +51,9 @@ SecureVector<byte> RSA_PublicKey::verify(const byte in[], u32bit len) const
 /*************************************************
 * Create a RSA private key                       *
 *************************************************/
-RSA_PrivateKey::RSA_PrivateKey(u32bit bits, u32bit exp)
+RSA_PrivateKey::RSA_PrivateKey(u32bit bits,
+                               RandomNumberGenerator& rng,
+                               u32bit exp)
    {
    if(bits < 1024)
       throw Invalid_Argument(algo_name() + ": Can't make a key that is only " +
@@ -60,8 +62,8 @@ RSA_PrivateKey::RSA_PrivateKey(u32bit bits, u32bit exp)
       throw Invalid_Argument(algo_name() + ": Invalid encryption exponent");
 
    e = exp;
-   p = random_prime((bits + 1) / 2, e);
-   q = random_prime(bits - p.bits(), e);
+   p = random_prime(rng, (bits + 1) / 2, e);
+   q = random_prime(rng, bits - p.bits(), e);
    d = inverse_mod(e, lcm(p - 1, q - 1));
 
    PKCS8_load_hook(true);
diff --git a/src/rw.cpp b/src/rw.cpp
index 758a95a04..425ab83b3 100644
--- a/src/rw.cpp
+++ b/src/rw.cpp
@@ -52,17 +52,19 @@ SecureVector<byte> RW_PublicKey::verify(const byte in[], u32bit len) const
 /*************************************************
 * Create a Rabin-Williams private key            *
 *************************************************/
-RW_PrivateKey::RW_PrivateKey(u32bit bits, u32bit exp)
+RW_PrivateKey::RW_PrivateKey(u32bit bits,
+                             RandomNumberGenerator& rng,
+                             u32bit exp)
    {
-   if(bits < 512)
+   if(bits < 1024)
       throw Invalid_Argument(algo_name() + ": Can't make a key that is only " +
                              to_string(bits) + " bits long");
    if(exp < 2 || exp % 2 == 1)
       throw Invalid_Argument(algo_name() + ": Invalid encryption exponent");
 
    e = exp;
-   p = random_prime((bits + 1) / 2, e / 2, 3, 4);
-   q = random_prime(bits - p.bits(), e / 2, ((p % 8 == 3) ? 7 : 3), 8);
+   p = random_prime(rng, (bits + 1) / 2, e / 2, 3, 4);
+   q = random_prime(rng, bits - p.bits(), e / 2, ((p % 8 == 3) ? 7 : 3), 8);
    d = inverse_mod(e, lcm(p - 1, q - 1) >> 1);
 
    PKCS8_load_hook(true);
diff --git a/src/x509_ca.cpp b/src/x509_ca.cpp
index 13e1520a1..602649930 100644
--- a/src/x509_ca.cpp
+++ b/src/x509_ca.cpp
@@ -91,13 +91,17 @@ X509_Certificate X509_CA::make_cert(PK_Signer* signer,
    const u32bit X509_CERT_VERSION = 3;
    const u32bit SERIAL_BITS = 128;
 
+   BigInt serial_no = random_integer(global_state().prng_reference(),
+                                     SERIAL_BITS);
+
    DataSource_Memory source(X509_Object::make_signed(signer, sig_algo,
          DER_Encoder().start_cons(SEQUENCE)
             .start_explicit(0)
                .encode(X509_CERT_VERSION-1)
             .end_explicit()
 
-            .encode(random_integer(SERIAL_BITS))
+            .encode(serial_no)
+
             .encode(sig_algo)
             .encode(issuer_dn)