Cryptanalyse d'Enigma


Cryptanalyse d'Enigma
Version américaine d'une machine de cryptanalyse d'Enigma.

La cryptanalyse d'Enigma, c'est-à-dire le décryptage des messages transmis et codés par Enigma, fut fondamentale au succès des Alliés pendant la Seconde Guerre mondiale.

Le mathématicien polonais Marian Rejewski a élaboré la première cryptanalyse, ceci avant le début de la guerre. Elle profitait d'une certaine redondance au début des messages : un code choisi par l'opérateur de la machine était doublé et chiffré pour être ensuite utilisé comme en-tête. Durant la guerre, les Britanniques améliorent la cryptanalyse de la machine grâce au travail d'Alan Turing et les nombreux collaborateurs de Bletchley Park.

Sommaire

Les pionniers

Les premières versions commerciales d'Enigma remontent au début des années 1920. La machine apparaît alors comme très sûre voire 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 dans cette tâche difficile. Pendant ce temps, la marine allemande met en place des versions modifiées d'Enigma pour chiffrer ses transmissions.

La persévérance de la Pologne

Machine exposée à Varsovie, Pologne
Biuro Szyfrów, Varsovie, 1932

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 vers Varsovie. Elle devait normalement être transportée par la valise diplomatique, mais une erreur lors de l'envoi 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, cela permet de confirmer que les Allemands utilisent massivement Enigma pour chiffrer leurs messages. Lorsque toute l'armée allemande se met à l'utiliser des années plus tard, les Polonais portent leur soupçon sur des variantes d'Enigma. Débute alors une cryptanalyse intensive dans le but de trouver le câblage utilisé dans la version militaire, et ultérieurement d'extraire les clés pour des messages donnés.

Marian Rejewski, mathématicien polonais de 27 ans, découvre alors un moyen mathématique pour retrouver ces deux paramètres essentiels. Il s'agit là d'une découverte capitale tant au niveau technique que stratégique. Rejewski remarque une redondance lorsque les opérateurs militaires chiffrent leurs messages. L'opérateur choisit en effet un mot très court et le répète une fois. Cette séquence est chiffrée et placée au début du message. Ces informations proviennent aussi des services d'espionnage qui permettent d'avoir une meilleure idée des procédures en vigueur lors du chiffrement.

Par exemple, l'opérateur pouvait choisir « WIK » comme paramètre et ensuite configurer Enigma selon la clé en vigueur ce jour-là. Il tapait ensuite « WIKWIK » et obtenait un résultat chiffré et variable selon la clé, disons « AXLQPB ». Rejewski observe alors ceci en comparant les lettres deux par 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 ».

Trouver les bonnes chaînes

Les Polonais s'étaient spécialisés dans l'exploitation des failles cryptographiques introduites par les Allemands. Leurs espions ont pu leur fournir un exemplaire d'un vieux manuel d'Enigma. Celui-ci renfermait un exemple de chiffrement avec un texte en clair, la clé et le résultat une fois chiffré. Rejewski l'étudie alors attentivement.

Le nombre de chaînes possibles s'élève à 105 456. Mais, à l'époque, en l'absence d'une puissance de calcul suffisante, la recherche est quasi-impossible. Grâce à Jerzy Różycki et Henryk Zygalski, l'équipe de Rejewski découvre plusieurs techniques pour accélérer les calculs. L'une d'entre elles fait appel à des feuilles transparentes, 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 donnent le code utilisé pour l'en-tête.

On apprit par la suite que 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 le code à trois lettres.

Bombe cryptographique

Malgré cette performance, la recherche manuelle n'en demeure pas moins très pénible. Les Polonais construisent alors une bombe cryptologique, la bomba kryptologiczna, véritable ordinateur électromécanique qui date de 1938. Six exemplaires sont montés à Varsovie dans le bureau du chiffre juste avant le début de la Seconde Guerre mondiale. 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 obtenir la clé.

Les Polonais seront ainsi capables de déchiffrer une bonne partie des transmissions de l'armée allemande dès 1933, durant la Guerre civile espagnole et ceci jusqu'à l'aube de la Seconde Guerre mondiale. L'espionnage aura ici représenté un puissant allié dans le cassage des codes grâce à des agents disséminés un peu partout. Le plus célèbre, Hans Thilo-Schmidt (nom de code « Asche » qui signifie « cendre »), est au service des Français. Il a accès à des manuels et à du matériel lié à Enigma.

L'invasion allemande

