RSA problem if i choose two specific small prime numbers?

Question

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 crypted message is wrong! Exactly when I choose p=11 and q=5, the rest goes like this:

n=55
euler(n)=40 = (p-1)(q-1)
e=13
d=37

the crypted message (using message=65) is:

c=10

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

Dp=7
Dq=1
Qinv=9
m1=10
m2=0
h=2

and the decrypted message is:

message=10 !!!!!

It´s a problem of the choosen prime numbers? I think that the rest I made it fine, I also check it with rsa calculator: https://www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAWorksheet.html

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

Answer 1

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

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

Answer 2

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.