\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{fullpage}
\usepackage{amsfonts}
\usepackage[dvips]{graphicx}

\newtheorem{theoreme}{Théorème}

\def\mod{~\mathrm{mod}~}
\def\Z{\mathbb{Z}}

\title{TD 3 de Cryptologie}
\date{Lundi 24 octobre 2005}

\begin{document}
\maketitle

\section{Chiffrement par flot}

\subsection{Génération}

On rappelle qu'on polynôme $P$ est primitif sur un corps $K$ si les
puissances de $X$ engendrent $\left(K[X]/P\right)^*$.

Par exemple $1+X+X^2$ est primitif sur $\mathbb{F}_2$ car il 
génère 
\[ o(X) = \{ X, X^2=X+1, X^3 = X^2+X = 1 \} = \mathbb{F}_2[X]/(X^2+X+1).\]

\begin{enumerate}
\item Montrer que le polynôme irréductible $X^6 + X^3 + 1$
n'est pas primitif sur $\mathbb{F}_2$.
\item Montrer que le polynôme $X^5+X^3+X^2+X+1$ est primitif sur
$\mathbb{F}_2$. Que dire des autres polynômes irréductibles de degré
$5$ sur $\mathbb{F}_2$~?
\end{enumerate}

\subsection{Synchronisation}

\begin{enumerate}
\item Montrer la re-synchronisation après $t$ caractères transmis
suite à une erreur pour le chiffrement par flot auto-synchronisant vu
en cours~:
\begin{eqnarray*}
\sigma_{i+1} & = & (c_{i-t}, c_{i-t+1}, \ldots, c_{i-1}) \\
z_i & = & g(\sigma_i, k) \\
c_i & = & h(z_i, m_i)
\end{eqnarray*}
o\`u l'\'etat initial (public) est $\sigma_0 = (c_{-t}, c_{-t+1},
\ldots,
c_{-1})$, $k$ est la cl\'e, $g$ la fonction produisant le flot de
chiffrement
$z_i$, et $h$ la fonction de sortie.


\item On considère le chiffrement par flot suivant~:
\begin{eqnarray*}
\sigma_{i+1} & = & (m_{i-t}, m_{i-t+1}, \ldots, m_{i-1}) \\
z_i & = & g(\sigma_i, k) \\
c_i & = & h(z_i, m_i)
\end{eqnarray*}

Est-il resynchronisant~?
\end{enumerate}

\section{Sécurité inconditionnelle}

\begin{enumerate}
\item Rappeler le principe du chiffrement \emph{one time pad} (OTP),
et les conditions sous lesquelles il est jugé sûr.
\item Montrer que le chiffrement OTP est inconditionnellement sûr,
c'est-à-dire que l'interception d'un chiffré ne fournit à l'adversaire
aucune information concernant le clair.
\end{enumerate}

\section{Chiffrements historiques~: Vigenère}

On considère pour $n \in \mathbb{N}^*$, un alphabet $\mathcal{A}$ de
taille finie $m$ noté $\mathcal{A} = [0, 1, \ldots m-1]$ et un mot $k$
de $n$ lettres sur $\mathcal{A}$ le chiffrement suivant~:

\begin{eqnarray*}
E : \mathcal{A}^* & \rightarrow & \mathcal{A}^*\\
x_0 x_1 x_2 \ldots x_u & \mapsto & (x_0 + k_0 \mod m)
    \ldots (x_{n-1} + k_{n-1} \mod m) (x_n + k_0 \mod m) \ldots
    (x_u + k_{u \mod n} \mod m)
\end{eqnarray*}
Exemple~:
\begin{center}
\begin{tabular}{|l|cccccccccccccccccc|}
\hline
Clair   & C&E&T&D&E&S&T&M&E&R&V&E&I&L&L&E&U&X\\
\hline
Clef    & L&A&U&R&E&N&T&L&A&U&R&E&N&T&L&A&U&R\\
\hline
Chiffré & N&D&N&U&I&F&M&X&E&L&M&I&V&E&W&E&O&O\\
\hline
\end{tabular}
\end{center}
On déchiffre avec la clef "PAGJWNH".

\begin{enumerate}
\item Pour une clef de chiffrement comment calculer la clef de
déchiffrement~?
\item Pour une clef de taille $m=1$ ce procédé s'appelle le chiffre de
César. Quelle est la difficulté de le casser~?
\end{enumerate}

On suppose qu'on sait que le texte clair est écrit en langue
anglaise, et que la distribution des lettres dans le texte en clair
est indépendant de la position considérée. On donne la distribution de
fréquence observée des lettres en langue anglaise dans la figure
\ref{freq}.

\begin{figure}
\begin{center}
\includegraphics[width=13cm]{freq.eps}
\end{center}
\caption{Fréquence des lettres en langue anglaise.}
\label{freq}
% Source : http://en.wikipedia.org/wiki/Frequency_analysis
\end{figure}

\begin{enumerate}
\setcounter{enumi}{2}
\item Quelle méthode de cryptanalyse du chiffre de César vous inspire
la figure \ref{freq}~?
\item Si on connait la taille de la clef de chiffrement de Vigenère,
que devient la difficulté de casser le chiffrement sous ces
hypothèses~?
\end{enumerate}

Pour deux textes $T_1$ et $T_2$ de même longueur on mesure
$\kappa(T_1, T_2)$ la fréquence du nombre de coïncidences,
c'est-à-dire du nombre de positions dans le texte où la lettre est la
même dans les deux textes.

\begin{enumerate}
\setcounter{enumi}{4}
\item Calculer $\kappa(T, T')$ où $T$ et $T'$ sont deux textes
aléatoires de longueur $m$ sur un alphabet de taille $n$.
\item Pour une langue dont les fréquences d'apparitions des lettres
$p_1, p_2, \ldots p_n$ sont données, calculer
$\kappa_{\mathrm{theorique}}$ de deux textes quelconques écrits dans
cette langue.
\item Montrer que pour deux textes $T$ et $T'$ le chiffrement par un
chiffre de César avec la même clef ne modifie pas la valeur de
$\kappa$.
\item En déduire une méthode d'estimation de la longueur de la clef
d'une chiffrement de Vigenère à partir d'un texte chiffré suffisamment
long.
\end{enumerate}

On donne pour référence $\kappa_{\mathrm{anglais}} = 6.61\%$ et
$\kappa_{\mathrm{francais}} = 7.78\%$.

\end{document}