# Can you help me understand this (old) school question related to RSA usage?

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)?

• The Carmichael function has the value $\lambda(15)=4.$ Therefore for all messages you have $m^4=1$ and then $m^5=m$. Feb 8 '17 at 12:09
• If your public exponent shares a factor with N attacks become trivial (just compute the GCD).
– SEJPM
Feb 8 '17 at 12:12
• @SEJPM: actually, the original Clifford Cox scheme had $e=N$; that worked perfectly fine (unless $p$ and $q$ had a really unlikely, and easily tested, relationship), and $\gcd(e, N)$ tells you nothing... Feb 8 '17 at 19:08
• you wrote : ...and in turn get d=13. But, $d=e^{-1}\pmod \phi = 5^{-1}\pmod 8 =5.$
– 111
Feb 10 '17 at 23:06

As in the other questions: Such low numbers can lead to curious-and-misleading effects. For example in this case: you choose $$q=5$$, and it happens that this is equal to $$\lambda(15) + 1 = 5$$. And that is a coincidence of this example, not a general relation.

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

Which question ans answer are you quoting here? Because it's not the one you linked to.

And I would actually say, there is no reason that $$e$$ has to be coprime to $$N$$ - except that it would be really terrible if anyone just tried to calculate $$gcd(e,N)$$. However, the encryption and decryption still work in the sense that you can retrieve the plaintexts (injective function).

Regarding the coincidence in th example: For every modulus, you have that $$m^{\lambda(N)} = 1 \mod N$$ with Carmichael function $$\lambda$$, and in turn $$m^{\lambda(N) + 1} = m \mod N$$.

And then, for two different primes $$p,q$$ this can be calculated as $$\lambda(pq) = lcm(p-1,q-1)$$. Alternatively, this is $$\lambda(N) = (p-1)(q-1) / g$$ for $$g = ggt(p-1,q-1)$$.

From that, we can see that if $$\lambda(N) + 1 = q$$, then we know immediately $$p-1$$ is a divisor of $$q-1$$.

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?

Yes, it does, but not for either $$p$$ or $$q$$. It happens for $$k \lambda(N)+1$$ for any arbitrary integer $$k$$.

In this example e=5 is equal to q, is that what makes the encryption become an "Involution Mathematics" (wikipedia)?

Since this is taken from the linked question - this is something similar, but not the same. An involution happens whenever $$e=d \mod \lambda(N)$$, because then you have that $$ed = e^2 = 1 \mod \lambda(N)$$. And again, it's pure coincidence in this number example, that it is equal to $$q$$. That is wrong in general.