I was asked this by my professor and I didn't understand the reasoning behind it. If Alice has a the key pair $(p_a, n_a)$ and Bob has the key pair $(p_b, n_b)$, why do $n_a$ and $n_b$ have to be relatively prime?


In RSA, the modulus is computed as $n=pq$ where $p$ and $q$ are prime. Given two moduli, if they have no primes in common, then the GCD is $1$ and they are relatively prime. If they share a prime factor, then the GCD will reveal that prime factor. Therefore, anyone who knows the two public keys can factorize the moduli and break security.

| improve this answer | |
  • $\begingroup$ Ahh that makes total sense. So that means p and q need to be unique to everyone? Surely there will be some people who choose similar primes between themselves. I guess there is a sort of "herd protection"? $\endgroup$ – n0pe Nov 5 '14 at 12:57
  • 2
    $\begingroup$ Theoretically, if good random number generators are used, there are enough primes to ensure this won't happen. In practice, however, it has been the case that this has happened (see this). $\endgroup$ – mikeazo Nov 5 '14 at 13:42
  • $\begingroup$ An other good reference: smartfacts.cr.yp.to $\endgroup$ – ddddavidee Nov 5 '14 at 20:59

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.