Importance historique

« 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 les codes secrets ne sont pas restés dans la mémoire collective à cause du caractère secret de ces travaux, classés secret défense jusqu’en 1995.

Conçue par l’ingénieur Arthur Scherbius en 1923, la machine Enigma a été commercialisée à toute personne qui voulait garder la confidentialité de ses communications, par exemple aux sociétés industrielles. Après un échec commercial cuisant, Scherbius a décidé en 1926 de vendre la machine à l’armée allemande, sans anticiper qu’elle allait servir aux nazis.

Grâce aux informations procurées par les services secrets Français en 1931, trois mathématiciens polonais, Marian Rejewski, Jerzy Różycki et Henryk Zygalski, ont réussi l’exploit de casser les codes d’Enigma. Leurs travaux ont été communiqués aux services secrets anglais en 1939, dans la forêt quelques jours avant que les tanks nazis entrent dans le pays. Les Britanniques ont ainsi pu lire les communications allemandes lors des six premiers mois de guerre. En se basant sur les travaux des Polonais, l’équipe du mathématicien anglais Alan Turing a réussi à casser les nouvelles versions d’Enigma et a offert à l’Angleterre un avantage considérable. Le caractère secret a fait que tous les documents furent détruits, mais on sait d’après les témoignages des anciens de l’équipe de Turing que plus d’un quart des messages allemands ont été décryptés.

Jamy explique dans un épisode de la série « C’est pas sorcier » comment les Alliés ont préparé le débarquement de Normandie en mettant les nazis sur une mauvaise piste. L’opération Fortitude est décrite dans la vidéo ci-dessous, à partir de la seconde 7:00. Il faut rajouter que les Anglais ont pu casser les messages allemands, chiffrés par Enigma, et montrer que l’opération Fortitude avait réussi. En cas d’échec le débarquement aurait été surement retardé :

Dans cet article nous étudions les travaux des Polonais car ils sont purement mathématiques, au contraire des travaux des Anglais qui combinent des aspects mathématiques et informatiques.

Le film « Imitation game » nous plonge dans l’atmosphère du petit village de Bletchley Park où les mathématiciens britanniques ont travaillé, sous l’alibi d’une fabrique de récepteurs radio. À la seconde 0:20 on voit le fonctionnement d’une machine Enigma :

L’intérieur de la machine

Quand on sort Enigma de sa caisse en bois, on voit qu’elle est constituée de

1. une pile ;
2. 26 lampes correspondant aux 26 lettres de l’alphabet ;
3. 26 touches de clavier correspondant elles aussi aux lettres ;
4. nombreux câbles qui relient les différents composants.

Pour chiffrer un message, on le tape sur le clavier et on lit son chiffré sur la rangée des lampes, par exemple on peut taper ALICE et lire BBODC. Quand on appuie sur une touche, par exemple A dans la figure ci-dessous, une petite barre bouge pour créer un contact électrique et obtenir ainsi un câble continu entre la pile et une des 26 lampes. Le chiffré de A est obtenu en suivant le câble qui part de A jusqu’à son arrivée sur une autre lettre, disons B.

Si on démonte patiemment la machine, alors on voit qu’à tout moment les câbles électriques forment exactement 26 chemins, qui partent des touches du clavier et vont aux lampes. Pour ce faire, les câbles traversent la zone avant de la machine, qu’on appellera tableau des connexions, une zone de pièces mobiles appelés rotors, une zone où ils rebroussent chemin, appelée réflecteur, de nouveau la zone des rotors et de nouveau le tableau des connexions. Voici un schéma pour fixer les idées.

Remarquez que le tableau des connexions et les rotors ont été représentés par des nuages pour indiquer que la façon dont les câbles échangent leur position est compliquée et qu’on n’aura pas besoin de la regarder en détail. Disons seulement que le tableau des connexions est une partie de la machine comportant 26 prises marquées de A à Z. Pour échanger 2 lettres on branche un câble entre les prises correspondantes.

Les rotors sont des roues en caoutchouc comportant 26 câbles qui les traversent en échangeant leur position d’une manière compliquée, comme les fils d’une tresse. Après chaque lettre tapée, un ou deux rotors tournent d’un cran pour former une nouvelle permutation des câbles. Un billet d’Images des maths sur l’histoire de la cryptologie explique pourquoi toute machine de chiffrement doit contenir des pièces mobiles pour ne pas réaliser un chiffrement de substitution.

