ArithmétiqueNotion · Glossaire
chiffrement par transposition
Le chiffrement par transposition est une méthode de cryptographie qui réordonne les caractères d’un message selon une permutation déterminée par une clé, sans les remplacer. L’expéditeur et le destinataire doivent partager cette clé, qui permet d’appliquer la permutation puis son inverse pour déchiffrer. Le procédé brouille ainsi la lecture tout en conservant les caractères et leurs fréquences ; cette conservation le distingue d’un chiffrement par substitution et limite sa sécurité lorsqu’il est utilisé seul.
Sommaire
Ce que vous allez apprendre
- Distinguer une transposition d'une substitution et d'un encodage.
- Chiffrer et déchiffrer un message avec une permutation de colonnes.
- Relier une permutation à sa matrice et à son inverse.
- Interpréter correctement n! et repérer les limites d'une transposition pure.
En clair
Écrivez RENDEZVOUSDEMAIN dans une grille de quatre colonnes. Les lettres ne changent pas : seule leur place change lorsque les colonnes sont lues dans l'ordre 3, 1, 4, 2. Le message obtenu, NVDIREUMDOENEZSA, devient difficile à lire sans connaître cet ordre.
C'est le geste essentiel du chiffrement par transposition. La clé indique comment déplacer les positions, puis la permutation inverse remet chaque caractère à sa place.
Définition
Le chiffrement par transposition est un chiffrement classique qui applique une permutation aux positions d'un texte. Il conserve chaque caractère et son nombre d'occurrences, mais modifie l'ordre dans lequel les caractères apparaissent. L'expéditeur et le destinataire doivent partager la permutation qui sert de clé et convenir du découpage du texte.
Dans une transposition rectangulaire, le texte est inscrit dans une grille, puis les colonnes sont lues selon un ordre fixé. Si la grille possède c colonnes toutes distinctes dans la clé, il existe c! ordres possibles. Une permutation portant sur n positions quelconques en possède n! ; ainsi, 20! = 2 432 902 008 176 640 000, soit environ 2,43 × 1018. Une scytale réalise matériellement une autre transposition : la bandelette enroulée autour d'un cylindre impose l'alignement qui rend le message lisible.
Si le bloc clair est représenté par un vecteur x et la clé par une matrice de permutation P, le bloc chiffré y vérifie . Le déchiffrement applique la permutation inverse : . Cette écriture linéaire explique pourquoi des paires de blocs clairs et chiffrés suffisamment informatives peuvent révéler la clé.
Un exemple, pas à pas
Chiffrons le message RENDEZVOUSDEMAIN par transposition rectangulaire. Les espaces sont retirés avant l'opération.
Données :
texte clair : RENDEZVOUSDEMAIN ;
longueur : 16 lettres ;
grille : 4 lignes et 4 colonnes ;
ordre secret de lecture des colonnes : 3, 1, 4, 2.
texte clair : RENDEZVOUSDEMAIN ;
longueur : 16 lettres ;
grille : 4 lignes et 4 colonnes ;
ordre secret de lecture des colonnes : 3, 1, 4, 2.
1. Remplir la grille par lignes : R E N D, puis E Z V O, puis U S D E, puis M A I N.
2. Lire la colonne 3 : NVDI.
3. Lire ensuite les colonnes 1, 4 et 2 : REUM, DOEN et EZSA.
4. Concaténer ces quatre groupes : NVDIREUMDOENEZSA.
2. Lire la colonne 3 : NVDI.
3. Lire ensuite les colonnes 1, 4 et 2 : REUM, DOEN et EZSA.
4. Concaténer ces quatre groupes : NVDIREUMDOENEZSA.
Le texte chiffré contient bien 16 lettres. Un contrôle refaisable consiste à compter chaque lettre dans les deux textes : leurs effectifs sont identiques. Pour déchiffrer, on replace successivement les groupes NVDI, REUM, DOEN et EZSA dans les colonnes 3, 1, 4 et 2, puis on relit les lignes.
En pratique
Pour réaliser une transposition rectangulaire à la main, on choisit une largeur, on remplit la grille par lignes et on lit les colonnes selon la clé. Une grille régulière convient lorsque le message remplit exactement le rectangle ; sinon, il faut convenir d'un remplissage ou d'une règle pour la dernière ligne.
La scytale remplace la grille par un objet matériel. On enroule une bandelette autour d'un cylindre du diamètre convenu, on écrit le long du cylindre, puis on déroule la bande. Un cylindre compatible restitue les mêmes alignements à la lecture.
Pour vérifier une transposition, on compare d'abord la longueur et les effectifs de chaque caractère avant et après chiffrement. Si une lettre disparaît ou apparaît, il ne s'agit pas d'une permutation pure. Ce contrôle nécessaire ne suffit toutefois pas à retrouver l'ordre secret.
À ne pas confondre
Chiffrement par substitution. Une substitution remplace les symboles tout en conservant généralement leurs positions ; une transposition conserve les symboles et déplace leurs positions. Dans RENDEZVOUSDEMAIN, remplacer chaque E par une autre lettre relève de la substitution, tandis que lire les colonnes dans l'ordre 3, 1, 4, 2 relève de la transposition.
Encodage. Un encodage fixe une représentation destinée à être interprétée, sans exiger de clé secrète. La transposition vise au contraire la confidentialité : connaître la règle de permutation permet de remettre les caractères dans l'ordre.
Limites et pièges
Dernière ligne incomplète. Si la longueur du message n'est pas un multiple du nombre de colonnes, la forme du dernier bloc peut trahir des positions. Il faut fixer avant chiffrement une convention de remplissage ou une lecture irrégulière réversible.
Taille théorique de la clé. Le nombre n! ne mesure l'espace de clés que si toute permutation des n positions est réellement autorisée. Dans l'exemple, seules les quatre colonnes sont permutées : il y a 4! = 24 ordres, et non 16!.
Fréquences préservées. Une transposition pure conserve exactement les effectifs des lettres et l'indice de coïncidence. Elle perturbe cependant les voisinages de lettres : l'échec d'une analyse fondée sur les seules fréquences simples ne rend pas toutes les analyses statistiques inopérantes.
Paires clair-chiffré. Des exemples connus ne révèlent la matrice de permutation que s'ils apportent assez d'information pour distinguer les positions. Des caractères répétés ou des blocs trop peu variés peuvent laisser plusieurs permutations compatibles ; il faut alors d'autres paires.
Pour aller plus loin
La fiche cryptographie replace la transposition parmi les méthodes qui protègent un message et précise le rôle d'une clé.
La fiche matrice de permutation montre comment représenter algébriquement un réordonnement et retrouver la permutation inverse.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres