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

[Blumenthal, Uri - 0553 - MITLL]

I think adding the recommended check would be beneficial. Considering the frequency of ‎key generation, performance impact shouldn't matter all that much. 

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

Hi Mancha,

Since p*q-1==(p-1)*(q-1)+(p-1)+q-1) any prime that divides (p-1) and 
(q-1) will divide all 4 of the terms in the definition of p*q-1. Thus 
it will be a common factor in the totient.

I have checked through the key generation code of the openssl ssl 
code. 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.

So there doesn't seem to be a practical problem with common divisors 
in the openssl code.

Still, I think this is a theoretical problem. There should be a 
gcd(p-1,q-1)>16 check for the two primes in key generation.

Paul


Quoting mancha <mancha1 at zoho.com>:

> On Fri, Jul 31, 2015 at 02:36:03AM +0000, paul at securecottage.com wrote:
>>
>> Hi there,
>>
>> I have looked at the RSA protocol a bit and have concluded that
>>
>> 1) common factors in (p-1) and (q-1) are also in the factorisation of
>> (p*q-1). 2) by factoring (p*q-1) you can come up with candidates for
>> squares in the totient. 3) you can also come up with d mod
>> commonfactor^2 if there is a common factor.
>>
>> the math is shown in my wikipedia users page math blog at:
>>
>> https://en.wikipedia.org/wiki/User:Endo999#The_Bad_Stuff_That_Happens_When_There_Are_Common_Factors_Between_.28P-1.29_and_.28Q-1.29
>
> [SNIP]
>
> Hi. How are you finding a common factor f such that f|(p-1) and f|(q-1)?
>
> Thanks.
>
> --mancha
>
> -- https://twitter.com/mancha140



_______________________________________________
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/20150731/db182751/attachment.bin>