# RSA by hand - did I do something wrong? (c = m on encryption)

to understand RSA better I am doing a little calculation by hand, this is what I got:

Choosing:

$p = 3\\ q = 5\\ n = 15\\ \varphi(p\cdot q) = 2 \cdot 4 = 8\\ e > \varphi(n) \implies e = 13\\ e \cdot d = 1 \pmod 8\\ 13 \cdot d = 1 \pmod 8\\ (13 \cdot 5) \mod 8 = 1$

So there has to be $m \le n$ and I choose $m = 7$

Encryption:

$c = m^e \mod n\\ c = 7^{13} \mod 15\\ c = 7$

And if I decrypt it's nice coming back to 7. But it looks a bit weird to me having $m = c$ but I don't find what I should be doing wrong.. ?

• Try larger $p$ and $q$. I've noticed when doing RSA by hand with very small $p$ and $q$ it is easy to run into corner cases in which weird things happen (for example, the reason for a previous question of mine: crypto.stackexchange.com/questions/1004/…). These corner cases only occur with negligible probability for large $p$ and $q$. Obviously if you choose $p$ and $q$ too large you can't do it by hand any more though, so you have to balance between doing it by hand and hitting weird cases. – mikeazo Jul 1 '13 at 12:58

Your math is correct. But: RSA defines choosing $e< \phi(n)$ not $e>\phi(n)$, and $e$ coprime to $\phi(n)$ obviously. The only necessary assumption here is that they are coprime (otherwise it's a lossy function and you can not decrypt any more). But since encryption with $e$ mod $\phi(n)$ results in the same ciphertext, you gain nothing but a larger exponentiation if $e$ is larger than $\phi(n)$.

About your numbers: Your choice of $p$ and $q$ lead to a curious coicidence: $5 = 5^{-1}$ mod 8. Therefore $e=d=5, ed=1$ mod 8. However, without knowledge of $\phi(n)$ it is hard to know if a random public RSA key fulfills this relation or not. By finding such an exponent, you got an involution. Roughly speaking, such a function can only send $x$ to itself or its inverse, otherwise it doesn't work.

• okay, so choosing e < phi(n) boosts the performance of encryption. and for the rest I am understanding that it is a random case which I encountered because of small values. It's just because I really try to understand how it works and not just accepting that it does.. – Stefan Jul 1 '13 at 19:37
• – Ilmari Karonen Dec 29 '15 at 10:07

In fact, your calculating is right. The problem is:

At first, $e=13=5\pmod 8$.

Next, $d=5=e$ since $d\cdot e=1\pmod 8$. This means that the decryption key is identical to the encryption key. You should avoid this of course.

Third, $7^{13}=7^5=(7^2)\cdot(7^2)\cdot 7\pmod{15}=(4\cdot 4)\cdot 7\pmod{15}=7\pmod{15}$. This is why your decryption outputs the same as the input. If you try another message, you may find that the cihertext is different to the plaintext.

• This starts to lighten up. So the problem is choosing a n e for which the inverse modulo is not the remainder of e mod n ? In fact this is the case for all values I have tried. Then how to choose it correctly and wisely? I have also seen that ciphertext varies and is not always m=c. – Stefan Jul 1 '13 at 11:37

What you're doing wrong is choosing $e$ to be (comparatively) way too large.
It is sufficient that $e$ and $d$ satisfy $\;\;\;\; e\hspace{-0.03 in}\cdot\hspace{-0.03 in}d \: \equiv \: 1 \;\; \pmod{\operatorname{lcm}(\hspace{.025 in}p\hspace{-0.03 in}-\hspace{-0.03 in}1,\hspace{-0.01 in}q\hspace{-0.03 in}-\hspace{-0.03 in}1)} \;\;\;\;$.
Since $\;\; 13 \equiv 1 \: \pmod{\operatorname{lcm}(\hspace{.01 in}3\hspace{-0.03 in}-\hspace{-0.03 in}1,\hspace{-0.01 in}5\hspace{-0.03 in}-\hspace{-0.03 in}1)} \;\;$, $\;\;$ your "encryption" will be just reducing modulo 15.

• But for choosing e bigger than phi(n) and relatively prime what would be a good choice? I don't think I understood completely what you try to say. Or is it wrong to have e > phi(n) ? – Stefan Jul 1 '13 at 8:10
• Well, 11 would have been a good choice, since that will give the same outputs as using 3. $\:$ Decryption will still work with e > phi(n), the public operation will just be much slower than one would get by using a smaller e. – user991 Jul 1 '13 at 8:21
• But choosing e=11 and m=10 would also give me m=c for 10^11 mod 15 – Stefan Jul 1 '13 at 8:32
• Yes, since 10 is idempotent. $\:$ More generally, that will happen for at most e^2 values, regardless of what n is. $\;\;\;$ – user991 Jul 1 '13 at 9:01

I think your problem is, that you are choosing $e > phi(n)$. But one can always modulo reduce $e$ mod $phi(n)$, so you should choose an $e < phi(n)$.

In fact, $e$ is often relativley small (i.e. small hamming-weight), to get faster encryption runtimes. That is, because the exponentiation algorithms used in real world RSA, need more multi-precision multiplications for higher hamming-weights.