34

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?

40

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

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

  • 3
    I'm trying to think of how you would use the Sieve of Eratosthenes to find large prime numbers, based on the linked Wikipedia article, and I'm not sure how you would actually use it effectively for large primes. Do you have a better link describing usage for finding large primes? Or, are there other deterministic tests that are more-commonly used? – Ethan Kaminski Dec 31 '17 at 9:17
  • @EthanKaminski Might not be used by OpenSSL, but I know OpenSSH uses it, see moduli(5). It looked like OpenSSL used it because the of the "fast test" in the source, but I just skimmed it. Though on second thought, BN_is_prime_fasttest_ex() seems to just do a trial division of a number of pre-computed small primes. – forest Dec 31 '17 at 11:33
  • 7
    @EthanKaminski: The Sieve of Eratosthenes might be used to generate the small primes for the first test. It surely isn't used to generate every prime until 2**1024. – Eric Duminil Dec 31 '17 at 11:51
  • 1
    BN_is_prime_fasttest_ex can first try the fixed list of small primes, but this is skipped if the caller says so and BN_generate_prime_ex used for RSA does because probable_prime has already done the sieving using a faster incremental method; then fasttest does a loop for(i=0;i<checks;i++) ... BN_pseudo_rand(check) ... witness(check,..,A1_odd,k,...) ... where each call of witness does one M-R trial with random check and A1_odd,k the decomposition of candidate-1 to odd and power-of-two as you explained. But your wp quote lost the superscripting for 2^s a^d x^2 . – dave_thompson_085 Jan 1 '18 at 1:19
  • 1
    @Jacco When the probability is as low as 2^-128, you really don't have to worry about it. After all, you're just as likely to guess a 128-bit key on the first try. – forest Feb 8 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.