Make the bn_rand_interval() API a bit more ergonomic

Provide bn_rand_in_range() which is a slightly tweaked version of what was
previously called bn_rand_range().

The way bn_rand_range() is called in libcrypto, the lower bound is always
expressible as a word. In fact, most of the time it is 1, the DH code uses
a 2, the MR tests in BPSW use 3 and an exceptinally high number appears in
the Tonelli-Shanks implementation where we use 32. Converting these lower
bounds to BIGNUMs on the call site is annoying so let bn_rand_interval()
do that internally and route that through bn_rand_in_range(). This way we
can avoid using BN_sub_word().

Adjust the bn_isqrt() test to use bn_rand_in_range() since that's the
only caller that uses actual BIGNUMs as lower bounds.

ok jsing

4 files changed, 36 insertions, 27 deletions

diff --git a/src/lib/libcrypto/bn/bn_bpsw.c b/src/lib/libcrypto/bn/bn_bpsw.c
index 82a4e87146..14f2800ad3 100644
--- a/src/lib/libcrypto/bn/bn_bpsw.c
+++ b/src/lib/libcrypto/bn/bn_bpsw.c
@@ -1,4 +1,4 @@
-/*      $OpenBSD: bn_bpsw.c,v 1.10 2023/05/10 21:05:24 tb Exp $ */
+/*      $OpenBSD: bn_bpsw.c,v 1.11 2023/08/03 18:53:55 tb Exp $ */
 /*
  * Copyright (c) 2022 Martin Grenouilloux <martin.grenouilloux@lse.epita.fr>
  * Copyright (c) 2022 Theo Buehler <tb@openbsd.org>
@@ -385,7 +385,7 @@ bn_miller_rabin(int *is_pseudoprime, const BIGNUM *n, BN_CTX *ctx,
     size_t rounds)
 {
         BN_MONT_CTX *mctx = NULL;
-        BIGNUM *base, *k, *n_minus_one, *three;
+        BIGNUM *base, *k, *n_minus_one;
         size_t i;
         int s;
         int ret = 0;
@@ -398,8 +398,6 @@ bn_miller_rabin(int *is_pseudoprime, const BIGNUM *n, BN_CTX *ctx,
                 goto err;
         if ((n_minus_one = BN_CTX_get(ctx)) == NULL)
                 goto err;
-        if ((three = BN_CTX_get(ctx)) == NULL)
-                goto err;
 
         if (BN_is_word(n, 2) || BN_is_word(n, 3)) {
                 *is_pseudoprime = 1;
@@ -451,11 +449,8 @@ bn_miller_rabin(int *is_pseudoprime, const BIGNUM *n, BN_CTX *ctx,
          * risk of false positives in BPSW.
          */
 
