%Do not change 
\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
% You may add the packages you need here
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}
\newcommand\nd{\textsuperscript{nd}\xspace}
\newcommand\bset{\{0,1\}}
\begin{document}
%Do not modify
\begin{textblock*}{4cm}(-1.7cm,-2.3cm)
\noindent {\large CS 555-Fall 2018} 
\end{textblock*}
%Do not modify other than putting your name where stated
\begin{textblock*}{8cm}(-1.5cm,-1cm)
\noindent {Name: } 
\end{textblock*}
%Do not modify other than typing your acknowledgement where stated
\begin{textblock*}{13.5cm}(-1.5cm,0cm)
\noindent {Purdue E-mail: } 
\end{textblock*}
\begin{textblock*}{18.5cm}(-1.5cm,0.5cm)
\noindent \textit{\footnotesize  I collaborated with (...). I affirm that I wrote the solutions in my own words and that I understand the solutions I am submitting.} 
\end{textblock*}
\vspace{1cm}
%Do not modify other than typing the homework number after #
\begin{center}
\textbf{\Large Homework 3} \\ 
\textbf{Due date: Thursday, November 1st\nd 3:00 PM}
\end{center}
%Rest should contain your solution for the homework. Feel free to improvise in ways that you believe make grading easier.
\subsection*{Question 1 (20 points)} 
Let $e=3$, $\langle N,e \rangle$ be an RSA public key, and $m_1 \neq m_2 \in \mathbb{Z}^*_N$ satisfy the condition that $m_2 = 2m_1 + 1 \mod{N}$. 

Show that: given $\langle N, e=3, c_1 = m_1^e, c_2 = m_2^e\rangle$ and the fact that $m_2 =2m_1 +1 \mod{N}$, one can construct a PPT adversary $\mathcal A$ that can recover both $m_1$ and $m_2$ 

\subsection*{Question 2 (20 points)}
Let $p \geq 5$ be prime and let $E$ be the elliptic curve given by  $y^2 = x^3 + Ax +B$ mod $p$ where $4A^3 + 27B^2 \neq 0$ mod $p$. Let $P_1, P_2 \neq \mathcal O$ be the points on $E$, with $P_1=(x_1,y_1)$ and $P_2=(x_2,y_2)$. Prove the following statements: 
\\
 	If $P_1 = P_2$ and $y_1 \neq 0$ then $P_1+P_2 = 2P_1 = (x_3,y_3)$ with 
 	\begin{equation}
 		\begin{split}
 			&x_3 =\big[m^2 -2x_1 \mod{p}\big]
 			\\&y_3 =\big[m\cdot(x_1-x_3) - y_1 \mod{p}\big]
 		\end{split}
 	\end{equation}
 	where $m = \bigg[\displaystyle\frac{3x_1^2+A}{2y_1}\bigg]$
\subsection*{Question 3 (15 points)} 
Consider a specific cyclic group $\mathbb G$ of prime order $q$ generated by $g\in \mathbb{G}$. Let $\mathcal A$ be an efficient algorithm with the following property: 
	$$\Pr[u \stackrel{\$}{\leftarrow} \mathbb{G}, x \leftarrow \mathcal{A}(\mathbb{G},g,u): g^x = u] = \epsilon$$
	Then we can construct an efficient algorithm $\mathcal B$ with the following property:
	$$\forall u \in \mathbb{G}~~~\Pr[ x \leftarrow \mathcal{B}(\mathbb{G},g,u): g^x = u] = \epsilon$$
	where the probability is over the random choices made by $\mathcal B$
\subsection*{Question 4 (25 points)} 
Fix $N \in \mathbb{N}$ such that $N,e \geq 1$ and $\mathtt{gcd}\left(e,\phi(N)\right) = 1$. Assume that there is an adversary $\mathcal{A}$ running in time $t$ such that
\[ \Pr\left[\mathcal{A} \left(\left[x^e \mod{N} \right] \right)=x \right] \geq 0.01 \]
where the probability is taken over the uniform choice of $x \in \mathbb{Z}_N^*$. Show how to construct an adversary $\mathcal{A}'$ with running time $t' = O\left( poly\left(t, \log_2 N\right) \right)$ such that \[ \Pr\left[\mathcal{A}' \left(\left[x^e \mod{N} \right] \right)=x \right] \geq 0.99 \ . \]
\noindent {\bf Hint: } Use the fact that $y^{1/e}\cdot r = \left(y \cdot r^e \right)^{1/e} \mod{N}$. Here, $y^{1/e} = y^d \in\mathbb{Z}_N^*$ where $d$ is a (secret) number such that $ed \equiv 1 \mod{\phi(N)}$.  Also use the fact that, given $r\in\mathbb{Z}_N^*$, we can find a number $r^{-1}$ such that $rr^{-1} = 1 \mod{N}$.
\subsection*{Question 5 (20 points)} 
Define a fixed-length hash function $(\mathsf{Gen}, H)$ as follows:
\begin{enumerate}
	\item[(a)] $\mathsf{Gen:}$ on input $1^n$, run $\mathcal G(1^n)$ to obtain $(\mathbb{G}, q, h_1)$ and selects $h_2, \cdots, h_t \leftarrow \mathbb{G}$. Output $s := \langle \mathbb{G},q, (h_1, \cdots, h_t) \rangle$ as the key.
	\item[(b)] $H:$ given a key $s := \langle \mathbb{G},q, (h_1, \cdots, h_t) \rangle$ and input $(x_1, \cdots, x_t)$ with $x_i \in \mathbb{Z}_q$, output $H^s(x_1,\cdots, x_t) = \prod_i h_i^{x_i}$
\end{enumerate}
Prove that if the discrete-logarithm problem is hard relative to $\mathcal G$ and $q$ is prime, then for any $t = \mathsf{poly}(n)$ this construction is a fixed length collision-resistant hash function
\end{document}