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

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{listings}
\usepackage{xcolor}

\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
 
\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},   
    commentstyle=\color{codegreen},
    keywordstyle=\color{magenta},
    numberstyle=\tiny\color{codegray},
    stringstyle=\color{codepurple},
    basicstyle=\footnotesize,
    breakatwhitespace=false,         
    breaklines=true,                 
    captionpos=b,                    
    keepspaces=true,                 
    numbers=left,                    
    numbersep=5pt,                  
    showspaces=false,                
    showstringspaces=false,
    showtabs=false,                  
    tabsize=2
}
 
\lstset{style=mystyle}
\lstset{language=Python}

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


\begin{document}
\headers{Math373}{Homework 7}{Due Wed, Mar. 1, 2023}

%\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 {} The Discrete Logarithm.  Evaluate the following in $\F_{23}$.
\begin{enumerate}
	\item $\log_{14}(22)$
	\item $\log_{15}(8)$
\end{enumerate}

\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$ in $\F_p$.
\begin{enumerate}
	\item Alice and Bob choose $p=11$ and $k=2$.  Find the order of $k$ in $\F_p$.  Is $k$ a primitive root?  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 $k$.
	\item In part (d), the intention is to find the secret key $k$ by using an efficient attack, but the numbers are small enough that you could find $k$ using brute force.  Carry out the attack again with $p$ and plaintext/ciphertext pairs $(m_1,c_1)$, $(m_2,c_2)$ as shown below.
	\begin{align*}
	p &= 49651418153203334334343025759447351841028834755961145327 \\
	m_1 &= 1442506475715854841019941447847762099575753178605423941 \\
	c_1 &= 11799308873252204640351057233329997891282186998411681189 \\
	m_2 &= 8741291516595786171636620315162766721085153317204173630 \\
	c_2 &= 35688851452468689917269021024163741705031317552447325666
	\end{align*}
\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}
