Substitution

La substitution est l’un des deux grands principes historiques du chiffrement, l’autre étant la transposition. Substituer, c’est remplacer chaque élément du clair par un autre symbole selon une règle fixe ou changeante. Le clair ATTAQUE peut devenir DWWDTXH (substitution), mais reste ATTAQUE après transposition (juste mélangé : TQEAUTA). Les deux familles ont leurs forces, leurs faiblesses, et se combinent dans tous les chiffres modernes.

Quatre sous-familles

1. Substitution monoalphabétique

Une seule table fixe. Chaque lettre devient toujours la même autre lettre. Espace de clés modeste à très grand selon la variante :

• César : décalage entier (25 clés). Le grand-père.
• Atbash : miroir de l’alphabet (1 transformation, sans clé).
• ROT13 : décalage 13 (1 transformation auto-inverse).
• Affine : c = a × p + b (312 clés).
• Substitution monoalphabétique générale : permutation arbitraire (26! ≈ 4 × 10²⁶ clés).

Toutes tombent à l’analyse de fréquence — la substitution préserve la signature statistique des lettres.

2. Substitution polyalphabétique

Plusieurs tables alternées. La même lettre du clair peut être chiffrée différemment selon sa position :

• Vigenère (1586) : 26 alphabets de César indexés par les lettres d’une clé textuelle répétée.
• Beaufort : variante par soustraction, auto-inverse.
• Autokey : la clé étend par concaténation du clair.
• Enigma (1923) : 3-4 rotors qui changent à chaque touche.
• Porta : 13 alphabets, structure plus régulière que Vigenère.

Aplatissent la signature de fréquence. Cassables par Kasiski + indice de coïncidence dès qu’il y a une période.

3. Substitution polygraphique

On substitue par groupes de lettres (digrammes, trigrammes…) plutôt que lettre à lettre. Préserve la signature au niveau du n-gramme, donc plus difficile à attaquer :

• Playfair (1854) : substitution de paires de lettres (digrammes) via une grille 5×5 dérivée d’un mot-clé.
• Hill (1929) : substitution de blocs de N lettres via multiplication matricielle modulo 26. Premier chiffre où l’algèbre linéaire entre vraiment en jeu.
• Two-square, four-square : variantes de Playfair sur deux ou quatre grilles.

Plus laborieuses à casser à la main, mais ne tiennent pas face à un ordinateur moderne.

4. Substitution homophonique

Une lettre fréquente du clair (le E par exemple) est remplacée par plusieurs symboles différents dans le chiffré, choisis aléatoirement à chaque occurrence. Idée : aplatir la fréquence en distribuant les E entre cinq ou six symboles distincts.

• Chiffre de Marie Stuart (XVIᵉ siècle) : nomenclateur substitution + table de noms codés. Cassé par Phelippes en 1586.
• Chiffre Beale (XIXᵉ siècle) : célèbre énigme américaine, partiellement résolue.
• Cipher 340 du Zodiac (1969) : chiffre homophonique cassé en 2020 par David Oranchak et Jarl Van Eycke.

Plus résistant que la monoalphabétique pure, mais reste vulnérable à des attaques statistiques avancées (modèles de chaînes de Markov sur les bigrammes).

Substitutions symboliques

Les chiffres dits symboliques (Pigpen, Templier, Hommes dansants, Aurebesh, Dancing Men) sont généralement des substitutions monoalphabétiques où le symbole substitué est un glyphe au lieu d’une lettre. La cryptanalyse ne change pas — l’analyse de fréquence appliquée aux glyphes les casse aussi vite qu’un chiffre lettré. Le glyphe n’est qu’un costume visuel ; il sert à intriguer ou à intégrer un univers fictionnel (Star Wars, Sherlock Holmes), pas à renforcer la sécurité.

Substitution versus transposition

	Substitution	Transposition
Action	Remplace les lettres	Réordonne les lettres
Fréquence du clair	Modifiée (mono) ou aplatie (poly)	Strictement préservée
Indice de coïncidence	Variable	Identique au clair
Anagramme du clair ?	Non	Oui
Exemples classiques	César, Vigenère, Playfair	Scytale, Rail Fence, Colonnaire

Les deux principes sont régulièrement combinés : ADFGVX combine substitution + transposition, Enigma fait de la substitution polyalphabétique en cascade, et AES alterne substitution (S-Box) et permutation/transposition (ShiftRows, MixColumns) à chaque round. C’est la doctrine de Shannon : « confusion + diffusion ». La substitution apporte la confusion (rend le lien entre clé et chiffré opaque) ; la transposition apporte la diffusion (étale l’effet d’un bit du clair sur tout le chiffré).

Pour creuser

• AES = 10 rounds de SubBytes (substitution non linéaire S-Box) + ShiftRows (transposition cyclique) + MixColumns (mixage linéaire) + AddRoundKey. C’est de la substitution polyalphabétique au niveau des octets, sur 128 bits.
• DES = combinaison de substitution (S-boxes) et de permutation (P-box) sur 16 rounds Feistel.

À retenir :

• Substitution = remplacer les éléments du clair. Transposition = les réordonner. Les deux principes fondamentaux du chiffrement classique.
• Quatre sous-familles : monoalphabétique, polyalphabétique, polygraphique, homophonique. Sécurité croissante.
• Les chiffres symboliques (Pigpen, Templier) sont des substitutions monoalphabétiques en glyphes — pas plus solides que César.
• AES et DES combinent substitution + transposition à chaque round (doctrine confusion + diffusion de Shannon).