Chapitre 3 FAQ de sci.crypt Chapitre 5 Retour à la case départ

Cryptologie mathématique

Ceci est le quatrième des dix chapitres de la FAQ de sci.crypt. Nous n'avons pas le temps d'envoyer ce qui manque par courrier électronique, donc ne demandez rien.
Des notes comme "[KAH67]" renvoient à la liste de références au dernier chapitre.

Les chapitres de cette FAQ sont disponibles par FTP anonyme sur ftp://rtfm.mit.edu/pub/usenet/news.answers/cryptography-faq/part[xx]
La FAQ de cryptographie est postée sur les groupes de discussions sci.crypt, talk.politics.crypto, sci.answers, et news.answer tous les 21 jours.

Table des matières best viewed with a brain Lecteur, attention: ce chapitre est hautement mathématique. Bon, peut-être pas hautement mathématique, mais il y a un bon paquet de symboles et de formules effrayantes. Vous êtes prévenu.
[NdT: c'est le chapitre le plus mal formulé de cette FAQ. Ceux qui s'intéressent vraiment aux aspects mathématiques de la cryptologie auront tout intérêt à lire "Cryptography: theory and practice" de Stinson, voire "Primality and cryptography" de Kranakis pour les plus courageux. Le Stinson a été traduit en français]

4.1. En termes mathématiques, qu'est-ce qu'un système à clé privée?

Un cryptosystème à clé privée est constitué d'un système de chiffrement E et d'un système de déchiffrement D. Le système de chiffrement E est un ensemble de fonctions EK, indexé par les clés K, définies d'un ensemble de textes clairs P vers un ensemble de textes chiffrés C. De même, le système de déchiffrement D est un ensemble de fonctions DK telles que DK(EK(P))=P pour tout texte clair P. C'est-à-dire que le déchiffrement d'un cryptogramme dans le bon texte clair nécessite la même clé (index) qui a été utilisée lors du chiffrement. De tels systèmes, où la même clé est utilisée pour chiffrer et déchiffrer sont aussi appelés systèmes symétriques.

4.2. Qu'est-ce qu'une attaque?

En termes intuitifs, une attaque (passive) contre un cryptosystème est une méthode qui, à partir d'informations sur des textes clairs et leurs textes chiffrés avec une certaine clé (inconnue), permet de trouver plus d'information sur les textes clairs. Il est possible d'exprimer mathématiquement ce que cela signifie. Allons-y.

Soient F, G et H des fonctions de n variables. Soit un cryptosystème E, et un ensemble de textes clairs et de clés.

Une attaque contre E utilisant G, supposant F, avec H donné, avec une probabilité p est un algorithme A ayant deux entrées f et g et une sortie h, ayant une probabilité p de calculer h=H(P1,...,Pn) si on a f=F(P1,...,Pn) et g=G(EK(P1),...,EK(Pn)). Notez que cette probabilité dépend de la distribution du vecteur (K,P1,...,Pn).

L'attaque est triviale s'il y a une probabilité au moins égale à p de calculer h=H(P1,...,Pn) si f=F(P1,...,Pn) et g=G(C1,...,Cn).
Ici C1,...,Cn varient uniformément parmi tous les cryptogrammes possibles et n'ont pas de relations particulières avec P1,...,Pn. En d'autres termes, une attaque est triviale si elle n'utilise pas les chiffrements EK(P1),...,EK(Pn).

