\documentclass{article}

\author{JC}

\title{HW 2 solutions}

\begin{document}

\maketitle

\begin{enumerate}


\item The key length is 11, the key is ``allyourbase'', the plaintext is
   Poe's ``The cask of Amontillado''.

\item We follow the same general lines as the example of computing the expected
   value of an IOC from class.

   Our space of outcomes consists of pairs of form $(c_1 \ldots c_m, d_1 \ldots d_m)$,
   where the probability of this outcome is $p_{c_1} \ldots p_{c_m} p_{d_1} \ldots p_{d_m}$;
   here $p_{\bf char}$ is the frequency of {\bf char} in English.  
   
   For each $i$ we define a random variable $X_i$ as follows. The value of
   $X_i$ is $1$ if $c_i$ plus the $(i -1) \mbox{ mod } 3 + 1$-th character of
   ``bcd'' mod $26$ equals $d_i$ plus the $(i -1) \mbox{ mod } 3 + 1$-th character of
   ``cdb'' mod $26$. A little thought shows that we can describe $X_i$ as follows
\begin{enumerate} 
\item If $i$ is congruent to $1$ or $2$ mod $3$, then $X_i =1$
   on events such that $c_i  = d_i +1$ mod $26$ and 0 elsewhere.
\item If $i$ is congruent to $0$ mod $3$, then $X_i =1$
   on events such that $c_i + 2 = d_i$ mod $26$ and 0 elsewhere.
\end{enumerate}


    The IOC between the encryption of $c_1 \ldots c_m$ with ``bcd'' and
    that of $d_1 \ldots d_m$ with ``cdb'' is exactly $\sum X_i/m$.
    So we compute $E(X_i)$ for each $i$ and use linearity of expectation.

    Start with $i =1$. $E(X_i)$ is the sum over all outcomes of the
    probability of the outcome times the value of $X_i$ on that outcome, which is either
    zero or one. So $E(X_1)$ is the sum of the probabilities for those outcomes such that
    $c_1 = d_1 + 1$ mod 26, or to use more probabilistic language it is the probability
    of the event ``$c_1 = d_1 + 1$'' mod 26.

    If you know some probability, you will see very quickly that the answer
    is the sum $p_b p_a + p_c p_b + p_d p_c + \ldots p_z p_y + p_a p_z$.
    
    If you don't see this, we can calculate it from scratch. We are computing
    the sum over all pairs $(c_1 \ldots c_m, d_1 \ldots d_m)$ such that
   $c_1 = d_1 + 1$ mod 26 of the product $p_{c_1} \ldots p_{c_m} p_{d_1} \ldots p_{d_m}$, 
    or more formally
\[
    \sum_{ (c_1 \ldots c_m, d_1 \ldots d_m), \,\, c_1 = d_1 + 1    } p_{c_1} \ldots p_{c_m} p_{d_1} \ldots p_{d_m}.
\]

    It is easy to see that by distributivity of times over plus this factors as
\[
    \left ( \sum_{ (c_1, d_1), \,\, c_1 = d_1 + 1    } p_{c_1} p_{d_1} \right ) \times 
    \left ( \sum_{ (c_2 \ldots c_m, d_2 \ldots d_m) } p_{c_2} \ldots p_{c_m} p_{d_2} \ldots p_{d_m} \right )
\]
   Applying distributivity again 
\[
    \sum_{ (c_2 \ldots c_m, d_2 \ldots d_m) } p_{c_2} \ldots p_{c_m} p_{d_2} \ldots p_{d_m} 
  = \left ( \sum_{c_2} p_{c_2} ) \right ) \times \left ( \sum_{c_m} p_{c_m} ) \right ) \times
   \left ( \sum_{d_2} p_{d_2} ) \right ) \times \left ( \sum_{d_m} p_{d_m} ) \right ) 
\]
   and this last expression is just $1$ because obviously $\sum_{\bf char} p_{\bf char} = 1$. 
   So $E(X_1)$ is $p_b p_a + p_c p_b + p_d p_c + \ldots p_z p_y + p_a p_z$,
   a quantity we abbreviate by $S$.

   We get the same value $S$ whenever $i$ is congruent to $1$ or $2$ mod $3$. 
   When $i$ is congruent to $0$ an identical argument gives 
   $E(X_i) = T$ where $T = p_a p_c + \ldots p_x p_z + p_y p_a + p_z p_b$. 


   So when $m=3 n$ we get an expected value of $n(2 S +T)/(3 n) = 2 S/3  + T/3$.
   When $m = 3 n +1$ we get $(n(2 S + T) + S)/(3 n + 1)$ and
   when $m = 3 n + 2$ we get $(n(2 S + T) + 2 S)/(3 n + 2)$.  For large $m$ we see the answer will be
   close to $2 S/3  + T /3$ whatever the congruence status of $m$.

   A little Maple calculation shows that $S$ is about $0.033$ and $T$ is about $0.039$,
   so the expected value is about $0.035$.        

\item  Looking at the defintions of the OTP and the Vigenere cipher, it is easy to see
    that for any Vigenere key $k$, the result of encrypting $P$ by the OTP method with key $X$,
    then doing Vigenere encryption with key $k$ is the same as doing Vigenere encryption
    with key $k$ and then doing OTP encryption with key $X$.
   
    This means that we have not really added any security at all. Someone who has the
    final ciphertext can just subtract the well-known string $X$, and then they have
    $P$ Vigenere encrypted with $k$ and can do the usual Vigenere encryption.

    The big problem here was that Vigenere encryption and OTP encryption ``commute'',
    that is the order in which they are performed does not affect the result.
    More generally we can see the following issue: if we use some cryptosystem Z
    in place of the Vigenere cipher then we are not adding any security if
    the result of applying Z (with some key $k$) to $P$ can be computed easily by someone who
    knows $X$ and  the result of applying Z to $P$ enxrypted by the OTP method with key $X$. 

     


\end{enumerate}

\end{document}

