1
$\begingroup$

okay so here is the original question:

Alice Bob and Carl are generating public keys for RSA, but they are lazy and decide to share some of the work of generating prime numbers. They find 3 large prime numbers p,q and r, then Alice uses the modulus $n_A = pq$, Bob uses the modulus $n_B = pr$ and Carl uses the modulus $n_C = qr$. The prime numbers used are much to large factoring to be feasible, but Eve learns that they shared prime numbers (and knows their public keys) how does she obtain p, q and r?

My thinking or possible reasoning for this question. Since Eve knows the public keys and that the keys share prime numbers she can compute the GCD of n or factorize n in order to calculate or find the private keys. In this case she would first use Euclid's algorithm for $n_A = pq$ & $n_B= pr $ which we know is p because both n's share a common prime $p$. She would use the same process for computing $q$ which is $n_A = pq$ & $n_C = qr$. Shes does it a third time for $r$ which $n_B = pr$ & $n_C = qr$.

I want to know If I am thinking about this the right way or if I have the right idea. If I am on the right track, how do I mathematically represent this?

Improve this question
$\endgroup$
1
  • $\begingroup$ This older question is related. In 2012 it was demonstrated that not only does identical primes happen in practice, it is even feasible to collect the keys used by servers across all IPv4 addresses and identify which pairs of them share primes. paper presentation $\endgroup$
    – kasperd
    Apr 29, 2018 at 21:49

2 Answers 2

Reset to default
5
$\begingroup$

Yes, your thinking is correct! Using a "shared prime" when calculating $n_A$ and $n_B$ is disastrous for security simply through the fact that it reveals $p$, $q$, and $r$ with a few calls to the $gcd$ algorithm.

Luckily this incredibly unlikely to happen with the use of good randomness. In the case of 512-bit RSA, there are roughly $2^{503}$ 512-bit primes which, when using the birthday bound, equates to about $\sqrt[2][2*2^{503}log(1/(1-0.5)] \approx 6.02520 * 10^{75}$ generated primes needed to achieve a 50% probability of a collision.

Source: http://www.loyalty.org/~schoen/rsa/

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Key phrase: with the use of good randomness. If your router is generating an RSA keypair on startup, it's not going to have much randomness available, and is quite likely to have one of the same primes as somebody else's router. $\endgroup$
    – Mark
    Apr 29, 2018 at 20:23
  • $\begingroup$ "with the use of good randomness" is the key. Real world systems have been broken because of poor randomness leading to repeated primes (it is possible to find common factors (if there are any) much faster than trying each pair in turn). $\endgroup$
    – Martin Bonner supports Monica
    Apr 29, 2018 at 20:23
0
$\begingroup$

Something similar has actually happened on a massive scale.

Someone examined lots of routers with a built-in private/public key pair and found that some routers had the identical public key. Which means they shared two out of two prime numbers. This doesn't let you crack the private key on either of them - but then they had the clever idea that if some routers share two prime numbers, which should never happen, then maybe some share one prime number, which allows you to crack both private keys easily.

And with some very clever maths, it is actually possible to take a billion public keys and find all pairs that share a prime factor in reasonable time.

Improve this answer
$\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.