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

[paul at securecottage.com]

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

I have looked at your latest source to see if you have a possible  
common factor for (p-1) and (q-1) in your RSA key generation code.

I have concluded, after a quick look, that you may when you are not  
using SAFE mode to generate the keys.

When keys are generated using SAFE mode then (p-1)/2 must be a prime.   
As the factorisation of p-1==2*prime and there are checks to make sure  
that p and q are not the same, then you cannot have a common factor in  
p-1 and q-1 besides 2.

The code in rsa_builtin_keygen() does not use safe mode when  
generating keys using
BN_generate_prime_ex(rsa->p, bitsp, 0, NULL, NULL, cb).  There are  
tests for these primes, but there does not seem to be an explicit  
check that there are no common factors in (p-1) and (q-1) besides 2 or  
3.

The authors of the code may well correct me here since I have just  
quickly looked at it.

A quick check for this condition with BN_GCD(p-1,q-1)>3 in   
rsa_builtin_keygen() would detect any problems and avoid the possible  
leaking of part of the totient.

I admit that it is unlikely that a large enough part of the totient  
would be revealed (when a truely random generator is used) to endanger  
the RSA pair, but I think it is a bit of housekeeping that knowledge  
of even small factors (besides 2 and 3) are kept out of the attackers  
hands.

Thank You

Paul Cheffers