Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was wondering how many possible private/public keys exist? If a million people – for whatever reason – would try to generate 5 keys each in the same minute (on the same date and time) is there a high chance of collision? I believe GUID would suffer from that problem as many bits are reversed for date/time (and GUID version) and isn't meant to be used in that way.

Would RSA suffer from collisions if many keys were to be generated in the same moment? Is the amount of possible keys known? I know RSA is based on prime numbers and small numbers are to be rejected. I’m sure values above a certain amount of digits/bits are rejected because software may not be able to support those large values?

So: How many RSA keys before a collision? And if you would try to make many at the same time, would that give you a high chance of collision?

share|improve this question
up vote 22 down vote accepted

Collisions of RSA keys should never happen for realistic key sizes and good random number generators.

Assume a 1024 bit RSA key; the primes from which it has been derived are about 512 bit. If we assume every 500ths 512 bit number is a prime, and we assume the most significant bit of the 512 bit number is set, we still get about $2^{500}$ or $10^{150}$ different primes. If you apply the birthday problem to these numbers then you would expect RSA keys to have a prime in common about every $2^{250}$ or $10^{75}$ key generations. Identical RSA keys are even more rare.

This is large enough to never happen in practice. Unfortunately bad PRNGs which cause collisions do happen in practice, but you can't translate this into probabilities.

I've neglected a few small factors within the calculations that should not have a significant impact on the outcome.


GUID collisions are a bit more likely. V4 GUIDs are random, except for 6 reserved bits. So there are $2^{122}$ different V4 GUIDs. It's possible to get collisions if you create huge, but achievable amounts of GUIDs if you have a huge system dedicated to creating random GUIDs. The creation of a collision is very unlikely to happen in a normally sized system, where GUIDs are only a part of the overall security system.


It shouldn't matter in theory that you create many RSA key pairs at the same time, as long as you seed your PRNG with enough entropy. But if you seed badly - so that there isn't much entropy in addition to the system time - then random extraction at the same moment can be a problem. One of the most common randomness related questions in C# is why two instances of System.Random created in quick succession return the same sequence. If the random sequences used for RSA key pair creation are the same, then the RSA key pair will be identical as well.

share|improve this answer
    
Great answer. +1, except i'm new and can't. – Nick wheatley May 6 '12 at 13:21
1  
Also, long before accidental collisions were a problem, intentional collisions would be a problem. So it not only has to be absurdly unlikely to get a collision in normal use, a malicious attacker must be unable to create a collision when trying to do so. It's much, much easier to do something intentionally than by accident, so accidental collisions have to be not just impossible for practical purposes but impossible by many orders of magnitude. – David Schwartz May 6 '12 at 23:59
    
Hi Codes, I've edited your anwer to make it easier to read / understand. However, could you explain what you mean with "I neglected a few small factors, but that's pretty irrelevant". I presume you mean that you didn't completely describe all the steps performed for key pair generation. But "factors" is also a mathematical term... – Maarten Bodewes Jul 30 '14 at 21:06
2  
@owlstead I used factor to mean small constant multiplier. My computation is only a rough approximation, I didn't care if there are 10x more or less primes than what I wrote, so I included that statement to preempt nitpickers. For example I didn't use a precise form of the prime number theorem and I expect a typical RSA implementation to set the top two bits to 1, not just the top bit to ensure that their product has precisely 1024 bits. According to Wolfram Alpha there are $10^{151}$ primes suitable for RSA 1024. – CodesInChaos Aug 1 '14 at 8:33
    
Thanks (also for the excellent answer of course). I've changed it to factors within the calculations. And there is me nitpicking on the comment in the answer that was there to avoid nitpicking :) – Maarten Bodewes Aug 1 '14 at 10:47

Now the standard key size for RSA is recommended of 2048 bits. This is large enough to never having a collision in practice, where brute force is 2^{2048}. Even if we consider some attacks that allow to break it with half the key size or in birthday attack, this number is quite secure. However, larger the key size, more overhead and lower efficiency.

share|improve this answer
    
wat's the problem with this comment? I observed ppl look for score and comment accordingly. I'm new to this forum, it does not mean I do not have knowledge. Having more than 8+ yrs of research exp in CS with a PhD: security n crypto! – user24094 Feb 8 at 15:38
    
New people are good to have here. The negative score is because your answer has problems. Specifically, it has three problems: 1. it answers old question, which already has been addressed a long time ago; 2. it does not add useful information over the previously written excellent answer by CodesInChaos; 3. Your estimate of work in brute force attacking RSA is incorrect. It is true that current RSA is 2048, making the problem even smaller than according to computation with RSA 1024, but the computation by CodesInChaos clearly pointed out that it was not the problem back then either. – user4982 Feb 8 at 19:03
    
Thanks for your comment. I just pointed according to the current standard. If you think it is wrong to post, I will never post. – user24094 Feb 8 at 19:36
    
Of course it is good thing to answer. Just make sure the answer is correct. Compare your answer against, e.g., crypto.stackexchange.com/a/3044/4982 and notice that the brute force estimate 2^{2048} is incorrect and not very useful. BTW, to get started with the site see, e.g., crypto.stackexchange.com/tour. Also, if you want to give good and useful answers, the best place to start is New & Unanswered. [Disclaimer: I'm not affiliated with the site except I've answered a few questions now and then.] – user4982 Feb 8 at 19:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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