ENSA (Oujda) Cryptographie - 3éme Année SIC
Année 2020-2021 Dr. [Link]
TD °3 – Confidentialité parfaite, Sécurité Sémantique, Générateurs Pseudo Aléatoires et
Chiffrement par flot
Concepts et définitions
Exercice 1 : Rappelez les définitions suivantes :
Un système de chiffrement inconditionnellement sûr
Utiliser la définition de Shannon
Utiliser le concept de distributions parfaitement t identiques
Un système de chiffrement sémantiquement sûr pour un usage unique de la clé
Utiliser le jeu Challenger-Adversaire pour illustrer cette définition
Utiliser le concept de distributions calculatoirement identiques
Exercice 2 : Rappelez les définitions suivantes :
Un générateur pseudo aléatoire (GPA) prévisible
Un générateur pseudo aléatoire (GPA) imprévisible
Un générateur pseudo aléatoire (GPA) sûr
Un système de chiffrement par flot
Confidentialité Parfaite
Exercice 3 : Soit un entier n strictement positif. Un carré latin d'ordre n est un tableau L
de taille (n x n) contenant les entiers 1, ..., n et tel que chacun des n entiers apparaît
exactement une fois dans chaque ligne et chaque colonne de L. Voici un exemple de carré
latin d'ordre 3:
1 2 3
L= 3 1 2
2 3 1
Etant donné un carré latin L d'ordre n, et le système cryptographique associé (M, C, K, E, D)
où M = C = K = {1,2, ..., n} et pour 1 ≤ i ≤ n, la règle de chiffrement définie par :
E(k = i, m = j) = L(i, j).
Donner une preuve complète qu'un tel système assure une confidentialité parfaite.
Exercice 4 : Montrez le premier théorème de Shannon qui stipule que pour avoir une
confidentialité parfaite il faut que |K| ≥ |M|. Où K est l’espace des clés, M l’espace des
messages clairs et C l’espace des messages chiffrés
Indication : Raisonner par l’absurde et supposez |K| < |M|, supposez aussi pour simplifier
que les messages m de M sont distribués de manière équiprobable et montrez que :
c C / m M : pM [m | c] ≠ pM [m].
Exercice 5 : Soit le système de chiffrement suivant : M = {a, b, c}, K = {k 1, k2, k3} et C
= {1, 2, 3, 4}. Les fonctions de chiffrement et de déchiffrement sont données par le
tableau suivant :
a b c
k1 1 2 3
k2 2 3 4
k3 3 4 1
Sachant que les clefs sont équiprobables et que la distribution des textes clairs est définie
par PM (a) = 1/2, PM (b) = 1/3 et PM (c) = 1/6. Est-ce qu’un tel système de chiffrement
garantit une confidentialité parfaite. Justifier votre réponse.
Indication : calculer PC(c) et PC(c|m) pour différentes valeurs de m et c et comparer
Générateurs Pseudo Aléatoires (GPA)
Exercice 6 : Soit G : {0,1}s → {0,1}n un GPA (Générateur Pseudo-Aléatoire) sûr.
Indiquer si les GPA suivants sont sûrs ou non et expliquer pourquoi.
G’(k) = G(k) || 0 où || est le symbole de concaténation.
G’(k) = G(k) 1n où 1n = 1…1 (n fois) et où est l’addition modulo 2 (Ou
exclusif).
G’(k) = G(k)|0in-2 (c-à-d où l’on fait sauter le dernier bit)
G’(k) = G(k 1s).
G’(k) = G(0s).
G’(k) = G(k) || G(k).
Exercice 7 : Soit G :K → {0,1}n un GPA.
1° Rappelez la définition de l'avantage AvGPA[A, G ] qu'à un test statistique A par rapport
au générateur pseudo aléatoire G.
2° Supposez le GPA G imprévisible/sûr. On définit le nouveau GPA G' par:
G' :K×K K → {0,1}n: G '(k1, k2, k3) = (G (k1) G (k2)) G(k3) où est la
multiplication modulo 2 et l’addition modulo 2.
Considérez le test statistique suivant :A :{0,1}n → {0,1} tel que A(x) = LSB(x), où
LSB(x) représente le bit de poids le plus faible de x (c.-à-d., le plus à droite dans
l’écriture binaire de x).
En Supposant que LSB(G (k)) = 0 pour exactement la moitié des clés k dans K,
déterminer l'avantage AvGPA[A, G' ] de A par rapport à G'.
3° Conclure.
Sécurité sémantique
Exercice 8 : Soit E un système de chiffrement sémantiquement sûr pour un usage unique
de la clé. Une banque utilise ce système pour chiffrer ses données confidentielles mais ne
souhaite pas confier la clé de déchiffrement à un seul agent mais à plusieurs agents de
manière à ce qu’aucun agent ne puisse à lui seul déchiffrer les données, sans le concours
des autres agents. On parle d’un schéma de parage de la clé secrète.
Schéma de partage entre deux agents : Pour ce faire, la clé k (une suite de bits de
longueur s générée de manière aléatoire) est scindée en deux moitiés p 1 et p2. Chaque
moitié est confiée à un agent. En pratique, la banque génère une clé k 1 dans {0, 1}s de
manière aléatoire et calcule k’1 = k k1. La banque confie ensuite p1 = k1 à un agent et p2
= k’1 à un autre agent. Notez que k = k1 k’1.
Schéma de partage entre trois agents : Supposez maintenant que la banque souhaite
utiliser trois agents chacun responsable d’une partie de la clé p 1, p2 ou p3. Elle aimerait
aussi que la procédure de déchiffrement soit possible même si un agent des trois est
absent. Pour ce faire la banque génère 2 couples de clés (k 1, k’1) et (k2, k’2) comme
illustré plus haut de sorte que k1 k’1 = k2 k’2 = k. Comment la banque doit elle
distribuer les parties de la clé pour que 2 agents sur 3 soient puissent déchiffrer mais
qu’un agent seul ne puisse pas le faire ? Indiquez les solutions possibles parmi les choix
suivants :
p1 = (k1, k2), p2 = (k’1), p3 = (k’2)
p1 = (k1, k2), p2 = (k2, k’2), p3 = (k’2)
p1 = (k1, k2), p2 = (k’1, k’2), p3 = (k’2)
p1 = (k1, k2), p2 = (k’1, k2), p3 = (k’2)
p1 = (k1, k2), p2 = (k1, k2), p3 = (k’2)
Exercice 9 : Soit E = (E, D) un système de chiffrement sémantiquement sûr pour un
usage unique de la clé. On suppose que M = C = {0,1}n. Indiquez si les méthodes de
chiffrements suivantes sont sémantiquement sûres pour un usage unique de la clé et
expliquer pourquoi :
E’ (k, m) = ordre inverse (E (k, m))
E’ (k, m) = E (k, m) || k
E’ (k, m) = E (k, m) || LSB(m) où LSB(m) est le bit de poids le plus faible de m.
E’ (k, m) = 0 || E (k, m)
E’ ((k, m), m) = E (k, m) || E (k, m)
E’ (k, m) = E (0n, m)
Exercice 10 : Soit G : {0,1}n → {0,1}2n un GPA. Définissons le système de chiffrement
par flot E = (E, D) par:
k ←R {0, 1}n (choisir k au hasard dans {0,1}n)
Soit m un message clair de {0, 1}2n, alors : c = E (k, m) = m G(k)
Soit c un message chiffré de {0, 1}2n, alors : m = D (k, c) = c G(k)
Répondre par vrai ou faux et justifiez votre réponse :
E est sémantiquement sûr pour un usage unique de la clé, si G est sûr ?
E est inconditionnellement sûr ?
E peut être utilisé en toute sécurité pour chiffrer plusieurs messages avec la même
clé.
L’espace des clés est au moins aussi large que l’espace des messages clairs.
Exercice 11 : Soit E = (E, D) un système de chiffrement défini sur (M, K, C)
1° Que veut dire E est sémantiquement sûr pour un usage unique de la clé dans K.
Utiliser le jeu Challenger-Adversaire pour illustrer la définition.
Supposons E sémantiquement sûr pour un usage unique de la clé avec M = C = K = {0,1}n.
2° Indiquez si les méthodes de chiffrements suivantes sont sémantiquement sûrs pour un
usage unique de la clé et expliquer pourquoi :
E’ (k, m) = (E (k, m)) où est une permutation des positions des bits
E’ (k, m) = E (k1n, m) || MSB(m) où MSB(m) est le bit de poids le plus fort de m
(le plus a gauche dans l’écriture binaire de m).
E’ (k, m) = E (k, m1n)
