37

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?

0

1 Answer 1

47

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 = 2sd + 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 ad ≡ 1 (mod n) (the Fermat test) and a2rd ≡ -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 k242 - √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.

10
  • 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?
    – Soron
    Dec 31, 2017 at 9:17
  • 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. Dec 31, 2017 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 . Jan 1, 2018 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, 2019 at 5:25
  • 1
    Beware naive attempts at randomized primality tests like Miller–Rabin tests. It is critical that the witnesses be chosen unpredictably and independently; otherwise an adversary can fool the test into falsely reporting that maliciously chosen composites are prime. Nov 10, 2019 at 4:17

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.