Le réflecteur est une partie d’Enigma où les câbles rebroussent chemin. Il est connu et ne change jamais, donc ne rajoute pas de sécurité au chiffrement. Son rôle était de simplifier l’usage d’Enigma car il échangeait les lettres deux à deux et alors la succession rotors, réflecteur, rotors en sens inverse avait la propriété que, si A est chiffré par R, alors R est chiffré par A. On pouvait donc régler la machine de la même manière que ce soit pour déchiffrer un message reçu ou pour chiffrer un nouveau message.

Les réglages R et C

Pour régler la machine on doit :

1. choisir 3 rotors parmi les 5 fournis avec la machine, ainsi que leur ordre ;
2. positionner chacun des rotors à une de ses 26 positions ;
3. choisir 10 paires de lettres à brancher dans le tableau des connexions.

Les cryptanalystes doivent d’abord trouver les 3 rotors parmi les 5 utilisés. Pour cela on a $5\cdot 4\cdot3=60$ possibilités. Quitte à répéter le travail suivant $60$ fois ou à le faire en parallèle sur $60$ ordinateurs, on peut supposer qu’on connaît ce choix. L’information recherchée par les cryptanalystes est donc :

• R, un triplet de lettres, désignant la position des 3 rotors ;
• C, 10 paires de lettres échangées dans le tableau des connexions.

Lors de la guerre, Enigma était accompagné d’un cahier comme ci-dessous, qui permettait aux unités militaires allemandes d’utiliser les mêmes rotors, ainsi que les mêmes valeurs de R et C. Chaque jour à 0h00, une personne réglait la machine en suivant les choix R et C, appelé réglage initial. Dans la journée, on remettait la machine dans la même configuration avant chaque usage, de telle sorte que tous les messages commençaient par le même réglage.

Quelques notions mathématiques

Avant de présenter la solution,

La cryptanalyse d’Enigma

Chaque jour les mathématiciens polonais puis les résidents de Bletchley Park cherchaient le réglage du jour (R,C). La première étape était pour les Polonais de trouver la permutation effectuée par la machine dans son réglage initial. En effet, appelons $\sigma$ la permutation effectuée par le tableau des connexions et $\rho$ la permutation effectuée par la succession rotors, réflecteur, rotors en sens inverse, dans la configuration initiale. Appelons aussi $\rho'$ la permutation faite par la même succession après qu’on a tapé sur une lettre et que les rotors aient bougé, $\rho''$ la permutation après 2 touches, et ainsi de suite avec $\rho'''$, $\rho^{(4)}$, $\rho^{(5)}$, etc.

