Factorisation and Discrete Logs (was Re: EE Times on PRZ)

strick wrote:
> 
> DH uses "discrete log" as the hard problem, and very straightforward
> mathematics.
> 
> RSA uses "factoring" as the hard problem, and a very clever back door.
> 
> How do you decide if one is based on the other?
> 
> # public-key technology with Diffie-Hellman public-key in particular, which
> # (as I understand it) is not particularly secure.
> 
> It's still up in the air, isn't it, whether the discrete log or 
> factoring is the harder to crack.   My intuition is they're the
> same hard.
> 
> I know of no problem with DH that RSA doesn't have similar problems.
> 
> 			strick

 
It seems to me that factoring a large number is no harder than finding
a discrete logarithm.

Assume, for the moment, that an efficient method of computing discrete
logs has been discovered, rendering systems like Diffie-Hellman key
exchange unusuable.

I contend that RSA is now equally unusable.  The following variant of
the Pollard p-1 method should provide an efficient factorisation method
for an RSA modulus, say N.

Choose, at random, "a" such that gcd(a,N) = 1.

Compute x such that:

     a^x = 1 (mod N)          [ Discrete log time! ]

Partially factor x; say x = f  *  f  *  f  ...   where f  is not necessarily
prime.                       1     2     3              n

Note that it is usually easy to partially factor a "random" large integer.
Simply using trial division up to some limit; or, at worst, pollard rho
or pollard p-1 (on x) should suffice.  If you're truly unlucky, pick
another value for a.

Compute:

     M = a^(10000! * f) (mod N)

Where f is some partial factor of x.

gcd(M-1,N) should yield a non-trivial factor of N.  If it doesn't,
another choice of f and/or a should work.

I'm by no means a professional mathematician, but it seems that this
scheme should work.

Comments, anyone?


Dana W. Albrecht
dwa@mirage.svl.trw.com

> Comments, anyone?

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..

So, within napkin-computation, you are correct.

-derek

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..

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.

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.

-- 
     Mike Duvos         $    PGP 2.6 Public Key available     $
     mpd@netcom.com     $    via Finger.                      $

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