L'historien romain Suétone raconte que Jules César, pour ses lettres confidentielles, remplaçait chaque lettre par celle qui se trouve trois rangs plus loin : A devient D, B devient E, et ainsi de suite. En nombres, c'est la fonction $x \mapsto x + 3$ modulo $26$, et l'on déchiffre par $y \mapsto y - 3$.

Ce chiffre est d'une faiblesse totale : il n'y a que $25$ décalages possibles, qu'un ennemi patient essaie en quelques minutes. Il a pourtant servi très longtemps, parce que peu de gens savaient lire.

Pour multiplier les clés, on chiffre la lettre de rang $x$ par la lettre de rang $y$ définie par

où le couple $(a\,;b)$ est la clé. Chiffrons le mot ORAL avec la clé $(5\,;8)$.

ORAL devient donc APIL. Mais attention : toutes les clés ne conviennent pas. Avec $a = 13$, la lettre A (rang $0$) donne $13 \times 0 = 0$ et la lettre C (rang $2$) donne $13 \times 2 = 26 \equiv 0$ : A et C sont chiffrées par la même lettre, et le destinataire ne peut plus savoir laquelle était écrite. Il faut comprendre quand on peut revenir en arrière.

Comme $26 = 2 \times 13$, les valeurs permises de $a$ sont les nombres impairs différents de $13$, entre $1$ et $25$ : il y en a $12$. Avec les $26$ valeurs de $b$, cela fait $12 \times 26 = 312$ clés. C'est mieux que César, mais un ordinateur les essaie toutes en une fraction de seconde.

Pour la clé $(5\,;8)$, il faut l'inverse de $5$ modulo $26$. L'algorithme d'Euclide donne $26 = 5 \times 5 + 1$, donc

soit

L'inverse est $u = -5 \equiv 21$ ; on vérifie : $5 \times 21 = 105 = 4 \times 26 + 1$. Pour des nombres plus grands, on remonte toutes les divisions de l'algorithme d'Euclide : c'est l'algorithme d'Euclide étendu, programmé plus bas en Python.

Déchiffrons APIL avec $x \equiv 21(y - 8)$ :

Pour $-168$, on ajoute $7 \times 26 = 182$ et l'on trouve bien $14$ : le reste d'un nombre négatif se calcule en ajoutant des multiples de $26$.

Supposons qu'un message chiffré par une clé affine inconnue contienne surtout des C, puis des U. On fait l'hypothèse que C chiffre E et que U chiffre S. En rangs : E $=4$ donne C $=2$, et S $=18$ donne U $=20$, d'où le système

Étape 1. On soustrait la première ligne de la seconde : $14a \equiv 18 \pmod{26}$.

Étape 2. Attention, on ne peut pas « diviser par $14$ », qui n'est pas premier avec $26$. On revient à la définition : $26$ divise $14a - 18$, donc $13$ divise $7a - 9$, soit $7a \equiv 9 \pmod{13}$. Comme $7 \times 2 = 14 \equiv 1 \pmod{13}$, on multiplie par $2$ : $a \equiv 18 \equiv 5 \pmod{13}$.

Étape 3. Entre $0$ et $25$, cela laisse $a = 5$ ou $a = 18$. Or $18$ est pair, donc pas premier avec $26$ : ce ne peut pas être une clé. Ainsi $a = 5$ et $b \equiv 2 - 4 \times 5 = -18 \equiv 8$.

On a retrouvé la clé $(5\,;8)$ sans l'avoir jamais vue. Il suffit ensuite de déchiffrer : si le texte obtenu a un sens, l'hypothèse était la bonne ; sinon, on essaie la troisième lettre la plus fréquente.

En 1586, Marie Stuart, reine d'Écosse prisonnière en Angleterre, correspond en secret avec des conjurés qui préparent l'assassinat d'Élisabeth I^re (le complot de Babington). Ses lettres sont chiffrées par substitution, avec quelques symboles pour des mots entiers. Elles sont interceptées et confiées au déchiffreur Thomas Phelippes, qui en vient à bout par l'analyse des fréquences. Les lettres déchiffrées servent de preuve à son procès, et Marie Stuart est exécutée en février 1587. Un chiffre faible est pire que pas de chiffre du tout : il donne confiance à celui qui écrit.

L'outil ci-dessous chiffre et déchiffre un texte par un chiffrement affine ou par le chiffre de Vigenère (présenté juste après). Le bouton « Reprendre le résultat » replace le texte obtenu dans la zone de saisie, pour le déchiffrer ensuite. L'outil affiche aussi les fréquences des lettres du résultat : chiffrez un long texte français avec une clé affine, et regardez la barre la plus haute.

