Supposons que W remplace un E:

Ce texte est trop court pour pouvoir en déduire quoi quelque chose de fiable sur les statistiques d'apparition des autres lettres. Mais si on connaît le contexte du message, on peut savoir par exemple qu'il contient avec une grande probabilité le mot DEFCON. Il n'y a que deux endroits où ce mot peut apparaître, si on ne s'est pas trompés sur les positions des E. Testons le premier emplacement: XEATUI correspond à DEFCON, donc X = D, A = F, T =C, U = O, et I = N. On obtient alors:

Le premier mot semble être LE. Le CE pourrait être le début de C'EST. Victoire ! On en déduit:

Si on n'avait pas su que le message contenait DEFCON, il aurait fallu faire des hypothèses sur des correspondances entre lettres, voir si ca menait à quelque chose, changer ses hypothèses, et ainsi de suite & Ou bien, vu la faible longueur du message, on aurait pu tester toutes les possibilités par informatique. On voit déjà l'intérêt d'exploiter la puissance des ordinateurs pour casser les codes utilisés facilement par des humains.

Du point de vue du chiffrement, pour ne pas avoir à retenir les 26 correspondances entre lettres, on peut utiliser l'algorithme de décalage vu au dessus, il suffit alors de retenir un nombre c entre 1 et 25 (la clé) pour connaître le moyen de déchiffrer le message. En appelant p la position de la lettre en clair dans l'alphabet, et k la position de la lettre cryptée qui y est associée, on passe alors de l'une à l'autre par la formule:

n est un nombre entier (0 ou 1 dans ce cas) choisi pour que k reste compris entre 1 et 26. Ca permet de boucler sur le début de l'alphabet. Par exemple, pour un décalage de trois caractères (c=3), la lettre W (p=23) se transforme en Z (k=26). Or p + c = 23 + 3 = 26, ca marche donc bien pour n=0. Par contre, la lettre Y (p=25) se transforme en k = 25 + 3 = 28 ! On sort de l'alphabet, il faut donc faire n=1 ce qui nous donne k = 28 - 26 = 2, qui correspond à la lettre B.

Pour décrypter il faut réaliser l'inverse de l'opération précédente:

D'autres algorithmes sont possibles. Par exemple la multiplication, donnée par:

Son inverse est:

La clé de déchiffrement d est connu à partir de la clé de chiffrement c par la relation: c.d = 1 + 26n.

Petit défi: seules certaines valeurs de c, comprises entre 1 et 26, sont utilisables pour que cette méthode fonctionne, c'est-à-dire pour que le message puisse être déchiffré correctement. Lesquelles ?

On peut même combiner ces deux algorithmes, en les appliquant l'un après l'autre ! Pour décoder un tel message, il suffit d'utiliser les deux algos de déchiffrement l'un après l'autre, mais dans l'autre sens (si on a codé avec le décalage puis la multiplication, il faut décoder en commençant par la multiplication).

Pour casser un message codé, si vous avez réussi à trouver une ou deux correspondances entre lettres, vous pouvez en déduire les clés des algos de décalage ou de multiplication. Vous pouvez alors tester un déchiffrement en utilisant ces algorithmes avec la clé que vous avez trouvée, et voir si ca marche.

Prenons par exemple le message suivant:

vowydrkmuobkodonklybnedsvscozyebnocsqxobexzodsdqoxsonovkzbyqbkwwkdsyxyeex
lsnyesvvoebkcdemsoehmodobwokoxcesdoodobozbsczkbvocwonskcodvoqbkxnzelvsmzy
ebzkbvobnoczsbkdoccsxdbynesckxdsvvoqkvowoxdnkxcnoccicdowocsxpybwkdsaeocod
vocbocokehofsnowwoxdvoczsbkdoccyxddboccyefoxdnocrkmuobcodmyxxksccoxdvocci
cdowocaesvczoxodboxdcebvolyednocnysqdcvowydmbkmuobkodokvybcedsvscozyebzkb
vobnomodizonorkmukqboccspwkscsvcoroebdokexqbyczbylvowomodobwoohscdonotkvo
mbkmuocdvkbdnonozvywlobvocvyqsmsovcnovocnocckccowlvobzyeboxpksbockedobvoc
zbydomdsyxc

