[openssl-dev] common factors in (p-1) and (q-1)
openssl-users at dukhovni.org
Sat Aug 1 02:06:59 UTC 2015
On Fri, Jul 31, 2015 at 11:31:08PM +0000, paul at securecottage.com wrote:
> I have checked through the key generation code of the openssl ssl code.
Not carefully enough...
> hacked it to report the greatest common divisor of p-1 and q-1. I then ran
> 100 key generations. It only had greatest common divisors of 2, 4 , 8, and
> 16. There were no other primes reported besides small powers of 2.
The reason is that all the pseudo-primes generated for testing are
sieved to avoid numbers that are congruent to either 0 or 1 mod p
for each of the first 2048 primes other than 2 (2 is avoided by
forcing the low bit to 1).
Thus any odd factor of (p-1) or (q-1) is necessarily larger than
the 2048th prime or 17863. To see an appreciable chance of such
a common factor you need O(20000) trials.
While a check to avoid gcd(p-1, q-1) > 2 is not too expensive, it
is not clear that it is worth the trouble. Perhaps it should be
done anyway, just because we can, but I am not convinced.
More information about the openssl-dev