\documentclass[11pt]{article}
\usepackage{amsmath, alltt, amssymb, xspace, times, epsfig}
\usepackage{amssymb}

\setlength{\evensidemargin}{0in} \setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in} \setlength{\textheight}{8.5in}
\setlength{\topmargin}{0in} \setlength{\headheight}{0in}

\newcommand{\Zn}{\ensuremath{\mathbb{Z}_n}\xspace}
\newcommand{\Zns}{\ensuremath{\mathbb{Z}_n^*}\xspace}
\newcommand{\Zp}{\ensuremath{\mathbb{Z}_p}\xspace}
\newcommand{\Zps}{\ensuremath{\mathbb{Z}_p^*}\xspace}
\newcommand{\Zq}{\ensuremath{\mathbb{Z}_q}\xspace}

\newcommand{\smod}{\ensuremath{\mathrm{mod}\;}}

\newcommand{\DD}{\ensuremath{\mathcal{D}}\xspace}

\newcommand{\Gen}{\ensuremath{\mathsf{Gen}}\xspace}
\newcommand{\Enc}{\ensuremath{\mathsf{Enc}}\xspace}
\newcommand{\Dec}{\ensuremath{\mathsf{Dec}}\xspace}

\renewcommand{\Pr}{\ensuremath{\mathbf{Pr}}\xspace}

\newcommand{\PT}{\ensuremath{\mathsf{PT}}\xspace}
\newcommand{\CT}{\ensuremath{\mathsf{CT}}\xspace}
\newcommand{\Key}{\ensuremath{\mathsf{Key}}\xspace}
\newcommand{\PrivK}{\ensuremath{\mathsf{PrivK}}\xspace}
\newcommand{\eav}{\ensuremath{\mathsf{eav}}\xspace}
\newcommand{\mult}{\ensuremath{\mathsf{mult}}\xspace}

\newcommand{\CC}{\ensuremath{\mathcal{C}}\xspace}
\newcommand{\KK}{\ensuremath{\mathcal{K}}\xspace}
\newcommand{\MM}{\ensuremath{\mathcal{M}}\xspace}
\newcommand{\AAA}{\ensuremath{\mathcal{A}}\xspace}



