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

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

\begin{document}
\headers{Math373}{Homework 2}{Due Wed, Jan. 26, 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 {} Modular Arithmetic Tables
\begin{enumerate}
	\item Make addition and multiplication tables for $\Z_3$.
	\item Make addition and multiplication tables for $\Z_6$.
\end{enumerate}

\item Compute the following.  Your answer should be an integer in the set $\{0, 1, \ldots, m-1\}$, where $m$ is the modulus in the given problem.
\begin{enumerate}
	\item $73 - 6173 \pmod{22}$
	\item $342\cdot 825 \pmod{17}$
\end{enumerate}


\item {} 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 Provide your source code.
	\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}
