L'algorithme proprement dit

Dans le premier chapitre, nous avons vu que dans un système asymétrique, la clé publique est générée à partir de la clé privée à l’aide d’une fonction mathématique simple mais difficilement réversible. Nos trois larrons ont utilisé la plus simple de toutes : la multiplication. En effet, il est très facile de multiplier deux nombres. En revanche, si je vous donne un nombre entier de grande taille, par exemple $332403452489$, vous serez bien en peine de retrouver qu’il est le produit de $738653$ et de $450013$. Avec des nombres suffisamment grands, la factorisation demande tellement de temps que tous les ordinateurs du monde réunis n’y parviendraient pas même en un million d’années.

Cela étant, on ne peut pas choisir n’importe quelle paire de nombres pour notre affaire. En effet, un nombre peut avoir plusieurs factorisations valides : $20 = 4 \times 5 = 2 \times 10$. Le seul moyen de garantir qu’il n’existe qu’une seule factorisation valide, c’est de multiplier deux nombres premiers. Nous y voilà.

Soient deux nombres premiers $P$ et $Q$ différents, par exemple $53$ et $97$. On définit les nombres $N = P \times Q$ et $M = (P - 1)(Q - 1)$, dans notre exemple $N = 5141$ et $M = 4992$.

Pour terminer la génération de nos clés, il nous faut choisir un nombre $E$ qui soit à la fois inférieur à $M$ et premier avec ce même nombre. Ici, nous pouvons choisir $7$.

Voilà, c’est terminé pour la génération des clés ! La clé publique est composée du couple $(N, E)$ et la clé privée est composée du triplet $(P, Q, E)$.

Vous allez me dire que dans notre exemple, il est relativement rapide de retrouver $P$ et $Q$ à partir de $N$. C’est parfaitement exact. C’est pourquoi, en situation réelle, on utilisera plutôt le produit suivant :

3 107 418 240 490 043 721 350 750 035 888 567 930 037 346 022 842 727 545 720 161 948 823 206 440 518 081 504 556 346 829 671 723 286 782 437 916 272 838 033 415 471 073 108 501 919 548 529 007 337 724 822 783 525 742 386 454 014 691 736 602 477 652 346 609

= 1 634 733 645 809 253 848 443 133 883 865 090 859 841 783 670 033 092 312 181 110 852 389 333 100 104 508 151 212 118 167 511 579

× 1 900 871 281 664 822 113 126 851 573 935 413 975 471 896 789 968 515 493 666 638 539 088 027 103 802 104 498 957 191 261 465 571

Mais pour donner un exemple trivial, ce n’est pas hyper-simple à utiliser.

L’algorithme RSA travaille exclusivement avec des nombres. Aussi, avant de chiffrer un message composé de texte, il faut transformer ce texte en nombres de manière non ambiguë. Cette étape ne pose pas de difficulté : tous les ordinateurs stockent le texte sous forme de nombres et on pourra utiliser le standard Unicode, qui nous offre une base bien pratique. Supposons que notre brave Adalbéron veuille envoyer le message « Douce Brunehaut, souffrez de recevoir mon ardent amour. » à sa bien aimée Brunehaut. Une fois converti en Unicode, on obtient la représentation suivante.

68 111 117 99 101 32 66 114 117 110 101 104 97 117 116 44 32 115 111 117 102 102 114 101 122 32 100 101 32 114 101 99 101 118 111 105 114 32 109 111 110 32 97 114 100 101 110 116 32 97 109 111 117 114 46

La fonction de chiffrement à l’aide d’une clé $(N, E)$ est la suivante.

$f : x \mapsto x^E \ [N]$

Cela signifie que pour obtenir votre code chiffré, vous devez élever votre code en clair à la puissance $E$ et lui appliquer le modulo $N$ : on dit que à tout antécédent $x$, la fonction $f$ associe l’image $x^E \ [N]$.

D’emblée, on comprend qu’il n’est possible de chiffrer que des nombres strictement inférieurs à $N$. En effet, $(N + 1) [N] = 1$ : si l’on n’y prend pas garde, les nombres supérieurs à $N$ donneront le même résultat que certains nombres inférieurs, et il sera impossible de les distinguer lors du déchiffrement. Dans l’exemple qui nous intéresse, nous allons réutiliser la clé $(5141, 7)$, donc ce problème ne se posera pas. Voyons ce que donne la fonction appliquée à notre message.

254 1858 1774 4105 1640 3675 386 737 1774 2127 1640 4960 970 1774 3935 4362 3675 3853 1858 1774 1689 1689 737 1640 4607 3675 4515 1640 3675 737 1640 4105 1640 204 1858 2437 737 3675 1657 1858 2127 3675 970 737 4515 1640 2127 3935 3675 970 1657 1858 1774 737 3522

Je vous épargne la reconversion en caractères, le résultat fait boguer mon navigateur. Cependant, vous pouvez voir que le code en clair ne présage en rien du code chiffré : 111 et 110 sont très proches et le premier supérieur au second, mais leurs équivalents chiffrés, 1858 et 2127, sont très différents et le premier inférieur au second.

Longue introduction

Le déchiffrement va nous demander un petit peu plus de calcul. En effet, nous allons avoir besoin d’un entier $D$ tel que $2 < D < M$ et que $D \cdot E \equiv 1 \ [M]$. Une formulation équivalente à cette congruence est qu’il existe un entier $k$ tel que $D \cdot E + k \cdot M = 1$.

Il est possible de trouver $D$ grâce à l’algorithme d’Euclide étendu. Il commence comme l’algorithme d’Euclide tout court qui permet de trouver le PGCD de deux entiers, par exemple $43$ et $12$. Souvenez-vous.

