\section{Introduction}

\subsection{Crypto system}

\begin{definition}
Let $\Plain$ denote a finite set of messages (also called plaintexts),
$\C$ a finite set of ciphered texts and $\K$ a finite set of keys. \\
For each $k \in \K$, we associate an {\it encryption} function $e_k: \Plain \map \C$
and a {\it decryption} function $d_k: \C \map \Plain$ such that $d_k(e_k(x)) = x$, for all $x \in \Plain$.
The set of $e_k$'s will be noted by $\E$ and 
$\D$ will designate the set of $d_k$'s.\\
$(\Plain, \C, \K, \E, \D)$ defines a {\it cryptosystem}.

\end{definition}

\scalebox{0.5}{\includegraphics{L7.eps}}

\subsection{Classic simple cryptosystems}

Most of the following cryptosystems will be defined over $\bbZ_{26}$, 
so to correspond with the english alphabet of $26$ symbols, but they can be 
generalized to $\bbZ_m$.

\subsubsection{Shift cipher}
Let $\Plain = \C = \K = \bbZ_{26}$.\\
For $0 \leq K \leq 25$ and $x, y \in \bbZ_{26}$ define 
$$e_K(x) = x + K \; mod \; 26$$
and
$$d_K(x) = y - K \; mod \; 26$$
For the particular case where $K = 3$, the scheme is called
the {\bf Caesar Cipher}.

\subsubsection{Substitution cipher}
Let $\Plain = \C = \bbZ_{26}$.\\
$\K = \{ \pi | \pi \; is \; a \; permutation \; over \; the \; symbols \; 0, 1, \ldots , 25 \; of \; \bbZ_{26} \}$\\
For $\pi \in \K$ and $x, y \in \bbZ_{26}$ define
$$e_{\pi}(x) = \pi(x)$$
and
$$d_{\pi}(y) = \pi^{-1}(y)$$
Note that the {\it shift cipher} is a special case of the {\it substitution cipher} in wich
only $26$ of the possible $26!$ permutations are used.

\subsubsection{Affine cipher}
Let $\Plain = \C = \bbZ_{26}$,\\
$\K = \{(a,b) \in \bbZ_{26} \times \bbZ_{26} \; | \; gcd(a, 26) = 1 \}$.\\
For $K = (a,b) \in \K$ and $x, y \in \bbZ_{26}$ define
$$e_K(x) = ax + b \; mod \; 26$$
and
$$d_K(y) = a^{-1}(y - b) \; mod \; 26$$
The functions used are called {\it affine} functions, thus the name
of the cryptosystem.
Note that the {\it affine cipher} is a special case of the {\it substitution cipher} in wich
only $26*12$ of the possible $26!$ permutations are used.
Notice that if $a = 1$, we have the {\it shift cipher}.

In the {\it substitution cipher}, once a key is chosen, each
alphabetic character is mapped to a unique alphabetic character.  These are called
{\it monoalphabetic} ciphers.  These ciphers are vulnarable to attacks in which we
can use the frequency of certain letters of the language in use.  In the next cipher we present
the well known {\it Vigen\`ere cipher}, which is a {\it polyalphabetic} cipher.

\subsubsection{Vigen\`ere Cipher}
Let $\Plain = \C = \K = (\bbZ_{26})^m$, for some fixed $m \in \bbZ_{26}$.\\
For $K = (k_1, k_2, \ldots, k_m)$ define
$$e_K(x_1, x_2, \ldots, x_m) = (x_1 + k_1, x_2 + k_2, \ldots, x_m + k_m)$$
and
$$d_K(y_1, y_2, \ldots, y_m) = (y_1 - k_1, y_2 - k_2, \ldots, y_m - k_m).$$
All operations are performed in $\bbZ_{26}$.


\subsubsection{Vernam's One-time pad}
Let $n \geq 1$ and \\
let $\Plain = \C = \K = (\bbZ_2)^n$.\\
For $K \in (Z_2)^n$, define
$$e_K(x) = (x_1 + K_1, \ldots, x_n + K_n) \; mod \; 2$$
and
$$d_K(y) = (y_1 + K_1, \ldots, y_n + K_n) \; mod \; 2.$$
The famous {\it one-time pad} has unconditional perfect secrecy.
If, when using the {\it Vigen\`ere} cipher, we use a new random key for 
each encryption 
then \comment{, as long as the plaintext has no repetitions,  } we have perfect secrecy.  This can be 
viewed as a generalisation of the {\it One-time pad} from a binary to an arbitrary alphabet .

\subsubsection{Hill cipher}
Let $m$ be a fixed integer and\\
let $\Plain = \C = (\bbZ_{26})^m$, $\K = \{m\times m \; invertible \;
over
\; \bbZ_{26} \}$.\\
For $K \in \K$, define
$$e_K(x) = x\cdot K$$
and
$$d_K(y) = y\cdot K^{-1}$$

\subsection{Cryptanalysis:  classes of attacks}
There are 4 basic classes of attacks on a cryptosystem.  In every case,
the
encryption-decryption scheme is known to everyone and an attacker $Oscar$ is
interested
in recovering the plaintext corresponding to a specific ciphertext, or
even
more drastically, deduce the decryption key of the scheme in use. \\
The four classes of attacks are presented in the following table:
\begin{center}
\begin{tabular}{|l||l|}
\hline
Classe & escription\\
\hline
\hline
{\it ciphertext-only} & Oscar tries to deduce the plaintext or
decryption\\
                      & key using only the ciphertext.\\
\hline
{\it known plaintext} & Oscar has access to a series of
ciphertext-plaintext\\
                      & pairs.\\
\hline
{\it chosen plaintext} & Oscar is given the ciphertexts corresponding \\
			& to the plaintexts of his choice. \\
\hline
{\it chosen ciphertext} & Oscar is given the plaintexts corresponding \\
			& to the ciphertexts of his choice.\\
\hline
\end{tabular}
\end{center}
