Le chiffre de Vigenère

Pour l’énigme de l’épisode 3 de Cryptotrucs, allez en bas d’article.

Un peu d’histoire

Contrairement à ce que suggère son appellation le chiffre de Vigenère semble avoir été conçu par Giovan Battista Bellaso, un cryptographe italien du 16ème siècle.

Malgré tout, c’est le chiffre de Vigenère qui restera et non celui de Bellaso.

Blaise de Vigenère présente son chiffrement 20 ans après Bellaso avec des évolutions par rapport à celui-ci.

On nomme cette méthode de chiffrement Vigenère à partir du 19ème siècle sans se soucier de Bellaso. De plus Bellaso a été rapidement oublié au profit de Porta.

Plein de noms. Ah, l’histoire !

Bien sûr, ce chiffre n’est pas sûr et a été cassé dès le 19ème siècle.

La clé à la place du décalage

Le chiffre de Vigenère introduit une grande innovation par rapport au chiffre de César : la notion de clé.

Cette différence place ce chiffrement comme polyalphabétique et non plus monoalphabétique. On n’a plus « une lettre en clair donne une, et seulement une, lettre chiffrée » mais on peut avoir une lettre en clair qui donne deux lettres chiffrées différentes et une lettre chiffrée qui peut venir de deux lettres en clair différentes.

On utilise donc plusieurs alphabets de substitution (différents décalages de lettres dans un même message) contrairement au chiffre de César. D’où le mot « polyalphabétique ».

Les règles de substitution (comment on passe d’un alphabet à l’autre) sont données par les lettres de la clé et une table de substitution.

Vous n’avez pas tout compris ? On va illustrer ça par des exemples dans les chapitres suivants, ne vous inquiétez pas.

De plus, un autre article reviendra sur la classification des chiffrements.

Le chiffre lui-même

On entre donc dans le vif du sujet. Il y a deux façons de se représenter le chiffre de Vigenère le plus classique (avec les variantes, c’est une autre histoire).

Représentation par table

Pour la représentation par table, on a besoin d’une table (oui, oui), ou plutôt d’un tableau de substitution. Le voici :

Ça vous semble touffu mais ça ne l’est pas tant que ça. Si vous regardez les lignes de la table, vous voyez l’alphabet latin avec un décalage d’une lettre par ligne. De même, si vous regardez les colonnes.

Le chiffre consiste à prendre la lettre à l’intersection de la lettre du message en clair (les colonnes) et la lettre de la clé (les lignes). Cette lettre à l’intersection est celle du message chiffré.

Exemple :

Chiffrement

Prenons le message : « J’ai plaqué mon chêne » (extrait de « Auprès de mon arbre » de Georges Brassens)

Et la clé : « Una mattina » (extrait de « Bella Ciao »)

On regarde l’intersection de chaque lettre :

La colonne « J » et la ligne « U » donnent « D »,

la colonne « a » (on oublie l’apostrophe pour l’instant) et la ligne « n » donnent « n »,

la colonne « i » et la ligne « a » donnent « i »,

etc.

Si le message dépasse la clé en longueur, on répète la clé. On considère le « ê » et le « é » comme un « e ».

On obtient donc :

« D ni bltjcr mia ctegx »

Déchiffrement

Pour le déchiffrement, on regarde pour chaque ligne, correspondant à la lettre de la clé, où se situe la lettre du message chiffré et on prend la lettre en haut de la colonne correspondante qui est celle du message en clair.

Donc, en reprenant la clé : « Una mattina »

Et le message chiffré : « D ni bltjcr mia ctegx »

Dans la ligne « U », la lettre « D » est à la dixième position, donc la colonne « J »,

dans la ligne « n », la lettre « n » correspond à la première position, la colonne « a »,

etc.

On retrouve donc :

« J ai plaque mon chene »

Représentation par congruence

La deuxième représentation est la représentation mathématique, la congruence. Si ce mot ne vous dit rien, regardez cet article.

Pour utiliser la congruence, on va substituer les lettres par des chiffres. On utilise la règle suivante :

