Drapeau vert : Cet article ne demande aucune connaissance mathématique particulière

Comment communiquer sans être lu par des indésirables ? Cette question est à la base de ce que l’on appelle la cryptographie, destinée à protéger vos messages des regards indiscrets. Son principe est simple : remplacer le message, l’information d’origine, par un nouveau message dit chiffré que seul votre destinataire devrait être en mesure de décoder.

Tout ceci semble simple sur le papier, et pourtant… Une technique trop simple rend vulnérable votre message, alors qu’un procédé trop compliqué rend difficile sa traduction par votre correspondant.

Note : dans la suite de l’article, j’utiliserai parfois le mot « coder » ou le mot « chiffrer ». Sachez qu’ici, ils désignent la même chose, alors ne soyez pas perturbés !

Le chiffre de César

La première chose qui vient à l’esprit lorsque l’on parle de coder un message sera peut-être de tout bêtement remplacer une lettre par une autre. C’est d’ailleurs sur cette idée que se base le chiffre dit de César.

Prenons un message en clair, par exemple : « Les Mathématiques, c’est fantastique ».

Dans un premier temps, nous allons supprimer les espaces et la ponctuation. Après tout, ce sont là des signes bien trop distinctifs pour être conservé, et nous souhaitons un minimum protéger notre message. Nous souhaitons donc envoyer à notre correspondant le message : LESMATHEMATIQUESCESTFANTASTIQUE.

Le chiffrage par Code César consiste simplement à décaler toutes les lettres de cette phrase d’un certain nombre de crans fixé à l’avance. Par exemple, en décalant les lettres de trois crans, le L devient un O, le E devient un H et ainsi de suite… Si l’on doit coder la lettre Z, il suffit de reprendre au début de l’alphabet : Z -> A -> B -> C. Le Z devient donc un C.

Notre phrasé codée est donc OHVPDWKHPDWLTXHVFHVWIDQWDVWLTXH. Pour le déchiffrer, rien de plus simple : il suffit de faire l’opération inverse, c’est-à-dire de prendre, pour chaque lettre, celle qui vient trois crans avant.

Vous l’aurez sans doute compris : ce codage est trop simple ! Même sans connaître le décalage, il n’existe que 25 possibilités à tester, une broutille. Nous pourrions imaginer corser l’affaire en n’utilisant pas l’alphabet classique ABCD… mais plutôt un autre alphabet, par exemple l’ordre d’apparition des lettres sur un clavier AZERTY. En décalant de trois lettres vers la droite, le A devient R, le Z devient T, le E devient Y et ainsi de suite.

L’ennui, c’est qu’une lettre est toujours codée de la même manière. Pour déchiffrer le code, il suffit alors de regarder les fréquences d’apparition de chaque lettre, et de les analyser. En effet, en Français, la lettre la plus courante dans un texte est la lettre « E ». Il y a donc de fortes chances que la lettre qui apparaisse le plus souvent dans un texte codé de la sorte corresponde à la lettre qui code le E du message de départ.

S’il s’agit d’un code de César classique, alors le décalage est trouvé, nous pouvons retrouver le message d’origine sans peine. Regardons le message codé suivant :

DORUVTXLOUHJDUGDLWVRQHQIDQWVDPXVHUDHPSLOHUGHVFXEHVOHPDW
KHPDWLFLHQGXGOHBODQJIRUGVHSULWDREVHUYHUSOXVHQGHWDLOVODW
RXUDLQVLIRUPHHFRPSRVHHGHWURLVSDLUHVGHFXEHVGHFRXOHXUVGLIIH
UHQWHVGLVRQVMDXQHURXJHHWEOHXFHOOHFLSUHVHQWDLWXQHSURSUL
HWHTXLOWURXYDHWRQQDQWHHQWUHOHVGHXAFXEHVMDXQHVVHWURXY
DLWXQFXEHHQWUHOHVGHXAURXJHVVHQWURXYDLHQWGHXAHWHQWUHO
HVGHXAEOHXVVHQWURXYDLHQWWURLV

Comptons maintenant le nombre d’apparitions de chacune des lettres dans ce message codé.

Comptage des lettres dans le message codé. La lettre k apparaît le plus souvent.

