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. However, for Miller-Rabin, it has been proven that all composite numbers pass the test for at most 1/4 of the possible bases. So as long as you do sufficiently many independent tests (different bases, preferably chosen at random), I don't see how you could be fooled. http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html Doing the test for more than 1/4 of the bases (which would actually prove the number prime, although without a succinct witness) for large numbers is too expensive though. One algorithm that results in a polynomially verifiable witness is: Almost All Primes Can be Quickly Certified http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-stoc-gk.pdf Btw, I've been playing with prime proving in the past, and if you want to specify a format for prime proofs that OpenSSL would understand, I would consider supporting the same format in GnuTLS. Trusting that numbers are prime for cryptographic purposes should require a proof. There are several prime proof formats, but I can't tell if they are practical for this purpose. Regards, Simon --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
