Les systèmes de Chiffrement symétriques

ou à Clefs secrètes

DES
(Data Encryption Standard)
 Le DES

Introduction.

Le DES (Data Encryption Standard)

est l'algorithme standard de chiffrement
symétrique.

Clé de Clé de
Chiffrement Déchiffrement
K K

Texte Texte Texte

Clair x Chiffré y Clair x

DES DES

Algorithme défini en 1976 par IBM.

2
 Le DES

Fonctionnement du DES

 Chiffrement par blocs de bits (taille: 64 bits)

avec une clé de 64 bits de laquelle on enlève
les 8 bits de parité.
 Longueur effective de la clé: 56 bits.
 Nombre total de clés: 256

 Le DES comporte en une série d'opérations de

transposition et de permutations:

 Permutation initiale (IP).

 16 'tours' consistant en des opérations plus
complexes de permutation/substitution
basée sur la clé.
 Permutation finale (IP-1).

3
 Le DES

Fonctionnement du DES

Schéma descriptif du DES.

Plaintext

IP

L0 R0

f
K1

L1=R0 R1=L0+ f(R0,K1)

L15=R14 R15=L14+ f(R14,K15)

f
K16

R16=L15+ f(R15,K16) L16=R15

IP

Ciphertext

4
 Le DES

Fonctionnement du DES

Les étapes du DES:

 Permutation initiale (IP)
 Division du bloc initial en 2 blocs de 32
bits (L0 et R0).
 16 Tours de DES

L i  Ri1
Ri  Li1  F (Ri1 , K i )
K i  G(K,i)
Où F(X,Y) est la fonction de
chiffrement opérant sur R i-1 et Ki
Ki est une sous-clé dérivée de K à
chaque tour i.
 Permutation finale (inverse de IP)
5
 Le DES

Fonctionnement du DES

Permutation initiale IP .

t1 t 2 ...t 64  t 58 t 50 ... t 7
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
6
 Le DES

Fonctionnement du DES

Permutation finale IP-1 .

' '
t t ...t
1 2
'
64  t t ...t
' '
40 8
'
25

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

7
 Le DES

Fonctionnement du DES

Les tours du DES .

 Li  t1 ...t 32
i ème
itération Ti  Li R i
 Ri  t 33 ...t 64
où Li  Ri1

Ri  Li1  F Ri1 , K i 

K i  G(K ,i)

8
 Le DES

Fonctionnement du DES

F(Ri-1, Ki) G(K, i)

Li-1 Ri-1 Key

Shift Shift

ExpansionPermutation CompressionPermu tation

S-BoxSubstitution

P-BoxPermutation

Li Ri Key

9
 Le DES

Fonctionnement du DES

Fonction de chiffrement F .
1. Opération d'expansion E(Ri-1).
 Ri-1 (32 bits) est étendu à 48 bits grâce à
la table d'expansion.

r1 r2 ...r32  r32 r1 r2 ...r32 r1  E Ri 1 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

32

48

1 2 3 4 56 78 9 10 1112 1314 15 16 1718 1920 21 22 2324

10
 Le DES

Fonctionnement du DES

1. Opération d'expansion (…) .

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

11
 Le DES

Fonctionnement du DES

2. Addition.
Le résultat de l'expansion est
additionné (modulo 2) à la sous-clé
Ki correspondant à l'itération i

E Ri1  K i  B1 B2 ... B8
B j bloc de 6 bits
B j  b1b2 b3 b4 b5 b6

12
 Le DES

Fonctionnement du DES

3. Boîtes de substitution.
 Chaque bloc Bj constitue ensuite l'input
de l'opération de substitution réalisée sur
base des S-box.

B j  S j B j 

Bloc de 6 Bloc de 4
bits bits

48-Bit Input

S-Box 1 S-Box 2 S-Box 3 S-Box 4 S-Box 5 S-Box 6 S-Box 7 S-Box 8

32-Bit Output

13
 Le DES

Fonctionnement du DES

3. Boîtes de substitution (…)

 L'opération de substitution consiste pour
chaque S-box à calculer:
• b1b6 = n° de ligne
• b2b3b4b5 = n° de colonne
N° de colonne
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

N° de ligne

 Résultat compris entre 0 et 15.

 4 bits/S-box.
 32 bits.
14
 Le DES

Fonctionnement du DES

4. Permutation.
 L'opération de permutation est réalisée
sur le résultat de la substitution des S-
box et est basée sur 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 de cette dernière

permutation est noté: F(R i-1 , K i)
15
 Le DES

Fonctionnement du DES

Calcul de la clé G(K, i) .

 Clé initiale K : 64 bits.

1. Réduction à 56 bits.
 Les bits de parité sont enlevés
 Permutation de la clé.

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
16
 Le DES

Fonctionnement du DES

2. Division de la clé. Numbe

 Division en 2 sous-clés de Iteration i r of

Left
28 bits. Shifts

1 1
2 1
3. Rotation de la clé. 3 2
 A chaque tour, chaque sous- 4 2
clé subit une rotation d'1 ou 5 2

2 bits vers la gauche. 6 2

7 2
8 2
9 1
10 2
11 2
12 2
13 2
14 2
15 22
16 1

17
 Le DES

Fonctionnement du DES

4. Regroupement des 2 sous-clés.

5. Réduction.
 La sous-clé résultante (56 bits est
réduite) à une sous-clé de 48 bits sur
base de la table suivante.

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

6. Le résultat de cette réduction est la

sous-clé Ki additionnée avec E(R i-1)
18
 Le DES

Génération des clefs

 Le DES

Fonctionnement du DES

Déchiffrement.

 Même algorithme que pour le

chiffrement mais

 Utilisation des clés en ordre inverse K16

puis K15 puis … K1 à la 16ème itération
puisque

Ri1  Li

Li1  Ri  F Li , K i 

K i  G(K,i)
20
Le DES