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?

Cryptography libraries like PGP, GPG, Openssl generate the primes used for RSA encryption. They generally won't store the primes directly but compute N and Phi then forget them.
Openssl can generate a 2048 bit RSA key quite fast in just a few seconds on my laptop. On a Linux machine or Mac OS X you can run the command
openssl genrsa and inspect the output.
