La machine Enigma

Piste bleue Le 10 mars 2018  - Ecrit par  Razvan Barbulescu Voir les commentaires (1)

La machine Enigma a été utilisée pour chiffrer les messages allemands pendant la guerre. Casser les codes revient à trouver un réglage secret formé d’un triplet de lettres, noté R, et de 10 paires de lettres, noté C. Le réglage changeait toutes les 24 heures, ce qui laissait tout autant de temps aux mathématiciens polonais pour trouver le réglage. Une énumération complète est impossible même avec un ordinateur moderne. Mais de manière miraculeuse, les mathématiciens polonais ont trouvé une méthode pour n’énumérer que les valeurs possibles pour R, ce qui réduisait le temps de calcul à environ 15 minutes. Nous expliquons leur méthode, en utilisant la théorie des permutations et en particulier une notion appelée « motif de décomposition ».

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.

JPEG

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.

PNG - 69.3 ko

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.

JPEG - 34 ko

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.

PNG

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.

Pour lire le cahier on prend le dictionnaire franco-allemand.

Chaque ligne correspond à un jour (Tag). Le choix des rotors (Walzen) est donné dans la deuxième colonne, ces derniers étant numérotés par i, ii, iii, iv et v. Il s’ensuit la position des anneaux (Ringstellung), qui déterminent le moment où les rotors tournent de deux crans au lieu d’un, comme ils font habituellement. Cela ne compte pas pour la méthode polonaise, on ne regardera pas la façon dont les rotors bougent. Le choix des 10 paires de lettres, noté C, est donné dans la colonne nommée « connexions des prises » (Stecker Verbindungen). La dernière colonne donne la valeur de R, la position des trois rotors. Ici on a quatre groupes de trois lettres car on est en 1941 quand les Allemands ont modifié la procédure d’envoi des messages, mais jusqu’en 1940 il n’y avait qu’un seul triplet. On parle de groupe de marquages (Kenn Grupen) et non pas de rotors car l’utilisateur devait faire tourner les roulettes qu’il voyait en haut de la machine (qui en réalité étaient les extrémités des rotors) pour faire apparaître les bons marquages.

Quelques notions mathématiques

Avant de présenter la solution,

rappelons quelques éléments de la théorie des permutations.

Une permutation de l’ensemble $E$ est une manière de mélanger ses éléments. En langage mathématique une permutation d’un ensemble fini $E$ est une fonction de $E$ vers $E$ telle que les images de tous les éléments soient différentes. Comme les fonctions se représentent par des flèches, les permutations aussi. Voici un exemple où E=$\{A,B,C,D,E\}$ :

Pour tout $x\in E$, $\sigma(x)$ désigne l’image de $x$ par $\sigma$. En cryptographie, le chiffre de substitution consiste à remplacer chaque lettre du message par sa valeur par $\sigma$. Par exemple le message ABBA a comme chiffré $\sigma(A)\sigma(B)\sigma(B)\sigma(A)=BCCB$.

Quand $\rho$ est une deuxième permutation de $E$, on calcule $\rho(\sigma(x))$ en cherchant d’abord l’image de $x$ par $\sigma$ puis en cherchant l’image de $\sigma(x)$ par $\rho$. L’élément $\rho(\sigma(x))$ est aussi noté $(\rho\circ \sigma)(x)$. La permutation qui à tout $x$ associe $(\rho\circ\sigma)(x)$ est appelée permutation composée de $\rho$ et $\sigma$. Parfois on oublie le petit cercle et on note simplement $\rho\sigma$. Dans l’exemple ci-dessous la permutation $\rho\circ\sigma$ est représentée en pointillé :

En cryptographie, si on chiffre un message deux fois, d’abord par $\sigma$ puis par $\rho$, on obtient le même résultat que de chiffrer directement par $\rho\circ\sigma$.

La permutation qui défait l’action de $\sigma$ est appelée inverse de $\sigma$ et notée $\sigma^{-1}$. En langage mathématique $\sigma^{-1}$ est la fonction réciproque (ou inverse) de $\sigma$. On peut calculer $\sigma^{-1}$ en représentant $\sigma$ par des flèches et en faisant une symétrie verticale et en inversant le sens des flèches. Dans la figure ci-dessous la permutation inverse est représentée par des flèches rouges. Par exemple, pour calculer $\sigma^{-1}(B)$,on suit la flèche rouge qui part de $B$ (en bas) et on trouve $A$ :

En cryptographie, un message chiffré par substitution selon la permutation $\sigma$ est déchiffré à l’aide d’une substitution par $\sigma^{-1}$.

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$.

