Indice de coïncidence

Quand on analyse un message chiffré, découvrir le type de chiffrement utilisé est primordial. Cette tâche n'est pas toujours évidente mais certains outils peuvent aider. Parmi ces outils l'indice de coïncidence ou IC est un passage obligé... autant que l'analyse de fréquence voire plus.

Présentation de l'Indice de Coïncidence

L'IC est une valeur décimale inventée par Wilfried Friedman et publiée en 1920 qui mesure la probabilité que deux lettres choisies aléatoirement dans un texte soient identiques.

La formule de l'IC est la suivante :

IC = SUM(1,N) Ni(Ni-1) / N(N-1

N : Nombre de lettre dans l'alphabet
Ni : Nombre d'occurrence de la lettre i

Chaque langue ayant ses propres caractéristiques, chaque langue a aussi un IC qui lui est propre (tableau original ici) :

Langue	Indice
Russe	0,0529
Serbe	0,0643
Suédois	0,0644
Anglais	0,0667
Esperanto	0,0690
Grec	0,0691
Norvégien	0,0694
Danois	0,0707
Finnois	0,0737
Italien	0,0738
Portugais	0,0745
Arabe	0,0758
Allemand	0,0762
Hébreu	0,0768
Espagnol	0,0770
Japonais	0,0772
Français	0,0778
Néerlandais	0,0798
Malaysien	0,0852

On peut trouver des IC différents selon les sources, tout dépend bien entendu du texte d'origine sur lequel il a été calculé. Par exemple un texte issu du livre La disparition de Georges Perec aura peu de chance d'être représentatif de la langue française et aura donc un IC bien différent.

Utilisation de l'Indice de Coïncidence

Bon c'est bien beau tout ça, mais ça n'explique pas en quoi l'IC peut aider au décryptage d'un texte. Pour commencer, la valeur de l'indice est indépendante des lettres utilisées, il mesure la probabilité de tomber deux fois sur la même lettre quelle que soit cette lettre.

Ce qui veut dire que dans le cas d'une substitution mono-alphabétique (césar, carré de polybe...), le texte chiffré et le texte en clair auront exactement le même IC. De la même façon les chiffres de transposition comme celui utilisé à la NDH par exemple, ne font que modifier l'ordre d'apparition des lettres dans le texte, sans en modifier la quantité, l'IC reste donc inchangé.

Quand on travaille sur un texte chiffré suffisamment long (pour être le plus représentatif possible), on peut donc facilement écarter certaines hypothèses grâce à cet outil. Si ce dernier a une valeur de 0.03 il y a peu de chance que ce soit une substitution mono-alphabétique ou une transposition, il faudra donc plus regarder en direction de chiffres polyalphabétiques par exemple de type Vigenère, Porta ou Gronsfeld qui eux modifient la quantité de chaque lettre.

L'utilisation de l'IC va bien au delà de la simple caractérisation du type de chiffrement utilisé. Prenons par exemple un texte en clair que l'on chiffre avec un algorithme qui va modifier la fréquence d'apparition de chaque lettre (Hill, ADFGVX, Playfair...), et on applique un surchiffrement dessus avec une substition mono-alphabétique. A priori l'exercice paraît compliqué pour passer du texte chiffré au texte en clair. Pourtant l'IC apporte ici une aide non négligeable.
Si on décide de faire une recherche exhaustive des clés du premier algo, il ne sera pas possible de savoir si on a trouvé la bonne clé, car le deuxième chiffrement nous masquera la réponse. Cependant on sait que le deuxième algo ne modifie pas l'IC. Il sera donc possible de réduire énormément l'espace de recherche, en ne sélectionnant que les textes qui ont un IC convenable. L'algorithme suivant permet d'expliquer cette démarche.

ecart_accepte = 0.01   // A adapter selon les besoins
Pour toutes les clés K faire
   plain = déchiffrer(cipher,K);
   Si abs(0.0778 - IC(plain)) < ecart_accepte Alors
      plain_possibles.add(plain);
   FinSi
FinPour

L'espace de recherche qui était constitué d'un ensemble aussi important que le nombre de clé est grandement réduit grâce à l'IC.

L'IC peut aussi être utilisé dans la recherche de la taille de la clé pour un message chiffré avec Vigenère. Cet algorithme modifie le rapport de fréquence d'apparition des lettres, et donc l'IC. Cependant il n'est ni plus ni moins qu'un ensemble de N décalages (N césar) où N est la taille de clé.

Prenons ce texte suivant : "CET ARTICLE PARLE DE L INDICE DE COINCIDENCE QUI EST UN OUTIL TRES UTILE EN CRYPTANALYSE" et chiffrons le avec la clé "CLE".

CETARTICLEPARLEDELINDICEDECOINCIDENCEQUIESTUNOUTILTRESUTILEENCRYPTANALYSE
CLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLEC
EPXCCXKNPGAETWIFPPKYHKNIFPGQTRETHGYGGBYKPWVFRQFXKWXTPWWEMNPIPNVAAXCYENJWG

Les 1°, 4°, 7°... caractères sont chiffrés avec le caractère C et sont donc décalés de 2 caractères (3° lettre de l'alphabet).
Les 2°, 5°, 8°... caractères sont chiffrés avec le caractère L et sont donc décalés de 11 caractères (12° lettre de l'alphabet).
Les 3°, 6°, 9°... caractères sont chiffrés avec le caractère E et sont donc décalés de 4 caractères (5° lettre de l'alphabet).

Il y a donc 3 groupes de lettres dans le texte en clair qui subissent chacun un décalage différent et chaque groupe de lettre a un IC proche de celui de sa langue d'origine. Etant donné qu'un décalage n'est qu'une substitution mono-alphabétique, l'IC de chaque groupe de lettres chiffrées doit être proche de celui de la langue d'origine, si c'est pas le cas c'est que le groupe n'est pas bon et que donc la taille de la clé est fausse.

# ./friedman_test.rb 1 4 EPXCCXKNPGAETWIFPPKYHKNIFPGQTRETHGYGGBYKP

WVFRQFXKWXTPWWEMNPIPNVAAXCYENJWG

Taille Clé:1 => 0.05213089802130898 

Taille Clé:2 => 0.04804804804804805 0.050793650793650794 

Taille Clé:3 => 0.07333333333333333 0.09057971014492754 0.07608695652173914 

Taille Clé:4 => 0.08187134502923976 0.0915032679738562 0.026143790849673203 0.032679738562091505

Comme on peut le voir ici, une taille de clé égale à 3 donne les IC les plus proches du français. La taille de la clé sera probablement de 3 caractères. Bien entendu, une clé de longueur multiple de 3 doit donner aussi de bons résultats. Ce test est appelé le test de Friedman.

Voilà pourquoi l'indice de coïncidence est un outil indispensable en cryptanalyse qui peut nous aider dans bien des cas.