Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
7  
Your only problem is that what you call message (65) is bigger than n (55). Your result (10) is the message reduced modulo n. –  fgrieu Mar 15 at 18:33
add comment

2 Answers 2

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

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

share|improve this answer
    
One should also have $\: 0\leq m \;$. $\;\;\;\;$ –  Ricky Demer Mar 16 at 22:39
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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