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

[Samuel Neves]

On 31-07-2015 22:03, Viktor Dukhovni wrote:
> Is finding sufficiently large factors a tractable problem?

p-1 will usually have a large prime factor. But for q-1 to have the same prime factor is highly unlikely. The
probability that GCD(n1, n2) = d for random n1, n2 is 6/(d^2 pi^2). For RSA-1024 we need at least 256 bits of d leaked
to factor n using Coppersmith-style attacks. For that to happen, we need a common factor of at least 128 bits to exist
(to leak d mod f^2). This is significantly less likely than Miller-Rabin plain failing  (with probability ~2^-80) and
selecting a non-prime p or q.

Regarding strong primes and their utility, the Rivest-Silverman paper is still worth reading:
https://people.csail.mit.edu/rivest/pubs/RS01.version-1999-11-22.pdf