Replace BigInt::random_integer test with a Chi-square test

GH #1476

2 files changed, 62 insertions, 41 deletions

diff --git a/src/tests/data/bn/random.vec b/src/tests/data/bn/random.vec
new file mode 100644
index 000000000..a8961fea9
--- /dev/null
+++ b/src/tests/data/bn/random.vec
@@ -0,0 +1,10 @@
+
+Seed = 1010
+Min = 0
+Max = 1000
+Output = 16
+
+Seed = 802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802
+Min = 1
+Max = 0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+Output = 0x2802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index f63cce7fe..b095c8a6a 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -11,6 +11,7 @@
    #include <botan/numthry.h>
    #include <botan/pow_mod.h>
    #include <botan/parsing.h>
+   #include "test_rng.h"
 #endif
 
 namespace Botan_Tests {
@@ -138,55 +139,40 @@ class BigInt_Unit_Tests final : public Test
 
          result.start_timer();
 
-         // A value of 500 caused a non-negligible amount of test failures
-         const size_t ITERATIONS_PER_POSSIBLE_VALUE = 750;
+         const size_t SAMPLES = 50000;
 
-         std::vector<size_t> min_ranges{ 0 };
-         std::vector<size_t> max_ranges{ 10 };
+         const uint64_t range_min = 0;
+         const uint64_t range_max = 100;
 
-         if(Test::run_long_tests())
-            {
-            // This gets slow quickly:
-            min_ranges.push_back(7);
-            max_ranges.push_back(113);
-            }
-
-         for(size_t range_min : min_ranges)
-            {
-            for(size_t range_max : max_ranges)
-               {
-               if(range_min >= range_max)
-                  {
-                  continue;
-                  }
+         /*
+         * We have a range of 0...100 thus 100 degrees of freedom.
+         * This bound is 99.9% probability of non-uniform
+         */
+         const double CHI_CRIT = 148.230;
 
-               std::vector<size_t> counts(range_max - range_min);
+         std::map<uint32_t, size_t> counts;
 
-               for(size_t i = 0; i != counts.size() * ITERATIONS_PER_POSSIBLE_VALUE; ++i)
-                  {
-                  uint32_t r = BigInt::random_integer(Test::rng(), range_min, range_max).to_u32bit();
-                  result.test_gte("random_integer", r, range_min);
-                  result.test_lt("random_integer", r, range_max);
-                  counts[r - range_min] += 1;
-                  }
+         for(size_t i = 0; i != SAMPLES; ++i)
+            {
+            uint32_t r = BigInt::random_integer(Test::rng(), range_min, range_max).to_u32bit();
+            counts[r] += 1;
+            }
 
-               for(const auto count : counts)
-                  {
-                  double ratio = static_cast<double>(count) / ITERATIONS_PER_POSSIBLE_VALUE;
+         // Chi-square test
+         const double expected = static_cast<double>(SAMPLES) / (range_max - range_min);
+         double chi2 = 0;
 
-                  if(ratio >= 0.85 && ratio <= 1.15) // +/-15 %
-                     {
-                     result.test_success("distribution within expected range");
-                     }
-                  else
-                     {
-                     result.test_failure("distribution ratio outside expected range (+/-15 %): " +
-                                         std::to_string(ratio));
-                     }
-                  }
-               }
+         for(auto sample : counts)
+            {
+            const double count = sample.second;
+            chi2 += ((count - expected)*(count - expected)) / expected;
             }
 
+         if(chi2 >= CHI_CRIT)
+            result.test_failure("Failed Chi-square test, value " + std::to_string(chi2));
+         else
+            result.test_success("Passed Chi-square test, value " + std::to_string(chi2));
+
          result.end_timer();
 
          return result;
@@ -646,6 +632,31 @@ class BigInt_InvMod_Test final : public Text_Based_Test
 
 BOTAN_REGISTER_TEST("bn_invmod", BigInt_InvMod_Test);
 
+class BigInt_Rand_Test final : public Text_Based_Test
+   {
+   public:
+      BigInt_Rand_Test() : Text_Based_Test("bn/random.vec", "Seed,Min,Max,Output") {}
+
+      Test::Result run_one_test(const std::string&, const VarMap& vars) override
+         {
+         Test::Result result("BigInt Random");
+
+         const std::vector<uint8_t> seed = get_req_bin(vars, "Seed");
+         const Botan::BigInt min = get_req_bn(vars, "Min");
+         const Botan::BigInt max = get_req_bn(vars, "Max");
+         const Botan::BigInt expected = get_req_bn(vars, "Output");
+
+         Fixed_Output_RNG rng(seed);
+         Botan::BigInt generated = BigInt::random_integer(rng, min, max);
+
+         result.test_eq("random_integer KAT", generated, expected);
+
+         return result;
+         }
+   };
+
+BOTAN_REGISTER_TEST("bn_rand", BigInt_Rand_Test);
+
 class DSA_ParamGen_Test final : public Text_Based_Test
    {
    public: