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

5 files changed, 65 insertions, 59 deletions

diff --git a/crypto/bn/bn_depr.c b/crypto/bn/bn_depr.c
index 18d02d8..4dbbdc3 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 4c86986..ec90338 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 7d89d32..fd1c3c3 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 e5e4ecc..c31b43b 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 211886f..1e4d499 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)