<div dir="ltr"><br><br><div class="gmail_quote"><div dir="ltr">On Sat, 1 Aug 2015 at 14:22 mancha <<a href="mailto:mancha1@zoho.com">mancha1@zoho.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Fri, Jul 31, 2015 at 06:46:22PM +0000, Viktor Dukhovni wrote:<br>
> On Fri, Jul 31, 2015 at 11:19:39AM -0700, Bill Cox wrote:<br>
><br>
> > Cool observation.  From running a bit of Python code, it looks like<br>
> > the probability that GCD(p-1, p-q) == 4 is a bit higher than 15%, at<br>
> > least for random numbers between 2048 and 4096 bits long.  It looks<br>
> > like putting in a GCD(p-1, q-1) check will slow down finding<br>
> > suitable p and q by around a factor of 6.5.<br>
><br>
> A smaller slow-down would be incurred one were to restrict both of p,q<br>
> to 3 mod 4. In that case 2 would be the largest common even factor of<br>
> (p-1) and (q-1), and any appreciably large common odd factor<br>
> (necessarily above 17863 due to how each of p/q is chosen) would be<br>
> very rare.<br>
><br>
> Is there a good argument for adding the gcd test?  How big does the<br>
> common factor have to be for any information it might provide to be<br>
> substantially useful in finding 1/e mod phi(m)?<br>
><br>
> The larger the common factor is, the smaller the probability of p-1<br>
> and q-1 sharing it (for a given sufficiently large prime factor "r" of<br>
> (p-1), the probability of (q-1) also having that factor is 1/(r-1)).<br>
> If say "r" needs be 80 bits long to be useful in attacking RSA 1024,<br>
> then only ~1 in 2^80 (p-1,q-1) pairs will have such a common factor,<br>
> which is sufficiently rare not warrant any attention.<br>
><br>
> Also one still needs to be able to fully factor (n-1).  After tens of<br>
> thousands of trials, I managed to generate a (p,q,n) triple with a<br>
> 1024-bit modulus n in which (p-1,q-1) have a common odd factor.<br>
><br>
>     n =<br>
>     123727085863382195696899362818055010267368591819174730632443285012648773223152448218495408371737254282531468855140111723936275062312943433684139231097953508685462994307654703316031424869371422426773001891452680576333954733056995016189880381373567072504551999849596021790801362257131899242011337424119163152403<br>
><br>
>     e = F_4 = 65537<br>
><br>
>     gcd(p-1,q-1) = 2 * 28559<br>
><br>
> What can the OP tell us about d, p or q?  Can anyone produce a full<br>
> factorization of n - 1?<br>
<br>
n-1 = 2 * 3^3 * 7 * 13 * 67 * 2399 * 28559 *<br>
5485062554686449262177590194597345407327047899375366044215091312099734701911004226037445837630559113651708968440813791318544450398897628672342337619064712331937685677843283385813601700381667290503026724160750373906990713551823941904482040860073543880341612964100618466865014941425056336718955019<br></blockquote><div><br></div><div>That is not a prime factorisation.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
--<br>
<a href="https://twitter.com/mancha140" rel="noreferrer" target="_blank">https://twitter.com/mancha140</a><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>
</blockquote></div></div>