La lettre « K » est la plus fréquente : il y a de fortes chances que ce soit le codage de la lettre « E ». Pour passer du « E » au « K », il y a un décalage de 5 lettres. Il est alors possible de décoder le message, qui se trouve être le début du précédent article sur le problème de Langford.

Si l’alphabet utilisé est un peu plus complexe, il faut fournir davantage de travail. Par exemple, une fois ce E trouvé, on peut également regarder autour. Le E est souvent associé au N, il se peut que les lettres autour du E codent donc le N du message clair, et ainsi de suite. Bref, il faut compliquer notre méthode.

Le carré de Vigenère

L’idée du chiffrage de Vigenère est d’utiliser plusieurs décalages différents, selon la position de la lettre dans le message. Nous allons pour cela avoir recours à une clé -c’est-à-dire un mot qui nous servira à chiffrer et à déchiffrer notre message – et à un tableau.

Pour la clé, prenons par exemple le mot « AUTOMATHS ». Nous allons écrire le message à coder et la clé l’un au-dessus de l’autre. Evidemment, la clé n’est pas aussi longue que le message, alors nous allons la répéter jusqu’au bout, ce qui donne ceci :

Pour chiffrer le message, il suffit alors de décaler la lettre du message clair d’un nombre de cran qui dépend de la lettre de la clé correspondante, auquel on retire 1.

• Par exemple, la première lettre du message clair est L, celle de la clé est A, qui est la 1ère lettre de l’alphabet. Je décale donc le L de (1-1) = 0 ce qui me donne toujours la lettre L.
• Pour la suivante, E, la lettre de la clé est U, qui est la 21ème lettre de l’alphabet : je décale donc le E de 21 – 1 = 20 crans, ce qui me donne un Y, et ainsi de suite.

En codant le même message que tout à l’heure, nous obtenons :

AFHFEQNPDRYZODDTPLSIGSZFTULSUFIEEKHWMJBZQRW

LKCOUSELXTSTBXAMTBJAEHWIPLXFDAHZTARWZWPLBH
MOUZWRPXFBLNZWNXXHMIEZDANHIDABUKIZHFYEXJG
MJHGQEWLLRIBGBABYWSXXQGBXZVEWHIXENYKDCYTQR
XULEMWWEOGZBAOGSDONNWENUZQUVLDLYVWBRXZW
NNTWFUGLHRIIFUEMLIUCEHDONCSENHBZAGAWEHMFQ
LXZVEOQQGBXZBAOGSESXAJOOOOUTNUUUVXSZTKLDEM
WSGXKVMGYLGQNMYGUPTWQNMKWURXHQNMYWLYLR
QUQIDEOLGQNMYGUPTWQNMAJOCL

Le procédé peut ainsi être résumé en un tableau à double entrée : une pour la lettre du message à chiffrer, l’autre pour celle de la clé.

La lettre M du message en clair est codée par la lettre O de la clé. La lettre du message codé sera donc le A.

Encore une fois, il est possible d’utiliser un autre alphabet que celui d’origine, ou une autre règle pour la conversion. Le message sera vraisemblablement plus compliqué à décoder : nous pouvons le voir en regardant de nouveau les fréquences d’apparition des lettres dans le message codé ; aucune ne semble beaucoup plus importante que les autres.

Fréquence d’apparition des lettres dans un message codé par le chiffre de Vigenère.

Pour décoder le message, il suffit alors de mettre le message codé et la clé l’un en-dessous de l’autre. Pour chaque lettre de la clé, on cherche alors la lettre du message codé, puis on remonte la colonne pour trouver la lettre du message clair.

Par exemple, si mon message codé présente un « S » codé avec la clé « K », je regarde où se situe le « S » sur la ligne du « K » dans mon tableau : cela correspond à la colonne du I.

Cette méthode est-elle pour autant infaillible ? Pas vraiment…

Ici, notre clé a 9 lettres, ce qui signifie que toutes les 9 lettres, nous utiliserons la même lettre en guise de clé. Autrement dit, dans ce cas, le chiffre de Vigenère n’est rien d’autre que 9 codes César mis côte à côte. Il est donc possible de les casser 1 par 1 pour tout décoder.

Trouver la clé

