2

This question already has an answer here:

In the RSA key generation steps, what if two entities select a common factor to generate n (i.e. p*q1=n1 and p*q2=n2) resulting in gcd(n1,n2) <> 1 ?

This will lead to a problem that everyone can calculate the p and q, thus breaking this encryption schema:

    gcd(n1,n2)=p
    n1/p gives q1
    n2/p gives q2

How does RSA ensure that this will not happen?

marked as duplicate by Mark, TildalWave, Graham Hill, Xander, Rory Alsop Oct 9 '14 at 14:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • @Mark this is indeed a Dupe imho, but to be fair, this question is better and more detailed then the "original" one, don't you think? – Lighty Oct 9 '14 at 7:20
  • 1
    @Lighty Dupe questions are not really "a problem" since they do somewhat help in finding answers to same or similar questions. The problem is that if left open it would needlessly dupe answers, often also inviting plagiarism and alike. They should be closed as dupes then, but I'm personally not harsh on them with my voting. ;) – TildalWave Oct 9 '14 at 10:46
3

The protection is called "luck". The probability that such an event occurs are sufficiently low that it can be neglected. Provided that the RSA keys are generated properly.

In 2012, some researchers made an interesting study in which they collected 11.5 millions of publicly available RSA keys (e.g. keys from SSL server certificates). They found that some keys were widely duplicated (my own sampling found the same: apparently there are widely deployed ADSL or cable modems that host a SSL server, all with the same public/private key pair). They also found, and that's what corresponds to your question, that factor sharing between distinct RSA keys was rare but not unheard of. This demonstrates use of a poorly seeded PRNG.

Indeed, any practical RSA key pair generation will produce random primes by running a PRNG seeded with some "initial randomness". If that initial random seed has not enough entropy, then the number of possible primes that this generator may produce is low. For instance, if the seed has 40 bits of entropy, then it suffices to generate a million RSA keys or so to obtain a collision (two of these keys using a common prime factor). More generally, if the seed has entropy n bits, then everybody should be safe as long as less than 2n/2 RSA keys are generated. Proper PRNG will aim at n = 128 or more.

While there is no need to fear such an outcome with properly generated RSA keys, this fact illustrates that adequate PRNG seeding is not easy, and, crucially, it is very hard to ascertain whether a given seeding process is adequate or not. Some embedded systems, and virtual machines, are most at risk of not having enough "physical" entropy to work with.

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