2
$\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?

$\endgroup$
  • $\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 '18 at 21:49
6
$\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/

$\endgroup$
  • 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 '18 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 Apr 29 '18 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.

$\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.