25
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ It is very unlikely if everything is done properly (i.e., a good random number generator is used). Unfortunately, it has happened in practice. See the Debian OpenSSL RNG bug also this paper which details other issues found in practice. $\endgroup$
    – mikeazo
    Jul 29, 2014 at 15:08
  • $\begingroup$ Cryptography is all about attacks being "very unlikely". Consider AES128 - the attacker can guess correctly with probability $2^{-128}$ with a single guess. The probability of colliding RSA keys is much smaller than that if you use perfectly random primes. $\endgroup$ Jul 29, 2014 at 21:20
  • $\begingroup$ @CodesInChaos : $\;\;$ On the other hand, except for 3-prime 1024-bit RSA, I don't know of any way to give a mathematical proof that the "probability of colliding RSA keys is much smaller than that if you use" primes compatible at least one $\: e \in \{3,\hspace{-0.03 in}5,\hspace{-0.04 in}17\} \:$ or with $\: e = 257 \:$ specifically that are otherwise chosen perfectly at random. $\;\;\;\;\;$ $\endgroup$
    – user991
    Jul 29, 2014 at 21:52

4 Answers 4

30
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ May 6, 2012 at 23:59
0
$\begingroup$

if someone generates the same RSA key pair as someone else,

then ... someone will have the same RSA key pair as someone else.

when someone generates a key pair, how can he/she be sure that nobody has already generated this key pair?

The exact same ways he/she can generate any unique value.

Proof: Let the unique value be the key pair, or let the secret key be the empty string and let the public key be the unique value.

See GUID and UUID.

$\endgroup$
0
$\begingroup$

The answer to both questions lies in understanding entropy, and how entropy is gathered to create a key. (And, of course, how well the implementation does so without bugs.) Each operating system creates and maintains a pool of entropy from which the entropy – also known as “randomness” – is tapped in the process of generating the key. Also, to the extent that you request a larger number of key bits, the larger the primes used to compute the keys and which would need to be factored as an attack. That’s why it is best to stick to RSA with 2048 bits (versus DSA with its limit of 1024).

So, to more specifically answer your question: if you assume that no one has made a mistake in coding the algorithms, then the first item that makes it likely not to generate a duplicate key is that the OS is sampling lots of states of different parts of itself to create the random numbers (entropy) to create the key.

As far as how likely, look at uniqueness of the RSA public modulus. Does $2^{2026}$ look big?

And if you really want to understand, this set of lecture notes (PDF) explains how random numbers from the OS entropy pool are used to compute the RSA primes $p$ and $q$, which are part of the public/private keypair and which would need to be factored to attack the algorithm. Section 12.3.1 of the Purdue lectures explain “Computational Steps for Selecting the Primes $p$ and $q$ in RSA Cryptography”.

$\endgroup$
2
-1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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