Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Introduction Conﬁdentialité parfaite Chap. IV : La Théorie de Shannon - partie

Introduction Conﬁdentialité parfaite Chap. IV : La Théorie de Shannon - partie 1 : La conﬁdentialité parfaite Laurent Poinsot UMR 7030 - Université Paris 13 - Institut Galilée Cours “ Sécrypt ” Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite En 1949, Claude Shannon publia un article intitulé “ Communication Theory of Secrecy Systems ” dans le Bell Systems Technical Journal qui eut une inﬂuence considérable sur l’étude de la cryptographie. Soixante ans plus tard, on estime que cet article a fondé les bases de la cryptographie moderne. Dans ce chapitre, on détaille plusieurs des idées de Shannon. Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite Sécurité calculatoire Il y a deux approches fondamentales dans l’étude de la sécurité d’un système cryptographique : la notion de conﬁdentialité parfaite de Shannon (que l’on étudie plus loin) et le concept de sécurité calculatoire. La sécurité calculatoire mesure la quantité de calcul nécessaire pour casser un système. On dira qu’un procédé est sûr au sens de la théorie de la complexité si le meilleur algorithme pour le casser nécessite N opérations où N est un nombre beaucoup trop grand pour que cet algorithme soit applicable en pratique. Dans la pratique, on dit souvent qu’un système est sûr si la meilleure attaque connue ne peut se faire avec une quantité raisonnable de temps de calcul. Le problème de cette approche c’est qu’un cryptosystème peut être sûr pendant un moment puis ne plus l’être lorsque l’on découvre un algorithme plus efﬁcace. Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite Sécurité inconditionnelle Ceci mesure la sécurité du système sans borne sur la quantité de calcul que l’attaquant est capable de faire. Un procédé est inconditionnellement sûr s’il ne peut être cassé, même avec une puissance de calcul inﬁnie. Lorsque que l’on étudie la sécurité d’un système cryptographique, on doit également préciser le type d’attaque considéré. On verra au chapitre suivant que le chiffrement par substitution est peu sûr face à une attaque à texte chiffré connu (avec sufﬁsamment de textes chiffrés). On étudie la sécurité inconditionnelle face à une attaque à texte chiffré connu. Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite La sécurité inconditionnelle ne peut évidemment pas s’envisager dans le cadre de la théorie de la complexité, puisque l’on permet une quantité inﬁnie de calculs. Le cadre le mieux approprié est celui de la théorie des probabilités. On utilisera quelques notions élémentaires que l’on rappelle ici. Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite Rappels : Théorie élémentaire des probabilités (1/3) Soit E = {x1, · · · , xn} un ensemble ﬁni. Une probabilité sur E est une application P : E →[0, 1] (1) telle que P(x1) + P(x2) + · · · + P(xn) = 1. Si P(x) = 1, on dit que x est un événement sûr, alors que si P(x) = 0, on dit que x est un événement impossible. Par exemple, on peut déﬁnir la probabilité uniforme sur E par P(x) = 1 n (2) quel que soit x ∈E. Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite Rappels : Théorie élémentaire des probabilités (2/3) Soient E et F deux ensembles ﬁnis (avec la possibilité E = F) munis des probabilités PE et PF respectivement. La probabilité mutuelle P(x, y) est la probabilité que x et y soient réalisés simultanément. La probabilité conditionnelle P(x|y) représente la probabilité de x sachant que y est réalisé. Les probabilités PE et PF sont indépendantes si P(x, y) = PE(x)PF(y) pour tous x, y possibles. La probabilité mutuelle est liée à la probabilité conditionnelle par les formules P(x, y) = P(x|y)PF(y) = P(y|x)PE(x) . (3) Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite Rappels : Théorie élémentaire des probabilités (3/3) À partir des deux précédentes formules on obtient immédiatement le théorème de Bayes : Si PF(y) > 0, on a P(x|y) = PE(x)P(y|x) PF(y) . (4) Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite À partir de maintenant, on suppose qu’une clef donnée est utilisée une et une seule fois dans le chiffrement. Supposons que le texte clair suive une probabilité particulière dans l’espace des textes clairs P. On note PP(x) la probabilité de tirer le texte clair x. On suppose également que la clef K a été choisie (par Alice et Bob) suivant la probabilité PK de l’espace K des clefs. En rappelant que la clef est choisie avant de savoir quel message Alice doit transmettre, on peut raisonnablement supposer que la clef K et le texte clair x sont indépendants. Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite Les deux probabilités sur P et K induisent une probabilité sur l’espace des textes chiffrés C. On peut facilement calculer la probabilité PC(y) que le texte chiffré y soit transmis. Pour une clef k ∈K, C(k) := {Ek(x) : x ∈P} . (5) Ainsi, C(K) représente l’ensemble des textes chiffrés possibles avec la clef k. Pour tout y ∈C, on déﬁnit Cy := {k ∈K : y ∈C(k)}, c’est-à-dire l’ensemble de toutes les clefs possibles qui permettent d’obtenir le chiffré y. On a alors PC(y) = X k∈Cy PK(k)PP(Dk(y)) . (6) Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite L’événement “ le texte chiffré est y ” n’est possible que si on a une clef k ∈Cy et si le message clair x se chiffre (par k) en y, soit encore Ek(x) = y ou x = Dk(y). La probabilité d’obtenir le “ texte chiffré y ” est la somme de toutes les probabilités mutuelles P(x, k). Les événements “ le message clair est x ” et “ la clef est k ” sont supposés indépendants, cette probabilité est égale à PP(x)PK(k), d’où le résultat ﬁnal. Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite On note également que pour tout y ∈C et x ∈P, on peut calculer la probabilité conditionnelle P(y|x) (c’est-à-dire la probabilité que y soit le texte chiffré en sachant que x est le texte clair) par P(y|x) = X k∈Dx,y PK(k) (7) où Dx,y := {k ∈K : x = Dk(y)}. Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite Avec tout cela, on peut maintenant calculer la probabilité conditionnelle P(x|y) (c’est-à-dire la probabilité que x soit le texte clair en connaissant le chiffré y) en utilisant le théorème de Bayes : P(x|y) = PP(x) X k∈Dx,y PK(k) X k∈Cy PK(k)PP(Dk(y)) (8) Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite Exemple (1/5) Voici un petit exemple pour illustrer ce calcul. Soit P = {a, b} avec PP(a) = 1 4 et PP(b) = 3 4. Soit K = {K1, K2, K3} avec PK(K1) = 1 2 et PK(Ki) = 1 4 pour i = 2, 3. Soit C = {1, 2, 3, 4} et supposons que les règles de chiffrement soient déﬁnies par EK1(a) = 1, EK1(b) = 2 ; EK2(a) = 2, EK2(b) = 3 et EK3(a) = 3, EK3(b) = 4. Avec ces données on peut calculer la probabilité PC. Calculons PC(1). On a alors C1 = {k ∈K : ∃x ∈P, Ek(x) = 1} = {K1}. Il en résulte que PC(1) = PK(K1)PP(DK1(1)) = PK(K1)PP(a) = 1 2 × 1 4 = 1 8. Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite Exemple (2/5) Calculons PC(2). On a C2 = {K1, K2}. Il en résulte que PC(2) = PK(K1)PP(DK1(2)) + PK(K2)PP(DK2(2)) = PK(K1)PP(b) + PK(K2)PP(a) = 1 2 × 3 4 + 1 4 × 1 4 = 3 8 + 1 16 = 7 16. Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite Exemple (3/5) En raisonnant de façon identique, on trouve PC(3) = 3 16 + 1 16 = 1 4 et PC(4) = 3 16. Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite Exemple (4/5) On peut également calculer la probabilité conditionnelle du texte clair en connaissant le texte chiffré. Regardons le cas x = a et y = 1. On a Da,1 = {k ∈K : a = Dk(1)} = {K1}. Il nous sufﬁt d’appliquer l’une des formules vues précédemment (car on connaît PC). On obtient donc par le calcul, P(a|1) = 1. Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite Exemple (5/5) De façon identique on obtient P(a|2) = 1 7 ; P(a|3) = 1 4 ; P(a|4) = 0 ; P(b|1) = 0 ; P(b|2) = 6 7 ; P(b|3) = 3 4 ; P(b|4) = 1. Laurent Poinsot Chap. IV : La théorie de Shannon Introduction Conﬁdentialité parfaite Conﬁdentialité parfaite : approche intuitive On peut maintenant déﬁnir la notion de conﬁdentialité parfaite. Intuitivement, il y a conﬁdentialité parfaite si un adversaire n’obtient aucune information sur le texte clair en observant seulement uploads/Philosophie/ chap4-print.pdf