Add BN_rand_range_ex and use internally.

There are many cases where we need |BN_rand_range| but with a minimum
value other than 0. |BN_rand_range_ex| provides that.

Change-Id: I564326c9206bf4e20a37414bdbce16a951c148ce
Reviewed-on: https://boringssl-review.googlesource.com/8921
Reviewed-by: David Benjamin <davidben@google.com>
Commit-Queue: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>

7 files changed, 52 insertions, 44 deletions

diff --git a/crypto/bn/cmp.c b/crypto/bn/cmp.c
index 121c894c..9cf33b48 100644
--- a/crypto/bn/cmp.c
+++ b/crypto/bn/cmp.c
@@ -185,6 +185,17 @@ int BN_abs_is_word(const BIGNUM *bn, BN_ULONG w) {
   }
 }
 
+int BN_cmp_word(const BIGNUM *a, BN_ULONG b) {
+  BIGNUM b_bn;
+  BN_init(&b_bn);
+
+  b_bn.d = &b;
+  b_bn.top = b > 0;
+  b_bn.dmax = 1;
+  b_bn.flags = BN_FLG_STATIC_DATA;
+  return BN_cmp(a, &b_bn);
+}
+
 int BN_is_zero(const BIGNUM *bn) {
   return bn->top == 0;
 }
diff --git a/crypto/bn/random.c b/crypto/bn/random.c
index 83334306..fb76f1dd 100644
--- a/crypto/bn/random.c
+++ b/crypto/bn/random.c
@@ -181,16 +181,17 @@ int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) {
   return BN_rand(rnd, bits, top, bottom);
 }
 
