Simon Josefsson wrote:
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.
Surely the attack of interest is where the attacker provides the prime -
no control of RNGs is required for this.
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
This appears to be a probabilistic certificate, which strikes me as
rather pointless.
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.
I'd be interested in doing this, but first we need to choose a proving
method!
Cheers,
Ben.
--
http://www.apache-ssl.org/ben.html http://www.thebunker.net/
"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
