Modify Testsuite_RNG slightly to avoid rotations

[Since I want to make rotate.h internal in 3.0]

During modification of Testsuite_RNG some hard to debug test failures
occurred. It turned out to be because on occasion, with a sufficiently
bad test RNG, you can end up with p == q during RSA key generation.
Check for this.

Also add a smoke test checking that the test RNG is producing roughly
uniform output.

4 files changed, 67 insertions, 5 deletions

diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index bce6fae0f..96f405892 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -291,6 +291,10 @@ RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng,
       // TODO could generate primes in thread pool
       p = generate_rsa_prime(rng, rng, p_bits, e);
       q = generate_rsa_prime(rng, rng, q_bits, e);
+
+      if(p == q)
+         throw Internal_Error("RNG failure during RSA key generation");
+
       n = p * q;
       } while(n.bits() != bits);
 
@@ -323,6 +327,9 @@ bool RSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
    if(get_p() * get_q() != get_n())
       return false;
 
+   if(get_p() == get_q())
+      return false;
+
    if(get_d1() != ct_modulo(get_d(), get_p() - 1))
       return false;
    if(get_d2() != ct_modulo(get_d(), get_q() - 1))
diff --git a/src/tests/test_rsa.cpp b/src/tests/test_rsa.cpp
index 871d3e789..8bc2e4f5f 100644
--- a/src/tests/test_rsa.cpp
+++ b/src/tests/test_rsa.cpp
@@ -216,6 +216,36 @@ class RSA_Keygen_Tests final : public PK_Key_Generation_Test
          }
    };
 
+class RSA_Keygen_Bad_RNG_Test final : public Test
+   {
+   public:
+      std::vector<Test::Result> run() override
+         {
+         Test::Result result("RSA keygen with bad RNG");
+
+         /*
+         We don't need to count requests here; actually this test
+         is relying on the fact that the Request_Counting_RNG outputs
+         repeating 808080...
+         */
+         Request_Counting_RNG rng;
+
+         try
+            {
+            Botan::RSA_PrivateKey rsa(rng, 1024);
+            result.test_failure("Generated a key with a bad RNG");
+            }
+         catch(Botan::Internal_Error& e)
+            {
+            result.test_success("Key generation with bad RNG failed");
+            result.test_eq("Expected message",
+                           e.what(), "Internal error: RNG failure during RSA key generation");
+            }
+
+         return {result};
+         }
+   };
+
 class RSA_Blinding_Tests final : public Test
    {
    public:
@@ -326,6 +356,7 @@ BOTAN_REGISTER_TEST("pubkey", "rsa_verify", RSA_Signature_Verify_Tests);
 BOTAN_REGISTER_TEST("pubkey", "rsa_verify_invalid", RSA_Signature_Verify_Invalid_Tests);
 BOTAN_REGISTER_TEST("pubkey", "rsa_kem", RSA_KEM_Tests);
 BOTAN_REGISTER_TEST("pubkey", "rsa_keygen", RSA_Keygen_Tests);
+BOTAN_REGISTER_TEST("pubkey", "rsa_keygen_badrng", RSA_Keygen_Bad_RNG_Test);
 BOTAN_REGISTER_TEST("pubkey", "rsa_blinding", RSA_Blinding_Tests);
 
 #endif
diff --git a/src/tests/test_runner.cpp b/src/tests/test_runner.cpp
index 69ab364c0..034b24dda 100644
--- a/src/tests/test_runner.cpp
+++ b/src/tests/test_runner.cpp
@@ -8,7 +8,6 @@
 #include "tests.h"
 
 #include <botan/version.h>
-#include <botan/rotate.h>
 #include <botan/loadstor.h>
 #include <botan/cpuid.h>
 
@@ -76,15 +75,16 @@ class Testsuite_RNG final : public Botan::RandomNumberGenerator
 
          for(size_t i = 0; i != ROUNDS; ++i)
             {
-            m_a += static_cast<uint32_t>(i);
+            m_a += static_cast<uint32_t>(i ^ 0x5555);
 
-            m_a = Botan::rotl<9>(m_a);
+            m_a *= 0x9e3779b9;
             m_b ^= m_a;
             m_d ^= m_c;
 
             m_a += m_d;
             m_c += m_b;
-            m_c = Botan::rotl<23>(m_c);
+
+            m_c += (m_c >> 17);
             }
          }
 
diff --git a/src/tests/test_tests.cpp b/src/tests/test_tests.cpp
index a35ab08cc..c3cf83645 100644
--- a/src/tests/test_tests.cpp
+++ b/src/tests/test_tests.cpp
@@ -177,10 +177,34 @@ class Test_Tests final : public Test
             }
 #endif
 
-         return {result};
+         return {result, test_testsuite_rng()};
          }
 
    private:
+      Test::Result test_testsuite_rng()
+         {
+         Test::Result result("Testsuite_RNG");
+
+         size_t histogram[256] = { 0 };
+
+         const size_t RUNS = 1000;
+
+         for(size_t i = 0; i != 256 * RUNS; ++i)
+            {
+            histogram[rng().next_byte()] += 1;
+            }
+
+         for(size_t i = 0; i != 256; ++i)
+            {
+            if(histogram[i] < RUNS / 2 || histogram[i] > RUNS * 2)
+               result.test_failure("Testsuite_RNG produced non-uniform output");
+            else
+               result.test_success("Testsuite_RNG seemed roughly uniform");
+            }
+
+         return result;
+         }
+
       void verify_failure(const std::string& what,
                           Test::Result& result,
                           const Test::Result& test_result)