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

[paul at securecottage.com]

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