# Trying to calculate RSA decryption key

I am testing a piece to encrypt and decrypt messages, and I am not 100% on why the algorithm does not seem to work as expected.

My test encryption key $e =27$. My primes $p = 263$ and $q = 911$. And when I run my code to generate a decryption key, $d$, using the algorithm $d\equiv e^{-1} \pmod{ (p-1)(q-1)}$, I get $d=70643$. When I then proceed to decode my cipher, $C$, using the algorithm $C^d \pmod{ (pq)}$, I get something unexpected, and incorrect.

the message m =82020161928606013010912592501081515590315136325211464072101146304100804061004

Anyone have an idea where I may be getting this wrong please? Thanks in advance

-
Is it not supposed to be $d \equiv e^{-1} \mod \phi(n)$ where $\phi(n)=(p-1)(q-1)$? –  Jalaj Mar 5 '12 at 1:15
oops! I corrected that. Yes, it is and I get d=70643. –  Kobojunkie Mar 5 '12 at 1:26

In Wolfram Alpha I tried $555^{27} \pmod{263*911} \equiv 44315$ then $44315^{70643}\pmod{263*911} \equiv 555$ so it seems to work here.
Here is the problem, when I put my Cipher through the same, I don't get the original back. $$106994^70643 (mod 239593)$$ in Wolfram also gives me $$152989$$, which is incorrect –  Kobojunkie Mar 5 '12 at 1:43
@Kobojunkie: The message has to be less than the modulus. It is giving you back m mod 239593, so your routines are working fine. Two $\LaTeX$ hints: enclose multicharacter things (like 70643) in braces: 2^33 gives $2^33$ but 2^{33} gives $2^{33}$ and the way to write mod239593 is \pmod {239593}. That way the mod isn't italicized. –  Ross Millikan Mar 5 '12 at 3:10