3
$\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$
6
$\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$
  • $\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 '13 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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