Chiffrement par transposition
Un chiffrement par transposition (ou chiffrement par permutation) est un chiffrement qui consiste à changer l'ordre des lettres, donc à construire des anagrammes. Cette méthode est connue depuis l'Antiquité, puisque les Spartiates utilisaient déjà une scytale.
Le chiffrement par transposition demande de découper le texte clair en blocs de taille identique. La même permutation est alors utilisée sur chacun des blocs. Le texte doit éventuellement être complété (procédé de bourrage) pour permettre ce découpage. La clef de chiffrement est la permutation elle-même.
Le nombre de permutations possibles d'une longueur donnée, qui est la factorielle de cette longueur, augmente donc rapidement avec celle-ci. Par exemple un mot de trois lettres ne peut être permuté que dans 6 (=3!) positions différentes. Ainsi "col" ne peut se transformer qu'en "col", "clo", "ocl", "olc", "lco" ou "loc". Lorsque le nombre de lettres croît, le nombre d'arrangements augmente rapidement et il devient plus difficile de retrouver le texte original sans connaître la permutation, et sans aucune connaissance sur le texte clair. Ainsi pour un chiffre par transposition qui utilise des blocs de 20 caractères, il y a 20! possibilités, soit 2 432 902 008 176 640 000 combinaisons.
Cryptanalyse
Les chiffrements par transposition ne modifient pas la fréquence des lettres du texte clair, puisque seul leur ordre change. Une analyse des fréquences des lettres d'un texte chiffré permet donc de repérer l'utilisation probable d'un chiffrement par transposition, mais ne permet pas ensuite de décrypter ce texte (contrairement à ce qui se passe pour les chiffrements par substitution). Un chiffrement par transposition ne modifie pas non plus l'indice de coïncidence.
Un chiffrement par transposition ne résiste pas à une attaque à texte clair connu (un couple clair-chiffré de la taille de la permutation utilisée donne immédiatement celle-ci).
Exemple
D'après des documents[1] déclassifiés dans les années 1990, le message suivant a été intercepté le par le service de renseignement radio (Radio Intelligence Division) de la FCC américaine, depuis sa station d'écoute à Laredo. Le message était envoyé par un agent allemand basé à Rio de Janeiro.
Message chiffré :
CARTM IELHX YEERX DEXUE VCCXP EXEEM OEUNM CMIRL XRTFO CXQYX EXISV NXMAH GRSML ZPEMS NQXXX ETNIX AAEXV UXURA FOEAH XUEUT AFXEH EHTEN NMFXA XNZOR ECSEI OAINE MRCFX SENSD PELXA HPRE
Clé de transposition : 8 4 9 14 1 2 16 10 3 17 15 19 11 5 20 6 7 12 13 18
Déchiffrement : le déchiffrement se fait en remplissant les colonnes verticalement, dans l'ordre défini par la clé. On commence par remplir de haut en bas la colonne numérotée 01 avec les huit premiers caractères du message chiffré : CARTMIEL. On continue en remplissant de la même façon la colonne numérotée 02 avec les huit caractères suivants HxYEERxD etc.
| 08 | 04 | 09 | 14 | 01 | 02 | 16 | 10 | 03 | 17 | 15 | 19 | 11 | 05 | 20 | 06 | 07 | 12 | 13 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | P | R | U | C | H | x | S | E | C | H | S | N | U | L | L | x | V | O | N |
| V | E | S | T | A | x | A | N | x | S | T | E | I | N | x | x | Q | U | E | E |
| N | x | M | A | R | Y | x | Q | U | E | E | N | x | M | A | R | Y | x | A | M |
| x | E | L | F | T | E | N | x | E | I | N | S | A | C | H | T | x | U | H | R |
| M | E | Z | x | M | E | Z | x | V | O | N | D | A | M | P | F | E | R | x | C |
| A | M | P | E | I | R | O | x | C | A | M | P | E | I | R | O | x | A | U | F |
| H | O | E | H | E | x | R | E | C | I | F | E | x | R | E | C | I | F | E | x |
| G | E | M | E | L | D | E | T | x | . | . | . | . | . | . | . | . | . | . | . |
Le texte clair est écrit horizontalement. Il s'avère être en Allemand :
Spruch 60. Von VESTA An STEIN.
QUEEN MARY am Elften eins acht Uhr MEZ von Dampfer CAMPEIRO auf hoehe RECIFE gemeldet.
Soit, en Français :
Texte 60, de VESTA pour STEIN.
Queen Mary signalé au large de Recife le 11 à 18 heures HEC par le vapeur Campeiro.
Remarques sur la sécurité de ce message :
- le numéro du message a été épelé (« sechs null », c'est-à-dire « six zéro ») plutôt qu'écrit en chiffres (« 60 »), ce qui aurait constitué une erreur permettant à un décrypteur ennemi de postuler immédiatement que les colonnes contenant le 6 et le 0 doivent être adjacentes.
- les noms propres sont doublés afin de fiabiliser la transmission du message. Ces redondances constituent une faille dans laquelle un décrypteur peut se glisser. En supposant que celui-ci ne connaisse pas la clé mais en connaisse ou déduise la longueur, il verra qu'à la ligne 7 du message certaines lettres sont doublées: C, E, E, E, F, H, I, R. Il pourra tenter de trouver un nom propre relatif au contexte du message en utilisant ces lettres : Recife. (Ici un H et un E ne sont pas utilisés)
Notes et références
- Cet article contient tout ou une partie d’un document provenant du site Ars Cryptographica. L’auteur autorise Wikipédia à utiliser les textes présents sur son site si la source originale est mentionnée.
- George E. Sterling, « (en) « The U.S. Hunt for Axis Agent Radios » », Studies in Intelligence, vol. 4, Issue 2, , p. 35-54 (lire en ligne).