Chapter 2.8, Problem 16E

Rework Example 5 by breaking the message into two-digit blocks instead of three-digit blocks. What is the enciphered message using the two-digit blocks?

Example 5: RSA Public Key Cryptosystem We first choose two primes (which are to be kept secret):

$p=17$, and $q=43$.

Then we compute $m$

(which is to be made public):

$m=pq=17\times 43=731$.

Next we choose $e$

(to be made public), where $e$ must be relatively prime to $(p-1)(q-1)=16\times 42=672$. Suppose we take $e=205$. The Euclidean Algorithm can be used to verify that $(205,672)=1$. Then $d$ is determined by the equation

$1=205d\mathrm{mod}672$

Using the Euclidean Algorithm, we find $d=613$

(which is kept secret). The mapping $f:A\to A$, where $A=\{0,1,2,\mathrm{...},730\}$, defined by

$f(x)=x^{205}\mathrm{mod}731$ is used to encrypt a message. Then the inverse mapping $g:A\to A$, defined by

$g(x)=x^{613}\mathrm{mod}731$ can be used to recover the original message.

Using the $27$-letter alphabet as in Examples 2 and 3, the plaintext message “no problem” is translated into the message as follows:

$\begin{array}{ccccccccccc}\text{plaintext:}& \text{n}& \text{o}& & \text{p}& \text{r}& \text{o}& \text{b}& \text{l}& \text{e}& \text{m}\\ \text{message:}& \text{13}& \text{14}& \text{26}& \text{15}& \text{17}& \text{14}& \text{01}& \text{11}& \text{04}& \text{12}\end{array}$

The message becomes

$13142615171401110412$.

This message must be broken into blocks $m_i$, each of which is contained in $A$. If we choose three-digit blocks, each block $m_i<m=731$.

$\begin{array}{cccccccc}{m}_i:& 131& 426& 151& 714& 011& 104& 12\\ f(m_i)=m_i^{205}\mathrm{mod}731=c_i:& 082& 715& 376& 459& 551& 593& 320\end{array}$

The enciphered message becomes

$\begin{array}{ccccccc}082& 715& 376& 459& 551& 593& 320\end{array}$ where we choose to report each $c_i$ with three digits by appending any leading zeros as necessary.

To decipher the message, one must know the secret key $d=613$ and apply the inverse mapping

$g$ to each enciphered message block $c_i=f(m_i):$

$\begin{array}{cccccccc}{c}_i:& 082& 715& 376& 459& 551& 593& 320\\ g(c_i)=c_i^{613}\mathrm{mod}731:& 131& 426& 151& 714& 011& 104& 12\end{array}$

Finally, by re-breaking the “message” back into two-digit blocks, one can translate it back into plaintext.

$\begin{array}{l}\begin{array}{cccccccc}\text{Three-digit}\text{block}\text{message:}& 131& 426& 151& 714& 011& 104& 12\end{array}\\ \begin{array}{ccccccccccc}\text{Two-digit}\text{block}\text{message:}& 13& 14& 26& 15& 17& 14& 01& 11& 04& 12\\ \text{Plaintext:}& n& o& & p& r& o& b& l& e& m\end{array}\end{array}$

The RSA Public Key Cipher is an example of an exponentiation cipher.