Pour autant, en règle générale, la clé est inconnue, et il n’est donc pas possible de savoir combien de décalages différents ont été utilisés pour coder le message. Il serait envisageable de toutes les tenter, de regarder si l’on arrive à quelque chose qui a du sens, mais nous sommes plus malins, n’est-ce pas ?

Rappelons donc le message que nous devons décoder :

AFHFEQNPDRYZODDTPLSIGSZFTULSUFIEEKHWMJBZQRWLKCOUSELXTSTBXAM
TBJAEHWIPLXFDAHZTARWZWPLBHMOUZWRPXFBLNZWNXXHMIEZDANHIDABU
KIZHFYEXJGMJHGQEWLLRIBGBABYWSXXQGBXZVEWHIXENYKDCYTQRXULEM
WWEOGZBAOGSDONNWENUZQUVLDLYVWBRXZWNNTWFUGLHRIIFUEMLIUCEH
DONCSENHBZAGAWEHMFQLXZVEOQQGBXZBAOGSESXAJOOOOUTNUUUVXSZ
TLDEMWSGXKVMGYLGQNMYGUPTWQNMKWURXHQNMYWLYLRQUQIDEOLGQN
MYGUPTWQNMAJOCL

Dans ce message codé, il est possible de déceler certaines suites de trois lettres – ou trigrammes – qui reviennent à différentes positions. Il y a alors deux possibilités :

• soit il y avait deux trigrammes identiques dans le texte d’origine qui ont tous deux été codé par la même partie de la clé, aboutissant à deux trigrammes encore identiques dans le message codé.
• soit deux trigrammes différents du message clair ont abouti par un heureux hasard à deux trigrammes identiques dans le message codé.

La probabilité de cette seconde possibilité est très faible, alors nous pouvons supposer que nous sommes dans le premier cas. En relevant alors les positions des trigrammes répétés, nous avons :

• XZV aux positions 152 et 251
• YGU aux positions 306 et 342

L’écart entre les deux répétitions des trigrammes est donc respectivement de 99 et 36. Or, nous avons supposé que les deux XZV étaient issus du même morceau de clé, ce qui signifie que 99 est forcément un multiple de la longueur de notre clé. C’est la même chose pour 36.

Ainsi, la longueur de notre clé est vraisemblablement un diviseur commun à 99 et à 36, ce qui ne laisse que peu de possibilités : 1, 3 ou 9. Et en l’occurrence, la longueur de la clé AUTOMATHS est de 9. Bingo, il ne reste plus qu’à décoder le tout !

Plus de complexité…

Le chiffre de Vigenère a résisté pendant près de trois siècles avant d’être enfin brisé mais est désormais facilement mis en défaut à cause de ces répétitions de la clé. Aussi, pour renforcer la sécurité, il faut utiliser une clé toujours plus longue, quitte à ce que celle-ci fasse la longueur du texte. Seulement, comment transmettre cette clé maintenant ?

C’est ici qu’intervient l’astucieux chiffrement autoclave : dans ce procédé, le message en clair fait lui-même partie de la clé !

Plus précisément, il existe bien un mot-clé, comme pour le chiffre de Vigenère, et nous choisirons toujours AUTOMATHS ici. Seulement, plutôt que de répéter cette clé à l’infini, il suffit, une fois la clé terminée, d’utiliser le message clair.

Une fois la clé placée, on répète le message lui-même : celui-ci fera office de clé pour la suite.

Pour chiffrer, on utilise alors le tableau de Vigenère. Pour décoder maintenant, on déchiffre les premières lettres grâce à la clé, puis on peut alors déchiffrer la suite grâce à ces premières lettres décodées et ainsi de suite.

Ici, plus de répétition, la méthode est robuste et tient le coup. Le seul souci, c’est qu’une seule erreur dans la transmission du message le rend impossible à déchiffrer. Attention à ne pas se tromper.

Naturellement, ce code n’est pas infaillible : le nombre de clés possibles n’est pas si élevée, mais il n’existe aucune autre astuce que de toutes les tester – hormis essayer les plus probables, mais vous ne feriez pas ça n’est-ce pas ?

Pour compléter

• Le site Dcode vous permet de chiffrer et déchiffrer le message de votre choix avec la méthode que vous préférez
• Un site sur le chiffre de Vigenère qui contient un mémoire assez complet sur la question