\documentclass{2800hw}
\usepackage{amsmath,amssymb,latexsym}
\usepackage{verbatim}
\usepackage{utf8}

\topic{RSA}
\homework{9}

\begin{document}
\maketitle

\begin{exercises}
\item Suppose we wish to transmit the message ``cs2800 rocks'' using RSA.
Suppose the public key has $m = pq = 3403$ and the exponent $k = 17$.

Note: for this problem, I used a spreadsheet to do the calculations.  If you use
calculators or spreadsheets to manipulate very large numbers, you can cause
overflow, so make sure you reduce mod $m$ as necessary to keep the numbers
small.  To compute $a^k$ for large $k$, it helps to write $k$ in binary, and
then use repeated squaring to find $a$ to a power-of-two power.  For example,
to compute $a^{52}$, I write $52 = 32 + 16 + 4$, so $a^{52} = a^{32} \cdot
a^{16} \cdot a^{4}$.
\begin{enumerate}
\item Use the mapping
\begin{center}
\begin{tabular}{|c|c|}
\hline
`a' & 01 \\ \hline
`b' & 02 \\ \hline
\vdots{} & \vdots \\ \hline
`y' & 25 \\ \hline
`z' & 26 \\ \hline
`~' & 27 \\ \hline
`0' & 28 \\ \hline
`1' & 29 \\ \hline
`2' & 30 \\ \hline
\vdots{} & \vdots \\ \hline
`9' & 37 \\ \hline
\end{tabular}
\end{center}
convert the message into a string of digits, and break the digits up into groups
of threes.
\item By separately encrypting each block of 3 digits, produce the RSA
cyphertext.  Add leading zeros to each encrypted block so that each block of
cyphertext is 4 digits long.
\item You have managed to intercept the private key: $p = 41$, $q = 83$.  Use
these factors to compute $\phi(m)$ and $k^{-1}$.  Use the algorithm you derived
in question 2 of homework 8 to compute $k^{-1}\mod \phi(m)$.

\item Using these values, decrypt the message ``0948 3332 1850 2898 2002 2692 0377 1398''.
\end{enumerate}

\end{exercises}

\end{document}
