substitution polyalphabétique

Imaginez que chaque lettre d'un message soit décalée dans l'alphabet, mais que le décalage change à chaque position. Une clé partagée indique successivement quel décalage employer. Ainsi, deux lettres identiques du texte initial peuvent devenir deux lettres différentes dans le texte chiffré. Cette variation distingue la substitution polyalphabétique d'un chiffrement qui conserverait la même correspondance du début à la fin.

Une substitution polyalphabétique remplace les lettres d'un message à l'aide de plusieurs alphabets de substitution. La clé connue de l'expéditeur et du destinataire détermine l'alphabet appliqué à chaque position. Avec l'alphabet latin numéroté de A = 0 à Z = 25, un chiffre de Vigenère peut être décrit par une addition modulo 26. Pour une position donnée, la valeur chiffrée est la somme de la valeur de la lettre claire et de celle de la lettre de clé, ramenée entre 0 et 25.

Le cadran chiffrant d'Alberti et le chiffre de Trithème comptent parmi les premières réalisations notables de cette idée. Le chiffre de Vigenère en est le représentant le plus célèbre et fut tenu pour inviolable pendant environ trois siècles. La machine Enigma en constitue une application électromécanique : ses rotors font évoluer les substitutions et produisent un très grand nombre de configurations possibles. Ces systèmes appartiennent à la même famille, sans employer nécessairement la même règle de changement d'alphabet.

Chiffrons le mot MATHS avec la clé CLE. Les données sont l'alphabet latin de 26 lettres, la numérotation A = 0 à Z = 25 et la clé répétée sous la forme CLECL. À chaque position, on additionne la valeur de la lettre claire et celle de la lettre de clé, puis on prend le reste modulo 26.

1. M vaut 12 et C vaut 2 : 12 + 2 = 14, donc la première lettre est O.

2. A vaut 0 et L vaut 11 : 0 + 11 = 11, donc la deuxième lettre est L.

3. T vaut 19 et E vaut 4 : 19 + 4 = 23, donc la troisième lettre est X.

4. H vaut 7 et C vaut 2 : 7 + 2 = 9, donc la quatrième lettre est J.

5. S vaut 18 et L vaut 11 : 18 + 11 = 29. Le reste de 29 dans la division par 26 est 3, donc la cinquième lettre est D. Le message chiffré est OLXJD. Pour contrôler, on soustrait les valeurs de CLECL modulo 26 : on retrouve successivement M, A, T, H et S.

Pour chiffrer un court message à la main avec le chiffre de Vigenère, les correspondants choisissent une clé, la répètent jusqu'à la longueur du texte, puis appliquent le décalage indiqué à chaque position. Une substitution monoalphabétique suffit seulement si l'on veut conserver une correspondance unique pendant tout le message.

Pour déchiffrer, le destinataire doit connaître la même clé et respecter le même alignement. Un décalage d'une position dans la clé modifie généralement l'alignement et peut donc modifier les lettres suivantes ; le bon réflexe est de vérifier ensemble le début de la clé et le début du message.

Pour étudier Enigma, on observe le rôle des rotors : leur évolution fait varier la substitution au fil de la frappe. Le chiffre de Vigenère est préférable comme modèle manuel lorsque l'objectif est de suivre explicitement les décalages lettre par lettre.

Substitution monoalphabétique. Elle conserve un seul alphabet de remplacement pour tout le message. Pour distinguer les systèmes, il faut examiner leur règle : une substitution monoalphabétique n'emploie qu'un alphabet, tandis qu'une substitution polyalphabétique peut en employer plusieurs selon la position. Une correspondance constante observée dans un message peut n'être qu'un cas particulier et ne suffit pas à conclure.

Chiffre de Vigenère. Il ne désigne pas toute la famille, mais un système célèbre qui en fait partie. Une méthode à alphabets variables peut donc être polyalphabétique sans suivre précisément la règle de Vigenère, comme le montrent le cadran d'Alberti, le chiffre de Trithème et Enigma.

Clé réduite à une seule lettre. Dans un Vigenère, le même décalage se répète alors à chaque position. Le symptôme est une correspondance redevenue constante ; il faut traiter ce cas comme une substitution monoalphabétique, et non comme une variation effective des alphabets.

Répétition de la clé. Une clé plus courte que le message recommence périodiquement. Dans l'exemple MATHS, CLE devient CLECL : les positions 1 et 4 utilisent toutes deux C. Il faut conserver cet alignement pour chiffrer comme pour déchiffrer.

Famille et réalisation. Dire qu'Enigma applique le principe polyalphabétique ne signifie pas qu'elle exécute simplement le calcul manuel de Vigenère. Ses rotors produisent des substitutions évolutives et un grand nombre de configurations ; il faut décrire séparément le mécanisme propre à chaque système.

Réputation d'inviolabilité. Le chiffre de Vigenère fut considéré comme inviolable pendant environ trois siècles, et les concepteurs d'Enigma croyaient leur machine indéchiffrable. Ces jugements historiques ne constituent pas une preuve mathématique d'impossibilité de déchiffrement.

Le chiffre de Vigenère détaille le représentant le plus célèbre de cette famille et son emploi d'une clé répétée.

La machine Enigma montre comment des rotors réalisent électromécaniquement des substitutions qui évoluent au fil du message.

La cryptanalyse présente l'étude des procédés qui cherchent à retrouver l'information dissimulée par un chiffrement.

La substitution monoalphabétique éclaire, par contraste, ce qui change lorsqu'un seul alphabet de remplacement reste fixe.