From 7d79d13a564d5c065318aa47f4cd511eece449e8 Mon Sep 17 00:00:00 2001 From: Shane Lontis Date: Thu, 21 Jun 2018 13:37:52 +1000 Subject: [PATCH] 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 Reviewed-by: Rich Salz (Merged from https://github.com/openssl/openssl/pull/6547) --- crypto/bn/bn_prime.c | 28 ++++++++++++-------------- test/bntest.c | 48 +++++++++++++++++++++++++++++++++----------- 2 files changed, 49 insertions(+), 27 deletions(-) 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); } -- 2.25.1