"Les mathématiciens ont gagné la guerre !" - résonne une voix au début du film "Un homme d'exception". Cette phrase peut surprendre car la mémoire collective n'a pas gardé les codes secrets comme un élément important de la guerre. La raison est que les travaux des mathématiciens ont été secrets pendant la guerre et ils ont été classés «secret défense» jusqu'en 1995. Quand ils ont été rendus publics on a appris que les aliés ont décrypté approximativement un tiers des messages allemands. Cela a permis aux convois anglais de contourner la blockade des 1154 sous-marins allemands dans l'Atlantique et d'apporter des ravitaillements, si précieux dans la bataille d'Angleterre où ils étaient plus précieux que les bombes.
Enigma se présente comme une machine à écrire. Quand on tape un texte au clavier, les lettres du mesage chiffré s'allument une à une dans une rangée d'ampoules marquées de A à Z. Avant de partir en mission les unités militaires allemandes prenaient un cahier avec les réglages de la machine pour chaque jour, entre 0h00 et 23h59. Une personne tapait le message sur la machine Enigma et une autre lisait le chiffré sur la rangée des ampoules. Ensuite le message était transmis par la radio et une autre unité le déchiffrait. Pour ce faire, une personne règlait la machine Enigma de la même manière que la première unité et tapait le texte chiffré au clavier. Une autre personne lisait le message clair sur la rangée des ampoules. Notez que le chiffrement et le déchiffrement se fasait de la même manière.
L'histoire d'Enigma s'articule en trois moments.
Pour le reste de l'article on va s'intéresser aux travaux des Polonais, qui utilisent peu de prérequis mathématiques et aucun prérequis informatique. A contrario, les travaux de l'équipe de Turing sur les Bombes marquent la naissance des ordinateurs. En effet, les Bombes sont le premier ordinateur programmable, c'est à dire dont on peut changer la tâche. La première machine de calcul prgrammable a été la machine Z3 construite par Konrad Zuse en 1939, mais elle n'a jamais fonctionné à cause de quelques défauts mineurs de conception. Le deuxième ordinateur de l'histoire a été la Bombe d'Alan Turing et Harold Keen, dont quelques centaines d'exemplaire ont été utilisés à Bletchley Park. (footnote Une chronologie de l'histoire de l'ordinateur est disponible en anglais ici).
Nous utilisons la notion de permutation d'un ensemble ayant un nombre fini d'éléments, qui est enseignée parfois aux lycéens de 1ère et parfois aux étudiants des filières scientifiques. Pour lire une introduction due à Lara Thomas, cliquez sur l'image suivante :
.
Avant de voir le théorème principal, on commence par une définition.
Définition Soit $\sigma$ une permutation de l'ensemble $E$ et $e$ un élément de $E$. Pour tout entier $i$, on note $\sigma^i(e)$ l'élément $\sigma(\sigma(\cdots(\sigma(e)\cdots))$, où $\sigma$ apparaît $i$ fois. On appelle orbite de $e$ par $\sigma$ l'ensemble des positions successives de $e$ quand on répète la permutation $\sigma$ : l'ensemble $\mathcal{O}(e,\sigma)=\{e,\sigma(e),\sigma^2(e),\sigma^3(e),\ldots\}$, qui est forcément fini car contenu dans $E$. On appelle motif de décomposition de $\rho$ la liste des longueurs de ses orbites triée par ordre croissant.
Exemple 1 Considérons la permutation $\rho=\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
2 & 3 & 1 & 5 & 4
\end{pmatrix}$. Alors $\rho(1)=2$, $\rho^2(1)=3$ et $\rho^3(1)=1$ et les autres puissances de $\sigma$ ne feront que répéter ces trois valeurs, donc l'orbite de $1$ est $\{1,\rho(1),\rho^2(1),\ldots\}=\{1,2,3\}$. De même on trouve que l'orbite de $4$ est $\{4,\rho(4),\rho^2(4),\ldots\}=\{4,5\}$. Ainsi le motif de décomposition de $\rho$ est $[2,3]$.
Exemple 2 On appelle $\rho$ la permutation qui associe à tout astre du système solaire l'astre situé à la même distance du soleil qui se trouve à un angle supérieur en sens trigronomique. Cela fait associer à toute planète elle même mais associe à tout astéroïde un astéroïde différent. Dans ce cas les orbites de la permutation $\rho$ coïncident aux orbites physiques.
Théorème Soient $\sigma$ et $\rho$ deux permutations. Alors $\rho$ et $\sigma\circ \rho\circ \sigma^{-1}$ ont le même motif de décomposition.
preuve :
Il suffit de prouver que, pour tout $e\in E$ les orbites $\mathcal{O}(e,\sigma)$ et $\mathcal{O}(\rho(e),\sigma\circ\rho\circ\sigma^{-1})$ on la même longueur. Soit $f$ un élment de $\mathcal{O}(e,\sigma)$ et $i$ un entier tel que $f=\sigma^i(e)$. Alors $\sigma(f)=\sigma(\rho^i(e))$. D'autre part $(\sigma\circ\rho\circ\sigma^{-1})^i(\sigma(e))=\sigma(\rho^i(e))$, donc $\sigma(f)$ appartient à $\mathcal{O}(\sigma(E), \sigma\circ \rho\circ \sigma^{-1})$. Réciproquement, soit $g$ un élément de $\mathcal{O}(\sigma(E), \sigma\circ \rho\circ \sigma^{-1})$ et soit $j$ un entier tel que $g=(\sigma\circ\rho\circ\sigma^{-1})^j(\sigma(e)) $. Alors $g=\sigma(\rho^j(e))$ donc $\sigma^{-1}(g)$ appartient à $\mathcal{O}(e,\rho).$
Avant de voir comment Enigma est construite il faut comprendre qu'elle ne fait qu'automatiser un chiffrement faisable à l'aide uniquement d'un crayon et d'un cahier.
Comme expliqué dans un article d'Images des maths , à l'époque où Enigma a été conçue la méthode de chiffrement la plus connue été celle de la substitution. Cette méthode de chiffrement consiste à appliquer une permutation $\rho$ aux lettres de l'alphabet. Ainsi le texte ALICE est chiffré par $\rho$(A) $\rho$(L) $\rho$(I) $\rho$(C) $\rho$(E). Cette méthode, utilisée juqu'au XIIe siècle dans l'Occident, notamment par l'ordre des Templiers, a été cassée par le savant musulman Al Kindi au IXe siècle dans « Manuscrit sur le chiffrement des messages cryptographiques ». Pour contrecarréer la méthode d'Al Kindi on écrit une permutation de l'alphabet sur chaque page d'un cachier : $\rho_1$ sur la page $1$, $\rho_2$ sur la page $2$, etc. Pour chiffrer le message ALICE on obtient $\rho_1$(A) $\rho_2$(L) $\rho_3$(I) $\rho_4$(C) $\rho_5$(E).La machine Enigma a pour but d'automatiser ce processus.
Enigma se présente comme une machine à écrire. Pour chiffrer une lettre on appuie sur la touche correspondante du clavier et une des ampoules étiquetées de A à Z s'allume, indiquant le chiffré. Si on avait 26 machines identiques réglés de la même façon et si on tapait A sur la première, B sur la deuxième etc alors on obtiendrait une permutation $\rho_1$ de l'alphabet $\{A,\ldots,Z\}$. Après que l'ampoule s'allume la machine passe dans un nouvel état où elle décrit une nouvelle permutation $\rho_2$, ensuite dans une permutation $\rho_3$ et ainsi de suite. Cela revient à chiffrer ALICE par $\rho_1$(A) $\rho_2$(L) $\rho_3$(I) $\rho_4$(C) $\rho_5$(E).
Chaque état de la machine est décrit par trois lettres qui peuvent se répéter, noté $\mathcal{R}$ et appelé position des rotors, et un ensemble de couples de lettres n'ayant aucune lettre en commun, noté $\mathcal{C}$ et appelé choix des cablages. En effet, trouver la permutation $\varepsilon$ effectuée par Enigma dans un certain état $(\mathcal{R},\mathcal{C})$ il faut suivre pour chaque lettre le cable qui part de sa touche jusqu'à arriver à une ampoule. Le cable commence par passer part la partie avant de la machine où soit il continue inchangé soit il passe par un des cables extérieurs. Par exemple, dans la figure ci-desous un cable relier A et O et un autre S et J. Cela correspond au choix des cablages $\mathcal{C}=\{\{A,O\},\{S,J\}\}$ et à la permutation
Après avoir traversé le tableau des cablages, le fil continue vers trois rotors qui se présente comme 3 roues pivotant autour d'un même axe, numérotés I, II, III. Chaque rotor est traversé par 26 cables qui ne se touchent pas et qui réalise une permutation des 26 lettres. Après avoir traversé les 3 rotors dans le ordre I, II, III le fil fait une boucle dans une pièce appelée réflecteur, rentre dans le rotor III par un autre trou que celui d'où il est sorti et parcourt les rotors dans l'ordre III, II et I. Une petite fenêtre permet de voir une lettre de chaque rotor, de façon que un triplet de lettres $R$ donne la position des 3 rotors. Nous notons $\rho_\mathcal{R}$ la permutation effectuée par la série de pièces : rotor I, rotor II, rotor III, réflecteur, rotors III, rotor II et rotor I. Finalement le fil parcourt une 2e fois les cablages et arrive aux ampoules.
À chaque fois qu'une touche est appuyée les rotors changent de position, en général comme les chiffres d'un chronomètre (AAA, AAB, AAC, ..., AAZ, ABA, ABB, ABC, ...) mais parfois on saute un triplet ou deux selon des critères compliqués. Dans nos solutions nous supposons que nous pouvons utiliser une machine Enigma identique à celle qui a chiffré les messages, donc on peut trouver le triplet de lettres qui suit un triplet donné. Si $R$ est un triplet on note $R^{(1)}$ le suivant, $R^{(2)}$ le deuxième suivant, et en général $R^{(n)}$ le triplet qui arrive après que $n$ lettres ont été chiffrées.
La permutation effectuée par Enigma ayant les rotors en position \mathcal{R} et les choix des couplages $\mathcal{C}$ est donc :
Comment faisaiet-on pour communiquer les réglages $\mathcal{R}$ et $\mathcal{C}$ ? Les $6$ premières lettres de chaque message étaient chiffrés avec le réglage du jour : toutes les machines Enigma étaient accompagnées d'un exemplaire d'un même catalogue, qui associait à chaque date du calendrier une valeur de $\mathcal{R}$ et une valeur de $\mathcal{C}$, à utiliser entre 0h00 et 23h59.
Pour chaque message la personne qui utilisait Enigma pour chiffrer pensait à un triplet de lettres, disons AZE. Il le chiffrait pour obtenir par exemple GUF. À cause du manque de fiabilité de la transmission par la radio, on avait besoin de répéter le triplet de lettres. Ainsi on aurait pu attendre que les 6 lettres transmises soit GUFGUF. De façon spectaculaire, les Allemands ne faisaint pas cela mais à la place chiffraient le message AZEAZE pour obtenir GUFQSP et l'envoyaient une seule fois. Après le chiffrement des 6 lettres, les rotors étaient repositionnés sur la triplet AZE et on chiffrait le message proprement-dit. (footnote : En 2009 Karsten Nohl a trouvé une faille dans le chiffrement des téléphones portables qui correspond à la même erreur : dans le protocol GSM 2 on chiffre le répété au lieu de répéter le chiffré.) Pour les lecteurs qui veulent essayer de casser les codes, voici les 6 premières lettres de quelques exemples de messages interceptés (attention GUFQSP n'est pas le chiffré de AZEAZE pour ne pas aider à la résolution):
Considérons le message intercepté CESBZV. Il chiffre un message abcabc où a, b et c sont trois lettres inconnues. Si $\mathcal{R}$ et $\mathcal{C}$ sont les réglages inconnus du jour, alors on sait que $\sigma_\mathcal{C}\circ\rho_\mathcal{R}\circ\sigma_\mathcal{C}(a)=C$ et $\sigma_\mathcal{C}\circ\rho_\mathcal{R}^{(3)}\circ\sigma_\mathcal{C}(a)=B$. Ainsi on a
$\sigma_\mathcal{C}\circ\rho_{\mathcal{R}^{(3)}}\circ\rho_\mathcal{R}^{-1}\circ\sigma_\mathcal{C}(C)=B$.
Grace à la 1ère et 4e lettre des autres messages interceptés on retrouve toutes les valeurs de la permutation $\sigma_\mathcal{C}\circ\rho_{\mathcal{R}^{(3)}}\circ\rho_\mathcal{R}^{-1}\circ\sigma_\mathcal{C}=\beta_0$ où
On obtient donc :
Problème 1: Étant donné trois permutations $\beta_0$, $\beta_1$ et $\beta_2$ de l'alphabet et une formule pour calculer $\mathcal{R}^{(n)}$ pour tout triplet de lettres $\mathcal{R}$ et tout entier $n$, trouver un triplet de lettre $\mathcal{R}$ et un ensemble de 6 pairs disjointes de lettres $\mathcal{C}$ tels que
Le nombre de triplets de lettres est $26^3=17576$. Le nombre de cablages (pairs de lettres échangées dans les cablages) a évolué entre les premières et les derières versions d'Enigma, passant de $6$ à $10$ pairs de lettres. Pour fixer les iées, concentrons nous sur la version avec $6$ pairs de lettres. Chaque cablage comprend 12 lettres ayant : 26 choix pour la première, 26-1=25 pour la 2e, 24=26-2 pour la 3e, et ainsi de suite jusqu'à 26-11=15 pour la 12e lettre. Une fois choisie $12$ lettres $(a_1,\ldots,a_{12})$, on peut former $6$ cablages en reliant $a_1$ à $a_2$, $a_3$ à $a_4$ et ainsi de suite. Puisque le choix $(a_2,a_1,a_3,a_4,\ldots,a_{12})$ donne le même réglage de la machine il faut diviser par $2^6$. De même le choix $(a_3,a_4,a_1,a_2,a_5,\ldots,a_{12})$ donne le même réglage de la machine donc il faut diviser par le nombre de façons dont on peut permuter les $6$ cables, qui est $6!$. Ainsi le nombre de cablages est $26\cdot\cdots\cdot15/(2^6\cdot 6!)$. En multipliant le nombre de choix pour $\mathcal{R}$ et celui des choix pour $\mathcal{C}$ on obtient :
| nombre de réglages ($\mathcal{R},\mathcal{C}$) d'Enigma | = | $26^3\cdot(26\cdot\cdots\cdot15)/(2^6\cdot 6!)$ |
| $\approx$ | $1.7\cdot 10^{15}.$ |
Un ordinateur moderne peut effectuer 9GHz opérations. Ici G est une abbréviation pour giga soit $10^9$ et Hz une abréviation pour Hertz soit "par seconde" donc un ordinateur fait $9\cdot10^9$ opérations arithmétiques par seconde. En multipliant par le nombre de secondes d'un jour, $86400=60\cdot60\cdot24$, on obtient :
L'idée de génie des mathématiciens Polonais est de remplacer le Problème 1 par deux problèmes bien plus faciles :
En effet, d'après le Théorème 1, les permutations $\sigma_C\circ \rho_R^{-1}\circ \rho_{R^{(3)}}\circ \sigma_C$ et $\rho_R^{-1}\circ\rho_{R^{(3)}}$ ont le même motif de décomposition. Il est de même pour $\sigma_C\circ \rho_R^{-1}\circ \rho_{R^{(3)}}\circ \sigma_C$ et $\rho_R^{-1}\circ\rho_{R^{(3)}}$ et pour $\sigma_C\circ \rho_R^{-1}\circ \rho_{R^{(3)}}\circ \sigma_C$ et $\rho_R^{-1}\circ\rho_{R^{(3)}}$. En résolvant le Problème 2.a on trouve $\mathcal{R}$. Ensuite on pose $\alpha_0=\rho_{\mathcal{R}^{(3)}}\circ \rho_\mathcal{R}^{-1}$, $\alpha_1=\rho_{\mathcal{R}^{(4)}}\circ \rho_{\mathcal{R}^{(1})}^{-1}$ et $\alpha_2=\rho_{\mathcal{R}^{(5)}}\circ \rho_{\mathcal{R}^{(2})}^{-1}$. Cela fournit $\mathcal{C}$.
La solution du Problème 2.a consiste à énumérer tous les $26^3=17576$ triplets de lettres et pour chacun à calculer le motif de décomposition de $\rho_{R^{(3)}}\circ \rho_\mathcal{R}^{-1}$ et à le comparer avec celui de $\beta_0$. Si un triplet passe le teste après on vérifie si les motifs de décomposition de $\sigma_C\circ \rho_R^{-1}\circ \rho_{R^{(3)}}\circ \sigma_C$ et $\rho_R^{-1}\circ\rho_{R^{(3)}}$ sont égaux respectivement à ceux de $\beta_1$ et $\beta_2$. Pour cela Rejewski, Rozycki et Zygalski ont construit la machine Bomba, qui résolvait le problème 2.a en moins d'une heure. Notre programme prend 12 secondes pour trouver les seuls triplets possibles : (B,A,E), (B,O,B) et (B,U,W).
La solution du Problème 2.b à énumérer tous les triplets de lettres $(a_1,a_2,a_3)$ et à assigner $\sigma(A)=a_1$, $\sigma(B)=a_2$ et $\sigma(C)=a_3$. Ensuite pour toute lettre $a$ pour laquelle on a fixé $\sigma(a)$ on peut fixer pour $i=0,1,2$ la valeur de $\beta_i(a)$ en posant
Notre programme prend 18 millisecondes pour trouver l'unique cablage possible pour $\mathcal{R}$=(b,O,B) : $\mathcal{C}=\{\{C,R\},\{Y,P\},\{T,O\},\{G,A\},\{H,I\},\{E,S\}\}$. Même les dernières versions d'Enigma qui utilisaient 10 cables se cassent en moins de 10 secondes. Pour les mathématiciens Polonais aussi, le problème 2.b prenait beaucoup moins de temps que le 2.a. D'ailleurs si on place le premier cable correctement on peut s'en rendre compte avant de tester les autres, mais nous n'avons pas besoin de cette amélioration.
Enigma est un exemple classique de problème cryptologique et sa solution est un modèle pour d'autres défis. Prenons un exemple rapide : une phrase a été écrite dans une grille de $6 \times 6$ lettres, sans espaces. Ensuite on a appliqué une permutation $\mathcal{R}$ des $6$ rangées de lettres et une permutation $\mathcal{C}$ des $6$ colonnes :
| a | e | d | n | i | r |
| t | o | o | e | u | j |
| n | l | p | o | a | r |
| r | l | s | u | m | a |
| u | o | a | q | n | d |
| n | e | a | n | r | i |
Une meilleur solution consiste à diviser le problème en deux problèmes plus simples: trouver $\mathcal{C}$ puis trouver $\mathcal{R}$. En effet, on peut reconnaitre une phrase en françasi même si on ne voit qu'un partie. On essaie les 620 possibilités pour $\mathcal{C}$ en éliminant la grande partie car certaines lettres ne peuvent pas se suivre, comme par exemple "q" et "d".Suppsons maintenant qu'on a trouvé la solution pour $\mathcal{C}$ et on obtient "nadire" sur la première rangée. Le texte devient :
| n | a | d | i | r | e |
| e | t | o | u | j | o |
| o | n | p | a | r | l |
| u | r | s | m | a | l |
| q | u | a | n | d | o |
| n | n | a | r | i | e |
Cet exemple est extrait du tour 3 de l'édition 2016-2017 du concours Alkindi.