Enigma

Dernière mise à jour : 25 décembre 2015

Présentation générale

Enigma est la machine à crypter les messages utilisée par l'armée allemande entre 1925 et 1945. Inventée par Scherbius, elle est l'héritière du disque à crypter conçu par Alberti au 15ème siècle. Il s'agissait d'un dispositif comportant deux disques concentriques et fonctionnant sur la base d'une clef constituée d'un mot, par exemple code. Pour crypter le mot guerre, on plaçait la lettre a du disque externe sur la lettre c, première lettre du mot code du disque interne et on recherchait la lettre correspondant au g, en l'occurrence i. Pour crypter la deuxième lettre u, on plaçait la lettre a du disque externe sur o, puis sur d et e, on revenait ensuite à c etc. (Plus d'informations)

La machine inventée par Scherbius est plus complexe qui est constituée :

– d'un clavier, ne contenant que les 26 lettres de l'alphabet : les espaces et les signes de ponctuation n'étaient pas codables, les chiffres étaient codés par des lettres selon une correspondance indiquée sur le clavier (p=0, q=1, w=2, e=3 etc.) ;

– d'interconnexions entre certaines lettres, intervertissant chaque lettre connectée en son double ;

– de trois rotors, qui tournaient au fur et à mesure du cryptage, et pouvaient être placés dans n'importe quel ordre ;

– d'un réflecteur, fixe ;

– d'un deuxième clavier, lumineux, renvoyant les lettres codées.

Sur la version commerciale d'Enigma, les lettres des rotors et du réflecteur étaient classées dans l'ordre du clavier (qwertz...) ; sur la version militaire, elles étaient classées par ordre alphabétique, décision qui a permis sa reconstitution par les Polonais qui ne disposaient que des plans de cablage : un ordre aléatoire, variant selon les rotors aurait été quasiment impossible à reconstituer.

Lors de la frappe d'une lettre sur le clavier, celle-ci est le cas échéant transformée en son double connecté, le résultat transformé en une autre lettre par le premier rotor, puis par le deuxième, le troisième et le réflecteur, et le résultat repasse par le troisième rotor, le deuxième, le premier, et s'affiche sur le clavier lumineux.

Une première complexité du chiffre obtenu tient au mouvement des rotors. Le premier rotor avance d'un cran à chaque lettre, de sorte que la même lettre n'est pas cryptée deux fois de suite de la même manière. De plus, quand le premier rotor a acompli un tour complet, c'est le deuxième rotor qui avance d'un cran, de sorte que la 27ème occurence d'une même lettre n'est pas non plus cryptée de la même manière que la première. Enfin, le troisième rotor avance de même d'un cran lorsque le deuxième a fini son tour et seule la 26*26*26=17 576ème occurrence de la même lettre est donc cryptée de la même manière que la première.

La deuxième complexité tient à ce que l'ordre et la position initiale des rotors sont variables, le rotor 1 peut être placé en première, deuxième ou troisième position et de même pour les deux autres, ce qui donne 3!=6 possibilités. Chaque rotor peut ensuite être initialement positionné sur n'importe quelle lettre a, b, c, d... ce qui donne encore 26*26*26=17 576 possibilités. La même lettre peut donc être codée de 3!*26^3=105 456 manières différentes.

