# Who generates the prime numbers for encryption?

I was talking to a friend of mine yesterday about encryption. I was explaining RSA and how prime numbers are used - the product $N = pq$ is known to the public and used to encrypt, but to decrypt you need to know the primes $p$ and $q$ which you keep to yourself. The factorization of $N$ is the hard part, and that's why RSA is safe.

Then I was asked: Who actually calculates these primes, and how? They're huge, so can you do it on just a normal computer (in reasonable time)? And if not, and encryption software gets the primes from somewhere else, this third party would have a list of primes (however large) to try to factor $N$ with. Using it would be considerably easier than just brute forcing, trying to divide with every prime number up to $\sqrt{N}$. If they (or someone else) has the list, encryption isn't really safe.

So, how is it actually done?

• The primes are generated locally, on your (or whoever's) computer. Finding large primes and testing that they really are prime can be done in reasonable time by normal computers nowadays (although the test might be probabilistic, but with an error probability below the probability of a hardware fault). – Daniel Fischer Feb 26 '14 at 21:34
• This question was raised and answered well over at Crypto SE. – anon Feb 27 '14 at 21:15
• If somebody else generates it, you have to worry about who else they tell. – Ross Millikan Feb 27 '14 at 21:30

1024-bit RSA requires two 512-bit primes. On my (old) machine it takes about 34 milliseconds to generate a 512-bit prime (so generating the whole key would take about 0.07 seconds). That's about 10 milliseconds to find the prime and 25 to verify it to high certainty. If I was willing to live with 'only' one mistake in $10^{100}$ I could verify a prime in a third the time. If I wanted to instead prove that it was a prime, it would take about 1.6 seconds... but that's overkill for reasonable purposes. (Better to move to a higher bit level with less certainty.)