Transposition
Aussi appelé : Chiffre par transposition · Permutation
La transposition est le second grand principe historique du chiffrement, complémentaire de la substitution. Plutôt que de remplacer chaque lettre, on garde les lettres du clair telles quelles et on en change l’ordre selon une règle déterministe. Le clair ATTAQUE peut devenir EUQATTA (renversé), TAQATEU (autre permutation), ou n’importe quel autre anagramme conformément à la règle.
La signature : fréquence préservée
Conséquence importante pour la cryptanalyse : la fréquence des lettres reste rigoureusement identique entre clair et chiffré. Compter les lettres d’un Rail Fence ou d’une Scytale donne exactement le même profil que pour le clair en français (le E à 17 %, le A à 8 %…) — l’analyse de fréquence est aveugle. C’est la première signature qui dit au cryptanalyste : « ne perds pas ton temps avec un comptage simple ».
L’indice de coïncidence d’un chiffré par transposition est aussi identique à celui du clair (~0,074 FR, ~0,067 EN). Mêmes lettres, même proportion : juste mélangées.
La faiblesse : digrammes brisés
En revanche, les digrammes (paires) et trigrammes (triplets) sont brisés. Si vous lisez QU 12 fois dans un texte clair français, vous le retrouverez 0 fois dans son chiffré par transposition (sauf accident). De même TH en anglais, ENT en français, etc.
C’est le levier de cryptanalyse classique : reconstituer les digrammes attendus en testant des permutations plausibles. Méthode :
- On suppose une largeur de grille (pour transposition par colonnes).
- On découpe le chiffré en colonnes.
- On essaie de réordonner ces colonnes pour que les paires de lettres adjacentes forment des digrammes français/anglais courants.
- Le bon ordre saute aux yeux quand
QU,EN,LEapparaissent en cascade.
Sur un texte court, le bruit domine et on peut bloquer. Sur un texte long, c’est mécanique.
Exemples typiques
Scytale (Sparte, -500)
Le chiffre le plus ancien attesté. On enroule un parchemin autour d’un bâton de circonférence fixée. On écrit le message ligne par ligne le long du bâton. Une fois déroulé, le parchemin porte les lettres dans un ordre permuté. Le destinataire avec un bâton de même circonférence peut relire le message ; tout autre lit du charabia. La clé est la circonférence.
Rail Fence
On écrit le clair en zigzag sur N « rails » (lignes), puis on lit ligne par ligne. Pour N = 3 :
A . . . T . . . A . . . U
. T . . . A . . . Q . . . E
. . T . . . . . . . . . .Lecture : ATAU + TAQE + T. Très simple, espace de clés ridicule (juste N), cassable en quelques essais.
Transposition par colonnes
On écrit le clair en grille de largeur fixée par une clé, puis on lit les colonnes dans l’ordre dicté par la clé. Avec clé CHIFFRE (7 colonnes) :
C H I F F R E
1 4 6 2 3 7 5
A T T A Q U E
A L A U B E .On lit colonne 1 (A,A), puis 2 (A,U), puis 3 (Q,B)… selon l’ordre alphabétique de la clé. Espace de clés : n! permutations possibles avec une clé de longueur n.
Double transposition
Deux passes de transposition par colonnes avec des clés différentes. Le résultat brouille les digrammes au point que la cryptanalyse devient très ardue. Utilisé par l’armée allemande pendant la Première Guerre mondiale (système ÜBCHI), puis cassé par les services français.
Grille tournante
Une grille rectangulaire à trous, posée sur une grille pleine. On écrit le clair dans les trous, on tourne la grille d’un quart de tour, on continue, et ainsi de suite. À la fin, on lit la grille pleine ligne par ligne. Inventé par le mathématicien italien Cardan au XVIᵉ siècle.
Substitution versus transposition : le tableau récapitulatif
| Substitution | Transposition | |
|---|---|---|
| Action | Remplace les lettres | Réordonne les lettres |
| Fréquence du clair | Modifiée | Préservée à l’identique |
| Indice de coïncidence | Variable | Identique au clair |
| Anagramme du clair ? | Non | Oui |
| Cryptanalyse | Analyse de fréquence | Reconstitution de digrammes |
Le mariage moderne : Shannon, confusion + diffusion
Les meilleurs chiffres modernes combinent toujours substitution ET transposition : c’est le principe de Shannon (1949) — « confusion + diffusion ». La substitution apporte la confusion (rend opaque le lien entre clé et chiffré). La transposition apporte la diffusion (étale l’effet d’un seul bit du clair sur tout le chiffré).
- AES alterne SubBytes (substitution non linéaire), ShiftRows (transposition cyclique), MixColumns (mixage linéaire), AddRoundKey à chaque round. Sur 10-14 rounds.
- DES alterne S-Boxes (substitution) et P-box (permutation/transposition) sur 16 rounds Feistel.
- ADFGVX (1918) chiffre allemand de la fin de la Première Guerre : substitution Polybius + transposition par colonnes. Cassé par Painvin en 1918.
La transposition pure aujourd’hui
La transposition pure (sans substitution) est devenue rare comme chiffrement de production — elle ne tient pas face aux outils modernes. Mais on la croise encore :
- En CTF et puzzles de chiffrement, comme étape pédagogique.
- En stéganographie linguistique : on permute les lettres d’un mot pour cacher un sens (anagrammes de noms).
- Dans des chiffres hybrides où la transposition vient compléter une substitution.
À retenir :
- Transposition = réordonner les lettres sans les remplacer. Anagramme géant.
- Préserve la fréquence des lettres et l’IC du clair → l’analyse de fréquence ne donne rien.
- Casse classique : reconstituer les digrammes/trigrammes attendus en testant des permutations.
- Exemples : scytale, rail fence, colonnaire, double transposition, grille tournante.
- Les chiffres modernes (AES, DES) combinent toujours substitution + transposition (doctrine confusion + diffusion de Shannon).