Le test de Friedman

Chapitre: X. Chiffres polyalphabétiques Prérequis: Indice de coïncidence,
chiffre de Vigenère

Le test de Friedman (aussi appelé test kappa) s'appuie sur la métrique appelée Indice de Coïncidence (IC). Il a pour premier objectif de déterminer si un texte a été chiffré avec un chiffre monoalphabétique ou polyalphabétique. Comme second bénéfice, il suggère la longueur du mot-clef si le chiffre est polyalphabétique.


Comment trouver la longueur de la clef d'un chiffre de Vigenère

Soit le message suivant, chiffré avec Vigenère (369 lettres):

PERTQ UDCDJ XESCW MPNLV MIQDI ZTQFV XAKLR PICCP QSHZY DNCPW EAJWS ZGCLM QNRDE OHCGE ZTQZY HELEW AUQFR OICWH QMYRR UFGBY QSEPV NEQCS EEQWE EAGDS ZDCWE OHYDW QERLM FTCCQ UNCPP QSKPY FEQOI OHGPR EERWI EFSDM XSYGE UELEH USNLV GPMFV EIVXS USJPW HIEYS NLCDW MCRTZ MICYX MNMFZ QASLZ QCJPY DSTTK ZEPZR ECMYW OICYG UESIU GIRCE UTYTI ZTJPW HIEYI ETYYH USOFI XESCW HOGDM ZSNLV QSQPY JSCAV QSQLM QNRLP QSRLM XLCCG AMKPG QLYLY DAGEH GERCI RAGEI ZNMGI YBPP

On va considérer les sous-chaînes obtenues en prenant les lettres à intervalle donné:

Intervalle de 1: PERTQ UDCDJ XESCW MPNLV ... (texte original)
Intervalle de 2: PRQDD XSWPL ...    et    ETUCJ ECMNV ...
Intervalle de 3: PTDJS MLIIQ ...  ,   EQCXC PVQZF...    et    RUDEW NMDTV
    ...

On calcule ensuite les IC pour toutes ces sous-chaînes.

Intervalle Indice de coïncidence
1 0.0456107
2 0.0476954, 0.0443098
3 0.044249, 0.0494469, 0.0426771
4 0.0465839, 0.0453894, 0.0449116, 0.0425227
5 0.0799704, 0.0925583, 0.0836727, 0.0795282, 0.0684932
6 0.0512956, 0.0407192, 0.0371585, 0.0382514, 0.0661202, 0.0431694

On remarque que quand l'intervalle est de 5, l'IC correspond plus ou moins avec l'IC caractéristique du français (en tout cas, c'est cette ligne qui s'approche le plus de 0.074, les autres lignes étant plutôt proches de 0.038). La longueur de la clef utilisée est donc probablement 5. Pour découvrir la clef elle-même, on peut ensuite procéder comme le faisait Kasiski (ceci est laissé en exercice).


Calculateur de l'indice de coïncidence pour le test de Friedman

Texte non accentué (au besoin prétraitez le texte):
Intervalle:            


Le fichier Mathematica ci-dessous vous permettra de calculer rapidement l'IC. Téléchargez le fichier ci-dessous:

friedman.nb (16 Ko)

Cliquez sur le nom du fichier ci-dessus puis enregistrez sur votre disque dur ce fichier en format Texte en allant dans le menu Fichier/Enregistrer sous...
Ouvrez ensuite ce fichier depuis Mathematica (version 3 ou supérieure), et complétez-le.


Si un message en français de longueur n et d'indice de coïncidence IC est chiffré avec un carré de Vigenère, alors r, la longueur du mot-clef composé de lettres distinctes, est donné par la formule:


En appliquant cette formule au texte précédent, on trouve r = 4.69, ce qui confirme ce que l'on avait trouvé ci-dessus.


Références


Didier Müller, 14.7.01