Use rejection sampling in BigInt::random_integer

Avoids the test vector contortions in RSA-KEM

1 files changed, 8 insertions, 10 deletions

diff --git a/src/lib/math/bigint/big_rand.cpp b/src/lib/math/bigint/big_rand.cpp
index cfc1facee..73f3cf070 100644
--- a/src/lib/math/bigint/big_rand.cpp
+++ b/src/lib/math/bigint/big_rand.cpp
@@ -45,19 +45,17 @@ void BigInt::randomize(RandomNumberGenerator& rng,
 BigInt BigInt::random_integer(RandomNumberGenerator& rng,
                               const BigInt& min, const BigInt& max)
    {
-   BigInt delta_upper_bound = max - min - 1;
+   BigInt r;
 
-   if(delta_upper_bound < 0)
-      throw Invalid_Argument("random_integer: invalid min/max values");
+   const size_t bits = max.bits();
 
-   // Choose x in [0, delta_upper_bound]
-   BigInt x;
-   do {
-      auto bitsize = delta_upper_bound.bits();
-      x.randomize(rng, bitsize, false);
-   } while(x > delta_upper_bound);
+   do
+      {
+      r.randomize(rng, bits, false);
+      }
+   while(r < min || r >= max);
 
-   return min + x;
+   return r;
    }
 
 }