République Algérienne Démocratique et Populaire

Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Université Abderrahmane Mira de Béjaia
Faculté des Sciences Exactes

Département d’Informatique
Module : Sécurité 1
Niveau : Master1
Série de TD N°3

Exercice 1

Un groupe de n étudiants souhaite utiliser un système cryptographique pour s’échanger deux

à deux des informations confidentielles. Les informations échangées entre deux membres ne
doivent pas être lues par un autre membre.
Le groupe décide d’utiliser un système de chiffrement Symétrique.
1. Quel est le nombre minimal de clés Symétriques nécessaires ? n*(n-1)/2
Donner un nom d’un système Symétrique connu. DES, RC4 …..
Le groupe décide après d’utiliser un Système de chiffrement Asymétrique.
2. Quel est le nombre minimal de couples de clés Asymétriques nécessaires pour que
chaque membre puisse envoyer et recevoir des informations chiffrées ? n couple de clés
Le groupe décide finalement d’utiliser un système hybride pour le chiffrement(combinaison
entre systèmes Symétrique et Asymétrique).
3. Donner les raisons qui ont poussées ce groupe à utiliser un tel système ;

La cryptographie asymétrique est intrinsèquement lente à cause des calculs complexes

qui y sont associés, alors que la cryptographie symétrique brille par sa rapidité. Toutefois, cette
dernière souffre d'une grave lacune, on doit transmettre les clés de manière sécurisée .
illustrer sous forme d’un schéma un tel système Hybride.

Année universitaire 2011-2012------------------------------------------------------------------------- FARAH.Z & YAHIA CHERIF.Z

1
Exercice2
Dans un système de chiffrement par flot RC4, quel est le problème se sécurité qu’on peut avoir,
si on chiffre plusieurs messages avec une même clé k.

sol
Attaque passive :
● Un attaquant écoute le trafic et va appliquer un XOR entre des données chiffrées avec la
même clé
● on m= et on =
● Les données chiffrées correspondent à :
ci = pi XOR ki ; pour i = 1; 2; : : :
= XOR ki ; pour i = 1; 2; : : :
où les ki correspondent aux bits de la la clé de flux.
FEn faisant un XOR entre les ci et on obtient :
pi XOR pour i = 1; 2; : : :
● L’attaquant connaît alors le XOR des données initiales pi et .
L’attaquant sait alors quels bits (pi , ) sont égaux (ou différents) dans les deux flux.
● Ainsi, pour chaque paire de bits, l’attaquant arrive à réduire la taille de son espace de
recherche de à .

Année universitaire 2011-2012------------------------------------------------------------------------- FARAH.Z & YAHIA CHERIF.Z

2
 ● Avoir plus de trames d’informations permet de réduire l’espace de recherche pour la
détermination de la clé.
● Si =0 alors si on fait un XOR entre les E( ) et E(m) on aura le message claire m.

Exercice3

1-Montrer que le processus de Déchiffrement DES consiste à appliquer le même algorithme

avec l’ordre des clés inversé (k16 au premier tour, k15 au deuxième tour,….k1 au dernier tour) .
Chifffement

Année universitaire 2011-2012------------------------------------------------------------------------- FARAH.Z & YAHIA CHERIF.Z

3
Année universitaire 2011-2012------------------------------------------------------------------------- FARAH.Z & YAHIA CHERIF.Z
4
Supposons que le message est le bloc de 64 bits M et le cryptogramme
reçu par le destinataire C avec, évidemment, les relations
C = EK (M)
et
M = DK (C).
En recevant C et connaissant K, il s’agit, pour le destinataire, de calculer DK (C).
On lit les opérations à effectuer sur le schéma général du DES , mais en faisant les opérations à
l’envers. On commence donc par faire subir aux bits de C la permutation initiale IP pour inverser
la dernière étape du chiffrement. On obtient ainsi le bloc de 64 bits R16L16 (dans cet ordre),
R16 et L16 désignant comme auparavant des « demi-blocs » de 32 bits ; ce sont ces deux blocs
avec les mêmes noms qui sont apparus dans le chiffrement de M avant le passage dans l’inverse
de la permutation initiale. À partir de là, on obtient le bloc L15R15 en, inversant l’opération de
chiffrement par la règle
R15 = L16
et
L15 = R16 XOR f (R15, K16).
Un procédé identique permet de remonter à L14R14 …, puis, finalement, à L0 R0 et à M en
inversant la permutation initiale. Cet algorithme de déchiffrement pourrait donner lieu à un
tableau comme celui explicitant le chiffrement ; la seule différence serait l’ordre d’intervention
des sous-clés : dans le déchiffrement, on fait d’abord intervenir K16 puis K15 … et, enfin, K1.

2-Sachant que la machine spécialisée DES-cracker met en moyenne 4.5 jours pour retrouver par
recherche exhaustive une clé DES de 56 bits, combien de temps mettrait-elle pour retrouver
une clé de 40bits ? 112 bits(3DES) ?

clé 40.
4.5 jours
X

X=

Clé 112 3DES

4.5 jours
X

X=

K = 133457799BBCDFF1 une clé (en hexadécimal).Trouver la clé K1 générée par le DES.

Année universitaire 2011-2012------------------------------------------------------------------------- FARAH.Z & YAHIA CHERIF.Z

5
voir le cour.

Exercice4

Les algorithmes de chiffrement symétrique, dits par blocs, tels que DES, 3DES ou AES, peuvent
être vus comme des boîtes noires prenant en entrée un bloc de données possédant une taille
fixe (64 bits pour le DES) ainsi qu’une clé et retournant un bloc de données chiffrées ayant la
même taille qu’en entrée.

