Repository: randombit/botan (cpp)

Issue:
BigInt::random_integer hangs
```cpp
#include <botan/bigint.h>
#include <botan/system_rng.h>

int main(void)
{
    using namespace Botan;
    System_RNG rng;

    BigInt A("0x1fec2433a4401374b0220cf2f92f7ac3a5a84610ff4896118525dfc6a556dfbf9ce2698c20cfc780");
    BigInt B("0x1fec2433a4401374b0220cf2f92f8735d4b73fe909f5fa3658d30b423d4630b4dce2698c20cfc780");

    BigInt::random_integer(rng, A, B);

    return 0;
}
```

Pull request description:
Fix BigInt::random_integer logic that can cause slow execution
We maintain a distinct codepath for the case where min is 0 or 1, since otherwise certain tests which expect stability of this function will break.

If min is > 1, we generate a number in the range `min + [0,max-min)`, which avoids the slow case.

Fixes #3590

Patch:
diff --git a/src/lib/math/bigint/big_rand.cpp b/src/lib/math/bigint/big_rand.cpp
index 4d069f03f..143ed7ed5 100644
--- a/src/lib/math/bigint/big_rand.cpp
+++ b/src/lib/math/bigint/big_rand.cpp
@@ -45,10 +45,26 @@ BigInt BigInt::random_integer(RandomNumberGenerator& rng, const BigInt& min, con
       throw Invalid_Argument("BigInt::random_integer invalid range");
    }
 
-   BigInt r;
+   /*
+   If min is > 1 then we generate a random number `r` in [0,max-min)
+   and return min + r.
+
+   This same logic could also be reasonbly chosen for min == 1, but
+   that breaks certain tests which expect stability of this function
+   when generating within [1,n)
+   */
+   if(min > 1) {
+      const BigInt diff = max - min;
+      // This call is recursive, but will not recurse further
+      return min + BigInt::random_integer(rng, BigInt::zero(), diff);
+   }
+
+   BOTAN_DEBUG_ASSERT(min <= 1);
 
    const size_t bits = max.bits();
 
+   BigInt r;
+
    do {
       r.randomize(rng, bits, false);
    } while(r < min || r >= max);


Test patch:
diff --git a/src/tests/data/bn/random.vec b/src/tests/data/bn/random.vec
index 3471508b6..4d30dc9db 100644
--- a/src/tests/data/bn/random.vec
+++ b/src/tests/data/bn/random.vec
@@ -10,6 +10,11 @@ Max = 0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
 Output = 0x2802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802
 
 Seed = FF0000000000FEFFFFFFFABC
-Min = 0xFEFFFFFFF000
+Min = 1
 Max = 0xFEFFFFFFFFFF
 Output = 0xFEFFFFFFFABC
+
+Seed = 802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802802
+Min = 0x1fec2433a4401374b0220cf2f92f7ac3a5a84610ff4896118525dfc6a556dfbf9ce2698c20cfc780
+Max = 0x1fec2433a4401374b0220cf2f92f8735d4b73fe909f5fa3658d30b423d4630b4dce2698c20cfc780
+Output = 0x1fec2433a4401374b0220cf2f92f7aeba8286e137f709891ad285feea7d707c21d0a6c0c48d247a8