I know that RSA normally is made to make it with big integers, but i trying to make the algorithm myself (with the help of wikipedia) and I´m making it with small numbers to track the problems easily.

The problem is that sometimes the decryption of the encrypted message is wrong! Exactly when I choose p=11 and q=5, the rest goes like this:

euler(n)=40 = (p-1)(q-1)

the encrypted message (using message=65) is:


and using the chinese reminder theorem (wikipedia´s advise):


and the decrypted message is:

message=10 !!!!!

It´s a problem of the chosen prime numbers? I think that the rest I made it fine, I also check it with rsa calculator.

I know also that to choose d and e there are more options, but the chosen ones they would be fine too. Maybe there is some other condition that is not on wikipedia?

  • 7
    $\begingroup$ Your only problem is that what you call message (65) is bigger than n (55). Your result (10) is the message reduced modulo n. $\endgroup$
    – fgrieu
    Mar 15, 2014 at 18:33

2 Answers 2


Actually, that's an expected result since $65 \equiv 10 \pmod{55}$.

You should choose $m < n$ to avoid this problem.

  • $\begingroup$ One should also have $\: 0\leq m \;$. $\;\;\;\;$ $\endgroup$
    – user991
    Mar 16, 2014 at 22:39

Apart from you're choosing a message greater than the modulus, another thing that might be confusing you is that, in this case, $C \equiv P \bmod N$.

That is, you take your message, 65, which is equivalent to 10 modulo 55, and encrypt it, and the result is 10, because $10^{13} \bmod 55 = 10$, So, when you decrypt it, you take the ciphertext 10, and naturally get the plaintext back as 10, as $10^{37} \bmod 55 = 10$.

This "ciphertext is the same as the plaintext" is an artifact of using a tiny $N$; it does happen on real size RSA modulii, but with extremely low probability if the plaintext was chosen randomly.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.