En 1939, les Polonais doivent se rendre à l'évidence : les Allemands ont complexifié la structure de leur machine. Au cours des années 1930, les Allemands avaient souvent 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 rotors supplémentaires. De plus, le début de la guerre marque l'arrêt de la procédure de répétition de lettres au début des messages. Du coup, tous les efforts des Polonais sont réduits à néant puisque leur cryptanalyse repose sur cette redondance. Il est probable que le service cryptographique de l'armée allemande eut vent des progrès polonais (ou tout au moins des soupçons) dans la découverte d'une faille dans leur procédé de chiffrement.

Les Polonais partagent alors le résultat de leurs travaux avec la France et les Britanniques, devenus leurs alliés (milieu de 1939). Durant l'été 1939, ils fournissent à la France et au Royaume-Uni des copies de machines Enigma, la description précise de l'attaque, la technique de la grille et les plans de la bombe cryptographique qui serviront à la fabrication de la bombe électromécanique. En septembre 1939, l'invasion de la Pologne par les Nazis débute. Les Soviétiques s'introduisent en Pologne par l'est. Face au conflit imminent, les cryptologues polonais évacuent dans l'urgence leur bureau de Varsovie (Biuro Szyfrów) et détruisent le matériel confidentiel durant leur escapade. En passant par la Yougoslavie et l'Italie (encore neutre en 1939), ils atteignent la France. Près de Paris, au PC Bruno, les Polonais se mettent au service de la France et recommencent à travailler sur Enigma. Peu avant l'invasion de la France en mai 1940, le mathématicien britannique Alan Turing demeure quelques jours au PC Bruno où il sera briefé par ses confrères polonais.

Après l'armistice, les cryptologues se déplacent dans le sud de la France et en Algérie, avec les risques que cela pouvait représenter. Certains officiers supérieurs (le Colonel Gwido Langer et le Major Maksymilian Cięźki) furent capturés et malgré de terribles interrogatoires, le secret au sujet de la cryptanalyse d'Enigma demeura intact. Quant à Marian Rejewski et Henryk Zygalski, c'est une épopée qui les attend. Tout d'abord à travers l'Espagne où ils seront temporairement emprisonnés, le Portugal et finalement Gibraltar d'où ils pourront gagner le Royaume-Uni. Jerzy Róźycki aura beaucoup moins de chance puisqu'il meurt noyé lors d'un naufrage en 1942 au sud de la France, après un voyage en Algérie.

Bletchley Park

Bletchley Park

Rejewski et Zygalski ne sont toutefois pas incorporés directement à la section qui s'occupe d'Enigma, ils sont gradés et s'occupent d'autres méthodes de chiffrement utilisées par les Allemands. La cryptanalyse d'Enigma était devenue entre temps une affaire britannique et américaine. Les méthodes polonaises ne fonctionnaient plus sur les versions militaires d'Enigma et la variante d'Enigma pour la marine allemande avait toujours été supérieure en termes de sécurité. Les Polonais ne s'étaient pas vraiment intéressés aux transmissions de la marine, alors que celles-ci étaient capitales pour les forces alliées à cause des nombreuses pertes dans l'Atlantique. C'est Alan Turing qui va s'occuper de l'analyse de l'Enigma navale. Turing est le chef de la huitième section à Bletchley Park, un manoir proche de Londres où se sont retranchés tous les cryptologues et mathématiciens alliés. Avec Gordon Welchman, ils seront à l'origine du déchiffrement complet d'Enigma. Les membres de Bletchley Park travaillent dans le secret le plus total, toute fuite pouvant avoir des conséquences désastreuses sur la suite de la guerre.

Les attaques développées par les Britanniques ressemblent à celles des Polonais. Une nouvelle attaque s'intéresse plus particulièrement au réflecteur, un élément qui garantissait que toute lettre était nécessairement différente après chiffrement. De plus, les Britanniques font appel à des techniques basées sur l'analyse des mots probables. Les messages avaient de forte chance de contenir des termes comme « Heil Hitler », « Panzer », « Führer », « Stuka », etc. Ces estimations du contenu du message étaient appelées des cribles. Les cryptologues pouvaient a posteriori deviner le contenu des messages en fonction de l'actualité et des assauts ennemis. En faisant quelques hypothèses sur le contenu et sachant qu'une lettre est obligatoirement modifiée lors du chiffrement, il n'était pas impossible de retrouver une partie du texte chiffré en essayant tous les alignements possibles. À partir des résultats positifs, on arrivait à retrouver le texte complet. Cette attaque ressemblait à celle des Polonais qui tentaient de deviner l'en-tête des messages. Turing avait découvert des « clicks », c'est-à-dire des paires de lettres qui apparaissaient plusieurs fois entre le message chiffré et sa version déchiffrée (n'oublions pas qu'il avait des machines Enigma à sa disposition pour tester). Comme Enigma est réversible, une correspondance A→J est équivalente à J→A.

