Add BN_check_prime()

Add a new API to test for primes that can't be misused, deprecated the
old APIs.

Suggested by Jake Massimo and Kenneth Paterson

Reviewed-by: Paul Dale <paul.dale@oracle.com>
GH: #9272

18 files changed, 176 insertions, 154 deletions

diff --git a/apps/prime.c b/apps/prime.c
index e00a3084a1..55cdad81a0 100644
--- a/apps/prime.c
+++ b/apps/prime.c
@@ -35,7 +35,7 @@ const OPTIONS prime_options[] = {
 int prime_main(int argc, char **argv)
 {
     BIGNUM *bn = NULL;
-    int hex = 0, checks = 20, generate = 0, bits = 0, safe = 0, ret = 1;
+    int hex = 0, generate = 0, bits = 0, safe = 0, ret = 1;
     char *prog;
     OPTION_CHOICE o;
 
@@ -64,7 +64,8 @@ opthelp:
             safe = 1;
             break;
         case OPT_CHECKS:
-            checks = atoi(opt_arg());
+            /* ignore parameter and argument */
+            opt_arg();
             break;
         }
     }
@@ -121,7 +122,7 @@ opthelp:
             BN_print(bio_out, bn);
             BIO_printf(bio_out, " (%s) %s prime\n",
                        argv[0],
-                       BN_is_prime_ex(bn, checks, NULL, NULL)
+                       BN_check_prime(bn, NULL, NULL)
                            ? "is" : "is not");
         }
     }
diff --git a/apps/s_client.c b/apps/s_client.c
index 016df7c657..392ab02234 100644
--- a/apps/s_client.c
+++ b/apps/s_client.c
@@ -272,8 +272,6 @@ typedef struct srp_arg_st {
     int strength;               /* minimal size for N */
 } SRP_ARG;
 
-# define SRP_NUMBER_ITERATIONS_FOR_PRIME 64
-
 static int srp_Verify_N_and_g(const BIGNUM *N, const BIGNUM *g)
 {
     BN_CTX *bn_ctx = BN_CTX_new();
@@ -281,10 +279,10 @@ static int srp_Verify_N_and_g(const BIGNUM *N, const BIGNUM *g)
     BIGNUM *r = BN_new();
     int ret =
         g != NULL && N != NULL && bn_ctx != NULL && BN_is_odd(N) &&
-        BN_is_prime_ex(N, SRP_NUMBER_ITERATIONS_FOR_PRIME, bn_ctx, NULL) == 1 &&
+        BN_check_prime(N, bn_ctx, NULL) == 1 &&
         p != NULL && BN_rshift1(p, N) &&
         /* p = (N-1)/2 */
-        BN_is_prime_ex(p, SRP_NUMBER_ITERATIONS_FOR_PRIME, bn_ctx, NULL) == 1 &&
+        BN_check_prime(p, bn_ctx, NULL) == 1 &&
         r != NULL &&
         /* verify g^((N-1)/2) == -1 (mod N) */
         BN_mod_exp(r, g, p, N, bn_ctx) &&
diff --git a/crypto/bn/bn_depr.c b/crypto/bn/bn_depr.c
index 18d02d894e..4dbbdc3814 100644
--- a/crypto/bn/bn_depr.c
+++ b/crypto/bn/bn_depr.c
@@ -52,7 +52,7 @@ int BN_is_prime(const BIGNUM *a, int checks,
 {
     BN_GENCB cb;
     BN_GENCB_set_old(&cb, callback, cb_arg);
-    return BN_is_prime_ex(a, checks, ctx_passed, &cb);
+    return bn_check_prime_int(a, checks, ctx_passed, 0, &cb);
 }
 
 int BN_is_prime_fasttest(const BIGNUM *a, int checks,
@@ -62,7 +62,7 @@ int BN_is_prime_fasttest(const BIGNUM *a, int checks,
 {
     BN_GENCB cb;
     BN_GENCB_set_old(&cb, callback, cb_arg);
-    return BN_is_prime_fasttest_ex(a, checks, ctx_passed,
-                                   do_trial_division, &cb);
+    return bn_check_prime_int(a, checks, ctx_passed, do_trial_division, &cb);
 }
+
 #endif
diff --git a/crypto/bn/bn_local.h b/crypto/bn/bn_local.h
index 4c86986804..ec90338510 100644
--- a/crypto/bn/bn_local.h
+++ b/crypto/bn/bn_local.h
@@ -665,4 +665,7 @@ static ossl_inline BIGNUM *bn_expand(BIGNUM *a, int bits)
     return bn_expand2((a),(bits+BN_BITS2-1)/BN_BITS2);
 }
 
+int bn_check_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx,
+                      int do_trial_division, BN_GENCB *cb);
+
 #endif
diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c
index 7d89d321d8..fd1c3c3088 100644
--- a/crypto/bn/bn_prime.c
+++ b/crypto/bn/bn_prime.c
@@ -24,6 +24,8 @@ static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods,
 static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods,
                              const BIGNUM *add, const BIGNUM *rem,
                              BN_CTX *ctx);
+static int bn_is_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx,
+                           int do_trial_division, BN_GENCB *cb);
 
 #define square(x) ((BN_ULONG)(x) * (BN_ULONG)(x))
 
