Cryptographie!

Calcul de l'entropie d'un texte

  Comment estimer l'entropie d'un texte M écrit en français et constitué de d lettres M1,...,Md? Si les lettres pouvaient être considérées comme indépendantes les unes des autres, on aurait H(M1...Md)=dH(M1). Mais ce n'est pas le cas! Après un L, il est beaucoup plus probable que l'on ait un A ou un E qu'un R. En revanche, au-delà de 3 ou 4 lettres d'écart, il y a beaucoup moins d'interactions : si on a un L en 1ère position, il n'est pas très clair que l'on aura en 5è position plutôt un A ou plutôt un R. Cela signifie que la suite

va très rapidement s'approcher d'une valeur limite H. Pour d suffisamment grand (en pratique, d>20 suffit), on pourra faire l'approximation:
L'applet au bas de cette page permet d'estimer H. Le calcul effectué sur un texte français de grande taille a donné comme estimation pour H: Remarquons que la valeur de H dépend fortement de la langue employée. Si on calcule l'entropie d'un texte écrit en anglais ou en allemand, on trouve une valeur de H sensiblement plus grande (de l'ordre de 4.2). Ceci a d'ailleurs une signification : la langue française est plus rigide que les langues anglaises ou allemandes : les digrammes ou trigrammes les plus fréquents ont une prédominance plus forte en français qu'en anglais.

  Si on cherche maintenant à calculer l'entropie d'un message français chiffré par substitution, avec une substitution choisie au hasard, voici comment procéder. La encore, l'entropie va être approximativement proportionnelle à la longueur du texte. Pour calculer le coefficient de proportionnalité, on prend un texte français très long, on calcule de nombreux chiffrés de ce message, pour des substitions choisies au hasard. On met bout à bout ces chiffrés, et on calcule l'entropie…On trouve finalement un coefficient de proportionnalité proche de 4,67 (aussi bien en français qu'en anglais d'ailleurs!) Si on se réfère à la formule de la distance d'unicité se trouvant sur cette page, ceci signifie en particulier que la cryptographie par substitution est un peu plus sûre en langue anglaise qu'en langue française.
L'applet java
  L'applet java suivante permet de calculer l'entropie d'un texte, et l'entropie moyenne des messages chiffrés à partir de ce message à l'aide d'une substitution.

Consulter aussi