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

  • $\begingroup$ 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$? $\endgroup$ – satya Dec 12 '18 at 11:17
  • 1
    $\begingroup$ @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. $\endgroup$ – Thomas Pornin Dec 12 '18 at 15:16

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.