Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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$

share|improve this answer
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
You are right, this is not a real valid approach to solve an RSA problem. However, since we already know N so we can find out how easy this approach is by finding phi of N (assuming that it is a reasonable number). Note Modified approach to multiply m^5 mod N by m^5 mod N till we get a cycle. – Minkus CNB Feb 25 '14 at 14:03
@Minkus: Finding $\phi(N)$ given $N$ is itself a difficult problem – figlesquidge Feb 26 '14 at 11:00
True that. I will update my answer to reflect your correction. – Minkus CNB Feb 26 '14 at 15:25
Ha okay fixed. If you find anything else let me know, I don't want to post a wrong or confusing answer. – Minkus CNB Feb 26 '14 at 18:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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