Cryptanalyse d'Enigma

Les premières versions commerciales d'Enigma remontent au début des années 1920. Le cryptage de la machine apparaît alors comme très sûr, impossible à casser. Dès 1926, plusieurs pays tentent de percer les mystères d'Enigma. Mais les mathématiciens américains, britanniques et français échouent. Pendant ce temps, la marine allemande met en place des versions modifiées d'Enigma pour chiffrer ses transmissions.

Machine exposée à Varsovie, Pologne

Biuro Szyfrów, Varsovie, 1934

Les Polonais commencent à travailler sur Enigma dès 1928, avec l'appui de leur service de renseignements. En 1929, ils interceptent une machine Enigma, envoyée de Berlin à Varsovie, qui aurait dû passer par la valise diplomatique. Cette erreur permet aux services polonais d'en examiner le contenu. Même s'il ne s'agit que d'une version commerciale a priori assez anodine, la machine confirme que les Allemands utilisent Enigma pour chiffrer leurs messages essentiels. Lorsqu'Enigma est adoptée par l'armée allemande, des années plus tard, les Polonais concentrent leurs recherches sur les évolutions de la machine. Débute alors une cryptanalyse intensive qui vise à définir les circuits de la version militaire, afin de trouver une méthode de déduction des clefs pour des messages donnés.

Marian Rejewski, mathématicien polonais de 27 ans, découvre alors un moyen mathématique de retrouver ces deux paramètres essentiels. Rejewski remarque une répétition de la clef. Le chiffreur choisit une combinaison de trois lettres qu'il chiffre deux fois. Cette clef chiffrée est l'un des articles du préambule du message.

Une fois Enigma disposée sur les réglages du jour, le chiffreur choisit arbitrairement une clef de trois caractères (ex. « WIK »). Il tape deux fois cette clef sur la machine qui la chiffrera sur son tableau lumineux (ex. « AXLQPB »). Cette clé chiffrée sera ensuite jointe en en-tête de tous les messages du jour. Elle représente la position dans laquelle les rotors du chiffreur commencent au début du message.

Rejewski compare les lettres deux à deux : la lettre « W » correspond à « A », mais également à « Q », la lettre « I » se transforme en « X » et en « P » et finalement la lettre « K » se chiffre en « L » et « B ».

Dans le cas de la lettre « W », trois rotations du disque produisent la lettre « Q », on fait la même observation pour les autres lettres. Cela veut dire qu'il y a un lien étroit entre ces correspondances, la rotation des rotors et le câblage interne de la machine. Même si les trois lettres originales sont inconnues, on sait que le nombre de câblages qui peuvent transformer ces trois lettres en une séquence particulière sont limités. Rejewski les nomme des « chaînes ».

Les Polonais exploitent les failles cryptographiques des Allemands. Leurs agents ont fourni un exemplaire d'un vieux manuel d'Enigma qui cite un exemple de chiffrement avec le texte en clair, la clé et le résultat une fois chiffré. Rejewski l'étudie attentivement.

Le nombre de chaînes possibles est 105 456. Mais, à l'époque, en l'absence d'une puissance de calcul suffisante, la recherche d'une solution est quasi impossible. Grâce à Jerzy Różycki et Henryk Zygalski, l'équipe de Rejewski découvre plusieurs techniques d'accélération des calculs. L'une d'elles fait appel à des feuilles transparentes (feuilles de Zygalski), avec les schémas des rotors. Les feuilles sont superposées et les lettres composant une chaîne dite « impossible » sont rayées. À la fin de l'opération, les trois lettres restantes sont la clef du message.

Les Britanniques avaient développé le même genre de technique basée sur une grille, technique qui avait fait ses preuves sur l'Enigma commerciale, mais n'était pas adaptée pour « casser » la version militaire. Une variante de cette méthode consiste à utiliser des cartes perforées. À la fin, un alignement complet des trous indique la clef de trois lettres.

Bombe cryptographique