Troisième élément de complexité : ce nombre de possibilités est encore accru par l'existence de connexions entre les lettres. La lettre a peut être cryptée simplement ou remplacée avant cryptage par n'importe laquelle des 25 autres lettres. La version de 1925 admettait 6 paires de lettres interconnectées, ce qui donnait 100 391 791 500 possibilités (choix d'une paire parmi 26, puis d'une deuxième parmi 24... le total devant être divisé par 2^6 puisque la paire ac est identique à la paire ca, puis par 6!, puisque l'ordre dans lequel sont opérées les connexions est indifférent).

Ces trois éléments – ordre des rotors, positionnement initial et connexions – étaient définis par une clef, qui changeait tous les jours, et, pour plus de sûreté, ne servait qu'à crypter une deuxième clef, modifiant exclusivement le positionnement initial des rotors. L'expéditeur commençait donc par se référer à un cahier, sur lequel étaient portées toutes les clefs de tous les jours, il utilisait cette clef du jour pour coder les trois lettres définissant le nouveau positionnement des rotors et utilisait ensuite celui-ci pour crypter son message. De cette manière, les caractères effectivement cryptés avec la clef commune étaient très peu nombreux, ce qui interdisait l'emploi des méthodes statistiques classiques pour déchiffrer les messages. Néanmoins, une précaution supplémentaire exigeait que la nouvelle clef soit cryptée deux fois en début de message et c'est cette répétition qu'exploitèrent les Polonais pour casser le code de la première version d'Enigma.

Une dernière caractéristique du fonctionnement d'Enigma est liée à l'existence du réflecteur, qui crée une symétrie dans le cryptage : si a est codée en b, réciproquement b sera codée en a, pour le même paramétrage. Cette symétrie a été voulue par Scherbius afin de faciliter le déchiffrage : rotors et connexions étant positionnés conformément à la clef utilisée pour le cryptage, il suffit d'entrer le message crypté au clavier pour obtenir le message initial. Cette symétrie est toutefois aussi une des faiblesses d'Enigma car elle interdit qu'une lettre soit cryptée par elle-même et ce point sera exploité par les Anglais pour casser le code de la deuxième version d'Enigma.

Simulation

Ces pages proposent une simulation d'Enigma et de son décryptage. La structure générale de la machine est respectée mais, sauf sur les pages Bonus qui intègrent les deux derniers, cette simulation se distingue de l'Enigma historique sur trois points.

1. Les rotors et réflecteurs ne reproduisent pas ceux effectivement utilisés par les Allemands, dont on trouvera le détail, par exemple, sur www.codesandciphers.org.uk ; il serait donc vain de tenter de retrouver avec cette simulation le cryptage obtenu avec les véritables machines utilisées entre 1925 et 1945.

2. La bague permettant de modifier la correspondance entre la structure du rotor et les lettres de l'alphabet n'a pas été prise en compte : lorsqu'un rotor est sur la position b, une lettre L est immuablement codée avec le cablage correspondant à b. Dans la version historique, le positionnement relatif du rotor et de la bague sur laquelle étaient gravés les lettres, ou les chiffres, pouvait être modifié. Ainsi, si la lettre b apparaissait dans la fenêtre de paramétrage, le câblage utilisé pour coder L pouvait être n'importe lequel des 26, l'ordre dans lequel intervenaient ces câblages restant toujours le même.

3. Quelle que soit la position initiale des rotors, le deuxième rotor avance d'un cran après 26 décalages du premier et le troisième rotor de même après 26 décalages du deuxième. Dans la version historique, cette avancée s'opérait lorsque la bague du rotor précédent parvenait à une lettre déterminée. S'agissant des cinq rotors de la version de 1938, ces lettres étaient R, F, W, K, A, que les Anglais avaient transposées en Royal Flags Wave Kings Above.

A ces réserves près, les deux versions sont envisagées.

Version 1925

La version initiale de 1925, décryptée par les Polonais, n'admet que trois rotors et six interconnexions. C'est à elle que correspondent les indications données ci-dessus sur le nombre de possibilités de clefs. De l'ordre de 100 milliards, celui-ci outrepassait les capacités techniques de l'époque en matière de test et c'est l'étude de la structure mathématique* des transformations opérées par la machine qui a permis aux Polonais, dirigés par Rejewski, d'en casser le code.

Un rotor peut être appréhendé, ou construit, comme un dispositif transformant une lettre en une autre lettre – a en d, b en n, c en q... – chaque lettre de l'alphabet devant être à la fois codée et codante, puisque une même lettre ne peut servir à coder deux lettres différentes. Un tel dispositif peut ainsi être décrit par les suites que sa structure propre le conduit à générer : a est codé en d, qui est codé en x, codé en m... codé en a. L'alphabet entier peut être couvert par une unique suite mais il ne s'agit là que d'un cas particulier et les transformations peuvent en faire apparaître plusieurs. Ainsi, dans le schéma précédent sur six lettres, le premier rotor donne deux suites :

a -> d -> e -> a

b -> c -> f -> b

tandis que le deuxième n'en donne qu'une

a -> c -> f -> d -> e -> b -> a

Les lettres ainsi liées peuvent changer, si l'on remplace les lettres par d'autres signes ou si l'on modifie le clavier, en intervertissant certaines lettres, mais, déterminés par la constitution du rotor, la longueur et le nombre des suites ainsi générées subsistent*.

Découverte par Marian Rejewski, alors jeune mathématicien recruté par le Bureau du Chiffre polonais, cette propriété générale des dispositifs de transformations se retrouve lorsque l'on considère les transformations qu'Enigma opère successivement sur une même lettre. Sur le schéma de 6 lettres, A qui était codé en B à la première étape, l'est ensuite en C et ce changement peut être décrit en disant que l'avancée du premier rotor transforme B en C. Si l'on applique le même raisonnement à toutes les lettres, le décalage du premier rotor se trouve produire ces deux suites :

b -> c -> d (-> b)

a -> f -> e (-> a)

dont la longueur, trois lettres, et le nombre, deux, ne dépendent que de l'ordre des rotors, de leur position et du nombre de décalages. Si l'on code en effet une troisième fois A et que l'on compare sa nouvelle lettre codante à la première, on constate que A est de nouveau codé en B, ou que le B du codage initial est conservé, et les suites ainsi obtenues sont :

a (-> a)

b (-> b)

e -> f (-> e)

c -> d (-> c)

soit deux suites de deux lettres et deux "suites" d'une seule lettre. Cette caractéristique, associant un nombre déterminé de suites d'une longueur déterminée à un positionnement déterminé des rotors, donc à une clef, va permettre aux Polonais de décrypter la première version de 1925 et toutes les stratégies élaborées ensuite n'en seront que des adaptations.

Ainsi, après le changement de réflecteur en mai 1937, les Polonais ne s'attacheront plus à répertorier toutes les boucles engendrées par toutes les clefs possibles mais se borneront à repérer les clefs codant la même lettre de la même manière après en l'occurrence trois avancées du premier rotor, ce qui revient à s'intéresser aux seules suites d'une seule lettre ou boucles de longueur 1. Cette même stratégie sera encore à l'arrière plan des feuilles dites de Zygalski, élaborées à la fin de 1938 pour tenir compte d'un changement dans le protocole d'envoi des messages, et encore utilisée par les Anglais jusqu'en mai 1940.

* Plus d'informations sur la dimension mathématique de cette structure : Marian Rejewski and the First Break into Enigma

Version 1938

La version d'Enigma inaugurée en décembre 1938 diffère de la précédente sur deux points :

– le cryptage s'opère toujours avec trois rotors mais ceux-ci peuvent dorénavant être choisis parmi cinq, ce qui multiplie par dix le nombre d'ordres de rotors possibles – 5 * 4 * 3 = 60 – ; il y a donc dorénavant 1 054 560 manières de crypter un message ;

– les interconnexions portent sur dix paires de lettres et, non plus seulement six, ce qui monte le nombre de possibilités à 150 738 274 937 250, soit 150 mille milliards.

Si l'on mesure la complexité d'un code au nombre de possibilités de cryptage, la version de décembre 1938 est donc 15 000 fois plus complexe que celle de 1925.

Cette complexité interdit certaines stratégies que la précédente version permettait encore, telle que le recensement systématique de tous les liens engendrés par tous les positionnements pour tous les ordres de rotors possibles : il avait fallu un an aux Polonais pour établir ce répertoire et, même avec un personnel plus important et un équipement plus performant, les Anglais n'auraient pu l'achever dans un délai raisonnable. La base réduite, et au reste suffisante, que constituaient les feuilles de Zygalski était seule envisageable.

Elle pousse également les Anglais à exploiter tout ce qui, dans la manière dont les Allemands utilisent effectivement Enigma, peut réduire le nombre de possibilités à envisager et en particulier le fait qu'un même rotor ne peut occuper la même place deux jours de suite*. Destinée du point de vue allemand à exclure des paramétrages jugés trop simples ou trop aisément identifiables, cette règle et surtout son application stricte facilitait en réalité le travail des décrypteurs puisque, l'ordre des rotors ayant été identifiés pour un jour donné, ce n'étaient plus soixante possibilités qu'il fallait examiner le lendemain mais trente-deux. Avec ces prescriptions en effet, ne subsistent déjà plus pour le premier rotor que quatre possibilités au lieu de cinq : si l'ordre choisi au jour J est 123, le premier rotor à J+1 ne peut plus être choisi qu'entre les rotors n° 2, 3, 4 et 5. Pour le deuxième, il reste ensuite soit quatre possibilités aussi, si le rotor n° 2 occupe la première position, soit trois seulement, puisqu'il faut soustraire le rotor n° 2 en plus de celui qui occupe la première position. Pour le dernier rotor enfin, il reste deux ou trois possibilités, selon que le rotor n° 3 occupe ou non l'une des deux premières positions. Un tableau répertoriant tous les cas de figures montre que le nombre d'ordres possible égale ainsi trente-deux.

La difficulté majeure du décryptage de cette version d'Enigma tient toutefois moins à sa complexité qu'à une modification du protocole de cryptage intervenue en mai 1940. Comme celle de Rejewski, la stratégie de Zygalski, reprise par les Anglais en 1939, exploitait le cryptage répété, en début de message, de la clef particulière servant à crypter le message proprement dit. En mai 1940, ces messages sont toujours cryptés avec une clef particulière mais celle-ci n'est plus répétée et les Anglais adopteront une autre stratégie restée associée au nom d'Alan Turing et fondée sur l'exploitation des mots probables. Partant de l'hypothèse qu'un mot ou expression, par exemple bulletin météorologique ou plus exactement bulletinmeteorologique, figurait dans un message intercepté, il s'agissait d'abord de le localiser, puis de déterminer la clef susceptible de transformer la chaine cryptée ainsi localisée en bulletinmeteorologique, ou en l'occurrence plutôt d'écarter toutes celles qui ne le pouvaient pas.

Quoique fondé sur un support différent, le détail de la stratégie reposait encore sur l'exploitation des propriétés mises en évidence par Rejewski, savoir que les substitutions de lettres opérées lors du cryptage présentaient des boucles ou des répétitions spécifiques de certaines clefs. L'avantage des Anglais fut alors de disposer de moyens matériels plus conséquents que les Polonais leur permettant de mécaniser les procédures de recherche et ainsi de faire face à l'accroissement des possibilités liées à l'adjonction des deux nouveaux rotors.

* La règle stipulant que deux lettres consécutives ne pouvaient être connectées ne s'appliquait apparemment pas à la Wehrmacht. D. Rijmenants donne des exemples de clefs du jour dans lesquels on trouve les connexions AB, HI...

Ressources

Codes and Ciphers

Dirk Rijmenants

Graham Ellsbury

American Mathematical Society : Marian Rejewski and the First Break into Enigma, The Polish Attack on Enigma II : Zygalski sheets

en.Wikipedia : Enigma Machine, Cryptanalysis of the Enigma

www.000webhost.com