Analyse fréquentielle

L'analyse fréquentielle ou analyse de fréquence est un procédé de décompte du nombre de lettres qui se base sur le fait que les lettres ont une fréquence d'apparition qui varie et qui est propre à chaque langue. En cryptanalyse, l'analyse fréquentielle est utilisée pour déchiffrer un chiffrement par substitution.

Il est possible de reproduire les calculs de fréquence détaillés dans cet article en utilisant cet outil d'analyse fréquentielle que j'ai dévéloppé et mis en ligne.

Fréquences d'apparition des lettres

Pour illustrer le concept de fréquence d'apparition de lettres, prenons le poème L'amour du mensonge de Baudelaire :

Quand je te vois passer, ô ma chère indolente,
Au chant des instruments qui se brise au plafond
Suspendant ton allure harmonieuse et lente,
Et promenant l'ennui de ton regard profond ;

Quand je contemple, aux feux du gaz qui le colore,
Ton front pâle, embelli par un morbide attrait,
Où les torches du soir allument une aurore,
Et tes yeux attirants comme ceux d'un portrait,

Je me dis : Qu'elle est belle ! et bizarrement fraîche !
Le souvenir massif, royale et lourde tour,
La couronne, et son coeur, meurtri comme une pêche,
Est mûr, comme son corps, pour le savant amour.

Es-tu le fruit d'automne aux saveurs souveraines ?
Es-tu vase funèbre attendant quelques pleurs,
Parfum qui fait rêver aux oasis lointaines,
Oreiller caressant, ou corbeille de fleurs ?

Je sais qu'il est des yeux, des plus mélancoliques
Qui ne recèlent point de secrets précieux ;
Beaux écrins sans joyaux, médaillons sans reliques,
Plus vides, plus profonds que vous-mêmes, ô Cieux !

Mais ne suffit-il pas que tu sois l'apparence,
Pour réjouir un coeur qui fuit la vérité ?
Qu'importe ta bêtise ou ton indifférence ?
Masque ou décor, salut ! J'adore ta beauté.

Si l'on compte le nombre de fois que chaque lettre apparait dans le texte on obtient le tableau suivant :

On peut noter que certaines caractères comme le e, le u, le s, le r et le a constituent près de la moitié des lettres du texte. À l'inverse g, h, v, x, y et z représentent moins de 4% des lettres du texte et la lettre w n'apparait pas.

Cette fréquence d'apparition de certains caractères plutôt que d'autres est ce qui défini la base de l'analyse fréquentielle. Il est cependant important de noter qu'il n'y a pas de fréquence exacte d'apparition des lettres car la fréquence d'un texte varie en fonction d'un grand nombre de facteurs :

Un exemple classique est le roman La Disparition de Georges Perec qui a été écrit dans son intégralité sans utiliser la lettre e, alors même que celle-ci est la plus utilisée dans la langue française.

Analyse multi-caractères

De la même manière que chaque lettre a une fréquence d'apparition propre, chaque groupe de lettre en a également une. On parle ainsi de n-gramme pour désigner l'analyse de caractères par groupe de taille n {\textstyle n}.

Les fréquences d'apparition de ces groupes peuvent être utilisées pour trouver des récurrences dans des messages chiffrés.

Digrammes

Si l'on reprend le poème de Baudelaire précédent et qu'on analyse les digrammes présent en utilisant une fenêtre glissante (pour un texte ABCDE on aura AB, BC, CD et DE), sur les 212 digrammes présent, les 10 suivants représentent 17.4% des apparitions :

Digramme Compte Fréquence
es 25 2.81%
re 19 2.13%
le 19 2.13%
qu 17 1.91%
nt 17 1.91%
et 15 1.69%
ur 15 1.69%
on 15 1.69%
eu 14 1.57%
ou 14 1.57%

Coupler avec la fréquence des lettres, les digrammes peuvent permettre de déchiffrer automatiquement un texte chiffré par subsitution puisque si certaines lettres ont une fréquence d'apparition proche entre elles, les digrammes permettent de trancher entre quelle lettre utiliser puisque certains ont de forte chances d'apparaitre là où d'autre sont très rarement présent.

Par exemple si l'on a un extrait d'un texte chiffré qui vaut xy et que l'on sait que y représente un n en texte clair mais que l'on hésite pour la valeur de x entre un o ou un u, on peut déterminer que :

Le digramme a donc plus de chance d'être un on et l'on peut émettre l'hypothèse que le caractère chiffré x correspond à un o en texte clair.

Déterminer une fréquence standard

