[openssl-dev] common factors in (p-1) and (q-1)

[Viktor Dukhovni]

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...

> I
> 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.

-- 
	Viktor.