> Ben Laurie <[EMAIL PROTECTED]> writes: > >> [EMAIL PROTECTED] wrote: >>> So Miller-Rabin is good for testing random candidates, but it is easy >>> to >>> maliciously construct an n that passes several rounds of >>> Miller-Rabin. >> >> Interesting! So how does one go about constructing such an n? > > I wonder if the original author didn't think of Carmichael numbers, > which are Fermat pseudoprime in every base. Some applications, > e.g. Libgcrypt used by GnuPG, use Fermat tests, so if you have control > of the random number generator, I believe you could make GnuPG believe > it has found a prime when it only found a Carmichael number.
Carmichael numbers with Fermat's test is a worst case example. A Carmichael number will pass Fermat's test for all bases. So if you give some one a Carmichael number (which is not a prime), and the person verifying the primality uses Fermat's test, you are sure to fool him. For Miller-Rabin, as you mentioned, it can be proven that in worst case, for a particular n, there is only 1/4 of bases for which the test will return "prime" when in fact the candidate is composite. But what I said is that you can "maliciously construct an n that passes several rounds of Miller-Rabin". In worst case, you can construct a prime that will pass several rounds of Miller-Rabin, for specific bases. Of course, if the person testing n uses random bases, the more tests the person does the greater the chance the person will catch the fact that n is in fact composite. But if you knew, in advance, the sequence of candidates that will be used, than it's a different game. The Miller true primality test I referred to in my initial post will always work assuming the Extended Riemann Hypothesis (ERH). In such a test, you start with base 2 and test, as long as the test passes increment by one, up to Poly(size(n)). I would have no problem believe ERH and using such an algorithm. In the worst case, if my code happened to generate a pseudo-prime, than I would have disproved the ERH hypothesis and could make allot of money out of that http://www.claymath.org/millennium/ If at the end all iterations passed, n is surely prime if ERH is true. The value of Poly(size(n)) that would need to be used for large n will be much smaller than 1/4*n, but (the big ick, considering all of the constants in the actual polynomial that needs to be considered) is still a very large number. In any case, go with Maurer's test, it really rocks and has been standardized. --Anton --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
