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?

  • 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