Re: Factorisation and Discrete Logs

[Brian A. LaMacchia <bal@martigny.ai.mit.edu>]

   From: mpd@netcom.com (Mike Duvos)
   Date: Wed, 18 Jan 1995 20:40:46 -0800 (PST)
   X-Mailer: ELM [version 2.4 PL23]
   Mime-Version: 1.0
   Content-Type: text/plain; charset=US-ASCII
   Content-Transfer-Encoding: 7bit
   Content-Length: 1017      
   Sender: owner-cypherpunks@toad.com
   Precedence: bulk

   Derek Atkins <warlord@MIT.EDU> writes:

    > You are right...  Given talks Ive had with Brian LaMacchia,
    > who broke a version of "Secure SunRPC" (a 192-bit prime), he
    > claims that the difficulty is reducing a D-L problem is
    > about the same amount of computation to factorize an RSA
    > modulus of approximately the same size..

Just to clarify, the estimate I give people is that computing discrete
logs in a prime field GF(p) is about as hard as factoring a number 10
digits (33 bits) longer than p.  This estimate is based on the empirical
data Andrew Odlyzko and I collected for 192-bit and 224-bit moduli.  To
the best of my knowledge no one has attempted a discrete log modulus
larger than 224 bits.  (There just haven't been any juicy targets
recently to attack...)

   Although DH and RSA are believed to be of approximately equal
   difficulty given the same number of bits, DH is additionally
   vulnerable because system designers usually publish an "official"
   modulus and primitive root for everyone to use, whereas in RSA,
   everyone has their own key.

This is not a property of D-H key exchange, per se, but of the actual
uses to which people have put the D-H protocol.  Two parties wishing to
generate a shared secret could certainly produce a D-H modulus and
generator on the fly for one-time use, but that takes some time.  The
fact that the discrete log problem is brittle simply means that you have
to choose your modulus taking a few more things into account when using
the D-H protocol for a particular application.

   To mount an attack on PGP, for instance, you must factor a key
   for each person whose privacy you wish to compromise.  Breaking
   Sun's published 192 bit DH modulus instantly broke SunRPC on all
   machines using the protocol.  The latter was a lot less work than 
   the former.

Breaking SunRPC was a lot less work than breaking a (typical) PGP key
simply because the SunRPC modulus was so small.  If I'm given a choice
of factoring 100 different 512-bit PGP keys (for 100 different users) or
breaking a 768-bit D-H modulus that compromises all 100 users
simultaneously, I'll take the factoring problems.

					--bal