\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 11}{Due Wed, Apr 12, 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{\ZZ}{\mathbb{Z}}
\renewcommand{\O}{\mathcal{O}}

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

\newcommand{\Dsig}{D_{\mathrm{sig}}}

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

\begin{enumerate}
\item Samantha uses the ElGamal signature scheme with prime $p=29669$ and primitive root $g=7$.
\begin{enumerate}
	\item Samantha selects private signing exponent $a=8216$.  Her private signing key is $(p,g,a)=(29669,7,8216)$.  What is her public verification key?
	\item Samantha wishes to sign a document $D$.  At first, she picks random element $k=12480$, but she realizes this will not work.  Why not?
	\item Instead, Samantha picks $k=20233$.  What is the value of $k^{-1}$?  (Hint: the answer is not 7499.)
	\item Given that $D=24910$, find the signature $\Dsig$.
\end{enumerate}

\item WVU decides to use the ElGamal signature scheme to sign its official messages.  It publishes the public verification key $(p,g,A) = (64937,24,32107)$.  Which of the following document/signature pairs, if any, are authentic?  Show your work.
\begin{enumerate}
	\item $D = 57917$, $\Dsig = (38546, 36585)$
	\item $D = 35829$, $\Dsig = (59960, 34982)$
	\item $D = 4737$, $\Dsig = (4196, 48679)$
\end{enumerate}

\item Let $E$ be the elliptic curve given by $y^2 = x^3 -27x + 55$.  In class, we showed that 
\[ [(2,3)(3,1)](-1,-9) = [(-1,-9)](-1,-9) = (-1,-9)^2 = (34/9, 71/27) .\]
\begin{enumerate}
    \item Compute $(3,1)(-1,-9)$.
    \item Use part (a) to verify that $(2,3)[(3,1)(-1,-9)] = (34/9, 71/27)$.
\end{enumerate}


\end{enumerate}
\end{document}
