Indice de coïncidence

Indice de coïncidence

L'indice de coïncidence est une technique de cryptanalyse inventée par William F. Friedman en 1920 (publiée dans The Index of Coincidence and its Applications in Cryptography) et améliorée par son collaborateur Solomon Kullback (en).

L'indice permet de savoir si un texte a été chiffré avec un chiffre mono-alphabétique ou un chiffre poly-alphabétique en étudiant la probabilité de répétition des lettres du message chiffré. Il donne également une indication sur la longueur de la clé probable.

L'indice se calcule avec la formule suivante : IC = \sum_{q=A}^{q=Z} \frac{n_{q}(n_{q}-1)}{n(n-1)} avec n le nombre de lettres total du message, nA le nombre de A, nB le nombre de B, etc.

En français, l'indice de coïncidence vaut environ 0,0746. Dans le cas de lettres uniformément distribuées (contenu aléatoire sans biais), l'indice se monte à 0,0385. L'indice ne varie pas si une substitution monoalphabétique des lettres a été opérée au préalable. C’est-à-dire que si l'on remplace par exemple 'a' par 'z' et 'z' par 'a', l'indice ne changera pas.

Sommaire

Indice de coïncidence pour les chiffrements polyalphabétiques

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 :

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, IClangue 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.

Raisonnement mathématique

Soit un alphabet de 26 lettres, un texte de longueur infinie et un tirage au sort aléatoire, sans biais. La chance d'obtenir une lettre donnée est de 1/26. Obtenir deux lettres identiques se monte à une probabilité de (1/26)2. La probabilité d'obtenir une paire de deux lettres identiques est de l'ordre de : 26*(1/26)2 = (1/26) = 0,0385 (La première lettre est tirée au hasard, la seconde a une probablilité 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 », ..., 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.

Autres langues

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,0778 pour le français.

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

Exemple d'utilisation

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.

Voir aussi

Liens externes

Articles connexes

v · Preuve de sécurité • Sécurité inconditionnelle • IND-CPA • IND-CCA • Kerckhoffs • Malléabilité • Sécurité calculatoire • Hypothèses calculatoires • Confusion et diffusion
Cryptanalyse de base Biais statistique • Corrélation • Dictionnaire • Force brute • Fréquence • Indice de coïncidence • Interpolation • Mot probable
Cryptanalyse par canal auxiliaire Acoustique • Consommation • Émanations EM • Faute • Sondage • Temporel
Cryptanalyse ciblée Clé apparentée • Clé faible • EFF • Enigma • Glissement • Intégrale • Linéaire / Différentielle / Différentielle impossible / Différentielle-linéaire / Boomerang • Modes opératoires • Modulo n • Quadratique • Rectangle • Rencontre au milieu • Vigenère • χ²
Systèmes asymétriques Clé apparentée • Clé faible • Homme au milieu • Sécurité sémantique
Fonctions de hachage Effet avalanche • Linéaire / Différentielle • Paradoxe des anniversaires • Pseudo-collision
Autres Anonymat • Confidentialité • Intégrité • Sécurité par l'obscurité

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Indice de coïncidence de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Indice De Coïncidence — L indice de coïncidence est une technique de cryptanalyse inventée par William F. Friedman en 1920 et publiée dans The Index of Coincidence and its Applications in Cryptography. L indice permet de savoir si un texte a été chiffré avec un chiffre… …   Wikipédia en Français

  • Indice de coincidence — Indice de coïncidence L indice de coïncidence est une technique de cryptanalyse inventée par William F. Friedman en 1920 et publiée dans The Index of Coincidence and its Applications in Cryptography. L indice permet de savoir si un texte a été… …   Wikipédia en Français

  • Cryptanalyse d'Enigma — Version américaine d une machine de cryptanalyse d Enigma. La cryptanalyse d Enigma, c est à dire le décryptage des messages transmis et codés par Enigma, fut fondamentale au succès des Alliés pendant la Seconde Guerre mondiale. Le mathématicien… …   Wikipédia en Français

  • Cryptanalyse d’Enigma — Cryptanalyse d Enigma La cryptanalyse d Enigma, c est à dire le décryptage des messages transmis et codés par Enigma, fut fondamentale au succès des Alliés pendant la Seconde Guerre mondiale. Le mathématicien polonais Marian Rejewski a élaboré la …   Wikipédia en Français

  • Analyse fréquentielle — L’analyse fréquentielle, ou analyse de fréquences, est une méthode de cryptanalyse découverte par Al Kindi au IXe siècle. Elle consiste à examiner la fréquence des lettres employées dans un message chiffré. Cette méthode est fréquemment… …   Wikipédia en Français

  • Cryptanalyse du chiffre de Vigenère — Le chiffre de Vigenère est un chiffrement basé sur une substitution polyalphabétique : une lettre de l alphabet dans le texte en clair peut être chiffrée de plusieurs manières. Ce principe remonte à des travaux antécédents à ceux de Blaise… …   Wikipédia en Français

  • Analyse Fréquentielle — L analyse fréquentielle, ou analyse de fréquences, est une méthode de cryptanalyse découverte par Al Kindi au IXe siècle. Elle consiste à examiner la fréquence des lettres employées dans un message chiffré. Cette méthode est fréquemment… …   Wikipédia en Français

  • Analyse frequentielle — Analyse fréquentielle L analyse fréquentielle, ou analyse de fréquences, est une méthode de cryptanalyse découverte par Al Kindi au IXe siècle. Elle consiste à examiner la fréquence des lettres employées dans un message chiffré. Cette… …   Wikipédia en Français

  • Attaque par biais statistique — Cryptanalyse La cryptanalyse s oppose, en quelque sorte, à la cryptographie. En effet, si déchiffrer consiste à retrouver le clair au moyen d une clé, cryptanalyser c est tenter de se passer de cette dernière. Même si on décrit les cryptanalystes …   Wikipédia en Français

  • Attaque par rencontre au milieu — Cryptanalyse La cryptanalyse s oppose, en quelque sorte, à la cryptographie. En effet, si déchiffrer consiste à retrouver le clair au moyen d une clé, cryptanalyser c est tenter de se passer de cette dernière. Même si on décrit les cryptanalystes …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”