Indice de coïncidence

Dans le cas où plusieurs alphabets seraient utilisés mais que le nombre d'alphabets est inconnu, l'indice de coïncidence peut être un précieux allié pour déterminer ce nombre. On utilise alors la formule suivante :

${\displaystyle IC={\frac {n-m}{m(n-1)}}\cdot IC_{langue}+{\frac {n(m-1)}{(n-1)m}}\cdot 0,0385}$ avec n le nombre total de lettres dans le message, m le nombre d'alphabets, IC_langue l'indice pour la langue analysée et 0.0385 est un terme correspondant à un contenu uniformément distribué. En variant m, on peut comparer l'indice obtenu via cette formule avec l'indice réel provenant de la formule classique.

Soit un alphabet de 26 lettres, un texte de longueur infinie et un tirage au sort aléatoire, sans biais. La probabilité d'obtenir une lettre donnée est de 1/26. Obtenir deux lettres identiques a une probabilité égale à (1/26)². La probabilité d'obtenir une paire de deux lettres identiques est de l'ordre de : 26*(1/26)² = (1/26) = 0,0385 (La première lettre est tirée au hasard, la seconde a une probabilité de 1/26 d'être identique). C'est l'indice de coïncidence pour un message avec des lettres uniformément distribuées.

Introduisons maintenant un biais dans la distribution et raisonnons sur un texte de longueur finie. Nous avons un texte de 100 lettres et le nombre d'unités pour chaque lettre n'est pas identique. Disons que nous avons 20 lettres « A », 5 lettres « B », 7 lettres « C », etc., et un seul « Z ». Dans ce cas, la chance de trouver une paire quelconque de lettres identiques est : (20/100)*(19/99) + (5/100)*(4/99) + (7/100)*(6/99) + ... + (1/100)*(0/99). Nous avons alors une approximation de l'indice de coïncidence pour un langage qui suit cette distribution.

On peut aussi obtenir une estimation de la langue utilisée dans un texte en regardant son indice de coïncidence, la distribution des lettres n'étant pas la même entre les langues. Les indices peuvent légèrement varier selon les sources et les textes considérés pour l'analyse. Friedman donne par exemple un indice de 0,0746 pour le français.

L'indice est très utile lors de la vérification automatique d'un déchiffrement, en particulier lors d'une recherche exhaustive de toutes les clés. Les clés incorrectes fournissent un indice très proche de l'indice de données aléatoires uniformément distribuées. Une clé donnant un indice plus élevé a donc des chances d'être la bonne. Pour un chiffrement tel celui effectué par la machine Enigma, cette utilisation est intéressante (bien qu'anachronique) car le pupitre de connexions d'Enigma effectue un chiffrement mono-alphabétique. Cela signifie que l'indice de coïncidence n'est pas affecté par la configuration du pupitre de connexions, et par conséquent l'espace de recherche des clés est réduit aux configurations possibles des rotors.

Un tel procédé peut en théorie être utilisé sur tous les types de chiffrement lors d'une attaque automatisée, bien que cette méthode soit hors de portée des ordinateurs actuels pour les systèmes de chiffrement modernes.