Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Decode the following message which was sent using mod $m = 7081$ and exponent $k=1789$ (RSA): $$ 5192 2604 4222 $$ I solved $\phi(7081)=6912$, and then solved the linear equation $1789u-6912v=1$ where $u=85$ and $v=22$.

But then, when I plugged this into $5192^85 \mod 7081$, successive squaring gave me $0$. Clearly incorrect.

I got: $$ 85=2^0+2^2+2^4+2^6 $$ $$ 5192^1=5192 \pmod{7081}\\ 5192^2=6578 \pmod{7081}\\ 5192^4=5174 \pmod{7081}\\ 5192^8=0 \pmod{7081} $$ I also got the other two numbers $(2604, 4222)$ raised to the $8$th power are congruent to $0$. Where did I go wrong in this problem?

share|improve this question
2  
What are you using to calculate this? $5192^8 \equiv 4096 \pmod {7081}$ –  Brandon Carter Apr 10 '11 at 16:19
1  
Specifically, your last step is wrong; $5192^4 \equiv 5174$, but then $5192^8 \equiv 5174^2 \not \equiv 0$. –  Zach Langley Apr 10 '11 at 16:25
1  
@Joseph: Wolfram Alpha gives the correct answer: wolframalpha.com/input/?i=5192^8+mod+7081 –  Brandon Carter Apr 10 '11 at 16:26
2  
@Joseph, I just plugged in exactly that and it gave the correct answer: wolframalpha.com/input/?i=4222%5E%282%5E3%29+mod+7081 –  Zach Langley Apr 10 '11 at 16:54
5  
Better yet for entering into Wolfram Alpha: PowerMod[4222, 2^3, 7081] –  J. M. Apr 10 '11 at 17:22
show 3 more comments

1 Answer

up vote 1 down vote accepted

You did it right, in that $d=85$ is the decryption exponent, as $d$ and $e = 1789$ are inverses modulo $\phi(n) = \phi(7081) = 6912$. Entering 5192 ** 85 % 7081 in python, I get 1615, which seems like 2 letters (using A = 1, etc in a digraphic code). Also the other 2 groups give 2823 and 1130, which seems to imply some extra characters besides just letters. Wolfram alpha agrees (entering 5192^85 mod 7081 etc.)

Just curious: what does this mean in your code?

share|improve this answer
    
It means Fermat. The code starts at A=11, B=12, etc. –  user7435 Apr 14 '11 at 19:07
add comment

Your Answer

 
discard

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