Checking the primality of numbers for use in RSA

Question

How can I check the primality of extremely large numbers such as those used in RSA, in Linux?

Answer 1

RSA is guaranteed to use prime numbers. In fact, if the numbers were not primes, RSA key operations would simply not work (with overwhelmingly high probability). However, the OpenSSL command line utility has the ability to check the primality of a number using Miller–Rabin primality testing, the standard test algorithm for checking large primes for use in cryptography:

OpenSSL> prime
No prime specified
options are
-hex           hex
-checks <n>    number of checks
-generate      generate prime
-bits <n>      number of bits
-safe          safe prime
error in prime
OpenSSL> prime -generate -bits 256
315016830147073940139675761214468273143
OpenSSL> prime 315016830147073940139675761214468273143
ECFE08DCA281B26A5EDDE8DF7D2A33F7 is prime
OpenSSL> prime 10000000000000
9184E72A000 is not prime

I believe the default number of checks is 64, but you can increase this to improve accuracy using the -checks option. Each check runs one Miller–Rabin test round which individually has a 75% chance of detecting that a composite number is indeed composite. Specifically, the chance of failing to identify a composite number as such is 4^-n, where n is the number of rounds used. With the default of 64 rounds, this is 4^-64, or 2^-128. To put that into perspective, if you put a composite number through 64 rounds of M-R primality testing, the chance that it is falsely labeled a prime is equivalent to the chance of correctly guessing a 128-bit encryption key on the first attempt.

If you are generating prime numbers at random, and not just testing untrusted numbers, the chance of incorrectly outputting a composite is significantly lower, with a lower bound for a k-bit prime being less than k²4^2-√k for any k larger than 1, and that's for a single round of testing! There are stronger bounds for larger primes, with a single 600-bit composite being incorrectly called prime with a chance of less than 2^-75 after a single round of testing. This was proven in a paper from 1993.

I explained more about primality testing in OpenSSL in another answer.