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

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$?
• 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?? Jun 24 '15 at 16:15
• 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. Jun 24 '15 at 20:32