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??

  • $\begingroup$ 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$. $\endgroup$ – Gerry Myerson Oct 16 '14 at 6:05
  • $\begingroup$ $31^{17}=(-2)^7=-128=-7=4\pmod{11}$, but $28=6\pmod{11}$, so maybe you should check your calculation. $\endgroup$ – Gerry Myerson Oct 16 '14 at 6:09
  • $\begingroup$ You're right. q=13 should be q=3. Just fixed it. $\endgroup$ – Jader J Rivera Oct 16 '14 at 11:35
  • $\begingroup$ Good. Now, did you check your calculation of $31^{17}\pmod{33}$? $\endgroup$ – Gerry Myerson Oct 16 '14 at 11:59
  • $\begingroup$ Yes. And now it somehow works. Thank you. $\endgroup$ – Jader J Rivera Oct 16 '14 at 12:08

Might as well state that it was just a precision error.

Changing (31) to (-2) "fixes" the problem, since (31)mod(33) == (-2)mod(33).

And ((-2)^17)mod(33) = (-29), where (-29)mod(33) == (4)mod(33).

So it comes down to that one should use more than 8 bytes or use smaller numbers.

  • $\begingroup$ 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$. $\endgroup$ – Gerry Myerson Oct 19 '14 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.