Les mathématiciens polonais utilisaient un vice dans la procédure allemande, qui leur permettait de ne pas avoir à connaître le début des messages.

En effet, nous avons décrit la manière dont les utilisateurs civils se servaient d’Enigma avant la guerre. L’armée allemande a introduit un protocole d’utilisation qui, à la première vue, ajoute une sécurité supplémentaire. La personne qui chiffrait commençait par choisir un triplet de lettres, disons AZE. Puis elle réglait Enigma dans la configuration initiale du jour (R,C) et chiffrait le message AZEAZE. La répétition permettait de détecter les erreurs de transmission. Ensuite la même personne mettait les rotors de la machine dans la position AZE et chiffrait le message proprement-dit. Si les mathématiciens polonais savaient que XRGOSZ représentait le chiffré d’un triplet de lettres écrites deux fois, $L_1L_2L_3L_1L_2L_3$, alors ils savaient que $(\sigma^{-1}\rho\sigma)(L_1)=X$ et $(\sigma^{-1}\rho^{'''}\sigma)(L_1)=O$. Un exercice simple montre que l’inverse de la permutation $(\sigma^{-1}\rho\sigma)$ est $(\sigma^{-1}\rho^{-1}\sigma)$ donc $(\sigma^{-1}\rho^{-1}\sigma)(X)=L_1$.
On a alors
\[O=(\sigma^{-1}\rho^{'''}\sigma)(L_1)= (\sigma^{-1}\rho^{'''}\sigma)((\sigma^{-1}\rho^{-1}\sigma)(X))= (\sigma^{-1}\rho^{'''}\rho^{-1}\sigma)(X).\]
En utilisant une quinzaine de messages interceptés, tels que chaque lettre de l’alphabet apparaisse dans les trois premières positions d’au moins un message, les Polonais connaissaient complètement la permutation $(\sigma^{-1}\rho^{'''}\rho^{-1}\sigma)$. Dans cet article on n’utilise pas le fait que $\sigma^{-1}=\sigma$, même si cela est vrai grâce à la manière dont $\sigma$ est réalisée, en échangeant des lettres deux à deux.

PNG - 125.1 ko

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 !
JPEG

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.

Pour prouver que ce nombre est petit on a besoin d’une formule d’Euler.

En effet, appelons partition d’un entier toute manière de l’écrire comme somme d’entiers non-nuls triés par ordre croissant, par exemple $1+1+1+1$, $1+1+2$, $2+2$, $1+3$ et $4$ sont les $5$ partitions de $n=4$. Clairement, tout motif de décomposition d’une permutation d’un ensemble fini $E$ est une partition du nombre d’éléments de $E$. Le nombre de motifs de décompositions possibles pour Enigma est majoré par le nombre de partitions de 26. Si on note $p(n)$ le nombre de partitions de n, alors Euler a montré que
\[p(n)=\sum_{k=1}^{\lfloor\sqrt{n} \rfloor} (-1)^{k-1}\left(p(n-k(3k-1)/2)+p(n-k(3k+1)/2)\right).\]
Un programme simple permet de calculer p(26)=2436. Ainsi le nombre moyen de triplets $R$ qui ont le même motif de décomposition (celui demandé) est d’environ $17576/2436\approx 7.19$.

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 :

aednir
tooeuj
nlpoar
rlsuma
uoaqnd
neanri

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 :

nadire
etoujo
onparl
ursmal
quando
nnarie

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).

Post-scriptum :

L’auteur tient à remercier Pierre-Antoine Guihéneuf pour son aide précieuse, qui a permis de faire évoluer l’article. La rédaction d’Images des Maths se joint à lui pour remercier les relecteurs Romain Dujardin, Jérôme et Marielle Simon pour
leur relecture attentive et leurs commentaires constructifs.

Article édité par Pierre-Antoine Guihéneuf

Partager cet article

Pour citer cet article :

Razvan Barbulescu — «La machine Enigma» — Images des Mathématiques, CNRS, 2018

Commentaire sur l'article

  • Filmographie

    le 16 mars à 11:44, par Marc Monticelli

    Je vous conseil de regarder le très bon docudrama « Codebreaker » sortie en 2012 pour le centenaire de la naissance de Turing plutôt que le film hollywoodien « Imitation Game ».
    Il est beaucoup plus complet sur la vie scientifique et personnel de Turing ; il y a moins d’erreurs historiques ; les acteurs ne sont pas moins excellents ; il y a un tas d’interview et d’image d’archive ; il est plus poignant ; et enfin il extrêmement bien réalisé.
    http://www.turingfilm.com

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM