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-us...@dukhovni.org> wrote: > On Sun, Aug 02, 2015 at 12:59:49AM +0000, p...@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 >
_______________________________________________ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
