Possible Duplicate:
Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?

I'm wondering if breaking the DLP, that is the basis for ElGamal and DSA, would automatically break RSA. The way I see it, RSA is based on the following three assumtpions, please correct me if I'm wrong.

  1. The hardness of integer factorization. This is obvious, if this would be possible, we could find p and q from N, calculate phi(N) = (p - 1)(q - 1) and then find d from e in polynomial time using the Extended Euclidian alg.

  2. The hardness of finding e'th rooths mod N. An encrypted message is c = m^e mod N, so knowing c and e (which an attacker does), he could find m by calculating the e'th root mod N.

  3. The hardness of finding The Discrete Logarithm mod N (DLP). After encrypting a message, the attacker knows m and c, and since this relation hold: m = c^d mod N, a solution to the discrete logarithm problem would find d.

When reading different sources, it seems to be the case that solving DLP does not in general break RSA. How is this possible? Does it have to do with the fact that the DLP over a prime order cyclic group (that ElGamal and DSA uses), where all integers less than the group order are members of the set, are concidered to be much easier to solve than over a non-prime group (that (Z_pq, *) is)?

Is it perhaps the case that breaking either 2 or 3 automatically gives a solution to 1 (there already exists polynomial time reduction algorithms), such that the statement "RSA is secure as long as integer factorization is hard" is indeed true.

Thank you in advance for clarifying this!

  • 2
    $\begingroup$ In a cryptographic context, the DLP is usually stated modulus a known prime or on an elliptic curve, which is quite different from the DLP in your variant 3, which is modulus a known composite of unknown factorization. I think it is correct that breaking the DLP in any arbitrary group would also break RSA and your other problems 1 and 2. $\endgroup$ – fgrieu Mar 5 '12 at 12:19
  • $\begingroup$ There was a similar question on here a while back. See, crypto.stackexchange.com/q/802/706 $\endgroup$ – mikeazo Mar 5 '12 at 12:32
  • $\begingroup$ Thank you for your responses! I think the link answered my question. $\endgroup$ – MartinSuecia Mar 5 '12 at 14:05
  • $\begingroup$ @fgrieu: If I understand right, the (non-zero) numbers mod $N$ with composite $N$ don't form a muliplicative group (since there are zero-divisors), thus DLP mod composite is not a case of DLP in a group. (I'm not sure if it can be traced back to such a DLP in some group, though.) $\endgroup$ – Paŭlo Ebermann Mar 5 '12 at 18:19
  • 1
    $\begingroup$ @PaŭloEbermann: Indeed, the set $\{j, 0<j<N\}$ is not a group under multiplication $\bmod N$ when $N$ is composite. But its subset $\{j, 0<j<N, GCD(j,N)=1\}$ is, and computation in this group is easy (including inversion) without knowledge of the factorization of $N$. Solving the DLP in this group without knowledge of the factorization of $N$ would break RSA, allow factorization of $N$, etc.. I thus stand by my original comment at least if "breaking the DLP in any arbitrary group" is taken as meaning "solving the DLP in a group given the group operation and inversion in this group". $\endgroup$ – fgrieu Mar 5 '12 at 20:30