Fix probable_prime over large shift
authorMatt Caswell <matt@openssl.org>
Fri, 13 Mar 2015 12:48:57 +0000 (12:48 +0000)
committerMatt Caswell <matt@openssl.org>
Tue, 17 Mar 2015 13:41:49 +0000 (13:41 +0000)
commite4676e900f165f5272991443225813002300b09b
tree50d2c4fdafad98e84961c5894136889e096a3416
parent3475c7a1854977e290ab44deb16551f6d55ad9a7
Fix probable_prime over large shift

In the probable_prime() function we behave slightly different if the number
of bits we are interested in is <= BN_BITS2 (the num of bits in a BN_ULONG).
As part of the calculation we work out a size_limit as follows:

    size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;

There is a problem though if bits == BN_BITS2. Shifting by that much causes
undefined behaviour. I did some tests. On my system BN_BITS2 == 64. So I
set bits to 64 and calculated the result of:

    (((BN_ULONG)1) << bits)

I was expecting to get the result 0. I actually got 1! Strangely this...

    (((BN_ULONG)0) << BN_BITS2)

...does equal 0! This means that, on my system at least, size_limit will be
off by 1 when bits == BN_BITS2.

This commit fixes the behaviour so that we always get consistent results.

Reviewed-by: Andy Polyakov <appro@openssl.org>
crypto/bn/bn_prime.c