\documentclass[a4paper]{article}

\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{enumerate}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{hyperref}
\usepackage{xspace}

        \newtheorem{theorem}{Theorem}
        \newtheorem{lemma}{Lemma}
        \newtheorem{proposition}{Proposition}
        \newtheorem{corollary}{Corollary}
        \newtheorem{definition}{Definition}
        \newtheorem{assumption}{Assumption}
        \newtheorem{claim}{Claim}
        \newtheorem{problem}{Problem}
        \newtheorem{construction}{Construction}
\DeclareMathOperator*{\expe}{\mathbb{E}}

\newcommand{\class}[1]{{\ensuremath{\mathsf{#1}}}}
\newcommand{\enc}{\ensuremath{\class{Enc}}\xspace}
\newcommand{\dec}{\ensuremath{\class{Dec}}\xspace}
\newcommand{\zo}{\ensuremath{\{0,1\}}\xspace}
\newcommand{\poly}{\ensuremath{\class{poly}}\xspace}
\newcommand{\negl}{\ensuremath{\class{ngl}}\xspace}
\newcommand{\mac}{\ensuremath{\class{Mac}}\xspace}
\newcommand{\ver}{\ensuremath{\class{Vfy}}\xspace}
\newcommand{\sign}{\ensuremath{\class{Sig}}\xspace}
\newcommand{\gen}{\ensuremath{\class{Gen}}\xspace}

\hypersetup{colorlinks,urlcolor=blue}
\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}

\title{CSE 5852: Problem Set 8}
\date{Due: November 28, 2016}
%\author{You}

\begin{document}
\maketitle

In this assignment you'll be doing be working with composite moduli and considering security definitions for signatures.

\section{The group $\mathbb{Z}_n^*$}

Assume that $p = 5, q = 7$ and $N = pq = 35$.

\begin{enumerate}
\item \textbf{5 pts} How many elements are in $\mathbb{Z}_N^*$?

\item \textbf{15 pts} What are the elements of $\mathbb{Z}_N^*$?

\item \textbf{10 pts} For each element of $\mathbb{Z}_N^*$ what is its inverse?  \textbf{Hint:} I recommend putting this question and the previous one in a large table.
\end{enumerate}

\section{The RSA problem}

As in the previous problem consider the setting where $p=5, q=7$ and $N = pq = 35$.

\begin{enumerate}
\item \textbf{5 pts} What is $\phi(N)$?
\item \textbf{15 pts} Recall the RSA problem requires finding an $e>1$ such that $\gcd(e, \phi(N)) = 1$.  How many possible values for $e$ are there between $2$ and $\phi(N)$?  What are they?
\item \textbf{5 pts} Compute $d$ for each possible $e$.  Recall that $d$ is $e$'s inverse $\mod \phi(N)$.  \item \textbf{15 pts} For  one $e, d$ pair show the computation using the extended Euclid algorithm for computing the $\gcd$.  This algorithm is below.  Remember if your output is negative you need to add $\phi(N)$ to make sure its between $1$ and $\phi(N)$.  I recommend using a table of the following form:

\begin{tabular}{c | c | c | c | c| c | c}
$\alpha$ & $\beta$ & $r$ & $\alpha_2$ & $\beta_2$ & $r_2$ &$t$ \\\hline
0 & 1 & e & 1 & 0 & $\phi(N)$ & 
\end{tabular}

\pagebreak
The extended Euclidean algorithm takes input $gcd(a,b)$ and outputs $\alpha, \beta, z$ such that $a \alpha+b \beta = z $ and $z = gcd(a, b)$. This algorithm runs in polynomial time in the size of the inputs.  
\paragraph{Extended Euclidean Algorithm}
\begin{enumerate}
\item Input $a, b$.
\item Set $\alpha =0 , \beta  =1, r=b$.
\item Set $\alpha_2 = 1, \beta_2 = 0, r_2 = a$.
\item While $r\neq 0$:
\begin{enumerate}
\item $t = r_2 / r$.
\item $(r_2, r) = (r, r_2 - t \cdot r)$.
\item $(\alpha_2, \alpha)  = (\alpha, \alpha_2- t\cdot \alpha)$.
\item $(\beta_2, \beta) = (\beta, \beta_2 - t\cdot \beta)$.
\end{enumerate}
\item Output $(\alpha_2, \beta_2, r_2)$.
\end{enumerate}
\end{enumerate}

\section{Definitions of Signatures}
In class we presented the following signature definition called existentially unforgeable under chosen message attack.

$\mathtt{EU-CMA}_{\gen, \sign, \ver, \mathcal{A}}(1^n)$:
\begin{enumerate}
\item Run $(vk, sk)\leftarrow \gen(1^n)$.
\item Give $vk $ to $\mathcal{A}$.
\item For $i=1$ to $k$:
\subitem Receive $m_i$ from $\mathcal{A}$.
\subitem Provide $\sigma_i$ to $\mathcal{A}$.
\item Receive $m', \sigma'$ from $\mathcal{A}$.
\item Output $1$ if and only if $\ver(vk, m', \sigma') =1$.
\end{enumerate}

\begin{definition}
A signature scheme $(\gen, \sign, \ver)$ is existentially unforgeable under chosen message attack if for all PPT $\mathcal{A}$ there exists a negligible $\epsilon(n)$ such that 
\[
\Pr[\mathtt{EU-CMA}_{\gen, \sign, \ver, \mathcal{A}}(1^n) = 1]<\epsilon(n).
\]
\end{definition}

Consider the setting where the sender signs only random messages.  We will still consider a forgery if the adversary is able to produce a signature on an arbitrary message.  We will call this setting \textbf{existentially-unforgeable under random message attack} or EU-RMA.

\begin{enumerate}
\item \textbf{10 pts} Provide an experiment and definition for EU-RMA.
\item \textbf{20 pts} Show that EU-CMA security implies EU-RMA security.  That is show that if there exists a PPT $\mathcal{A}$ that forges in the EU-RMA game with probability $1/p(n)$ for some polynomial $p(n)$ there there is a PPT $\mathcal{A}'$ that forges in the EU-CMA game with an inverse polynomial probability.  \textbf{Explicitly describe the behavior of $\mathcal{A}'$ and how it uses $\mathcal{A}$}.
\end{enumerate}
\end{document}