Cryptographie!

L'indice de coïncidence

Indice de coïncidence

On appelle indice de coïncidence d'un texte la probabilité pour que, si on tire simultanément deux lettres au hasard dans ce texte, ce soient les mêmes. Si un texte est composé de $n$ lettres choisies parmi l'alphabet A,...,Z, alors son indice de coïncidence $I_c$ vaut : $$I_c=\frac{n_A(n_A-1)}{n(n-1)}+\cdots+\frac{n_B(n_B-1)}{n(n-1)}$$ où $n_A$ désigne le nombre de A dans le texte,... En effet, la probabilité pour que deux lettres choisies au hasard soient identiques vaut la probabilité que l'on ait choisi deux A plus la probabilité que l'on ait choisi deux B + ... + la probabilité que l'on ait choisi deux Z. Il suffit donc de calculer la probabilité pour que l'on ait choisi deux fois A? Il y a une probabilité exactement égale à $n_A/n$ pour que la première lettre choisie soit un $A$. Il reste alors $n-1$ lettres, et $n_A-1$ lettres $A$. La probabilité que l'on ait tiré encore un A pour deuxième lettre est donc $(n_A-1)/(n-1)$ La probabilité que l'on ait tiré deux fois la lettre A vaut donc exactement $\frac{n_A(n_A-1)}{n(n-1)}$.

On peut également retrouver cette dernière probabilité en utilisant le langage des combinaisons. Si on note $k=n_A$, il y a $\binom k2$ choix de deux A possibles dans le texte. Mais on peut faire $\binom n2$ choix de deux lettres quelconques. La probabilité pour que l'on tire deux fois la lettre A est donc $\frac{\binom{k}2}{\binom n2}=\frac{k(k-1)}{n(n-1)}$.

Indice de coïncidence aléatoire

Pour un long texte complètement aléatoire, avec probabilités d'apparition des lettres identiques, on a $n_A=n/26$ et l'indice de coïncidence d'un tel texte aléatoire est donc $$I_a=26\times\frac{\frac{n}{26}\left(\frac{n}{26}-1\right)}{n(n-1)}=\frac{\frac n{26}-1}{n-1}.$$ Ceci admet pour limite, quand $n$ tend vers l'infini, l'indice de coïncidence aléatoire limite $$I_a=\frac 1{26}.$$

Indice de coïncidence et cryptage de Vigenère

On suppose donc qu'un texte français de $n$ lettres est chiffré par le chiffre de Vigenère avec une clé de $k$ lettres, $n$ étant très grand par rapport à $k$. On cherche à exprimer la valeur théorique de l'indice de coïncidence du texte codé $I_c$. Les paires de 2 lettres du texte peuvent être partagées en 2 groupes :

  • ou bien elles sont codées avec la même lettre de la clé. Il y a $n\times (n/k-1)/2$ telles paires, soit à peu près $n(n-k)/2k$.
  • ou bien elles sont codées avec une lettre différente. Il y a $n(n-n/k)/2=n^2(k-1)/2$ telles paires.

On peut donc espérer que le nombre de paires de 2 lettres identiques du texte sera : $$\frac{n(n-k)}{2k}I_f+\frac{n^2(k-1)}2I_a$$ où $I_f$ désigne l'indice de coïncidence d'un texte écrit en français. Comme il y a $n(n-1)/2$ paires de deux lettres dans le texte, l'indice de coïncidence probable du texte est : $$I_c=\frac{1}{k(n-1)}\left((I_f-I_a)n+k(nI_a-I_f)\right).$$

Consulter aussi