# 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?

• +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. 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-4, 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). Mar 1 '12 at 13:48
• @Vilx Large primes are surprisingly common. You only need to look at a few hundred candidates. 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. Mar 1 '12 at 16:50
• The algorithm (as it stands now) generates primes with significantly biased distribution: primes with a long gap of composites just below them are significantly more likely than other primes. It is common to first choose a moderately large random secret $s$ and replace $p=p+2$ in step 3 by $p=p+2s$. It is enough that $s\approx\log_2(p)$ to mostly avoid that bias. In practice, $s$ is often the product of two much larger secret auxiliary prime $p_1$ and $p_2$ chosen such that we'll end with $p\equiv1\pmod{p_1}$ and $p\equiv-1\pmod{p_2}$.
– fgrieu
Jun 11 '15 at 8:23

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

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. Dec 11 '12 at 18:22
• @tylerl: On security.SE, I think ECDHE is more common than ECDHA. $\:$
– user991
Jun 30 '13 at 10:17
• @RickyDemer I think you might have attached this comment to the wrong answer (and wrong site). Jun 30 '13 at 19:58
• Well, sort of. $\:$ I don't have an account on $\:$ security.SE . $\;\;\;$
– user991
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. Jul 29 '13 at 20:12

You can use the next_prime function available in the GMP library, after generating a random large number. Here's the link : https://gmplib.org/manual/Number-Theoretic-Functions.html

• It's better not to do that. You will introduce a bias in the prime numbers that get selected. Jul 11 '15 at 19:54
• @SquareRootOfTwentyThree While it does introduce a bias toward primes with a large gap between it and the previous prime, the bias is extremely small and is not thought to be exploitable. May 26 '19 at 23:23
• @forest it can exploited via side channels May 28 '19 at 8:35
• @SquareRootOfTwentyThree Skimming the paper at least, it looks like that attack is applicable to both methods of prime generation. May 28 '19 at 9:04
• "The most rigorous [countermeasure is] [...] to generate each prime candidate independent from its predecessors (→Pseudoalgorithm 1)" May 28 '19 at 20:46

I have implemented Maurer's algorithm of generating random provable primes (see Menezes et al., Handbook of Applied Cryptography) in Python, which is, as comparison showed, only moderately slower than via usage of the test of Miller-Rabin (which can deliver only primes that are highly probably prime) for primes of sizes commonly employed for RSA currently in practice. Python is interpreted hence runs not very fast but that doesn't matter much in the present context for the common people who need only to generate a few large primes for RSA etc. My code PROVABLEPRIME is available at: http://s13.zetaboards.com/Crypto/topic/7234475/1/

• That's great. But... it doesn't really answer the question. :P Oct 17 '15 at 18:48
• @Vilx: You are right. I was rather directly commenting on the post of mikeazo above, which, I presume, somehow answered your OP. Oct 18 '15 at 10:03