Øhistorique :

Le D.E.S. (Data Encryption Standard, c’est-à-dire Standard de Chiffrement de Données) est un standard mondial depuis plus de 15 ans. Bien qu’il soit un peu vieillissant, il résiste toujours très bien à la cryptanalyse et reste très sûr contre les ennemis sauf peut-être les plus puissants.

Au début des années 70, le développement des communications entre ordinateurs a nécessité la mise en place d’un standard de chiffrement de données pour limiter la prolifération d’algorithmes différents ne pouvant pas communiquer entre eux. Pour résoudre ce problème, L’Agence Nationale de Sécurité américaine (N.S.A.) a lancé des appels d’offres.

La société I.B.M. a développé alors un algorithme nommé Lucifer, relativement complexe et sophistiqué. Après quelques années de discussions et de modifications, cet algorithme, devenu alors D.E.S., fut adopté au niveau fédéral le 23 novembre 1976.

C’est, comme son nom l’indique, un standard ; pour cette raison l’algorithme est parfaitement défini et immuable. Toute modification apportée à D.E.S. impose de renommer l’algorithme obtenu.

ØPrincipe de fonctionnement de l’algorithme :

Le D.E.S. est un système de chiffrement par blocs. Cela signifie qu’il découpe virtuellement le texte en clair en blocs de 64 bits qu’il code séparément, puis il les concatène .

C’est un algorithme de cryptage à clef secrète. La clef sert donc à la fois à crypter et à décrypter le message. Cette clef a ici une longueur de 64 bits, soit 8 caractères, mais seulement 56 bits sont utilisés. On peut donc éventuellement imaginer un programme testant l’intégrité de la clef en exploitant ces bits inutilisés comme bits de contrôle de parité.

L’algorithme est assez simple puisqu’il ne combine en fait que des permutations et des substitutions. On parle en cryptologie de techniques de confusion et de diffusion.

L'entière sécurité de l'algorithme repose sur les clefs puisque l'algorithme est parfaitement connu de tous. La clef de 64 bits est utilisée pour générer 16 autres clefs de 48 bits chacune qu'on utilisera lors de chacune des 16 itérations du D.E.S.. Ces clefs sont les mêmes quel que soit le bloc qu'on code dans un message. On les calcule donc une fois pour toute.

ØGénération des clefs :

On commence par effectuer une permutation compressive sur la clef entrée par l'utilisateur qui fait passer le nombre de bits de 64 à 56. On forme donc un bloc de 56 bits que l'on sépare en deux blocs, G0 et D0, de 28 bits chacun. On décale d'un bit vers la gauche chaque bloc G0 et D0. On obtient donc G1 et D1. On forme alors le bloc G1D1 (en concaténant les deux blocs bout à bout) auquel on applique la permutation P2 qui ne retourne que 48 bits, lesquels forment la clef K1.

Ce calcul se généralise pour calculer les 15 autres clefs Ki à partir de Gi-1 et Di-1 à ceci près que le nombre de bits de décalage de Gi et de Di varie en fonction de i de la manière suivante :

nombre de bits de décalage : {1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1}.

On génère donc 16 clefs Ki où iÎ {1;2;3;...;16}.

ØAlgorithme proprement dit

Le bloc de 64 bits issu du message subi une permutation initiale P0 qui renvoie les 64 bits dans un autre ordre. On coupe ensuite le bloc ainsi obtenu en 2 blocs de 32 bits L0 et R0. Le D.E.S. réalise ensuite 16 fois une série d'opérations sur ces 2 blocs : on appelle cela les 16 itération du D.E.S. ou les 16 rondes du D.E.S.. Chacune de ces rondes, nommée parfois fonction f, peut être décrite en 5 étapes ; elle utilise le bloc Li et le bloc Ri, ainsi que la clef Ki précédemment générée.

– Première étape :

Le bloc Ri subie une permutation expansive qui le fait passer de 32 bits à 48 bits en répétant certain bits. On obtient le bloc Ri'.

– Deuxième étape :

On réalise un OU-Exclusif entre les 48 bits de la clef Ki et les 48 bits du bloc Ri' que l'on vient de générer.

– Troisième étape :

Le bloc ainsi obtenu est coupé en 8 blocs de 6 bits chacun. Chaque bloc est substitué de la manière suivante :

