4
$\begingroup$

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

$\endgroup$

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Oh, I could easily program this, and I can image people who would. Simply load a PKCS#11 library each time you require a random, and use a software library of a HSM that uses a PRNG with a static state. Same random, same prime. return 4; $\endgroup$
    – Maarten Bodewes
    Aug 24, 2013 at 1:05
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ "1024-bit RSA provides 99.8% security at best" - the issue with the vulnerable keys is not inherent with 1024-bit RSA; instead, they were generated by bad key generators. $\endgroup$
    – poncho
    Jun 27, 2019 at 7:30
  • $\begingroup$ Didn't I mention this in They suspect that the main cause for this to happen is that proper seeding of random number generators is still a problematic issue. ? Should I edit the post to make it explicitly clear? $\endgroup$ Jun 27, 2019 at 7:36
  • $\begingroup$ Hello, @AleksanderRas it is nice that you put that paper in your answer. I am just asking myself what you mean by that 99.8% security. Does it mean that if I generate RSA keys several times, then in 0.2% of the cases, my keys will be vulnerable? $\endgroup$ Jun 27, 2019 at 7:46
  • $\begingroup$ @HilderVítorLimaPereira The 99.8% is for 1024-bit RSA keys. And yes, if you use a bad key generator the chance is 0.2% that anybody else in the world has a public key that shares one factor with your public key. But there's not too large of a concern, since pratically everybody nowadays uses at least keys of size 2048-bit. $\endgroup$ Jun 27, 2019 at 8:11
  • 1
    $\begingroup$ This conclusion is just wrong. You generalize, that the evidence gathered in this study shows a general law like in physics. That is just wrong, and is not in the slightest provable. The actual ratio does not show how many systems or keys are bad at all - systems are used differently, collisions have a chance to happen, user numbers differ, etc. All we can conclude: yes, such collisions happen and have to be taken seriously, the chance is not negligible. Generalizing such a ratio does not make sense. $\endgroup$
    – tylo
    Jun 27, 2019 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.