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 [EMAIL PROTECTED]