A=0, B=1, C=2, D=3, E=4, F=5, G=6, H=7, I=8, J=9, K=10, L=11, M=12, N=13, O=14, P=15, Q=16, R=17, S=18, T=19, U=20, V=21, W=22, X=23, Y=24, Z=25

Et pour chiffrer, on additionne la clé au message. Pour déchiffrer, on soustrait la clé du message.

Exemple :

Chiffrement

On reprend notre message : « J’ai plaqué mon chêne »

Et notre clé : « Una mattina »

On va aligner le message et la clé (en enlevant l’apostrophe et les accents) et répéter la clé pour couvrir tout le message :

« J ai plaque mon chene »

+

« Una mattina Una matti »

=

9

+

20

=

29

On n’a pas de lettre de valeur 29 (le maximum c’est 25), donc on utilise la congruence. On considère un modulo 26 (de 0 à 25, 26 nombres).

Donc,

$$ 29 \equiv 29-26 \pmod{26} \equiv 3 \pmod{26} = D $$

On peut continuer nos calculs :

« J ai plaque mon chene »

+

« Una mattina Una matti »

=

9

+

20

=

29

≡

3 mod(26)

=

D

Et ainsi de suite. On retrouve le message chiffré : « D ni bltjcr mia ctegx »

Déchiffrement

Pour déchiffrer, on soustrait la clé au message chiffré. On utilise toujours la congruence, bien sûr.

« D ni bltjcr mia ctegx »

-

« Una mattina Una matti »

=

3

-

20

=

-17

≡

-17+26 mod(26)

≡

9 mod(26)

=

J

Et, de niveau, étape par étape, on retombe sur :

« J ai plaque mon chene »

Variantes

Le chiffre de Vigenère a connu de multiples variations. En voici quelques unes :

Le précurseur Bellaso

Avant Vigenère, il y avait eu Bellaso. Mais le pauvre homme s’est fait piqué la vedette par un autre italien, plus connu à son époque, Giovanni Della Porta, puis par Vigenère. Bref, du coup on parle du chiffre de Porta/Bellaso.

Pour ce chiffre, il faut une table que voici :

Dans la colonne de gauche se trouve la lettre de la clé, et dans la colonne de droite se trouve la substitution.

Un petit exemple pour vous montrer comment ça fonctionne :

Chiffrement

Prenons le message suivant : « Trois Anneaux pour les Rois Elfes » (extrait du « Seigneur des anneaux » de Tolkien)

Avec la clé suivante : « La République Galactique » (extrait de « Starwars » de Lucas)

La première lettre de la clé est « L ».

On cherche dans la première colonne et cette lettre (« L »)est dans la sixième ligne avec « K ».

La première lettre du message est « T ». On cherche donc la lettre « T » dans la deuxième colonne à la sixième ligne.

On voit que « T » se trouve en dessous de « L » (dans les deux lignes présentes dans chaque ligne de la deuxième colonne), donc la lettre chiffrée est « L ».

On passe à la deuxième lettre de la clé (pour être sûr que vous suivez). C’est la lettre « a ».

Elle se situe à la première ligne dans la première colonne. La deuxième lettre du message en clair est « r ».

Dans la deuxième colonne de la première ligne, « r » est en dessous de « e », donc la lettre chiffrée est « e ».

Ensuite :

« R » : 9ème ligne : « o » devient « j »,

« e » : 3ème ligne : « i » devient « t » (« i » est au dessus de « t »),

etc.

Le message chiffré est donc :

« Lejtm qafnsem fbme xvb ijyh zyxpm »

Déchiffrement

Vous reprenez la clé, vous retrouvez la ligne et faites la correspondance. Donc :

Avec la clé : « La République Galactique »

Et le message chiffré : « Lejtm qafnsem fbme xvb ijyh zyxpm »

« L » : 6ème ligne : « L » devient « T »,

« a » : première ligne : « e » devient « r »,

etc.

On retombe sur le message : « Trois Anneaux pour les Rois Elfes »

Beaufort

On passe rapidement sur cette variante et la suivante. La seule différence avec Vigenère est qu’au lieu d’additionner la clé au message pour chiffrer, on soustrait le message à la clé.

Donc pour déchiffrer, on soustrait le message chiffré à la clé :

Clé – Message = Chiffré => Message = Clé – Chiffré

