Will we run out of primes for RSA?

Make a big prime

Size256 bits512 bits1,024 bits (half of a 2,048-bit RSA key)1,536 bits

 Find a prime

What goes wrong when two keys share a prime

Make two toy keys that share a prime, and break them

Primes are made by your browser's secure random generator and never leave this page. The demo keys are toys.

Could two RSA keys ever share a prime by chance? No. A 2,048-bit RSA key is made from two primes of 1,024 bits each, and there are about 10³⁰⁵ primes of that size. The observable universe holds roughly 10⁸⁰ atoms, so primes of this size outnumber atoms by an absurd margin, and two people generating keys independently won't pick the same one unless their random number generators are broken. In 2012 researchers found that exactly that had happened to thousands of real servers.

How many primes are there of a given size?

The prime number theorem says the number of primes up to x is about x divided by the natural logarithm of x. Gauss and Legendre conjectured it around 1800, and Hadamard and de la Vallée Poussin proved it in 1896. Applied to 1,024-bit numbers it gives two results (scripts/examples/rsa-primes-count.mjs):

• The density. A random 1,024-bit number is prime with probability about 1 in 710 (that's ln 2¹⁰²⁴), or 1 in 355 if you only count odd numbers. So a program that tries random odd numbers needs about 355 of them on average.
• The count. The primes with exactly 1,024 bits number about 10³⁰⁵. For 512 bits it's about 10¹⁵¹, and for 1,536 bits about 10⁴⁵⁹.

Two different 1,024-bit primes make about 10⁶¹⁰ different 2,048-bit moduli. Even if every atom in the universe had its own private supply, each atom could hold 10²²⁵ different primes of this size. Running out isn't a concern, and neither is collision by chance. The estimate ignores a few details (the top two bits are fixed, and the theorem is an approximation), and none of them changes the order of magnitude.

How software really finds one

There's no list of primes and no formula for them. A program draws a random number of the right size, makes it odd, and tests it. Doing that naively would waste time, so there are three steps, and the tool above reports how many candidates went through each:

1. Pick a random odd candidate with the top bit set (and, for RSA, the second one too, so that p × q really has 2,048 bits), using a secure random generator. If the generator is predictable, so are the primes.
2. Screen it with small primes. Dividing by every prime below 2,000 rejects about 85% of the odd candidates in microseconds, since only 14.7% of odd numbers have no prime factor below 2,000. It's the same idea as the sieve.
3. Run Miller–Rabin on what remains. A composite number almost always fails on the first base, so the expensive test (a 1,024-bit modular exponentiation) is mostly spent proving that one number is composite. Only the final prime takes the full set of bases. See how the test works.

In a run of the generator over sixty 1,024-bit primes, the average was 413 candidates, 353 of them removed by the screen and 60 sent to Miller–Rabin. Node took about 0.2 seconds per prime on the machine that measured this, and your browser will be in the same range. Libraries such as OpenSSL work in outline the same way. (cipher.ink itself never generates a prime, because AES and PBKDF2 don't need one.)

When two keys share a prime

RSA's security rests on the difficulty of factoring n = p × q. But if two keys share the prime p and differ in the other one, then the greatest common divisor of the two moduli is p. Finding it is a division-style calculation that takes microseconds, however large the keys, and both keys are broken at once. The tool shows it with toy keys.

In 2012, Nadia Heninger, Zakir Durumeric, Eric Wustrow and J. Alex Halderman published Mining Your Ps and Qs, a survey of about 22 million hosts on the internet. They looked for shared factors among the RSA keys, and recovered the private keys of 0.50% of the TLS hosts they found, and 0.03% of the SSH hosts. The keys were mostly in headless and embedded devices, such as routers, that generate their keys at first boot, when the random number generator has had little time to collect unpredictable input. Their analysis traced part of the problem to a hole in the way the Linux generator was seeded early in boot. The pattern, as the paper explains it, fits a device that starts p with the same near-empty state as its twins and picks up a bit of entropy before q. The authors also recovered DSA private keys for 1.03% of the SSH hosts, from weak randomness in a different place. The paper won the conference's best paper award. The fix is in the operating system, not in the mathematics: seed the generator properly before generating a key (random numbers in the browser shows why this is the part cipher.ink takes most care over).

The result is a good reminder of what the 10³⁰⁵ primes mean. The number of primes protects you only if the choice among them is really random.

Common questions