Skip to site navigation (Press enter)

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

Viktor Dukhovni Fri, 31 Jul 2015 11:47:11 -0700

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? -- Viktor. _______________________________________________ openssl-dev mailing list To unsubscribe: [mta.openssl.org]

- [openssl-dev] common factors in (p-1) and (... paul
- Re: [openssl-dev] common factors in (p... mancha
- Re: [openssl-dev] common factors i... paul
- Re: [openssl-dev] common facto... Viktor Dukhovni
- Re: [openssl-dev] common facto... mancha

- Re: [openssl-dev] common factors in (p... Bill Cox
- Re: [openssl-dev] common factors i... Viktor Dukhovni
- Re: [openssl-dev] common facto... mancha
- Re: [openssl-dev] common f... Ben Laurie
- Re: [openssl-dev] com... mancha

- Re: [openssl-dev] common factors i... mancha
- Re: [openssl-dev] common facto... Bill Cox
- Re: [openssl-dev] common f... Viktor Dukhovni
- Re: [openssl-dev] com... Samuel Neves

- Re: [openssl-dev] common factors in (p... Kurt Roeckx
- Re: [openssl-dev] common factors in (p... Blumenthal, Uri - 0553 - MITLL