\section{Symmetric Cryptosystems}

\definition{}
The goal of cryptography is to establish private communication between two parties over
a public channel. The rest of this handout tries to achieve this goal, using the tools we've
developed in the last two sections. \\

In this handout, a ``symmetric cryptosystem'' consists of the following:
\begin{itemize}
	\item[-] A public prime number $p$ (Ideally, a \textit{big} prime number).
	\item[-] $k$, a secret key that is shared between both parties. This is NOT public.
	\item[-] $E_k(m) = c$, a function that uses key $k$ to encrypt message $m$ into a ciphertext $c$.
	\item[-] $D_k(c) = m$, a function that uses key $k$ to decrypt a ciphertext $c$ into message $m$. \\
	\item[-] Of course, $D_k(E_k(m)) = m$. \\
\end{itemize}

We have a good reason for picking a prime $p$. A prime base guarantees that every\footnote[1]{except those $\equiv 0 \pmod{p}$, of course} integer has an inverse mod $p$. Review \ref{mod_has_inverse} and convince yourself that this is true. \\

\vspace{2ex}

We'll assume that the secret key $k$ has been shared beforehand. How such a $k$ is created is beyond the scope of this handout, but those that are curious may look up ``Diffie-Hellman Key Exchange'' (Computerphile offers a
pretty good introduction). \\

\vspace{2ex}

One may wonder why we care about secretly exchanging numbers. Those of you with experience in computing may have an answer: any information---text, images, etc---may be represented as a number. For example, we can encode the 26 letters of the alphabet as the numbers $1 - 26$. Such mappings are called ``encodings.'' \\

\vspace{2ex}

Finally, you will notice that the encryption schemes that follow can only take a limited range of inputs. Indeed, even the cyphers in use today have a limited input size. A simple (though possibly insecure) way to overcome this limitation is to split the message into blocks of a desired size, encrypting each independently.



\vfill
\pagebreak

\problem{Multiplication mod p}
Consider the cryptosystem where
\begin{itemize}
	\item[-] $p$ is a prime (for this problem, fix $p = 11$. Remember, $p$ is public.)
	\item[-] $k$ is an integer
	\item[-] $E_k(m) = k \times m \pmod{p}$
	\item[-] $D_k(c) = k^\star \times c \pmod{p}$
\end{itemize}


\problempart{}
Encrypt $m = 8$ with $k = 5$. \\
Decrypt $c = 3$ with $k = 9$. \\
\textcolor{gray}{In other words, find $E_5(8)$ and $D_9(3)$}

\begin{solution}
	$E_5(8) = 5 \times 8 \equiv 7$ \\
	$D_9(3) = k^\star \times 3 = 5 \times 3 \equiv 4$
\end{solution}

\vfill

\problempart{}
Using this cryptosystem, Nikita sends a message to Sanjit. \\
Looking over Sanjit's shoulder, you find that $E_k(9) = 8$ \\
What key was used? \\
\textcolor{gray}{This is called a \textit{known plaintext attack}. With a good cryptosystem, it will be very difficult to solve this problem.}

\begin{solution}
	$E_k = c = km$ \\
	$E_k \times m^\star = kmm^\star = k$ \\

	$m^\star = 5; k = 7$
\end{solution}

\vfill

\problempart{}<mult_analysis>
If you know many ciphertexts encrypted with the same key, can you find the key used to create them? \\
What range of values can this system effectively encrypt?
Justify all answers.

\begin{solution}

	If the messages are independent, no. However, analysis is possible if the plaintexts have a known structure.

	\linehack{}

	$m \in \{1, 2, ..., 10\}$ \\
	Note that $m$ cannot be $\equiv 0$.

\end{solution}


\vfill
\pagebreak

\problem{The Affine Cipher}
Consider the cryptosystem where
\begin{itemize}
	\item[-] $p$ is a prime (for this problem, fix $p = 541$)
	\item[-] $k = (k_1,\ k_2)$ is a tuple of two integers
	\item[-] $E_k(m) = k_1 \times m + k_2 \pmod{p}$
	\item[-] $D_k(c) = k_1^\star \times (c - k_2) \pmod{p}$
\end{itemize}


\problempart{}
Encrypt $m = 204$ with $k = (34,\ 71)$. \\
Decrypt $c = 431$ with $k = (34,\ 71)$.

\begin{solution}
	$E_k(204) = 34 \times 204 + 71 \equiv 515$ \\

	$k^\star = 366$
	\hfill\textcolor{gray}{Known from \ref{find_inverse}}\\
	$D_k(431) =  366 (431 - 71) \equiv 297$
\end{solution}

\vfill

\problempart{}
Now, let $p = 601$. You know two plaintext-ciphertext pairs:\\
$(m_1,\ c_1) = (387,\ 324)$ \\
$(m_2,\ c_2) = (491,\ 381)$ \\
How would you find $(k_1, k_2)$? \\
\textcolor{gray}{\textit{Note: } You do NOT have to find $k$. The calculations take a lot of manual labor. All you need to do is detail the steps you \textit{would} take if you had a calculator.}

\begin{solution}
	$E_k(387) = k_1 \times 387 + k_2 \equiv 324 \pmod{601}$ \\
	$E_k(491) = k_1 \times 491 + k_2 \equiv 381 \pmod{601}$ \\

	$387k_1 + k_2 - 324 \equiv 491k_1 + k_2 - 381$ \\
	$387k_1 + 57 \equiv 491k_1$ \\
	$104k_1 \equiv 57$ \\
	So $104k_1 + 601a = 57$ \\

	Solve $104k_1 + 601a = \gcd(601, 104) = 1$, then scale.
	\hfill\textcolor{gray}{Remember, 601 is prime.} \\
	$k_1 \equiv -2964 \equiv 41 \pmod{601}$. \\

	Substitute $k_1 = 41$. \\
	$(k_1, k_2) = (41, 83)$

\end{solution}
\vfill

\problempart{}
If you only know one message and its corresponding ciphertext, can you find the encryption key? \\
If you know many ciphertexts encrypted with the same key, can you find the key used to create them? \\
What range of values can this system effectively encrypt?
Justify all answers.

\begin{solution}
	Given $m$ and $c$, you cannot find $k_1$ or $k_2$.

	\linehack{}

	Given any number of ciphertexts, you cannot find $k$.

	\linehack{}

	$m \in \{1, 2, ..., 540\}$

	Other answers are the same as those to \ref{mult_analysis}.
\end{solution}

\vfill
\pagebreak
