Hi Bill -- > Stiglic's paper goes into a lot of explanation about > some issues of safe parameters, particularly recommendations > for sufficiently safe primes. Much of the discussion on the net > about prime safety for DH has been about whether safe primes > are necessary or not worth the bother, and at least with the > current methods for factoring, it's believed they aren't needed. > (One catch, of course, is that the best factoring method > 10 or 50 years from now may be affected by safe vs. unsafe primes.) > At least in the initial Photuris versions, there were some > standard choices of primes that everybody used, > so it made sense to pick Sophie-Germain primes anyway.
I know there has been some discussion on whether _strong_ primes are needed for _RSA_. The definition of a strong prime is a little more involved; c.f. the paper by Rivest and Silverman [http://eprint.iacr.org/2001/007/ and also available on Ron Rivest's web page]. I was unaware, though, that there is a debate regarding the use of safe primes for Diffie-Hellman. My impression is that the use of safe primes is generally accepted to be an important practice that thwarts various attempts to compute a discrete log (e.g. Pohlig-Hellman); also enough safe primes and generators are published -- one may utilize them in a protocol (assuming the people who published the list are trusted not to have deliberately chosen prime groups for which computing a discrete log is easier :)). I'm also not sure how the choice of primes for Diffie-Hellman relates to the complexity of factoring as you mentioned in your post. As far as I know, no one (in the open community at least) has discovered a meaningful reduction in a standard model between the Diffie-Hellman problem over a prime group and Factoring (nor has anyone proven that such reductions cannot exist). The closest thing I can think of is trying to come up with the factorization of p-1 as you might want to do in the Pohlig-Hellman algorithm -- but in that case, the complexity would be prohibitive if p-1 had any large prime factors... Are you referring to performing Diffie-Hellman over some other group? Or is there a connection that you know of and can elaborate on? Best Regards, Zully ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Zulfikar Ramzan IP Dynamics, Inc. http://www.ipdynamics.com Secure, Scalable Virtual Community Networks --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
