# Decryption of a RSA encrypted message is not working.

Using RSA with e=13 (encrypting power), d=17 (decrypting power) & n=33 (RSA modulus) I noticed that once I decrypted the encrypted message it would be different then the original message. Why is that??

I used the primes p=11 & q=3 to get the modulus n=33. So the totient Phi(n) = k = 10*2 = 20

By choosing e=13, (d*e)mod(k)=1 d is 17.

.

If I encrypt "4"

(4^13)mod(33) = 31

Decrypting "31" to get back "4"

(31^17)mod(33) = 28 (It's not working)

.

Though by using e=3 & d=7 it works. Is there a relationship to these numbers??

• It would help if you would say what you mean by $e,d,n,p,q$. Not all sources use the same letters for the same things. In particular, if $n=pq$, then $q=13$ should be $q=3$. – Gerry Myerson Oct 16 '14 at 6:05
• $31^{17}=(-2)^7=-128=-7=4\pmod{11}$, but $28=6\pmod{11}$, so maybe you should check your calculation. – Gerry Myerson Oct 16 '14 at 6:09
• You're right. q=13 should be q=3. Just fixed it. – Jader J Rivera Oct 16 '14 at 11:35
• Good. Now, did you check your calculation of $31^{17}\pmod{33}$? – Gerry Myerson Oct 16 '14 at 11:59
• Yes. And now it somehow works. Thank you. – Jader J Rivera Oct 16 '14 at 12:08

• Or one should calculate $a^b\pmod c$ by some method more clever than first computing $a^b$ and then reducing modulo $c$. It can be done without ever having to deal with any numbers bigger than $c^2$. – Gerry Myerson Oct 19 '14 at 9:07