From: dwa@mirage.svl.trw.com (Dana Albrecht)
Date: Wed, 18 Jan 95 19:39:07 PST
To: cypherpunks@toad.com
Subject: Factorisation and Discrete Logs (was Re: EE Times on PRZ)
Message-ID: <9501190339.AA20854@mirage.svl.trw.com>
MIME-Version: 1.0
Content-Type: text/plain


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