Chiffrement par substitution

Le chiffrement par substitution est une technique de chiffrement utilisée depuis bien longtemps puisque le chiffre de César en est un cas particulier. Sans autre précision, elle désigne en général un chiffrement par substitution monoalphabétique, qui consiste à substituer dans un message chacune des lettres de l'alphabet par une autre (du même alphabet ou éventuellement d'un autre alphabet), par exemple, ainsi que procédait César a par d, b par e et ainsi de suite. Quand l'alphabet d'arrivée est le même, la substitution est définie par une permutation des lettres de l'alphabet. Cependant, le chiffrement par substitution se distingue donc des chiffrements par permutation, définis eux par une permutation des lettres du message.

Le simple chiffrement par substitution est facile à casser par analyse des fréquences des lettres du texte chiffré mais demeure en tant que composant élémentaire des chiffrements modernes (ce sont les S-Boxes des réseaux de substitution-permutation).

Pour brouiller la cryptanalyse par analyse de fréquences, diverses techniques de substitution plus ou moins élaborées ont été inventées au cours des siècles, comme les chiffrements par substitution homophonique (une lettre fréquente peut être remplacée par des signes différents) ou par substitution polyalphabétique.

La substitution monoalphabétique est une des plus anciennes méthodes de chiffrement. Elle consiste à remplacer systématiquement dans le message clair une lettre donnée de l'alphabet par un signe donné (qui peut être simplement une autre lettre). Deux lettres distinctes doivent être chiffrées en deux signes distincts, sinon il y aurait ambiguïté lors du déchiffrement. Une même lettre est toujours chiffrée par le même signe : c'est le principe de la substitution monoalphabétique. Voici un exemple où l'alphabet du clair et celui du chiffré sont tous deux les 26 lettres de l'alphabet latin :

ABCDEFGHIJKLMNOPQRSTUVWXYZ
AZERTYUIOPQSDFGHJKLMWXCVBN

le message SUBSTITUTION devient LWZLMOMWMOGF.

L'ordre de l'alphabet latin étant connu, il suffit de donner la suite des 26 signes correspondant, qui est la clef de chiffrement. L'alphabet du chiffré peut être le même que celui du clair (en changer n'introduit pas de sécurité supplémentaire). Pour l'alphabet latin, ceci permet de construire 26! ≈ 4 × 10²⁶ substitutions (soit de l'ordre de 2⁸⁸), à savoir le nombre de permutations des 26 lettres.

Pour pouvoir retenir plus facilement la clef du chiffre (une suite de 26 lettres quand on chiffre avec l'alphabet latin), il est possible de l'obtenir à partir d'un mot clef, complété ensuite par les lettres restantes dans l'ordre de l'alphabet (en partant du début de l'alphabet ou de la dernière lettre du mot clef).

• carré de Polybe
• chiffre de Delastelle
• chiffre des Templiers
• chiffre de PigPen
• Chiffrement par décalage (chiffre de César)

La substitution polyalphabétique consiste à substituer une lettre du message en clair, par une autre choisie en fonction d'un état du cryptosystème, et non plus de manière fixe comme pour la monosubstitution. Ce changement de lettre tout au long du processus, s'obtient à l'aide d'une clé, qui indique le nombre de décalage à réaliser à ce moment. Pour chiffrer la lettre suivante on utilise alors le caractère suivant de la clé et ainsi de suite. On recommence au début de la clé quand tous ses caractères sont épuisés. La plus célèbre utilisation de cette technique reste la machine allemande Enigma, utilisée pendant la Seconde Guerre mondiale.

L'exemple suivant montre une polysubstitution simple avec une clé de longueur 3 qui va décaler les lettres de l'alphabet :

On définit la clé '123' qui indique que le premier caractère sera décalé d'une position, le second de 2 et le troisième de 3 positions, etc.

Le mot : WIKIPEDIA donne donc dans ce cas XKNJRHEKD.

Mais si on chiffre le mot : AAAAAAAAA cela donnera BCDBCDBCD.

On s'aperçoit tout de suite que chiffrer une suite identique de lettres donne une indication (entre autres) sur la longueur de la clé utilisée.