Malgré cette performance, la recherche manuelle reste beaucoup trop longue. Les Polonais construisent en 1938 une bombe cryptologique, la bomba kryptologiczna, calculateur électromécanique qui teste des milliers de combinaisons des trois rotors dont elle sélectionne les quelques solutions acceptables. Six exemplaires sont montés à Varsovie dans le bureau du chiffre, juste avant septembre 1939. Chacune contient l'équivalent de six machines Enigma commandées électriquement. Le volume occupé est par contre considérable, l'équivalent d'un atelier de 100 personnes, mais le gain de temps est significatif : il suffit de deux heures pour trouver la clef.

Les Polonais seront ainsi capables de déchiffrer, par intermittences, une certaine partie des transmissions de l'armée allemande, durant la Guerre civile espagnole, jusqu'à l'aube de la Seconde Guerre mondiale. Le renseignement avait joué un rôle. Dès 1931, un agent du SR-Guerre français, Hans-Thilo Schmidt, prête des documents liés à Enigma.

En 1939, les Polonais doivent se rendre à l'évidence : les Allemands ont compliqué leur système de codage. Au cours des années 1930, les Allemands avaient modifié quelques paramètres, mais rien qui n'avait pu empêcher les Polonais de trouver une parade. Cette fois-ci, avec la guerre qui s'annonce, la situation est plus grave. Jusqu'alors, seuls trois rotors étaient employés, mais l'armée allemande introduisit deux autres rotors. Le 1^er mai 1940, la répétition de la clef citée dans le préambule du message est supprimée. Du coup, les efforts des Polonais sont réduits à néant, puisque leur cryptanalyse repose sur cette redondance. L'armée allemande avait identifié cette répétition comme une faille. Cette suppression avait été prévue par Turing qui avait entrepris de chercher un autre mode d'entrée.

À l'été 1939, les Polonais partagent leurs secrets avec les Français et les Britanniques[2]. Ils fournissent deux copies d'Enigma, la description précise de leurs documents, méthode du gril, méthode de l'horloge, feuilles de Zygalski, et les plans de la bombe cryptographique qui inspireront la bombe électromécanique de Turing. Le 1^er septembre 1939, la Pologne est envahie. Sur ordre, les cryptologues polonais fuient Varsovie. Près de Paris, au PC Bruno, ils travaillent pour le SR-Guerre, en liaison avec le GC&CS. À deux reprises, Alan Turing demeure quelques jours au PC Bruno où il est mis au courant par ses confrères polonais[note 1].

Le 24 juin 1940, les cryptologues polonais sont exfiltrés en Algérie. Ils reviennent en zone libre, au centre Cadix. Trois périssent noyés en Méditerranée, après un séjour en Algérie. En novembre 1942, invasion de la zone libre. En février 1943, Rejewski et Zygalski passent en Espagne où ils sont emprisonnés, au Portugal et à Gibraltar d'où ils gagnent le Royaume-Uni. En mars 1943, cinq, dont les deux chefs, Langer et Ciezki, sont capturés dans les Pyrénées. Deux meurent au camp de Sachsenhausen. En mars 1944, Langer et Ciezki interrogés admettent avoir réussi à décrypter certains messages, avant la guerre, mais ils taisent leurs activités après septembre 1939.

Seuls les Français ont réussi à décrypter 141 messages d'Enigma entre fin octobre 1939 et mai-juin 1940[4]. Par la suite, plus de 15 000 messages seront décryptés durant la guerre[4].

Bletchley Park Mansion

Mis à l'écart d'Enigma, Rejewski et Zygalski sont affectés aux chiffres manuels allemands. La cryptanalyse d'Enigma est devenue une affaire britannique. Les méthodes polonaises ne lisent plus les trafics Enigma de la Heer et de la Luftwaffe.

La capture des différents modèles ENIGMA (Wehrmacht et navale) dès 1940 permit de mettre au point la machine utilisée pour son déchiffrement[note 2].