On lance un petit programme (voir plus bas) qui nous montre que la lettre qui apparaît le plus souvent est le O : 18,58 %. On peut donc penser qu'elle remplace E, et que s'il s'agit d'un algo de décalage, la clé utilisée est 10 (puisque si on décale la lettre E de 10 positions dans l'alphabet on trouve O).

Avec le programme, on essaie alors de décoder le message avec la clé 10, ce qui nous donne effectivement un message en clair:

lemothackeraetedabordutilisepourdesignerunpetitgeniedelaprogrammationouun
bidouilleurastucieuxcetermeaensuiteetereprisparlesmediasetlegrandpublicpo
urparlerdespiratessintroduisantillegalementdansdessystemesinformatiqueset
lesreseauxevidemmentlespiratessonttressouventdeshackersetconnaissentlessy
stemesquilspenetrentsurleboutdesdoigtslemotcrackeraetealorsutilisepourpar
lerdecetypedehackagressifmaisilseheurteaungrosproblemecetermeexistedejale
crackestlartdedeplomberleslogicielsdelesdessassemblerpourenfairesauterles
protections

Ordre d'apparition: E / ASITN / RULO / D / CMP / VQGFBH / JX / YZ

Ordre des digrammes: ES / RE / ON / DE / EN / NT / LE / ER / TE / SE / AN / TI / RA

Ordre des trigrammes: ENT / ION / TIO / ONS / RES / QUE / DES / EDE

En anglais:

 

E	T	O	A	N	I	R	S	H	D	L	C	F
13.05	9.02	8.21	7.81	7.28	6.77	6.64	6.46	5.85	4.11	3.60	2.93	2.88
U	M	P	Y	W	G	B	V	K	X	J	Q	Z
2.77	2.62	2.15	1.51	1.49	1.39	1.28	1.00	0.42	0.30	0.23	0.14	0.09

Ordre d'apparition: E / TA / ONISRH / LDCU / PFMW / YBGV / KQXJZ

Ordre des digrammes: TH / HE / AN / IN / ER / RE / ES / ON / EA / TI / AT / ST / EN / ND / OR

Ordre des trigrammes: THE / AND / THA / ENT / ION / TIO / FOR / NDE

LE PROGRAMME

Pour automatiser les taches de cryptage et décryptage, et surtout de cryptanalyse, j'ai écrit un programme en C. Il est assez bien commenté, donc je vous conseille de le lire et de regarder les commentaires pour mieux comprendre. Ce prog a été écrit sous linux avec emacs et compilé avec gcc (gcc -o crypto crypto.c; ./crypto), mais il marche aussi sous windows & co.

Il implémente (pour l'instant) des fonctions de cryptage et de décryptage par l'algorithme de décalage, une cryptanalyse par force brute de cet algo, un affichage des statistiques d'apparition des différentes lettres dans l'alphabet, et un test permettant de savoir si le texte fourni est clair ou crypté.

TEST DE SUCCES

Si on sait qu'un message a été encrypté par un certain algo, on peut tester toutes les clés possibles pour essayer de trouver celle qui le décryptera. C'est particulièrement vrai dans le cas des algorithmes vus au-dessus car il y a au maximum 25 possibilités à tester pour la clé, ce qui est très rapide.

Toute la subtilité est d'arriver à faire un test pour que l'ordinateur puisse savoir s'il a réussi à décrypter ou s'il faut essayer une autre clé. Chacun peut choisir sa propre méthode. Voici un moyen simple mais pas parfait (voir le programme) :

- d'abord, on calcule la fréquence d'apparition de chaque lettre (en pourcentage).

- pour chaque lettre, on fait la différence entre la fréquence observée et la fréquence théorique d'un texte français donnée par les tables. On élève tout ça au carré.

- on ajoute ensuite les valeurs trouvées pour chaque lettre.

Le résultat obtenu sera faible si le texte est clair, mais s'il est crypté il y aura de grandes différences entre les fréquences théoriques et les fréquences observées, et donc le résultat sera beaucoup plus grand. Pour l'exemple précédent voici ce que donne le programme:

Fichier en clair: indice = 0.227048

Fichier crypté avec la clé 10: indice = 8.433677

Bravo, decryptage reussi avec la cle 10 (indice = 0.227048)

CRYPTANALYSE DES TRANSPOSITIONS

Si l'analyse des fréquences montre que le texte est en clair, et que pourtant ce texte ne veut rien dire, c'est peut-être que des transpositions de lettres ont été effectuées avant ou après le cryptage. Le texte que nous obtenons est donc un anagramme du texte en clair, c'est-à-dire qu'il y a les mêmes lettres mais dans un ordre différent. Quels moyens permettent de retrouver la disposition initiale des lettres ?

On pourrait essayer de tester toutes les permutations des lettres. Si le message fait n lettres, il y a n! = n*(n-1)*(n-2)* & *3*2*1 possibilités, ce qui est vite trop gros pour notre pôvre PC dès que n est trop grand. Mais on peut imaginer de se limiter aux premières lettres, par exemple, en espérant que les transpositions ne mettent pas en jeu des lettres très espacées. Reprenons notre exemple simple du début, où on prenait une lettre sur deux. Les deux premières lettres du message se trouvent donc éloignées (après la transposition) d'un nombre égal à la moitié du nombre de lettres du message. Si on ne prend que le début du message pour tester les transpositions possibles, ca ne marchera donc pas puisqu'on ne prendra en compte que la moitié des lettres. Par contre, si la transposition utilisée consiste à échanger des groupes de lettres voisins, on pourra obtenir un résultat intéressant, puisqu'on pourra retrouver cette transposition avec notre programme.

On peut aussi tester un certains nombre de transpositions classiques. En particulier, il faut essayer la méthode constitant à ne prendre qu'une lettre sur deux (ou sur trois, ou sur quatre) en partant de la première lettre, puis de recommencer à partir de la seconde lettre, et des suivantes si nécessaire. Par exemple, si on fait prend les lettres trois par trois, le texte suivant :

devient:

Les messagers spartiates utilisaient déjà un système de ce genre 5 siècles avant Jésus-Christ !!! En fait ils enroulaient une longue et fine feuille (une sorte de bandelette) en spirale autour d'un baton, et écrivaient le message sur le baton dans le sens de la longueur. Ensuite ils déroulaient la feuille et remplissaient les blancs entre chaque lettre par des lettres quelconques. Le message ne pouvait alors être lu que par quelqu'un connaissant le truc et possédant un baton de largeur identique.

Si on informatise le décodage, il nous faut trouver un nouveau critère pour savoir si on a bien obtenu un message en clair, puisque l'analyse des fréquences ne marche plus. Heu & en fait si, elle peut marcher, mais pas sur les lettres seules, sur les groupes de plusieurs lettres. Il existe des tables donnant les fréquences d'apparition des "ll", "eu", "qw", & dans la langue française. Pareil pour les groupes de trois lettres: "ent", "ell", "zqw" & . Or, les transpositions détruisent l'association entre deux lettres qui se suivent, et changent donc les fréquences d'apparition de ces groupes. En théorie, le groupe "eee" pourrait alors apparaître plus souvent que le groupe "ent" ! En reprenant le programme d'analyse de fréquences pour lettres seules et en le modifiant pour tenir compte des fréquences des doubles et triples groupes de lettres, on peut réussir à savoir si le message obtenu est en clair ou non.

Il y a un autre critère possible, plus facile à mettre en oeuvre dans les messages courts (dans lesquels l'analyse des fréquences est peu fiable), et le seul possible dans le cas où des lettres inutiles sont rajoutées exprès et brouillent les fréquences (c'est le cas du système spartiate): on peut dire que le message obtenu est en clair si un certain mot y apparaît. D'où l'intérêt d'avoir une petite idée de ce que peut bien raconter ce message. Si on ne connait rien, on peut tout de même essayer de se rabattre sur certains mots très utilisés ("THE" en anglais par exemple), mais ça ressemble un peu à de l'analyse de fréquences en moins poussé.

PASSONS A LA VITESSE SUPERIEURE

Vous avez maintenant acquis des concepts de base sur la cryptographie et les méthodes de cryptanalyse. Dans le prochain manuel, nous allons développer notre programme pour qu'il gère de nouveaux algorithmes, plus efficaces, les substitutions polyalphabétiques. On étudiera en particulier le célèbre cryptage de Vigenère, et on implémentera dans le prog des méthodes pour le casser automatiquement. On commencera aussi à s'intéresser au cryptage de données quelconques, pas seulement d'un texte.

Il faudra patienter trois mois & En attendant, pourquoi ne pas essayer d'améliorer le prog pour implémenter les transpositions, et d'autres algorithmes de substitution monoalphabétiques ? Vous pouvez m'envoyer vos améliorations à fozzy@dmpfrance.com.

Voici enfin un petit challenge pour vous torturer les méninges:

ftvseyzvsqtesmyrvxeizrsemrvxgqlesmmwwpmilwdjzsimxwttevvsxgmlgemmtriiewym
gplceepypvierykrixeetwvlmespvpmytgemwrheirgxejhsidedycbc

Good luck ! ;)