7
$\begingroup$

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

|improve this question
$\endgroup$
  • 1
    $\begingroup$ The Carmichael function has the value $\lambda(15)=4. $ Therefore for all messages you have $m^4=1$ and then $m^5=m$. $\endgroup$ – gammatester Feb 8 '17 at 12:09
  • $\begingroup$ If your public exponent shares a factor with N attacks become trivial (just compute the GCD). $\endgroup$ – SEJPM♦ Feb 8 '17 at 12:12
  • 1
    $\begingroup$ @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... $\endgroup$ – poncho Feb 8 '17 at 19:08
  • $\begingroup$ you wrote : ...and in turn get d=13. But, $d=e^{-1}\pmod \phi = 5^{-1}\pmod 8 =5.$ $\endgroup$ – 111 Feb 10 '17 at 23:06
2
$\begingroup$

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.

|improve this answer
$\endgroup$

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.