La saga du DES
L'histoire 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. Le DES fut publié comme standard par le NBS le
15 janvier 1977.
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, chiffre considérable, mais en fait très insuffisant avec la puissance des ordinateurs modernes.
Dès sa naissance, le DES a fait l'objet de polémiques. Bien que sa description soit assez compliquée (cf ci-dessous),
la plupart des opérations qu'il effectue sont des opérations linéaires. Or, on sait depuis longtemps vaincre les chiffres linéaires.
Toute la sécurité du DES repose donc sur les opérations non-linéaires qu'il effectue. Cela est effectué à l'aide de 8 "mystérieurses" boites-S,
qui sont des tableaux de 4 lignes et 16 colonnes, chaque ligne comprenant les 16nombres de 0 à 15. Ces boites-S ont été choisies par la NSA, ce
qui a suscité le trouble de certains : comment être sûr que la NSA n'a pas choisi ces boites-S en y plaçant des "trappes" qui lui permettaient
de tout décrypter, tout en affirmant que l'algorithme était sûr?
Pour être honnête, rien dans l'histoire du DES n'a objectivement étayé cela. En particulier, il 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. Ainsi, le DES a progressivement été abandonné à la fin des
années 1990. Il a dans un premier temps été remplacé par le triple DES, qui consiste en trois applications de DES à la suite avec 2 clés différentes (d'où une clé de 112 bits) :
Si la sécurité était largement assurée, le triple DES était 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).
Description du fonctionnement du DES
Le DES est un algorithme de chiffrement par bloc de 64 bits, c'est-à-dire que le texte est d'abord découpé en bloc de 64 bits et que l'on applique
l'algorithme à chaque bloc. Comme précisé plus haut, la clé de chiffrement comporte elle aussi 64 bits, même si seuls 56 bits sont utiles, les 8 bits restant étant des bits
de contrôle destinés à éviter les erreurs de transmission. Les grandes lignes de l'algorithme sont :
- Phase 1 : Préparation - Diversification de la clé.
On diversifie 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 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 - schéma de Feistel
On applique 16 tours d'un même schéma de Feistel. A partir de $G_{i-1}D_{i-1}$ (pour i de 1 à 16), on calcule $G_iD_i$ en posant :
- $G_i=D_{i-1}$;
- $D_i=g_{i-1}\oplus f(D_{i-1},K_i)$
où $\oplus$ est le "ou exclusif" bit à bit, et $f$ est une fonction de confusion, suite de substitutions et de permutations.
- 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.
Voyons maintenant les détails pratiques de l'implantation du DES.
La diversification de la clé
On part d'une clé K constitué de 64 bits. Pour calculer les clés diversifiées K1,...,K16, on effectue dans l'ordre les opérations suivantes :
- Permutation initiale : on calcule $PC_1(K)$, chaîne de 56 bits, où $PC_1(K)$ est constituée des bits de K pris dans l'ordre suivant :
| PC-1 |
| 57 | 49 | 41 | 33 | 25 | 17 | 9 |
| 1 | 58 | 50 | 42 | 34 | 26 | 18 |
| 10 | 2 | 59 | 51 | 43 | 35 | 27 |
| 19 | 11 | 3 | 60 | 52 | 44 | 36 |
| 63 | 55 | 47 | 39 | 31 | 23 | 15 |
| 7 | 62 | 54 | 46 | 38 | 30 | 22 |
| 14 | 6 | 61 | 53 | 45 | 37 | 29 |
| 21 | 13 | 5 | 28 | 20 | 12 | 4 |
Ainsi $PC_1(K)$ est constitué du 57è bit de K, puis du 49è,… On note $C_0D_0=PC_1(K)$, où $C_0$ est constitué des 28 premiers bits de $K$, et $D_0$ des 28 derniers.
- Décalage itéré : pour i allant de 1 à 16, on calcule $C_i$ et $D_i$ par les formules suivantes : $C_i$ est obtenu à partir de $C_{i-1}$ par permutation
circulaire (vers la gauche) de une position si $i=1,2,9,16$ et de deux positions sinon. $D_i$ est obtenu à partir de $D_{i-1}$ par permutation
circulaire (vers la gauche) de une position si $i=1,2,9,16$ et de deux positions sinon.
- calcul des clés diversifiées : la clé diversifiée $K_i$ est obtenue à partir de $C_iD_i$ en appliquant une deuxième substitution, appelée
$PC_2(K)$ : $K_i=PC_2(C_iD_i)$. La subbstitution $PC_2$ utilisée est la suivante :
| PC-2 |
| 14 | 17 | 11 | 24 | 1 | 5 |
| 3 | 28 | 15 | 6 | 21 | 10 |
| 23 | 19 | 12 | 4 | 26 | 8 |
| 16 | 7 | 27 | 20 | 13 | 2 |
| 41 | 52 | 31 | 37 | 47 | 55 |
| 30 | 40 | 51 | 45 | 33 | 48 |
| 44 | 49 | 39 | 56 | 34 | 53 |
| 46 | 42 | 50 | 36 | 29 | 32 |
La permutation initiale
A partir du bloc de 64 bits $X$, on calcule $Y=P(X)$ où $P$ est la permutation donnée par le tableau suivant (on donne aussi $P^{-1}$, utile pour la dernière étape) :
| P |
| 58 | 50 | 42 | 34 | 26 | 18 | 10 | 2 |
| 60 | 52 | 44 | 36 | 28 | 20 | 12 | 4 |
| 62 | 54 | 46 | 38 | 30 | 22 | 14 | 6 |
| 64 | 56 | 48 | 40 | 32 | 24 | 16 | 8 |
| 57 | 49 | 41 | 33 | 25 | 17 | 9 | 1 |
| 59 | 51 | 43 | 35 | 27 | 19 | 11 | 3 |
| 61 | 53 | 47 | 37 | 29 | 21 | 13 | 5 |
| 63 | 55 | 49 | 39 | 31 | 23 | 15 | 7 |
|
| P-1 |
| 40 | 8 | 48 | 16 | 56 | 24 | 64 | 32 |
| 39 | 7 | 47 | 15 | 55 | 23 | 63 | 31 |
| 38 | 6 | 46 | 14 | 54 | 22 | 62 | 31 |
| 37 | 5 | 45 | 13 | 53 | 21 | 61 | 29 |
| 36 | 4 | 44 | 12 | 52 | 20 | 60 | 28 |
| 35 | 3 | 43 | 11 | 51 | 19 | 59 | 27 |
| 34 | 2 | 42 | 10 | 50 | 18 | 58 | 26 |
| 33 | 1 | 41 | 9 | 49 | 17 | 57 | 25 |
|
La fonction de confusion
On étudie ici la fonction $f$ qui est utilisée dans l'itération du schéma de Feistel. Plus précisément, on détaille comment calculer f(D,K), où D est un bloc de 32 bits (partie droite obtenue à l'étape précédente) et K un bloc de 48 bits (obtenu par diversification de la clé).
- Etape 1 : Expansion. D est augmenté en une chaîne de 48 bits, suivant une fonction d'expansion E. E(D) est composé de tous les bits de D, écrits dans un ordre donné, 16 d'entre eux apparaissant 2 fois. La fonction E utilise la table suivante :
| E |
| 32 | 1 | 2 | 3 | 4 | 5 |
| 4 | 5 | 6 | 7 | 8 | 9 |
| 8 | 9 | 10 | 11 | 12 | 13 |
| 12 | 13 | 14 | 15 | 16 | 17 |
| 16 | 17 | 18 | 19 | 20 | 21 |
| 20 | 21 | 22 | 23 | 24 | 25 |
| 24 | 25 | 26 | 27 | 28 | 29 |
| 28 | 29 | 30 | 31 | 32 | 1 |
- Etape 2 : Ajout de la clef. On calcule $B=E(D)\oplus K$, et le résultat est découpé en 8 chaînes de 6 bits B1...B8.
- Etape 3 : Transformations locales. Pour chaque i de 1 à 8, on possède une boîte Si, qui est un tableau à 4 lignes et 16 colonnes, chaque colonne comprenant tous les entier compris entre 0 et 15. On écrit Bi sous la forme b1b2...b6. b1b6 est l'écriture en binaire d'un nombre entre 0 et 3, soit une ligne l de Si. b2b3b4b5 est l'écriture en bianire d'un nombre entre 0 et 15, soit une colonne c de Si. L'entier à la l-ième ligne et à la c-ième colonne de Si est représenté sur 4 bits et donne Ci=c1c2c3c4. Par exemple, voici la table correspondant à $S_1$ :
| S1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
| 0 |
14 |
4 |
13 |
1 |
2 |
15 |
11 |
8 |
3 |
10 |
6 |
12 |
5 |
9 |
0 |
7 |
| 1 |
0 |
15 |
7 |
4 |
14 |
2 |
13 |
1 |
10 |
6 |
12 |
11 |
9 |
5 |
3 |
8 |
| 2 |
4 |
1 |
14 |
8 |
13 |
6 |
2 |
11 |
15 |
12 |
9 |
7 |
3 |
10 |
5 |
0 |
| 3 |
15 |
12 |
8 |
2 |
4 |
9 |
1 |
7 |
5 |
11 |
3 |
14 |
10 |
0 |
6 |
13 |
Ex: on entre dans S1 avec comme entrée les bits 110101. Le premier et le dernier bit donnent 11, soit 3 en décimal : ceci indique la ligne 3 du tableau. Les 4 bits centraux sont 1010, qui donne 10 en décimal. A l'intersection de la 3è ligne et de la 10è colonne, on trouve 3, qui écrit en binaire donne 0011, c'est-à-dire les 4 bits de sortie.
- Etape 4 : Réassemblage et permutation. On réassemble les 8 blocs de 4 bits C=C1...C8, sur 32 bits. C est ensuite réordonné par une dernière permutation.
| Permutation finale |
| 16 | 7 | 20 | 21 |
| 29 | 12 | 28 | 17 |
| 1 | 15 | 23 | 26 |
| 5 | 18 | 31 | 10 |
| 2 | 8 | 24 | 14 |
| 32 | 27 | 3 | 9 |
| 19 | 13 | 30 | 6 |
| 22 | 11 | 4 | 25 |
En référence, voici le contenu de 7 autres boîtes-S, boites sur lesquelles une bonne part de la sécurité du DES repose :
| S2 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
| 0 |
15 |
1 |
8 |
14 |
6 |
11 |
3 |
4 |
9 |
7 |
2 |
13 |
12 |
0 |
5 |
10 |
| 1 |
3 |
13 |
4 |
7 |
15 |
2 |
8 |
14 |
12 |
0 |
1 |
10 |
6 |
9 |
11 |
5 |
| 2 |
0 |
14 |
7 |
11 |
10 |
4 |
13 |
1 |
5 |
8 |
12 |
6 |
9 |
3 |
2 |
15 |
| 3 |
0 |
14 |
7 |
11 |
10 |
4 |
13 |
1 |
5 |
8 |
12 |
6 |
9 |
3 |
2 |
15 |
| S3 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
| 0 |
10 |
0 |
9 |
14 |
6 |
3 |
15 |
5 |
1 |
13 |
12 |
7 |
11 |
4 |
2 |
8 |
| 1 |
13 |
7 |
0 |
9 |
3 |
4 |
6 |
10 |
2 |
8 |
5 |
14 |
12 |
11 |
15 |
1 |
| 2 |
13 |
6 |
4 |
9 |
8 |
15 |
3 |
0 |
11 |
1 |
2 |
12 |
5 |
10 |
14 |
7 |
| 3 |
1 |
10 |
13 |
0 |
6 |
9 |
8 |
7 |
4 |
15 |
14 |
3 |
11 |
5 |
2 |
12 |
| S4 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
| 0 |
7 |
13 |
14 |
3 |
0 |
6 |
9 |
10 |
1 |
2 |
8 |
5 |
11 |
12 |
4 |
15 |
| 1 |
13 |
8 |
11 |
5 |
6 |
15 |
0 |
3 |
4 |
7 |
2 |
12 |
1 |
10 |
14 |
9 |
| 2 |
10 |
6 |
9 |
0 |
12 |
11 |
7 |
13 |
15 |
1 |
3 |
14 |
5 |
2 |
8 |
4 |
| 3 |
3 |
15 |
0 |
6 |
10 |
1 |
13 |
8 |
9 |
41 |
5 |
11 |
12 |
7 |
2 |
14 |
| S5 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
| 0 |
2 |
12 |
4 |
1 |
7 |
10 |
11 |
6 |
8 |
5 |
3 |
15 |
13 |
0 |
14 |
9 |
| 1 |
14 |
11 |
2 |
12 |
4 |
7 |
13 |
1 |
5 |
0 |
15 |
10 |
3 |
9 |
8 |
6 |
| 2 |
4 |
2 |
1 |
11 |
10 |
13 |
7 |
8 |
15 |
9 |
12 |
5 |
6 |
3 |
0 |
14 |
| 3 |
11 |
8 |
12 |
7 |
1 |
14 |
2 |
13 |
6 |
15 |
0 |
9 |
10 |
4 |
5 |
3 |
| S6 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
| 0 |
12 |
1 |
10 |
15 |
9 |
2 |
6 |
8 |
0 |
13 |
3 |
4 |
14 |
7 |
5 |
11 |
| 1 |
10 |
15 |
4 |
2 |
7 |
12 |
9 |
5 |
6 |
1 |
13 |
14 |
0 |
11 |
3 |
8 |
| 2 |
9 |
14 |
15 |
5 |
2 |
8 |
12 |
3 |
7 |
0 |
4 |
10 |
1 |
13 |
11 |
6 |
| 3 |
4 |
3 |
2 |
12 |
9 |
5 |
15 |
10 |
11 |
14 |
1 |
7 |
6 |
0 |
8 |
13 |
| S7 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
| 0 |
4 |
11 |
2 |
14 |
15 |
0 |
8 |
13 |
3 |
12 |
9 |
7 |
5 |
10 |
6 |
1 |
| 1 |
13 |
0 |
11 |
7 |
4 |
9 |
1 |
10 |
14 |
3 |
5 |
12 |
2 |
15 |
8 |
6 |
| 2 |
1 |
4 |
11 |
13 |
12 |
3 |
7 |
14 |
10 |
15 |
6 |
8 |
0 |
5 |
9 |
2 |
| 2 |
6 |
11 |
13 |
8 |
1 |
4 |
10 |
7 |
9 |
5 |
0 |
15 |
14 |
2 |
3 |
12 |
| S8 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
| 0 |
13 |
2 |
8 |
4 |
6 |
15 |
11 |
1 |
10 |
9 |
3 |
14 |
5 |
0 |
12 |
7 |
| 1 |
1 |
15 |
13 |
8 |
10 |
3 |
7 |
4 |
12 |
5 |
6 |
11 |
0 |
14 |
9 |
2 |
| 2 |
7 |
11 |
4 |
1 |
9 |
12 |
14 |
2 |
0 |
6 |
10 |
13 |
15 |
3 |
5 |
8 |
| 3 |
2 |
1 |
14 |
7 |
4 |
10 |
8 |
13 |
15 |
12 |
9 |
0 |
3 |
5 |
6 |
11 |
Consulter aussi
