\iffalse

INSTRUCTIONS: (if this is not ps1, use the right file name)

  Clip out the ********* INSERT HERE ********* bits below and insert
appropriate TeX code.  Once you are done with your file, run

  ``latex ps1.tex''

from the Athena shell.  If your TeX code is clean, the latex will exit
back to a prompt.  Once this is done, run

  ``dvips ps1.dvi''

which should print your file to the nearest printer.  There will be
residual files called ps1.log, ps1.aux, and ps1.dvi.  All these can be
deleted, but do not delete ps1.tex.

\fi
\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{latexsym}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newcommand{\handout}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf 6.875J/18.425J Cryptography and
  Cryptanalysis} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\ho}[5]{\handout{#1}{#2}{Instructor:
#3}{Teaching Assistant: #4}{Handout #1: #5}}
\newcommand{\al}{\alpha}
\newcommand{\Z}{\mathbb Z}

\begin{document}
\handout{P1}{DUE: September 12, 2001}{Instructor: Anna Lysyanskaya}
{Teaching Assistant: Moses Liskov}
{*********** INSERT YOUR NAME HERE ***********: PS 1}

I collaborated with *********** INSERT COLLABORATORS HERE *************.

\section*{Problem 1}
We define the Lily problem: given two integers $n$ and $S$, determine
whether $S$ is relatively prime to $\varphi(n)$.  Prove that if the Lily
problem is hard, then RSA is hard to invert.


\bigskip 
{\bf Solution:} \bigskip \noindent

***************** INSERT PROBLEM 1 SOLUTION HERE ***************

\section*{Problem 2} 
Assume one is using RSA with the same modulus $n$ but different
relatively prime public exponents $e_1$ and $e_2$ to encrypt a
message $m$. Prove that the adversary can reconstruct $m$ from the two
encryptions (i.e. from $m^{e_1} \bmod\; n$ and $m^{e_2} \bmod\; n$).

\bigskip
{\bf Solution:} \bigskip \noindent

***************** INSERT PROBLEM 2 SOLUTION HERE **************

\section*{Problem 3}
Assume Alice, Bob and Carol have 3 randomly chosen moduli $n_A$, $n_B$
and $n_C$, s.t. $3$ is a common RSA exponent for all of them (i.e.
$gcd(3,\varphi(n_X))=1$, $X=A,B,C$). A user $U$ encrypts the same message $m$
using their public keys. Show that an adversary can reconstruct $m$
from the $3$ encryptions (i.e. from $m^3 \bmod\; n_A$, $m^3 \bmod\;
n_B$ and $m^3 \bmod\; n_C$).

\bigskip
{\bf Solution:} \bigskip \noindent

***************** INSERT PROBLEM 3 SOLUTION HERE **************

\section*{Problem 4}
Suppose $SQRT(a,p)$ is a polynomial-time algorithm that, if $p$ is
prime and $a$ is a quadratic residue $a \in Z_p^*$, outputs (w.h.p.)
some square root of $a$ mod $p$.  

\smallskip

{\bf (a)} Prove that the following algorithm
is a primality test (i.e. that on a prime input outputs PRIME with
high probability, and on a composite input outputs COMPOSITE with
probability at least $1/2$.)  

\begin{enumerate}
\item If $n=2$, output PRIME.
\item If $n$ is even or of the form $n=p^b$ for some $p, b > 1$,
output COMPOSITE.
\item Choose a random $r \in \{1, \ldots, n-1\}$.  If $gcd(r,n) > 1$,
output COMPOSITE.
\item Compute $x \leftarrow SQRT(r^2 \bmod n, n)$.
\item If $x = \pm r \bmod n$, output PRIME.  Otherwise, output COMPOSITE.
\end{enumerate}

\bigskip
{\bf Solution:} \bigskip \noindent

***************** INSERT PROBLEM 4a SOLUTION HERE **************

\bigskip

{\bf (b)}  Suppose $p = 4m+3$ is a prime and that $a$ is a quadratic
residue modulo $p$.  Prove that $a^{m+1}$ is a square root of $a$
modulo $p$.

\bigskip
{\bf Solution:} \bigskip \noindent

***************** INSERT PROBLEM 4b SOLUTION HERE **************

\bigskip

{\bf (c)}  Use (a) and (b) to devise a primality testing
algorithm for integers equivalent to 3 modulo 4.

\bigskip
{\bf Solution:} \bigskip \noindent

***************** INSERT PROBLEM 4c SOLUTION HERE **************


\section*{Problem 5}
Suppose $p$ is a prime and $g$ is a generator modulo $p$.  

Experiment 1:  Pick $x$ at random in $\{1, \ldots, p-1\}$.
Output $g^x$.

Experiment 2: Pick $x, y$ at random in $\{1, \ldots, p-1\}$.
Output $g^{xy}$.

Prove or disprove: Experiment 1 and Experiment 2 produce
identically distributed outputs.

\bigskip
{\bf Solution:} \bigskip \noindent

***************** INSERT PROBLEM 5 SOLUTION HERE **************

\end{document}