# Decode message $m = p * q$, where $p ^ 5 \bmod N$, $q ^ 5 \bmod N$ and $N$ are known

I been going through some cryptography exercises and stumbled across this problem.

Discover message $m$. You know that $m = p * q$. Also $p ^ 5 \bmod N$, $q ^ 5 \bmod N$ and $N$ are known numbers.

I am really lost and don't know where to start. Could anyone give some hints or point me to right direction where to read up on this problem?

-
Do you know the factorization of $N$? If not (and if $N$ is large enough to make factorization infeasible), this is known to be a hard problem ("the RSA problem") – poncho Feb 24 '14 at 20:28
@poncho Thank you, that's exactly the case and I can see the RSA in it now. Should I divide it into two problems or will knowing $p ^ 5 mod N$ and $q ^ 5 mod N$ help in any way? – user12197 Feb 24 '14 at 20:54
No, knowing $p^5 \bmod N$ and $q^5 \bmod N$ doesn't particularly help; given an Oracle that solves your problem, it's easy to use it to solve an arbitrary RSA instance with $e=5$ – poncho Feb 24 '14 at 20:58
And knowing $m^2$ and $p^5$? because you could use the fact that $GCD(2, 5)= 1$ and $GCD(m^2, p^5) = p^2$ ?? Just an idea, not tried – ddddavidee Feb 24 '14 at 21:34
@ddddavidee: actually, you don't know $p^5$, you know $p^5 \bmod N$; if you know $p^5$ and $q^5$, then it'd be easy (it's easy to take fifth-roots over the integers). – poncho Feb 24 '14 at 21:56

I don't have a full answer yet but here is what I have so far. Since you know what $p^5 \bmod N$ is and what $q^5 \bmod N$ is then you know what $m^5 \bmod N$ is. Since we also know what $N$ is then we should be able to find out how many times we need multiply $m^5 \bmod N$ by $m^5 \bmod N$ till we get a full cycle (you can calculate it through $\phi(N)$ or you can multiply by m till you get back to your original number). From that cycle, go back 4 terms and that should be what $m \bmod N$ is.
Update: Finding $\phi(N)$ can be difficult for sufficiently large $N$ but multiplication with mods is a fairly easy cheap. First make sure that N and 5 are relatively prime, and then (for practicality purposes) repeatedly iterate $F: x\mapsto x^5\bmod N$, starting with the known $x_0=m^5\bmod N$ until $x_{j+1}=x_0$, thus making $x_{j}$ a possible $m$
This answer is "lets compute $(pq)^5 \bmod N$, and then solve the RSA problem to recover $pq$". While this is a valid approach (in fact, would appear to be the only reasonable approach unless, as fgrieu has suggested, $p$ and $q$ have been picked to make this easy), there are far better ways to attack the RSA problem (not to mention that you can't multiply $m^5$ by $m$ as you don't know $m$; that's the value we're trying to recover) – poncho Feb 25 '14 at 13:54
@Minkus: Finding $\phi(N)$ given $N$ is itself a difficult problem – figlesquidge Feb 26 '14 at 11:00