Indice de coïncidence

L’indice de coïncidence (souvent abrégé IC, ou IoC en anglais) est une statistique qui caractérise la « concentration » de la distribution de lettres d’un texte. Concrètement, on calcule la probabilité que, en piochant deux lettres au hasard dans le texte, elles soient identiques. C’est une signature numérique de la langue (ou de l’absence de langue) — et l’un des outils les plus efficaces de la cryptanalyse classique.

La formule

Sur un texte de N caractères dont chaque lettre i apparaît n_i fois (sur l’alphabet de 26 lettres) :

IC = Σ n_i × (n_i − 1) / (N × (N − 1))

L’idée : n_i × (n_i − 1) compte le nombre de paires ordonnées (sans répétition) qu’on peut former avec la lettre i. La somme sur toutes les lettres donne le nombre total de paires identiques. Diviser par N × (N − 1) (le total des paires possibles) donne la probabilité qu’une paire tirée au hasard contienne deux lettres identiques.

Trois valeurs étalons

Type de texte	IC typique
Texte aléatoire uniforme (chaque lettre équiprobable)	≈ 0,038 (= 1/26)
Texte anglais en clair	≈ 0,067
Texte français en clair	≈ 0,074
Texte allemand en clair	≈ 0,072
Texte italien en clair	≈ 0,074
Vigenère bien clé long	≈ 0,038 à 0,045
César / Atbash / substitution monoalphabétique	identique au clair (≈ 0,067 EN, 0,074 FR)

Ces valeurs ne sont pas magiques : elles découlent directement des fréquences de lettres de chaque langue. Une langue où une lettre domine fortement (le E en français) concentre les paires identiques, et l’IC monte. Une langue plate (ou un chiffre polyalphabétique qui aplatit la fréquence) fait redescendre l’IC vers la valeur uniforme.

Application 1 : distinguer mono- de polyalphabétique

Premier usage classique : devant un chiffré inconnu, on mesure l’IC.

• IC ≈ 0,07 (français) ou 0,065 (anglais) → on est probablement face à un chiffre monoalphabétique (César, Atbash, substitution). Lancer une analyse de fréquence.
• IC ≈ 0,04 → c’est probablement un chiffre polyalphabétique (Vigenère, Beaufort) ou un chiffré moderne. L’analyse de fréquence directe ne marchera pas ; il faut d’abord déterminer la longueur de la clé.
• IC ≈ 0,038 et chiffré uniformément aléatoire d’apparence → chiffre moderne (AES, ChaCha20) ou OTP. Abandonner la cryptanalyse classique.

Cette mesure prend trois lignes de code et donne une orientation immédiate.

Application 2 : trouver la longueur de clé d’un Vigenère

Deuxième usage, plus puissant. Sur un Vigenère, l’IC global est plat (~0,04). Mais si on prend un sous-message en sélectionnant une lettre sur k, ce sous-message a été chiffré avec une seule lettre de clé — c’est-à-dire un César. Son IC remonte à la valeur de la langue.

Procédure :

1. Pour k = 1, 2, 3, … 20 (raisonnablement), on prend le chiffré et on extrait toutes les lettres en positions 0, k, 2k, 3k, …. Ça donne le « premier sous-message ».
2. On calcule l’IC de ce sous-message.
3. On répète pour tous les k testés.
4. La valeur de k qui donne un IC ≈ 0,07 (FR) ou 0,065 (EN) est très probablement la longueur de clé.

C’est cette astuce qui a permis à William F. Friedman, à la NSA, de mécaniser le cassage du Vigenère dans les années 1920. Couplée au test de Kasiski, elle ramène un chiffre réputé indéchiffrable à un puzzle de quelques heures.

L’apport de Friedman et Kullback

William Friedman publie en 1922 son célèbre « The Index of Coincidence and Its Applications in Cryptography ». Il y formalise la mesure et démontre comment elle permet de :

1. Déterminer la longueur de clé d’un chiffre polyalphabétique périodique.
2. Identifier la langue d’un texte clair retrouvé.
3. Détecter une dépendance statistique entre deux textes (notamment pour les attaques par texte clair connu).

Son collègue Solomon Kullback étendra l’approche à la divergence de Kullback-Leibler, mesure plus générale que l’IC mais qui s’en inspire directement. Tous deux finissent à l’origine de la NSA.

Calcul pratique sur un exemple court

Soit le chiffré ATTACKATDAWN (12 lettres) :

• A apparaît 4 fois → 4 × 3 = 12
• T apparaît 3 fois → 3 × 2 = 6
• C apparaît 1 fois → 0
• K apparaît 1 fois → 0
• D apparaît 1 fois → 0
• W apparaît 1 fois → 0
• N apparaît 1 fois → 0
• Somme = 18
• IC = 18 / (12 × 11) = 18 / 132 ≈ 0,136

L’IC est très élevé — mais ici sur 12 lettres, le bruit statistique domine. L’IC n’est fiable qu’à partir de ~100 caractères, idéalement 200+. Sur des textes courts, comparer plusieurs IC entre eux reste possible, mais juger en valeur absolue est hasardeux.

À retenir :

• L’IC mesure la concentration de la distribution de lettres : élevé pour une langue (E, A dominent), bas pour un texte aléatoire.
• Valeurs étalons : ≈ 0,074 français, 0,067 anglais, 0,038 aléatoire.
• Premier usage : distinguer monoalphabétique (IC élevé) de polyalphabétique (IC bas) sur un chiffré inconnu.
• Deuxième usage : trouver la longueur de clé d’un Vigenère en testant l’IC de sous-messages pris tous les k caractères.
• Calcul peu fiable sur moins de ~100 caractères. Au-delà, c’est un outil de cryptanalyste tout à fait robuste.