Enigma : sur les traces de Turing

Guillaume Poupard

Guillaume.Poupard@ens.fr
http://www.di.ens.fr/~poupard/X/projet

1   Préambule

Le chiffrement des communications militaires a de tout temps été une préoccupation majeure des diverses forces armées. Dés l'antiquité, Jules César utilisait un système, très simple mais suffisant pour l'époque, afin de rendre inintelligibles par ses ennemis les messages qu'il envoyait à ses généraux. Les techniques de chiffrement se sont progressivement perfectionnées aux cours des siècles, au fur et à mesure que celles de cryptanalyse, i.e. de cassage des codes secrets, se sont développées. Ainsi, jusqu'à la fin de la première guerre mondiale, la protection des communications et l'espionnage de ses dernières n'a fait que se développer sans que ni les cryptographes, ni les cryptanalystes ne prennent vraiment le dessus. Ainsi, la quasi-totalité des nouveau codes étaient rapidement cassés. De plus, toutes les opérations étaient réalisées à la main, soit directement par écrit, soit à l'aide d'ingénieux mécanismes, mais sans que les opérations de chiffrement et de déchiffrement soient réellement efficaces. De même la cryptanalyse d'un code sans moyen de calcul autre que le cerveau humain était une tâche longue et pénible. Après la première guerre mondiale, l'apparition des première machine électro-techniques a tout naturellement ouvert de nouveaux horizons aux concepteurs de systèmes de codage. Arthur Scherbius a ainsi présenté en 1918 une machine de chiffrement, appelée Enigma, qui devait laisser son nom dans l'histoire moderne car après avoir semblé jouer un rôle déterminant dans la victoire nazie, elle contribua à la chute d'Hitler.

2   Description d'Enigma

La machine Enigma ressemble à une machine à écrire; elle dispose d'un clavier avec les 26 lettres de l'alphabet ainsi que d'un écran de 26 lampes, une pour chaque lettre. Une fois correctement initialisée, nous y reviendrons, son emploi est simple car pour chiffrer un texte, il suffit de le taper lettre par lettre sur le clavier et le texte chiffré correspondant est obtenu en notant les lettres associées aux lampes qui s'allument successivement. A l'intérieur de la machine, on distingue plusieurs éléments : le tableau de connexions, les brouilleurs et le réflecteur. Nous allons les décrire successivement.

2.1   Le tableau de connections

Ce tableau permet d'échanger des paires de lettres de l'alphabet, deux à deux, au moyen de fiches. Il y a 6 fiches qui permettent donc d'échanger 12 lettres. Un tableau de connections est donc une permutation très particulière composée d'au plus 6 échanges. En voici un exemple où on a échanger les paires (B,J), (E,G), (P,Z), (A,T), (M,N) et (D,X) :
A B C D E F G H I J K L M
T J C X G F E H I B K L N
N O P Q R S T U V W X Y Z
M O Z Q R S A U V W D Y P

2.2   Les brouilleurs

Un brouilleur est également une permutation, mais cette fois-ci quelconque, d'un ensemble à 26 éléments. Ainsi, si à chaque entrée de la permutation est associée une lettre, un brouilleur permet de lui associer une autre lettre. On peut de plus composer les brouilleurs (Enigma en compte 3), tout comme l'on compose les permutations. La figure 1 propose un exemple pour 6 lettres (au lieu de 26) et 3 brouilleurs.



Figure 1 : permutation au moyen de 3 brouilleurs en série


De plus, les brouilleurs se présentent sous la forme de rotors cylindriques; ils peuvent par conséquent tourner autour de leur axe. Ainsi, lorsque l'on chiffre un message, les brouilleurs sont initialement dans une position qui va constituer une partie de la clé secrète. La première lettre est chiffrée en passant dans le tableau de connections puis dans les brouilleurs. Le premier brouilleur (le plus à gauche) tourne alors d'un cran. On peut ensuite chiffrer la deuxième lettre et faire de nouveau tourner le premier brouilleur d'un cran et ainsi de suite. Lorsque le premier brouilleur a fait un tour complet, un mécanismes comparable à ceux employés pour certains compteur mécaniques permet de faire avancer le deuxième brouilleur d'un cran. Ainsi, il faut chiffrer 26× 26× 26=17576 lettres avant de retrouver les trois brouilleurs dans la position de départ.



