Indice de coïncidence

L'indice de Coïncidence (IC) est la probabilité que deux lettres choisies aléatoirement dans un texte soient identiques. Il fut inventé par William Friedman et publié en 1920, dans l'article "The Index of Coincidence and its Applications in Cryptography", Riverbank Publications Number 22.
Pour calculer cet indice, soient:

n = nombre de lettres du texte
William Friedman (1891-1969)
n1 = nombre de A dans le texte
n2 = nombre de B dans le texte
n3 = nombre de C dans le texte
...
n26 = nombre de Z dans le texte

La probabilité de tirer deux "A" parmi les n lettres d'un texte (clair ou crypté) est:

Pour calculer la probabilité de tirer deux lettres identiques, il faut faire la somme des 26 possibilités:

Voici quelques exemples d'indices calculés sur des textes contemporains dans différentes langues:

Langue allemand anglais espagnol esperanto français italien norvégien suédois
IC 0.072 0.065 0.074 0.069 0.074 0.075 0.073 0.071

Remarques importantes
  1. Pour un langage de 26 lettres où chaque lettre a la même fréquence (1/26), IC = 0.038 (vérifiez ce résultat avec la formule ci-dessus).
  2. Pour tout chiffre monoalphabétique, la distribution des fréquences est invariante, donc l'IC sera le même que pour le texte clair. Idem pour les chiffres de transposition.
  3. Donc, si on calcule l'IC d'un texte chiffré avec un chiffre monoalphabétique, on devrait trouver un IC "proche" de 0.074 (en français). Si l'IC est beaucoup plus petit (p. ex. 0.050), le chiffre est probablement polyalphabétique.

Calculateur de l'indice de coïncidence

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

 

L'indice de coïncidence peut servir à déterminer approximativement le nombre d'alphabets utilisés dans un chiffre polyalphabétique (par exemple le chiffre de Vigenère). En effet, l'IC théorique en fonction du nombre d'alphabets est:

où N est le nombre de lettres du message, IClangue est l'indice pour la langue du cryptogramme (voir tableau) et m le nombre d'alphabets.

Exercices

  1. Calculez à la main l'indice de coïncidence du texte ci-dessous, puis vérifiez-le avec la programme javascript ci-dessus: L'indice de coincidence est considere comme une des grandes decouvertes cryptographiques du debut du vingtieme siecle.

  2. Parmi les trois textes ci-dessous, lesquels sont des substitutions polyalphabétiques ?

    1. USGVM VBHOX MGJBK JMKSS MVTYJ SPOWP FBNKD IOHNK UTFHO KCBQZ ULWRE BOGOI VLNXM WCOMJ MGPZF GOIES MGDMP BMOUT PGMOJ PFRYS IRECH YQRTH LAKXJ CHY

    2. DOLJG YHHFN USOZI IMKIY UPQZF UWIQH UPFIH PHLMS TLGIC YRRDR KSSZW UVPHX BPWLP TPIEL JYFYU INHLW BBVWJ KLTMV PEUL

    3. MTPYB FPWPN STQQC POPNP DLCDZ TEOFY PDTXA WTNTE POPDL CXLYE PTWPD ELWZC TRTYP OPMPL FNZFA OPDJD EPXPD AWFDN ZXAWT BFPD

  3. Vérifiez l'IC concernant l'espagnol (0.074) en utilisant le tableau des fréquences d'apparition de lettres en espagnol.

Programmation

Ecrivez un programme Python qui calcule l'indice de coïncidence d'un texte. Solution

Références

Licence Creative Commons Didier Müller, 27.4.21