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

[Mehdi Sotoodeh]

This characteristic is not limited to common factors of p-1 and q-1. For
every factor of (p-1) (and similarly for q-1) there exists a k where p*q+k
having same factor. In this case p-1 and q+k are sharing the same factor:
p*q+k = (p-1)(q-1) + (p-1) + (q+k). Based on this GCD(n+x,n+y) for a range
of x and y's can reveal some factors of (p-1)(q-1).

On Sat, Aug 1, 2015 at 8:14 PM, Viktor Dukhovni <openssl-users at dukhovni.org>
wrote:

> 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.
> _______________________________________________
> openssl-dev mailing list
> To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mta.openssl.org/pipermail/openssl-dev/attachments/20150802/57b02b89/attachment-0001.html>