Analyse fréquentielle

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L’analyse fréquentielle, ou analyse de fréquences, est une méthode de cryptanalyse dont la description la plus ancienne est réalisée par Al-Kindi au IXe siècle. Elle consiste à examiner la fréquence des lettres employées dans un message chiffré. Cette méthode est fréquemment utilisée pour décoder des messages chiffrés par substitution, dont un exemple très simple est le chiffre de César.

L'analyse fréquentielle est basée sur le fait que, dans chaque langue, certaines lettres ou combinaisons de lettres apparaissent avec une certaine fréquence. Par exemple, en français, le e est la lettre la plus utilisée, suivie du a et du s. Inversement, le w est peu utilisé.

Ces informations permettent aux cryptanalystes de faire des hypothèses sur le texte clair, à condition que l'algorithme de chiffrement conserve la répartition des fréquences, ce qui est le cas pour des substitutions mono-alphabétiques et poly-alphabétiques.

Une deuxième condition nécessaire pour appliquer cette technique est la longueur du message à décrypter (Cryptogramme). En effet, un texte trop court ne reflète pas obligatoirement la répartition générale des fréquences des lettres. De plus, si la clé est de la même longueur que le message, il ne pourra y avoir de répétition de lettre et l'analyse fréquentielle deviendra impossible.

Histoire[modifier | modifier le code]

Première page du Manuscrit sur le déchiffrement des messages cryptographiques d'Al-Kindi

Al-Kindi au IXe siècle fait la plus ancienne description de l’analyse fréquentielle, méthode de cryptanalyse probablement utilisée pour décrypter les documents administratifs et économiques de la dynastie abasside mais aussi pour reconstituer la chronologie des révélations du Coran[1].

Il expose les fondements de cette méthode de cryptanalyse dans son traité intitulé Manuscrit sur le déchiffrement des messages cryptographiques. Il montre qu'un message chiffré conserve la trace du message clair original en gardant les fréquences d'apparitions de certaines lettres.

Principe[modifier | modifier le code]

Fréquence d'Apparition[modifier | modifier le code]

On peut constater que selon la langue, un texte comportera une répartition particulière des fréquences de lettres. Par exemple en français, les lettres les plus fréquentes, c’est-à-dire les lettres que l'on retrouve le plus souvent, sont le E, suivi du A, du I et du S ... On obtient ainsi la répartition de fréquences des lettres suivante (en %) :


A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Français 9,42 1,02 2,64 3,39 15,87 0,95 1,04 0,77 8,41 0,89 0,00 5,34 3,24 7,15 5,14 2,86 1,06 6,46 7,90 7,26 6,24 2,15 0,00 0,30 0,24 0,32
Anglais 8,08 1,67 3,18 3,99 12,56 2,17 1,80 5,27 7,24 0,14 0,63 4,04 2,60 7,38 7,47 1,91 0,09 6,42 6,59 9,15 2,79 1,00 1,89 0,21 1,65 0,07

Ce qui nous donne l'ordre suivant.

E A I S T N R U L O D M P C V Q G B F J H Z X Y K W

Cette répartition des fréquences des lettres n'est qu'approximative[Note 1], cela dépend de nombreux paramètres tels que le niveau de langue du texte, ainsi que du style d'écriture (Par exemple un message militaire emploiera de nombreuses abréviations). On peut aussi analyser la fréquence des bigrammes dans un texte, c’est-à-dire la fréquence des groupes de deux lettres. Cela amènera des indices importants pour décrypter un texte chiffré car on sait que l'on ne pourra trouver des bigrammes tels que XK ou WX dans le texte clair.

Application au Jeu du Scrabble[modifier | modifier le code]

On peut remarquer que ces fréquences correspondent à peu de choses près aux distributions des lettres dans le jeu du Scrabble, celle-ci rapportant plus ou moins de points en fonction de leur fréquence d'utilisation. En effet, la répartition des lettres avec le nombre de points correspondant est la suivante :

A1 B3 C3 D2 E1 F4 G2 H4 I1 J8 K10 L1 M2 N1 O1 P3 Q8 R1 S1 T1 U1 V4 W10 X10 Y10 Z10
9 2 2 3 15 2 2 2 8 1 1 5 3 6 6 2 1 6 6 6 6 2 1 1 1 1

La répartition des lettres du premier exemplaire du jeu du Scrabble a d'ailleurs été faite par analyse statistique du New York Times.