La question qui se pose pour pouvoir utiliser l'analyse fréquentielle à des fins de cryptographie est donc de savoir quelle fréquence d'apparition des lettres utiliser. Comme vu précédemment, la fréquence d'apparition des lettres dépend de nombreux facteurs et de fait il n'est pas possible d'en avoir une qui soit universelle.

Une pratique courante est d'utiliser une quantité de texte importante issue de différente sources et auteurs pour établir une fréquence la plus représentative possible. C'est notamment ce qu'à fait L'université de Toulouse en 2008 en mesurant la fréquence d'apparition des lettres de l'ensemble des articles en français de wikipédia.

Une autre solution est de constituer son propre corpus de texte et d'analyse la fréquence des caractères et des n-grammes présents. Ici nous allons utiliser les ouvrages suivant disponible au format texte sur le site du projet Gutenberg et sur Internet Archive :

Sur un total de 2 650 118 lettres différentes on a la répartition de fréquence suivante :

Trigramme Compte Fréquence
ait 23614 0.89%
ent 20315 0.77%
que 19210 0.72%
les 13841 0.52%
lle 12839 0.48%
ede 12171 0.46%
ais 12065 0.46%
tre 11287 0.43%
ant 10822 0.41%
ous 10797 0.41%
des 10371 0.39%
res 10344 0.39%

Exemple de déchiffrement par analyse de fréquence

Prenons le texte suivant :

GVRMEHZMEWLTMCHLKDKEHGVBZECVUVHITWWEAVHKMJBKEPPTMJGVHBZVUEAHLVAWCKEHKBZKCPVCTEKMBKIKCVWDVCWLVGVUKAGKEGVHWKCWEAVHGVIVMCCVVWGMLKUITAYMEOMWKUTEWEVOCTEGIEVAZVMCVMJLKPPTANVKEPVHLKUIVHHTMHPKWKIPVDVCWVLVBTAWVURPKEPVHHMLVWHWCVHAKEOHGVPKWKREHHVCEVVWBVOMWKGTCKIPVYMKAGPKOEPPVKMJWVWTAHVATCUVHKMJQVMJDEOHBVPPVPKBVAVHWRKHMAIKEHVCYMEPVRVMCVCEVMHVUKRRTCWKGVHWKCWEAVHGVIVMCCVGMLKUITAWEVGVGKAHMARPKWBTPTCEVGMLKUITACTHVVWIPKABRKCOMUVGMAVNTMHHVGKEPVWUVURPEWPKBZTRVEUUVAHVKDVBHKUTMHHVYMVGTCKEWMACKQTAGVHTPVEPKCCEVCV

Si l'on regarde son indice de coïncidence on peut voir que celui-ci vaut 0.0721, ce qui est très proche de celui du Français (0.0778). On peut donc déduire que ce texte est donc très probablement chiffré par substitution mono-alphabétique.

Si on effectue son analyse fréquentielle on obtient le tableau suivant :

Pour les digrammes principaux on a :

Pour les trigrammes on a :

Dans un premier temps les éléments suivants peuvent être déduit de ces résultats :

Si l'on applique ces déductions au texte on obtient :

DERMISZMIWLTMCSLADAISDEBZICEUESITWWIAESAMJBAIPPTMJDESBZEUIASLEAWCAISABZACPECTIAMBAIACEWDECWLEDEUAADAIDESWACWIAESDEIEMCCEEWDMLAUITAYMIOMWAUTIWIEOCTIDIIEAZEMCEMJLAPPTANEAIPESLAUIESSTMSPAWAIPEDECWELEBTAWEURPAIPESSMLEWSWCESAAIOSDEPAWARISSECIEEWBEOMWADTCAIPEYMAADPAOIPPEAMJWEWTASEATCUESAMJQEMJDIOSBEPPEPABEAESWRASMAIAISECYMIPEREMCECIEMSEUARRTCWADESWACWIAESDEIEMCCEDMLAUITAWIEDEDAASMARPAWBTPTCIEDMLAUITACTSEEWIPAABRACOMUEDMAENTMSSEDAIPEWUEURPIWPABZTREIUUEASEADEBSAUTMSSEYMEDTCAIWMACAQTADESTPEIPACCIECE

Si l'on regarde la fin de ce texte, on peut voir que l'on a l'enchainement de lettre suivant : E_E. En français la plupart des lettres encadrées par des E sont T, R et S. La lettres S ayant déjà été identifiée, si l'on essaye de remplacer la lettre C par R, on obtient :

