\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 13}{Due Wed, Apr 26, 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}}
\renewcommand{\poly}[1]{\mathbf{#1}}

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

\begin{enumerate}

\item Alice and Bob wish to share a secret using Elliptic Curve-based Diffie--Hellman.  They agree on the curve $E$ given by $y^2 = x^3 + 14x + 2$ over $\F_{31}$ and the base element $g=(12,10)$.
\begin{enumerate}
    \item Bob picks $b=10$ as his private exponent.  What should Bob send to Alice?
    \item Alice sends $A = (18, 17)$ to Bob.  Compute Alice and Bob's shared secret.
    \item \textbf{[Challenge (optional)]} Find Alice's private exponent $a$.  In other words, find $a$ such that $g^a = A$.  This is an instance of the Elliptic Curve Discrete Logarithm Problem (ECDLP).
\end{enumerate}

\item \emph{Programming with elliptic curves.}  In the following, we write code to multiply points and compute powers of points in the elliptic curve group $E$ over $\F_p$, where $p$ is prime and $E$ is given by $y^2 = x^3 + Ax + B$.  We assume that $B\ne 0$ so that we may represent the identity element in $E$ as the special pair $(0,0)$.
\begin{enumerate}
    \item Write code for a function $\texttt{ec\_mult}(p,A,B,x_1,y_1,x_2,y_2)$ that multiplies the points $(x_1,y_1)$ and $(x_2,y_2)$ in the elliptic curve group $E$ over $\F_p$, where $E$ is given by $y^2 = x^3 + Ax + B$.  Be sure to handle the cases where the inputs or output are the identity point.  For example, $\texttt{ec\_mult}(p,A,B,x_1,y_1,0,0)$ should return $(x_1,y_1)$ (modulo $p$) and $\texttt{ec\_mult}(p,A,B,x,y,x,-y)$ should return $(0,0)$.  Submit your code.
    \item Implement the fast power algorithm in a routine $\texttt{ec\_fast\_power}(p,A,B,x,y,n)$ that computes $(x,y)^n$ where  within the elliptic curve group $E$ over $\F_p$.  Submit your code.
\end{enumerate}

\item Alice and Bob use Elliptic Curve ElGamal to send an encrypted message.  They use the curve $E$ over $\F_p$, where $p=942857$ and $E$ is given by $y^2 = x^3 + 152654x + 95765$.  They agree to use base point $g=(395876, 217218)$, which happens to have prime order $q=470749$ in $E$.
\begin{enumerate}
    \item Check your code from problem \#2 by verifying the following: 
    \begin{enumerate}
        \item $g^{500} = (485216, 167677)$
        \item $g^q = (0,0)$, our representation for the identity element in $E$, and
        \item $g^{q+1} = g$.
    \end{enumerate}
    \item Alice selects $a=199481$ as her secret exponent.  What should Alice send to Bob?
    \item Bob wants to send the message $m=(358621, 245390)$ to Alice.  He picks random element $k=304364$.  What is the corresponding ciphertext $(c_1,c_2)$ that he should send to Alice?
    \item Later, Alice receives a second encrypted message $(c_1, c_2)$ from Bob, where $c_1 = (21125, 331345)$ and $c_2 = (448432, 307568)$.  Decrypt the message.
\end{enumerate}


\end{enumerate}
\end{document}
