It is well known that it's possible to fool Fermat test with Carmichael numbers. But, is it possible to deliberately fool many-rounded Miller-Rabin test by constructing some special number without using brute forcing strategy? I know that one round of Miller-Rabin distinguish with probability 25% that number is prime, but for many rounds brute force will become infeasible.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
In fact even brute force does not work, unless you know what random numbers the Miller-Rabin test will use to test the numbers, because in case of each possible non-prime number, some Miller-Rabin test input will reveal it is composite.
FIPS 186-4 C.3 contains recommended Miller-Rabin number of rounds to use to test the numbers. Those amounts of Miller-Rabin tests are expected to catch composite numbers with overwhelmingly large probability. The document contains useful information about Miller-Rabin and how test is supposed to (probabilistically) protect from this attack (fooling it with composite numbers).
-
$\begingroup$ Thanks! I just checked openssl source, and it seems to generate random number for each round, as you said. $\endgroup$ Commented Jan 8, 2014 at 7:12
-
$\begingroup$ Actually, the tests in FIPS 186-4 are tuned to be appropriate for random numbers (or ones generated from a benign source) - they don't assume that an adversary is selecting the numbers in an attempt to fool it. $\endgroup$– ponchoCommented Dec 10, 2019 at 15:46
-
$\begingroup$ run a sprp test base 2, and the lucas test as mentioned in the standard FIPS186-4. There are strong chances that NO pseudoprimes to one of the test will pass the other test. This is the best defense against adversarial conditions. And then, run the MR tests exactly as described by the standard, because the standard is the standard. This is the best defense against known weaknesses. $\endgroup$– PierreCommented Sep 6 at 17:56
$\begingroup$
$\endgroup$
If you test really random numbers then the Miller-Rabin test works as well as described by user4982. But if someone evil is giving you the "prime numbers" to test, they can be composite and passing OpenSSL's primality test with probability 1/16 despite provable failure rate of $2^{-80}$ (at least that's the state of the art in 2018). This is no contradiction to the claimed security by OpenSSL, as the error bound $2^{-80}$ is for random prime candidates (average case), not for particularly bad prime candidates (worst case).
