Implementation guides for DH?

[Zully Ramzan]

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 majordomo at wasabisystems.com