\documentclass[12pt]{amsart}

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

\usepackage{fullpage}

\begin{document}

\title[Math 75 Homework \#8]{Math 75: Mathematical Cryptography \\ Homework \#8}
\date{Due Wednesday, 25 May 2016}

\maketitle

\section*{Problems}

\begin{problab}{1} \ 
\begin{enumalph}
\item Let $p=101$.  Compute $\log_2 11$ (using complete enumeration by hand).
\item Let $p=27781703927$ and $g=5$.  Suppose Alice and Bob engage in a Diffie-Hellman key exhange; Alice chooses the secret key $a=1002883876$ and Bob chooses $b=21790753397$.  Describe the key exchange: what do Alice and Bob exchange, and what is their common (secret) key?  \emph{[You may use a computer!]}
\end{enumalph}
\end{problab}

\begin{problab}{2}
Let $p=1021$.  Compute $\log_{10} 228$ using the baby step-giant step method.
\end{problab}

\begin{problab}{3}
In a modified Diffie-Hellman key exchange protocol, Alice and Bob choose a large prime $p$ which they make public, but when they choose a primitive root $g$ for $p$ they decide for safety to keep it secret.  Alice sends $x \equiv g^a \pmod{p}$ to Bob and Bob sends $y \equiv g^b \pmod{p}$ to Alice.  Suppose Eve bribes Bob to tell her the values of $b$ and $y$.  Suppose that $\gcd(b,p-1)=1$.  Show how Eve can determine $g$ from the knowledge of $p,y$ and $b$.
\end{problab}

\begin{problab}{4}
Suppose the ElGamal system is used with $p=71$, $g \equiv 7 \pmod{p}$, public key $g^b \equiv 3 \pmod{p}$ and random integer $a=2$.  What is the ciphertext for the message $x \equiv 30 \pmod{p}$?
\end{problab}

\begin{problab}{5}
Let $E$ be the elliptic curve given by the equation $y^2 = x^3 + x^2 + 1$ over $\F_3$.
\begin{enumalph}
\item Determine all points of $E(\F_3)$.
\item Make an addition table for $E(\F_3)$.
\end{enumalph}
\end{problab}




\end{document}