Les accents et la ponctuation sont retirés, les espaces conservés ; les anciens chiffreurs supprimaient aussi les espaces, qui trahissent la longueur des mots.

Pour échapper à l'analyse des fréquences, il faut qu'une même lettre claire ne soit pas toujours chiffrée de la même façon. Le chiffre décrit par Giovan Battista Bellaso en 1553, puis par Blaise de Vigenère en 1586 (qui lui a laissé son nom), utilise un mot-clé : on écrit le mot-clé sous le message, en le répétant, et chaque lettre est décalée du rang de la lettre de la clé placée dessous. Chiffrons GRANDORAL avec la clé MATHS (rangs $12$, $0$, $19$, $7$, $18$) :

Les deux A du message deviennent T, mais les deux R deviennent R, et le S chiffré provient tantôt de G, tantôt de L : les fréquences sont brouillées. Pendant près de trois siècles, ce chiffre passe pour « indéchiffrable ».

Le carré de Vigenère : on lit la lettre chiffrée à l'intersection de la colonne de la lettre claire et de la ligne de la lettre de la clé. Image : Brandon T. Fields, Wikimedia Commons, domaine public.

Le point faible est la répétition de la clé. Si un même groupe de lettres du message tombe deux fois sous la même portion de la clé, il est chiffré deux fois de la même façon. Cela arrive quand la distance entre les deux groupes est un multiple de la longueur de la clé. Charles Babbage l'avait compris vers 1854 sans le publier ; l'officier prussien Friedrich Kasiski publie la méthode en 1863.

Voici un message chiffré avec la clé MATHS :

MTMHIGESSWBOGAHGILLFEUBAWMTMHIGESSSSAKLHGILYWZDXGNAULHMBOGA

Celui qui l'intercepte ne connaît pas la clé, mais il remarque des groupes répétés. Numérotons les lettres à partir de $0$ :

• MTMHIGESS apparaît aux positions $0$ et $25$ : distance $25$ ;
• HGIL apparaît aux positions $14$ et $39$ : distance $25$ ;
• BOGA apparaît aux positions $10$ et $55$ : distance $45$.

La longueur de la clé divise probablement toutes ces distances, donc leur PGCD : $\mathrm{PGCD}(25\,;45) = 5$. La clé a très probablement $5$ lettres (ou $1$, ce que les fréquences écartent vite). Le message clair était ATTAQUEZ LE PONT PUIS ENSUITE ATTAQUEZ LA GARE PUIS RENDEZ VOUS AU PONT : les répétitions de ATTAQUEZ, de PUIS et de PONT ont trahi la clé. Une répétition peut aussi être due au hasard, surtout pour des groupes de deux ou trois lettres : c'est pourquoi on retient les groupes longs et l'on cherche le diviseur commun au plus grand nombre de distances.

Une fois la longueur $5$ connue, on sépare le message en cinq sous-messages : les lettres de rangs $0$, $5$, $10$, …, puis celles de rangs $1$, $6$, $11$, …, et ainsi de suite. Chacun est chiffré par un simple décalage de César, que l'analyse des fréquences casse comme plus haut. Le chiffre « indéchiffrable » tombe ainsi en cinq petits problèmes faciles.

Il n'existe qu'une parade complète : une clé aléatoire aussi longue que le message, utilisée une seule fois (le « masque jetable »). C'est le seul chiffre dont on démontre qu'il est incassable, mais il faut transporter autant de clé que de message, ce qui le réserve à des usages rares, comme le « téléphone rouge » entre Washington et Moscou pendant la guerre froide.

Chiffrons HELP, découpé en HE et LP.

• HE donne $(7\,;4)$ : $3 \times 7 + 3 \times 4 = 33 \equiv 7$ et $2 \times 7 + 5 \times 4 = 34 \equiv 8$, soit HI.
• LP donne $(11\,;15)$ : $3 \times 11 + 3 \times 15 = 78 \equiv 0$ et $2 \times 11 + 5 \times 15 = 97 \equiv 19$, soit AT.

HELP devient HIAT. Chaque lettre chiffrée dépend des deux lettres du bloc : les fréquences des lettres isolées ne suffisent plus.

Pour notre clé, $\delta = 3 \times 5 - 3 \times 2 = 9$, et $9 \times 3 = 27 \equiv 1$, donc $u = 3$ :

