Machine Enigma : combinatoire, probabilité et cryptographie

Introduction

Pendant la Seconde Guerre mondiale, les Allemands utilisaient une machine appelée Enigma pour chiffrer leurs messages militaires. Avec ses rotors et ses câblages, elle produisait un nombre gigantesque de combinaisons, si bien qu’on la croyait incassable. Pourtant, grâce aux mathématiques, et notamment aux travaux d’Alan Turing et de son équipe, ce code a été brisé.

I. La machine Enigma : fonctionnement et enjeux historiques

1. Principe de base de la machine

La machine Enigma est l’une des plus célèbres machines de cryptographie de l’Histoire. Elle a été utilisée par l’armée allemande pendant la Seconde Guerre mondiale pour chiffrer toutes ses communications stratégiques.

Son fonctionnement repose sur un principe simple mais très ingénieux :

• Un opérateur tape une lettre sur un clavier électrique.
• Le courant traverse alors une série de rotors, chacun réalisant une permutation des 26 lettres de l’alphabet.
• Après avoir traversé les rotors et un réflecteur, le courant revient par les mêmes rotors dans l’autre sens.
• Une lampe s’allume sur le tableau, donnant la lettre chiffrée.

Chaque frappe provoque en plus la rotation d’un rotor (le «rotor rapide»), ce qui décale toutes les permutations. Ainsi, même si on tape deux fois la même lettre, elle ne sera pas chiffrée de la même manière.

Mathématiquement, chaque rotor est une permutation de l’ensemble [math]{A,B,C,\dots,Z}[/math]. Si l’on compose plusieurs permutations (rotor de droite, rotor du milieu, rotor de gauche, puis le réflecteur), on obtient une permutation beaucoup plus complexe, qui change après chaque frappe de touche.

C’est ce mécanisme de permutation + rotation qui rend le code d’Enigma si puissant : le chiffrement dépend non seulement de la clé initiale, mais aussi de la position courante des rotors.

2. L’importance du secret : un nombre astronomique de clés

Chaque jour, les opérateurs allemands recevaient une clé secrète quotidienne, composée de plusieurs paramètres. Ces choix, combinés entre eux, créaient un espace de configurations gigantesque.

Voyons cela étape par étape avec des outils de dénombrement.

a) Choix et ordre des rotors

Parmi 5 rotors disponibles, il fallait en choisir 3, dans un certain ordre.

C’est une arrangement de 5 objets pris 3 à 3 :

A_5^3 = 5\times 4\times 3 = 60.

b) Orientation initiale des rotors

Chaque rotor peut être placé sur 26 positions différentes (une par lettre de l’alphabet).

Comme il y a 3 rotors : [math]26^3 = 17576[/math] positions possibles.

c) Tableau de connexions (le “plugboard”)

C’est la partie la plus complexe. On y connecte généralement 10 câbles qui relient 20 lettres sur 26 par paires.

1. On choisit d’abord les 20 lettres à connecter : [math]\binom{26}{20}[/math] façons.
2. Puis on forme des paires entre ces 20 lettres. Le nombre de façons de partitionner 20 lettres en 10 paires est :

\dfrac{20!}{2^{10}10!}

(en effet, on divise par [math]2^{10}[/math] car l’ordre dans chaque paire ne compte, et par [math]10![/math] car l’ordre des paires ne compte pas non plus).

Au total, le nombre de configurations du plugboard vaut :

\binom{26}{20}\times\dfrac{20!}{2^{10}10!}\approx 6\times 10^{14}.

d) Nombre total de clés

En combinant les trois étapes :

N = 60 \times 26^3 \times \left(\binom{26}{20}\dfrac{20!}{2^{10}10!}\right).

Ce produit donne environ :

N \approx 1,6\times 10^{20}.

e) Interprétation et comparaison d’ordres de grandeur

Si on testait 1 clé par seconde, il faudrait :

\dfrac{1,6\times 10^{20}}{60\times 60\times 24\times 365}\approx 5\times 10^{12}\ \text{années}.

Or, l’âge de l’univers est estimé à environ [math]1,4\times 10^{10}[/math] années.

Donc même en testant une clé par seconde depuis le Big Bang, on n’aurait pas fini d’explorer l’espace des clés d’Enigma !

La force d’Enigma reposait donc uniquement sur la taille astronomique de son espace de clés.

C’est pourquoi les Allemands étaient persuadés qu’Enigma était «incassable». Mais comme on le verra, ce n’est pas la taille de l’espace qui a vaincu les Alliés, mais les faiblesses logiques et l’utilisation des probabilités.

II. Les faiblesses exploitées : probabilités et statistiques

1. Les “cribs” (hypothèses sur des mots probables)

Pour casser Enigma, les Alliés ne pouvaient pas tester les [math]1,6 \times 10^{20}[/math] clés possibles une par une : c’était matériellement impossible.

Ils ont donc cherché à exploiter des régularités linguistiques.