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