Quand on chiffre le message ALICE, la lettre A est chiffrée par $\sigma$, puis $\rho$, puis $\sigma$ parcourue en sens inverse donc $\sigma^{-1}$. Ainsi le chiffré de $A$ est $(\sigma^{-1}\rho \sigma)(A)$. Quand on chiffre $L$, on l’envoie d’abord sur $\sigma(L)$, puis on le chiffre par la succession rotors-réflecteur-rotors au sens inverse. Comme on a déjà tapé une lettre, les rotors ont bougé, donc la permutation faite est $\rho'$. Finalement, $\rho'(\sigma(L))$ est passé par le tableau de connexions en sens inverse donc on lui applique $\sigma^{-1}$. On obtient ainsi $(\sigma^{-1}\rho'\sigma)(L)$. On continue et on trouve que le message ALICE est chiffré par \[ (\sigma^{-1}\rho \sigma)(A) (\sigma^{-1}\rho' \sigma)(L) (\sigma^{-1}\rho'' \sigma)(I) (\sigma^{-1}\rho''' \sigma)(C)(\sigma^{-1}\rho^{(4)} \sigma)(E). \]
Pour chaque message on remettait la machine dans la configuration initiale donc la première lettre de chaque message était chiffrée par $\sigma^{-1}\rho\sigma$.

Du côté des cryptanalystes, il est possible de trouver $\sigma^{-1}\rho\sigma$ ! En effet, en l’espace de 24 heures, chaque unité allemande envoyait entre deux et trois cents messages, dont beaucoup étaient prévisibles. Certaines unités envoyaient le message « Rien à signaler » pour montrer qu’ils ont bien fait le réglage. D’autres commençaient par saluer le Führer et utilisaient un vocabulaire très restreint. Mais la plus significative a été la météo car elle était omniprésente dans les communications militaires. Les cryptanalystes de Bletchley Park se promenaient avec des antisèches sur lesquelles étaient écrits des mots allemands, appelés « crib » qui signifie « antisèche ».

Pour faire simple, plaçons nous dans la situation où nous avons intercepté le premier mot d’une cinquantaine de messages différents, au moins un message commençant par chaque lettre. Par exemple, si le message « Attendez » a été chiffré par « XRBOORJH », « Bienvenue » par « GEBOUTTNR » et « Cinq degrés » par « VFGRGYFHZQ » alors $(\sigma^{-1}\rho\sigma)(A)=X$, $(\sigma^{-1}\rho\sigma)(B)=G$ et $(\sigma^{-1}\rho\sigma)(C)=V$.

Sécurité apparente

La première méthode à laquelle on pense quand il faut trouver les réglages du jour (R,C) est d’énumérer toutes les possibilités et d’essayer de déchiffrer un message quelconque. Pour chaque réglage possible on tape le message chiffré à une machine Enigma réglée ainsi et on voit si on reconnait ou pas un mot français. Cette méthode ne s’automatise pas très bien car un ordinateur ne sait pas reconnaitre un mot français, à moins de parcourir à chaque fois le dictionnaire, ce qui multiplie le temps de calcul par plus de cent mille. Dans les années 1930 et 1940 les cryptanalystes se sont toujours arrangés pour trouver la permutation initiale $\sigma^{-1}\rho\sigma$ ou une permutation similaire.

La sécurité apparente d’Enigma est alors celle d’énumérer tous les couples (R,C) possibles, de simuler le comportement de la machine dans sa configuration (R,C) pour obtenir $\sigma^{-1}\rho\sigma$ (les plans de la machine étaient connus) et de la comparer à la permutation initiale, telle qu’elle a été déduite à partir des messages interceptés. Pour estimer la sécurité, on évalue le nombre de couples (R,C) : le nombre de triplets R multiplié par le nombre de choix des connexions C. Dans la suite on reprend l’analyse d’une vidéo de la chaîne Science4all .

Le nombre de possibilités pour R est égal au nombre de triplets de lettres : $26\cdot26\cdot26=17576$. Pour choisir les 10 paires de lettres à connecter, on commence par choisir 20 lettres différentes : pour la première on a 26 choix, pour la 2e on a 25 choix et ainsi de suite, donc on a $26\cdot25\cdot24\cdot23\cdot22\cdot\cdots\cdot7$ possibilités. Notons $a_1$ la première lettre choisie, $a_2$ la 2e, $\ldots$, $a_{20}$ la dernière lettre choisie. On observe que le fait d’échanger $a_1$ et $a_2$ revient à débrancher le câble et à le remettre à sa place. On divise donc le nombre de possibilités par $2$ pour chaque câble, donc on divise le tout par $2^{10}$. De même, le fait d’échanger un câble par un autre ne change pas la configuration, par exemple si on met les lettres des connexions dans l’ordre $a_3$, $a_4$, $a_1$, $a_2$, $a_5$, $a_6$, $\ldots$, alors on obtient le même branchement que dans l’ordre initial $a_1$, $a_2$, $\ldots$. Il faut donc diviser par le nombre de façons de permuter $10$ câbles, ce qui vaut $1\cdot2\cdot 3\cdots10$, noté $10!$. Ainsi le nombre de réglages d’Enigma est \[26^3\cdot26\cdot25\cdots7/(10 !\cdot2^{10})= 150 738 274 937 250.\]
Un ordinateur moderne a une fréquence d’environ 2 GHz, ce qui signifie qu’il fait $2\cdot 10^9$ opérations par seconde, soit $7200000000000$ par heure. Si on est optimiste et on dit qu’une seule opération suffit pour énumérer un réglage (R,C), alors le cassage d’Enigma prendrait 21 heures. Comme le réglage changeait toutes les 24 heures et comme on a négligé le facteur 60 du choix et la position des 3 rotors parmi les 5 possibles, ainsi que le coût des calculs pour chaque réglage, la machine Enigma a une sécurité apparente suffisante pour l’année 2018 (pour se protéger contre une attaque avec un seul ordinateur de bureau). Les ordinateurs des années 1940, ci-dessous, auraient mis des millions d’années !

La solution polonaise

L’idée de génie des mathématiciens polonais a été de couper le problème en deux : d’abord on trouve R en oubliant C puis on fixe R et on cherche C. Ainsi on laisse le tableau des connexions sans aucun câble et on énumère les 17576 possibilités pour R. Au lieu de vérifier si la permutation obtenue est égale à celle qu’on cherche, on teste seulement si les deux ont une propriété mathématique commune. Rappelons que, si $\sigma$ est la permutation faite par le tableau des connexions et $\rho$ la permutation réalisée par les rotors dans la configuration initiale, alors la permutation totale d’Enigma est $\sigma^{-1}\rho\sigma$.

Les mathématiciens polonais ont utilisé un théorème très ancien :

Augustin Louis Cauchy

Théorème.(de Cauchy) Si $\sigma$ et $\rho$ sont deux permutations d’un ensemble $E$. Alors la permutation $\sigma^{-1}\rho\sigma$ est égale à la permutation obtenue en appliquant $\rho$ au même ensemble après avoir renommé chaque $x\in E$ en $\sigma^{-1}(x)$.

Par exemple voici ci-dessous à gauche la permutation $\sigma^{-1}\rho\sigma$ pour deux permutations $\sigma$ et $\rho$. À droite on garde la permutation $\sigma$ car la forme des flèches est la même. Par contre on a effacé les noms des lettres $x$ et marqué dessus $\sigma^{-1}(x)$, par exemple on a effacé $A$ et marqué $\sigma^{-1}(A)=B$. D’après le Théorème de Cauchy, les deux figures représentent la même permutation. Par exemple, si on cherche l’image de $C$, alors à gauche comme à droite on trouve $B$, si on cherche l’image de $F$ alors à gauche comme à droite on trouve $A$.

Un invariant pour les permutations

Les mathématiciens aiment chercher ces propriétés d’un objet mathématique qui restent inchangées quand il subit une transformation. Par exemple quand on applique une symétrie à une figure géométrique, la longueur des segments est invariante. Quand on ajoute un multiple de 10 à un entier, le dernier chiffre est invariant. On peut alors se demander quelle est la propriété d’une permutation d’un ensemble E qui reste inchangée quand on renomme les éléments de E.

On appelle orbite d’un élément $A$ par une permutation $\sigma$ l’ensemble des éléments qui sont atteints si on répète la permutation $\sigma$ :
\[\text{orbite}(A,\sigma)=\{A,\sigma(A),\sigma(\sigma(A)),…\}.\]
Si l’ensemble permuté est fini alors toutes les orbites sont finies et on appelle motif de décomposition de $\sigma$ l’ensemble des longueurs des orbites distinctes, triées par ordre croissant.

Pour calculer le motif de décomposition on dessine les éléments permutés en cercle et on représente la permutation par des flèches :

Par la permutation de gauche, $A$ est envoyé sur $\sigma(A)=B$. À son tour $\sigma(A)=B$ est envoyé sur $\sigma(\sigma(A))=\sigma(B)=D$, puis $D$ est envoyé sur $\sigma(\sigma(\sigma(A)))=C$ et finalement $C$ est envoyé sur $A$. Donc une des orbites est formée des lettres $\{A,B,D,C\}$. De même on a $\sigma(E)=F$ et $\sigma(\sigma(E))=E$ donc $\{E,F\}$ est une orbite et alors le motif de décomposition de la permutation de gauche est $(2,4)$. De manière analogue le motif de la permutation de droite est $(3,3)$.

Rappelons nous maintenant que, d’après le théorème de Cauchy, la permutation $\sigma^{-1}\rho\sigma$ est la même que la permutation $\rho$ après avoir renommé les éléments de l’ensemble. On vient de prouver :

Corollaire(du théorème de Cauchy) Si $\sigma$ et $\rho$ sont deux permutations d’un ensemble fini, alors $\rho$ et $\sigma^{-1}\rho\sigma$ ont le même motif de décomposition.

Par exemple, après avoir renommé les éléments de l’ensemble $\{A,B,C,D,E,F\}$, on obtient :

La méthode polonaise consiste donc à énumérer les triplets R, à trouver $\rho$ et à calculer son motif de décomposition. Pour la grande majorité des triplets il ne coïncide pas avec celui de la permutation initiale, telle qu’elle a été trouvée d’après les messages interceptés, donc on peut éliminer presque tous les triplets.
En essayant la méthode polonaise sur différentes réglages possibles (notre programme met 11 secondes au lieu de 21 heures sans le motif de décomposition), on observe que généralement on élimine tous les triplets sauf un petit nombre, généralement deux ou trois.

Fin de la résolution

Une fois le nombre de possibilités pour R réduit à deux ou trois on peut toutes les tester. On connait maintenant $\sigma^{-1}\rho\sigma$ et $\rho$.
On cherche C en essayant toutes les possibilités de câblage pour les lettres A, B, C, soit $26^3=17576$ possibilités. Remarquons que pour toute lettre où on a assigné une valeur à une lettre $L_1$ en choisissant $\sigma(L_1)$, on déduit de manière nécessaire la valeur de $\sigma^{-1}\rho(\sigma(L_1))$ par $\sigma$. En effet, si $(\sigma^{-1}\rho\sigma)(L_1)=L_2$ alors $\sigma(L_2)=\rho(\sigma(L_1))$. De proche un proche, chaque lettre pour laquelle on trouve l’image par $\sigma$ nous donne l’image d’une autre lettre. Soit on trouve une contradiction, auquel cas on élimine la possibilité $\sigma$, soit on trouve la totalité (ou une très grande partie) des valeurs de $\sigma$.

Les Polonais ont construit une machine électrique, qui énumérait les $26^3$ possibilités pour R et trouvait la réponse en moins d’un quart d’heure. À cause du bruit infernal qu’elle faisait on l’appelait Bomba. Le calcul des C était fait à la main car il s’avère très simple en pratique. En hommage aux mathématiciens polonais, les cryptanalystes de Bletchley Park ont appelées Bombe le premier ordinateur (Turing-complet) fonctionnel de l’histoire de l’informatique.

Discussion

La méthode polonaise se résume en une phrase : chercher des propriétés du message invariantes lors du chiffrement. C’est un principe général qu’on peut utiliser dans de nombreux défis, faisant appel à des invariants de plusieurs branches mathématiques : combinatoire, théorie des nombres, etc. Casser des codes secrets est une façon de faire des mathématiques et de l’informatique. L’auteur fait partie de l’équipe qui organise le concours de cryptanalyse Alkindi où les élèves de 4e, 3e et 2nde découvrent la cryptologie et entraînent leur logique en cassant des codes secrets.

Prenons l’exemple d’un exercice du tour 1 de la première édition :

Chaque lettre de l’alphabet a été remplacée par un nouveau signe. Étant donnée une liste de mots (à gauche) et la liste de leurs chiffrés en désordre (à droite), faites la correspondance entre chaque mot et son chiffré. La clé de la solution est de remarquer qu’un mot et son chiffré ont la même longueur, ou de manière équivalente, la longueur est un invariant lors du chiffrement ! Une autre propriété invariante est celle de contenir des lettres doubles, ce qui permet de distinguer le chiffré de « pomme » de celui de « nuage ».

Prenons un deuxième exemple inspiré du tour 3 de la deuxième édition : une phrase a été écrite dans une grille de $6 \times 6$ lettres, sans espaces. Ensuite on a appliqué une permutation $\sigma$ des $6$ lignes et une permutation $\rho$ des $6$ colonnes :

Une solution naïve consiste à tester toutes les $6!=720$ possibilités pour $\sigma$ et toutes les $6!=720$ possibilités pour $\rho$, pour un total de $518400$ possibilités.

Une meilleure solution consiste à couper le problème en deux : trouver $\rho$ grâce à un invariant puis trouver $\sigma$. En effet, si on part d’un texte en français et on permute les lignes on ne change pas le fait que la lettre D ne suit jamais la lettre Q, sauf si un mot finit par Q et le suivant commence par D, ce qui est très peu fréquent. Autrement dit, les fréquences des bigrammes (groupes de 2 lettres consécutives dans un texte) sont invariantes quand on permute les lignes. Ainsi, on essaie les 720 possibilités pour $\rho$ en éliminant une grande partie qui ont une fréquence des bigrammes différente de celle du français, par exemple on élimine les permutations des colonnes qui font apparaître le bigramme QD.

Supposons maintenant qu’on ait trouvé la permutation $\rho$ des colonnes, qui fait apparaître « nadire » sur la première ligne. Le texte devient alors :

Si on peut utiliser un ordinateur on n’a que 720 possibilités à tester. On résout l’exercice en $720+720=1440$ essais au lieu de $720\cdot720=518400$. Si on a du flair de cryptologue alors on peut prendre un raccourci. Une des lignes doit être le début d’une phrase française donc les seules possibilités sont « on parle » ou « quand o ». On voit aussi que les rangées « e toujo » et « urs mal » se suivent pour former le mot « toujours ». De proche en proche on trouve « On parle toujours mal quand on n’a rien a dire », une célèbre citation de Voltaire.

Références

Olivier Forcade, Enigma : le chiffre et les lettres (un article historique sur les codes secrets lors des deux guerres mondiales) ;

Razvan Barbulescu. Enigma (une version longue de cet article, comprenant un langage plus technique) ;

Nigel Smart. Cryptography (an introduction) (un livre spécialisé de cryptologie, qui traite la cryptanalyse d’Enigma - chapitre 4).