Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
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; –  owlstead Aug 24 '13 at 1:05
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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