

\section{Méthodes de cryptage \og à clé publique\fg{} }
\subsection{Principe}
Supposons qu'un individu $A$ soit obligé de transmettre à un autre individu $B$ un message $M$ en utilisant un réseau de communication public, par exemple les ondes hertziennes. N'importe quel individu peut se mettre à l'écoute et intercepter le message.\\


Le problème est donc :
\begin{itemize}
\item le message doit être inintelligible pour tout individu autre que $A$ et $B$.
\item $B$ doit pouvoir le comprendre.
\item $B$ doit pouvoir s'assurer que le message provient bien de $A$ (et non d'un plaisantin quelconque).\\
\end{itemize}


L'idée est de doter tous les participants de la même méthode de cryptage. Les résultats du cryptage d'un même message par divers individus sont cependant différents, car chacun d'entre eux emploie une \og clé\fg{} qui lui est propre.

\begin{Ex}
Lorsque l'on remplace 'a' par 'c', 'b' par 'd', etc\ldots, la méthode de cryptage est \og décalage des lettres de l'alphabet\fg{} et la clé est la longueur du décalage, ici 2. 
\end{Ex}



La méthode de cryptage est fondée sur l'existence de fonctions $f$, dépendant d'un paramètre (la \og clé\fg{} ), inversibles, mais pour lesquelles la détermination de l'inverse est matériellement impossible, en l'état actuel des connaissances humaines.\\


Soit $f_A$ la fonction de cryptage qui utilise la clé propre à
l'individu $A$.
\begin{itemize}
 \item La clé de A est publique, ainsi n'importe qui est en mesure d'appliquer la fonction $f_A$ à un message $M$ quelconque.
\item Par contre, seul $A$ connaît la fonction inverse $f_A^{-1}$ qui permet de retrouver le message initial.\\
\end{itemize}

 

Au message $M$ , $A$ applique en fait $f_A^{-1}$ (il est le seul à
pouvoir le faire).



Puis, à ce message $f_A^{-1}(M)$, il applique la fonction de cryptage de $B$, soit $f_B$ (il peut le faire, la clé de $B$ est publique), pour obtenir $f_B\circ f_A^{-1}(M)$, incompréhensible car les clés sont évidemment uniques, et donc $f_B\circ f_A^{-1}$ n'est pas l'identité.\\



C'est ce message \og doublement\fg{} crypté qui est envoyé. $B$ le reçoit et lui applique aussitôt $f_B^{-1}$, ce qu'il est le seul à pouvoir faire, pour obtenir $f_A^{-1}(M)$, auquel il applique $f_A$ : si le résultat est compréhensible, $B$ est sûr que le message lui était bien destiné, et qu'il a bien été envoyé par $A$.



\subsection{Utilisation de l'indicatrice d'Euler}

\begin{Exo}[Fonction indicatrice d'Euler]
Soit $n$ un entier strictement positif; on note $\varphi(n)$ le nombre des entiers inférieurs à $n$ qui sont premiers avec $n$.

L'application de $\Net$ dans $\Net$ ainsi définie est appelée \emph{fonction indicatrice d'Euler}.
\begin{enumerate}
\item Montrer que, pour $p$ premier, $\varphi(p) = p - 1$
\item Montrer que, pour $p$ premier, $\varphi(p^{\alpha}) = p^\alpha-p^{\alpha-1}$
\item On considère les nombres de la
forme $ap+bq$, pour $p$ et $q$ premiers entre eux et l'application de
$(\Z/q\Z)\times(\Z/p\Z)$ dans $(\Z/pq\Z)$
définie par $(a,b)\fc ap+bq\ [pq]$; montrer que cette application est injective et surjective. 
\item En déduire (en utilisant les nombres de la forme $ap+bq\ [pq]$) que, pour $p$ et $q$
premiers entre eux, $\varphi(pq)=\varphi(p)\varphi(q)$. \item
Utiliser le résultat précédent et le théorème de Fermat ci-dessus pour prouver que, pour tout entier $a$ premier avec $n$, et
pour tout entier positif $n$ dépourvu de facteur carré, $a^{\varphi(n)}\equiv 1\ [n]$.
\end{enumerate}
\end{Exo}

\subsubsection{Résultat de base}

Diverses fonctions \og à inverse difficile à déterminer\fg{} ont été
proposées. Les plus satisfaisantes sont celles qui utilisent le
résultat suivant :

\begin{Th}
s'il est très facile d'obtenir un très grand nombre entier composé par produit de deux nombres premiers eux-mêmes grands, la décomposition en facteurs premiers d'un nombre composé est très difficile.
\end{Th}

\subsubsection{Méthode de cryptage}

La méthode de cryptage est la suivante :

\begin{enumerate}
 \item Soit donc $n = pq$ un entier, produit de deux nombres entiers premiers, par exemple tels que $p \equiv q \equiv 2 [3]$.
 \item Soit $M$ le message, préalablement chiffré (sans précautions particulières, par exemple en remplaçant les lettres par leurs codes ASCII).
