\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{fullpage}
\usepackage{amsfonts}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage[T1]{fontenc}

%\usepackage[dvips]{graphicx}
\def\application#1#2#3#4{%                                                      
\left\{\begin{array}{lcl}#1 & \longrightarrow & #2\\ #3 & \longmapsto &         
#4\end{array}\right.}

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

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

\title{TD 5 de Cryptologie}
\date{Lundi 14 novembre 2005}

\begin{document}
\maketitle

\section{Cryptosystème Elgamal}

On se place dans un groupe $G$ cyclique de taille $q$, de générateur
$g$.

\subsection{Génération de clef}

\begin{itemize}
\item Alice choisit $x$ au hasard dans $\left\{0, 1, \ldots, q-1\right\}$.
\item Alice calcule $h = g^x$ dans $G$ (si $G$ est noté
multiplicativement).
\end{itemize}
$x$ est la clef secrète d'Alice; $h$, $G$, $g$ et $q$ sa clef publique.

\begin{enumerate}
\item Pour le groupe $G= (\Z/13\Z, +)$ calculer $q$, le nombre de
générateurs et les décrire.
\item Même question pour le groupe $G = (\Z/42\Z,+)$.
\item Même question pour le groupe $G = (\F_{17}^*,*)$.
\item Dans le groupe $G = (\Z/13\Z, +)$ on choisit $g=2$. Calculer la
clef publique associée à la clef privée $x = 5$.
\item Est-il possible de retrouver la clef privée à partir de la clef
publique dans $G= (\Z/42\Z, +)$ ~? Généraliser la méthode à $(\Z/n\Z,
+)$ pour $n \geq 2$.
\end{enumerate}

\subsection{Chiffrement}

Bob souhaite envoyer un message $m \in \left\{0, 1, \ldots,
q-1\right\}$ à Alice.

\begin{itemize}
\item Bob choisit $y\in \left\{0, 1, \ldots, q-1\right\}$ au hasard.
\item Bob calcule $c_1 = g^y$, $c_2 = m \cdot h^y$.
\item Bob envoie $(c_1, c_2)$ à Alice.
\end{itemize}

\begin{enumerate}
\setcounter{enumi}{5}
\item Retrouver la procédure de déchiffrement d'Alice.
\item Montrer que le problème de déchiffrer un message sans connaître
la clef privée est plus facile que le problème du logarithme discret.
\item Dans $G = (\F_{17}^*, *)$ on prend $x = 13$, $g = 3$.
    \begin{itemize}
    \item Calculer la clef publique correspondante.
    \item Calculer le chiffré de $m=8$ pour $y=9$.
    \item Détailler le déchiffrement.
    \end{itemize}
\end{enumerate}

\subsection{Sécurité}
Pour un groupe cyclique $G$ de générateur $g$ on appelle problème
Diffie-Hellman calculatoire (\emph{CDH}) celui de trouver $g^{ab}$
connaissant $(g, g^a, g^b)$.

Le problème Diffie-Hellman décisionnel (\emph{DDH}) est celui de
savoir distinguer les tuples $(g, g^a, g^b, g^{ab})$ des couples $(g,
g^a, g^b, t)$ où $t$ est un élément aléatoire de $G$, c'est-à-dire
distinguer des tuples "Diffie-Hellman" de tuples aléatoires.

\begin{enumerate}
\setcounter{enumi}{8}
\item Montrer que le problème du logarithme discret est plus difficile
que CDH.
\item Montrer que le problème CDH est plus difficile que DDH.
\item Des groupes $G_1$, $G_2$ et $G_3$ dire lequel est le plus sûr
\emph{a priori} pour une utilisation dans le cryptosystème Elgamal
sachant que~:
    \begin{itemize}
    \item le problème du logarithme discret est dur dans $G_1$,
    \item le problème CDH est dur dans $G_2$,
    \item le problème DDH est dur dans $G_3$.
    \end{itemize}
\item Si CDH est dur mais DDH facile, que peut faire un attaquant~?
\end{enumerate}

\subsubsection{Sécurité du chiffrement Elgamal dans $G=\F_p^*$}

Pour $p$ premier dans le corps $\F_p$ à $p$ éléments on dit que $x \neq 0$ est
un résidu quadratique s'il existe $y \in \F_p$ tel que $x = y^2$.
\begin{enumerate}
\setcounter{enumi}{12}
\item Montrer que si $x$ est un résidu quadratique alors
$x^{(p-1)/2} = 1$.
\item Montrer que
$\varphi:\application{\F_p^*}{\F_p^*}{x}{x^2}$
est un morphisme et calculer son noyau. En déduire le nombre de
résidus quadratiques et de non résidus quadratiques dans $\F_p$.
\item Montrer que si $g$ est un générateur de $\F_p^*$ alors $g$ n'est
pas un résidu quadratique.
\item Pour $a \in \left\{1, p - 1 \right\}$, comment déterminer
simplement si $g^a$ est un résidu quadratique~?
\item On note $\chi(x) = 1$ si $x$ est un résidu quadratique, $-1$ sinon.
Calculer $\chi(g^{ab})$ en fonction de $\chi(g^a)$ et $\chi(g^b)$.
\item En déduire une méthode probabiliste pour répondre au problème
DDH, et calculer l'avantage de l'adversaire.
\end{enumerate}
\end{document}