\documentclass[12pt]{amsart}

\input{../../TeX/macros}

\usepackage{fullpage}

\begin{document}

\title[Math 75 Homework \#4]{Math 75: Mathematical Cryptography \\ Homework \#4}
\date{Due Wednesday, 27 April 2016}

\maketitle

\section*{Problems}

\begin{problab}{1}
Let 
\[
A=\begin{pmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 10 
\end{pmatrix}. \]
For which $n$ is the matrix $A$ invertible over $\Z/n\Z$?  Find its inverse if $n=100$.
\end{problab}

\begin{problab}{2}
Alice uses the Hill cipher, encrypting the plaintext
\begin{center}
\textsf{Consistency is the last refuge of the unimaginative}
\end{center}
to get the ciphertext
\begin{center}
\texttt{voqimugocogmttfkxvlvdynhawugtfrsksoizgaanlygk}
\end{center}
to send to Bob using blocks of size $m=3$ (and $n=26$).  Playing the role of Eve, hack Alice's encryption key $A \in M_3(\Z/26\Z)$.  The matrix key spells out a keyword: what is it?  

After you find the key, notice that Alice has not followed the protocol correctly.  Find two plaintexts that encrypt to the same ciphertext.
\end{problab}

\begin{problab}{3}
The Hill cipher succumbs to a known plaintext attack if sufficiently many plaintext-ciphertext pairs are known.  It is even easier to break the cipher if Eve can trick Alice into encrypting a chosen plaintext, a \emph{chosen plaintext attack}.  Describe such an attack.
\end{problab}

\begin{problab}{4}
Let $n \in \Z_{>0}$.  We consider the row-reduction algorithm over $\Z/p\Z$ where $p$ is prime.  Show that every nonzero element in $\Z/p\Z$ has an inverse, so that $\F_p=\Z/p\Z$ is a \emph{field} and the methods of linear algebra apply.

Find an explicit polynomial $f(x) \in \Q[x]$ of degree $3$ such that no more than $f(n)$ operations in $\F_p$ are required by the row-reduction algorithm for computing the determinant of a matrix in $M_n(\F_p)$.  How many of these operations are inversions?
\end{problab}

\begin{problab}{5}
Decrypt the message
\begin{center}
\texttt{CLV SSH = MMBVC RDMVE PFZII EAVYS XFTHS FNMOB RRPDH VBSQH}
\end{center}
with the following Enigma settings: 
\begin{verbatim}
Walzenlage (Rotors): I V III
Ringstellung (Ring setting): 13 06 24
Steckerverbindungen (Plug connections): AU PB EF IQ RH ZL DT MS CG KN
Kenngruppen: KIJ TFR BVC ZAE
\end{verbatim}
\emph{[Hint: The message is in German!]}
\end{problab}

\begin{problab}{6}
Read Section 15.1 (pages 368--376) of \emph{The Pleasures of Counting} by Koerner (\verb|http://www.math.dartmouth.edu/~m75s16/koerner.pdf|) and do Exercises 15.1.1--15.1.3.
\end{problab}

\end{document}