How many prime numbers are there (available for RSA encryption)?

Question

Am I mistaken in thinking that the security of RSA encryption, in general, is limited by the amount of known prime numbers?

To crack (or create) a private key, one has to combine the right pair of prime numbers.

Is it impossible to publish a list of all the prime numbers in the range used by RSA? Or is that list sufficiently large to make this brute force attack unlikely? Wouldn't there be "commonly used" prime numbers?

Solution 1

RSA doesn't pick from a list of known primes: it generates a new very large number, then applies an algorithm to find a nearby number that is almost certainly prime. See this useful description of large prime generation):

The standard way to generate big prime numbers is to take a preselected random number of the desired length, apply a Fermat test (best with the base 2 as it can be optimized for speed) and then to apply a certain number of Miller-Rabin tests (depending on the length and the allowed error rate like 2−100) to get a number which is very probably a prime number.

(You might ask why, in that case, we're not using this approach when we try and find larger and larger primes. The answer is that the largest known prime has over 17 million digits- far beyond even the very large numbers typically used in cryptography).

As for whether collisions are possible- modern key sizes (depending on your desired security) range from 1024 to 4096, which means the prime numbers range from 512 to 2048 bits. That means that your prime numbers are on the order of 2^512: over 150 digits long.

We can very roughly estimate the density of primes using 1 / ln(n) (see here). That means that among these 10^150 numbers, there are approximately 10^150/ln(10^150) primes, which works out to 2.8x10^147 primes to choose from- certainly more than you could fit into any list!!

So yes- the number of primes in that range is staggeringly enormous, and collisions are effectively impossible. (Even if you generated a trillion possible prime numbers, forming a septillion combinations, the chance of any two of them being the same prime number would be 10^-123).

Solution 2

As new research comes out the answer to your question becomes more interesting. In a recent paper "Imperfect Forward Secrecy:How Diffie-Hellman Fails in Practice" by David Adrian et all found @ https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf accessed on 10/16/2015 the researchers show that although there probably are a sufficient number of prime numbers available to RSA's 1024 bit key set there are groups of keys inside the whole set that are more likely to be used because of implementation.

We estimate that even in the 1024-bit case, the computations are plausible given nation-state resources. A small number of fixed or standardized groups are used by millions of servers; performing precomputation for a single 1024-bit group would allow passive eavesdropping on 18% of popular HTTPS sites, and a second group would allow decryption of traffic to 66% of IPsec VPNs and 26% of SSH servers. A close reading of published NSA leaks shows that the agency’s attacks on VPNs are consistent with having achieved such a break. We conclude that moving to stronger key exchange methods should be a priority for the Internet community.

The research also shows a flaw in TLS that could allow a man-in-middle attacker to downgrade the encryption to 512 bit.

So in answer to your question there are probably a sufficient quantity of prime numbers in RSA encryption on paper but in practice there is a security issue if your hiding from a nation state.

Comments

[pinhead]

And there are enough prime numbers that there have never been any collisions? I mean, they have to be "small" enough to fit in RAM or some kind of limit like that?

[David Robinson]

@pinhead: See my latest update. The prime numbers of this size can fit in RAM incredibly easily- they range from 1-4 kb. But the list of possible primes (estimated above to be about 10^147) wouldn't fit even if you used every single atom in the universe to store a different bit.

[Nick Johnson]

"which means the prime numbers range from 512 to 2048" - I think you mean 512 to 2048 bits.

[Hans Dampf]

Very good answer. The problem is that it assumes a perfect PRNG to generate this amount of unique numbers to derive the primes from. In reality PRNG are often not as good as they should be, due to lack of entropy or due to buggy implementations. Because RSA public keys contain the date of generation you know already a part of the entropy which further can help to restrict the range of possible random numbers. Here is a good example showing that there may be less possible RSA keys than one might expect: lwn.net/Articles/482089

[Hans Dampf]

Many public keys contain version information, so that you know what software and version was use to generate the key. If this version had known vulnerbilities in key generation this can further help you in cracking it.

[Dessa Simpson]

@DavidRobinson When you say 1/ln(n), do you mean n/ln(n)? Because that is what you plug in with 10^150.

[David Robinson]

@DuncanXSimpson 1/ln(n) is the density (thus n/ln(n) is the number)

[doubleOrt]

2^512 is 134078079299425970995740249982058461274793658205923933777235‌​61443721764030073546‌​97680187429816690342‌​76900318581864860508‌​53753882811946569946‌​433649006084096, how do you get 150 from that result ?

[David Robinson]

@Taurus 10^150, not 150

[Nic]

Fun math fact: The number of bits required to represent the current largest prime we know is roughly 56,000,000. (log2(10^(17000000)) ~= 5.6 * 10^7)

[SpelingError]

The prime number function π(x), which is approximated by x/ln(x) covers all primes less than or equal to x. However, for RSA encryption, you are only using 1024 bit primes, and not using primes smaller than that. So technically, to estimate the size of a prime library of 1024 bits, you have to subtract all of the smaller primes less than 1024 bits. (Granted, I believe the result is still the same order of magnitude)

[SomeCallMeTim]

This post is a bit older, but researchers in 2012 found public certificates that shared primes. Some 0.2% of the 6.2M they tested were easily factored/broken in less than a day of CPU time. So apparently the random number generation isn't sufficiently random? Maybe these were the result of that Debian bug? eprint.iacr.org/2012/064.pdf and the algorithm explained: algorithmsoup.wordpress.com/2019/01/15/…