Merge pull request #221 from webmaster128/bitint

Fix BigInt random_integer() distribution issue

1 files changed, 22 insertions, 7 deletions

diff --git a/src/lib/math/bigint/big_rand.cpp b/src/lib/math/bigint/big_rand.cpp
index ab66c6cdd..cfc1facee 100644
--- a/src/lib/math/bigint/big_rand.cpp
+++ b/src/lib/math/bigint/big_rand.cpp
@@ -7,6 +7,7 @@
 
 #include <botan/bigint.h>
 #include <botan/parsing.h>
+#include <botan/internal/rounding.h>
 
 namespace Botan {
 
@@ -14,20 +15,27 @@ namespace Botan {
 * Randomize this number
 */
 void BigInt::randomize(RandomNumberGenerator& rng,
-                       size_t bitsize)
+                       size_t bitsize, bool set_high_bit)
    {
    set_sign(Positive);
 
    if(bitsize == 0)
+      {
       clear();
+      }
    else
       {
-      secure_vector<byte> array = rng.random_vec((bitsize + 7) / 8);
+      secure_vector<byte> array = rng.random_vec(round_up(bitsize, 8) / 8);
 
+      // Always cut unwanted bits
       if(bitsize % 8)
          array[0] &= 0xFF >> (8 - (bitsize % 8));
-      array[0] |= 0x80 >> ((bitsize % 8) ? (8 - bitsize % 8) : 0);
-      binary_decode(array.data(), array.size());
+
+      // Set the highest bit if wanted
+      if (set_high_bit)
+         array[0] |= 0x80 >> ((bitsize % 8) ? (8 - bitsize % 8) : 0);
+
+      binary_decode(array);
       }
    }
 
@@ -37,12 +45,19 @@ void BigInt::randomize(RandomNumberGenerator& rng,
 BigInt BigInt::random_integer(RandomNumberGenerator& rng,
                               const BigInt& min, const BigInt& max)
    {
-   BigInt range = max - min;
+   BigInt delta_upper_bound = max - min - 1;
 
-   if(range <= 0)
+   if(delta_upper_bound < 0)
       throw Invalid_Argument("random_integer: invalid min/max values");
 
-   return (min + (BigInt(rng, range.bits() + 2) % range));
+   // 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);
+
+   return min + x;
    }
 
 }