Un bloc est représenté par les 6 bits le constituant : (b1, b2, b3, b4, b5, b6). A l'aide de ces bits on forme 2 nombres représentant une colonne et une ligne de la matrice de substitution du D.E.S. qui est parfaitement connue et définie. Ainsi, en regroupant b1 et b6 on forme le nombre (b1b6) compris entre 0 et 3 qui donne l'indice de ligne ; le regroupement des autres bits forment le nombre (b2b3b4b5) compris entre 0 et 15 qui indique le numéro de colonne. Ces 2 indices fournissent la valeur correspondante dans la matrice de substitution. C'est un nombre compris entre 0 et 15 c’est-à-dire codé sur 4 bits. On substitue donc 4 bits à 6 bits. Pour améliorer un peu l'algorithme, chaque bloc utilise une matrice de substitution différente. Il y a donc 8 matrices de substitutions pour chacun des 8 blocs de 6 bits. En revanche les mêmes matrices sont utilisée dans 2 itérations différentes du D.E.S. sinon sa programmation serait délicate. Les 8 blocs de 4 bits ainsi obtenus sont ensuite concaténés.

Le résultat de la troisième étape est donc la substitution d'un bloc de 48 bits par un bloc de 32 bits obtenu grâce au tables de substitution.

– Quatrième étape :

Les 32 bits renvoyés par l'étape 3 sont permutés par la permutation P qui renvoie 32 bits. On obtient le bloc Ri".

– Cinquième étape :

On réalise un OU-Exclusif entre le bloc Li et le bloc Ri" qui ont bien tous les deux 32 bits. On obtient alors le bloc Ri+1. Le bloc Li+1 est pris égal au bloc Ri du début de la première étape. Cette dernière étape renvoie donc les blocs Li+1 et Ri+1 qui seront utilisés pour la ronde suivante.

On a donc Li+1 = Ri et Ri+1 = f(Li, Ri, Ki).

Après les 16 rondes, on concatène les blocs R16 et L16 pour former le bloc (R16, L16) – notons que les blocs sont échangés : on ne forme pas le bloc (L16, R16) comme il aurait été logique de le faire ; ceci assure le caractère involutif de l'algorithme – auquel on applique la permutation P0^-1 qui est la réciproque de la permutation initiale. On obtient – enfin ! – le bloc chiffré qui fait donc 64 bits.

ØDéchiffrement du D.E.S.

Bien que toutes les opération réalisées semblent à sens unique, il n'en est rien en fait puisque toutes les opérations effectuées sont bijectives. Le même algorithme pourra donc être utilisé pour le déchiffrement la seule différence étant l'ordre d'utilisation des clefs : il faut prendre les clefs dans l'autre sens c'est-à-dire en commençant par K16. En revanche l'algorithme sera lu dans le même sens que lors du chiffrement.

ØAvantages et inconvénients du D.E.S. :

Le D.E.S. possède 2 avantages de taille qui font de lui le système cryptographique le plus utilisé à l'heure actuelle qui sont sa sécurité et sa relative vitesse de chiffrement par des puces spécialisées.

En effet la sécurité du D.E.S. avec ses 16 rondes est grande et résiste à l'heure actuelle à toutes les attaques linéaires, différentielles ou par clefs corrélées, effectuées avec des moyens financiers et temporels raisonnables (i.e. moins de 10 millions de dollars et moins d'un mois). La grande sécurité repose sur ses tables de substitutions non linéaires très efficaces pour diluer les informations. De plus le nombre de clefs est élevé (2⁵⁶=7,2*10¹⁶) et peut être facilement augmenté en changeant le nombre de bits pris en compte. D'autres avantages plus techniques au niveau cryptanalyse existent.

De plus, cet algorithme est relativement facile à réaliser matériellement et certaines puces chiffrent jusqu'à 1 Go de données par seconde ce qui est énorme :c'est plus que ce qu'est capable de lire un disque dur normal. Pour les industriels c'est un point important notamment face à R.S.A..

Il existe quand même quelques défauts. Le principal est le sentiment de frustration de beaucoup sur sa réelle sécurité. La N.S.A. a-t-elle inséré une brèche secrète dans l'algorithme pour pouvoir contrôler les messages chiffrés ? Mais les nombreuses études développées depuis n'ont jamais rien prouvé. De plus on a constaté l'existence de certaines clefs dites faibles c'est-à-dire dont l'utilisation peut permettre un décodage plus facile qu'avec d'autres clefs. Il faut donc bien choisir sa clef si on veut une réelle efficacité. Enfin la polémique sur la longueur de la clef se poursuit afin de déterminer si une clef de 56 bits est assez longue.

Toujours est-il que le D.E.S. (ou une de ses nombreuses variantes qui existent) a encore une belle perspective de vie avant que soit trouvé quelque chose de vraiment plus performant.

retour aux exemples.