Les grilles tournantes du colonel Fleissner
La méthode des grilles tournantes est une méthode de cryptographie popularisée par le colonel autrichien Fleissner dans son livre Handbuch der Kryptographie. Il est difficile de savoir s'il en est réellement l'inventeur (des procédés de chiffrement par grille étaient utilisés depuis fort longtemps), mais son nom est resté attaché à cette méthode car Jules Verne, en 1885, a repris cette méthode de cryptographie dans son roman Mathias Sandorf, en l'attribuant à Fleissner.
Une grille de Fleissner est un carré que l'on divise lui-même en 36 petits carrés (égaux). Neuf de ces petits carrés sont découpés, en respectant la règle suivante : si on tourne la grille d'un 1/4 de tour, d'un 1/2 tour ou de 3/4 de tour, les trous que l'on obtient ne sont jamais superposés. Par exemple, la grille suivante est une grille de Fleissner.
Pour chiffrer un message, on commence par poser la grille sur une feuille, puis on écrit les neuf premières lettres du message dans les trous de la grille. On effectue alors un quart de tour à la grille (en la laissant au même endroit de la feuille). On écrit les 9 lettres suivantes dans les trous (qui ont changé de place). On recommence alors deux fois (en tournant à chaque fois la grille d'un quart de tour). Éventuellement, on complète le message avec des lettres choisies au hasard. A la fin, on obtient donc un tableau 6×6 de lettres. En lisant le tableau de gauche à droite et de haut en bas, on fabrique le message codé. Si le message comporte plus de 36 lettres, on recommence l'opération…
Voyons par exemple comment coder ENVOYER DES RENFORTS ET DES MUNITIONS avec la grille précédente. La première étape donne :
Les 3 étapes suivantes donnent :
Remarquez que l'on doit compléter le message par des lettres factices pour remplir la dernière grille. Maintenant, si on ôte la grille, il reste sur la feuille de papier les lettres suivantes, disposées en carré :
Le message chiffré est lu de gauche à droite et de haut en bas :
TEENI VTOSN ORSDY EEMNE DSRFU MOERD UTNEI S
Si le message fait plus de 36 lettres, on répète plusieurs fois le même procédé.
Pour déchiffrer un message, on fait les opérations en sens inverse. On commence par disposer les 36 premières lettres sous la forme d'un carré 6×6. On pose la grille, les 9 trous découvrent les 9 premières lettres du message clair. On tourne la grille d'un quart de tour, et on obtient les 9 lettres suivantes, et ainsi de suite… Ce déchiffrement est très bien expliqué par Jules Verne dans Mathias Sandorf.
On peut construire des grilles de Fleissner de toute taille $n×n$ (si $n$ est impair, il ne faut pas tenir compte du carré central). Ces grilles furent utilisées par l'arméee allemande durant la Première Guerre Mondiale, à la fin de l'année 1916. Chaque grille possédait un non de code : Anna pour la grille 5×5, Berta pour la grille 6×6, Clara pour la grille 7×7, Dora pour la grille 8×8, Emil pour la grille 9×9, Franz pour la grille 10×10.
Cette partie nécessite quelques connaissances en dénombrement (du niveau Terminale Spécialité).
La sécurité d'un chiffre dépend en partie du nombre de clés différentes qu'on peut produire. On veut donc ici calculer le nombre de grilles différentes de taille $n.$ On va supposer que $n$ est pair. Il nous faut choisir $n^2/4$ carrés dans la grille de telle sorte qu'il n'y ait pas de recouvrement en effectuant l'une des rotations possibles.
On commence par choisir un des carrés. Il y a $n^2$ choix possibles. Pour le choix du deuxième carré, on ne peut pas choisir ce premier carré, ni les 3 carrés que l'on obtient par rotation de la grille. Il reste $n^2-4$ choix. Pour le choix du troisième carré, on ne peut choisir ni le premier carré, ni le deuxième carré, ni aucune des carrés obtenus à partir de ces deux par rotation. Il reste $n^2-8$ choix.
On pourra donc avoir l'impression qu'il y a $$n^2\times(n^2-4)\times (n^2-8)\times\cdots \times 4$$ choix possibles de grilles. Mais il faut faire attention! En effet, on obtient la même grille si on échange le premier trou et le deuxième trou ou plus généralement si on permute les trous que l'on a choisi. Comme on a choisi $n^2/4$ carrés, il y a $(n^2/4)!$ permutations de ces carrés et on en déduit que le nombre de grilles de Fleissner possible est \begin{align*} N&=\frac{n^2\times(n^2-4)\times (n^2-8)\times\cdots \times 4}{\left(\frac{n^2}4\right)!}\\ &=\frac{4\times \frac{n^2}4\times 4\times \left(\frac{n^2}4-1\right)\times \cdots \times 4\times 1}{\left(\frac{n^2}4\right)!}\\ &=\frac{4^{n^2/4}\times \left(\frac{n^2}4\right)!}{\left(\frac{n^2}4\right)!}\\ &=4^{n^2/4}. \end{align*} Ainsi, pour $n=6,$ il y a $4^9=262144$ grilles de taille $6\times 6$ différentes, suffisamment pour que le chiffre soit, avec les moyens de l'époque, considéré comme sûr. Toutefois, il avait deux inconvénients : il était peu aisé de choisir et de se mettre d'accord sur une grille parmi les 262144. De plus, si quelqu'un parvient à dérober la grille utilisée, toute la sécurité du chiffre s'envole...
Pour définir votre grille de Fleissner, cocher les cases que vous voulez trouer.