Présentation

L’histoire du chiffrement des textes ne date pas d’aujourd’hui, puisque des recherches indiquent que 2000 ans avant J.C, les égyptiens ont employé des hiéroglyphes non conformes à la langue sur les pierres tombales, afin de masquer l’identité des morts. Au début, le cryptage et la cryptanalyse n’étaient l’affaire que des militaires, mais aujourd’hui, c’est devenu également le problème des banques, des informaticiens et on peut dire de pratiquement tout le monde, surtout avec le développement d’internet et tous ce qu’il engendre en termes de la protection de la vie privée.

Chiffrement Simple par décalage

Le but de cet exercice est de décrypter une phrase cryptée avec un chiffrement de César.
Ce chiffrement consiste à opérer un décalage sur les lettres de l’alphabet selon un pas donné. Pour un pas 2 on trouve par exemple : a ==> c et  w ==> y.
On crée alors une fonction (Dans un langage de programmation approprié) qui permet de faire toutes les permutations possibles.
Après avoir lancé toutes les permutations possibles, on retrouve la phase décryptée à partir de la phrase initialement cryptée.

Phrase cryptée : LD L CFWP, XPY HZCCJ XZCP LMZFE HSLE ESPJ NLYYZE DPP ESLY LMZFE HSLE ESPJ NLY. UFWTFD NLPDLC

Phrase décryptée: AS A RULE, MEN WORRY MORE ABOUT WHAT THEY CANNOT SEE THAN ABOUT WHAT THEY CAN. JULIUS CAESAR

Remarque : La méthode est assez simple puisque le nombre de cas à tester est petit (25 façons de chiffrer), on choisit ainsi le chiffrement qui donne un sens à la phrase (citation).

Chiffrement par permutation

Une méthode de chiffrement plus solide consiste à appliquer une permutation sur les lettres de l’alphabet. Avoir la clef du code c’est donc connaitre la permutation qui a été utilisée.
Afin de trouver toutes les permutations possibles on a besoin de 26! permutations. D’où l’impossibilité d’utiliser l’approche citée dans la partie précédente. Pour pallier ce problème, on simule des permutations avec des algorithmes de Monte Carlo et des chaînes de Markov (l’algorithme de Metropolis Hastings).

Pour implémenter cette méthode, nous avons besoin d’un texte assez long qui nous servira de base d’apprentissage. On s’intéresse aux fréquences d’apparition d’une lettre après une autre en calculant la matrice des fréquences d’apparition d’un symbole après l’autre (alphabet + espace). On essaie, avec ce calcul, d’avoir une matrice représentative de la langue de l’apparition d’un symbole après un autre.

Nous définissons après la vraisemblance d’un texte ‘w’, formé par la succession des caractère xi, comme suit :

L(w)=Π?(??,??+1) , avec ‘A’ la matrice des fréquences d’apparition.

D’après l’écriture de cette vraisemblance, on peut déduire que plus un texte a une grande vraisemblance, plus il a de chance d’être un texte correct dans la langue en question. Donc notre objectif pour le décryptage serait de maximiser cette vraisemblance.

L’idée générale de l’algorithme et de partir d’une permutation aléatoire représentant l’état X0 pour la chaîne de Markov, et de simuler dans chaque itération une nouvelle permutation aléatoire,  et de l’accepter si elle permet d’améliorer la vraisemblance du texte traduit.

Après un certain nombre d’itérations, la vraisemblance devient stationnaire et maximale, car on n’accepte plus les nouvelles permutations. Ainsi, le chiffrement du texte est celui relatif à la dernière permutation acceptée par l’algorithme.

A noter que d’autres paramètres peuvent être ajoutés dans l’algorithme pour gagner en efficacité.

Conclusion

Les résultats obtenus nous montrent l’efficacité de l’utilisation des chaînes de Markov.
En effet, le décryptage par simulation donne le bon résultat après un nombre optimal d’itérations aux alentours de 3000 (Pour un texte d’environ ).