Quelques éléments de cryptanalyse

Notion de sécurité

Chaque procédé cryptographique spécifie un problème supposé difficile contre lequel il doit offrir une certaine sécurité. En général, on ne sait pas la minorer de manière intéressante. Le rôle des cryptanalystes est de la majorer de manière aussi spectaculaire que possible. La sécurité correspond à la complexité, c'est-à-dire le coût en temps, en espace de travail ou en matériel de calcul, de la résolution de problèmes contre lesquels on souhaite se protéger. Actuellement, on constate un saut entre les procédés destinés à un usage pratique, dont on ne sait pas montrer la sécurité autrement que par une expertise des cryptanalystes, et les procédés théoriques que l'on traite en théorie de la complexité.

On souligne également l'existence d'une notion de sécurité parfaite. Cette sécurité est liée à l'incapacité théorique de casser le problème (au sens de la théorie de l'information). Les rares exemples de protocoles qui offrent une sécurité parfaite sont hélas trop coûteux.

En général, un ``procédé théorique'' est une famille infinie de procédés associés à un paramètre de taille. On arrive parfois à étudier le comportement asymptotique de la complexité des problèmes sous-jacents en fonction du paramètre. Par exemple, on dira qu'un procédé théorique est sûr si la complexité croît exponentiellement. Une expertise a posteriori des cryptanalystes donne ensuite une idée du paramètre à utiliser en pratique. Hélas, ce paramètre est souvent trop grand.

Un ``procédé pratique'' (ou une instance d'un procédé théorique pour un paramètre donné) est sûr si la complexité de son problème sous-jacent est supérieure à un seuil. Pour des applications militaires, on pourra fixer un seuil correspondant à l'exploitation des ressources de calcul dans le monde entier pendant un siècle. Pour des applications domestiques, on pourra fixer un seuil correspondant à l'utilisation de machines coûteuses pendant un semaine.

Attaques des fonctions de chiffrement

Les fonctions de chiffrement sont supposées rendre impossible le décryptage, c'est-à-dire la récupération d'un message clair sans la clef. A fortiori, elle doivent protéger le secret des clefs. On distingue plusieurs types d'attaques :

• les attaques à texte chiffré connu, où l'on ne connaît que les textes chiffrés pour essayer de retrouver la clef;
• les attaques à texte clair connu, où l'on connaît des couples clairs/chiffrés;
• les attaques à texte clair choisi, où l'on suppose que l'on a un contrôle sur le texte clair (on dispose d'une boîte noire à chiffrer et l'on cherche la clef enfermée à l'intérieur).

Nous détaillerons deux types d'attaques :

Attaque de D.E.S.

Attaque de R.S.A.