@@ -82,6 +84,20 @@ static int calc_trial_divisions(int bits)
     return NUMPRIMES;
 }
 
+/*
+ * Use a minimum of 64 rounds of Miller-Rabin, which should give a false
+ * positive rate of 2^-128. If the size of the prime is larger than 2048
+ * the user probably wants a higher security level than 128, so switch
+ * to 128 rounds giving a false positive rate of 2^-256.
+ * Returns the number of rounds.
+ */
+static int bn_mr_min_checks(int bits)
+{
+    if (bits > 2048)
+        return 128;
+    return 64;
+}
+
 int BN_GENCB_call(BN_GENCB *cb, int a, int b)
 {
     /* No callback means continue */
@@ -112,7 +128,7 @@ int BN_generate_prime_ex2(BIGNUM *ret, int bits, int safe,
     int found = 0;
     int i, j, c1 = 0;
     prime_t *mods = NULL;
-    int checks = BN_prime_checks_for_size(bits);
+    int checks = bn_mr_min_checks(bits);
 
     if (bits < 2) {
         /* There are no prime numbers this small. */
@@ -151,7 +167,7 @@ int BN_generate_prime_ex2(BIGNUM *ret, int bits, int safe,
         goto err;
 
     if (!safe) {
-        i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb);
+        i = bn_is_prime_int(ret, checks, ctx, 0, cb);
         if (i == -1)
             goto err;
         if (i == 0)
@@ -165,13 +181,13 @@ int BN_generate_prime_ex2(BIGNUM *ret, int bits, int safe,
             goto err;
 
         for (i = 0; i < checks; i++) {
-            j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb);
+            j = bn_is_prime_int(ret, 1, ctx, 0, cb);
             if (j == -1)
                 goto err;
             if (j == 0)
                 goto loop;
 
-            j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb);
+            j = bn_is_prime_int(t, 1, ctx, 0, cb);
             if (j == -1)
                 goto err;
             if (j == 0)
@@ -208,16 +224,46 @@ int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
 }
 #endif
 
+#if !OPENSSL_API_3
 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
                    BN_GENCB *cb)
 {
-    return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
+    return bn_check_prime_int(a, checks, ctx_passed, 0, cb);
 }
 
-/* See FIPS 186-4 C.3.1 Miller Rabin Probabilistic Primality Test. */
 int BN_is_prime_fasttest_ex(const BIGNUM *w, int checks, BN_CTX *ctx,
                             int do_trial_division, BN_GENCB *cb)
 {
+    return bn_check_prime_int(w, checks, ctx, do_trial_division, cb);
+}
+#endif
+
+/* Wrapper around bn_is_prime_int that sets the minimum number of checks */
+int bn_check_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx,
+                       int do_trial_division, BN_GENCB *cb)
+{
+    int min_checks = bn_mr_min_checks(BN_num_bits(w));
+
+    if (checks < min_checks)
+        checks = min_checks;
+
+    return bn_is_prime_int(w, checks, ctx, do_trial_division, cb);
+}
+
+int BN_check_prime(const BIGNUM *p, BN_CTX *ctx, BN_GENCB *cb)
+{
+    return bn_check_prime_int(p, 0, ctx, 1, cb);
+}
+
+/*
+ * Tests that |w| is probably prime
+ * See FIPS 186-4 C.3.1 Miller Rabin Probabilistic Primality Test.
+ *
+ * Returns 0 when composite, 1 when probable prime, -1 on error.
+ */
+static int bn_is_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx,
+                           int do_trial_division, BN_GENCB *cb)
+{
     int i, status, ret = -1;
 #ifndef FIPS_MODE
     BN_CTX *ctxlocal = NULL;
@@ -332,8 +378,8 @@ int bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx,
     if (mont == NULL || !BN_MONT_CTX_set(mont, w, ctx))
         goto err;
 
-    if (iterations == BN_prime_checks)
-        iterations = BN_prime_checks_for_size(BN_num_bits(w));
+    if (iterations == 0)
+        iterations = bn_mr_min_checks(BN_num_bits(w));
 
     /* (Step 4) */
     for (i = 0; i < iterations; ++i) {
diff --git a/crypto/bn/bn_rsa_fips186_4.c b/crypto/bn/bn_rsa_fips186_4.c
index e5e4eccb22..c31b43ba8f 100644
--- a/crypto/bn/bn_rsa_fips186_4.c
+++ b/crypto/bn/bn_rsa_fips186_4.c
@@ -68,44 +68,6 @@ static int bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(int nbits)
 }
 
 /*
- * FIPS 186-4 Table C.3 for error probability of 2^-100
- * Minimum number of Miller Rabin Rounds for p1, p2, q1 & q2.
- *
- * Params:
- *     aux_prime_bits The auxiliary prime size in bits.
- * Returns:
- *     The minimum number of Miller Rabin Rounds for an auxiliary prime, or
- *     0 if aux_prime_bits is invalid.
- */
-static int bn_rsa_fips186_4_aux_prime_MR_min_checks(int aux_prime_bits)
-{
-    if (aux_prime_bits > 170)
-        return 27;
-    if (aux_prime_bits > 140)
-        return 32;
-    return 0; /* Error case */
-}
-
-/*
- * FIPS 186-4 Table C.3 for error probability of 2^-100
- * Minimum number of Miller Rabin Rounds for p, q.
- *
- * Params:
- *     nbits The key size in bits.
- * Returns:
- *     The minimum number of Miller Rabin Rounds required,
- *     or 0 if nbits is invalid.
- */
-int bn_rsa_fips186_4_prime_MR_min_checks(int nbits)
-{
-    if (nbits >= 3072) /* > 170 */
-        return 3;
-    if (nbits == 2048) /* > 140 */
-        return 4;
-    return 0; /* Error case */
-}
-
-/*
  * Find the first odd integer that is a probable prime.
  *
  * See section FIPS 186-4 B.3.6 (Steps 4.2/5.2).
@@ -123,9 +85,8 @@ static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1,
 {
     int ret = 0;
     int i = 0;
-    int checks = bn_rsa_fips186_4_aux_prime_MR_min_checks(BN_num_bits(Xp1));
 
-    if (checks == 0 || BN_copy(p1, Xp1) == NULL)
+    if (BN_copy(p1, Xp1) == NULL)
         return 0;
 
     /* Find the first odd number >= Xp1 that is probably prime */
@@ -133,7 +94,7 @@ static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1,
         i++;
         BN_GENCB_call(cb, 0, i);
         /* MR test with trial division */
-        if (BN_is_prime_fasttest_ex(p1, checks, ctx, 1, cb))
+        if (BN_check_prime(p1, ctx, cb))
             break;
         /* Get next odd number */
         if (!BN_add_word(p1, 2))
@@ -259,11 +220,8 @@ int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
     int ret = 0;
     int i, imax;
     int bits = nlen >> 1;
-    int checks = bn_rsa_fips186_4_prime_MR_min_checks(nlen);
     BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2;
 
-    if (checks == 0)
-        return 0;
     BN_CTX_start(ctx);
 
     R = BN_CTX_get(ctx);
@@ -331,8 +289,7 @@ int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
                     || !BN_sub_word(y1, 1)
                     || !BN_gcd(tmp, y1, e, ctx))
                 goto err;
