On Sat, Aug 01, 2015 at 01:50:00PM +0000, Ben Laurie wrote: > On Sat, 1 Aug 2015 at 14:22 mancha <manc...@zoho.com> wrote: > > > On Fri, Jul 31, 2015 at 06:46:22PM +0000, Viktor Dukhovni wrote: > > > On Fri, Jul 31, 2015 at 11:19:39AM -0700, Bill Cox wrote: > > > > > > > Cool observation. From running a bit of Python code, it looks > > > > like the probability that GCD(p-1, p-q) == 4 is a bit higher > > > > than 15%, at least for random numbers between 2048 and 4096 bits > > > > long. It looks like putting in a GCD(p-1, q-1) check will slow > > > > down finding suitable p and q by around a factor of 6.5. > > > > > > A smaller slow-down would be incurred one were to restrict both of > > > p,q to 3 mod 4. In that case 2 would be the largest common even > > > factor of (p-1) and (q-1), and any appreciably large common odd > > > factor (necessarily above 17863 due to how each of p/q is chosen) > > > would be very rare. > > > > > > Is there a good argument for adding the gcd test? How big does > > > the common factor have to be for any information it might provide > > > to be substantially useful in finding 1/e mod phi(m)? > > > > > > The larger the common factor is, the smaller the probability of > > > p-1 and q-1 sharing it (for a given sufficiently large prime > > > factor "r" of (p-1), the probability of (q-1) also having that > > > factor is 1/(r-1)). If say "r" needs be 80 bits long to be useful > > > in attacking RSA 1024, then only ~1 in 2^80 (p-1,q-1) pairs will > > > have such a common factor, which is sufficiently rare not warrant > > > any attention. > > > > > > Also one still needs to be able to fully factor (n-1). After tens > > > of thousands of trials, I managed to generate a (p,q,n) triple > > > with a 1024-bit modulus n in which (p-1,q-1) have a common odd > > > factor. > > > > > > n = > > > > > > > 123727085863382195696899362818055010267368591819174730632443285012648773223152448218495408371737254282531468855140111723936275062312943433684139231097953508685462994307654703316031424869371422426773001891452680576333954733056995016189880381373567072504551999849596021790801362257131899242011337424119163152403 > > > > > > e = F_4 = 65537 > > > > > > gcd(p-1,q-1) = 2 * 28559 > > > > > > What can the OP tell us about d, p or q? Can anyone produce a > > > full factorization of n - 1? > > > > n-1 = 2 * 3^3 * 7 * 13 * 67 * 2399 * 28559 * > > > > 5485062554686449262177590194597345407327047899375366044215091312099734701911004226037445837630559113651708968440813791318544450398897628672342337619064712331937685677843283385813601700381667290503026724160750373906990713551823941904482040860073543880341612964100618466865014941425056336718955019 > > > > That is not a prime factorisation.
Just helping get things started. Feel free to take over and claim the last number in my product.
pgp2BFvzlN2bz.pgp
Description: PGP signature
_______________________________________________ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
