\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}
\usepackage{graphicx}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}

\begin{document}
\headers{Math373}{Homework 1}{Due Wed, Jan. 19, 2022}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve the following problems.  All written work must be your own.  See the course syllabus for detailed rules.

\begin{enumerate}

\item {} The Caesar cipher.
\begin{enumerate}
	\item Encrypt the message ``exchange all assets'' using a Caesar cipher with a forward shift of 5 characters.
	\item Decrypt the following message, which has been encoded with a Caesar cipher.
	\begin{center}
\begin{verbatim}
DPYLA OLTVU LFAVT VYYVD
\end{verbatim}
	\end{center}
\end{enumerate}

\item {} [JJJ 1.\{9,10\}.c] Let $d=\gcd(16261,85652)$.  Use the extended Euclidean algorithm to find integers $u$ and $v$ such that $16261u + 85652v = d$.

\item {} [\textbf{To be submitted with HW2 on Jan 26, 2022.}]  A grayscale image with depth $d$ is a two-dimensional array whose entries are in $\{0,\ldots,d-1\}$.  For example, the following image $T$ has depth $4$.
\begin{center}
\hfill 
$T = \left[
\begin{array}{cccc}
	0 & 0 & 2 & 1 \\
	0 & 0 & 2 & 3 \\
	3 & 3 & 2 & 1
\end{array}
\right]$
\hfill
\begin{tabular}{c|cccc}
plaintext & 0 & 1 & 2 & 3\\
\hline
cyphertext & 3 & 1 & 0 & 2
\end{tabular}
\hfill
$C = \left[
\begin{array}{cccc}
	3 & 3 & 0 & 1 \\
	3 & 3 & 0 & 2 \\
	2 & 2 & 0 & 1
\end{array}
\right]$
\hfill ~
\end{center}
When the plaintext image $T$ is encrypted with a substitution cypher whose key is displayed in the center table, the result is the cyphertext image $C$, displayed on the right.
The images \texttt{A.png} (depth $32$), \texttt{B.png} (depth $64$), \texttt{C.png} (depth $128$), \texttt{D.png} (depth $256$) contain grayscale images that have been encrypted with a simple substitution cypher; the keys are unknown.
\begin{center}
\begin{tabular}{c|c}
\includegraphics[width=0.4\textwidth]{A-scaled.png} &
\includegraphics[width=0.4\textwidth]{B-scaled.png} \\
\texttt{A.png} (32 colors, scaled) &
\texttt{B.png} (64 colors, scaled) 
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{c|c}
\includegraphics[width=0.4\textwidth]{C-scaled.png} &
\includegraphics[width=0.4\textwidth]{D-scaled.png} \\
\texttt{C.png} (128 colors, scaled) &
\texttt{D.png} (256 colors, scaled) 
\end{tabular}
\end{center}

\begin{enumerate}
	\item Find a formula for the size of the keyspace for a substitution cypher on an image with depth $d$.  If a computer can check 1 million keys per second, how many years would it take to decrypt \texttt{A.png} and \texttt{D.png}?
	\item Write some efficient code that breaks this cryptosystem, and use your code to decrypt the given images without knowledge of the key.  The python template file \texttt{im\char`_sub\char`_cypher.py} contains some routines used to encrypt, decrypt, and save image files.  To use the template, you will need the common python packages numpy and the Python Image Library.  Note: you will probably need to test and debug your code on images that you encrypt and for which you know the encryption key.  Hint: when designing your algorithm, exploit that nearby pixels are likely to have similar brightness levels.
	\item Describe in English how your algorithm works.
	\item Give the 4 plaintext images that your algorithm produces when running on the given files \texttt{A.png} (depth $32$), \texttt{B.png} (depth $64$), \texttt{C.png} (depth $128$), and  \texttt{D.png} (depth $256$).  
\end{enumerate}
\end{enumerate}
\end{document}