-            if (BN_is_one(tmp)
-                    && BN_is_prime_fasttest_ex(Y, checks, ctx, 1, cb))
+            if (BN_is_one(tmp) && BN_check_prime(Y, ctx, cb))
                 goto end;
             /* (Step 8-10) */
             if (++i >= imax || !BN_add(Y, Y, r1r2x2))
diff --git a/crypto/bn/bn_x931p.c b/crypto/bn/bn_x931p.c
index 211886f5ee..1e4d4991b2 100644
--- a/crypto/bn/bn_x931p.c
+++ b/crypto/bn/bn_x931p.c
@@ -30,7 +30,7 @@ static int bn_x931_derive_pi(BIGNUM *pi, const BIGNUM *Xpi, BN_CTX *ctx,
         i++;
         BN_GENCB_call(cb, 0, i);
         /* NB 27 MR is specified in X9.31 */
-        is_prime = BN_is_prime_fasttest_ex(pi, 27, ctx, 1, cb);
+        is_prime = BN_check_prime(pi, ctx, cb);
         if (is_prime < 0)
             return 0;
         if (is_prime)
@@ -131,7 +131,7 @@ int BN_X931_derive_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2,
              * offering similar or better guarantees 50 MR is considerably
              * better.
              */
-            int r = BN_is_prime_fasttest_ex(p, 50, ctx, 1, cb);
+            int r = BN_check_prime(p, ctx, cb);
             if (r < 0)
                 goto err;
             if (r)
diff --git a/crypto/dh/dh_check.c b/crypto/dh/dh_check.c
index 45c699b33b..70f083603f 100644
--- a/crypto/dh/dh_check.c
+++ b/crypto/dh/dh_check.c
@@ -12,8 +12,6 @@
 #include <openssl/bn.h>
 #include "dh_local.h"
 
-# define DH_NUMBER_ITERATIONS_FOR_PRIME 64
-
 /*-
  * Check that p and g are suitable enough
  *
@@ -137,7 +135,7 @@ int DH_check(const DH *dh, int *ret)
             if (!BN_is_one(t1))
                 *ret |= DH_NOT_SUITABLE_GENERATOR;
         }
-        r = BN_is_prime_ex(dh->q, DH_NUMBER_ITERATIONS_FOR_PRIME, ctx, NULL);
+        r = BN_check_prime(dh->q, ctx, NULL);
         if (r < 0)
             goto err;
         if (!r)
@@ -151,7 +149,7 @@ int DH_check(const DH *dh, int *ret)
             *ret |= DH_CHECK_INVALID_J_VALUE;
     }
 
-    r = BN_is_prime_ex(dh->p, DH_NUMBER_ITERATIONS_FOR_PRIME, ctx, NULL);
+    r = BN_check_prime(dh->p, ctx, NULL);
     if (r < 0)
         goto err;
     if (!r)
@@ -159,7 +157,7 @@ int DH_check(const DH *dh, int *ret)
     else if (!dh->q) {
         if (!BN_rshift1(t1, dh->p))
             goto err;
-        r = BN_is_prime_ex(t1, DH_NUMBER_ITERATIONS_FOR_PRIME, ctx, NULL);
+        r = BN_check_prime(t1, ctx, NULL);
         if (r < 0)
             goto err;
         if (!r)
diff --git a/crypto/dsa/dsa_gen.c b/crypto/dsa/dsa_gen.c
index 00feba381a..67551e545b 100644
--- a/crypto/dsa/dsa_gen.c
+++ b/crypto/dsa/dsa_gen.c
@@ -154,8 +154,7 @@ int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits,
                 goto err;
 
             /* step 4 */
-            r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
-                                        use_random_seed, cb);
+            r = BN_check_prime(q, ctx, cb);
             if (r > 0)
                 break;
             if (r != 0)
