From: Shane Lontis <shane.lontis@oracle.com>
Date: Thu, 21 Jun 2018 03:37:52 +0000 (+1000)
Subject: Fixed range of random produced in BN_is_prime_fasttest_ex() to be 1 < rand < w-1... 
X-Git-Tag: OpenSSL_1_1_1-pre9~259
X-Git-Url: https://git.openssl.org/gitweb/?p=openssl.git;a=commitdiff_plain;h=7d79d13a564d5c065318aa47f4cd511eece449e8;hp=b8c32081e02b7008a90d878eccce46da256dfe86

Fixed range of random produced in BN_is_prime_fasttest_ex() to be 1 < rand < w-1. It was using 1<= rand < w (which is wrong by 1 on both ends)

Reviewed-by: Paul Dale <paul.dale@oracle.com>
Reviewed-by: Rich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/6547)
---

diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c
index 03ccde9510..b91b31b1f3 100644
--- a/crypto/bn/bn_prime.c
+++ b/crypto/bn/bn_prime.c
@@ -154,19 +154,21 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
     int i, j, ret = -1;
     int k;
     BN_CTX *ctx = NULL;
-    BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
+    BIGNUM *A1, *A1_odd, *A3, *check; /* taken from ctx */
     BN_MONT_CTX *mont = NULL;
 
-    if (BN_cmp(a, BN_value_one()) <= 0)
+    /* Take care of the really small primes 2 & 3 */
+    if (BN_is_word(a, 2) || BN_is_word(a, 3))
+        return 1;
+
+    /* Check odd and bigger than 1 */
+    if (!BN_is_odd(a) || BN_cmp(a, BN_value_one()) <= 0)
         return 0;
 
     if (checks == BN_prime_checks)
         checks = BN_prime_checks_for_size(BN_num_bits(a));
 
     /* first look for small factors */
-    if (!BN_is_odd(a))
-        /* a is even => a is prime if and only if a == 2 */
-        return BN_is_word(a, 2);
     if (do_trial_division) {
         for (i = 1; i < NUMPRIMES; i++) {
             BN_ULONG mod = BN_mod_word(a, primes[i]);
@@ -186,20 +188,18 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
     BN_CTX_start(ctx);
 
     A1 = BN_CTX_get(ctx);
+    A3 = BN_CTX_get(ctx);
     A1_odd = BN_CTX_get(ctx);
     check = BN_CTX_get(ctx);
     if (check == NULL)
         goto err;
 
     /* compute A1 := a - 1 */
-    if (!BN_copy(A1, a))
-        goto err;
-    if (!BN_sub_word(A1, 1))
+    if (!BN_copy(A1, a) || !BN_sub_word(A1, 1))
         goto err;
-    if (BN_is_zero(A1)) {
-        ret = 0;
+    /* compute A3 := a - 3 */
+    if (!BN_copy(A3, a) || !BN_sub_word(A3, 3))
         goto err;
-    }
 
     /* write  A1  as  A1_odd * 2^k */
     k = 1;
@@ -216,11 +216,9 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
         goto err;
 
     for (i = 0; i < checks; i++) {
-        if (!BN_priv_rand_range(check, A1))
-            goto err;
-        if (!BN_add_word(check, 1))
+        /* 1 < check < a-1 */
+        if (!BN_priv_rand_range(check, A3) || !BN_add_word(check, 2))
             goto err;
-        /* now 1 <= check < a */
 
         j = witness(check, a, A1, A1_odd, k, ctx, mont);
         if (j == -1)
diff --git a/test/bntest.c b/test/bntest.c
index 35587780f3..0502497fe3 100644
--- a/test/bntest.c
+++ b/test/bntest.c
@@ -2128,25 +2128,48 @@ err:
     return st;
 }
 
-static int test_3_is_prime(void)
+static int primes[] = { 2, 3, 5, 7, 17863 };
+
+static int test_is_prime(int i)
 {
     int ret = 0;
     BIGNUM *r = NULL;
+    int trial;
 
-    /*
-     * For a long time, small primes were not considered prime when
-     * do_trial_division was set.
-     */
-    if (!TEST_ptr(r = BN_new())
-            || !TEST_true(BN_set_word(r, 3))
-            || !TEST_int_eq(BN_is_prime_fasttest_ex(r, 3 /* nchecks */, ctx,
-                                0 /* do_trial_division */, NULL), 1)
-            || !TEST_int_eq(BN_is_prime_fasttest_ex(r, 3 /* nchecks */, ctx,
-                                1 /* do_trial_division */, NULL), 1))
+    if (!TEST_ptr(r = BN_new()))
         goto err;
 
+    for (trial = 0; trial <= 1; ++trial) {
+        if (!TEST_true(BN_set_word(r, primes[i]))
+                || !TEST_int_eq(BN_is_prime_fasttest_ex(r, 1, ctx, trial, NULL),
+                                1))
+            goto err;
+    }
+
     ret = 1;
+err:
+    BN_free(r);
+    return ret;
+}
 
+static int not_primes[] = { -1, 0, 1, 4 };
+
+static int test_not_prime(int i)
+{
+    int ret = 0;
+    BIGNUM *r = NULL;
+    int trial;
+
+    if (!TEST_ptr(r = BN_new()))
+        goto err;
+
+    for (trial = 0; trial <= 1; ++trial) {
+        if (!TEST_true(BN_set_word(r, not_primes[i]))
+                || !TEST_false(BN_is_prime_fasttest_ex(r, 1, ctx, trial, NULL)))
+            goto err;
+    }
+
+    ret = 1;
 err:
     BN_free(r);
     return ret;
@@ -2250,7 +2273,8 @@ int setup_tests(void)
         ADD_TEST(test_gf2m_modsqrt);
         ADD_TEST(test_gf2m_modsolvequad);
 #endif
-        ADD_TEST(test_3_is_prime);
+        ADD_ALL_TESTS(test_is_prime, (int)OSSL_NELEM(primes));
+        ADD_ALL_TESTS(test_not_prime, (int)OSSL_NELEM(not_primes));
     } else {
         ADD_ALL_TESTS(run_file_tests, n);
     }