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:

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

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

  • 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 '14 at 18:33

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 '14 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, privacy policy and cookie policy

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