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