@@ -226,7 +225,7 @@ int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits,
             /* step 10 */
             if (BN_cmp(p, test) >= 0) {
                 /* step 11 */
-                r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
+                r = BN_check_prime(p, ctx, cb);
                 if (r > 0)
                     goto end;   /* found it */
                 if (r != 0)
@@ -425,8 +424,7 @@ int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
                 goto err;
 
             /* step 4 */
-            r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
-                                        seed_in ? 1 : 0, cb);
+            r = BN_check_prime(q, ctx, cb);
             if (r > 0)
                 break;
             if (r != 0)
@@ -506,7 +504,7 @@ int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
             /* step 10 */
             if (BN_cmp(p, test) >= 0) {
                 /* step 11 */
-                r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
+                r = BN_check_prime(p, ctx, cb);
                 if (r > 0)
                     goto end;   /* found it */
                 if (r != 0)
diff --git a/crypto/rsa/rsa_chk.c b/crypto/rsa/rsa_chk.c
index 6e2557f095..9d8049132b 100644
--- a/crypto/rsa/rsa_chk.c
+++ b/crypto/rsa/rsa_chk.c
@@ -73,13 +73,13 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb)
     }
 
     /* p prime? */
-    if (BN_is_prime_ex(key->p, BN_prime_checks, NULL, cb) != 1) {
+    if (BN_check_prime(key->p, NULL, cb) != 1) {
         ret = 0;
         RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_P_NOT_PRIME);
     }
 
     /* q prime? */