On vérifie le déchiffrement de HI, c'est-à-dire $(7\,;8)$ : $15 \times 7 + 17 \times 8 = 241 \equiv 7$ (H) et $20 \times 7 + 9 \times 8 = 212 \equiv 4$ (E). On retrouve bien HE.

Le chiffre de Hill a une faiblesse : il est linéaire. Si l'ennemi connaît deux blocs clairs et leurs chiffrés (une formule de politesse, une date), il obtient une équation matricielle $Y \equiv KX$ dont il tire $K$ en inversant $X$. Les chiffres modernes mélangent pour cette raison des opérations linéaires et non linéaires.

Tous les chiffres précédents, comme la machine Enigma de la Seconde Guerre mondiale, sont symétriques : la même clé sert à chiffrer et à déchiffrer. Il faut donc d'abord se la transmettre en secret, ce qui est impossible avec un inconnu sur Internet. En 1977, Ronald Rivest, Adi Shamir et Leonard Adleman publient un chiffre à clé publique : chacun peut chiffrer avec la clé publiée par le destinataire, mais seul celui-ci sait déchiffrer. On sait depuis 1997 que Clifford Cocks, aux services secrets britanniques, avait trouvé la même idée en 1973, restée classée secrète.

L'image est celle d'un cadenas ouvert : n'importe qui peut le refermer sur une boîte, mais seul celui qui a la clé peut le rouvrir. Mathématiquement, RSA repose sur un théorème de 1640.

Commençons par un exemple avec $p = 7$ et $a = 3$. Les multiples $3, 6, 9, 12, 15, 18$ ont pour restes modulo $7$ :

On retrouve exactement les nombres de $1$ à $6$, dans un autre ordre. Et l'on constate que $3^6 = 729 = 104 \times 7 + 1$, donc $3^6 \equiv 1 \pmod 7$. Ce n'est pas un hasard.

Le destinataire choisit deux nombres premiers distincts $p$ et $q$, calcule $n = pq$ et $\varphi = (p-1)(q-1)$. Il choisit un exposant $e$ premier avec $\varphi$, puis, par l'algorithme d'Euclide étendu, un entier $d$ tel que $ed \equiv 1 \pmod{\varphi}$.

• Il publie la clé publique $(n\,;e)$ et garde secrète la clé privée $d$.
• Pour lui envoyer un nombre $m$ (avec $0 \leqslant m < n$), on calcule le reste $c$ de $m^e$ modulo $n$.
• Il déchiffre en calculant le reste de $c^d$ modulo $n$.

Puisque $c$ et $m^e$ sont congrus modulo $n$, on a $c^d \equiv m^{ed} \equiv m \pmod n$ : le reste de $c^d$ modulo $n$ est le message $m$, qui est déjà compris entre $0$ et $n - 1$.

Prenons $p = 5$ et $q = 11$ : $n = 55$ et $\varphi = 4 \times 10 = 40$. L'exposant $e = 3$ est premier avec $40$. Pour $d$, l'algorithme d'Euclide donne $40 = 13 \times 3 + 1$, donc $3 \times (-13) \equiv 1 \pmod{40}$ et $d = -13 + 40 = 27$ (on vérifie : $3 \times 27 = 81 = 2 \times 40 + 1$).

Chiffrer le message $m = 7$ : $7^3 = 343 = 6 \times 55 + 13$, donc $c = 13$.

Déchiffrer : il faut le reste de $13^{27}$ modulo $55$. Plutôt que de faire $26$ multiplications, on écrit $27 = 16 + 8 + 2 + 1$ et l'on élève au carré de proche en proche, en réduisant à chaque fois modulo $55$ :

Alors $13^{27} = 13^{16} \times 13^{8} \times 13^{2} \times 13^{1}$, et :

• $31 \times 36 = 1116 \equiv 16$ ;
• $16 \times 4 = 64 \equiv 9$ ;
• $9 \times 13 = 117 \equiv 7$.

On retrouve $m = 7$ avec $7$ multiplications au lieu de $26$. C'est l'exponentiation rapide : pour un exposant de $2\,048$ chiffres binaires, elle demande quelques milliers de multiplications, au lieu d'un nombre qui dépasse tout ce qu'on peut écrire.

Le programme suivant code l'exponentiation rapide et l'algorithme d'Euclide étendu, puis construit une clé RSA avec $p = 61$ et $q = 53$. Modifiez le message ou les nombres premiers.

