2
$\begingroup$

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} \pmod{7081}$, successive squaring gave me $0$, which is 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?

  • 2
    What are you using to calculate this? $5192^8 \equiv 4096 \pmod {7081}$2011-04-10
  • 0
    I was using Wolfram Alpha.2011-04-10
  • 1
    Specifically, your last step is wrong; $5192^4 \equiv 5174$, but then $5192^8 \equiv 5174^2 \not \equiv 0$.2011-04-10
  • 1
    @Joseph: Wolfram Alpha gives the correct answer: http://www.wolframalpha.com/input/?i=5192^8+mod+70812011-04-10
  • 0
    Try plugging this into Wolfram Alpha: 4222^(2^3) mod 7081 it gives the wrong answer. but thanks, I figured out the code.2011-04-10
  • 2
    @Joseph, I just plugged in exactly that and it gave the correct answer: http://www.wolframalpha.com/input/?i=4222%5E%282%5E3%29+mod+70812011-04-10
  • 5
    Better yet for entering into Wolfram Alpha: `PowerMod[4222, 2^3, 7081]`2011-04-10
  • 0
    @Zach: Bizarre. I clicked your link and it gave me 0. But anyway, I got the code. Thanks everybody for your help.2011-04-10

1 Answers 1

1

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?

  • 0
    It means Fermat. The code starts at A=11, B=12, etc.2011-04-14