|
|
Chiffrements par blocs
DES |
Introduction
L'algorithme DES, Data Encryption Standard, a été créé dans les laboratoires de la firme IBM Corp. Il est devenu le standard du NIST en 1976 et a été adopté par le gouvernement en 1977. C'est un chiffrement qui transforme des blocs de 64 bits avec une clé secrète de 56 bits au moyen de permutations et de substitutions. Le DES est considéré comme étant raisonnablement sécuritaire.
Le DES est officiellement défini dans la publication FIPS 46-3 et il est public.
La clé est en fait constituée de 64 bits, dont 56 bits sont générés aléatoirement et utilisés dans l'algorithme. Les huit autres bits peuvent être utilisés pour la détection d'erreurs (dans une transmission par exemple). Chacun des huit bits est utilisé comme bit de parité des sept groupes de 8 bits.
Comme blowfish, le DES est un chiffrement Feistel. Il utilise les transformations de substitution et de transposition (chiffrement par produit). Il est aussi appelé Data Encryption Algorithm (DEA).
Algorithme
Pour être chiffré, un bloc subit tout d'abord une permutation initiale, puis un algorithme complexe est appliqué en fonction de la clé (calcul médian), et enfin le bloc subit une permutation finale. Cette dernière permutation est l'inverse de la permutation initiale. De cette façon, l'algorithme de chiffrement et de déchiffrement est le même.
Le calcul médian dépendant de la clé peut être défini comme étant deux fonctions : une première appelée la fonction de chiffrement et une fonction de programmation de la clé.
Chifffement
Programmation de la clé
La fonction de programmation du bloc de 48 bits en fonction de la clé est appelée à chaque round avec en entrée, un nombre entier "n" entre 1 et 16 et le bloc de 64 bits de la clé. La sortie est le bloc clé "K" de 48 bits, ce bloc étant une sélection de bits de la clé après des permutations.
Kn = PC(n,CLÉ)
PC = programmation de la clé
Permuation initiale
Les 64 bits du bloc en entrée dans l'algorithme DES subissent la permutation initiale.
| Bloc en entrée |
|
Bloc en sortie |
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
| 9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
| 17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
| 25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
| 33 |
34 |
35 |
36 |
37 |
38 |
39 |
40 |
| 41 |
42 |
43 |
44 |
45 |
46 |
47 |
48 |
| 49 |
50 |
51 |
52 |
53 |
54 |
55 |
56 |
| 57 |
58 |
59 |
60 |
61 |
62 |
63 |
64 |
|
|
P.I. |
| 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 |
45 |
37 |
29 |
21 |
13 |
5 |
| 63 |
55 |
47 |
39 |
31 |
23 |
15 |
7 |
|
|
Ainsi, le premier bit du bloc résultant de la permutation initiale est le 58ème bit du bloc en entrée, le deuxième bit est le 50ème bit et ainsi de suite.
Calcul médian
Le calcul médian peut se résumer comme étant une fonction contenant 16 itérations identiques. Cette fonction traite deux blocs à la fois : un bloc de 32 bits, les données, et l'autre de 48 bits, la clé. Le résultat donne un bloc de 32 bits.
Le bloc de donnée de 64 bits est préalablement divisé en deux blocs de 32 bits, "L" et "R" (pour "Left" et "Right"), après être passé dans la permutation initiale. Ainsi, "L" contient les bits pairs et "R" contient les bits impairs.
Les 48 bits du bloc "K" (pour "Key") sont choisis à partir de la clé initiale de 64 bits. La sortie de L'R' après l'itération est définie par :
L' = R
R' = L XOR f(R,K)
L'R' = [R][L + f(R,K)]
L'entrée à la première itération du chiffrement est le bloc ayant subit la permutation initiale. À la fin, le bloc L'R' restant après la seizième itération devient le bloc de pré-sortie (avant la permutation finale). À chaque itération, un bloc "K" différent de 48 bits est choisi à partir de la clé de 64 bits.
Pour "n" variant de 1 à 16, on a
Ln = Rn-1
Rn = Ln-1 XOR f(Rn-1,Kn)
La fonction de chiffrement "f"
f reçoit le bloc "R" et le bloc "K" en entrée.
La fonction E prend un bloc de 32 bits en entrée et donne un bloc de 48 bits en sortie. Les 48 bits, représentés en huit blocs de 6 bits chacun, sont obtenus en sélectionnant les bits du bloc en entrée selon le tableau suivant.
| 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 |
|
Ainsi les trois premiers bits du bloc sortant sont le 32ème, le 1er et le 2ème bit du bloc en entrée. Chacune des huit fonctions de sélection, les S-Boxes, prend un bloc de 6 bits comme entrée et donne un bloc de 4 bits en sortie. La première fonction de sélection "S1" est représentée par la table suivante :
| S1 |
| Ligne No. |
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
|
|
|
|
| 14 |
4 |
13 |
1 |
2 |
15 |
11 |
8 |
3 |
10 |
6 |
12 |
5 |
9 |
0 |
7 |
| 0 |
15 |
7 |
4 |
14 |
2 |
13 |
1 |
10 |
6 |
12 |
11 |
9 |
5 |
3 |
8 |
| 4 |
1 |
14 |
8 |
13 |
6 |
2 |
11 |
15 |
12 |
9 |
7 |
3 |
10 |
5 |
0 |
| 15 |
12 |
8 |
2 |
4 |
9 |
1 |
7 |
5 |
11 |
3 |
14 |
10 |
0 |
6 |
13 |
|
|
Le contenu des 7 autres S-Boxes est défini à l'adresse suivante.
Le bloc en entrée de 8 bits "B" est traité comme suit : le premier bit et le dernier bit du bloc unis représentent un nombre compris entre 0 et 3 en base 2, appelé Bi, alors que les 4 bits restants du milieu représentent un nombre compris entre 0 et 15 en base 2, appelé "Bj". Par exemple, si le bloc "B" est "011011" :
Bi = 01 = 1 en base 10
Bj = 1101 = 13 en base 10
Ainsi, Bi étant le numéro de la ligne de S1 et Bj étant le numéro de sa colonne, le bloc de 4 bits de sortie sera "5" en base 10 , donc "0101" en base 2.
Les 8 fonctions de sélection S1, S2, S3, ..., S8 traitent chacune un des 8 blocs. Ces 8 blocs sont consolidés pour former qu'un seul bloc de 32 bits, lequel sera l'entrée pour une dernière permutation dans la fonction f.
La permutation "P" sur le bloc de 32 bits est représentée par la table suivante :
| 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 |
|
Le résultat est un bloc de 32 bits.
À la suite des 16 rounds, le bloc de pré-sortie est L16R16.
Permutation finale
Le contenu du bloc de pré-sortie, est permuté une dernière fois. Cette permutation correspond à l'inverse de la permutation initiale.
| 40 |
8 |
48 |
16 |
56 |
24 |
64 |
32 |
| 39 |
7 |
47 |
15 |
55 |
23 |
63 |
31 |
| 38 |
6 |
46 |
14 |
54 |
22 |
62 |
30 |
| 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 |
|
Ainsi, le premier bit du bloc final est le 40ème bit du bloc précédent, le deuxième bit égale le 8ème bit, etc..
Déchiffrement
La permutation finale est l'inverse de la permutation initiale. On applique exactement le même algorithme, mais à l'inverse, en tenant bien compte que chaque itération du déchiffrement traite les mêmes paires de blocs utilisées dans le chiffrement.
Rn-1 = Ln
Ln-1 = Rn XOR f(Ln,Kn)
Maintenant R16L16 et le bloc d'entrée dans la fonction de déchiffrement, et R0L0 est le bloc de pré-sortie, avant la permutation finale. Ainsi le bloc relatif à la clé K16 est utilisé dans la première itération et K1 dans la dernière.
Considérations
La recherche de failles a mis en relief la possibilité qu'il pourrait exister des relations linéaires ou quasi linéaires entre le texte clair et le texte chiffré du DES. Si cette possibilité se révélait vrai, le DES serait extrêmement vulnérable face aux attaques relatives aux relations linéaires. Les résultats des recherches ont été gardés secrets.
|
 |
|
|
|
|
