How many prime numbers are there (available for RSA encryption)?
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
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).