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

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

\begin{document}
\headers{Math373}{Homework 6}{Due Wed, Feb. 23, 2022}

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

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

\makeatletter
\def\@oddfoot{}
\makeatother

\newcommand{\K}{\mathcal{K}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\C}{\mathcal{C}}


\newcommand{\ord}{\mathrm{ord}}
\newcommand{\F}{\mathbb{F}}

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

\begin{enumerate}

\item {} [JJJ 1.46] Explain why the exclusive-or cipher is not secure against a chosen plaintext attack.  Demonstrate the attack by computing the key given the plaintext/ciphertext pair with $m=1100101001$ and $c=0011001100)$.

\item {} [JJJ 1.48] Why modular arithmetic?  Alice and Bob decide to use a multiplicative cipher that does not involve modular arithmetic.  That is, they use $\K = \{p\st \mbox{$p$ is a prime}\}$, $\M = \C = \{1,2,3,\ldots\}$, and 
\begin{align*}
e_k(m) &= km  &  d_k(c) &= c/k.
\end{align*}
Eve intercepts the following ciphertexts:
\begin{align*}
c_1 &= 19157632841654891 &
c_2 &= 39493517444969867 &
c_3 &= 32351977451572789
\end{align*}
Illustrate that this cipher lacks property (3) by finding the key $k$.

\item {} Modular exponentiation cipher.  Consider the cipher where $\K$ is the set of primitive roots in $\F_p$, $\M = \Z_{p-1}$, $\C = \F_p^*$, and $e_k(m) = k^m$.
\begin{enumerate}
	\item Alice and Bob choose $p=11$ and $k=2$.  Encrypt the message $6$ and decrypt the message $3$.
	\item Prove that the encryption function is injective, and describe the decryption function.
	\item Does this cipher have property (1) (i.e. given $k\in \K$ and $m\in \M$, it is easy to compute $e_k(m)$)?  Does it have property (2) (i.e. given $k\in \K$ and $c\in \C$, it is easy to compute $d_k(c)$)?
	\item Here, we illustrate that this cipher is vulnerable to a chosen plaintext attack.  Alice and Bob choose $p=2687$ and a secret key.  Eve manages to discover the plaintext/ciphertext pairs $(1866, 1864)$ and $(1231, 2565)$.  Find the secret key.
\end{enumerate}

\item {} The Discrete Logarithm.  Evaluate the following in $\F_{23}$.
\begin{enumerate}
	\item $\log_{14}(22)$
	\item $\log_{15}(8)$
\end{enumerate}

\item {} Diffie--Hellman Key Exchange.  Alice and Bob select and publish
\begin{align*}
    p &= 918398656403699\\
    g &= 581330380946540.
\end{align*}
\begin{enumerate}
\item Alice selects the secret integer $a=382114$.  Compute $A = g^a$.  Alice sends $A$ to Bob.
\item Bob selects the secret integer $b=1744891346$.  Compute $B = g^b$.  Bob sends $B$ to Alice.
\item What modular computation does Alice perform to obtain the shared secret?  As Alice, compute the shared secret.
\item What modular computation does Bob perform to obtain the shared secret?  As Bob, compute the shared secret.
\end{enumerate}


\end{enumerate}
\end{document}
