How does OpenSSL generate a big prime number so fast?

Question

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?

Answer 1

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 against small primes, then a series of probabilistic 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.

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). To test an integer n where n = 2^sd + 1 with s and d positive and d odd, the algorithm chooses a random witness a in the range [2, n - 1) and checks if a^d ≡ 1 (mod n) (the Fermat test) and a^2rd ≡ -1 (mod n) for some r in [0, s). If both of these congruence relations hold true, then n is probably prime.

Although it's often said that a composite number will survive a single Miller–Rabin test with no more than a 1/4 chance, the false positive rate for generated primes is actually significantly lower. A paper from 1993 proved that a k-bit composite will survive a single round of testing with no greater than a k²4^{2 - √k} chance for any k ≥ 2. Even stronger bounds exist for larger numbers, with 2^-75 for k = 600! There are also a number of much slower ways to test if a number is prime with complete certainty, such as ECPP, but for cryptographic purposes, multiple rounds of Miller–Rabin is plenty.

In some cases, OpenSSL does some other tests to look for a safe prime, so when 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, although it is not necessary for RSA because an algorithm called ECM negates the supposed benefits.

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

See this Crypto.SE answer on RSA key generation and the FIPS 186-4 standard, section 5.1.