Bien sûr, c’est selon la représentation par congruence.

Variante allemande de Beaufort

Pour cette variante, c’est le contraire. On soustrait la clé au message pour chiffrer.

Et pour déchiffrer, on additionne le message chiffré à la clé :

Message – Clé = Chiffré => Message = Clé + Chiffré

Alphabet désordonné

On peut s’amuser à mettre les lettres de l’alphabet dans le désordre. Si les deux correspondants ont bien la même table, le système fonctionne.

Bien sûr, il faut qu’il n’y ait qu’une seule fois chaque lettre par colonne et par ligne.

Il faut aussi que toutes les lettres soient présentes dans toutes les colonnes et toutes les lignes.

Par exemple, on peut considérer ces valeurs :

C=0, E=1, A=2, Z=3, B=4, D=5, F=6, G=7, H=8, I=9, J=10, K=11, L=12, M=13, N=14, O=15, P=16, Q=17, R=18, S=19, U=20, T=21, V=22, W=23, X=24, Y=25

Alphabet agrandi ou différent

On a travaillé sur un alphabet latin de 26 lettres mais rien n’interdit de l’agrandir pour inclure des signes supplémentaires voire d’utiliser un autre alphabet.

Par exemple :

A=0, B=1, C=2, D=3, E=4, F=5, G=6, H=7, I=8, J=9, K=10, L=11, M=12, N=13, O=14, P=15, Q=16, R=17, S=18, T=19, U=20, V=21, W=22, X=23, Y=24, Z=25,!=26,?=27

Dans ce cas, on a un modulo 28 et non 26.

Variantes de Bellaso

On a utilisé la table originale de Bellaso mais rien n’interdit de la transformer.

On peut très bien avoir trois lettres dans la première colonne au lieu de deux et réduire le nombre de lignes en conséquence.

Ou avoir un nombre de lettres différentes par ligne.

Ou changer les substitutions d’alphabet dans la deuxième colonne.

La seule chose que cette table impose est que le nombre de lettres/signes de votre alphabet soit pair pour que chaque signe ait une correspondance dans la deuxième colonne.

Faiblesses

Attaque par analyse de fréquences

Comme rappelé au préambule historique, ce chiffre, ainsi que ses variantes, a été cassé au 19ème siècle.

Il souffre de la même faiblesse, même s’il est beaucoup plus résistant, que le chiffre de César.

Les langues n’utilisent pas les mêmes lettres avec les mêmes fréquences. Par exemple, en français, la lettre « e » est beaucoup plus utilisée que les autres.

Un attaquant peut se servir de cette différence de fréquences pour deviner le message ou la clé.

Mais contrairement au chiffre de César, il y a une étape préalable.

L’attaquant doit, d’abord, chercher à deviner la longueur de la clé. Cela lui permet de définir des segments de longueur égale dans le message chiffré.

Pour ça, il recherche des motifs dans le message chiffré. C’est à dire des groupes de trois lettres ou plus qui sont présents de manière régulière dans le message chiffré.

En effet, les langues ont aussi des motifs qui reviennent souvent : « les » apparaît souvent en français, par exemple.

La probabilité est plus forte que le même bout de la clé tombe sur un même motif du message en clair et donc chiffre de la même façon, qu’un simple phénomène aléatoire.

En repérant ces motifs, l’attaquant estime donc la taille de la clé et peut segmenter le message chiffré.

Chaque lettre du message en clair, dans le segment, étant chiffré par la même lettre de la clé, on peut revenir à l’étude de fréquences des lettres.

Cela vous semble obscur, incompréhensible. Pas de panique, un prochain article éclaircira tout ça avec des exemples.

Le chiffre de Vigenère est à mi-chemin entre le chiffre de César, dont il tire la règle de substitution, et le masque jetable, qui est l’algorithme parfait, qui n’apparaîtra qu’au début du 20ème siècle.

Énigme de Cryptotrucs

Le Carré de Polybe est 6x6.

La clé est : « les framboises savent »

Le message chiffré est : « 12 11 11 12 33 12 42 16 42 24 11 11 23 31 16 44 26 12 32 15 23 43 44 12 31 31 12 »