-    if (BN_is_prime_ex(key->q, BN_prime_checks, NULL, cb) != 1) {
+    if (BN_check_prime(key->q, NULL, cb) != 1) {
         ret = 0;
         RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_Q_NOT_PRIME);
     }
@@ -87,7 +87,7 @@ int RSA_check_key_ex(const RSA *key, BN_GENCB *cb)
     /* r_i prime? */
     for (idx = 0; idx < ex_primes; idx++) {
         pinfo = sk_RSA_PRIME_INFO_value(key->prime_infos, idx);
-        if (BN_is_prime_ex(pinfo->r, BN_prime_checks, NULL, cb) != 1) {
+        if (BN_check_prime(pinfo->r, NULL, cb) != 1) {
             ret = 0;
             RSAerr(RSA_F_RSA_CHECK_KEY_EX, RSA_R_MP_R_NOT_PRIME);
         }
diff --git a/crypto/rsa/rsa_sp800_56b_check.c b/crypto/rsa/rsa_sp800_56b_check.c
index cf15212b87..d614504bc9 100644
--- a/crypto/rsa/rsa_sp800_56b_check.c
+++ b/crypto/rsa/rsa_sp800_56b_check.c
@@ -119,16 +119,15 @@ err:
  * Check the prime factor (for either p or q)
  * i.e: p is prime AND GCD(p - 1, e) = 1
  *
- * See SP800-5bBr1 6.4.1.2.3 Step 5 (a to d) & (e to h).
+ * See SP800-56Br1 6.4.1.2.3 Step 5 (a to d) & (e to h).
  */
 int rsa_check_prime_factor(BIGNUM *p, BIGNUM *e, int nbits, BN_CTX *ctx)
 {
-    int checks = bn_rsa_fips186_4_prime_MR_min_checks(nbits);
     int ret = 0;
     BIGNUM *p1 = NULL, *gcd = NULL;
 
     /* (Steps 5 a-b) prime test */
-    if (BN_is_prime_fasttest_ex(p, checks, ctx, 1, NULL) != 1
+    if (BN_check_prime(p, ctx, NULL) != 1
             /* (Step 5c) (√2)(2^(nbits/2 - 1) <= p <= 2^(nbits/2 - 1) */
             || rsa_check_prime_factor_range(p, nbits, ctx) != 1)
         return 0;
@@ -235,7 +234,7 @@ int rsa_get_lcm(BN_CTX *ctx, const BIGNUM *p, const BIGNUM *q,
  */
 int rsa_sp800_56b_check_public(const RSA *rsa)
 {
-    int ret = 0, nbits, iterations, status;
+    int ret = 0, nbits, status;
     BN_CTX *ctx = NULL;
     BIGNUM *gcd = NULL;
 
@@ -268,7 +267,6 @@ int rsa_sp800_56b_check_public(const RSA *rsa)
     if (ctx == NULL || gcd == NULL)
         goto err;
 
-    iterations = bn_rsa_fips186_4_prime_MR_min_checks(nbits);
     /* (Steps d-f):
      * The modulus is composite, but not a power of a prime.
      * The modulus has no factors smaller than 752.
@@ -278,7 +276,7 @@ int rsa_sp800_56b_check_public(const RSA *rsa)
         goto err;
     }
 
-    ret = bn_miller_rabin_is_prime(rsa->n, iterations, ctx, NULL, 1, &status);
+    ret = bn_miller_rabin_is_prime(rsa->n, 0, ctx, NULL, 1, &status);
     if (ret != 1 || status != BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME) {
         RSAerr(RSA_F_RSA_SP800_56B_CHECK_PUBLIC, RSA_R_INVALID_MODULUS);
         ret = 0;
diff --git a/doc/man1/openssl-prime.pod b/doc/man1/openssl-prime.pod
index c11bcc9c84..aa9af22102 100644
--- a/doc/man1/openssl-prime.pod
+++ b/doc/man1/openssl-prime.pod
@@ -50,8 +50,7 @@ generated is I<n>, then check that C<(I<n>-1)/2> is also prime.
 
 =item B<-checks> I<num>
 
-Perform the checks I<num> times to see that the generated number
-is prime.  The default is 20.
+This parameter is ignored.
 
 =back
 
diff --git a/doc/man3/BN_generate_prime.pod b/doc/man3/BN_generate_prime.pod
index 6a3376b1fd..cdd7ed0e8e 100644
--- a/doc/man3/BN_generate_prime.pod
+++ b/doc/man3/BN_generate_prime.pod
@@ -2,7 +2,7 @@
 
 =head1 NAME
 
-BN_generate_prime_ex2, BN_generate_prime_ex, BN_is_prime_ex,
+BN_generate_prime_ex2, BN_generate_prime_ex, BN_is_prime_ex, BN_check_prime,
 BN_is_prime_fasttest_ex, BN_GENCB_call, BN_GENCB_new, BN_GENCB_free,
 BN_GENCB_set_old, BN_GENCB_set, BN_GENCB_get_arg, BN_generate_prime,
 BN_is_prime, BN_is_prime_fasttest - generate primes and test for primality
@@ -18,10 +18,7 @@ BN_is_prime, BN_is_prime_fasttest - generate primes and test for primality
  int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add,
                           const BIGNUM *rem, BN_GENCB *cb);
 
- int BN_is_prime_ex(const BIGNUM *p, int nchecks, BN_CTX *ctx, BN_GENCB *cb);
-
- int BN_is_prime_fasttest_ex(const BIGNUM *p, int nchecks, BN_CTX *ctx,
-                             int do_trial_division, BN_GENCB *cb);
+ int BN_check_prime(const BIGNUM *p, BN_CTX *ctx, BN_GENCB *cb);
 
  int BN_GENCB_call(BN_GENCB *cb, int a, int b);
 
@@ -45,19 +42,32 @@ L<openssl_user_macros(7)>:
                            BIGNUM *rem, void (*callback)(int, int, void *),
                            void *cb_arg);
 
- int BN_is_prime(const BIGNUM *a, int checks,
+ int BN_is_prime(const BIGNUM *p, int nchecks,
                  void (*callback)(int, int, void *), BN_CTX *ctx, void *cb_arg);
 
- int BN_is_prime_fasttest(const BIGNUM *a, int checks,
+ int BN_is_prime_fasttest(const BIGNUM *p, int nchecks,
                           void (*callback)(int, int, void *), BN_CTX *ctx,
                           void *cb_arg, int do_trial_division);
 
+Deprecated since OpenSSL 3.0:
+
+ int BN_is_prime_ex(const BIGNUM *p, int nchecks, BN_CTX *ctx, BN_GENCB *cb);
+
+ int BN_is_prime_fasttest_ex(const BIGNUM *p, int nchecks, BN_CTX *ctx,
+                             int do_trial_division, BN_GENCB *cb);
+
 =head1 DESCRIPTION
 
 BN_generate_prime_ex2() generates a pseudo-random prime number of
 at least bit length B<bits> using the BN_CTX provided in B<ctx>. The value of
 B<ctx> must not be NULL.
+
 The returned number is probably prime with a negligible error.
+The maximum error rate is 2^-128.
+It's 2^-287 for a 512 bit prime, 2^-435 for a 1024 bit prime,
+2^-648 for a 2048 bit prime, and lower than 2^-882 for primes larger
+than 2048 bit.
+
 If B<add> is B<NULL> the returned prime number will have exact bit
 length B<bits> with the top most two bits set.
 
@@ -111,37 +121,43 @@ B<ctx> parameter is passed.
 In this case the random number generator associated with the default OPENSSL_CTX
 will be used.
 
-BN_is_prime_ex() and BN_is_prime_fasttest_ex() test if the number B<p> is
-prime.  The following tests are performed until one of them shows that
-B<p> is composite; if B<p> passes all these tests, it is considered
-prime.
-
-BN_is_prime_fasttest_ex(), when called with B<do_trial_division == 1>,
-first attempts trial division by a number of small primes;
-if no divisors are found by this test and B<cb> is not B<NULL>,
-B<BN_GENCB_call(cb, 1, -1)> is called.
-If B<do_trial_division == 0>, this test is skipped.
-
-Both BN_is_prime_ex() and BN_is_prime_fasttest_ex() perform a Miller-Rabin
-probabilistic primality test with B<nchecks> iterations. If
-B<nchecks == BN_prime_checks>, a number of iterations is used that
-yields a false positive rate of at most 2^-64 for random input.
-The error rate depends on the size of the prime and goes down for bigger primes.
-The rate is 2^-80 starting at 308 bits, 2^-112 at 852 bits, 2^-128 at 1080 bits,
-2^-192 at 3747 bits and 2^-256 at 6394 bits.
-
-When the source of the prime is not random or not trusted, the number
-of checks needs to be much higher to reach the same level of assurance:
-It should equal half of the targeted security level in bits (rounded up to the
-next integer if necessary).
-For instance, to reach the 128 bit security level, B<nchecks> should be set to
-64.
-
-If B<cb> is not B<NULL>, B<BN_GENCB_call(cb, 1, j)> is called
-after the j-th iteration (j = 0, 1, ...). B<ctx> is a
-pre-allocated B<BN_CTX> (to save the overhead of allocating and
+BN_check_prime(), BN_is_prime_ex(), BN_is_prime_fasttest_ex(), BN_is_prime()
+and BN_is_prime_fasttest() test if the number B<p> is prime.
+The functions tests until one of the tests shows that B<p> is composite,
+or all the tests passed.
+If B<p> passes all these tests, it is considered a probable prime.
+
+The test performed on B<p> are trial division by a number of small primes
+and rounds of the of the Miller-Rabin probabilistic primality test.
+
+The functions do at least 64 rounds of the Miller-Rabin test giving a maximum
+false positive rate of 2^-128.
+If the size of B<p> is more than 2048 bits, they do at least 128 rounds
+giving a maximum false positive rate of 2^-256.
+
+If B<nchecks> is larger than the minimum above (64 or 128), B<nchecks>
+rounds of the Miller-Rabin test will be done.
+
+If B<do_trial_division> set to B<0>, the trial division will be skipped.
+BN_is_prime_ex() and BN_is_prime() always skip the trial division.
+
+BN_is_prime_ex(), BN_is_prime_fasttest_ex(), BN_is_prime()
+and BN_is_prime_fasttest() are deprecated.
+
+BN_is_prime_fasttest() and BN_is_prime() behave just like
+BN_is_prime_fasttest_ex() and BN_is_prime_ex() respectively, but with the old
+style call back.
+
+B<ctx> is a pre-allocated B<BN_CTX> (to save the overhead of allocating and
 freeing the structure in a loop), or B<NULL>.
 
+If the trial division is done, and no divisors are found and B<cb>
+is not B<NULL>, B<BN_GENCB_call(cb, 1, -1)> is called.
+
+After each round of the Miller-Rabin probabilistic primality test,
+if B<cb> is not B<NULL>, B<BN_GENCB_call(cb, 1, j)> is called
+with B<j> the iteration (j = 0, 1, ...).
+
 BN_GENCB_call() calls the callback function held in the B<BN_GENCB> structure
 and passes the ints B<a> and B<b> as arguments. There are two types of
 B<BN_GENCB> structure that are supported: "new" style and "old" style. New
@@ -176,9 +192,9 @@ BN_is_prime_fasttest_ex(), respectively.
 
 BN_generate_prime_ex() return 1 on success or 0 on error.
 
-BN_is_prime_ex(), BN_is_prime_fasttest_ex(), BN_is_prime() and
-BN_is_prime_fasttest() return 0 if the number is composite, 1 if it is
-prime with an error probability of less than 0.25^B<nchecks>, and
+BN_is_prime_ex(), BN_is_prime_fasttest_ex(), BN_is_prime(),
+BN_is_prime_fasttest() and BN_check_prime return 0 if the number is composite,
+1 if it is prime with an error probability of less than 0.25^B<nchecks>, and
 -1 on error.
 
 BN_generate_prime() returns the prime number on success, B<NULL> otherwise.
@@ -220,6 +236,8 @@ L<RAND(7)>
 The BN_GENCB_new(), BN_GENCB_free(),
 and BN_GENCB_get_arg() functions were added in OpenSSL 1.1.0.
 
+BN_check_prime() was added in OpenSSL 3.0.
+
 =head1 COPYRIGHT
 
 Copyright 2000-2019 The OpenSSL Project Authors. All Rights Reserved.
diff --git a/include/openssl/bn.h b/include/openssl/bn.h
index 12fbcdaccd..2eabadab27 100644
--- a/include/openssl/bn.h
+++ b/include/openssl/bn.h
@@ -109,8 +109,9 @@ void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
 
 void *BN_GENCB_get_arg(BN_GENCB *cb);
 
-# define BN_prime_checks 0      /* default: select number of iterations based
-                                 * on the size of the number */
+# if !OPENSSL_API_3
+#  define BN_prime_checks 0      /* default: select number of iterations based
+                                  * on the size of the number */
 
 /*
  * BN_prime_checks_for_size() returns the number of Miller-Rabin iterations
@@ -175,14 +176,15 @@ void *BN_GENCB_get_arg(BN_GENCB *cb);
  *  (b) >=    6 |     >=    12 |         34 |         64 bit
  */
 
-# define BN_prime_checks_for_size(b) ((b) >= 3747 ?  3 : \
-                                (b) >=  1345 ?  4 : \
-                                (b) >=  476 ?  5 : \
-                                (b) >=  400 ?  6 : \
-                                (b) >=  347 ?  7 : \
-                                (b) >=  308 ?  8 : \
-                                (b) >=  55  ? 27 : \
-                                /* b >= 6 */ 34)
+#  define BN_prime_checks_for_size(b) ((b) >= 3747 ?  3 : \
+                                      (b) >=  1345 ?  4 : \
+                                      (b) >=  476 ?  5 : \
+                                      (b) >=  400 ?  6 : \
+                                      (b) >=  347 ?  7 : \
+                                      (b) >=  308 ?  8 : \
+                                      (b) >=  55  ? 27 : \
+                                      /* b >= 6 */ 34)
+# endif
 
 # define BN_num_bytes(a) ((BN_num_bits(a)+7)/8)
 
@@ -353,15 +355,16 @@ DEPRECATEDIN_0_9_8(int
                                         BN_CTX *ctx, void *cb_arg,
                                         int do_trial_division))
 
+DEPRECATEDIN_3(int BN_is_prime_ex(const BIGNUM *p, int nchecks, BN_CTX *ctx, BN_GENCB *cb))
+DEPRECATEDIN_3(int BN_is_prime_fasttest_ex(const BIGNUM *p, int nchecks, BN_CTX *ctx,
+                            int do_trial_division, BN_GENCB *cb))
 /* Newer versions */
 int BN_generate_prime_ex2(BIGNUM *ret, int bits, int safe,
                          const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb,
                          BN_CTX *ctx);
 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add,
                          const BIGNUM *rem, BN_GENCB *cb);
-int BN_is_prime_ex(const BIGNUM *p, int nchecks, BN_CTX *ctx, BN_GENCB *cb);
-int BN_is_prime_fasttest_ex(const BIGNUM *p, int nchecks, BN_CTX *ctx,
-                            int do_trial_division, BN_GENCB *cb);
+int BN_check_prime(const BIGNUM *p, BN_CTX *ctx, BN_GENCB *cb);
 
 int BN_X931_generate_Xpq(BIGNUM *Xp, BIGNUM *Xq, int nbits, BN_CTX *ctx);
 
diff --git a/include/openssl/dsa.h b/include/openssl/dsa.h
index f14be2812d..858c316b66 100644
--- a/include/openssl/dsa.h
+++ b/include/openssl/dsa.h
@@ -144,15 +144,17 @@ int DSAparams_print_fp(FILE *fp, const DSA *x);
 int DSA_print_fp(FILE *bp, const DSA *x, int off);
 # endif
 
-# define DSS_prime_checks 64
+# if !OPENSSL_API_3
+#  define DSS_prime_checks 64
 /*
  * Primality test according to FIPS PUB 186-4, Appendix C.3. Since we only
  * have one value here we set the number of checks to 64 which is the 128 bit
  * security level that is the highest level and valid for creating a 3072 bit
  * DSA key.
  */
-# define DSA_is_prime(n, callback, cb_arg) \
-        BN_is_prime(n, DSS_prime_checks, callback, NULL, cb_arg)
+#  define DSA_is_prime(n, callback, cb_arg) \
+           BN_is_prime(n, DSS_prime_checks, callback, NULL, cb_arg)
+# endif
 
 # ifndef OPENSSL_NO_DH
 /*
diff --git a/test/bntest.c b/test/bntest.c
index c3d6b933a5..07b8aade37 100644
--- a/test/bntest.c
+++ b/test/bntest.c
@@ -2312,7 +2312,7 @@ static int test_is_prime(int i)
 
     for (trial