\documentclass[12pt]{amsart}

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

\usepackage{fullpage}

\begin{document}

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

\maketitle

\section*{Problems}

\begin{problab}{1}
Consider the affine cipher with $\calP=\calC=\Z/n\Z$.  
\begin{enumalph}
\item Suppose $n=541$ and we take the key $(a,b)=(34,71)$.  Encrypt the plaintext $m=204$, and decrypt the ciphertext $c=431$.
\item Eve intercepts a ciphertext from Alice and through espionage she learns that the letter $x \in \calP$ is encrypted as $y \in \calC$ in this message.  Show that Eve can decrypt the message using $O(n)$ trials.  
\item Now suppose that (contrary to Kerckhoffs's principle) the integer $n$ is not public knowledge.  Is the affine cipher still vulnerable if Eve manages to steal a plaintext/ciphertext pair?  How might Eve break the system?
\end{enumalph}
\end{problab}

\begin{problab}{2}
Let $f,g:\R_{\geq 0} \to \R_{\geq 0}$ be continuous functions (in particular, defined on all of $\R_{\geq 0}$), and suppose that $f(x)=O(g(x))$.  Let $F(x)=\int_0^x f(t)\,dt$ and $G(x)=\int_0^x g(t)\,dt$.  Show that $F(x)=O(G(x))$.  If $f,g$ are differentiable, is it true that $f'(x) = O(g'(x))$?
\end{problab}

\begin{problab}{3}
Encrypt the message 
\begin{center}
\textsf{Why is a raven like a writing desk} 
\end{center}
using the Vign\`ere cipher with keyword \texttt{rabbithole}.
\end{problab}

\begin{problab}{4}
[\textsf{Sage}] Decrypt the following message, which was encrypted using a Vign\`ere cipher.
\begin{verbatim}
          mgodt beida psgls akowu hxukc iawlr csoyh prtrt udrqh cengx
          uuqtu habxw dgkie ktsnp sekld zlvnh wefss glzrn peaoy lbyig
          uaafv eqgjo ewabz saawl rzjpv feyky gylwu btlyd kroec bpfvt
          psgki puxfb uxfuq cvymy okagl sactt uwlrx psgiy ytpsf rjfuw
          igxhr oyazd rakce dxeyr pdobr buehr uwcue ekfic zehrq ijezr
          xsyor tcylf egcy
\end{verbatim}
\begin{enumalph}
\item Use the method of displacement coincidences to guess the key length.
\item Use the Kasiski test of matching trigrams to give more evidence for your guess for the key length.  
\item Use frequency analysis with the guessed key length to decrypt the message.
\end{enumalph}
\emph{[You are encouraged to start this by hand and to finish it up by computer.]}
\end{problab}

\begin{problab}{5}
Consider the quadratic map
\begin{align*}
E:\Z/n\Z &\to \Z/n\Z \\
x &\mapsto x^2+ax+b
\end{align*}
with $a,b \in \Z/n\Z$.  Show that if $n \neq 2$, then $E$ is \emph{never} an encryption function.  What can you say about other maps $x \mapsto f(x)$ where $f(x) \in \Z[x]$?
\end{problab}

\begin{problab}{6}
Let $D_n = \{x \in \R^n : \sum_{i=1}^n x_i^2 = 1\}$.  Let $x \in D_n$.  Consider the map
\begin{align*}
D_n &\to \R \\
y &\mapsto x \cdot y = \sum_{i=1}^n x_i y_i.
\end{align*}
Show that this function achieves a unique maximum at $x=y$.  (How does this relate to frequency analysis?)
\end{problab}

\end{document}