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?

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


Generate a random $512$ bit odd number, say $p$
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
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.
