Le code RSA

Le plus célèbre des codes à clé publique est dû à Ron Rivest, Adi Shamir et Leonard Adleman du MIT. La clé publique est connue de tous et est utilisée pour coder les messages. Par contre un message codé par la clé publique ne peut être décodé que par quelqu'un qui connaît la clé privée. Les clés sont constituées de la façon suivante.

1. Choisir deux (grands) nombres premiers $p$ et $q$.
2. Calculer $n=pq$ : les opérations s'effectueront modulo $n$.
3. Calculer $\varphi(n)=(p\!-\!1)(q\!-\!1)$.
4. Choisir un entier $e$ inférieur à $\varphi(n)$ et premier avec $\varphi(n)$ : c'est l'exposant de la clé publique.
5. Calculer l'inverse $d$ de $e$ pour la multiplication modulo $\varphi(n)$ (il existe et est unique puisque $e$ et $\phi(n)$ sont premiers entre eux : calcul par l'algorithme d'Euclide). L'entier $d$ est l'exposant de la clé privée.

La clé publique se compose de l'entier $n$ et de l'exposant $e$, connus de tous. La clé privée est l'exposant $d$ qui doit être tenu secret. Évidemment, quelqu'un qui connaît $n$ peut théoriquement retrouver ses deux facteurs premiers $p$ et $q$ et donc calculer $\varphi(n)$ puis $d$ connaissant $e$. La sécurité du système repose sur le fait que la décomposition d'un nombre en produit de facteurs premiers est très coûteuse en temps de calcul : il est virtuellement impossible de décomposer un nombre produit de deux très grands facteurs premiers. Cela n'empêche pas les utilisateurs de changer assez souvent de clé par mesure de sécurité.

Voici comment fonctionnent le codage et le décodage. Le message à transmettre est d'abord transformé en un entier (par exemple par concaténation des codes ascii des caractères qui le composent). Notons $m$ cet entier qui est censé être inférieur à $n$. Le codage le transforme en $c=m^e$ modulo $n$. Pour décoder, il faut connaître $d$ et calculer $c^d$ modulo $n$. Miracle, on retrouve $m$. Vous pouvez nous croire sur parole, mais ce serait dommage, car la démonstration est parfaitement à votre portée.

Définition 9   On appelle caractéristique d'Euler la fonction qui à un entier $n$ fait correspondre le nombre d'entiers premiers avec $n$, compris entre $1$ et $n$. On note cette fonction $\varphi$.

Si $p$ est premier, alors $\varphi(p)=p\!-\!1$, puisque tout entier strictement inférieur à $p$ est premier avec $p$. Si $n=pq$ est le produit des 2 nombres premiers $p$ et $q$, alors $\varphi(n)=(p\!-\!1)(q\!-\!1)$. Pourquoi ? Vous pouvez trouver tout seul : comptez les multiples de $p$ puis les multiples de $q$, entre $1$ et $pq$ (ne comptez pas $pq$ deux fois). Voici maintenant la généralisation du petit théorème de Fermat, que nous vous avons posé en exercice.

Théorème 9   Soit $n$ un entier et $a$ un entier premier avec $n$. Alors $a^{\varphi(n)}\equiv 1\;[n]$.

Cela aussi, vous pouvez le démontrer vous-mêmes : considérez le sous-ensemble de $\mathbb{Z}/n\mathbb{Z}$, noté $P$, constitué des $\varphi(n)$ entiers premiers avec $n$ compris entre $1$ et $n$. Montrez ensuite que l'application qui à $r\in P$ associe $ar$ modulo $n$ est une bijection de $P$ sur lui-même (raisonnez par l'absurde et utilisez le lemme de Gauss). Cela signifie que $\{ar [n] ,\;r\in P\}$ est égal à $P$. Maintenant faites le produit modulo $n$ de tous les éléments de chacun des deux ensembles :

$$\prod_{r\in P} ar =a^{\varphi(n)}\prod_{r\in P} r\equiv \prod_{r\in P} r\;[n]\;.$$

Allez, vous y êtes presque : un dernier coup de lemme de Gauss peut-être ? Après un tel effort, vérifier que le codage RSA fonctionne, c'est presque du repos : Puisque $ed\equiv 1\;[\varphi(n)]$, il existe un entier $k$ tel que $ed=k(p\!-\!1)(q\!-\!1)+1$. Alors : $(m^e)^d=m^{ed}=m (m^k)^{\varphi(n)}\equiv m\;[n]$.

Euh...  à condition que $m$ soit premier avec $n$, pour pouvoir appliquer le théorème ci-dessus à $m^k$. Si $m$ n'est pas premier avec $n$, il est divisible par $p$ ou par $q$, mais pas les deux (car il est inférieur à $pq$). Supposons qu'il soit divisible par $p$ et écrivons : $m=p^\alpha h$, où $h$ est premier avec $p$ et avec $q$. Allez, vous allez encore devoir travailler : montrez d'abord que $p^{\alpha ed}\equiv p^\alpha \;[p]$, puis que $p^{\alpha ed}\equiv p^\alpha \;[q]$. Maintenant, vous pouvez en déduire que $p^{\alpha ed}\equiv p^\alpha \;[n]$. Recollez les morceaux : $m^{ed}=p^{\alpha ed} h^{ed}\equiv p^{\alpha} h \;[n]$. Vous y êtes, le message est bien décodé ! Par pure bonté d'âme, nous vous dispensons de recommencer ce qui précède si $m$ est multiple de $q$ : merci qui ?