From: Bodo Möller <bodo@openssl.org>
Date: Fri, 14 Dec 2001 10:09:29 +0000 (+0000)
Subject: fix BN_rand_range
X-Git-Tag: OpenSSL-engine-0_9_6c^2^2~149
X-Git-Url: https://git.openssl.org/gitweb/?p=openssl.git;a=commitdiff_plain;h=66df02fd98959497ad12dc50b7629e0ca87b8fe6

fix BN_rand_range
---

diff --git a/CHANGES b/CHANGES
index 1c9c7fd35c..92cded83ef 100644
--- a/CHANGES
+++ b/CHANGES
@@ -12,6 +12,12 @@
          *) applies to 0.9.6a/0.9.6b/0.9.6c and 0.9.7
          +) applies to 0.9.7 only
 
+  *) Fix BN_rand_range bug pointed out by Dominikus Scherkl
+     <Dominikus.Scherkl@biodata.com>.  (The previous implementation
+     worked incorrectly for those cases where  range = 10..._2  and
+     3*range  is two bits longer than  range.)
+     [Bodo Moeller]
+
   *) Only add signing time to PKCS7 structures if it is not already present.
      [Steve Henson]
 
diff --git a/crypto/bn/bn_rand.c b/crypto/bn/bn_rand.c
index b9ce9e5d3f..9e08ccd22e 100644
--- a/crypto/bn/bn_rand.c
+++ b/crypto/bn/bn_rand.c
@@ -239,22 +239,15 @@ static int bn_rand_range(int pseudo, BIGNUM *r, BIGNUM *range)
 
 	n = BN_num_bits(range); /* n > 0 */
 
+	/* BN_is_bit_set(range, n - 1) always holds */
+
 	if (n == 1)
 		{
 		if (!BN_zero(r)) return 0;
 		}
-	else if (BN_is_bit_set(range, n - 2))
-		{
-		do
-			{
-			/* range = 11..._2, so each iteration succeeds with probability >= .75 */
-			if (!bn_rand(r, n, -1, 0)) return 0;
-			}
-		while (BN_cmp(r, range) >= 0);
-		}
-	else
+	else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3))
 		{
-		/* range = 10..._2,
+		/* range = 100..._2,
 		 * so  3*range (= 11..._2)  is exactly one bit longer than  range */
 		do
 			{
@@ -273,6 +266,15 @@ static int bn_rand_range(int pseudo, BIGNUM *r, BIGNUM *range)
 			}
 		while (BN_cmp(r, range) >= 0);
 		}
+	else
+		{
+		do
+			{
+			/* range = 11..._2  or  range = 101..._2 */
+			if (!bn_rand(r, n, -1, 0)) return 0;
+			}
+		while (BN_cmp(r, range) >= 0);
+		}
 
 	return 1;
 	}