Un espion connaît $n$ et $e$. Pour trouver $d$, il lui faut $\varphi$, donc $p$ et $q$ : il doit factoriser $n$. Pour $55$, c'est immédiat. Mais on ne connaît aucune méthode rapide pour factoriser un produit de deux nombres premiers de plusieurs centaines de chiffres. En 2020, une équipe en grande partie française a factorisé le nombre RSA-250, de $250$ chiffres décimaux ($829$ bits), au prix d'environ $2\,700$ années de calcul d'un cœur de processeur, réparties sur des milliers de machines. Les clés utilisées aujourd'hui comptent en général $2\,048$ bits ou plus.

Toute la sécurité repose donc sur une asymétrie : multiplier deux nombres premiers est facile, retrouver les facteurs à partir du produit est très difficile. Personne n'a démontré que la factorisation est réellement difficile ; on constate seulement que des générations de chercheurs n'ont pas trouvé de méthode rapide.

En 1976, un an avant RSA, Whitfield Diffie et Martin Hellman montrent comment deux personnes qui ne se sont jamais rencontrées peuvent fabriquer une clé commune en ne s'échangeant que des messages publics. L'image habituelle est celle des pots de peinture : mélanger des couleurs est facile, les séparer est presque impossible.

L'échange de Diffie-Hellman avec de la peinture : Alice et Bob partent d'une couleur commune (common paint), y mêlent chacun une couleur secrète (secret colours), s'envoient les mélanges par un canal public (public transport) puis y ajoutent à nouveau leur couleur secrète. Ils obtiennent la même couleur (common secret), qu'un espion ne sait pas reconstituer. Schéma : A. J. Vinck, version SVG Flugaal, Wikimedia Commons, domaine public.

En mathématiques, la peinture commune est un nombre premier $p$ et un entier $g$, publiés. Prenons $p = 23$ et $g = 5$.

• Alice choisit en secret $a = 6$ et envoie le reste de $5^6$ modulo $23$. Comme $5^2 = 25 \equiv 2$, $5^6 \equiv 2^3 = 8$ : elle envoie $A = 8$.
• Bob choisit en secret $b = 15$ et envoie le reste de $5^{15}$ modulo $23$, qui vaut $B = 19$.
• Alice calcule $B^a = 19^6$ : comme $19 \equiv -4$, $19^6 \equiv 4^6 = 4096 = 178 \times 23 + 2$, donc elle obtient $2$.
• Bob calcule $A^b = 8^{15} = 2^{45}$. Or $2^{11} = 2048 = 89 \times 23 + 1$, donc $2^{44} = \left(2^{11}\right)^4 \equiv 1$ et $2^{45} \equiv 2$.

Ils partagent le secret $2$, car $(g^b)^a = g^{ab} = (g^a)^b$. L'espion connaît $p$, $g$, $A$ et $B$ ; pour trouver le secret, il devrait retrouver $a$ à partir de $5^a \equiv 8$ : c'est le problème du logarithme discret. Avec $23$, on essaie toutes les valeurs ; avec un nombre premier de plusieurs centaines de chiffres, on ne sait pas le faire. Le cadenas des pages https utilise aujourd'hui couramment une variante de cet échange, sur des courbes elliptiques.

En 1994, Peter Shor a montré qu'un ordinateur quantique suffisamment grand pourrait factoriser les entiers et calculer des logarithmes discrets rapidement. RSA et Diffie-Hellman tomberaient alors tous deux. Les machines quantiques actuelles sont encore très loin de la taille nécessaire, et personne ne sait dire avec certitude quand, ni si, elles l'atteindront.

Le danger est pourtant pris au sérieux dès maintenant, à cause d'une stratégie appelée « récolter maintenant, déchiffrer plus tard » : un service de renseignement peut enregistrer aujourd'hui des communications chiffrées et attendre de pouvoir les lire. Des secrets qui doivent rester protégés pendant trente ans sont donc déjà menacés.

D'où la cryptographie post-quantique : des méthodes fondées sur d'autres problèmes, que l'on ne sait résoudre rapidement ni avec un ordinateur classique ni avec un ordinateur quantique. Après un concours international ouvert en 2016, l'agence américaine de normalisation (NIST) a publié en août 2024 trois premières normes, dont deux reposent sur des problèmes de réseaux de points (trouver un point proche dans une grille de très grande dimension), décrits avec des matrices et des congruences. Plusieurs navigateurs et messageries ont commencé à les combiner avec les méthodes classiques.

La cryptographie a aussi toujours une dimension géopolitique : cassage d'Enigma, restrictions à l'exportation des logiciels de chiffrement dans les années 1990, débats actuels sur l'accès des polices aux messageries chiffrées. Les mathématiques y sont une arme autant qu'un bouclier.