# Recovering 3 private keys if Eve knows that the keys are shared prime numbers and knows their public keys, How would this be done?

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?

• 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 – kasperd Apr 29 '18 at 21:49

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^{503}log(1/(1-0.5)] \approx 6.02520 * 10^{75}$ generated primes needed to achieve a 50% probability of a collision.