3
$\begingroup$

I need some help with the following statement from the book A Graduate Course in Applied Cryptography* - Dan Boneh and Victor Shoup, in 8.10.1 The key derivation problem, page 320 of v0.5:

Later, we will see examples of number-theoretic transformations that are widely used in public-key cryptography. Looking ahead a bit, we will see that for a large, composite modulus $N$, if $x$ is chosen at random modulo $N$, and an adversary is given $y := x^3 \bmod N$, it is hard to compute $x$.

To be specific, my doubt is related to how do we really prove that RSA problem can keep hard, despite small and known exponents $x^3 \bmod N$, for an adversary who doesn't know $x$. The authors said that "we will see examples" in the book. But I couldn't find them. Can you please give me some direction for such proof?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Actually, this is not a DL problem; it's the RSA problem... $\endgroup$
    – poncho
    May 4, 2020 at 15:11
  • $\begingroup$ @poncho, thanks a lot: I fixed the title. $\endgroup$
    – Paollo
    May 4, 2020 at 15:20
  • $\begingroup$ The book probably used the vague "we will see that" rather than "we will prove that" on purpose. As a simple empirical observation, the problem is hard in the ordinary language meaning of "hard", and this is easy enough to see. You just observe massive computational resources being thrown at the problem in vain. The problem comes when you try to formalize "hard" and to prove that it actually is (rather than merely appears to be) hard in that sense. $\endgroup$
    – John Coleman
    May 5, 2020 at 18:22

1 Answer 1

Reset to default
12
$\begingroup$

Can you please give me some direction for such proof?

You're looking for a proof that the RSA problem is hard? No such proof is known (even in the specific case of $e=3$). Furthermore, there is no known reduction to a 'more fundamental' problem, such as factorization or discrete log.

The closest we can get is a proof that if you can find the 'decryption exponent', that is, the value $d$ such that $y^d \equiv x \pmod N$, you can factor $N$ (and using the value $d$ is how the holder of the RSA private key recovers $x$ in practice). However, this does not show that there isn't another way (that's easier than factoring) to recover $x$.

The only 'proof' we have that the RSA problem is hard is 'lots of smart people have looked for a way to solve it, and they haven't found one'

Improve this answer
$\endgroup$
8
  • 8
    $\begingroup$ @Paollo: actually, the question makes perfect sense. It's just that we don't know an answer, and anyone who finds an answer (either in the "here's how we can prove RSA is reducible to factoring" direction or "here's how to solve RSA quickly without factoring") would have quite a notable result. $\endgroup$
    – poncho
    May 4, 2020 at 16:41
  • 3
    $\begingroup$ If I recall correctly, for the similar system with $e = 2$, there is such a proof. Wikipedia seems to concur: en.wikipedia.org/wiki/Rabin_cryptosystem $\endgroup$
    – ilkkachu
    May 5, 2020 at 8:47
  • 3
    $\begingroup$ Even with the proof that the Rabin cryptosystem is at least as hard as factorisation, we have no proof that factorisation itself is difficult, just a lot of people trying really hard for a few thousand years. We generally assume that it is difficult in specific cryptographic models, so that we can make other deductions about the cryptosystem. $\endgroup$
    – Cyclic3
    May 5, 2020 at 9:23
  • 2
    $\begingroup$ @Paollo: if $p$ is prime, then it is an easy problem. If $p\equiv 2 \pmod 3$, then $b = c^{(2p-1)/3} \bmod p$. If $p \equiv 1 \pmod 3$, then it's a tad more work, however it's still doable (and there will be 3 possible values of $b$) $\endgroup$
    – poncho
    May 5, 2020 at 15:01
  • 2
    $\begingroup$ @Paollo: this is a different problem; the original problem was "given $b, b^d$, find $d$. This problem is "given $b^d$, find $b$". Now, with this new problem, there will be approximately $A$ possible values for $b$ (and with no further information, we can't say which one it is), and it should take about $O(A)$ time to list them all. $\endgroup$
    – poncho
    May 5, 2020 at 19:46

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.