Chapter 12, Problem 49CRP

Explanation of Solution

Determine the decrypt of message 111 with use of the public key:

The public key is $n=133$ and $d=5$. And the message is 111 that is $c=110$.

• To find the binary representation of message value that is $c$, multiply value at once place with 2 raised with power 0 at tens place with 2 raised to the power 1 and at hundred’s place with 2 raised to the power 2.

  $\begin{array}{c}111=1\times 2^2+1\times 2^1+1\times 2^0\\ =1\times 4+1\times 2+1\times 1\\ =4+2+1\\ =7\end{array}$

• Thus, the binary representation of the encrypted message is $c=7$.
• The decryption formula for the RSA public-key encryption is,

  $m=c^d\left(\mathrm{mod}n\right)$

  Here, $c$ is the encryption key.

  Substitute 7 for $c$, 5 for $d$ and 133 for $n$ in the above equation.

  $\begin{array}{c}m=7^5\left(\mathrm{mod}133\right)\\ =49\end{array}$

• To represent the above result in decoded message, convert the result in binary