TD_crypto_DES+RSA
TD_crypto_DES+RSA
TD_crypto_DES+RSA
ARI & GI S3
1 DES simplifié
On considère une simplification de l’algorithme DES dans laquelle les clés et les blocs ont une
taille de 16 bits (au lieu de 64). Les tables utilisées dans cette simplification sont en annexe, à la fin
de ce document (section A). On considère les éléments suivants donnés en notation hexadécimale :
K = 0x1a2b, la clé
M = 0x3c4d, un bloc du texte en clair.
Les conversions entre écritures hexadécimales et binaires se font simplement en utilisant le tableau
de correspondances suivant :
hexa 0 1 2 3 4 5 6 7
bin 0000 0001 0010 0011 0100 0101 0110 0111
hexa 8 9 a b c d e f
bin 1000 1001 1010 1011 1100 1101 1110 1111
1
2. Appliquer l’expansion E sur R0 pour obtenir E(R0) (figure 2).
3. Dériver la première sous-clé K1 (figure 3) ; la rotation à gauche est de 1 bit.
4. Calculer A = E(R0) ⊕ K1, où ⊕ est le ou exclusif (xor).
5. Grouper les bits de A en 2 blocs de 6 éléments et calculer la valeur fournie par la S-Box S1
sur le premier bloc et celle fournie par S2 sur le second bloc (figures 2 et 4).
6. Concaténer les résultats obtenus à la question (5) ci-dessus pour obtenir la suite B de 8
bits.
7. Appliquer la permutation P à B pour obtenir P (B) (figure 2).
8. Calculer R1 = P (B) ⊕ L0.
9. Écrire en hexadécimal le bloc chiffré L1R1 obtenu (figure 1).
2 DES complet
Les tables utilisées dans l’algorithme DES complet sont en annexe, à la fin de ce document
(section B). On considère les éléments suivants donnés en notation hexadécimale :
K = 0x0123456789abcdef, la clé
M = 0x23456789abcdef01, un bloc du texte en clair.
Les conversions entre écritures hexadécimales et binaires se font comme à l’exercice précédent.
1. Calculer les deux sous-blocs de 32 bits L0 et R0 (figure 1).
2. Appliquer l’expansion E sur R0 pour obtenir E(R0) (figure 2).
3. Dériver la première sous-clé K1 (figure 3) ; la rotation à gauche est de 1 bit.
4. Calculer A = E(R0) ⊕ K1, où ⊕ est le ou exclusif (xor).
5. Grouper les bits de A en blocs de 6 éléments et calculer les valeurs fournies par les S-Box
S1, . . . , S8 correspondantes (figures 2 et 4).
6. Concaténer les résultats obtenus à la question (5) ci-dessus pour obtenir la suite B de 32
bits.
7. Appliquer la permutation P à B pour obtenir P (B) (figure 2).
8. Calculer R1 = P (B) ⊕ L0.
9. Écrire en hexadécimal le bloc chiffré L1R1 obtenu (figure 1).
3 RSA
Calculs à la main
On choisit p = 5 et q = 11.
1. Combien vaut n ?
2. Combien vaut φ(n) ?
3. On choisit e = 3 : est-ce correct ? Pourquoi ?
4. Donnez une valeur correcte pour d.
5. Cryptez le message M = 5.
2
FIguRE 1 – Les 16 rondes du DES, où IP est la permutation initiale, FP la permutation finale,
F la fonction de Feistel et ⊕ le ou exclusif (xor).
3
FIguRE 3 – Calcul des sous-clés du DES. La notation <<< désigne des rotations à gauche.
16 14 12 10 8 6 4 2
15 13 11 9 7 5 3 1
A.2 Expansion E
er e
Entrée : 8 bits. Sortie : 12 bits. Le 1 bit de la sortie est obtenu en prenant le 8 bit de l’entrée,
er er
le second en prenant le 1 bit de l’entrée, . . . , le dernier en prenant le 1 bit de l’entrée.
8 1 2 3 4 5
4 5 6 7 8 1
4
A.3 Permutation P
er e
Entrée : 8 bits. Sortie : 8 bits. Le 1 bit de la sortie est obtenu en prenant le 8 bit de l’entrée,
e e
le second en prenant le 4 bit de l’entrée, . . . , le dernier en prenant le 7 bit de l’entrée.
8 4 2 6 1 5 3 7
A.4 Permutation PC 1
er
Entrée : une clé de 16 bits. Sortie : 14 bits. Le 1 bit de la moitié gauche de la sortie est obtenu
e e er
en prenant le 14 bit de la clé, le second en prenant le 12 bit de la clé, . . . Le 1 bit de la moitié
e e
droite de la sortie est obtenu en prenant le 15 bit de la clé, le second en prenant le 13 bit de la
clé, . . .
Moitié gauche (7 bits) Moitié droite (7 bits)
14 12 10 6 4 2 1 15 13 11 9 7 5 3
A.5 Permutation PC 2
er e
Entrée : 14 bits. Sortie : 12 bits. Le 1 bit de la sortie est obtenu en prenant le 10 bit de
e e
l’entrée, le second en prenant le 8 bit de l’entrée, . . . , le dernier en prenant le 2 bit de l’entrée.
10 8 1 6 12 4
13 3 11 5 9 2
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
B.2 Expansion E
er e
Entrée : 32 bits. Sortie : 48 bits. Le 1 bit de la sortie est obtenu en prenant le 32 bit de
er er
l’entrée, le second en prenant le 1 bit de l’entrée, . . . , le dernier en prenant le 1 bit de l’entré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
5
B.3 Permutation P
er e
Entrée : 32 bits. Sortie : 32 bits. Le 1 bit de la sortie est obtenu en prenant le 16 bit de
e e
l’entrée, le second en prenant le 7 bit de l’entrée, . . . , le dernier en prenant le 25 bit de l’entrée.
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
B.4 Permutation PC 1
er
Entrée : une clé de 64 bits. Sortie : 56 bits. Le 1 bit de la moitié gauche de la sortie est obtenu
e e er
en prenant le 57 bit de la clé, le second en prenant le 49 bit de la clé, . . . Le 1 bit de la moitié
e e
droite de la sortie est obtenu en prenant le 63 bit de la clé, le second en prenant le 55 bit de la
clé, . . .
Moitié gauche (28 bits) Moitié droite (28 bits)
57 49 41 33 25 17 9 63 55 47 39 31 23 15
1 58 50 42 34 26 18 7 62 54 46 38 30 22
10 2 59 51 43 35 27 14 6 61 53 45 37 29
19 11 3 60 52 44 36 21 13 5 28 20 12 4
B.5 Permutation PC 2
er e
Entrée : 56 bits. Sortie : 48 bits. Le 1 bit de la sortie est obtenu en prenant le 14 bit de
e e
l’entrée, le second en prenant le 17 bit de l’entrée, . . . , le dernier en prenant le 32 bit de l’entrée.
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
S1
x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x
0yyyy0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0yyyy1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
1yyyy0 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
1yyyy1 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S2
x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x
0yyyy0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
0yyyy1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
1yyyy0 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
1yyyy1 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S3
x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x
0yyyy0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
0yyyy1 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
1yyyy0 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1yyyy1 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
S4
x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x
0yyyy0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
0yyyy1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
1yyyy0 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
1yyyy1 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S5
x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x
0yyyy0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
0yyyy1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
1yyyy0 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
1yyyy1 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
S6
x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x
0yyyy0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
0yyyy1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
1yyyy0 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
1yyyy1 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
S7
x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x
0yyyy0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
0yyyy1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1yyyy0 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
1yyyy1 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
S8
x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x
0yyyy0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
0yyyy1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
1yyyy0 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
1yyyy1 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
FIguRE 4 – Les 8 S-Box. Entrée : 6 bits. Sortie : 4 bits. Par exemple, pour S5 avec l’entrée 011011, on regarde
la case ligne 0yyyy1, colonne x1101x, et on obtient comme sortie 9 i.e. 1001.