Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 5 down vote accepted

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).

share|improve this answer
    
Thanks! I just checked openssl source, and it seems to generate random number for each round, as you said. –  catpnosis Jan 8 at 7:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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