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

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}
\newcommand{\ord}{\mathrm{ord}}
\newcommand{\priv}{\mathrm{priv}}
\newcommand{\pub}{\mathrm{pub}}

\begin{document}
\headers{Math373}{Homework 8}{Due Fri, Mar. 21, 2014}

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

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

\newcommand{\compicon}%
{%
	\begin{tikzpicture}[scale=0.15]%
		\draw[double] (0,0) rectangle (1,1) ;
		\begin{scope}[yshift=-5pt]
			\draw (-0.5, -0.5) rectangle (1.5, 0) ;
		\end{scope}
	\end{tikzpicture}
}


\makeatletter
\def\@oddfoot{}
\makeatother

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

\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 2.8] Alice and Bob agree to use the prime $p=1373$ and the base $g=2$ for communications using the ElGamal public key cryptosystem.
\begin{enumerate}
	\item Alice chooses $a=947$ as her private key.  What is the value of her public key?
	\item Bob chooses $b=716$ as his private key, so his public key is $B = 2^{716} = 469$.  Alice encrypts the message $m=583$ using the ephemeral key $k=887$.  What is the ciphertext $(c_1, c_2)$ that Alice sends to Bob?
	\item Alice decides to choose a new private key $a=299$ with associated public key $A=2^{299} = 34$.  Bob encrypts a message using Alice's public key and sends her the ciphertext $(661, 1325)$.  Decrypt the message.
	\item Now Bob chooses a new private key and publishes the associated public key $B = 893$.  Alice encrypts a message using this public key and sends the ciphertext $(693, 793)$ to Bob.  Eve intercepts the transmission.  Help Eve by solving the discrete logarithm problem $2^b \equiv 893 \pmod{1373}$ and use the value of $b$ to decrypt the message.
\end{enumerate}

\item {} In this problem, we modify the ElGamal public key cryptosystem to create a new cryptosystem called ElGamalAdd.  Instead of multiplying the message $m$ by the shared secret, this system adds $m$ to the shared secret.  Specifically, we publish a large prime $p$ and a primitive root $g$ in $\F_p$ of large prime order.  The key space consists of all pairs $(k_\priv, k_\pub)$ of the form $(a, g^a)$ where $a\in \F_p^*$.  The encryption function follows.
\begin{algo}
$e_{k_\pub}(m)$, where $k_\pub$ has the form $g^a$:\+\\
Choose an ephemeral key $k$ in $\F_p$ at random.\\
Compute $c_1 = g^k$ and $c_2 = m + (g^a)^k$.\\

Return $(c_1, c_2)$
\end{algo}
\begin{enumerate}
	\item What is the associated decryption function?
	\item If Eve wishes to decrypt messages sent with the ElGamalAdd cryptosystem, she may want to solve the corresponding ElGamalAdd Problem, or EGAP.  The EGAP problem is to compute $m$ given the information $p, g, g^a, g^k, m + g^{ak}$ that is available to Eve.  Prove that EGAP and the Diffie--Hellman Problem (DHP) have the same level of difficulty.  \textbf{Note:} this means you must show (1) how a black box solution to DHP can be used to solve EGAP efficiently, and (2) how a black box solution to EGAP can be used to solve DHP efficiently.
	\item In light of the result in part (b), discuss the relative strengths of the ElGamal and ElGamalAdd cryptosystems.
\end{enumerate}

\item {} [JJJ 2.16] Decide whether each of the following are true or false.
\begin{enumerate}
\item $x^2 + \sqrt{x} \in O(x^2)$.
\item $k^{300} \in O(2^k)$.
\item $2^k \in O(e^k)$.  
\item $e^k \in O(2^k)$.
\item $k^r \in O(e^{\sqrt{k}})$ for each positive real number $r$.
\item $e^{\sqrt{k}} \in O(e^{rk})$ for each positive real number $r$.
\end{enumerate}

\item {} Shanks's Algorithm.  Let $p=211$ and let $g=8$.
\begin{enumerate}
	\item Find the order $N$ of $g$ in $\F_p$.
	\item Compute List 1 in Shanks's Algorithm for computing $\log_g(h)$.
	\item Use Shanks's Algorithm to find each of the following discrete logarithms.  In each case, explicitly give List 2.
	\begin{enumerate}
		\item $\log_g(122)$
		\item $\log_g(150)$
		\item $\log_g(200)$
	\end{enumerate}
\end{enumerate}

\end{enumerate}
\end{document}
