Mesure de l'imperfection d'un système cryptographique
Il faut avoir compris cette page avant d'envisager de consulter celle-ci.
Nous avons vu que la théorie de l'information permet de mesurer la qualité d'un système cryptographique grâce à la quantité H(M|C). Elle va même plus loin, et permet de répondre à cette question : à partir de quand notre système n'est plus sûr?
Prenons l'exemple de la cryptographie par sustitution mono-alphabétique. On sait bien que ce système de cryptographie ne résiste pas à l'analyse des fréquences. Mais combien faut-il de lettres au cryptanalyste pour reconstituer la clé?
Optons pour la modélisation suivante : le message est constitué d'une succession de lettres M1...Mn, la clé K est une permutation de l'alphabet à 26 lettres. En particulier, H(K)=log(26!). Le chiffré est une succession de lettres C1...Cn. On définit la distance d'unicité comme le plus petit entier d tel que :
Concrètement, d désigne le nombre moyen de lettres du message chiffré qu'il faut connaitre pour pouvoir déterminer la clé. D'autre part, on a :
(connaitre la clé et le message chiffré équivaut à connaitre la clé et le message en clair). D'où :
Cette égalité provient du fait que la clé est indépendante du message. On a donc :
L'estimation des quantités à gauche permet d'obtenir une approximation de d :
On a déjà vu que H(K)=log(26!).
On peut calculer empiriquement une valeur de H(M1...Md) en se basant sur une analyse statistique de nombreux textes écrits en français (les détails sont expliqués dans cette page). On constate alors que
L'évaluation de H(C1...Cd) est plus délicate. Si on suppose que tous les messages chiffrés ont une probabilité égale d'apparition, on a H(C)=log(26d)=d×log(26). Cette hypothèse est malheureusement inexacte, car s'il y a probabilité égale d'apparition pour chaque lettre, le message chiffré AAAA est très improbable (car aucun texte en clair, dont le chiffré est issu, ne contient 4 fois de suite la même lettre). Le mieux est encore de faire là-aussi une analyse statistique - voir cette applet -. On constate alors que
On en déduit que :
En pratique, il faut effectivement de l'ordre de ce nombre de lettres pour retrouver la clé.
Rem : Si on avait pris l'hypothèse d'équirépartition des messages chiffrés, on aurait trouvé Cette hypothèse donne donc une assez bonne approximation!
Et encore, dans la cryptographie expliquée...
Il faut avoir compris cette page avant d'envisager de consulter celle-ci.
Cette hypothèse donne donc une assez bonne approximation!
Et encore, dans la cryptographie expliquée...
