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?

Answer 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).

Answer 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.