DERMISZMIWLTMRSLADAISDEBZIREUESITWWIAESAMJBAIPPTMJDESBZEUIASLEAWRAISABZARPERTIAMBAIAREWDERWLEDEUAADAIDESWARWIAESDEIEMRREEWDMLAUITAYMIOMWAUTIWIEORTIDIIEAZEMREMJLAPPTANEAIPESLAUIESSTMSPAWAIPEDERWELEBTAWEURPAIPESSMLEWSWRESAAIOSDEPAWARISSERIEEWBEOMWADTRAIPEYMAADPAOIPPEAMJWEWTASEATRUESAMJQEMJDIOSBEPPEPABEAESWRASMAIAISERYMIPEREMRERIEMSEUARRTRWADESWARWIAESDEIEMRREDMLAUITAWIEDEDAASMARPAWBTPTRIEDMLAUITARTSEEWIPAABRAROMUEDMAENTMSSEDAIPEWUEURPIWPABZTREIUUEASEADEBSAUTMSSEYMEDTRAIWMARAQTADESTPEIPARRIERE

On peut voir que les dernières lettres du texte forme un mot correcte ; ARRIERE, nos suppositions étaient donc probablement correctes.

On peut ensuite voir qu'il y a plusieurs digrammes de la lettre P à plusieurs endroits dans le texte. En supposant que ces lettres ne soient pas collées entre elles suite à la suppression des espaces du texte d'origine on peut en déduire que c'est probablement un L (les digrammes composées de la même lettre les plus fréquents étant de loin SS , EE et LL et on a déjà les lettres S et E)

On obtient alors :

DERMISZMIWLTMRSLADAISDEBZIREUESITWWIAESAMJBAILLTMJDESBZEUIASLEAWRAISABZARLERTIAMBAIAREWDERWLEDEUAADAIDESWARWIAESDEIEMRREEWDMLAUITAYMIOMWAUTIWIEORTIDIIEAZEMREMJLALLTANEAILESLAUIESSTMSLAWAILEDERWELEBTAWEURLAILESSMLEWSWRESAAIOSDELAWARISSERIEEWBEOMWADTRAILEYMAADLAOILLEAMJWEWTASEATRUESAMJQEMJDIOSBELLELABEAESWRASMAIAISERYMILEREMRERIEMSEUARRTRWADESWARWIAESDEIEMRREDMLAUITAWIEDEDAASMARLAWBTLTRIEDMLAUITARTSEEWILAABRAROMUEDMAENTMSSEDAILEWUEURLIWLABZTREIUUEASEADEBSAUTMSSEYMEDTRAIWMARAQTADESTLEILARRIERE

Le texte est assez déchiffré pour pouvoir trouver des candidats uniques pour les lettres restantes :

DEPUISHUITJOURSJAVAISDECHIREMESBOTTINESAUJCAILLOUJDESCHEMINSJENTRAISACHARLEROIAUCABARETVERTJEDEMANDAIDESTARTINESDEBEURREETDUJAMBONQUIFUTAMOITIEFROIDBIENHEUREUJJALLONGEAILESJAMBESSOUSLATABLEVERTEJECONTEMPLAILESSUJETSTRESNAIFSDELATAPISSERIEETCEFUTADORABLEQUANDLAFILLEAUJTETONSENORMESAUJYEUJVIFSCELLELACENESTPASUNBAISERQUILEPEURERIEUSEMAPPORTADESTARTINESDEBEURREDUJAMBONTIEDEDANSUNPLATCOLORIEDUJAMBONROSEETBLANCPARFUMEDUNEGOUSSEDAILETMEMPLITLACHOPEIMMENSEAVECSAMOUSSEQUEDORAITUNRAYONDESOLEILARRIERE

En rajoutant les espaces, accent et la ponctuation manquantes on retrouve le poème Au Cabaret Vert d'Arthur Rimbaud :

Depuis huit jours, j'avais déchiré mes bottines
Aux cailloux des chemins. J'entrais à Charleroi.
- Au Cabaret-Vert : je demandai des tartines
De beurre et du jambon qui fût à moitié froid.

Bienheureux, j'allongeai les jambes sous la table
Verte : je contemplai les sujets très naïfs
De la tapisserie. - Et ce fut adorable,
Quand la fille aux tétons énormes, aux yeux vifs,

- Celle-là, ce n'est pas un baiser qui l'épeure ! -
Rieuse, m'apporta des tartines de beurre,
Du jambon tiède, dans un plat colorié,

Du jambon rose et blanc parfumé d'une gousse
D'ail, - et m'emplit la chope immense, avec sa mousse
Que dorait un rayon de soleil arriéré.

Conclusion

Comme vu ci-dessus, l'analyse fréquentielle peut permettre de déchiffrer n'importe quel texte chiffré par substitution mono-alphabétique dès lors que celui-ci est suffisament long. Aujourd'hui ce type de chiffrement n'est de fait plus sécurisé et l'on préfèrera utiliser des algorithmes comme AES.