Fwd: Tor security advisory: DH handshake flaw
Hal Finney
hal at finney.org
Sun Aug 21 15:16:50 EDT 2005
Ben Laurie writes:
> Related to this is a project I keep considering and never quite getting
> around to is to include a prime proof verifier in OpenSSL. It would be
> pretty cool to have modes which only work when all relevant primes come
> with proofs.
>
> I've looked into this a few times, but have always ended up at a slight
> brick wall: I'd like to use proofs for which there's efficient (yes, I
> know "efficient" means "only takes a few months to run") code to produce
> the proofs, as well as (obviously) efficient (where efficient means
> "really fast") verifiers. This is, of course, so new proven primes can
> be produced without having to wait for someone with proprietary code to
> feel so inclined.
If you look at Wei Dai's Crypto++ library, www.cryptopp.com, you
will see two implementations of provable prime generators, called
MihailescuProvablePrime and MaurerProvablePrime. The first in particular
was quite fast and took only about 10 seconds to generate a 1024 bit
prime on my laptop (1GHz Mac G4). However 2048 bit primes took more like
6 to 8 minutes, so it does slow down quite a bit for larger primes.
These functions don't output the "certificate" that proves it to be prime,
but they have a recursive structure and if you preserve the intermediate
values then there is a fast way of verifying the resulting primes.
The Mihailescu version is from his Crypto 94 paper which is available
from his web site, http://www-math.uni-paderborn.de/~preda/ and also
discusses verification. I googled and found a someone more recent paper
by Mihailescu,
http://grouper.ieee.org/groups/1363/P1363a/contributions/mihailescu.pdf.
> Oh, BTW, bonus points if the prover can be run on large numbers of
> processors in parallel. Even more points if communication between the
> CPUs are low bandwidth.
Unless you're looking for primes with a special format, like Sophie
Germain primes or ones with lots of 1's up front and/or in the back, or
primes considerably larger than 2048 bits, current methods should be fast
enough for most applications even on sequential processors.
Hal Finney
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list