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

[Viktor Dukhovni]

On Sun, Aug 02, 2015 at 12:59:49AM +0000, paul at securecottage.com wrote:

> He managed to get a common factor of
> gcd(p-1,q-1) = 2 * 28559 from the following 1024 bit rsa generated key
> (factorisation of p*q-1 is shown):
> 
> n-1 = 2 * 3^3 * 7 * 13 * 67 * 2399 * 28559 *
> 5485062554686449262177590194597345407327047899375366044215091312099734701911004226037445837630559113651708968440813791318544450398897628 67234233761906471233193768567784328338581360170038166729050302672416075037390699071355182394190448204086007354388034161296410061846686501
> 4941425056336718955019

Note, the last factor is not a prime, but producing its prime
factors may be non-trivial.

> Any rsa key generation in SAFE mode will always have a gcd(p-1,q-1)=2, so
> SAFE mode always avoids common factors.

Safe (Sophie Germain) primes are too expensive to generate, if your
concerns are warranted, the simpler approach is to reject q when
GCD (p-1,q-1) != 2.  We can set p = 3 mod 4, to ensure that no
higher power of 2 is ever possible.  The GCD check will then rarely
fail, so the overhead is mostly just the GCD check (much faster
than generating "safe" primes).

> My conclusion is that openssl code can have common factors (must be above
> 17863) in its rsa keys every 20,000 key generations or so when not generated
> in SAFE mode, and that at this time approximately 30 bits of the totient
> will be revealed out of the 1024 bits of the full totient. There is, of
> course, no way of knowing which of the 20,000 key generations will have the
> common factors.

It is a bit of a leap to claim a leak of 30 bits, because there's
no obvious way to know which if any of the prime factors of (n-1)
are also shared by (p-1) and (q-1).  Also knowing d (e^-1) modulo
an ~30 bit number, is not nearly so tidy as knowing "30 bits of d".

The key question is whether this information can help speed up
GNFS.  Speeding up a brute force search through a 1024-bit keyspace
by 30 bits is no use at all.

I don't know enough about GNFS to comment on whether such residues
can actually help speed factoring.

Perhaps you are arguing that the GCD check is cheap, and should be
done out of "an abundance of caution".  That might be true, but
I'd like to hear that advice from someone well versed in state of
the art factorization methods.

-- 
	Viktor.