An old question I am preparing for a security / cryptography class has an example of an RSA chiper.
This is almost the same as "RSA by hand - did I do something wrong? (c = m on encryption)" but with some other question following up.
Let $p=3$, $q=5$ giving $N=15$ and $\phi=8$
Let $e=7$. Find $d$.
Fair enough, $e\times d = k\times \phi+1$ can be rather quickly evaluated to $d=7$. $k$ would be $6$ in this case.
Encryption of messages $m$ in the range $1 < m < n$ work fine with $e=d=7$. Not very helpful to have $e=d$, but it works. Well, kind of, as some messages get encoded to the same value (4, 5, 6 and 9 for example). So the target of encryption is reached only partly but the answer for the test $d=7$ is correct and complete.
This was the easier part.
Now… could you have chosen $5$ for $e$? And follow-up question: Why not? The solution provided has
no
and
because $5$ has a common divisior with $n$
Our lecture script and every page I found regarding RSA demands $e$ and $d$ to not share a divisior (except $1$, of course) with $\phi$. I never found a remark regarding sharing with $n$.
Problem is this: What happens if you use $e=5$ (and in turn get $d=13$) is that you get no encrytion at all. $c = m^e\ mod\ n$ stays $= m$ for all $m$.
So the mathematics "work", no information is messed up, but the desired encryption is not reached at all. Is there a reason why $5$ is kind of "neutral exponent"? Does such a thing also happen for "real" rsa values?
In this example $e=5$ is equal to $q$, is that what makes the encryption become an "Involution Mathematics" (wikipedia)?
How would one word his reasoning why $5$ is an unsuitable value for $e$? More important, how can one see this in a exam situation without excel spread sheet to quickly run some numbers (without any calculator, in fact)?