How are primes generated for RSA?

As I understand it, the RSA algorithm is based on finding two large primes (p and q) and multiplying them. The security aspect is based on the fact that it's difficult to factor it back into p and q. Now, since RSA keys are so large (often 1024 bits and above), the primes have to be at least half that (at least 512 bits then). Such large primes would be difficult to generate (you'd have to check many, many numbers and try to factor each of them), so I understand that the typical approach is to use pre-generated lists of large primes.

But doesn't that make the key very easy to crack? Even if the list container 1,000,000 primes (which I find unlikely), checking all the combinations would only take a couple of hours on a typical desktop computer.

Which part have I misunderstood?

-

migrated from security.stackexchange.comMar 2 '12 at 12:47

This question came from our site for Information security professionals.

+1. had the same mental barrier. factoring out two primes from the product is very hard, but finding large primes is quite easy. it's not that intuitive though. –  Yoav Aner Mar 1 '12 at 14:23
Hi @Vilx, while this question is on topic here, it still would be even more at home at our brother site - Cryptography. –  AviD Mar 2 '12 at 12:46
For more background about why using lists of primes would be bad see this blogentry and the paper "Ron was wrong, Whit is right". How big primes can be found is described in the answers to this question. –  Someone Mar 2 '12 at 14:59

You don't use a pre-generated list of primes. That would make it easy to crack as you note. The algorithm you want to use would be something like this (see note 4.51 in HAC, see also an answer on crypto.SE):

1. Generate a random $512$ bit odd number, say $p$
2. Test to see if $p$ is prime; if it is, return $p$; this is expected to occur after testing about $Log(p)/2 \sim 177$ candidates
3. Otherwise set $p = p+2$, goto 2

There are other methods to generate primes (e.g., do step 1, if step 2 fails goto step 1). The method I outlined is what OpenSSL uses though.

For an official, public standard on RSA key generation, see FIPS 186-3, section 5.1 and Appendix B.3.1.

-
And it doesn't take 10 weeks to produce a prime? At those magnitudes I'd expect primes to be lightyears apart! Also - how do you test for primality? Last I heard brute-force was the only actual way (with a few optimizations, but still), which means something on the order of O(2^512). –  Vilx- Mar 1 '12 at 13:29
@Vilx-, remember, OpenSSL does exactly what I described, so it must be quick. There are plenty of probabilistic primality tests (see the HAC doc I linked to). One is Miller-Rabin, which is very quick. With those tests, you can get arbitrarily close to a probability of 1 that p is prime. Finally, the distribution of primes is dense enough to make the described algorithm fairly quick (see en.wikipedia.org/wiki/Prime_number_theorem). –  mikeazo Mar 1 '12 at 13:48
Oh, nice. I didn't know that. Thanks! :) –  Vilx- Mar 1 '12 at 13:53
@Vilx Large primes are surprisingly common. You only need to look at a few hundred candidates. –  CodesInChaos Mar 1 '12 at 14:15
@Vilx- According to the prime number theorem, the distance between prime numbers near x is approximately ln(x). For a 1024-bit number, this is 1024*ln(2), or approximately 710. Thus, checking every odd number near some large 1024-bit number, we'd expect to have to check about 355 numbers to find a prime. For a computer, this is practically nothing. –  BlueRaja - Danny Pflughoeft Mar 1 '12 at 16:50

The key is that the test used by crypto libraries to determine whether a number is prime is probabilistic. That is, if the test uses a randomly-chosen value (the "witness") which serves as the basis for the test. If the test passes, then the number is probably prime, but possibly not. We can repeat the same test with a new "witness", and if the test passes again then we have increased our certainty. We can continue to re-test as many times as we want until we've reached the level of certainty that we need.

It is possible, therefore, that the primes used are not actually prime. But it's unlikely enough that it doesn't significantly affect the security of the key.

-
Fast probabilistic testing is only half the answer, though. It's convenient primes are so dense at density $\frac{1}{\ln{n}}$, otherwise it wouldn't matter that we can check for primality quickly because we'd never actually pick a prime to check and validate. –  Thomas Dec 11 '12 at 18:22
@tylerl: On security.SE, I think ECDHE is more common than ECDHA. $\:$ –  Ricky Demer Jun 30 '13 at 10:17
@RickyDemer I think you might have attached this comment to the wrong answer (and wrong site). –  tylerl Jun 30 '13 at 19:58
Well, sort of. $\:$ I don't have an account on $\:$ security.SE . $\;\;\;$ –  Ricky Demer Jun 30 '13 at 20:51
Actually, there are deterministic ways to find large primes that are about as fast as the probabilistic tests. Hence, the fact that probablistic methods are generally used isn't that relevant to why RSA key generate is the speed that it is. –  poncho Jul 29 '13 at 20:12

"I understand that the typical approach is to use pre-generated lists of large primes."

This is what I also thought. But I had not considered how many primes we might choose from. As it turns out you choose from ~2.8x10^147 primes with a 1024 bit RSA key and from about ~7.0x10^613 with a 4096 bit RSA key. Then you have up to 4.9x10^1227 possible pairs of primes. This amount is enormous, you shouldn't be able to just skim through a list then.

The original answer is at Stackoverflow from David Robinson:

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

-