thumb|Version américaine de la Bombe de Turing, une machine de cryptanalyse. La cryptanalyse d'Enigma, c'est-à-dire le décryptage de messages chiffrés par la machine à coder allemande Enigma, fut un facteur des succès alliés pendant la Seconde Guerre mondiale.
Avant le début de la guerre, le mathématicien polonais Marian Rejewski élabore la première cryptanalyse, fondée sur une redondance : le mode de chiffrement de la clef choisie par le chiffreur était répété dans le préambule du message. Durant la guerre, les Britanniques améliorent la cryptanalyse de la machine grâce aux efforts d'Alan Turing et des très nombreux cryptographes de Bletchley Park.
Il a été estimé que le conflit en Europe a été écourté d'au minimum deux ans grâce à la cryptanalyse des chiffres et des codes allemands..
Les pionniers
Les premières versions commerciales d'Enigma remontent au début des années 1920. Le chiffrement 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.
Persévérance de la Pologne
Les Polonais commencent à travailler sur Enigma dès 1928, avec l'appui de leur service de renseignement. 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 , 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 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 . 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.
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 . 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 , 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, avait prêté des documents liés à Enigma.
Invasion de la Pologne 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 , 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. 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 , 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.
Le , 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 , invasion de la zone libre. En , Rejewski et Zygalski passent en Espagne où ils sont emprisonnés, au Portugal et à Gibraltar d'où ils gagnent le Royaume-Uni. En , cinq, dont les deux chefs, Langer et Ciezki, sont capturés dans les Pyrénées. Deux meurent au camp de Sachsenhausen. En , Langer et Ciezki interrogés admettent avoir réussi à décrypter certains messages, avant la guerre, mais ils taisent leurs activités après .
Seuls les Français ont réussi à décrypter d'Enigma entre fin et mai-Anthony Cave Brown, La guerre secrète, tome 1, . . Par la suite, plus de seront décryptés durant la guerre.
Bletchley Park
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.
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 :
A T T A Q U E C E S O I R S U R W I K I P E D I A Y A O P W M K L R B F Z L V C X K T R O T Q A L D
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 du message en clair est un « A » qui se transforme en « P ». Finalement, la 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.
A T T A Q U E C E S O I R S U R W I K I P E D I A Y A O P W M K L R B F Z L V C X K T R O T Q A L D
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 = . 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 et s une fois chiffrés ne peuvent pas être ceux qu'il avait frappés, idem pour les et et les et , ce qui réduit les combinaisons possibles à 24x24x24x60 = .
Interceptions de messages Messages de test