Figure 2 : A gauche, un brouilleur Enigma entier. A droite une version démontée; on distingue en particulier complètement à droite les fils réalisant la permutation.


2.3   Le réflecteur

Au bout des 3 brouilleurs est situé une dernière permutation appelée réflecteur et qui permet de faire revenir en arrière le ``signal''. Afin de chiffrer une lettre, le parcours suivi est donc le suivant : la touche du clavier correspondant à la lettre est pressée, on passe à travers le tableau de connections, on traverse les 3 brouilleurs, le réflecteur ``réfléchit'' la lettre, on retraverse les brouilleurs, le tableau de connections et enfin la bonne lampe s'allume. La figure  3 indique un exemple dans un alphabet réduit à 6 caractères, où le A est chiffré par la lettre D.



Figure 3 : Chiffrement d'une lettre avec Enigma : le A est chiffré en D


L'intérêt du réflecteur vient du fait que pour déchiffrer une lettre, il suffit d'appuyer dessus sur le clavier et la lettre en clair correspondante s'allume. Les opérations de chiffrement et de déchiffrement sont donc parfaitement identiques.

2.4   Utilisation d'Enigma

Afin de chiffrer un message, il convient de connaître une clé secrète partagée avec le destinataire de la communication. Cette clé se compose des informations nécessaires pour initialiser la machine, i.e. Une clé secrète est donc de la forme
[(B,J),(E,G),(P,Z),(A,T),(M,N),(D,X),(2,3,1),(A,V,P)]
Une fois la machine configurée, il suffit de taper un texte pour le chiffrer; après le codage de chaque lettre, les brouilleurs tournent comme précédemment expliqué. Pour déchiffrer un texte, il faut connaître la clé secrète, i.e. la position initiale des fiches et des brouilleurs. Le déchiffrement est ensuite identique au chiffrement.

2.5   Nombre de clés possibles

Le nombre de clés possible est gigantesque. En effet, le nombre de manière de placer les 6 fiches sur le tableau de connexions est égal au nombre de choix de 6 paires de lettres dans l'alphabet, soit
26!
12!× 14!
×
12!
6!×26
=100 391 791 500
Le nombre de manières de choisir l'ordre des brouilleurs est égal à 6 et enfin le nombre de positions initiales des brouilleurs est égal à 263=17576. Il y a donc au total plus de 1016 clés possibles, ce qui est colossal (pour l'époque). Il est cependant important de remarquer que les permutations employées dans les brouilleurs et le réflecteurs ne peuvent pas être considérées comme faisant partie du secret. En effet, toutes les machines utilisent les mêmes et il suffit donc d'en avoir une à disposition (les Anglais en ont par exemple récupéré une durant la guerre dans un sous-marin coulé) pour connaître ces permutations que l'on ne peut pas modifier. Ceci est une illustration d'un principe général en cryptographie, principe dit de Kerckhoffs, qui veut que tout le secret doit résider dans la clé secrète de chiffrement et de déchiffrement et pas dans une quelconque confidentialité de l'algorithme (ici la machine) qui ne peut être raisonnablement garantie.

3   Cryptanalyse d'Enigma

Malgré le nombre très important de clés possibles, les alliés ont quand même pu casser le système Enigma. Ce tour de force a pu être réalisé grâce au génie d'un chercheur Anglais, Alan Turing, inventeur de l'ordinateur. Les conséquences de ce cassage ont ensuite été capitales et ont grandement facilité la victoire des alliés en Europe. Nous renvoyons aux ouvrages cités en référence pour plus de détail sur cette passionnante histoire.
Nous allons utiliser une approche plus moderne que celle de Turing afin de casser Enigma grâce à la puissance des ordinateurs modernes. La précédente analyse du nombre de clés indique qu'il n'y a pas tant de manière que cela de choisir et de placer les brouilleurs mais qu'au contraire c'est le tableau de connexions qui crée la complexité. D'autre part, si l'on connaît la position des brouilleurs, on peut retrouver la position des fiches de connections en remarquant que 14 des lettres ne sont pas permutées. Pour cela, on utilise un outil théorique très puissant appelé indice de coïncidence et qui fonctionne de la manière suivante :
On considère une suite de N symboles choisis dans un alphabet donné. Pour chaque symbole i, on compte le nombre Ni d'apparitions de ce symbole. L'indice de coïncidence IC est alors obtenu au moyen de la formule suivante
IC=
 
