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

[Blumenthal, Uri - 0553 - MITLL]

Viktor,

This is my logic precisely:"Perhaps we should do this check, just because we can". 

It makes things cryptographically better. Is it really necessary (better vs. good enough)? I don't know, maybe not. But the prudent approach seems to be closing as many of the potential loopholes as possible, even if we don't see an exploit coming from one right now. And it is possible to close this loophole without spending much on it, so why not?

P.S. I didn't have a chance yet to discuss this with my colleagues.

Sent from my BlackBerry 10 smartphone on the Verizon Wireless 4G LTE network.
  Original Message  
From: Viktor Dukhovni
Sent: Friday, July 31, 2015 22:07
To: openssl-dev at openssl.org
Reply To: openssl-dev at openssl.org
Subject: Re: [openssl-dev] common factors in (p-1) and (q-1)

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.
_______________________________________________
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/x-pkcs7-signature
Size: 4350 bytes
Desc: not available
URL: <http://mta.openssl.org/pipermail/openssl-dev/attachments/20150802/6fb94121/attachment.bin>