Les attaques des Britanniques ressemblent à celles des Polonais. Une nouvelle attaque s'intéresse au réflecteur, qui garantit que toute lettre est différente après chiffrement. De plus, les Britanniques font appel à l'analyse des mots probables. Les messages ont de fortes chances de contenir des termes comme « Keine besonderen Ereignisse (rien à signaler) », « Eins (chiffre 1) », « Répétez », « munition », « Wet (météo) », etc. Ces mots probables sont baptisés « cribs (antisèches) ». Les cryptologues essaient de deviner le contenu des messages, en fonction de renseignements obtenus par ailleurs. En faisant quelques hypothèses sur le contenu et sachant qu'une lettre n'est jamais chiffrée par elle-même, il n'est pas impossible de retrouver une partie du texte clair, en essayant tous les alignements possibles. À partir des résultats positifs, on arrive parfois à deviner un texte presque complet. Cette attaque ressemble à celle des Polonais qui avaient tenté de deviner le préambule des messages. Turing découvre des « clicks », paires de lettres qui apparaissent plusieurs fois entre le message chiffré et sa version déchiffrée (il avait des copies d'Enigma à sa disposition). Comme Enigma est réversible, une correspondance A→J est équivalente à J→A.

Pour illustrer ce principe d'une manière très simplifiée, prenons la phrase suivante en clair : « ATTAQUECESOIRSURWIKIPEDIA ». On intercepte le message chiffré : « YAOPWMKLRBFZLVCXKTROTQALD ». Effectuons une première comparaison :

L'attaque de Turing se base sur la recherche de boucles entre le texte clair et le texte chiffré. La deuxième lettre du message en clair « T » donne un « A » chiffré. La 4^e lettre du message en clair est un « A » qui se transforme en « P ». Finalement, la 21^e lettre du crible est un « P », il se transforme en « T » et nous voilà donc avec une boucle car elle commence et se termine avec la même lettre.

La bombe teste les configurations qui permettent d'obtenir des boucles. Pour chaque possibilité, on cherche si le crible est compatible avec la boucle observée. Si ce n'est pas le cas, on passe à la configuration suivante. Le nombre des possibilités est 26*26*26*60 = 1 054 560. Impossible de calculer à la main mais pas impossible au moyen de la bombe de Turing. Pour calculer ces combinaisons, on ne peut se contenter d'une seule Enigma. Chaque bombe simule plusieurs Enigma montées en parallèle.

Cette première attaque part du principe que la lettre « T » n'est pas modifiée par le Steckerboard, tableau de permutations qui se limitait à 6 substitutions au début de l'utilisation d'Enigma. Les versions ultérieures de la bombe font appel à divers palliatifs de ce problème grâce à des optimisations mécaniques et algorithmiques astucieuses.

Le chiffreur prend trois rotors et les dispose sur leur position initiale, conformément aux instructions du jour, par exemple I/IV/II « CHD ». Ensuite, il frappe deux fois la clef du message, une suite de trois lettres choisies par lui, ex. « MARMAR ». Ainsi, les 1^er et 4^e caractères une fois chiffrés ne peuvent pas être ceux qu'il avait frappés, idem pour les 2^e et 5^e et les 3^e et 6^e, ce qui réduit les combinaisons possibles à 24x24x24x60 = 829 440.

Une fois découverte la clef quotidienne d'un réseau, c'est-à-dire, dès qu'une vingtaine de mots allemands lisibles ont été alignés au moyen d'une clef, les cryptanalystes passent la main aux décrypteurs qui, en principe, sont alors en mesure de déchiffrer tout le trafic que ce réseau a émis à l'aide de cette clef, ce jour-là. Truffés de jargon militaire allemand, de termes et abréviations techniques inconnus, les messages déchiffrés sont livrés aux traducteurs et aux conseillers…

Les quelques techniques sommairement évoquées ici ne rendent pas compte de l'extraordinaire complexité du problème. Le GC&CS a toujours eu les plus grandes difficultés à accomplir sa mission. Les périodes de trous noirs ont été nombreuses. Les messages ne sont souvent décryptés que trop longtemps après leur réception. En particulier, l'Enigma navale a donné beaucoup de fil à retordre.

Lorsque la capacité combinée des centaines de bombes électromécaniques anglo-saxonnes permet enfin de lire Enigma presque sans trous ni délais, la Wehrmacht est déjà brisée par l'Armée rouge et surclassée par la puissance industrielle et militaire des Alliés.