Déchiffrement par analyse fréquentielle[modifier | modifier le code]

La répartition des fréquences obtenues peut être utilisée pour décrypter un message codé via un système de substitution. En effet, si on découvre une lettre très fréquente dans le message chiffré, il s'agira sans doute de la lettre E dans le message clair car c'est la lettre la plus courante en français. Nous pouvons ensuite en déduire les autres lettres en étudiant toutes les fréquences des lettres du message chiffré. Par exemple, considérons le message chiffré suivant :

  • segelazew aop qj lnkfap z ajyuyhklazea cnwpqepa aynepa ykklanwperaiajp

Il faut donc calculer les fréquences d'apparition de chacune des lettres du message chiffré afin de les comparer à la répartition normale des fréquences des lettres en français. On obtient la répartition des fréquences (en %) suivante pour ce message chiffré :

Lettres A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Total
Occurrences 12 0 1 0 7 1 1 1 1 3 4 4 0 4 1 7 2 1 1 0 1 0 3 0 4 3 62
Fréquences 19,4 0 1,6 0 11,3 1,6 1,6 1,6 1,6 4,8 6,5 6,5 0 6,5 1,6 11,3 3,2 1,6 1,6 0 1,6 0 4,8 0 6,5 4,8 100

Nous pouvons donc constater que c'est la lettre A qui est la plus fréquente dans le message chiffré. Celle-ci a donc de grande chance de représenter la lettre E dans le message clair, car c'est la lettre la plus courante en français. Le E et le P sont également fréquents dans le texte chiffré, ils représentent donc sûrement les lettres S ou A du texte clair. Ces suppositions nous amènent à retrouver une partie du texte non chiffré, ce qui va permettre de déduire à partir de ces quelques lettres une partie de la clé. Dans le cas d'un chiffre de substitution monoalphabétique, nous pouvons avoir affaire à un chiffrement de César, nous obtiendrons alors dans ce cas un décalage de 4 lettres puisque l'on a supposé A=E. Muni de cette clé, nous pouvons décrypter le reste du message, ce qui nous donne :

  • Wikipédia est un projet d'encyclopédie gratuite écrite coopérativement.

Ce message est cohérent, nos suppositions de départ étaient exactes.

L'analyse fréquentielle intervient également, combinée à d'autres méthodes, pour la cryptanalyse de chiffrements plus complexes. Par exemple l'analyse des chiffrements polyalphabétiques tels le chiffre de Vigenere, sont ramenés à celle d'un chiffrement par substitution, après une recherche de coïncidences dans le texte chiffré.

Implémentation en Python[modifier | modifier le code]

La source suivante effectue une analyse fréquentielle sur un cryptogramme chiffré via un système monoalphabétique.

from string import maketrans, ascii_uppercase
 
FR_Freq = {'A':9.2,'B':1.02,'C':2.64,'D':3.39,'E':15.87,'F':0.95,'G':1.04,'H':0.77,'I':8.41,
'J':0.89,'K':0.00,'L':5.34,'M':3.24,'N':7.15,'O':5.14,'P':2.86,'Q':1.06,'R':6.46,'S':7.90,
'T':7.26,'U':6.24,'V':2.15,'W':0.00,'X':0.30,'Y':0.24,'Z':0.32}
EN_Freq = {'A':8.08,'B':1.67,'C':3.18,'D':3.99,'E':12.56,'F':2.17,'G':1.80,'H':5.27,'I':7.24,
'J':0.14,'K':0.63,'L':4.04,'M':2.60,'N':7.38,'O':7.47,'P':1.91,'Q':0.09,'R':6.42,'S':6.59,
'T':9.15,'U':2.79,'V':1.00,'W':1.89,'X':0.21,'Y':1.65,'Z':0.07}
 
def Nbr_Letters(Chaine):
    Tab_Letters = {'A':0,'B':0,'C':0,'D':0,'E':0,'F':0,'G':0,'H':0,'I':0,'J':0,'K':0,'L':0,'M':0,
'N':0,'O':0,'P':0,'Q':0,'R':0,'S':0,'T':0,'U':0,'V':0,'W':0,'X':0,'Y':0,'Z':0}
    for Char in Chaine:
        if Char.upper() in Tab_Letters:
            Tab_Letters[Char.upper()]+=1
    return Tab_Letters
 