En pratique ces algorithmes de chiffrement sont utilisés par des méthodes de chiffrement
(modes de chiffrement). Le mode le plus basique est appelé ECB (Electronic Code Book). Le
mode ECB, illustré sur la figure 1 avec DES, consiste simplement à découper les données à
chiffrer en n blocs X1 , X2 , X3…..Xn possédant la longueur du bloc de l’algorithme de chiffrement
utilisé (64 bits pour DES) et à chiffrer chaque bloc au moyen de la même clé K, obtenant ainsi les
blocs chiffrés Y1 , Y2 , Y3…..Yn .

Mode ECB avec DES

Question : Expliquer pourquoi ce mode de chiffrement peut fournir certaines informations sur
les données chiffrées (à travers un exemple).

Sol

On chiffre les deux messages suivants avec un mode ECB et un algorithme de chiffrement
par bloc qui travaille avec un bloc de deux caractères à la fois. Ce type de fichier pourrait
correspondre à une liste de salaires.
JOHN__105000
JACK__500000

Le chiffrement sur le premier message donne ceci :

JO|HN|__|10|50|00
Q9|2D|FP|VX|C9|IO

Et sur le deuxième message, on obtient :

JA|CK|__|50|00|00
LD|AS|FP|C9|IO|IO

Année universitaire 2011-2012------------------------------------------------------------------------- FARAH.Z & YAHIA CHERIF.Z

6
 On constate que des paires de caractères apparaissent dans les deux messages chiffrés, il en
va de même dans les messages en clair :

Q9|2D|FP|VX|C9|IO
LD|AS|FP|C9|IO|IO

En partant du principe que John connait son salaire, il pourrait deviner le salaire de Jack car la
séquence "C9" correspond à "50" et "IO" à "00". John en déduit que le salaire de Jack, chiffré
en "C9IOIO" correspond à "500000".

Exercice5

1-Effectuer les calculs suivants en utilisant l’algorithme de calcul (Square-and-multiply)

mod(101) ; mod(101).

2-Calculer les coefficients u et v satisfaisant au+bv=PGCD(a,b), telque : a=6711 et b=831, sur Z.

SOL
279 mod(101) ; 3197 mod(101).

Année universitaire 2011-2012------------------------------------------------------------------------- FARAH.Z & YAHIA CHERIF.Z

7
2-Calculer les coefficients u et v satisfaisant au+bv=PGCD(a,b), telque : a=6711 et b=831, sur Z.

Année universitaire 2011-2012------------------------------------------------------------------------- FARAH.Z & YAHIA CHERIF.Z

8
Exercice6

1-Rappeler le principe de RSA.

2-Montrer que la fonction de chiffrement est bien l’inverse de la fonction de déchiffrement
(D(E(x))=x).
3-Chiffrer le message ‘21’ avec la clé publique (103,143).
4-Sachant que n=11*13, calculer la clé privée associée à la clé publique (103.143).
5-Déchiffrer le message obtenu à la question 3 .

SOL
Solution de l’Exercice5
1-Rappeler le principe de RSA (voir le cours)
2-Montrer que la fonction de chiffrement est bien l’inverse de la fonction de déchiffrement (D(E(x))=x).
Théorème4 :
Soit n=p.q où p et q sont deux nombre premiers distincts.
Alors, pour tout a et k>0 on a : ak(p-1)(q-1)+1 mod n=a (la démonstration se fait par le théorème de
Fermat)

Dans RSA, on a :
φ(n)=(p-1)(q-1)
On choisie un d tel que e*d mod φ(n)=1 ; donc il existe un k>0 tel que :
e*d=k* φ(n)+1………………(1)
De plus, par définitions et propriétés des opérations modulo n, on a :
Dk(Ek(M))=((M)e mod n)d mod n=Me*d mod n ; on remplace e*d par (1), on aura :
Dk(Ek(M))=M k φ(n)+1 = M k* (p-1)(q-1)+1 mod n=M (théorème4)
Et donc : Dk(Ek(M))=M mod n
3-Chiffrer le message ‘21’ avec la clé publique (103,143).
21103 mod 143 =109 ( utilisez Square and multiply)
4-Sachant que n=11*13, calculer la clé privée associée à la clé publique (103,143).
Euclide Etendu on trouve : d=7 ; clé privé (7,143)
5-Déchiffrer le message obtenu à la question 3 .
1097 mod 143=21 (Square and multiply).

Exercice7

On considère un module RSA avec n=pq, où p et q sont les inconnues. Une des méthodes de
cryptanalyse de tel système et la factorisation de n. Montrer simplement que la connaissance
de Φ(n) permet de remonter à la factorisation de n.

solution
Proposition
Année universitaire 2011-2012------------------------------------------------------------------------- FARAH.Z & YAHIA CHERIF.Z
9
La connaissance de Φ(n) est équivalente a la connaissance de la factorisation de N.
Proof.
Si la factorisation de N = p*q est connue alors on peut évidement calculer Φ(n) = (p-1)(q-1).
Réciproquement supposons connu Φ(n) = (p -1)(q-1). On peut remarquer que p et q sont racine
de l’équation du second degré suivante
- (N + 1- Φ(n) )X + N = 0
-(p*q + 1- (p -1)(q-1))X + p*q = 0
Donc p et q peuvent être calculés explicitement.

Année universitaire 2011-2012------------------------------------------------------------------------- FARAH.Z & YAHIA CHERIF.Z

10