\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage[francais]{babel}
\usepackage{times}
\usepackage{xspace}
\newcommand{\bs}{\symbol{92}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newtheorem{theorem}{Theorem}
\newtheorem{defn}{Definition}

\begin{document}

\title{Cryptographie}
\author{Préparation agrégation, option C}
\date{Révision du 03/06}

\maketitle

Ce texte pr\'esente quelques mises en oeuvre de la 
m\'ethode de cryptographie RSA et de variantes ainsi que
quelques attaques.
Une bonne partie de ce texte est un condens\'e de\\
\verb|http://iml.univ-mrs.fr/~rolland/rr/lycees/concret1.pdf|
(Robert Rolland)

\section{RSA}
Du nom de ses inventeurs Ron Rivest, Adi Shamir et Len Adleman.

\subsection{Principe}
Soit $n=pq$ le produit de deux nombres premiers, alors le
groupe multiplicatif des inversibles de $\Z/n\Z$ poss\`ede
$\phi(n)=(p-1)(q-1)$ \'el\'ements, donc si $a$ est premier
avec $n$ et $d$ et $e$ sont inverses l'un de l'autre dans
$\Z/\phi(n)Z$, on a
\[ (a^{d})^e \pmod n = a^{de} \pmod n = a^{1+\alpha \phi(n)} \pmod n =
a \pmod n\]
On observe que cette identit\'e reste encore vraie si $a$ n'est pas
premier avec $n$.
En cons\'equence on peut retrouver $a \pmod n$ connaissant $b=a^d \pmod
n$ en calculant $b^e \pmod n$. La fonction de codage consiste \`a
transformer le texte en une suite de nombres modulo $n$, \`a calculer
les puissances $d$-i\`emes de ces nombres modulo $n$, le d\'ecodage
\`a calculer les puissances $e$-i\`emes de ces nombres modulo $n$
(ou inversement, car $d$ et $e$ jouent un role sym\'etrique).

L'int\'er\^et de RSA est que $n$ et $e$ peuvent \^etre publi\'e sans
que $d$ ne soit calculable en un temps raisonnable, pourvu que 
$n$ soit assez grand (par exemple 1024 bits), parce qu'on ne
connait pas d'algorithme de factorisation efficace. On peut donc
signer un message en utilisant sa clef priv\'ee $d$ et en transmettant
un entier $a$ d\'ependant du message cod\'e en $a^d $. N'importe
qui pourra d\'ecoder la signature car $e$ est public. On peut transmettre
un message destin\'e \`a un seul destinataire en le codant avec
la clef publique du destinataire ($a \rightarrow a^e$), seul celui-ci
sera en mesure de le d\'ecoder avec sa clef priv\'ee $d$.

\subsection{Attaques triviales}
Si le message transmis $m$ est petit et si $e$ est petit (par exemple
$e=3$) alors
il peut se produire que $m^e<n$, on peut alors calculer $m$ par
extraction de racine cubique. Si
les messages possibles $m$ sont dans un ensemble de cardinal
petit (par exemple si on prend $m$ le code ASCII des caract\`eres
du message), on peut construire l'ensemble des valeurs possibles
de $m^e$ et d\'ecrypter le texte transmis en comparant le texte
chiffr\'e \`a cette table. En pratique, il faut donc disposer
d'un nombre important de valeurs de message \`a transmettre (on peut 
par exemple grouper plusieurs lettres, en rajoutant des espaces au
besoin,  et utiliser la repr\'esentation en base 256), rendre
impossible la transmission de 0 et 1, \'eviter les $m$ ayant
un facteur commun avec $n$, ne pas choisir une clef publique (ni
priv\'ee!) trop petite.

\subsection{Attaque par fraction continue}
Fonctionne si la clef priv\'ee $d$ est petite et si $p$ et $q$ sont
du m\^eme ordre de grandeur~: 
\[ p>q, \quad p< 2q\]
Le principe consiste \`a calculer les r\'eduites de $e/n$.
Soit $k \in ]0,d[$ tel que
\[ ed=1+k \phi(n) = 1+k(n+1-p-q) = kn + 1 + k(1-p-q)\]
On divise par $dn$~:
\[ \frac{e}{n} = \frac{k}{d} + \frac{1+k(1-p-q)}{dn} \]
donc~:
\begin{eqnarray*}
 |\frac{e}{n} - \frac{k}{d} | & = & \frac{k(p+q-1)-1}{dn} \\
& \leq  & \frac{k(p+q)}{nd} \\
& \leq  & \frac{kq(\frac{p}{q}+1)}{nd} \\
& \leq & \frac{3kq}{nd} \\
& \leq & \frac{3k}{\sqrt{n}d} \\
& < & \frac{3}{\sqrt{n}}
\end{eqnarray*}
Si $3/\sqrt{n} < 1/(2d^2)$, alors les r\'esultats connus sur les
fractions continues permettent de conclure que $k/d$ est une
r\'eduite de $e/n$. Il suffit de les calculer et voir si on a
$m^{de}=m \pmod n$.

\section{Signature avec ombre des cartes bancaires}
\subsection{Principe}
On choisit $p$ et $q$ tels que $\phi(n)$ ne soit pas divisible par 3.
On pose par exemple $e=3$. Le num\'ero de carte est un nombre $I$ cod\'e sur $k$
bits, on construit le nombre $J=I 2^k +I$. $J$ est sign\'e par le
calcul de $A=J^d \pmod n$. On stocke sur la carte bancaire
$I$ et $A$. Lorsqu'on saisit le code secret sur un terminal, la carte
transmet au terminal les valeurs de $I$ et $A$. Le terminal calcule
alors $J$ et $A^3 \pmod n$ et v\'erifie que $J=A^3$. Une personne
d\'esirant cr\'eer une carte bancaire pirate devra donc fournir
$I$ et $A$ tel que $A^3 =(I+2^k I)\pmod n$. On peut bien sur calculer
le cube d'un nombre modulo $n$ mais la probabilit\'e de tomber sur
un nombre ombr\'e est infime (on peut aussi construire un nombre
ombr\'e mais le calcul de sa racine cubique modulo $n$ est impraticable).

\subsection{Attaque: calcul de $n$ s'il n'est pas
  publi\'e.}
Si on connait deux couples $I_1,A_1$ et $I_2,A_2$, alors
\verb|gcd(A1^3-J1,A2^3-J2)| est un multiple $kn$ de $n$ avec
$k$ tr\`es probablement petit. En divisant par les petits premiers
ce pgcd, on trouve tr\`es probablement $n$.

\section{\'Echange de clefs de Diffie-Hellman}
Le principe~: on se donne un premier $p$, et un \'el\'ement primitif
$\alpha$ de $\Z/p\Z^*$. Chacun des deux interlocuteurs qui veulent
se mettre d'accord sur une clef choisit secr\`etement un entier
$n_1$, $n_2$ inf\'erieur \`a l'ordre du groupe. 
Ils envoient alors \`a l'autre interlocuteur
$\alpha^{n_1} \pmod p$ ($\alpha^{n_2} \pmod p$). La clef commune est d\'eduite de 
$\alpha^{n_1n_2} \pmod p$.

Ce principe n\'ecessite de pouvoir construire un \'el\'ement primitif $a$
de $\Z/p\Z^*$. Il faut donc tester que $a^{(p-1)/d} \neq 1 \pmod p$
pour tout diviseur premier $d$ de $p-1$. En pratique, on ne sait pas
forc\'ement factoriser $p-1$, on inverse donc le probl\`eme, on part
d'un grand nombre premier $q$ et on construit les entiers $2kq+1$ pour
$k$ suffisamment petit pour \^etre factoris\'e. On s'arr\^ete d\`es
que $2kq+1$ est premier. Le th\'eor\`eme de Dirichlet sur la densit\'e
des nombres premiers permet de montrer qu'il faut en moyenne $\ln(p)$
essais avant succ\`es, o\`u $p$ est la taille du premier souhait\'e
de cette forme.

\section{Le cryptosyst\`eme ElGamal}
(D'apr\`es \verb|wikipedia.fr|).
Cet algorithme tire son nom de son inventeur Taher Elgamal.
L'algorithme fonctionne comme suit~:
\begin{itemize}
\item 
Alice calcule $h = g^x $,  $g \in \mathbb{Z}_p$ 
pour un grand nombre premier $p$, 
et divulgue sa clé publique $(p,g,h)$. 
La valeur $x$ est sa clé privée.
\item Si Bob veut envoyer un message à Alice, il convertit d'abord 
son message sous la forme d'un nombre $m\in \mathbb{Z}_p$.
\item Bob génère un nombre entier $k$ aléatoirement et calcule 
$c1 = g^k$ et $c_2=m\cdot h^k$. Il envoie $(c1,c2)$ à Alice.
\item Alice peut reconstruire le message initial m en calculant $c_2/c_1^x$.
On remarque en effet que~:
\[ \frac{c_2}{c_1^x} = \frac{m\cdot h^k}{g^{xk}} = 
\frac{m\cdot g^{xk}}{g^{xk}} = m \]
\end{itemize}

L'int\'er\^et de ce cryptosyst\`eme est qu'un m\^eme message
n'est pas cod\'e deux fois de suite de la m\^eme facon. Le prix
\`a payer est qu'on envoie en gros deux fois plus d'informations
qu'avec un cryprotsyst\`eme comme RSA.

Il n'est pas obligatoire d'utiliser $\mathbb{Z}_p$. 
Tout groupe cyclique convient.

La s\'ecurit\'e de ElGamal repose sur la difficult\'e de calculer
le logarithme discret dans le groupe cyclique choisi. 
Si $G$ est un groupe cyclique d'ordre $q$,
\'etant donn\'e $(g,g^a,g^b)$ pour un g\'en\'erateur $g$ de $G$
et $a,b$ deux nombres al\'eatoires compris entre 0 et $q-1$, 
l'\'el\'ement $g^{ab}$ doit \^etre comme un \'element al\'eatoire de $G$.

\section{Suggestions de d\'eveloppement}
\begin{itemize}
\item Tests de primalit\'e, de pseudo-primalit\'e, g\'en\'eration
de clefs.
\item Mise en oeuvre de RSA, ou de ElGamal et d'une application.
\item Mise en oeuvre d'une attaque (par exemple fraction continue).
\end{itemize}

\end{document}