Loading
Notes d'étude
Study Reminders
Support
Text Version

Sécurité parfaite

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Fondations de CryptographyProf. Dr. Ashish Choudhury (Former) Infosys Foundation Career Development Chair ProfessorIndian Institute of Technology-BengaluruLecture-04Perfect SecurityHello everyone, welcome to lecture 4. (voir Diapositive #: 00:28) Le plan de cette conférence est le suivant: nous discuterons du secret parfait, qui est la première notion formelle de sécurité, qui est aussi la plus forte notion de secret. Nous allons également discuter de différentes définitions équivalentes du secret parfait (voir Diapositive: 00 :45) Ainsi, la définition de la sécurité parfaite a été donnée par Claude Shannon dans son travail classique en 1948 et Shannon est souvent considérée comme le père de la théorie de l'information et cette notion de sécurité est aussi appelée sécurité inconditionnelle et sécurité de la théorie de l'information. Le modèle d'attaque qui est pris en compte dans la définition de la sécurité parfaite est le modèle d'attaque de chiffrement uniquement, où nous supposons que nous avons un émetteur et un récepteur qui ont convenu d'une valeur de clé aléatoire k. Nous supposons que l'expéditeur a chiffré un seul message à l'aide d'un processus de chiffrement public sous cette clé k, et que le texte a été intercepté par l'adversaire. La partie intéressante de ce modèle d'attaque est que nous supposons ici que l'adversaire est sans limite de calcul. Cela signifie que nous ne faisons aucune supposition sur sa puissance de calcul. Nous supposons qu'il peut effectuer tout type de calcul avec la force brute ou tout autre calcul. C'est donc l'aspect intéressant de ce modèle de sécurité. Informellement, la sécurité parfaite dit que, indépendamment de toute information préalable que l'agresseur a sur le texte sous-jacent, le fait de voir le texte de chiffrement ne lui fournit pas d'informations supplémentaires sur le texte en clair sous-jacent. Cela signifie que le chiffrement est absolument inutile pour l'attaquant. Peu importe ce qu'il pouvait déduire du message à partir du texte chiffré, il aurait déjà pu en déduire avant que n'importe quel texte chiffré aurait été communiqué. Donc ici nous avons 2 entités, nous avons les informations préalables et nous avons le terme pas d'informations supplémentaires. Nous devons maintenant apprendre un peu de maths pour comprendre comment formaliser ces 2notions, c'est-à-dire celles de l'information préalable et qui n'ont pas d'autres informations. (Référez-vous à la diapositive: 02 :36) Donc, imaginez que nous nous sommes donnés un algorithme de chiffrement à clé publique, à savoir un triplet d'algorithme de génération de clé d'algorithmes, un algorithme de chiffrement et un algorithme de déchiffrement. Ensuite, tout agresseur possède les informations suivantes sur le processus de chiffrement. Il connaît trois espaces, à savoir l'espace de message, l'espace de clés et l'espace de texte de chiffrement, où l'espace de message est l'ensemble de tous les messages légitimes qui peuvent être cryptés par le processus de cryptage. L'espace de clés indique toutes les clés possibles qui peuvent être générées par l'algorithme de génération de clé. Et le texte chiffré dénote tous les algorithmes de chiffrement possibles, qui peuvent être générés par l'algorithme de chiffrement. Du point de vue de l'agresseur, tout schéma de chiffrement induit trois distributions de probabilité, une distribution de probabilité sur l'espace de message, une distribution de probabilité sur l'espace de clé et une distribution de probabilité sur l'espace de chiffrement. Alors, allons-nous maintenant sur cette distribution de probabilité un par un. La première distribution de probabilité est au-dessus de l'espace clé et ceci est induit par l'algorithme de génération de clé. Rappelez-vous donc, selon le principe de Kerckhoffs ’, nous supposons que les étapes de l'algorithme de génération de clés, l'algorithme de chiffrement et l'algorithme de déchiffrement sont publiquement connues de l'agresseur. Nous avons aussi discuté que l'algorithme de génération clé doit être un algorithme aléatoire. Cela signifie que chaque fois que nous exécutons l'algorithme de génération de clé, il va générer une clé candidate possible à partir de l'espace clé avec une certaine probabilité. C'est donc ce que nous entendons par la distribution des probabilités sur l'espace clé induit par l'algorithme de génération de clé. De plus, nous avons discuté dans une des conférences précédentes que dans la plupart des cas, l'algorithme de génération de clé va générer une clé uniformément aléatoire à partir de l'espace clé. En effet, si la taille de l'espace de clé est la cardinalité de l'espace clé, toute clé candidate peut être générée avec une probabilité sur l'espace de clé. Donc c'est la distribution uniforme sur l'espace clé, que l'adversaire aura déjà s'il connaît les étapes de l'algorithme de génération de clé. Mais il n'est pas nécessaire que votre algorithme de génération de clé génère toujours des clés uniformément aléatoires à partir de l'espace clé. Donc, cela induirait une autre sorte de distribution de probabilité, quel que soit le cas, puisque les étapes des algorithmes de génération de clés sont connues publiquement. Nous savons que du point de vue de l'attaquant, il y a une distribution de probabilité sur différentes valeurs de clés, ce qui peut se produire avec des probabilités différentes, c'est précisément la distribution de probabilité sur l'espace de texte en clair que l'attaquant a. Nous pouvons aussi saisir mathématiquement ce que nous entendons par aucune information supplémentaire. Formellement, un processus de cryptage, à savoir une collection d'algorithmes de génération de clé, Enc et Dec sur un espace de texte en clair M est appelé parfaitement sécurisé si pour chaque distribution de probabilité sur l'espace de texte en clair et l'espace clé, et pour chaque texte en clair m appartenant à l'espace de texte en clair, selon cette distribution de probabilité, et pour chaque chiffrement c appartenant à l'espace de chiffrement, Pr [ M =? | C =? ] = Pr [ M =? ]. Alors, essayons de comprendre ce que exactement le LHS et le RHS de cette égalité sont pour. Si vous considérez la partie RHS de cette égalité, à savoir Pr [ M =? ], m pourrait être communiqué par l'expéditeur. Il s'agit d'une information préalable sur le texte sous-jacent avant toute communication de l'expéditeur au destinataire, avant que n'importe quel algorithme de génération de clé ait été utilisé, et le message a été chiffré. C'est l'information a priori sur le texte en clair sous-jacent, alors que la partie LHS de cette égalité Pr [ M =? | C =? ] cette probabilité a posteriori que le message m est chiffré dans c. Cela signifie, étant donné que l'adversaire a vu ou intercepté un texte de chiffrement c, quelle est la probabilité que le texte en clair m soit chiffré dans ce texte de chiffrement c. Ainsi, intuitivement, lorsque nous disons que ces 2 probabilités sont égales, cela signifie que tout ce que l'adversaire savait à propos du texte sous-jacent avant tout texte de chiffrement a été communiqué avec la même probabilité que l'adversaire sait qu'un texte ordinaire peut être m et dans le texte de chiffrement donné c. Cela signifie que l'observation du texte de chiffrement c ne change pas les connaissances de l'agresseur sur la distribution du texte en clair. Quel que soit le savoir de l'agresseur, c'est avant de voir le texte chiffré, la même connaissance qu'il a, même après avoir vu le texte chiffré. De plus, elle tient même si l'adversaire n'est pas délimité sur le plan informatique. C'est l'importance de cette définition. Cette définition ne limite pas la puissance de calcul de l'adversaire. Même si l'adversaire connaît les étapes de l'algorithme, même s'il sait ce qui peut être les clés du candidat même s'il est autorisé à faire de la force brute, son point de vue ou ses connaissances sur le texte sous-jacent ou la distribution du texte en clair ne doivent pas changer avant et après avoir vu le texte chiffré. Remarquez que dans cette définition, j'ai mis en évidence peu de choses, à savoir, j'ai dit que la condition devrait tenir pour chaque distribution de probabilité sur l'espace de texte en clair, ce qui signifie qu'il importe peu que la distribution sur un espace de texte en clair soit une distribution uniforme ou une distribution de biais, la condition devrait tenir pour toute distribution de probabilité possible sur l'espace de message. De la même façon, la condition ou l'égalité doit tenir pour n'importe quel type de distribution de probabilité sur l'espace clé, qu'il s'agisse d'une clé générée de façon uniforme, si l'algorithme de génération de clés génère uniformément des clés aléatoires ou des clés de biais encore la condition doit être hold.En outre, une fois que nous avons fixé la distribution de probabilité de l'espace de texte en clair et de l'espace clé, la condition doit tenir pour chaque texte en clair appartenant à l'espace de message et chaque texte chiffré appartenant à l'espace de chiffrement. (Référez-vous à la diapositive: 20 :45) Donc maintenant, ce que nous ferons, c'est que nous verrons un autre équivalent. Définitions pour une sécurité parfaite. C'est la définition originale de la sécurité parfaite donnée par Shannon et l'interprétation de l'égalité de ces 2 probabilités est que la probabilité de savoir un texte en clair reste la même avant et après avoir vu le texte du code de chiffrement. C'est l'interprétation de la définition originale de la sécurité parfaite donnée par Shannon.Maintenant, voyons la première définition alternative. La première définition alternative dit que nous allons dire un processus de cryptage ou un schéma de cryptage pour être parfaitement sécurisé si pour chaque distribution de probabilité sur l'espace de texte en clair et l'espace clé et pour chaque paire de message m0, m1 qui se produit avec une probabilité non nulle par rapport à cette distribution de probabilité et chaque texte de chiffrement c l'égalité suivante doit tenir: Pr [ C =? | M =? 0 ] = Pr [ C =? | M =? 1 ] L'égalité dit que Pr [ C =? | M =? 0 ] est identique à Pr [ C =? | M =? 1 ]. L'interprétation de cette égalité est que la distribution de probabilité du texte de chiffrement est indépendante de ce qui est exactement votre texte en clair. Cela signifie que si l'adversaire voit le texte de chiffrement c sur le canal, peu importe si M =? 0 ou M =? 1 avec une probabilité égale du point de vue de l'agresseur, le texte de chiffrement c doit être un chiffrement candidat de m0 ainsi qu'un chiffrement de candidat de m1.Il ne devrait pas y avoir de biais dans la probabilité. Mais s'il s'agit d'un chiffrement de m0 ou s'il s'agit d'un chiffrement de m1, cela signifie que la distribution du texte doit être indépendante du texte en clair sous-jacent. (Référez-vous à la diapositive: 22 :32) Donc maintenant ce que nous allons faire ensuite, nous allons prouver que ces deux définitions sont équivalentes. À savoir, nous montrerons que s'il y a un processus de cryptage qui satisfait à l'état original de la sécurité parfaite de Shannon, alors le même processus de cryptage doit satisfaire la définition alternative et vice versa. Faisons d'abord la preuve de l'équivalence de la définition en supposant que nous avons un processus de cryptage qui satisfait à la condition d'une autre définition.Nous supposons que nous avons un processus de cryptage où pour chaque distribution de probabilité, Pr [ C =? | M =? 0 ] = Pr [ C =? | M =? 1 ] =?, disons delta, pour toutes les paires de messages m0, m1 dans l'espace de texte en clair, et pour tous les codes de chiffrement c appartenant à l'espace de texte de chiffrement. Compte tenu de cela, nous prouverons que la condition d'origine de la sécurité parfaite du Shannon ’ est également vraie pour le processus de cryptage. | C =? ] = Pr [ M =? ]. Donc ce que nous allons faire, c'est supposer que nous avons un texte en clair arbitraire et un caractère de texte arbitraire. Essons maintenant de calculer le Pr [ M =? | C =? ]. Donc ce que je vais faire ici, c'est que je vais appliquer le théorème de Bayes ici. En appliquant le théorème de Bayes, essayons maintenant de calculer Pr [ C =? ]? La probabilité que votre code de chiffrement soit c va être cette somme. Cet état de résumé indique que vous prenez tous les messages possibles à partir de l'espace de texte en clair et que vous trouvez la probabilité que le message soit le texte en clair de la candidate, à savoir m ’ et que le message est m ’, quelle est la probabilité que m ’ soit chiffré dans c. Cela vous donnera la distribution des probabilités sur le texte de chiffrement c. Parce que ce qu'il faut, en gros, c'est imaginer que vous avez l'espace de texte en clair, vous prenez chacun du texte en clair qui est précisément le premier terme dans cette sommation. Et une fois que vous avez corrigé le texte du candidat, vous calculez simplement ce qui est la probabilité que le texte en clair du candidat vous emportera sur le texte chiffré c, c'est-à-dire ce second terme. Et si vous multipliez tout cela, si ces 2 probabilités et prenez la somme sur l'ensemble du texte en clair, cela vous donnera la distribution de probabilité du texte de chiffrement c. Maintenant, comme dans notre hypothèse de la condition, nous savons que la probabilité conditionnelle que le texte est c étant donné le texte en clair est m ’ est la même pour tous les m ’ à savoir, Pr [ C =? | M =? ’ ] =?, parce que c'est l'hypothèse que nous faisons. Nous partons du principe que notre processus de chiffrement satisfait à l'autre condition. Donc, pour chaque m ’, je peux remplacer le second terme par la sommation?. Par conséquent, j'ai cette forme simplifiée de la summationNous avons calculé la valeur de probabilité de C = c, c'est-à-dire?. Maintenant, essayons de calculer Pr [ C =? | M =? ], c'est la partie numérateur de cette expression RHS. Et encore, selon notre hypothèse de ce théorème, ou de ce lemme, nous savons déjà que Pr [ C =? ] =?. Et c'est indépendamment de ce qui est mon m, il pourrait être m0, il pourrait être m1 il pourrait être m2 pour n'importe quel candidat m de la base de texte en clair, Pr [ C =? ] =?. Donc, cela signifie que la partie numérateur de cette expression RHS est aussi?. Par conséquent, je peux dire que mon LHS original, c'est-à-dire, le Pr [ M =? | C =? ] rien d'autre que cette égalité.Et dans le numérateur ainsi que dans le dénominateur, j'ai le? Je peux l'annuler. Et donc, j'obtiens que cette probabilité conditionnelle n'est rien d'autre que Pr [ M =? ], ce qui est précisément ce que nous voulions prouver. Cela signifie que nous avons prouvé que si le processus de cryptage satisfait à la condition de la définition alternative, il doit aussi satisfaire à l'état de la définition originale de Shannon. Alors, faisons maintenant la preuve dans le sens inverse. (Référez-vous à la diapositive: 27 :54) À savoir, nous supposons que nous avons un processus de chiffrement qui satisfait à l'état de la définition originale de Shannon. C'est le Pr [ M =? | C =? ] = Pr [ M =? ] ∀? M,? ?. Cela prouvera que la distribution du texte de chiffrement est indépendante du texte en clair sous-jacent. Il n'est pas important de savoir si le texte en clair est m0 ou si le texte en clair est m1avec une probabilité égale, il peut conduire au texte de chiffrement c, et cela tient pour chaque paire de messages m0, m1 dans l'espace de texte en clair et chaque texte de chiffrement c à partir de l'espace de texte de chiffrement. Essayons d'abord de calculer Pr [ C =? | M =? 0 ]. Pour cela, nous allons utiliser le fait que selon la condition donnée, puisque le schéma de cryptage satisfait la condition originale de Shannon ’, nous savons que Pr [ C =? | M =? 0 ] = Pr [ M =? 0 ]. Donc maintenant ce que je vais faire, c'est que je vais étendre mon rôle LHS ici en utilisant le théorème de Bayes, où je change simplement le numérateur et le dénominateur de la probabilité conditionnelle. Et en appliquant le théorème de Bayes, j'ai cette égalité. = Pr [ M =? 0 ] Maintenant, ce que je peux faire c'est que je peux annuler ce terme commun à la fois du LHS et du RHS. C'est pourquoi j'ai obtenu ce Pr [ C =? | M =? 0 ] = Pr [ C =? ]. En appliquant la même logique, je peux conclure que Pr [ C =? | M =? 1 ] = Pr [ C =? ]. Par conséquent, le Pr [ C =? | M =? 0 ] et Pr [ C =? | M =? 1 ] sont les mêmes, c'est-à-dire que c'est Pr [ C =? ]. Cela signifie que nous avons prouvé que si la condition d'origine de Shannon est satisfaite, alors le processus de cryptage doit également satisfaire la condition de la définition alternative. Donc, si on vous donne un processus de cryptage et si on vous demande de prouver qu'il est parfaitement sûr ou non, alors vous pouvez le prouver selon la condition originale de Shannon ou vous pouvez le prouver selon la première définition alternative. (Référez-vous Diapositive: 30: 30) Maintenant, voyons une autre définition équivalente de la sécurité parfaite. Avant d'entrer dans cette définition, essayons d'abord de comprendre l'intuition sous-jacente que nous voulons saisir par cette définition. Donc, l'objectif de la sécurité parfaite est le suivant: imaginez un scénario où une clé pour le processus de cryptage a été convenue entre l'expéditeur et le récepteur. Supposons que l'adversaire le sache? { ?0,? 1 } et cela aussi avec une probabilité égale.Supposons que l'expéditeur va chiffrer le message m0 ou m1 avec une probabilité égale. Et il chiffre l'un de ces messages au hasard à l'aide de la clé k selon le processus de chiffrement, calcule le texte de chiffrement c et l'envoie sur le canal. Dis, l'attaquant intercepte le texte de chiffrement c, et l'attaquant a une puissance de calcul non délimitée. Le secret intuitivement parfait exige que les connaissances de l'adversaire sur le texte sous-jacent restent les mêmes même après avoir vu le texte de chiffrement c. Donc, quelle était cette information sur le texte brut avant que n'importe quel texte de chiffrement soit communiqué dans ce cas particulier: avec la probabilité de moitié du point de vue de l'agresseur, le texte en clair pourrait être m0, et avec la probabilité la moitié du texte en clair serait m1. Maintenant le secret parfait exige que même après avoir vu le texte de chiffrement c et même après avoir connu les étapes du processus de cryptage, et même si l'adversaire a une puissance de calcul non bornée, l'avantage que l'adversité obtient après avoir vu le texte de chiffrement et apprendre le texte sous-jacent doit être 0.Cela signifie, même après avoir vu le texte de chiffrement c, la probabilité que le texte de la plaine sous-jacente soit m0 ou m1 devrait être la moitié. Adversary ne peut rien faire mieux que de deviner le texte sous-jacent. C'est l'intuition sous-jacente que nous allons maintenant formaliser (voir Diapositive: 32 :21) Et cette intuition est formalisée par un jeu de réponses défi, que nous appelons cette expérience. Et nous allons voir que dans le reste de ce cours, chaque définition de sécurité va être formalisée par ce genre d'expérience de réponse à un défi ou d'un jeu qui modèle quelque chose que nous voulons, ce qui peut se produire dans la réalité. L'expérience est la suivante: nous supposons que nous sommes donnés un algorithme de chiffrement connu publiquement = (Gen, Enc, Dec), M, et le jeu est joué entre 2entities.La première entité ici est un adversaire ou un algorithme pour l'attaquant que nous dénotent par cet algorithme A et l'algorithme ou l'adversaire est sans limite de calcul. C'est le fait que nous essayons de saisir la notion de secret parfait où l'adversaire n'est pas lié par les calculs. La deuxième entité ici est le vérificateur hypothétique qui va modéliser le sender.Now, la nomenclature que nous allons suivre tout en nommant ce genre d'expériences est la suivante: cette expérience particulière est dénotée? ???? (?, Π) ???. Essons maintenant de décoder chacune des parties individuelles de ce nom compliqué. Ainsi, le nom PrivK indique ici que nous essayons de modéliser une expérience pour un processus de chiffrement symétrique ou un processus de chiffrement de clé privée. C'est pourquoi le nom PrivK, plus tard, lorsque nous essaierons de modéliser l'exigence de sécurité pour les primitives de clé publique. Ce privK sera remplacé par PubK. Le nom de la chaîne eav dénote ici que nous envisageons un adversaire où l'adversaire est seulement autorisé à écouter ou à écouter le texte du code de chiffrement parce que nous sommes dans le texte de chiffrement seulement modèle d'attaque. Le nom A indique le nom de l'algorithme ici et indique le nom du processus de chiffrement par rapport auquel ce jeu sera joué. C'est la nomenclature que nous allons suivre pour désigner cette expérience particulière. Maintenant, quelles sont les règles de ce jeu? Cette expérience sera une expérience randomisée. La première étape est que l'adversaire sélectionne une paire de messages à partir de l'espace de texte en clair, disons m0et m1 avec la restriction que leur taille doit être identique. Un adversaire peut choisir n'importe quelle paire de messages. Il n'y a absolument aucune restriction que nous mettons sur la paire de messages qu'elle peut soumettre au vérificateur. La seule restriction est que leur longueur doit être la même, alors l'adversaire peut déterminiser une paire de message, il peut choisir au hasard une paire de message, il peut utiliser n'importe quelle stratégie pour choisir la paire de message qu'il veut envoyer au vérificateur. Maintenant, une fois que la paire de messages est communiquée au vérificateur, ce que le vérificateur va faire est le suivant: il va exécuter l'algorithme de génération de clé qui va générer une clé uniformément aléatoire ou une clé selon les étapes de l'algorithme de génération de clé pour le vérificateur. Et le vérificateur va choisir au hasard un de ces deux messages pour le chiffrement. L'index du message qui va choisir pour le chiffrement est indiqué par b, qui est trié uniformément au hasard. Cela signifie, avec la moitié de la probabilité, qu'il peut choisir le message m0 pour le chiffrement, ou avec la probabilité qu'il ramasse le message m1 pour le chiffrement. Une fois qu'il a décidé l'index du message, il chiffre ce message mb à l'aide de la clé k qui n'est connue qu'au vérificateur et le texte chiffré est donné à l'adversaire.Et maintenant l'objectif de l'adversaire est de trouver l'index du message qui a été crypté dans c, cela signifie que l'adversaire doit savoir si le c est un chiffrement de m0 ou s'il s'agit d'un chiffrement de m1. Après analyse du texte de chiffrement c selon la stratégie que l'adversaire veut suivre, il leur donne des prédictions. A savoir, elle génère un bit, soit 0 ou 1 correspondant à l'index, ce qui signifie que ce message particulier a été chiffré dans le texte de chiffrement c. Cela signifie que b ’ indique l'index, qui selon l'adversaire est l'index du message qui est chiffré dans le texte chiffré c. C'est l'expérience. Comme vous pouvez le voir, il s'agit d'une expérience randomisée, car l'adversaire peut choisir n'importe quelle paire de messages selon son caractère aléatoire. De la même manière que le vérificateur va choisir n'importe quel message aléatoire de cette paire pour le chiffrement, et la clé peut être n'importe quelle clé aléatoire selon l'algorithme de génération de clé. Maintenant, la sortie de l'expérience est décidée comme suit. Nous disons que la sortie de l'expérience est 1 ou qui est interprétée comme un adversaire a gagné le jeu, s'il a correctement prédit ce qui est exactement le message qui est crypté dans le texte chiffré c. Cela signifie que s'il produit correctement b ’ égal à b, alors nous disons que l'adversaire a gagné cette expérience ou l'adversaire ’ la sortie de l'expérience est 1.En revanche, si l'adversaire identifie de manière incorrecte ce qui est crypté dans ce texte de chiffrement c ce qui signifie qu'il produit b ’ ce qui est différent de b, alors nous disons que la sortie de l'expérience est 0, ce qui est interprété comme l'adversaire a perdu le jeu. Nous avons aussi vu la définition du jeu-baseddefinition, qui modéle l'indistinction parfaite. J'espère que vous avez apprécié cette conférence. Merci !