<div dir="ltr"><div class="gmail_default" style="font-family:verdana,sans-serif">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).<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Aug 1, 2015 at 8:14 PM, Viktor Dukhovni <span dir="ltr"><<a href="mailto:openssl-users@dukhovni.org" target="_blank">openssl-users@dukhovni.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Sun, Aug 02, 2015 at 12:59:49AM +0000, <a href="mailto:paul@securecottage.com">paul@securecottage.com</a> wrote:<br>
<br>
> He managed to get a common factor of<br>
> gcd(p-1,q-1) = 2 * 28559 from the following 1024 bit rsa generated key<br>
> (factorisation of p*q-1 is shown):<br>
><br>
> n-1 = 2 * 3^3 * 7 * 13 * 67 * 2399 * 28559 *<br>
> 5485062554686449262177590194597345407327047899375366044215091312099734701911004226037445837630559113651708968440813791318544450398897628 67234233761906471233193768567784328338581360170038166729050302672416075037390699071355182394190448204086007354388034161296410061846686501<br>
> 4941425056336718955019<br>
<br>
Note, the last factor is not a prime, but producing its prime<br>
factors may be non-trivial.<br>
<br>
> Any rsa key generation in SAFE mode will always have a gcd(p-1,q-1)=2, so<br>
> SAFE mode always avoids common factors.<br>
<br>
Safe (Sophie Germain) primes are too expensive to generate, if your<br>
concerns are warranted, the simpler approach is to reject q when<br>
GCD (p-1,q-1) != 2.  We can set p = 3 mod 4, to ensure that no<br>
higher power of 2 is ever possible.  The GCD check will then rarely<br>
fail, so the overhead is mostly just the GCD check (much faster<br>
than generating "safe" primes).<br>
<br>
> My conclusion is that openssl code can have common factors (must be above<br>
> 17863) in its rsa keys every 20,000 key generations or so when not generated<br>
> in SAFE mode, and that at this time approximately 30 bits of the totient<br>
> will be revealed out of the 1024 bits of the full totient. There is, of<br>
> course, no way of knowing which of the 20,000 key generations will have the<br>
> common factors.<br>
<br>
It is a bit of a leap to claim a leak of 30 bits, because there's<br>
no obvious way to know which if any of the prime factors of (n-1)<br>
are also shared by (p-1) and (q-1).  Also knowing d (e^-1) modulo<br>
an ~30 bit number, is not nearly so tidy as knowing "30 bits of d".<br>
<br>
The key question is whether this information can help speed up<br>
GNFS.  Speeding up a brute force search through a 1024-bit keyspace<br>
by 30 bits is no use at all.<br>
<br>
I don't know enough about GNFS to comment on whether such residues<br>
can actually help speed factoring.<br>
<br>
Perhaps you are arguing that the GCD check is cheap, and should be<br>
done out of "an abundance of caution".  That might be true, but<br>
I'd like to hear that advice from someone well versed in state of<br>
the art factorization methods.<br>
<span class="HOEnZb"><font color="#888888"><br>
--<br>
        Viktor.<br>
_______________________________________________<br>
openssl-dev mailing list<br>
To unsubscribe: <a href="https://mta.openssl.org/mailman/listinfo/openssl-dev" rel="noreferrer" target="_blank">https://mta.openssl.org/mailman/listinfo/openssl-dev</a><br>
</font></span></blockquote></div><br></div>