\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{\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 \#1}
\end{center}

\paragraph{Due date \& time:} 10:30am on January 26, 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 (25 pts)]
Write a program that breaks the Vigen\`{e}re cipher automatically.  That is, assuming that the plaintext is a case-insensitive English text using only the 26 letters (without space or any other symbol), your algorithm should take in a ciphertext encrypted under the Vigen\`{e}re cipher, and automatically output the plaintext.

\textbf{Hint.}  For telling whether a shift value is correct, you can consult the paragraph titled ``An improved attack on the shift cipher'' in the textbook on Pages 13--14.  You are encouraged to come up with a different way for doing this as well.

\begin{itemize}
 \item
Include the core part of the source code of your implementation (leave out input processing), and state the language you use. Also email a zip file of your source code to the TA.  

 \item
Present the plaintext for the attached ciphertext file, computed using your program.\\
\textbf{Ciphertext}: (Use the latex source file for the ciphertext.)
\begin{alltt}
rimqessfntwpwtelqdeerkwdpezrfxjumpqxqqurxhifdjaffirlffnsyahrxtou
tszwaxwvdspwqbpidwhitvpdnvizstnexzrhpujfcwmfvihdcspkqbrvpczztxug
nfdlhdzreheyrkworezrnrpcmatrsdesifqpwwfvnxdmssnsysgltzbgwyqbpidw
oegidgnvxvgbyhivvgwrffcixogiskcwlvuchwpjdfnxewamcwcsxefwbrhvqvcm
fmfyryotoefopscwweprfwnpxkmelxmwaxtxfjecmbqejkvfyxuqnxxfbnzhqfag
gpduzkdoclnzbupvespxhkvfomeqvtazbfdsranxwvabemogpsbgiupveqvictsb
yhqzrgiiwdlpqbtmcvsstrsoctazqbemabfsutfzaxaueeeymjygxiqipkadlvpg
psbgiupvbofwlffedezrrptthszruqpsbdssniofltifzprcbfvsgkcusiycqige
ohpamgnpbfgudczcacbfithmfvrrrimqemabglttcogidgvscftjyjafzeizcoqv
aanvtrrbmpqggeivhpltboeickbpywqbfiiystprpsevtkojyiphuipswmtxkhbh
ttfzaxfvrmcwcsxefwbrperusidsssgvowzmpiaapehfotqffscjpftrsooptkcs
pepwgwxeqfhsdzqapiwbyhfvresmsoesrhuirfaqfxqfgltdsusspghwtuhpnedf
lsjkqsjtfcysvpvbginspsbvwonvqofmcxzznsydyimrbetxeoctazqbemabzsgv
kjoiedeipuapoidbpvnghprvmducufzmzaeofxgfbhwceqvickwgtgmdcvdrqilr
prrwxxbtnvkdgsvioqsmooykdiwusqeoesjerdzqbigeizcolptoehcvgtlweizt
izcodqmyvrvjidsexubvxkvndlmfqxdsfflonmnrpujfcwmflmizgusiafrxxtom
wcbcfwxszfesnfrezjidseemfxtdpvemfwfmcwsbdmnzrxductzfkoaceiodemoo
yqtrbtelqgrwrysnpwmfrxwvffqsdspsbgiulxucaeacmtpggfrxwvffpbuggmcw
csxefwbriyspcifwpeacmtpggfrwrysnpwfvnxeicwlfxmpececuminfboteoopb
macptzgusiabrxxdsqlhnigxwvgfdgtszihrffxsdsqmuwwdfpfhbmbgzfxizhgl
pehipxtsbvtkwdlpxmovtrybmpqphxrfaqfxmhvscrzmjwqqhvtdsdsezwfqhtfz
axazbknismlxqrgirybpwssmuehiojdipoaybssszjxsteazgtfiewaxwviotxqr
xmcxrpxeprvxxfbtesfvrvtximlxucasuzbwpwfwteiffzasisewpthspugweihr
gvdtqqgistfjxmzoyxdyoooshsexwvwsprofltizcovikwsehbsemcxojicwcsni
ysaxdkvfcaugrxwvitpviwypurqflgdwzmcrzdsedurxwvsmpgffbrxttszrfwrv
ufiooefwbrxjwogsxjrhxeodlwqwaxwvgvavqargdlfuzjfvryczhfowfogihnvj
nliwyppjqfcxmwamuisrfmdwakhlgqpgfsqggzajyexggseicwthqhuixisonvkd
gmdeyfjwfcyelvbgzvoszickwtfrocawizhvemabnpiysfqjugnvvlworxtogxwz
gjdehwbppkwpysrhuigzuiesrbbxqvworjafpiskcjygdwzmcrhfzrqgrpurghtz
qbvriysgtjfvnqternprf
\end{alltt}

%\note{Generate a ciphertext of sufficient length, so that it can be broken by the standard method.}
\end{itemize}

 \item[Problem 2 (5 pts)]
Consider the following enhancement of the Vigen\`{e}re cipher.  We again assume that the plaintext is a case-insensitive English text using only the 26 letters (without space or any other symbol).  To encrypt a plaintext $m$ of length $n$, one first uniformly randomly generate a string over the alphabet $[A..Z]$ of length $13$.  Then insert this string into the beginning of the plaintext.  That is, we construct a string $x=x_1x_2\ldots x_{n+13}$, such that $x_1\cdots x_{13}$ is the string we have generated, and $x_{14}\cdots x_{n+13}$ is the plaintext string.  We then construct a string $y$ as follows: $y_i=x_i$ for $1\leq i\leq 13$, and for $i\in [14,n+13]$, $y_i$ is the result of using $y_{i-13}$ to encrypt $x_i$; that is, when the $x_i$'s and $y_i$'s are treated as numbers in $[0..25]$, we have $y_i = ((x_i + y_{i-13}) \mod 26)$.  We then apply the Vigen\`{e}re cipher to the string $y$, making sure that the key length is not a multiple of $13$.

\begin{itemize}
 \item
Write the Pseudo-code of the algorithms \Enc,\Dec for this cipher.  

\textit{Note that this cipher offers randomized encryption.  The same plaintext encrypted twice result in different ciphertexts. Also note that the ciphertext of a plaintext is always 13 characters longer than the plaintext.  This is necessary for randomized encryption.}

 \item \textbf{Optional Question.  No credit.}  

Describe how you would break the above encryption scheme.

\textit{Do it only if you have the time and enjoy doing it.  The instructor does not know the answer.  If you are able to break the cipher, the solution will be presented in class.  You get to present it if you choose to do so.}\\

%\note{I haven't thought of a way to break this cipher.  Try to see whether this is too hard. }
\end{itemize}

 \item[Problem 3 (10 pts)]
Consider an encryption scheme in which $\MM = \{a,b,c\}$,
$\KK=\{K_1,K_2,K_3\}$ and $\CC=\{1,2,3,4\}$.
The keys are chosen uniformly randomly; in other words, $\Pr[\Key=K_1] = \Pr[\Key=K_2] = \Pr[\Key=K_3] = 1/3$,
and the encryption matrix is as follows:
$$
\begin{array}{||c|c|c|c||}\hline
     & a & b & c
 \\ \hline
 K_1 & 1 & 2 & 3
 \\ \hline
 K_2 & 2 & 3 & 4
 \\ \hline
 K_3 & 3 & 4 & 1
 \\ \hline
\end{array}
$$

\begin{itemize}
 \item
Assuming the plaintext distribution in which each plaintxt is chosen with the same probability, i.e., $\Pr[\PT=a]=\Pr[\PT=b]=\Pr[\PT=c]=\frac{1}{3}$.
\begin{itemize}
 \item \textbf{(2 pts)}
Compute the probability distribution of the ciphertext \CT, that is, give the probabilities for $\Pr[\CT=1]$, $\Pr[\CT=2]$, $\Pr[\CT=3]$, $\Pr[\CT=4]$.

 \item \textbf{(2 pts)}
Compute the joint distribution of $\PT$ and $\CT$, by filling out a table like the one below.
$$
\begin{array}{||c|c|c|c||}\hline
     & \PT=a & \PT=b & \PT=c
 \\ \hline
 \CT=1 & \frac{1}{9} &  &
 \\ \hline
 \CT=2 &  &  &
 \\ \hline
 \CT=3 &  &  &
 \\ \hline
 \CT=4 & & & \\ \hline
\end{array}
$$

 \item \textbf{(1 pt)}
Are $\PT$ and $\CT$ independent?
\end{itemize}

 \item  \textbf{(5 pt)}
Repeat the questions above, assuming the following plaintext distribution, $\Pr[\PT=a]=\frac{1}{2}$, $\Pr[\PT=b]=\frac{1}{3}$, $\Pr[\PT=c]=\frac{1}{6}$.\\
\end{itemize}

 \item[Problem 4 (16 pts)]
Read Chapter 1 of the PDF file ``Mathematics for Computer Science'' by Lehman and Leighton.  (Available from http://www.cs.princeton.edu/courses/archive/spr10/cos433/mathcs.pdf)

\begin{itemize}
 \item \textbf{(2 pts)} Check whether the following statements are propositions.
   \begin{itemize}
     \item (a)
      1,2 and 3 are prime numbers.
     \item (b)
      $\forall x\in\mathbb{R},\exists y\in\mathbb{R}, x^2-x+1>y$.
     \item (c)
      Let's try to prove the existence of pseudorandom generators!
     \item (d)
      Let $a,b>1$ with $b\nmid a$, then $gcd(a,b)=gcd(b,a$ mod $b)$.
  \end{itemize}

 \item \textbf{(4 pts)} Check whether the following propositions are tautology.\\
 ($P,Q,R$ are boolean variables)
  \begin{itemize}
     \item (a)
     $P\wedge\neg P\Rightarrow Q$

     \item (b)
     $(P\Rightarrow Q)\Leftrightarrow\neg P\vee Q$
     \item (c)
     $(P\Rightarrow Q)\wedge(Q\Rightarrow P)$
     \item (d)
     $(P\Rightarrow Q)\wedge(R\Rightarrow \neg Q)\wedge R \Rightarrow\neg P$
  \end{itemize}

 \item \textbf{(8 pts)} Prove the following propositions.
   \begin{itemize}
     \item (a) (2 pts)
     A complete number is not a prime number.(Note: complete number refers to a number which is equal to the sum of its proper divisors. For example, 6 and 28 are complete numbers since $6=2\times3=1+2+3, 28=2\times2\times7=1+2+4+7+14$.)

     \item (b) (3 pts)
     For all $n\geq 4$, $2^n < n! < n^n$

     \item (c) (3 pts)
     There is no rational number $x$ for which $x^3+x+1=0$.
     
     \textbf{Hint: a rational number can be written as $a/b$ such that $a$ and $b$ are not both even numbers.}
  \end{itemize}
  
 \item \textbf{(2 pts)} Order the following functions in terms of their growth: $\log n$, $n^{\log n}$, $n^{100}$, $1.1^n$, $e^n$, $n!$.  
 
 \textit{This is not related to the reading here, but serves as a review for concepts used in later topics.  Consult, for example, wikipedia page on big-o notation if you are unfamiliar with this.}\\
\end{itemize}

%\note{Need to figure out some question to ask, to help motivate students to actually read it. }

 \item[Problem 5 (9 pts)]
This question asks you to consider the relationship between keyspace size $|\mathcal{K}|$, plaintext space size $|\mathcal{M}|$, ciphertext space size $|\mathcal{C}|$, for symmetric ciphers, which we require that
$$\forall m \forall k \Dec_{k}(\Enc_k(m)) = m.$$
\begin{itemize}
 \item
For the pair $(|\mathcal{M}|,|\mathcal{C}|)$, identify which of the following choice is true, and show that your answer is correct.
\begin{itemize}
 \item (a)
It must be that $|\mathcal{M}| = |\mathcal{C}|$.
 \item (b)
It must be that $|\mathcal{M}| \geq |\mathcal{C}|$, and it is possible that $|\mathcal{M}| > |\mathcal{C}|$.
 \item (c)
It must be that $|\mathcal{M}| \leq |\mathcal{C}|$, and it is possible that $|\mathcal{M}| < |\mathcal{C}|$.
 \item (d)
Each of the following is possible: $|\mathcal{M}| > |\mathcal{C}|$, $|\mathcal{M}| = |\mathcal{C}|$, and $|\mathcal{M}| < |\mathcal{C}|$.
 \item (e)
None of the above is true.
\end{itemize}

 \item
Choose among (a)-(e) for the pair $(|\mathcal{M}|,|\mathcal{K}|)$, and justify your answer.

 \item
Choose among (a) -(e) above for the pair $(|\mathcal{C}|,|\mathcal{K}|)$, and justify your answer.\\
\end{itemize}

 \item[Problem 6 (9 pts)]
Repeat the previous problem for a symmetric-key cipher that satisfies perfect secrecy.\\

 \item[Problem 7 (6 pts)]
(Katz and Lindell.  Page 41.  Problem 2.5.)\\
Prove or refute: Every encryption scheme for which the size of the key space equals the size of the
message space, and for which the key is chosen uniformly from the key space, is perfectly secret.\\

 \item[Problem 8 (10 pts)]
(Katz and Lindell.  Page 42.  Problem 2.7.)\\
Prove that Definition 2.1 implies Definition 2.4.

\textbf{Def. 2.1}: An encryption scheme (\Gen,\Enc,\Dec) over a message space $\MM$ is perfectly secret if for every probability distribution over $\MM$, every message $m\in\MM$, and every ciphertext $c\in\CC$ for which $\Pr[C=c]>0$: $\Pr[M=m|C=c]=\Pr[M=m]$.  \\
\textbf{Def. 2.4}: An encryption scheme (\Gen,\Enc,\Dec) over a message space $\MM$ is perfectly secret if for every adversary \AAA it holds that $\Pr[\PrivK^\eav_{\AAA,\Pi}=1]=\frac{1}{2}$.

\textbf{Hint from textbook.} Use Exercise 2.6 to argue that perfect secrecy holds for the uniform distribution over any two plaintexts(and in particular, the two
messages output by $\AAA$ in the experiment). Then apply Lemma 2.3.

\textbf{Exercise 2.6}: Say encryption scheme (\Gen,\Enc,\Dec) satisfies Definition 2.1 for all distributions over $\MM$ that assign non-zero probability to each $m\in\MM$ (as per the simplifying convention used in this chapter). Show that the scheme satisfies the definition for all
distributions over $\MM$ (i.e. including thoes that assign zero probability to some messages in $\MM$). Conclude that the scheme is also perfectly
secret for any message space $\MM'\subset\MM$.

\textbf{Lemma 2.3}: An encryption scheme (\Gen,\Enc,\Dec) over a message space $\MM$ is perfectly secret if and only if for every probability distribution over $\MM$, every $m_0,m_1\in\MM$, and every $c\in\CC$: $\Pr[C=c|M=m_0]=\Pr[C=c|M=m_1]$.\\

 \item[Problem 9 (10 pts)]
(Katz and Lindell.  Page 42.  Problem 2.8.)\\
Prove the second direction of Proposition 2.5. That is, prove that Definition 2.4 implies Definition 2.1.

\textbf{Hint.} If a scheme $\Pi$ is not perfectly secret with respect to Definition 2.1, then Lemma 2.3 shows that there exist messages $m_0,m_1\in\MM$
and $c\in\CC$ for which $\Pr[C=c|M=m_0]\neq\Pr[C=c|M=m_1]$. Use these $m_0$ and $m_1$ to construct an $\AAA$ for which $\Pr[\PrivK^\eav_{\AAA,\Pi}=1]>\frac{1}{2}$.


\end{description}

\end{document}
