Show how one can decrypt RSA message with e = 3 and $m<N^{1/3}$ without knowing the private key.

I really don't know how to solve this one.

we just learned about quadratic residues so i guess it has something to do with that.

First thing is I need to understand what do I know and what do I need to find.

after reading some about RSA I think I need to find x for the following congruence-

$c \equiv x^3 \pmod N$

where I know c, and N

is that correct? any help , clues , solutions or more information will be appriciated


Hint: If $m<N^{1/3}$ then $m^3<N$. What does this tell you about $m^3\bmod N$?

  • $\begingroup$ so it tells me that $m^3 \pmod N$ is $m^3$ ?? and then I check all numbers $\in 1^3 , 2^3, 3^3, ... , N^{1\3} $ and for each one checks if $c-m \equiv 0 \pmod N$ ? is it solvable if N is big?? $\endgroup$ Jun 24 '15 at 16:15
  • $\begingroup$ First question, yes. Then you seem to go off on a tangent. Computing $m$ when you know $m^3$ is easy, there is no need to try all possibilities. You can use a variant of Newton's method, just rounding each iterate to an integer as you go. $\endgroup$ Jun 24 '15 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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