In order to generate a 2048 bit RSA key pair, you need to generate two big prime numbers with 1024 bits length. As far as I know, OpenSSL chooses a random 1024 bit number and starts looking for a prime number around it. How can OpenSSL check if the number is prime or not so quickly?
Testing for primality is much easier than performing integer factorization.
There are several ways to test for primality, such as the deterministic Sieve of Eratosthenes and the probabilistic Miller–Rabin primality tests. OpenSSL uses several tests to check for primality. First they subject the number to the deterministic checks, attempting division of the candidate with a number of small primes, then a series of Miller–Rabin primality tests. The vast majority of candidate primes are discarded with the very first primality test. Any candidates which pass them are subject to further rounds of testing, each of which increase the certainty that it is a prime.
When using the Miller–Rabin tests, a composite number has a 75% chance of being detected as such at each round, so after a mere 64 rounds of testing, the probability that a composite number goes undetected is a staggering 2-128. In other words, the test has a 4-n chance of a false negative, where n is the number of testing rounds. There are also a number of much slower ways to test if a number is prime with complete certainty, such as the Agrawal–Kayal–Saxena primality test, but for cryptographic purposes, being really, really sure is sufficient, so they tend not to be used.
By default, OpenSSL tends to be extra paranoid and does some other tests, specifically for a safe prime. So when a prime, p, is found, it also checks if (p - 1) / 2 is prime. This is important for specific applications of primes such as Diffie–Hellman where safe primes prevent certain attacks.
This is possible at a high speed because verifying that an integer is a prime with an extremely low margin of error is significantly easier than factoring it, and because primes are not that uncommon (it is easy to find a large number of primes by incrementing a number and testing for primality). The Miller–Rabin primality test is very efficient. The test proves compositeness if xn - 1 ≢ 1 (mod n) (the Fermat test), and by testing whether or not x(n - 1) / 2e (mod n) is a nontrivial square root of 1 mod n where n is the integer being tested and x is a random witness satisfying the interval 1 < x < n.
The pseudocode implementation of the test taken from Wikipedia is:
Input: n > 3, an odd integer to be tested for primality; k, a parameter that determines the accuracy of the test Output: composite if n is composite, otherwise probably prime
write n − 1 as 2r·d with d odd by factoring powers of 2 from n − 1 WitnessLoop: repeat k times: pick random integer a in the range [2, n − 2] x ← ad mod n if x = 1 or x = n − 1 then continue WitnessLoop repeat r - 1 times: x ← x2 mod n if x = 1 then return composite if x = n − 1 then continue WitnessLoop return composite return probably prime