\newcommand{\note}[1]{\textbf{Note for TA:} #1}\xspace

\begin{document}
%\author{Ninghui Li}
%\date{}
%\maketitle

\thispagestyle{empty}

\noindent \textbf{CS555: Cryptography\hspace*{\fill}Spring 2012}
\begin{center}
{\LARGE Homework \#2}
\end{center}

\paragraph{Due date \& time:} 10:30am on February 16, 2012.
Hand in at the beginning of class (preferred), or email to the TA
(jiang97@purdue.edu) by the due time.

\vspace*{-0.1in}\paragraph{Late Policy:} You have three extra days in
total for all your homeworks.  Any portion of a day used counts as one
day; that is, you have to use integer number of late days each time. If
you emailed your homework to the TA by 10:30am the day after it was due,
then you have used one extra day. If you exhaust your three late days,
any late homework won't be graded.

\vspace*{-0.1in}\paragraph{Additional Instructions:}
The submitted homework must be typed. Using Latex is recommended, but not required.

\begin{description}

\item[Problem 1 (12 pts)] Number theory exercises.  Write out the intermediate steps to show that you understand the algorithm.  Do not include just the final answer.
\begin{itemize}
 \item
Use the Extended Euclidean Algorithm to compute the multiplicative inverse: (a) $17^{-1} \mod 113$, (b) $271^{-1} \mod 1009$.  

 \item
Compute $\gcd(57,93)$ and find integers $s$ and $t$ such that $57s + 93t=\gcd(57,93)$.

 \item
Solve the linear congruence equation $19 x \equiv 8 (\smod 97)$.

 \item
Solve the linear congruence equation $20 x \equiv 8 (\smod 96)$.

 \item
Solve the linear congruence equation $20 x \equiv 8 (\smod 95)$.\\
\end{itemize}

 \item[Problem 2 (6 pts)]
An integer $a$ is called square-free if it is not divisible by the
square of any integer greater than 1. Show that:
\begin{itemize}
 \item
(a) A number $a$ is square-free if and only if $a = \pm p_1 \cdots p_r$, where the $p_i$'s are distinct primes;
 \item
(b) Every positive integer $n$ can be expressed uniquely as $n = ab^{2}$, where $a$ and
$b$ are positive integers, and $a$ is square-free.

\textbf{Hint.  The Fundamental Theorem of Arithmetic may be helpful.}\\
\end{itemize}


 \item[Problem 3 (6 pts)]
Prove that if $k\leftarrow \{0,1\}^n$ is drawn at uniform random, then for any probability distribution $D$ over $\{0,1\}^n$, when $x$ is drawn from the distribution, both $\left(k+x\:\smod 2^{n}\right)$ and $k\oplus x$, where $\oplus$ denotes bit-by-bit XOR, have uniform random distribution.  That is, you need to show that for any $v\in \{0,1\}^n$, we have $\Pr[\left(k+x\mod 2^{n}\right) = v] = \frac{1}{2^n}$ and $\Pr[k\oplus x = v] = \frac{1}{2^n}$\\

 \item[Problem 4 (10 pts)]
(Katz and Lindell.  Page 106.  Exercise 3.1.)\\

 \item[Problem 5 (5 pts)]
(Katz and Lindell.  Page 106.  Exercise 3.2.)\\

 \item[Problem 6 (5 pts)]
(Katz and Lindell.  Page 106.  Exercise 3.4.)\\

 \item[Problem 7 (6 pts)]
(Katz and Lindell.  Page 106.  Exercise 3.6.  With slight modifications.)\\
Let $G$ be a pseudorandom generator where $|G(s)|> 4\cdot |s|$.
\begin{itemize}
 \item (a) Define $G'(s) \overset{\mathsf{def}}{=} G(s 0^{|s|})$.  That is $G'(s)$ invokes $G$ with a concatenation of $s$ and a string of $0$'s of the same length as $s$.  Is $G'$ necessarily a pseudorandom generator?
 \item (b) Define $G'(s) \overset{\mathsf{def}}{=} G(s_1 \cdots s_{n/2})$, where $s=s_1\cdots s_n$.  Is $G'$ necessarily a pseudorandom generator?
\end{itemize}

 \item[Problem 8 (10 pts)]
(Katz and Lindell.  Page 107.  Exercise 3.9.)\\

 \item[Problem 9 (12 pts)]
(Katz and Lindell.  Page 107.  Exercise 3.15.)\\

\item[Problem 10 (13 pts)]  Let $p$ be a 128-bit prime and let \Zp be the set of integers $\{0, ..., p-1\}$.  Consider the following encryption scheme. The secret key is a pair of integers $a,b\in \Zp$ where $a\ne 0$.  To encrypt a message $m\in \Zp$, one chooses $r \leftarrow \Zp$ uniformly at random and compute:
$$\Enc_{a,b}[M] = \langle r,\: (ar + b + m)\,\smod p \rangle $$
\begin{description}
\item[a. (5 pts)] Show that when this scheme is used to encrypt a single message
$m\in\Zp$ the system has perfect secrecy.

\item[b. (8 pts)] Show that the system is insecure when encrypting multiple messages, i.e., it \emph{does not} have indistinguishable \emph{multiple encryptions}.  That is, give an algorithm $\mathcal{A}$ that can win the $\PrivK^\mult$ experiment with non-negligible probability. \\
\end{description}


 \item[Problem 11 (15 pts)]
Conduct an analysis of the security of RC4 and write a summary.  The summary should include: (a) the currently most effective attacks against RC4 (how much time and how many messages are needed, the basic ideas); (b) the recommendation on how to use RC4 for encrypting multiple messages.  One starting point is the wikipedia page for RC4.

\end{description}

\end{document}
