Introduction au chiffrement avec DES

Décembre 2016

DES, le chiffrement à clé secrète

Le 15 mai 1973 le NBS (National Bureau of Standards, aujourd'hui appelé NIST - National Institute of Standards and Technology) a lancé un appel dans le Federal Register (l'équivalent aux Etats-Unix du Journal Officiel en France) pour la création d'un algorithme de chiffrement répondant aux critères suivants :

  • posséder un haut niveau de sécurité lié à une clé de petite taille servant au chiffrement et au déchiffrement
  • être compréhensible
  • ne pas dépendre de la confidentialité de l'algorithme
  • être adaptable et économique
  • être efficace et exportable

Fin 1974, IBM propose « Lucifer », qui, grâce à la NSA (National Security Agency), est modifié le 23 novembre 1976 pour donner le DES (Data Encryption Standard). Le DES a finalement été approuvé en 1978 par le NBS. Le DES fut normalisé par l'ANSI (American National Standard Institute) sous le nom de ANSI X3.92, plus connu sous la dénomination DEA (Data Encryption Algorithm).

Principe du DES

Il s'agit d'un système de chiffrement symétrique par blocs de 64 bits, dont 8 bits (un octet) servent de test de parité (pour vérifier l'intégrité de la clé). Chaque bit de parité de la clé (1 tous les 8 bits) sert à tester un des octets de la clé par parité impaire, c'est-à-dire que chacun des bits de parité est ajusté de façon à avoir un nombre impair de '1' dans l'octet à qui il appartient. La clé possède donc une longueur « utile » de 56 bits, ce qui signifie que seuls 56 bits servent réellement dans l'algorithme.

L'algorithme consiste à effectuer des combinaisons, des substitutions et des permutations entre le texte à chiffrer et la clé, en faisant en sorte que les opérations puissent se faire dans les deux sens (pour le déchiffrement). La combinaison entre substitutions et permutations est appelée code produit .

La clé est codée sur 64 bits et formée de 16 blocs de 4 bits, généralement notés k1 à k16. Etant donné que « seuls » 56 bits servent effectivement à chiffrer, il peut exister 256 (soit 7.2*1016) clés différentes !

L'algorithme du DES

Les grandes lignes de l'algorithme sont les suivantes :

  • Fractionnement du texte en blocs de 64 bits (8 octets) ;
  • Permutation initiale des blocs ;
  • Découpage des blocs en deux parties: gauche et droite, nommées G et D ;
  • Etapes de permutation et de substitution répétées 16 fois (appelées rondes) ;
  • Recollement des parties gauche et droite puis permutation initiale inverse.

algorithme du DES

Fractionnement du texte

Permutation initiale

Dans un premier temps, chaque bit d'un bloc est soumis à la permutation initiale, pouvant être représentée par la matrice de permutation initiale (notée PI) suivante :

PI
585042342618102
605244362820124
625446383022146
645648403224168
57494133251791
595143352719113
615345372921135
635547393123157

Cette matrice de permutation indique, en parcourant la matrice de gauche à droite puis de haut en bas, que le 58ème bit du bloc de texte de 64 bits se retrouve en première position, le 50ème en seconde position et ainsi de suite.

Scindement en blocs de 32 bits

Une fois la permutation initiale réalisée, le bloc de 64 bits est scindé en deux blocs de 32 bits, notés respectivement G et D (pour gauche et droite, la notation anglo-saxonne étant L et R pour Left and Right). On note G0 et D0 l'état initial de ces deux blocs :

G0
585042342618102
605244362820124
625446383022146
645648403224168

D0
57494133251791
595143352719113
615345372921135
635547393123157

Il est intéressant de remarquer que G0 contient tous les bits possédant une position paire dans le message initial, tandis que D0 contient les bits de position impaire.

Rondes

Les blocs Gn et Dn sont soumis à un ensemble de transformation itératives appelées rondes, explicitées dans ce schéma, et dont les détails sont donnés plus bas :

rondes

Fonction d'expansion

Les 32 bits du bloc D0 sont étendus à 48 bits grâce à une table (matrice) appelé table d'expansion (notée E), dans laquelle les 48 bits sont mélangés et 16 d'entre eux sont dupliqués :

E
3212345
456789
8910111213
121314151617
161718192021
202122232425
242526272829
28293031321

Ainsi, le dernier bit de D0 (c'est-à-dire le 7ème bit du bloc d'origine) devient le premier, le premier devient le second, ...
De plus, les bits 1,4,5,8,9,12,13,16,17,20,21,24,25,28 et 29 de D0 (respectivement 57, 33, 25, l, 59, 35, 27, 3, 6l, 37, 29, 5, 63, 39, 31 et 7 du bloc d'origine) sont dupliqués et disséminés dans la matrice.

OU exclusif avec la clé

La matrice résultante de 48 bits est appelée D'0 ou bien E[D0]. L'algorithme DES procède ensuite à un OU exclusif entre la première clé K1 et E[D0]. Le résultat de ce OU exclusif est une matrice de 48 bits que nous appelerons D0 par commodité (il ne s'agit pas du D0 de départ!).

Fonction de substitution

D0 est ensuite scindé en 8 blocs de 6 bits, noté D0i. Chacun de ces blocs passe par des fonctions de sélection (appelées parfois boîtes de substitution ou fonctions de compression), notées généralement Si.
Les premiers et derniers bits de chaque D0i détermine (en binaire) la ligne de la fonction de sélection, les autres bits (respectivement 2, 3, 4 et 5) déterminent la colonne. La sélection de la ligne se faisant sur deux bits, il y a 4 possibilités (0,1,2,3). La sélection de la colonne se faisant sur 4 bits, il y a 16 possibilités (0 à 15). Grâce à cette information, la fonction de sélection "sélectionne" une valeur codée sur 4 bits.

Voici la première fonction de substitution, représentée par une matrice de 4 par 16 :

S1
 0123456789101112131415
01441312151183106125907
10157414213110612119538
24114813621115129731050
31512824917511314100613

Soit D01 égal à 101110. Les premiers et derniers bits donnent 10, c'est-à-dire 2 en binaire. Les bits 2,3,4 et 5 donnent 0111, soit 7 en binaire. Le résultat de la fonction de sélection est donc la valeur situé à la ligne n°2, dans la colonne n°7. Il s'agit de la valeur 11, soit en binaire 111.

Chacun des 8 blocs de 6 bits est passé dans la fonction de sélection correspondante, ce qui donne en sortie 8 valeurs de 4 bits chacune. Voici les autres fonctions de sélection :

S2
 0123456789101112131415
01518146113497213120510
13134715281412011069115
20147111041315812693215
31381013154211671205149

S3
 0123456789101112131415
01009146315511312711428
11370934610285141211151
21364981530111212510147
31101306987415143115212

S4
 0123456789101112131415
07131430691012851112415
11381156150347212110149
21069012117131513145284
331506101138 94511127214

S5
 0123456789101112131415
02124171011685315130149
11411212471315015103986
24211110137815912563014
31181271142136150910453

S6
 0123456789101112131415
01211015926801334147511
11015427129561131401138
29141552812370410113116
34321295151011141760813

S7
 0123456789101112131415
04112141508133129751061
11301174911014351221586
21411131237141015680592
36111381410795015142312

S8
 0123456789101112131415
01328461511110931450127
11151381037412561101492
17114191214206101315358
12114741081315129035611

Chaque bloc de 6 bits est ainsi substitué en un bloc de 4 bits. Ces bits sont regroupés pour former un bloc de 32 bits.

Permutation

Le bloc de 32 bits obtenu est enfin soumis à une permutation P dont voici la table :

P
167202129122817
11523265183110
282414322739
19133062211425

OU Exclusif

L'ensemble de ces résultats en sortie de P est soumis à un OU Exclusif avec le G0 de départ (comme indiqué sur le premier schéma) pour donner D1, tandis que le D0 initial donne G1.

Itération

L'ensemble des étapes précédentes (rondes) est réitéré 16 fois.

Permutation initiale inverse

A la fin des itérations, les deux blocs G16 et D16 sont "recollés, puis soumis à la permutation initiale inverse :

PI-1
408481656246432
397471555236331
386461454226230
375451353216129
364441252206028
353431151195927
342421050185826
33141949175725

Le résultat en sortie est un texte codé de 64 bits !

Génération des clés

Etant donné que l'algorithme du DES présenté ci-dessus est public, toute la sécurité repose sur la complexité des clés de chiffrement.

L'algorithme ci-dessous montre comment obtenir à partir d'une clé de 64 bits (composé de 64 caractères alphanumériques quelconques) 8 clés diversifiées de 48 bits chacune servant dans l'algorithme du DES :

algorithme de generation des cles DES

Dans un premier temps les bits de parité de la clé sont éliminés afin d'obtenir une clé d'une longueur utile de 56 bits.

La première étape consiste en une permutation notée CP-1 dont la matrice est présentée ci-dessous :

CP-1
57494133251791585042342618
10259514335271911360524436
635547393123157625446383022
1466153453729211352820124

Cette matrice peut en fait s'écrire sous la forme de deux matrice Gi et Di (pour gauche et droite) composées chacune de 28 bits :

Gi
5749413325179
1585042342618
1025951433527
1911360524436

Di
63554739312315
7625446383022
1466153453729
211352820124

On note G0 et D0 le résultat de cette première permutation.

Ces deux blocs subissent ensuite une rotation à gauche, de telles façons que les bits en seconde position prennent la première position, ceux en troisième position la seconde, ...
Les bits en première position passent en dernière position.

Les 2 blocs de 28 bits sont ensuite regroupés en un bloc de 56 bits. Celui-ci passe par une permutation, notée CP-2, fournissant en sortie un bloc de 48 bits, représentant la clé Ki.

CP-2
14171124153281562110
23191242681672720132
415231374755304051453348
444939563453464250362932

Des itérations de l'algorithme permettent de donner les 16 clés K1 à K16 utilisées dans l'algortihme du DES.

LS
124681012141517192123252728

TDES, une alternative au DES

En 1990 Eli Biham et Adi Shamir ont mis au point la cryptanalyse différentielle qui recherche des paires de texte en clair et des paires de texte chiffrées. Cette méthode marche jusqu'à un nombre de rondes inférieur à 15, or un nombre de 16 rondes sont présentes dans l'algorithme présenté ci-dessus.

D'autre part, même si une clé de 56 bits donne un nombre énorme de possibilités, de nombreux processeurs permettent de calculer plus de 106 clés par seconde, ainsi, utilisés parallèlement sur un très grand nombre de machines, il devient possible pour un grand organisme (un Etat par exemple) de trouver la bonne clé...

Un solution à court terme consiste à chaîner trois chiffrement DES à l'aide de deux clés de 56 bits (ce qui équivait à une clé de 112 bits). Ce procédé est appelé Triple DES, noté TDES (parfois 3DES ou 3-DES).

Triple DES - 3DES

Le TDES permet d'augmenter significativement la sécurité du DES, toutefois il a l'inconvénient majeur de demander également plus de ressources pour les chiffrement et le déchiffrement.

On distingue habituellement plusieurs types de chiffrement triple DES :

  • DES-EEE3 : 3 chiffrements DES avec 3 clés différentes ;
  • DES-EDE3 : une clé différente pour chacune des 3 opérations DES (chiffrement, déchiffrement, chiffrement) ;
  • DES-EEE2 et DES-EDE2 : une clé différente pour la seconde opération (déchiffrement).

En 1997 le NIST lança un nouvel appel à projet pour élaborer l'AES (Advanced Encryption Standard), un algorithme de chiffrement destiné à remplacer le DES.

Le système de chiffrement DES fût réactualisé tous les 5 ans. En 2000 lors de la dernière révision, après un processus d'évaluation qui a duré 3 années, l’algorithme conçu conjointement par deux candidats belges, Messieurs Vincent Rijmen et Joan Daemen fût choisi comme nouveau standard par le NIST. Ce nouvel algorithme baptisé RIJNDAEL par ses inventeurs, remplacera dorénavant le DES.

Plus d'informations


A voir également :


Introduction to encryption with DES
Introduction to encryption with DES
Introducción al cifrado mediante DES
Introducción al cifrado mediante DES
Introduzione alla cifratura con DES
Introduzione alla cifratura con DES
Introdução à codificação DES
Introdução à codificação DES
Ce document intitulé «  Introduction au chiffrement avec DES  » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.