index of coincidence

Prenez deux positions différentes dans un texte et regardez les lettres qui s’y trouvent. Si elles sont identiques, vous avez une coïncidence. L’indice mesure la fréquence de ce résultat lorsque tous les couples possibles de positions sont pris en compte.

Une langue répète certaines lettres plus que d’autres. Cette empreinte statistique subsiste après une transposition ou une substitution monoalphabétique, tandis que l’emploi de plusieurs alphabets tend à la rendre moins marquée.

L’indice de coïncidence est la probabilité que deux positions distinctes, choisies au hasard dans un texte, contiennent la même lettre. On fixe un alphabet de n caractères. Le nombre total de lettres du texte est noté N, et le nombre d’occurrences de sa i-ième lettre est noté n_i. Il faut au moins deux lettres, donc N ≥ 2.

Avec ces notations, l’indice est donné par :Le numérateur compte les couples ordonnés de positions portant une même lettre. Le dénominateur compte tous les couples ordonnés de positions distinctes. Leur quotient est sans unité et appartient à l’intervalle de 0 à 1.

La valeur dépend de la langue : pour un texte français non chiffré, elle vaut environ 0,075. Une transposition ou une substitution monoalphabétique conserve les effectifs des lettres, donc l’indice. Selon la clé, les alphabets employés et la longueur du texte, un chiffrement polyalphabétique peut abaisser l’indice ; une valeur de l’ordre de 0,05 suggère l’emploi de plusieurs alphabets. Introduit par William Friedman, cet indice fait partie des outils d’attaque du chiffrement de Vigenère.

Calculons l’indice du mot BANANE.
Le texte contient N = 6 lettres.
A apparaît 2 fois et N apparaît 2 fois.
B et E apparaissent chacune 1 fois.

1. Pour A, le nombre de couples ordonnés identiques vaut 2 × (2 − 1) = 2. Pour N, il vaut aussi 2. Les lettres présentes une seule fois apportent chacune 1 × (1 − 1) = 0.

2. Le numérateur vaut donc 2 + 2 + 0 + 0 = 4. Le nombre total de couples ordonnés de positions distinctes vaut 6 × (6 − 1) = 30.

3. Le calcul complet donne :L’indice de BANANE est donc exactement 2/15, soit environ 0,133 en écriture décimale.

Le contrôle consiste à énumérer les coïncidences : les deux A donnent deux ordres possibles, et les deux N en donnent deux autres. On retrouve 4 cas favorables parmi 30.

Face à un texte chiffré, on commence par compter les occurrences de chaque lettre, puis on applique la formule. Un indice voisin du repère de la langue est compatible avec une transposition ou une substitution monoalphabétique, car ces procédés conservent les effectifs.

Un indice de l’ordre de 0,05 oriente plutôt vers un chiffrement polyalphabétique. Ce résultat fournit une piste, pas une identification certaine : il doit être interprété avec la longueur du texte et avec d’autres outils de cryptanalyse.

Pour attaquer un chiffrement de Vigenère, l’indice sert ainsi de test statistique. Si le texte est très court, mieux vaut éviter une conclusion tranchée, car quelques répétitions suffisent à déplacer fortement le résultat.

Indice de coïncidence et fréquence d’une lettre. La fréquence de A ne concerne que A ; l’indice additionne les répétitions de toutes les lettres. Dans BANANE, A et N ont chacune une fréquence de 2/6, tandis que l’indice global vaut 2/15.

Coïncidence et égalité à la même position. Le calcul ne superpose pas deux copies du texte. Il choisit deux positions distinctes dans un seul texte. Les deux A de BANANE coïncident parce qu’ils occupent deux positions différentes portant la même lettre.

Moins de deux lettres. Si N vaut 0 ou 1, le dénominateur N(N − 1) est nul. L’indice n’est alors pas défini ; il ne faut pas lui attribuer arbitrairement la valeur 0.

Texte très court. Le mot BANANE donne environ 0,133, bien au-dessus du repère français 0,075, sans être un échantillon représentatif d’un texte français. Il faut augmenter la longueur analysée avant de tirer une conclusion.

Alphabet ou préparation différents. Les espaces, signes et variantes de lettres modifient N et les effectifs s’ils sont inclus. Il faut fixer les caractères comptés et conserver cette convention dans toute comparaison.

Indice pris pour une preuve. Une valeur de l’ordre de 0,05 suggère plusieurs alphabets, mais ne suffit pas à nommer le chiffrement. L’indice oriente l’analyse ; il ne remplace pas les autres vérifications cryptanalytiques.

Le chiffrement replace l’indice dans son contexte : il aide à distinguer les grandes familles de transformations auxquelles la cryptanalyse s’intéresse.

Un prolongement naturel consiste à étudier pourquoi une permutation des positions ou un renommage unique des lettres conserve la somme des effectifs, alors que l’emploi de plusieurs alphabets tend à modifier la répartition observée selon leur diversité, la clé et la longueur du texte.