|
La saga du DES
 Jusque dans les années 1970, seuls les militaires possédaient des algorithmes à clé secrète fiables. Devant l'émergence de besoins civils, le NBS (National Bureau of Standards) lança le 15 mai 1973 un appel d'offres dans le Federal Register (l'équivalent du Journal Officiel américain) pour la création d'un système cryptographique. Le cahier des charges était le suivant :
- l'algorithme repose sur une clé relativement petite, qui sert à la fois au chiffrement et au déchiffrement.
- l'algorithme doit être facile à implémenter, logiciellement et mâtériellement, et doit être très rapide.
- le chiffrement doit avoir un haut niveau de sûreté, uniquement lié à la clé, et non à la confidentialité de l'algorithme.
Les efforts conjoints d'IBM, qui propose Lucifer fin 1974, et de la NSA (National Security Agency) conduisent à l'élaboration du DES (Data Encryption Standard), l'algorithme de chiffrement le plus utilisé au monde durant le dernier quart du XXiè s.
La clé du DES est une chaîne de 64 bits (succession de 0 et de 1), mais en fait seuls 56 bits servent réellement à définir la clé. Les bits 8,16,24,32,40,48,56,64 sont des bits de parité (=bits de détection d'erreur). Le 8ème bit est fait en sorte que sur les 8 premiers bits, il y ait un nombre impair de 1. Par exemple, si les 7 premiers bits sont 1010001, le 8ème bit est 0. Ceci permet d'éviter les erreurs de transmission.
Il y a donc pour le DES 256 clés possibles, soit environ ... 72 millions de milliards possibilités. Les grandes lignes de l'algorithme sont :
- Phase 1 : Préparation - Diversification de la clé.
Le texte est découpé en blocs de 64 bits. On diversifie aussi la clé K, c'est-à-dire qu'on fabrique à partir de K 16 sous-clés K1,...,K16 à 48 bits. Les Ki sont composés de 48 bits de K, pris dans un certain ordre.
- Phase 2 : Permutation initiale.
Pour chaque bloc de 64 bits x du texte, on calcule une permutation finie y=P(x). y est représenté sous la forme y=G0D0, G0 étant les 32 bits à gauche de y, D0 les 32 bits à droite.
- Phase 3 : Itération
On applique 16 rondes d'une même fonction. A partir de Gi-1Di-1 (pour i de 1 à 16), on calcule GiDi en posant :
- Gi=Di-1.
- Di-1=Gi-1 XOR f(Di-1,Ki).
XOR est le ou exclusif bit à bit, et f est une fonction de confusion, suite de substitutions et de permutations. Le détail de cette fonction de confusion se trouve en annexe.
- Phase 4 : Permutation finale.
On applique à G16D16 l'inverse de la permutation initiale. Z=P-1(G16D16) est le bloc de 64 bits chiffré à partir de x.
Régulièrement, le DES a fait l'objet de polémiques. Toute sa sécurité repose sur la fonction de confusion f, et en particulier à l'intérieur de celle-ci sur des boîtes S, tableau 4x16 d'entiers compris entre 0 et 15, aux valeurs mystérieuses. Certains ont affirmé que la NSA, qui a finalisé l'algorithme, a placé dans ces boîtes S des trappes qui lui permettaient de tout décrypter, tout en affirmant que l'algorithme est sûr. Toutefois, rien n'a objectivement étayé cela. En particulier, le DES a toujours résisté aux travaux des cryptanalystes non basés sur la force brute.
En revanche, ce qui a signé l'arrêt de mort du DES est l'extraordinaire progression de la puissance des ordinateurs. Le 17 juin 1997, le DES est cassé en 3 semaines par une fédération de petites machines sur Internet. Et on estime très officiellement (dans un rapport présenté au Sénat Américain) à cette date à quelques secondes le temps nécessaire à un Etat pour percer les secrets d'un message chiffré avec le DES.
La solution a été dans un premier temps l'adoption du triple DES, trois applications de DES à la suite avec 2 clés différentes (d'où une clé de 112 bits) :
Si le TDES est largement suffisant à l'heure actuelle, il est malheureusement trois fois plus lent que le DES. C'est pourquoi, en janvier 1997, le NIST (National Institute of Standards and Technologies) lance un nouvel appel pour créer un successeur au DES. Une nouvelle saga commence pour l'AES (Advanced Encryption Standard).
Et encore, dans la cryptographie expliquée...
|