[18329] in cryptography@c2.net mail archive
Re: Fwd: Tor security advisory: DH handshake flaw
daemon@ATHENA.MIT.EDU (astiglic@okiok.com)
Mon Aug 29 12:08:53 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <ilu64tpm7f1.fsf@latte.josefsson.org>
Date: Mon, 29 Aug 2005 11:57:47 -0400 (EDT)
From: astiglic@okiok.com
To: "Simon Josefsson" <jas@extundo.com>
Cc: "Ben Laurie" <ben@algroup.co.uk>, cryptography@metzdowd.com,
astiglic@okiok.com
> Ben Laurie <ben@algroup.co.uk> writes:
>
>> astiglic@okiok.com 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 majordomo@metzdowd.com
