% YOU ALSO NEED THE FILE bitstorm2.eps AVAILABLE IN THIS DIRECTORY IN
% ORDER TO PROPERLY COMPILE THIS FILE.
\nopagenumbers
\font\largerbold = cmbx10 scaled \magstep1
\def\mod{{\ \rm mod\ }}
\magnification=\magstep1
\rightline{\sevenrm April 20, 2000}\smallskip
\centerline{\largerbold Crypto review for the final exam}

\bigskip

\noindent {\bf Exam conditions} Again, the final exam will be ``open book,
open notes''. You may bring to the exam anything additional to help
you which is {\sl non-living}.
\smallskip
\count100=1
\def\xy{\smtableskip &\number\count100 .~\global\advance\count100 by 1} 
{\offinterlineskip
\def\tablerule{\noalign{\hrule}}
\def\tableskip{\omit&&height2pt \cr}
\def\smtableskip{\omit&&height1pt \cr}
\halign{#\strut&\vrule width .01in\ {\vtop{\raggedright\noindent
\hsize=2.06in  # %\strut
}}&\vrule
width.01in#\cr
\tablerule\tablerule\tableskip\tableskip
&Define, explain, or briefly discuss each of the terms below.&\cr
\tableskip\tableskip\tableskip
\tablerule\tableskip
\xy  Enigma&\cr
\xy  VENONA&\cr 
\xy  DES &\cr
\xy  One time pad&\cr 
\xy Depth &\cr
\xy  ``Randomness'' &\cr
\xy  Binary &\cr
\xy  The discrete log problem&\cr 
\xy  Polynomial time algorithm &\cr
\xy  Exponential time algorithm &\cr
\xy  Encryption &\cr
\xy  Encryption key &\cr
\xy  Decryption key &\cr
\xy  Hash &\cr
\xy  Algorithm&\cr 
\xy  Man in the middle attack&\cr 
\xy  Certificate authority &\cr
\xy  Plain text &\cr
\xy  Cipher text  &\cr
\xy  Secret Sharing &\cr
\xy  Steganography&\cr
\xy  One-way function &\cr
\xy  Factoring and cryptanalysis&\cr
\xy  Trapdoor in a cryptosystem &\cr
\xy  Pseudo-random&\cr 
\xy  Collision (hashing)&\cr
\xy  Public key encryption&\cr
\xy  Exhaustive search&\cr
\tableskip\tablerule\tablerule}
}

%was hsize 3.5
\def\zz #1{\leftline{{\hskip 2.2in} \vtop{\hsize =3.3in \noindent #1
}}\medskip}
\vfootnote*{Many more, per capita, than in the
U.~S.}
\vskip -5.47in


\zz{A.~Our \underbar{messages} are positive integers, such as {\bf
2}3278{\bf 7}. A hashing algorithm is applied to these messages.
The result is the product of the first and last digits of the
message. Since $2\cdot 7=14$, 14 is the hash value of the message
232787. Are collisions possible? If they are, exhibit two messages
with the same hash. Can 43 be a hash value for some message?
Estimate how many distinct messages there could be whose hashes are
all different.}

\zz{B.~John receives the message, ``Darling, I love you!'',
supposedly from Gilda. Describe a crypto environment in which he can
be reasonably certain that the message was actually from Gilda.}

\zz {C.~A committee of seven people wish to share a secret (which can
be thought of as a number!) so that any majority of the committee (at
least four members) must agree to have access to the secret. Describe
how to do this. Illustrate your description with a worked-out
example. (Simple examples are fine!)}

\zz {D.~There are many cell phones in western Europe\raise .5ex
\hbox{*}. Describe a reasonable strategy by which two cell phones,
after being connected by the network, could ``negotiate'' and then
transport a long conversation with some likelihood of privacy. Due to
the size of cell phones, the dynamics of the market, and the structure
of the network, it is not reasonable to suppose that every individual
cell phone can carry information about every other individual cell
phone.}

\zz {E.~On what basis do people decide whether or not an encryption 
system is secure? Explain your answer.}

\zz{F.~The only words in a language are {\bf A$=111$} and 
{\bf B$=0000$}. Two sentences in the language are xor'd with the
\underbar{same} random bitstream, and we observe:}
\rightline{${\rm First\ sentence\ flipped:}\ 01110\, 11010\, 01000\,
11100\, 1$;} 
\rightline{${\rm Second\ sentence\ flipped:}\ 01101\, 01101\, 10100\,
11111\, 0$.}
\smallskip
\zz{Use this information to find good candidates for the original
sentences.}  

\input epsf
\vskip -.91in
\line{\qquad\qquad\ \ {\epsfxsize=.76in\epsfbox{bitstorm2.eps}\hfil}}

\vfil\eject\end

MD5 RC5 stream cipher block cipher shift register crib

z1 := 111000011111100000000
z2 := 111111000000000000111
dirt := 100101110110100111001
\vfil\eject\end


if hashing gives a 8 bit stream how many distinct messages are
required before there are two with an identical hash? 










