From 6e64c560663f5542fdc2580bb7b030c19b6919e4 Mon Sep 17 00:00:00 2001 From: Adam Langley Date: Thu, 20 Apr 2017 09:20:50 -0700 Subject: [PATCH] Small primes are primes too. Previously, BN_is_prime_fasttest_ex, when doing trial-division, would check whether the candidate is a multiple of a number of small primes and, if so, reject it. However, three is a multiple of three yet is still a prime number. This change accepts small primes as prime when doing trial-division. Reviewed-by: Kurt Roeckx Reviewed-by: Rich Salz (Merged from https://github.com/openssl/openssl/pull/3264) --- crypto/bn/bn_prime.c | 2 +- test/bntest.c | 24 ++++++++++++++++++++++++ 2 files changed, 25 insertions(+), 1 deletion(-) diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c index bbb124fb61..9295aeb625 100644 --- a/crypto/bn/bn_prime.c +++ b/crypto/bn/bn_prime.c @@ -176,7 +176,7 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, if (mod == (BN_ULONG)-1) goto err; if (mod == 0) - return 0; + return BN_is_word(a, primes[i]); } if (!BN_GENCB_call(cb, 1, -1)) goto err; diff --git a/test/bntest.c b/test/bntest.c index 0c15a129ce..449b3a4fd2 100644 --- a/test/bntest.c +++ b/test/bntest.c @@ -2084,6 +2084,29 @@ err: return st; } +static int test_3_is_prime() +{ + int ret = 0; + BIGNUM *r = BN_new(); + + /* For a long time, small primes were not considered prime when + * do_trial_division was set. */ + if (r == NULL || + !BN_set_word(r, 3) || + BN_is_prime_fasttest_ex(r, 3 /* nchecks */, ctx, + 0 /* do_trial_division */, NULL) != 1 || + BN_is_prime_fasttest_ex(r, 3 /* nchecks */, ctx, + 1 /* do_trial_division */, NULL) != 1) { + goto err; + } + + ret = 1; + +err: + BN_free(r); + return ret; +} + /* Delete leading and trailing spaces from a string */ static char *strip_spaces(char *p) @@ -2250,6 +2273,7 @@ int test_main(int argc, char *argv[]) ADD_TEST(test_gf2m_modsqrt); ADD_TEST(test_gf2m_modsolvequad); #endif + ADD_TEST(test_3_is_prime); ADD_TEST(file_tests); RAND_seed(rnd_seed, sizeof rnd_seed); -- 2.25.1