Add Miller-Rabin test for random bases to BPSW

The behavior of the BPSW primality test for numbers > 2^64 is not very
well understood. While there is no known composite that passes the test,
there are heuristics that indicate that there are likely infinitely many.
Therefore it seems appropriate to harden the test. Having a settable
number of MR rounds before doing a version of BPSW is also the approach
taken by Go's primality check in math/big.

This adds a new implementation of the old MR test that runs before running
the strong Lucas test. I like to imagine that it's slightly cleaner code.
We're effectively at about twice the cost of what we had a year ago. In
addition, it adds some non-determinism in case there actually are false
positives for the BPSW test.

The implementation is straightforward. It could easily be tweaked to use
the additional gcds in the "enhanced" MR test of FIPS 186-5, but as long
as we are only going to throw away the additional info, that's not worth
much.

This is a first step towards incorporating some of the considerations in
"A performant misuse-resistant API for Primality Testing" by Massimo and
Paterson. Further work will happen in tree. In particular, there are plans
to crank the number of Miller-Rabin tests considerably so as to have a
guaranteed baseline. The manual will be updated shortly.

positive feedback beck
ok jsing

1 files changed, 11 insertions, 5 deletions

diff --git a/src/lib/libcrypto/bn/bn_prime.c b/src/lib/libcrypto/bn/bn_prime.c
index c2fd0fc2e9..b8f0eb69ce 100644
--- a/src/lib/libcrypto/bn/bn_prime.c
+++ b/src/lib/libcrypto/bn/bn_prime.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_prime.c,v 1.31 2023/04/25 19:57:59 tb Exp $ */
+/* $OpenBSD: bn_prime.c,v 1.32 2023/05/10 12:21:55 tb Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -195,12 +195,12 @@ BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add,
                 goto err;
 
         if (!safe) {
-                if (!bn_is_prime_bpsw(&is_prime, ret, ctx))
+                if (!bn_is_prime_bpsw(&is_prime, ret, ctx, 1))
                         goto err;
                 if (!is_prime)
                         goto loop;
         } else {
-                if (!bn_is_prime_bpsw(&is_prime, ret, ctx))
+                if (!bn_is_prime_bpsw(&is_prime, ret, ctx, 1))
                         goto err;
                 if (!is_prime)
                         goto loop;
@@ -213,7 +213,7 @@ BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add,
                 if (!BN_rshift1(p, ret))
                         goto err;
 
-                if (!bn_is_prime_bpsw(&is_prime, p, ctx))
+                if (!bn_is_prime_bpsw(&is_prime, p, ctx, 1))
                         goto err;
                 if (!is_prime)
                         goto loop;
@@ -243,8 +243,14 @@ BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
 {
         int is_prime;
 
+        if (checks < 0)
+                return -1;
+
+        if (checks == BN_prime_checks)
+                checks = BN_prime_checks_for_size(BN_num_bits(a));
+
         /* XXX - tickle BN_GENCB in bn_is_prime_bpsw(). */
-        if (!bn_is_prime_bpsw(&is_prime, a, ctx_passed))
+        if (!bn_is_prime_bpsw(&is_prime, a, ctx_passed, checks))
                 return -1;
 
         return is_prime;