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
participants (4)
-
Brian A. LaMacchia -
Derek Atkins -
dwa＠mirage.svl.trw.com -
mpd＠netcom.com