\item Si $M\geqslant n$, on décompose $M$ en plusieurs sous-messages, ses \og chiffres\fg{} en base $n$, par exemple.
\item Si $n$ est la clé choisie par $A$, et pour $M<n$, $f_A(M)=C$, avec $C\equiv M^3\ [n]$. Comme $n$ est connu de tous, n'importe qui peut calculer $C$ très rapidement. Par contre, les facteurs premiers $p$ et $q$ de $n$ sont soigneusement tenus secrets par $A$.
\item Un résultat (élémentaire) d'arithmétique indique que, comme $n$ n'a pas de facteur carré, si $M$ est premier avec $n$, alors $M^{\varphi(n)}\equiv 1\ [n]$ (dans cette expression, $\phi$ est la fonction indicatrice d'Euler, c'est-à-dire que $\varphi(n)$ est le nombre de nombres strictement positifs inférieurs à $n$ qui sont premiers avec $n$).
\item Un autre résultat (élémentaire) d'arithmétique dit que, comme $n=pq$, avec $p$ et $q$ premiers, $\varphi(n)=\varphi(pq)=\varphi(p)\varphi(q)=(p-1)(q-1)$.
\item On a donc, en combinant ces deux résultats,
$M^{(p-1)(q-1)}\equiv 1\ [n]$, donc $M^{2(p-1)(q-1)}\equiv 1\ [n]$, et
finalement $M^{2(p-1)(q-1)+1}\equiv M\ [n]$.
\item Comme on a choisi $p\equiv q\equiv 2\ [3]$, $(p-1)(q-1)\equiv 1\ [3]$, $2(p-1)(q-1)\equiv 2\ [3]$ et $2(p-1)(q-1)+1\equiv 0\ [3]$. Il s'agit donc d'un multiple de 3, on peut poser $2(p-1)(q-1)+1=3k$, et on a $M^{3k}\equiv M\ [n]$.
\item Or $M^{3k}=(M^3)^k$, donc, si le message crypté est $C\equiv M^3\ [n]$, $C^k\equiv M\ [n]$ et la connaissance de $k=\fr{2(p-1)(q-1)+1}3$ permet de retrouver le message original.
\end{enumerate}

\begin{Ex}
Avec $p=5$, $q=11$, $n=pq=55$.

Le message à envoyer est chiffré $M=7$.

Alors $7^2\equiv 49\ [55]$, $7^3\equiv 13\ [55]$.

Le message crypté est $C=13$.

Ici $k=\fr{2\times 4\times 10+1}3=27$, donc $M\equiv 13^{27}\ [55]$.

On a $13^{27}=13^{16+8+2+1}$, or $13^2\equiv 4\ [55]$, $13^4\equiv 4\times 4\equiv 16\ [55] $, $13^8\equiv 16\times 16\equiv 256\equiv 36\ [55] $ $13^{16}\equiv 36\times 36\equiv 1296\equiv 21\ [55]$, donc $13^3\equiv 4\times 13\equiv 52\ [55]$ , $13^{11}\equiv 52\times 36\equiv 37\ [55]$, $13^{27}\equiv 37\times 21\equiv 7\ [55]$.
\end{Ex}


Si, par malchance, $M$ est un multiple de $p$ ou de $q$, il suffit
de modifier légèrement le premier chiffrage, par exemple en introduisant un espace supplémentaire dans les caractères du message d'origine, ce qui ne modifie pas son sens. Ne pas oublier cette précaution indispensable.


\section{Choix d'un nombre n}

Dans l'exemple ci-dessus, le cryptage est immédiatement percé à jour, puisque la décomposition de 55 en ses facteurs premiers 5 et 11 est immédiate. On peut en dire autant de tout entier représentable sur 32 bits.\\

Il faut aller chercher bien plus loin pour assurer un minimum de sécurité. Pour fixer les idées, les clés utilisées sont à l'heure actuelle le produit de deux nombres qui ont entre 100 et 200 chiffres dans leur représentation décimale.


\subsection{Nombres premiers}

Pour produire un nombre $n$ utilisable, il faut tout d'abord trouver deux
nombres $p$ et $q$ premiers, suffisamment grands.\\

On choisit deux nombres se terminant par 1, 3, 7 ou 9 dans leur représentation décimale et de longueurs comparables (mais pas trop proches : il existe un algorithme de décomposition qui est capable de décomposer rapidement un nombre qui est le produit de deux nombres de
longueurs très proches).\\

Il faut vérifier qu'ils sont premiers et, pour cela, disposer d'un critère de primalité (voir plus loin).\\

Lorsque le nombre produit au hasard n'est pas premier, il suffit de lui ajouter 2 , puis encore 2 etc., jusqu'à obtenir un nombre premier, ce qui interviendra très rapidement.\\

Avec ces deux nombres premiers $p$ et $q$ ainsi obtenus, on obtient la clé $n$.


\subsection{Décomposition en facteurs premiers}

Théoriquement, bien sûr, la décomposition d'un nombre composé (non premier) est un problème résolu : il suffit de tenter de le diviser par tous les nombres premiers jusqu'à sa racine carrée.\\


Pratiquement, cet algorithme est totalement impraticable dès que la longueur du nombre dépasse une vingtaine de chiffres décimaux (durée d'exécution trop élevée).\\

La durée d'exécution d'un algorithme de décomposition en facteurs premiers dé\-pend, bien sûr, de la longueur du nombre à décomposer. Mais il n'y a pas proportionnalité stricte : cela dépend aussi de l'algorithme utilisé. Pour prendre un exemple limite, 1000!, qui est un nombre dont la représentation décimale occupe plus de 4000 chiffres, est décomposé en quelques fractions de seconde par le plus rudimentaire des algorithmes.\\

Le seul moyen, donc, pour savoir si un nombre $n$ obtenu comme ci-dessus est une \og bonne\fg{} clé, est de tenter de le décomposer par tous les algorithmes connus. S'il résiste vaillamment, on peut l'adopter, sinon, il faut en changer.\\

La conclusion de cette présentation est qu'il est donc nécessaire de disposer d'un test de primalité et d'algorithmes de décomposition en facteurs premiers, questions que nous allons aborder dans les paragraphes suivants.