-        if (!BN_set_word(three, 3))
-                goto err;
-
         for (i = 0; i < rounds; i++) {
-                if (!bn_rand_interval(base, three, n_minus_one))
+                if (!bn_rand_interval(base, 3, n_minus_one))
                         goto err;
 
                 if (!bn_fermat(is_pseudoprime, n, n_minus_one, k, s, base, ctx,
diff --git a/src/lib/libcrypto/bn/bn_local.h b/src/lib/libcrypto/bn/bn_local.h
index 9447ed4f4c..5b7e852d70 100644
--- a/src/lib/libcrypto/bn/bn_local.h
+++ b/src/lib/libcrypto/bn/bn_local.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_local.h,v 1.32 2023/08/02 08:44:38 tb Exp $ */
+/* $OpenBSD: bn_local.h,v 1.33 2023/08/03 18:53:55 tb Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -274,7 +274,8 @@ void bn_div_rem_words(BN_ULONG h, BN_ULONG l, BN_ULONG d, BN_ULONG *out_q,
     BN_ULONG *out_r);
 
 int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom);
-int bn_rand_interval(BIGNUM *rnd, const BIGNUM *lower_inc, const BIGNUM *upper_exc);
+int bn_rand_in_range(BIGNUM *rnd, const BIGNUM *lower_inc, const BIGNUM *upper_exc);
+int bn_rand_interval(BIGNUM *rnd, BN_ULONG lower_word, const BIGNUM *upper_exc);
 
 void    BN_init(BIGNUM *);
 
diff --git a/src/lib/libcrypto/bn/bn_mod_sqrt.c b/src/lib/libcrypto/bn/bn_mod_sqrt.c
index bdd5b2cdba..280002cc48 100644
--- a/src/lib/libcrypto/bn/bn_mod_sqrt.c
+++ b/src/lib/libcrypto/bn/bn_mod_sqrt.c
@@ -1,4 +1,4 @@
-/*      $OpenBSD: bn_mod_sqrt.c,v 1.2 2023/07/08 12:21:58 beck Exp $ */
+/*      $OpenBSD: bn_mod_sqrt.c,v 1.3 2023/08/03 18:53:55 tb Exp $ */
 
 /*
  * Copyright (c) 2022 Theo Buehler <tb@openbsd.org>
@@ -237,7 +237,7 @@ static int
 bn_mod_sqrt_find_sylow_generator(BIGNUM *out_generator, const BIGNUM *p,
     const BIGNUM *q, BN_CTX *ctx)
 {
-        BIGNUM *n, *p_abs, *thirty_two;
+        BIGNUM *n, *p_abs;
         int i, is_non_residue;
         int ret = 0;
 
@@ -245,8 +245,6 @@ bn_mod_sqrt_find_sylow_generator(BIGNUM *out_generator, const BIGNUM *p,
 
         if ((n = BN_CTX_get(ctx)) == NULL)
                 goto err;
-        if ((thirty_two = BN_CTX_get(ctx)) == NULL)
-                goto err;
         if ((p_abs = BN_CTX_get(ctx)) == NULL)
                 goto err;
 
@@ -259,14 +257,12 @@ bn_mod_sqrt_find_sylow_generator(BIGNUM *out_generator, const BIGNUM *p,
                         goto found;
         }
 
-        if (!BN_set_word(thirty_two, 32))
-                goto err;
         if (!bn_copy(p_abs, p))
                 goto err;
         BN_set_negative(p_abs, 0);
 
         for (i = 0; i < 128; i++) {
-                if (!bn_rand_interval(n, thirty_two, p_abs))
+                if (!bn_rand_interval(n, 32, p_abs))
                         goto err;
                 if (!bn_mod_sqrt_n_is_non_residue(&is_non_residue, n, p, ctx))
                         goto err;
diff --git a/src/lib/libcrypto/bn/bn_rand.c b/src/lib/libcrypto/bn/bn_rand.c
index f68913473f..a5b163c820 100644
--- a/src/lib/libcrypto/bn/bn_rand.c
+++ b/src/lib/libcrypto/bn/bn_rand.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_rand.c,v 1.28 2023/07/08 12:21:58 beck Exp $ */
+/* $OpenBSD: bn_rand.c,v 1.29 2023/08/03 18:53:55 tb Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -284,29 +284,46 @@ BN_rand_range(BIGNUM *r, const BIGNUM *range)
 LCRYPTO_ALIAS(BN_rand_range);
 
 int
-bn_rand_interval(BIGNUM *rnd, const BIGNUM *lower_inc, const BIGNUM *upper_exc)
+bn_rand_in_range(BIGNUM *rnd, const BIGNUM *lower_inc, const BIGNUM *upper_exc)
 {
-        BIGNUM *len = NULL;
+        BIGNUM *len;
         int ret = 0;
 
-        if (BN_cmp(lower_inc, upper_exc) >= 0)
-                goto err;
-
         if ((len = BN_new()) == NULL)
                 goto err;
-
         if (!BN_sub(len, upper_exc, lower_inc))
                 goto err;
-
-        if (!bn_rand_range(0, rnd, len))
+        if (!BN_rand_range(rnd, len))
                 goto err;
-
         if (!BN_add(rnd, rnd, lower_inc))
                 goto err;
 
         ret = 1;
+
  err:
         BN_free(len);
+
+        return ret;
+}
+
+int
+bn_rand_interval(BIGNUM *rnd, BN_ULONG lower_word, const BIGNUM *upper_exc)
+{
+        BIGNUM *lower_inc = NULL;
+        int ret = 0;
+
+        if ((lower_inc = BN_new()) == NULL)
+                goto err;
+        if (!BN_set_word(lower_inc, lower_word))
+                goto err;
+        if (!bn_rand_in_range(rnd, lower_inc, upper_exc))
+                goto err;
+
+        ret = 1;
+
+ err:
+        BN_free(lower_inc);
+
         return ret;
 }