[NdT: je n'aime pas ce terme trivial. Peut-on me dire quelle est la traduction française exacte ?]

Une attaque est appelée à un cryptogramme si n=1, à deux cryptogrammes si n=2, et ainsi de suite.

4.3. Quel est l'intérêt de formuler tout ceci mathématiquement?

En cryptologie de base vous ne pouvez jamais prouver qu'un cryptosystème est sûr. Lisez le chapitre 3: nous n'arrêtons pas de dire "un cryptosystème robuste doit avoir cette propriété, mais avoir cette propriété ne garantit pas que le cryptosystème soit robuste!".

Au contraire, le but de la cryptologie mathématique est de formuler précisément et si possible de prouver que le cryptosystème est robuste. On dit, par exemple, que le système résiste à toutes les attaques (passives) si toute attaque non triviale contre le système est trop lente pour être utilisable. Si on peut prouver ceci alors on saura que le cryptosystème résistera à toute technique cryptanalytique (passive). Si on peut ramener cette proposition à un problème non résolu bien connu, alors on saura que le cryptosystème n'est pas facile à casser.

D'autres parties de la cryptologie peuvent être formulées mathématiquement. Là encore le but est de définir explicitement les hypothèses que l'on fait et de prouver qu'on produit les résultats désirés. On peut se demander ce que signifie pour un cryptosystème particulier d'être utilisé "correctement": ça veut juste dire que les hypothèses sont valides.

La même méthodologie est utile pour la cryptanalyse aussi. Le cryptanalyste peut tirer partie des hypothèses incorrectes. Souvent il peut essayer de construire une preuve de la sécurité du système, voir où la preuve échoue, et utiliser cette faille comme le point de départ de son analyse.

4.4. Qu'est-ce que le masque jetable?

[NdT: la traduction française de [KAH67] dit clé aléatoire une fois]

Par définition, le masque jetable est un cryptosystème où les textes clairs, chiffrés et les clés sont tous des chaînes (disons des chaines d'octets) de longueur m, et EK(P) est juste la somme (disons le OU exclusif) de K et P.

Il est facile de prouver mathématiquement qu'il n'existe aucune attaque non triviale à un cryptogramme contre le masque jetable, en supposant que les clés soient distribuées uniformément. Notez que l'on a pas besoin d'une distribution uniforme des textes clairs.
(voici la preuve: soit A une attaque, c'est-à-dire un algorithme prenant deux entrées f et g et une sortie h, avec une probabilité p que h=H(P) si f=F(P) et g=G(EK(P)) (i.e., g=G(K+P)).
Alors, comme la distribution de K est uniforme et indépendante de P, la distribution de K+P est aussi uniforme et indépendante de P. Mais la distribution de C est aussi uniforme et indépendante de P. Donc il y a une probabilité exactement égale à p que h=H(P) si f=F(P) et g=G(C), pour tous P et C. Donc l'attaque A est triviale)

[NdT: je trouve tout ceci passablement "brain damaged", surtout après mon passage. Grossièrement, on ne peut pas casser le masque jetable, même en essayant toutes les clés car tous les libellés sont équiprobable, donc on ne peut pas choisir le bon.
Pour une formulation mathématique, voir la notion de perfect secrecy dans Cryptography: theory and practice de Stinson]

D'un autre coté, le masque jetable n'est pas sûr si une clé K est utilisée pour plus d'un texte clair: c'est-à-dire, il existe une attaque non triviale à plusieurs textes chiffrés. Donc pour être utilisé correctement la clé doit être jetée après un chiffrement. La clé est aussi appelée un masque, d'où l'expression masque jetable [NdT: ou clé aléatoire une fois].

Ainsi un générateur pseudo aléatoire sur ordinateur n'est pas un vrai masque jetable à cause de ses propriétés déterministes.
Cf. générateurs pseudo-aléatoires comme flux de clé

4.5. Qu'est-ce qu'une attaque texte chiffré seul ?

Avec la notation définie plus haut, dans une attaque texte chiffré seul F est constante. Etant donné seulement l'information G(EK(P1),...,EK(Pn)) sur n cryptogrammes, l'attaque doit produire l'information H(P1,...,Pn) sur les textes clairs. L'attaque est triviale si elle a une chance de fournir H(P1,...,Pn) quand on lui donne G(C1,...,Cn) pour C1,...,Cn aléatoires.

Par exemple, soit G(C)=C et soit H(P) le premier bit de P. Nous pouvons facilement monter une attaque (la "devinette") qui devine simplement que H(P) vaut 1. Cette attaque est triviale car elle n'utilise pas le texte chiffré: elle a 50 % de chance de deviner correctement quoi qu'il arrive. D'un autre coté, il y a une attaque contre le RSA qui produit 1 bit d'information sur P avec 100 % de succès en utilisant C. Si on lui donne un cryptogramme C aléatoire, sa chance de succès tombe à 50%. Donc c'est une attaque non triviale.

4.6. Qu'est-ce qu'une attaque texte clair connu ?

L'attaque classique à texte clair connu a F(P1,P2)=P1, G(C1,C2)=(C1,C2), et H(P1,P2) dépend seulement de P2. En d'autres termes, étant donnés deux cryptogrammes C1 et C2 et un libellé P1, l'attaque à texte clair connu founit de l'inforrmation sur l'autre libellé P2.

Notez que l'attaque à texte clair connu est souvent définie dans la littérature comme renseignant sur la clé mais ceci est injustifié: le cryptanalyste ne se soucie de la clé que dans la mesure où elle lui permet de décrypter d'autres messages.

4.7. Qu'est-ce qu'une attaque texte clair choisi ?

Une attaque à texte clair choisi est la première d'une série d'attaques actives de plus en plus difficiles à mettre en pratique: dans ces attaques le cryptanalyste alimente le chiffrement. Ces attaques n'entrent pas dans le cadre des attaques passives expliquées plus haut. Une attaque à texte clair choisi permet au cryptanalyste de choisir un libellé et de regarder le cryptogramme correspondant, et de recommencer jusqu'à ce qu'il ait trouvé comment décrypter n'importe quel message. Des exemples encore plus absurdes de ces sortes d'attaques sont l'attaque à clé choisie et l'attaque à système choisi.

[NdT: depuis que ce texte a été écrit, Bruce Schneier et ses acolytes ont monté une attaque à clés corrélées assez redoutable contre tout un éventail de cryptosystèmes. En introduction de leur papier ils expliquent pourquoi cette attaque est beaucoup moins théorique qu'il n'y paraît -- Cf. http://www.counterpane.com ]

Une forme d'attaque active beaucoup plus importante est l'attaque par corruption de message, où l'attaquant tente de changer le texte chiffré pour provoquer un changement utile dans le texte clair.

Il existe de nombreuses méthodes faciles pour tenir en échec toutes ces attaques: par exemple, en chiffrant automatiquement tout texte clair P comme T,EK(h(T+R+P),R,P), où T est une clé temporelle (numéro de séquence), R un nombre aléatoire, et h une fonction de hachage à sens unique. Ici "virgule" indique la concaténation et "plus" le OU exclusif.

4.8. En termes mathématiques, que peut-on dire d'une attaque par force brute?

Considérez l'attaque à texte clair connu suivante. Nous avons les libellés P1,...,P_{n-1} et les cryptogrammes C1,...,C_{n-1}. Nous avons aussi un cryptogramme Cn. Nous essayons toutes les clés K. Quand nous avons trouvé une clé K telle que EK(Pi)=Ci pour tout i < n, nous affichons DK(Cn).

Si n est suffisamment grand pour qu'une seule clé marche, alors cette attaque réussira tout le temps sur des entrées valides, tandis qu'elle produira une réponse correcte une fois tous les 36 du mois pour des entrées aléatoires. Donc c'est une attaque non triviale. Son seul problème est qu'elle est très lente s'il y a beaucoup de clés possibles.

4.9. Qu'est-ce qu'une attaque devinette? Qu'est-ce que l'entropie?

Imaginons que quelqu'un utilise le masque jetable --- mais ne choisisse pas les clés uniformément parmi tous les messages de m bits comme il était censé le faire dans notre preuve. En fait, disons qu'il préfère utiliser des mots anglais comme clés. Alors un cryptanalyste peut essayer tous les mots anglais comme clés. Cette attaque marchera souvent, et elle est beaucoup plus rapide que la recherche brutale sur l'ensemble de l'espace des clés. Nous pouvons mesurer à quel point une distribution de clé est mauvaise en calculant son entropie. Ce nombre E mesure les "vrais bits d'information" de la clé: un cryptanalyste trouvera la clé en 2^E essais. E est défini comme la somme de -pK*log2(pK), où pK est la probabilité de la clé K.
Chapitre 3 FAQ de sci.crypt Chapitre 5 Retour à la case départ
Michel Arboi
Last modified: Sun Mar 25 16:20:43 CEST 2007