Take the 2-minute tour ×
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.

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 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 at 20:54
2  
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 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 at 21:34
2  
@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 at 21:56

1 Answer 1

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
3  
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 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 at 14:03
    
@Minkus: Finding $\phi(N)$ given $N$ is itself a difficult problem –  figlesquidge Feb 26 at 11:00
1  
True that. I will update my answer to reflect your correction. –  Minkus CNB Feb 26 at 15:25
1  
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 at 18:58

Your Answer

 
discard

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.