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 _______________________________________________ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
