Hal Finney wrote:
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.
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.
Incidentally, I presume that using constructed primes rather narrows the
search space if they need to be secret (though I believe that proving
arbitrary primes is rather too painful for routine use in this case, sadly).
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]