def Freq_Calc(Tab_Nbr_Letters):
    Total_occurrence = 0
    for i in Tab_Nbr_Letters:
        Total_occurrence += Tab_Nbr_Letters[i]
    for Indice in Tab_Nbr_Letters:
        if Tab_Nbr_Letters[Indice] != 0.:
            Tab_Nbr_Letters[Indice]=100./(Total_occurrence/Tab_Nbr_Letters[Indice])
    return Tab_Nbr_Letters
 
def Freq_Analyse(Chaine_Freq, Lang_Freq):
    A = sorted(Chaine_Freq.keys())
    B = sorted(Lang_Freq.keys())
    x = max(Chaine_Freq.values())
    y = max(Lang_Freq.values())
    for i in A:
        if Chaine_Freq[i] == x:
            L_a = i
            break
    for j in B:
        if Lang_Freq[j] == y:
            L_b = j
            break
    i = 0
    I_a, I_b =0,0
    while i < len(A):
        if A[i] == L_a:
            I_a = i
        if B[i] == L_b:
            I_b = i
        i+=1
    return I_b-I_a,{L_a:L_b}
 
def Crack(Key, Text):
    return Text.translate(maketrans(ascii_uppercase, ascii_uppercase[Key:] 
+ ascii_uppercase[:Key]))
 
Crypt = raw_input("Votre cryptogramme : ")
Analyse = Freq_Calc(Nbr_Letters(Crypt))
 
#Changer FR_Freq en EN_Freq si vous entrez des cryptogrammes Anglais
raw_input(Crack(Freq_Analyse(Analyse, FR_Freq)[0], Crypt.upper()))

Analyse fréquentielles des bigrammes[modifier | modifier le code]

Un bigramme est un ensemble de 2 lettres côte à côte. Dans le tableau ci-dessous, les bigrammes sont deux lettres appartenant à un même mot prises au hasard dans des textes en français.

Bigrammes les plus courants en langue française
Bigrammes Pourcentages
ES 3,15 %
LE 2,46 %
EN 2,42 %
DE 2,15 %
RE 2,09 %
NT 1,97 %
ON 1,64 %
TE 1,63 %
ER 1,63 %
SE 1,55 %

Limites[modifier | modifier le code]

L'analyse fréquentielle ne peut être utilisée que pour des codes de substitutions simples, elle est par exemple inefficace contre les méthodes de chiffrement RSA et DES. Elle ne fonctionne pas pour les codes dits de transposition, qui changent la place des lettres ou des symboles dans le message. Pour savoir si l'on a affaire à un code de substitutions, on peut utiliser l'indice de coïncidence avant l'analyse fréquentielle. Cela permet également d'avoir une longueur de mot clé conseillée qui peut servir de base pour l'analyse statistique.

L'analyse de fréquences ne peut pas non plus être utilisée si la longueur du message est très faible, car la clé se répétera très peu et nous ne pourrons observer de particularités dans la fréquence des lettres. C'est aussi pour cette raison que l'on ne peut pas déchiffrer un message codé avec une longueur de clé égale à celle du message. Un même message chiffré peut correspondre alors à n'importe quel message clair, puisqu'il y a autant de clés que de clairs. Nous ne pouvons donc pas dans ce cas précis déterminer le sens général du message, c'est le principe du masque jetable qui garantit un message réellement indéchiffrable.

Pour se prémunir d'une cryptanalyse par analyse fréquentielle, les cryptographes ont inventé plusieurs parades utilisées dans les algorithmes de chiffrements. On peut utiliser un chiffre qui attribue plusieurs symboles pour une seule lettre, en fonction de sa fréquence (par exemple, on utilisera 4 ou 5 symboles pour le E mais un seul pour le K). On dit alors que l'on utilise un code homophonique.

On peut également utiliser le surchiffrement, qui consiste à recoder le texte chiffré par un autre type de chiffrement pour ne pas permettre de faire des hypothèses sur les lettres les plus fréquentes. Pour une combinaison de chiffrements bien choisie, un texte surchiffré sera donc plus difficile à déchiffrer.

L'analyse fréquentielle en littérature[modifier | modifier le code]

Message codé de la fiction des Hommes dansants.

L'analyse fréquentielle est une technique de cryptanalyse fréquemment relatée dans les fictions. On la retrouve par exemple dans Le Scarabée d'or d'Edgar Allan Poe ou dans Les Hommes dansants, une aventure de Sherlock Holmes écrite par Arthur Conan Doyle. Dans cette dernière énigme, les messages étaient alors codés avec différents symboles, en forme de personnages dansants.

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

Références[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]