1

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

closed as off-topic by Steffen Ullrich, multithr3at3d, CaffeineAddiction, ThoriumBR, Xander Jun 18 '18 at 21:26

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about Information security within the scope defined in the help center." – multithr3at3d, CaffeineAddiction, ThoriumBR, Xander
If this question can be reworded to fit the rules in the help center, please edit the question.

2

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.

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

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