-int BN_rand_range(BIGNUM *r, const BIGNUM *range) {
+int BN_rand_range_ex(BIGNUM *r, BN_ULONG min_inclusive,
+                     const BIGNUM *max_exclusive) {
   unsigned n;
   unsigned count = 100;
 
-  if (range->neg || BN_is_zero(range)) {
+  if (BN_cmp_word(max_exclusive, min_inclusive) <= 0) {
     OPENSSL_PUT_ERROR(BN, BN_R_INVALID_RANGE);
     return 0;
   }
 
-  n = BN_num_bits(range); /* n > 0 */
+  n = BN_num_bits(max_exclusive); /* n > 0 */
 
   /* BN_is_bit_set(range, n - 1) always holds */
   if (n == 1) {
@@ -204,7 +205,8 @@ int BN_rand_range(BIGNUM *r, const BIGNUM *range) {
       return 0;
     }
 
-    if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) {
+    if (!BN_is_bit_set(max_exclusive, n - 2) &&
+        !BN_is_bit_set(max_exclusive, n - 3)) {
       /* range = 100..._2, so 3*range (= 11..._2) is exactly one bit longer
        * than range. This is a common scenario when generating a random value
        * modulo an RSA public modulus, e.g. for RSA base blinding. */
@@ -216,12 +218,12 @@ int BN_rand_range(BIGNUM *r, const BIGNUM *range) {
       /* If r < 3*range, use r := r MOD range (which is either r, r - range, or
        * r - 2*range). Otherwise, iterate again. Since 3*range = 11..._2, each
        * iteration succeeds with probability >= .75. */
-      if (BN_cmp(r, range) >= 0) {
-        if (!BN_sub(r, r, range)) {
+      if (BN_cmp(r, max_exclusive) >= 0) {
+        if (!BN_sub(r, r, max_exclusive)) {
           return 0;
         }
-        if (BN_cmp(r, range) >= 0) {
-          if (!BN_sub(r, r, range)) {
+        if (BN_cmp(r, max_exclusive) >= 0) {
+          if (!BN_sub(r, r, max_exclusive)) {
             return 0;
           }
         }
@@ -232,11 +234,16 @@ int BN_rand_range(BIGNUM *r, const BIGNUM *range) {
         return 0;
       }
     }
-  } while (BN_cmp(r, range) >= 0);
+  } while (BN_cmp_word(r, min_inclusive) < 0 ||
+           BN_cmp(r, max_exclusive) >= 0);
 
   return 1;
 }
 
+int BN_rand_range(BIGNUM *r, const BIGNUM *range) {
+  return BN_rand_range_ex(r, 0, range);
+}
+
 int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range) {
   return BN_rand_range(r, range);
 }
diff --git a/crypto/dh/dh.c b/crypto/dh/dh.c
index 94eb3643..eea14325 100644
--- a/crypto/dh/dh.c
+++ b/crypto/dh/dh.c
@@ -275,11 +275,9 @@ int DH_generate_key(DH *dh) {
 
   if (generate_new_key) {
     if (dh->q) {
-      do {
-        if (!BN_rand_range(priv_key, dh->q)) {
-          goto err;
-        }
-      } while (BN_is_zero(priv_key) || BN_is_one(priv_key));
+      if (!BN_rand_range_ex(priv_key, 2, dh->q)) {
+        goto err;
+      }
     } else {
       /* secret exponent length */
       DH_check_standard_parameters(dh);
diff --git a/crypto/dsa/dsa.c b/crypto/dsa/dsa.c
index 5e1f81ab..e1488afa 100644
--- a/crypto/dsa/dsa.c
+++ b/crypto/dsa/dsa.c
@@ -425,11 +425,9 @@ int DSA_generate_key(DSA *dsa) {
     }
   }
 
-  do {
-    if (!BN_rand_range(priv_key, dsa->q)) {
-      goto err;
-    }
-  } while (BN_is_zero(priv_key));
+  if (!BN_rand_range_ex(priv_key, 1, dsa->q)) {
+    goto err;
+  }
 
   pub_key = dsa->pub_key;
   if (pub_key == NULL) {
@@ -818,11 +816,9 @@ int DSA_sign_setup(const DSA *dsa, BN_CTX *ctx_in, BIGNUM **out_kinv,
   }
 
   /* Get random k */
-  do {
-    if (!BN_rand_range(&k, dsa->q)) {
-      goto err;
-    }
-  } while (BN_is_zero(&k));
+  if (!BN_rand_range_ex(&k, 1, dsa->q)) {
+    goto err;
+  }
 
   BN_set_flags(&k, BN_FLG_CONSTTIME);
 
diff --git a/crypto/ec/ec_key.c b/crypto/ec/ec_key.c
index dcacdfa4..3e4456c4 100644
--- a/crypto/ec/ec_key.c
+++ b/crypto/ec/ec_key.c
@@ -425,11 +425,9 @@ int EC_KEY_generate_key(EC_KEY *eckey) {
   }
 
   const BIGNUM *order = EC_GROUP_get0_order(eckey->group);
-  do {
-    if (!BN_rand_range(priv_key, order)) {
-      goto err;
-    }
-  } while (BN_is_zero(priv_key));
+  if (!BN_rand_range_ex(priv_key, 1, order)) {
+    goto err;
+  }
 
   if (eckey->pub_key == NULL) {
     pub_key = EC_POINT_new(eckey->group);
diff --git a/crypto/ecdsa/ecdsa.c b/crypto/ecdsa/ecdsa.c
index 69383259..a85c28a4 100644
--- a/crypto/ecdsa/ecdsa.c
+++ b/crypto/ecdsa/ecdsa.c
@@ -263,20 +263,18 @@ static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
     /* If possible, we'll include the private key and message digest in the k
      * generation. The |digest| argument is only empty if |ECDSA_sign_setup| is
      * being used. */
-    do {
-      int ok;
-
-      if (digest_len > 0) {
-        ok = BN_generate_dsa_nonce(k, order, EC_KEY_get0_private_key(eckey),
-                                   digest, digest_len, ctx);
-      } else {
-        ok = BN_rand_range(k, order);
-      }
-      if (!ok) {
-        OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED);
-        goto err;
-      }
-    } while (BN_is_zero(k));
+    if (digest_len > 0) {
+      do {
+        if (!BN_generate_dsa_nonce(k, order, EC_KEY_get0_private_key(eckey),
+                                   digest, digest_len, ctx)) {
+          OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED);
+          goto err;
+        }
+      } while (BN_is_zero(k));
+    } else if (!BN_rand_range_ex(k, 1, order)) {
+      OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED);
+      goto err;
+    }
 
     /* We do not want timing information to leak the length of k,
      * so we compute G*k using an equivalent scalar of fixed
diff --git a/crypto/rsa/blinding.c b/crypto/rsa/blinding.c
index d9d90c2b..71f2e6f8 100644
--- a/crypto/rsa/blinding.c
+++ b/crypto/rsa/blinding.c
@@ -222,7 +222,7 @@ static int bn_blinding_create_param(BN_BLINDING *b, const BIGNUM *e,
   int retry_counter = 32;
 
   do {
-    if (!BN_rand_range(b->A, &mont->N)) {
+    if (!BN_rand_range_ex(b->A, 1, &mont->N)) {
       OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
       return 0;
     }