[12207] in cryptography@c2.net mail archive
RE: Implementation guides for DH?
daemon@ATHENA.MIT.EDU (Zully Ramzan)
Thu Jan 2 14:46:42 2003
Date: Thu, 2 Jan 2003 11:23:21 -0800
From: "Zully Ramzan" <zramzan@ipdynamics.com>
To: "Bill Stewart" <bill.stewart@pobox.com>,
"Adam Shostack" <adam@homeport.org>
Cc: <cryptography@wasabisystems.com>
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 :)).=20
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...=20
Are you referring to performing Diffie-Hellman over some other group?
Or is there a connection that you know of and can elaborate on?=20
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@wasabisystems.com
