\documentstyle[11pt]{article}

\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}

\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcounter{questnum}
\newcommand{\question}[1]{
\vspace{.1in}
  \refstepcounter{questnum}
{\bf \medskip Problem \thequestnum: }}

\newcommand{\titledquestion}[2]{
 \refstepcounter{questnum}
{\bf \medskip Problem \thequestnum:} #2 {\normalsize (#1 pts) \\}}

\newcommand{\answerspace}{\verb+                                  +
\underline{\makebox[2.0in]{}}}
\newcommand{\smanswerspace}{\underline{\makebox[0.5in]{}}}

\setlength{\topmargin}{-0.5 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{8.75 in}
\setlength{\textwidth}{6.5 in}
\setlength{\parindent}{0.0 in}

\begin{document}

{\large 
CS294-3: Algorithms in the real world \hfill Assignment 2 (Cryptography)\\[.03in]
Due: Wednesday Oct 1, 1997\\[.1in]
}

\question{??}

Assume you design an encryption scheme with a single round
DES (instead of the usual 16 rounds and ignoring the initial and
final permutations).  If you know
a message cipher pair ($m_1,c_1$) for a key $k$ 
for the values given below, what is $m_2$ assuming 
$c_2 = DES1_k(m_2)$.
Assume the following hexidecimal values for $m_1, c_1$ and $c_2$.

\begin{eqnarray*}
m_1 & = & \mbox{\tt 3F72D4E6 04CD825B} \\
c_1 & = & \mbox{\tt 04CD825B 8E25E338} \\
c_2 &= & \mbox{\tt 04CD825B 327C7D29}
\end{eqnarray*}

If you show the first 2 (leftmost) hexidecimal digits of $m_2$ that
will convince me you know the rest.

\question{}

Assume we have a $3 \times 3$-bit s-box used in a block ciphers.
For each of the following three substitutions explain what is wrong.

\begin{center}
\begin{tabular}{cccc}
  Input & out$_1$  & out$_2$ & out$_3$ \\
   0 & 2 & 0 & 4 \\
   1 & 5 & 4 & 3 \\
   2 & 3 & 1 & 7 \\
   3 & 7 & 5 & 2 \\
   4 & 0 & 2 & 5 \\
   5 & 4 & 6 & 0 \\
   6 & 3 & 3 & 6 \\
   7 & 1 & 7 & 1
\end{tabular}
\end{center}

\question{}
\begin{description}
\item[(a)] 
Assuming $p$ and $q$ are primes,
express $x^{-1} \bmod pq$ as a positive power of $x$.  

\item[(b)] 
Given public key $e = 3$, $n = 391$ encode the value 45 using RSA.

\item[(c)] 
Assuming the same public key,
decode the value 105 (you might want to write a short program to do it).

\item[(d)] 
In RSA for some $n$ lets say $e = 3$ (a standard choice in some systems).  If
I accidentally give away $d$ show how one can use this information to
factor $n$.
\end{description}

\newpage

\question{}
\begin{description}
\item[(a)] 
Using ElGamal Encryption with the public key $p = 11, g= 7, y=5$
encrypt the value 9 with random $k=3$.

\item[(b)] 
Decrypt the pair (2,2).

\item[(c)] 
Given $p = 11$ why is 10 a bad value for $g$?
\end{description}

\question{}
\begin{description}
\item[(a)] 
Generate the first 4 bits of the BBS random bit generator
assuming that $n = 77, r_0 = 39$.

\item[(b)] 
For an arbitrary Blum integer $n = pq$
give an upper bound on the period of the generator (how many iterations
it takes before it repeats).  This need not be the strongest upper-bound
but you will get more credit the stronger it is.
\end{description}

\end{document}