How many RSA keys before a collision?

Question

I was wondering how many possibilities of private/public keys there are? If a million people for whatever reason tried to generate 5keys 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 (, guid version) and isn't meant to be used in that way.

Would RSA get collisions if many were generated in the same moments? 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?

How many RSA keys before a collision? and if you tried to make many in the same moment would that give you a high chance of collision?

Answer 1

For realistic key sizes and good random number generators collisions of RSA keys never happen.

For example assume a 1024 bit RSA key. The primes from which it comes 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. Applying the birthday problem to this, RSA keys which have a prime in common takes about $2^{250}$ or $10^{75}$ key generations. Identical RSA keys are even rarer.

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 neglected a few small factors, but that's pretty irrelevant

---

GUID collisions are a bit more likely. V4 GUIDs a 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. But it's very unlikely to happen in any normally sized system, where GUIDs are used only as a part.

---

The "at the same moment" part shouldn't matter in theory, since you should seed your PRNG with enough entropy. But if you seed badly, so that there isn't much entropy apart from the time(this is common in non cryptographic PRNGs), this 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.