Pour illustrer ce principe d'une manière simplifiée, prenons la phrase suivante que l'on suppose présente dans le message original : « 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 en clair et chiffré. La deuxième lettre du message en clair « T » donne un « A » chiffré. La 4e lettre du message en clair est un « A » qui se transforme en « P ». Finalement, la 21e 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.

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 testait en fait les configurations qui permettaient d'obtenir des boucles. Pour toutes les possibilités, on cherchait si le crible était compatible avec la boucle observée. Si ce n'était pas le cas, on continuait avec la configuration suivante. Le nombre de possibilités se montait à 26*26*26*60 = 1 054 560, impossible à la main mais pas impossible pour la bombe de Turing. Pour calculer ces combinaisons, on ne pouvait se contenter d'une machine. Les Britanniques vont introduire une parallélisation astucieuse de la machine Enigma.

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

Interceptions des messages

Les opérateurs allemands aidèrent involontairement les cryptanalystes à maintes occasions. On pouvait demander à un opérateur d'effectuer un test en envoyant un message comprenant uniquement des T. En découvrant un message dépourvu de la lettre T, on pouvait déduire qu'il s'agissait d'un message composé uniquement de cette lettre. Certains des opérateurs d'Enigma utilisaient toujours les mêmes paramètres au début de leurs messages, par exemple les initiales d'un proche. Les Britanniques utiliseront le terme de « cillies » pour qualifier ces messages (à cause d'un opérateur qui utilisait systématiquement les initiales C.I.L.), ce néologisme est à comparer avec « silly » qui signifie « stupide » en anglais.

Un énorme travail devait être effectué en amont pour trier les messages interceptés et retenir ceux qui étaient intéressants. Avec suffisamment de messages, il était possible de déterminer les paramètres journaliers. D'autres opérateurs ajoutaient un en-tête selon le type de message, par exemple WET (de Wetter signifiant météo en allemand) s'il s'agissait d'un rapport météo.

Plus tard durant la guerre, ces bulletins d'information météorologiques furent des pièces maîtresses de la cryptanalyse : les météorologues en mer rédigeaient les messages et les envoyaient en Allemagne à l'aide d'un système de chiffrement moins « robuste » qu'Enigma (la météo n'étant pas une information véritablement secrète). Une fois arrivés dans les quartiers généraux, ces messages étaient expédiés quasiment sans modifications aux U-Boot, qui, cette fois-ci, les chiffraient avec Enigma. Les Alliés disposaient de textes clairs qu'ils pouvaient ainsi mettre en rapport avec les textes chiffrés d'Enigma dans le but d'établir des cribles.

Si les Allemands avaient eu la possibilité de changer plus souvent les rotors d'Enigma, il est possible que les efforts des experts de Bletchley Park soient restés vains. L'envoi de nouveaux rotors demandait une infrastructure qu'il n'était pas possible de déployer durant la guerre. Il fallait entre autres s'assurer que tous les navires et unités soient en possession des bons rotors. Les Allemands optèrent pour l'ajout de rotors sans modifier les autres, en particulier pour la Kriegsmarine. Ce changement eut pour effet de rendre les communications navales assez sûres de février à octobre 1942, et ce d'autant que les opérateurs des U-boot évitaient les messages-types et autres « cillies ».

Face au danger que cela représentait, et notamment une éventuelle défaite dans la Bataille de l'Atlantique, les Alliés se devaient de réagir. Ils mirent sur pied plusieurs opérations périlleuses pour voler les carnets de code allemands. Certaines virent le jour, et furent efficaces, d'autres restèrent au stade de projet, comme l'Opération Sans-Pitié imaginée par Ian Fleming, le futur « père » de James Bond et officier dans le renseignement naval britannique. Ainsi, les cryptanalystes eurent quelques difficultés lors de ces remplacements mais parvinrent rapidement à obtenir les nouveaux paramètres des machines.

Attaque par l'indice de coïncidence

Une autre méthode, plus adaptée aux moyens modernes, consiste à essayer toutes les possibilités et à calculer l'indice de coïncidence du texte déchiffré. Un message proche au contenu aléatoire aura un indice proche de 0.0385 alors qu'il se montera aux environs de 0.075 pour du français. L'indice varie selon la langue mais il est invariant aux substitutions monoalphabétiques. Dans le cas d'Enigma, on peut essayer toutes les combinaisons des rotors et regarder l'indice obtenu. Soit un message intercepté crypté par une Enigma comme celle utilisée par la Wehrmacht (3 rotors) :

RFCNT RAONM CVIJZ CBRWS XOTJG SMOMX DUWFW LBYBK BPOFY AOEQW PHNLJ MXMYM JDVPI TOHOC MUIYW WYQRZ LTBEI HUDJE Y

Maintenant, essayons toutes les configurations des rotors et calculons l'indice de coïncidence après déchiffrement, voici un extrait des résultats :

Rotors Message IC
ONS GKNQC CJIBD GYEFO ZQCBH OWJVU AYYLR IXJTC URIEA LVCLS KIVVR GQFEQ DBTMU GIAAY FXVRH RRBPO TQEFF XNQBV ZFMGZ J 0.03909
ONT DWRIE GMZSA RQVWC NEGNJ GLFAQ PDANF RAZVG DOKHW NUEPO USNUZ KOXCV VLYPX SHOWP BJYKV QDCLT CVKLO JGEKS EKYPM O 0.03492
ONU ATTAQ UECES OIRSU RWIKI PEDIA ILFAU TECRI REPLU SDART ICLES ETSUR TOUTT ERMIN ERCET ARTIC LEDEC RYPTA NALYS E 0.07473
ONV CLRHE MPTBX LPUVM FOGOE DBNKW FNNWN PGGPN QHXNE AFYWF LFQHM IPGSU YSXNF MUEMM AKWVL AAYQL ZNVWN NNKHF WGRMY K 0.04591

Au vu des résultats et en présence d'un indice proche de 0.074, on peut en conclure que la configuration « ONU » est probablement la bonne alors que les autres ont un indice largement inférieur et proche d'une distribution uniforme. Pour plus d'assurance, on pourrait procéder à une analyse de la fréquence des lettres dans le message. On se rendrait compte que le message « ONU » contient un grand nombre de 'E' et de 'A' et qu'il est probablement en français.

Le message est de ce fait : ATTAQ UECES OIRSU RWIKI PEDIA ILFAU TECRI REPLU SDART ICLES ETSUR TOUTT ERMIN ERCET ARTIC LEDEC RYPTA NALYS E que l'on transforme en "attaque ce soir sur wikipedia il faut ecrire plus d articles et surtout terminer cet article de cryptanalyse"



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Cryptanalyse d'Enigma de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Cryptanalyse d’Enigma — Cryptanalyse d Enigma La cryptanalyse d Enigma, c est à dire le décryptage des messages transmis et codés par Enigma, fut fondamentale au succès des Alliés pendant la Seconde Guerre mondiale. Le mathématicien polonais Marian Rejewski a élaboré la …   Wikipédia en Français

  • Enigma (Machine) — Pour les articles homonymes, voir Enigma …   Wikipédia en Français

  • Cryptanalyse Différentielle Impossible — En cryptanalyse, la cryptanalyse différentielle impossible ou cryptanalyse par différentielles impossibles est une technique basée sur la cryptanalyse différentielle (1990), elle a été proposée en 1999 par Eli Biham, Adi Shamir et Alex Biryukov… …   Wikipédia en Français

  • Cryptanalyse differentielle impossible — Cryptanalyse différentielle impossible En cryptanalyse, la cryptanalyse différentielle impossible ou cryptanalyse par différentielles impossibles est une technique basée sur la cryptanalyse différentielle (1990), elle a été proposée en 1999 par… …   Wikipédia en Français

  • Cryptanalyse par différentielles impossibles — Cryptanalyse différentielle impossible En cryptanalyse, la cryptanalyse différentielle impossible ou cryptanalyse par différentielles impossibles est une technique basée sur la cryptanalyse différentielle (1990), elle a été proposée en 1999 par… …   Wikipédia en Français

  • Enigma (machine) — Pour les articles homonymes, voir Enigma …   Wikipédia en Français

  • Cryptanalyse différentielle impossible — En cryptanalyse, la cryptanalyse différentielle impossible ou cryptanalyse par différentielles impossibles est une technique basée sur la cryptanalyse différentielle (1990), elle a été proposée en 1999 par Eli Biham, Adi Shamir et Alex Biryukov… …   Wikipédia en Français

  • Cryptanalyse Différentielle — La cryptanalyse différentielle est une méthode générique de cryptanalyse qui peut être appliquée aux algorithmes de chiffrement itératif par blocs, mais également aux algorithmes de chiffrement par flots et aux fonction de hachage. Dans son sens… …   Wikipédia en Français

  • Cryptanalyse differentielle — Cryptanalyse différentielle La cryptanalyse différentielle est une méthode générique de cryptanalyse qui peut être appliquée aux algorithmes de chiffrement itératif par blocs, mais également aux algorithmes de chiffrement par flots et aux… …   Wikipédia en Français

  • Cryptanalyse Linéaire — La cryptanalyse linéaire est une technique inventée par Mitsuru Matsui, chercheur chez Mitsubishi. Elle date de 1993 et fut développée à l origine pour casser l algorithme de chiffrement symétrique DES. Ce type de cryptanalyse se base sur un… …   Wikipédia en Français