Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I am using an algorithm (can be found here1) that can compute efficiently the GCD of multiple RSA keys. It intended for RSA keys that were generated with low entropy and may have one of their primes in common.
In the documentation it is stated that:
if a modulus shares both of its prime factors with two other distinct moduli, then the GCD will be the modulus itself rather than one of itsprime factors
Here's the scenario that this caveat in the documentation worries about:
Suppose you had three modulii:
$M_1 = p \times q$
$M_2 = p \times r$
$M_3 = q \times s$
Then, when the program outputs the GCD of $M_1$, it'll output $p \times q = M_1$. It'd do this even though the above has enough information to factor $M_1$ efficiently.
It does this because it actually outputs $GCD( M_1, M_2M_3)$; because both factors of $M_1$ appear in $M_2M_3$, both factors appear in the output.
This is certainly possible; as for how likely it is, well, that rather depends on the details within exact RSA generation algorithm. I personally would be surprised, though; most RSA generation algorithms pick one prime, and then pick the other (and run into problems because entropy was lousy when they picked the first prime, and then got better when it picked the second). The primes it picks depends on the internal state (and the entropy). For the first primes to match, we need to assume that the initial entropy was lousy (however, it got better when picking the second prime); this is plausible. However, in order to share the second prime, then two runs must have distinct states when picking the first prime, and then somehow fall into exactly the same state when picking the second. That seems rather implausible (although not impossible) to me.
return 4;
$\endgroup$
If both primes are shared with different moduli you could compute the classic GCD between two moduli and recover the factorization.
Said that, I think that if the generator has a poor source of entropy it can happen that some primes are used more times.
Update (26.06.2019), this was actually done in February 2012.
Paper: Ron was wrong, Whit is right
They collected 11.4 Million public RSA keys, where almost 27000 of them are vulnerable. These include 10 2048-bit RSA keys.
It was possible by applying a special form of the GCD algorithm.
They suspect that the main cause for this to happen is that proper seeding of random number generators is still a problematic issue.
Overall, 1024-bit RSA provides 99.8% security at best.