å
i
Ni(Ni-1)
N(N-1)
La principale propriété de l'indice de coïncidence est d'être d'autant plus grand que les fréquences d'apparition des symboles sont déséquilibrées.
En pratique, l'alphabet de symboles considéré peut être l'ensemble des lettres ou bien l'ensemble des bigrammes (groupes de 2 lettres), l'ensembles des trigrammes, etc... Dans une langue quelconque, les fréquences de ces symboles sont très distinctes. Ainsi, le ``e'' est bien plus fréquent que le ``f'', le ``de'' bien plus que ``kh''... Ainsi, plus un texte est bien décodé, plus l'indice de coïncidence est fort car plus les fréquences des symboles sont distinctes. Par contre, un texte totalement brouillé va avoir un indice de coïncidence faible, chaque fréquence étant sensiblement égale aux autres.
Une stratégie de cassage d'Enigma est donc la suivante : étant donné un long texte chiffré, on devine la position initiale des brouilleurs. Avec une chance sur environ 100 000, on se trouve donc avec une bonne position des brouilleurs. On cherche ensuite à deviner la position des fiches. Pour cela, on essaye de placer la première; il y a 26× 25=650 possibilités et à chaque fois ont calcul l'indice de coïncidence du texte déchiffré. Intuitivement, la position donnant l'indice le plus élevé (ou un des indices les plus élevés) correspond à une bonne position de la fiche, i.e. une position où l'on a le plus de lettres à la bonne place. On peut ensuite deviner la place de la deuxième fiche et ainsi de suite. Nous sommes donc capables a priori, si la position des brouilleurs est initialement correctement devinée, de retrouver la position des fiches du tableau de connections, sans avoir à énumérer l'ensemble des possibilités, ce qui serait difficilement réalisable, même avec des ordinateurs puissants. Par contre, il est facile d'énumérer les 100 000 positions initiales possibles et à chaque fois de faire une recherche sur la position des fiches jusqu'à en trouver une qui fournisse un indice de coïncidence bien plus important que pour les autres.

4   Travail demandé

Le but de ce projet est double. Dans un premier temps, on écrira un programme en Java permettant de simuler une machine Enigma. Ce travail peut être réalisé de manière minimaliste en proposant un programme qui, pour une clé donnée, est capable de produire le chiffré d'un texte composé uniquement de lettres majuscules. De nombreuses extensions sont cependant envisageable : Dans un deuxième temps, on programmera la stratégie de cassage d'Enigma exposée ci-dessus. Pour cela, il est conseillé de résoudre progressivement les difficultés de la manière suivante : Si l'on souhaite partager le travail entre deux personnes d'un même binôme, il est déconseillé d'avoir une personne qui chiffre et une autre qui casse, cette dernière tâche nécessitant d'avoir bien compris le chiffrement ! D'autre part, il semble inutile de réaliser une belle interface graphique (ce qui est joli mais ne présente pas d'intérêt en terme d'algorithmique) si la cryptanalyse ne fonctionne pas. On veillera à faire un rapport clair et détaillé et à écrire un programme le plus lisible et modulaire possible.

5   Pour en savoir plus...

Trois livres retracent, entre autre, l'évolution historique de la cryptographie : Enfin, de nombreux sites WEB, de qualité très inégale, sont consacrés à Enigma ainsi qu'à d'autres aspect historiques de la cryptographie.
Ce document a été traduit de LATEX par HEVEA.