2
$\begingroup$

I'm trying to understand why the RSA problem is not related to the Discrete Log problem, and how breaking the Discrete Log problem does not directly compromise RSA.

I will explain my reasoning of why it seems to me that they are the same in hope that someone will find the flaw in my reasoning and correct me.

If you don't take into account how you generate the public and private keys and just assume they exist, we could minimize the RSA problem to just modular exponentiation in this way:

  • $M$: Plain text
  • $C$: cipher text
  • $E$: some number

  • $D$: some other number

  • This is easy (encrypt): $M^E \bmod N = {?}$

  • This is hard (decrypt): ${?}^E \bmod N = C$

Now, according to this khan academy video, ${?}^E \bmod N = C$ is equivalent to $C^{D} \bmod N = {?}$ for some unknown $D$, this will act as our private key.

Now my question is: If I can identify if I have decrypted $M$, by some file header for example. isn't finding $D$ for $C^{D} \bmod N = M$ the Discrete Log problem? Given this khan academy video about the discrete log problem, it would appear it is.

Improve this question
$\endgroup$
2
  • $\begingroup$ why was $\equiv$ replaced with $=$ on the edit? I thought that $\equiv$ was the correct symbol for this. $\endgroup$
    – Joaquin Brandan
    Mar 8, 2018 at 0:27
  • 2
    $\begingroup$ $a \equiv b \pmod n$ and $a\bmod n = b$ are different things. $\endgroup$
    – fkraiem
    Mar 8, 2018 at 0:35

1 Answer 1

Reset to default
2
$\begingroup$

If you could take discrete logarithms modulo a composite number of unknown factorization, you could recover the decryption exponent.

Compute $c = m^e \bmod N$ for some $m < N$. We know that $c^d \equiv m \bmod N$.

You have $m, c, N$, and knowledge that $c^d \equiv m \bmod N$. Recovery of $d$ is the discrete logarithm problem.

The factorization of $N$ being unknown will probably work against you when attempting to compute the discrete logarithm. Depending on the hypothetical algorithm that you employ to compute discrete logarithms, knowledge of the factors of $N$ may be required, which implies that you still have to factor $N$ to compute the discrete log, which means breaking RSA would still be as hard as factoring.

Diffie-Hellman usually works with a prime modulus, so the factors of the modulus (which are just $1, P$) are public information.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Just for clarification. So the RSA problem does not only rely on the difficulty of solving the problem of factorization of a large semiprime $N$ but also on solving the discrete logarithm problem over an $N$ with unknown factorization, while in DH the difficulty relies on solving the discrete logarithm problem over an $N$ with known factorization, and that might or might not affect the actual hipotetical algorithm used to solve the discrete logarithm problem on a usefull time. is that right? $\endgroup$
    – Joaquin Brandan
    Mar 8, 2018 at 0:45
  • 1
    $\begingroup$ @JoaquinBrandan That sounds more or less correct, though I would amend it to say DH relies on solving discrete logs modulo a prime, rather than rather than an $N$ of known factorization. Knowledge of the factors of $N$ could be a requirement for the hypothetical discrete-log computing algorithm - or it might not be, but that sounds even more fantastical. $\endgroup$
    – Ella Rose
    Mar 8, 2018 at 0:59
  • $\begingroup$ I just realized you would need the entire $M$ for this, so partial knowledge of the plain text would not be suficent. $\endgroup$
    – Joaquin Brandan
    Mar 8, 2018 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.