diff options
author | Adam Langley <agl@chromium.org> | 2013-04-23 14:36:06 -0400 |
---|---|---|
committer | Ben Laurie <ben@links.org> | 2013-06-04 18:52:30 +0100 |
commit | 96a4c31be3344cb08994a9d460c0ebd55939cc5b (patch) | |
tree | 45882a374b9c9dd0c46c0df2f17d640de3448d82 /crypto/bn/bn_prime.c | |
parent | 2b0180c37fa6ffc48ee40caa831ca398b828e680 (diff) |
Ensure that, when generating small primes, the result is actually of the
requested size. Fixes OpenSSL #2701.
This change does not address the cases of generating safe primes, or
where the |add| parameter is non-NULL.
Conflicts:
crypto/bn/bn.h
crypto/bn/bn_err.c
Diffstat (limited to 'crypto/bn/bn_prime.c')
-rw-r--r-- | crypto/bn/bn_prime.c | 71 |
1 files changed, 61 insertions, 10 deletions
diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c index 7b25979dd1..339dbec570 100644 --- a/crypto/bn/bn_prime.c +++ b/crypto/bn/bn_prime.c @@ -165,6 +165,19 @@ int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, BN_CTX *ctx; int checks = BN_prime_checks_for_size(bits); + if (bits < 2) + { + /* There are no prime numbers this small. */ + BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL); + return 0; + } + else if (bits == 2 && safe) + { + /* The smallest safe prime (7) is three bits. */ + BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL); + return 0; + } + ctx=BN_CTX_new(); if (ctx == NULL) goto err; BN_CTX_start(ctx); @@ -378,27 +391,65 @@ static int probable_prime(BIGNUM *rnd, int bits) { int i; prime_t mods[NUMPRIMES]; - BN_ULONG delta,maxdelta; + BN_ULONG delta; + BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES-1]; + char is_single_word = bits <= BN_BITS2; again: if (!BN_rand(rnd,bits,1,1)) return(0); - /* we now have a random number 'rand' to test. */ + /* we now have a random number 'rnd' to test. */ for (i=1; i<NUMPRIMES; i++) mods[i]=(prime_t)BN_mod_word(rnd,(BN_ULONG)primes[i]); - maxdelta=BN_MASK2 - primes[NUMPRIMES-1]; + /* If bits is so small that it fits into a single word then we + * additionally don't want to exceed that many bits. */ + if (is_single_word) + { + BN_ULONG size_limit = (((BN_ULONG) 1) << bits) - BN_get_word(rnd) - 1; + if (size_limit < maxdelta) + maxdelta = size_limit; + } delta=0; - loop: for (i=1; i<NUMPRIMES; i++) + loop: + if (is_single_word) { - /* check that rnd is not a prime and also - * that gcd(rnd-1,primes) == 1 (except for 2) */ - if (((mods[i]+delta)%primes[i]) <= 1) + BN_ULONG rnd_word = BN_get_word(rnd); + + /* In the case that the candidate prime is a single word then + * we check that: + * 1) It's greater than primes[i] because we shouldn't reject + * 3 as being a prime number because it's a multiple of + * three. + * 2) That it's not a multiple of a known prime. We don't + * check that rnd-1 is also coprime to all the known + * primes because there aren't many small primes where + * that's true. */ + for (i=1; i<NUMPRIMES && primes[i]<rnd_word; i++) { - delta+=2; - if (delta > maxdelta) goto again; - goto loop; + if ((mods[i]+delta)%primes[i] == 0) + { + delta+=2; + if (delta > maxdelta) goto again; + goto loop; + } + } + } + else + { + for (i=1; i<NUMPRIMES; i++) + { + /* check that rnd is not a prime and also + * that gcd(rnd-1,primes) == 1 (except for 2) */ + if (((mods[i]+delta)%primes[i]) <= 1) + { + delta+=2; + if (delta > maxdelta) goto again; + goto loop; + } } } if (!BN_add_word(rnd,delta)) return(0); + if (BN_num_bits(rnd) != bits) + goto again; bn_check_top(rnd); return(1); } |