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

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

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

\title{TD 2 de Cryptologie}
\date{Lundi 17 octobre 2005}

\begin{document}
\maketitle

\section{Fonctions de hachage}

Pour les fonctions de hachage ou de compression suivantes, dire si
elles sont résistantes à l'inversion, aux collisions au sens fort, et aux
collisions au sens faible.

\begin{enumerate}

\item 
\begin{eqnarray*}
h : \{ 0, 1\}^{4n} & \rightarrow & \{ 0, 1\}^{n}\\
x_1 || x_2 & \mapsto & g(x_1 \oplus x_2),\quad |x_1|=|x_2|=2n
\end{eqnarray*}
où $g : \{ 0, 1\}^{2n} \rightarrow \{ 0, 1\}^n$ est une fonction de compression
résistant fortement aux collisions et $\oplus$ désigne le ou exclusif.

\item
\begin{eqnarray*}
j : \Z/n\Z \times \Z/n\Z & \rightarrow & \Z/n\Z\\
(x_1, x_2) & \mapsto & x_1^2 + x_2
\end{eqnarray*}
où $n = pq$ est produit de deux nombres premiers.

\begin{eqnarray*}
k : \Z/n\Z \times \Z/n\Z & \rightarrow & \Z/n\Z\\
(x_1, x_2) & \mapsto & x_1^2 + x_2^2
\end{eqnarray*}
où $n = pq$ est produit de deux nombres premiers.

\item $l$ définie comme $j$ pour $n=p$ premier.
\item $m$ définie comme $k$ pour $n=p$ premier.

\end{enumerate}

\section{SHA-1 et variations}

L'algorithme de hachage SHA-1 produit des hachés de $160$ bits ou $20$
octets. Par exemple :

\begin{verbatim}
SHA-1("Test SHA1") = c8d73cf5447f4db6ab75ed0bcf88f11cb3f723ed
\end{verbatim}

\begin{enumerate}
\item Combien y-a-t-il de hachés théoriquement possibles ?
\item En prenant $n$ messages aléatoires et en supposant que les
résultats sont équirépartis dans l'espace d'arrivée, quelle est la
probabilité de générer une collision avec le haché donné en exemple ?
\item En déduire l'espérance du nombre de hachés nécessaires pour
obtenir une collision avec l'exemple.
\end{enumerate}

Alice et Bob s'échangent souvent des fichiers via un canal non
sûr. Une fois un fichier transféré, Alice et Bob se téléphonent pour
confirmer le haché du fichier.

\begin{enumerate}
\setcounter{enumi}{3}
\item En supposant qu'un adversaire peut lire le fichier en cours de
transmission et le remplacer par un fichier de son choix et qu'il
dispose de ressources lui permettant de calculer le haché de $200$Mo
de données en une seconde, quelle est l'espérance du temps de calcul
nécessaire à l'adversaire pour remplacer un fichier de $2$Mo par un
fichier de même taille? On supposera que le coût de calculer des
hachés est linéaire en la taille de l'entrée.

\item Pour gagner du temps, Alice et Bob ne vérifient en général que
les 2 premiers octets du haché. Que devient le travail de l'adversaire
dans ce cas?
\end{enumerate}

\end{document}