Si la clé utilisée est un mot et non pas un nombre, la position de chaque lettre dans l'alphabet sera utilisée afin de connaître le nombre de décalage à utiliser pour chacune des lettres. Ainsi, si le mot «clé» était utilisé au lieu de «123», il faudrait vérifier la position des lettres C, L et E dans l'alphabet. Le C arrive en 3e position, le L en 12e et le E en 5e. Il faudra donc utiliser la suite 3-12-5 pour déchiffrer le message. Le mot WIKIPEDIA deviendrait alors ZUPLBJGUF. Prendre note que si les positions des lettres dans le mot WIKIPEDIA et celles dans le mot CLÉ dépassent 26 (soit la lettre Z) on recommence à 1 (A). Dans l'exemple précédent, le P (16) additionné au L (12) nous amène à 28. Donc 28 - 26 = 2, ce qui donne B. Lors du déchiffrement, il ne faut pas oublier que l'on doit soustraire la clé du message chiffré. Donc, il faut prendre ZUPLBJGUF moins la clé, c'est-à-dire Z (26) - C (3), U (21) - L (12), P (16) - E (5), etc. Si en soustrayant la clé du message, nous obtenons un chiffre négatif, il faut simplement retourner à la lettre Z (26) et continuer de descendre. Ainsi, admettons que nous avons E (5) - J (10), nous obtiendrons finalement un U (21).

On sait depuis le XIX^e siècle que ce principe de polysubstitution possède de nombreuses failles, comme le montre l'officier prussien Friedrich Kasiski dans son test.

• chiffre de Vigenère
• chiffre de Hill
• Enigma

Ces chiffres, y compris les chiffres polyalphabétiques, n'ont plus qu'un intérêt historique, pédagogique ou de divertissement, et ne sont plus utilisés seuls pour les applications sérieuses, car les techniques permettant de les casser sont connues. L'exception étant peut-être la technique du masque jetable, qui utilise une clé aléatoire plus longue que le message et à usage unique, ce qui rend ce système incassable, mais pose d'importants problèmes de gestion d'un grand nombre de clés pour un grand nombre d'agents.

Les chiffres utilisant la simple substitution monoalphabétique sont faciles à casser par analyse fréquentielle, technique qui s'est utilisée également pour les chiffres par substitution homophonique. Pour les chiffres par substitution polyalphabétique il est nécessaire de connaître la longueur de la clef (le nombre de substitutions monoalphabétiques utilisées) pour pratiquer l'analyse de fréquence. La longueur de la clef peut se déceler par recherche de répétitions dans le chiffré (voir cryptanalyse du chiffre de Vigenère), ou par des méthodes statistiques (voir indice de coïncidence). Plus la clé est longue et aléatoire, plus le cassage du code est difficile.

Ce qui explique que certaines techniques de chiffrement par substitution polyalphabétique se sont révélés très difficiles à casser par ces méthodes, comme celui de la machine Enigma, utilisée par les Allemands lors de la Seconde Guerre mondiale. En effet, l'utilisation des rotors dans le fonctionnement de la machine allongeait considérablement la clé de chiffrement^[1] : 17576 (26*26*26) caractères pour la version avec 3 rotors (M3) et autant d'alphabets de substitution, ce qui correspond au nombre de lettres que l'on doit taper pour que le dernier rotor effectue une révolution complète. Ce nombre augmentait encore avec l'ajout de divers réglages supplémentaires (bagues rotor, ordre des rotors, etc). Comme la plupart des messages de tous types (communication militaire, ou autre...) dépasse rarement 17576 caractères, le cassage du code par analyse fréquentielle est compliqué de manière considérable. Pour le rendre possible la cryptanalyse d'Enigma a du exploiter une masse considérable de messages, diverses faiblesses comme des régularités dans les messages, et une grande puissance électromécanique de calcul, mais elle a atteint son objectif.

• Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone (1986), handbook of applied cryptography, 5^e édition (2001), CRC Press (ISBN 0-8493-8523-7),consultable en ligne, ch, 1.5.

• Chiffrement par décalage
• Chiffrement par permutation

• Portail de la cryptologie