3
$\begingroup$

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!

Improve this question
$\endgroup$
6
  • 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 ♦
    Commented Mar 5, 2012 at 12:19
  • $\begingroup$ There was a similar question on here a while back. See, crypto.stackexchange.com/q/802/706 $\endgroup$
    – mikeazo
    Commented Mar 5, 2012 at 12:32
  • $\begingroup$ Thank you for your responses! I think the link answered my question. $\endgroup$
    – MartinSuecia
    Commented Mar 5, 2012 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
    Commented Mar 5, 2012 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 ♦
    Commented Mar 5, 2012 at 20:30

0

Reset to default

Browse other questions tagged or ask your own question.