RSA exercise with known $n$ and $e$

Bob decides to use $$n = 697 \rightarrow 17 × 41$$ and $$e = 33$$ as his public key for an RSA cryptosystem.

1. Show that the decryption exponent is $$97$$.

2. Find the encrypted form of the message $$17$$.

Since you "have done a bit of work on this", it would be nice to actually show that "bit of work".

Anyway, here are three hints:

1. The exercise phrasing is actually wrong. $$97$$ is not "the" decryption exponent. It's only "a" decryption exponent, among a set of decryption exponents that match the public exponent $$e = 33$$. That set is infinite. $$97$$ is not even the smallest value in that set of solution; it is just the "traditional" solution. Another solution is $$17$$. In fact, all integers $$17+80k$$ for any $$k\ge 0$$ are "private exponents" that match $$e = 33$$ for modulus $$n = 697$$.

2. Everything in RSA can be done with the Chinese Remainder Theorem. In a nutshell, that theorem says that since $$41$$ and $$17$$ are prime to each other, all computations modulo $$41\times 17 = 697$$ are equivalent to computing things modulo $$41$$ and modulo $$17$$ in parallel. This means that you can split your problem of verifying that $$97$$ is a proper private exponent into two sub-problems: verifying that it works modulo $$41$$, and verifying that it works modulo $$17$$. The CRT really tells you that if it works modulo both, then it will work modulo their product $$697$$.

3. For the second question, use the CRT again.

With these hints, you can solve all of it with a pen-and-paper, or even doing the computations in your head (I know it's feasible, I just did).

• Here $\phi(n) = 16*40 = 640$. and 17*33 = 561. How is it a solution? Why is $17+80k$ a solution if $\phi(n) \neq 80$? – satya Dec 12 '18 at 11:17
• @satya It is not necessary that $d$ is an inverse of $e$ modulo $\phi(n)$. For RSA to work, you just need to have $d$ an inverse of $e$ modulo both $p-1$ and $q-1$ (the CRT tells you this is sufficient; try it!). For that, you make $d$ and inverse of $e$ modulo the least common multiple of $p-1$ and $q-1$, which is 80 in that case. The Euler function $\phi(n) = (p-1)(q-1)$ is a multiple of that common multiple. – Thomas Pornin Dec 12 '18 at 15:16