Use rejection sampling in BigInt::random_integer

Avoids the test vector contortions in RSA-KEM

3 files changed, 12 insertions, 15 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;
    }
 
 }
diff --git a/src/lib/rng/rng.h b/src/lib/rng/rng.h
index 2e29a713c..3fd3dcec8 100644
--- a/src/lib/rng/rng.h
+++ b/src/lib/rng/rng.h
@@ -132,6 +132,8 @@ class BOTAN_DLL RandomNumberGenerator
       virtual ~RandomNumberGenerator() {}
    };
 
+typedef RandomNumberGenerator RNG;
+
 /**
 * Null/stub RNG - fails if you try to use it for anything
 */
diff --git a/src/tests/data/pubkey/rsa_kem.vec b/src/tests/data/pubkey/rsa_kem.vec
index 6fb76fcfe..a55523533 100644
--- a/src/tests/data/pubkey/rsa_kem.vec
+++ b/src/tests/data/pubkey/rsa_kem.vec
@@ -2,14 +2,11 @@
 # RSA-KEM tests vectors from ISO-18033-2
 # http://www.shoup.net/iso/std4.pdf
 
-# R values here are -1 from the actual desired value to account for
-# some logic in random_integer wrt the bounds
-
 # Test C.6.2
 E = 65537
 P = 74100103850091296168511028051948833436338123529747970640732238422269665602829
 Q = 79461607023043824134896992211543210236933205105414344240218914846895267687977
-R = 032E45326FA859A72EC235ACFF929B15D1372E30B207255F0611B8F785D764374152E0AC009E509E7BA30CD2F1778E113B64E135CF4E2292C75EFE5288EDFDA3
+R = 032E45326FA859A72EC235ACFF929B15D1372E30B207255F0611B8F785D764374152E0AC009E509E7BA30CD2F1778E113B64E135CF4E2292C75EFE5288EDFDA4
 C0 = 4603E5324CAB9CEF8365C817052D954D44447B1667099EDC69942D32CD594E4FFCF268AE3836E2C35744AAA53AE201FE499806B67DEDAA26BF72ECBD117A6FC0
 KDF = KDF2(SHA-1)
 K = 0E6A26EB7B956CCB8B3BDC1CA975BC57C3989E8FBAD31A224655D800C46954840F
@@ -19,7 +16,7 @@ K = 0E6A26EB7B956CCB8B3BDC1CA975BC57C3989E8FBAD31A224655D800C46954840F
 E = 65537
 P = 74100103850091296168511028051948833436338123529747970640732238422269665602829
 Q = 79461607023043824134896992211543210236933205105414344240218914846895267687977
-R = 032E45326FA859A72EC235ACFF929B15D1372E30B207255F0611B8F785D764374152E0AC009E509E7BA30CD2F1778E113B64E135CF4E2292C75EFE5288EDFDA3
+R = 032E45326FA859A72EC235ACFF929B15D1372E30B207255F0611B8F785D764374152E0AC009E509E7BA30CD2F1778E113B64E135CF4E2292C75EFE5288EDFDA4
 C0 = 4603E5324CAB9CEF8365C817052D954D44447B1667099EDC69942D32CD594E4FFCF268AE3836E2C35744AAA53AE201FE499806B67DEDAA26BF72ECBD117A6FC0
 KDF = KDF2(SHA-256)
 K = 10a2403db42a8743cb989de86e668d168cbe6046