Fwd: Tor security advisory: DH handshake flaw

[Hal Finney]

Ben Laurie writes:
> Apologies, slightly at cross-purposes here. For a start, Sophie Germain 
> primes are needed for D-H (or rather, safe primes), and secondly, I was 
> talking about proving arbitrary primes, rather than constructing 
> provable primes.

Dan Bernstein has lots of good information on the state of the art in
general primality (and compositeness) proving.

http://cr.yp.to/primetests.html points to his recent survey paper and has
a table of the various algorithms.  Interestingly there are considerable
tradeoffs between proving time and verification time.  There are some
methods that create "instant" proofs but then take a long time to verify.

http://cr.yp.to/ntheory.html has some of Dan's own work, including an
algorithm which creates a certificate in time quadratic in length, with
verification costing time proportional to the 4th power of the length.

He suggests that at this point the best practical algorithm is based on
elliptic curves, which is conjectured to have running time proportional
to the 4th power of length for finding proofs and to the 3rd power for
verifying them.  I don't know what the actual numbers are for prime sizes
of interest (presumably 1K-8K bits or so).  References are available
from his papers.

Several programs to implement ECPP can be found from
http://primes.utm.edu/links/programs/seeking_large_primes/.  I don't
know about source code however.  It might be interesting to run these
over some of the Oakley primes and publish the certs - I vaguely recall
seeing something like that in an RFC.

Hal

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com