Les équivalences données à côté de chaque égalité ne sont pas innocentes. En effet, nous allons prendre la dernière, celle qui commence par $1 =$, et remplacer dans le membre droit de l’égalité tous les nombres à l’exception des quotients par une formulation alternative telle que déterminée plus haut. Voyez plutôt.

Pour une raison très simple : $4992 = 713 \times 7 + 1 \Leftrightarrow 1 = 4992 \times 1 + 7 \times (-713)$. Comme vous le voyez, il n’y a qu’une seule opération à faire pour trouver le résultat, ce qui ne permet pas de mettre en lumière l’algorithme.

Cependant, vous aurez remarqué que $D = -713$, ce qui ne colle pas avec l’obligation d’être supérieur à $2$ que nous avons vue plus haut. Il est possible de contourner la difficulté. On va chercher un nombre entier $a$ tel que $2 < D + a \cdot M < M$ ; dans la plupart des cas, $a = 1$ fonctionne, sinon on essaye avec $2$, $3$, etc. Revenons à notre égalité de départ $D \cdot E + k \cdot M = 1$.

On voit bien que $D + a \cdot M$ remplit les deux conditions énoncées au début de cette section. Dans le cas qui nous intéresse, $-713 + 1 \cdot 4992 = 4279$ : nous avons trouvé notre $D$ !

Courte explication

Une fois que ce $D$ est déterminé, la fonction permettant de déchiffrer un message $x$ est ridiculement simple.

$f : x \mapsto x^D \ [N]$

Oui. C’est ça qui est bien. Voyons à présent ce que cela donne sur un message qu’Adalbéron vient de recevoir de la part de Brunehaut. Il ne s’agit pas du message de tout à l’heure, sinon ce serait trop simple.

Code chiffré : 3852 1858 2127 3675 2799 737 1640 1774 3712 3675 787 4515 970 4527 2814 4964 737 1858 2127 4632 3675 737 1640 3935 737 1858 1774 204 1640 1489 1657 1858 2437 3675 1640 2127 3675 4527 970 3675 298 1858 1774 737 3675 3852 970 4650 2127 1640 3675 3543 3675 4527 970 3675 1657 2437 2127 1774 2437 3935 3522

Code en clair : 77 111 110 32 112 114 101 117 120 32 65 100 97 108 98 233 114 111 110 44 32 114 101 116 114 111 117 118 101 45 109 111 105 32 101 110 32 108 97 32 84 111 117 114 32 77 97 103 110 101 32 224 32 108 97 32 109 105 110 117 105 116 46

Message en clair : « Mon preux Adalbéron, retrouve-moi en la Tour Magne à la minuit. »

Et voilà ! C’est on ne peut plus simple ! Dans cet exemple, on a utilisé la même clé pour Adalbéron et Brunehaut, pour simplifier, mais elle doivent bien sûr impérativement être différentes.

Il nous reste à présent à montrer pourquoi l’algorithme fonctionne. C’est-à-dire pourquoi, si l’on applique successivement la fonction de chiffrement et de déchiffrement, on obtient le message de départ, quel qu’il soit. On l’a vu, si le message en clair est un entier positif $x$, le message chiffré est $x^E \ [N]$ et le message déchiffré est $(x^E \ [N])^D \ [N] = x^{ED} \ [N]$. Il faut donc montrer que $x^{ED} \equiv x \ [N]$.

Cela va se faire en plusieurs étapes. Tout d’abord, il faut introduire une règle que l’on appelle couramment le lemme de Gauss (voyez le lien pour la démonstration de ce lemme), et qui appliqué à notre cas dit que si $P \ | \ bQ$ et $P$ et $Q$ sont premiers entre eux (ce qui est nécessairement le cas puisqu’ils sont premiers tout court et différents) alors $P \ | \ b$, c’est à dire qu’il existe un entier $c$ tel que $b = cP$.

À présent, prenons $u$ et $v$ deux entiers tels que $u \equiv v \ [P]$ et $u \equiv v \ [Q]$.
Alors, il existe un couple d’entiers $(a, b)$ tel que $(u - v) = aP = bQ$.
Donc $P \ | \ bQ$.
D’après le lemme de Gauss, $P \ | \ b$ i.e. il existe un entier $c$ tel que $b = cP$.
Alors, $(u - v) = bQ = cPQ$ ce qui équivaut à $u \equiv v \ [PQ]$.
Comme $PQ = N$, cela signifie que si nous pouvons démontrer que $x^{ED} \equiv x \ [P]$ et $x^{ED} \equiv x \ [Q]$, alors nous aurons démontré que $x^{ED} \equiv x \ [N]$.

Deux cas se présentent. Soit $P$ divise $x$, soit $P$ ne divise pas $x$. Le raisonnement est strictement le même avec $Q$.

Cas 1 : $P$ divise $x$.
On a : $P \ | \ x \Leftrightarrow x \equiv 0 \ [P] \Leftrightarrow x^{DE} \equiv 0 \ [P]$.
Si ce résultat vous étonne, retournez lire le paragraphe sur les congruences dans le chapitre précédent.
Puis, $x$ et $x^{DE}$ étant congrus au même nombre modulo $P$, par définition, $x^{ED} \equiv x \ [P]$.

Cas 2 : $P$ ne divise pas $x$.
Il faut se souvenir que $DE + kM = 1$. Donc $DE = 1 + (-k)M = 1 + (-k)(P - 1)(Q - 1)$.
Or, d’après le petit théorème de Fermat, comme $P$ est premier et $P$ ne divise pas $x$, on a le développement suivant :

En somme, $x^{ED} \equiv x \ [P]$. De manière analogue, $x^{ED} \equiv x \ [Q]$, donc $x^{ED} \equiv x \ [N]$.

CQFD. Le raisonnement est un peu abscons, mais on s’est efforcé de le rendre le plus évident possible.