Loading
Notes d'étude
Study Reminders
Support
Text Version

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

    +

Foundations of Cryptography Prof. Ashish Choudhury Department of Computer Science International Institute of Information Technology-Bangalore Lecture-49 CCA Secure Public Key Ciphers Based on Diffie-Hellman Problems (référez-vous à la diapositive: 00:33) Bonjour tout le monde. Bienvenue à cette conférence. Le plan de cette conférence est le suivant: lors de cette conférence, nous verrons l'insécurité de l'ACC du cryptosystème de la clé publique d'El Gamal, que nous avions prouvé plus tôt pour être sûr de l'ACP. Ensuite, nous verrons une instanciation du mécanisme d'encapsulation des clés sécurisées de la CCA en fonction des hypothèses de l'écart-CDH. Nous introduisons donc formellement ce qui est exactement l'hypothèse de l'écart-CDH. Et sur la base de cela, nous verrons une instanciation sécurisée de la CCA sur le mécanisme d'encapsulation clé et depuis lors, nous avons vu que, si on vous donne un KEM sécurisé de la CCA, et que vous la combinez avec n'importe quel algorithme de chiffrement à clé symétrique de la CCA, nous pouvons obtenir un système de chiffrement de clé publique hybride sécurisé CCA. Ainsi, en faisant cela, nous obtenterons une version sécurisée CCA d'instanciation de cryptosystème de clé publique hybride basée sur les problèmes Diffie-Hellman et les deux variantes d'une telle instanciation, à savoir les DHIES et les ECIES, nous allons en discuter. (Référez-vous à la diapositive: 01 :26) Commissons donc avec la malleabilité d'El Gamal Cipher. Pour rappel, il s'agit d'une description du processus de cryptage d'El Gamal. L'algorithme de génération de clé génère une clé publique et une clé secrète, où la clé publique est un g α, où α est choisi au hasard à partir de Zq et d'une clé secrète. Pour chiffrer un texte en clair, l'expéditeur calcule d'abord g β, où β est choisi au hasard à partir de Zq. Et puis le message est multiplié par la clé publique (pk) β et (pk) β n'est rien d'autre qu'une clé Diffie-Hellman g α β. Par souci de simplicité, je suppose que mon groupe sous-jacent est un groupe multiplicatif et c'est pourquoi mon c2 est le produit de m et du composant (pk) β. Pour déchiffrer, le récepteur calcule d'abord une clé Diffie-Hellman commune en élevant la partie c1 du texte de chiffrement à la clé secrète et en prenant son inverse multiplicatif et en le multipliant par le composant c2 du texte de chiffrement. Ainsi, l'effet de g α β annule. Et nous avons prouvé que si l'hypothèse de DDH est valable, alors c'est la CPA sécurisée. Alors souvenons-nous que, nous avons aussi discuté dans l'une de nos conférences précédentes la propriété homomorphe des chiffrements El Gamal. Donc El Gamal ciphers, donc ce que nous voulons dire exactement c'est que, supposons que vous êtes donné cryptage cm d'un message inconnu m, puis comme par la syntaxe de l'El Gamal cipher cm sera constitué de deux éléments de groupe. Le premier élément de groupe sera quelques g β (uknonwn β) Et le second composant sera le texte en clair inconnu m multiplié par g α β. Maintenant, si nous prenons le texte de chiffrement et que nous prenons le second composant du texte de chiffrement et multipliez-le par n'importe quelle valeur c du groupe. Ensuite ce que nous obtenons est essentiellement un nouveau texte de chiffrement composé de deux éléments de groupe, qui peut être considéré comme valide El Gamal cryptage du message c times m. Cela signifie que mon processus de cryptage d'El Gamal est malléable, parce qu'en prenant un texte de chiffrement d'un message inconnu, je peux produire un texte chiffré d'un message connexe, à savoir c fois où c est connu de moi, mais le m n'est pas connu de moi, en effectuant seulement quelques opérations locales et il s'avère que si mon processus de cryptage est malléable, alors nous ne pouvons pas espérer qu'il puisse être sécurisé CCA et je vais le démontrer avec un exemple ici. (Référez-vous à la diapositive: 04:05) Donc imaginez, il y a un polytime de l'adversaire arbitraire, qui participe à une instance de jeu CCA contre le chiffrement El Gamal. Ainsi, selon les règles du jeu, le challenger jettera la clé publique à l'adversaire, où la clé publique u est g α, où α n'est pas connu. Ce que fait l'adversaire, c'est qu'il prend une paire arbitraire de texte en clair du groupe. Le défi est préparé par le challenger en choisissant m0 ou m1 pour le chiffrement. Et il soumet un message de chiffrement défi c * à l'adversaire et ce qu'est l'adversaire maintenant, il sait que le défi de chiffrement du texte, qui se compose de deux éléments de groupe, a cette structure: 1 ← et 2 ←. , où β n'est pas connu, le mb réel n'est pas connu et g α β n'est pas connu, mais ce que l'adversaire peut faire est, il peut choisir des x arbitraires du groupe et il peut exploiter la propriété de malleabilité du texte de chiffrement El Gamal. Et il peut maintenant produire un texte de chiffrement modifié comme c, qui est maintenant un chiffrement du message x fois le message inconnu mb et ce que fait l'adversaire maintenant est, il demande le service d'oracle de décryptage pour ce texte modifié c, qui est autorisé selon les règles du jeu CCA. Maintenant, le challenger a à déchiffrer ce texte modifié c et à le décrypter, va renvoyer x * mb à l'adversaire. Maintenant que l'adversaire sait que la valeur de x et x appartient au groupe, il peut calculer l'inverse multiplicatif de la valeur x et en le multipliant par m, il peut identifier complètement ce que mb et donc, il peut soumettre le droit b et comme vous pouvez voir que la probabilité que cette stratégie accusatoire gagne le jeu, le jeu CCA est exactement 1. Cela signifie que mon chiffrement El Gamal n'est pas sécurisé par la CCA. Il n'est sécurisé que par l'ACP. Dès que nous chiffrons un message à l'aide du code de chiffrement d'El Gamal et si nous sommes dans le modèle accusatoire malveillant à l'aide du service d'oracle de décryptage, l'adversaire peut complètement découvrir ce qui est exactement chiffré. (Référez-vous à Diapositive: 06:20) Donc, maintenant, nous devons penser que la façon dont nous pouvons concevoir une instanciation sécurisée de la CCA d'El Gamal, donc ce que nous allons faire, c'est plutôt de voir une version sécurisée de la CCA d'El Gamal, nous allons voir une variante de chiffrement hybride El Gamal, et pour que ce que nous allons faire est, nous allons instancier un KEM sécurisé basé sur des problèmes Diffie-Hellman. Donc, rappelez le mécanisme d'encapsulation de clé sécurisée CPA basé sur l'hypothèse CDH dans le modèle d'oracle aléatoire, que nous avons discuté dans une des conférences précédentes. Alors imaginez Sita veut mettre en place la clé pour son principal mécanisme d'encapsulation. Donc ce qu'elle fait est, elle fait sa part du protocole d'échange de clés Diffie-Hellman une fois pour tout en choisissant une α aléatoire, qui est définie comme sa clé secrète et faisant de g α comme sa clé publique. Cela peut être considéré, ce message g α peut être considéré comme un message une fois pour tous pour chaque expéditeur potentiel qui veut communiquer à elle et maintenant s'il y a Ram qui veut encapsuler la clé, alors l'algorithme d'encapsulation pour Ram sera comme suit. Ram fera sa part du protocole d'échange de clés Diffie-Hellman en choisissant un β aléatoire et en calculant g β, c'est-à-dire l'encapsulation. Et la clé, que Ram obtient ou qui est considérée comme encapsulée dans cette encapsulation c est essentiellement la sortie de (pk) β évaluée sous la fonction de dérivation de clé, qui est accessible au public, où la fonction de dérivation de clé sous-jacente mappe l'élément du groupe cyclique g, à l'espace clé de certains schémas de chiffrement de clé symétrique sous-jacent. Pour décorer c, ce que Sita a à faire est, elle doit faire sa part du protocole d'échange de clés Diffie-Hellman pour obtenir la clé commune g α β et obtenir la sortie de la fonction de dérivation de clé sur ce g α β et ensuite elle peut récupérer la même clé k. Nous avons prouvé que dans le modèle d'oracle aléatoire, si nous supposons que le problème CDH est difficile à résoudre dans le groupe sous-jacent, alors le mécanisme d'encapsulation de clé ci-dessus est sécurisé par l'ACP. Mais il s'avère que le même mécanisme d'encapsulation de clé n'est pas sécurisé par la CCA, même si nous sommes dans le modèle d'oracle aléatoire. C'est parce que si nous supposons qu'il y a un adversaire polytime, qui participe à une instance de jeu CCA contre le mécanisme d'encapsulation de clé ci-dessus, alors le jeu aura l'aspect suivant. Le challenger va générer la clé secrète et une clé publique et utiliser la clé publique, il effectuera une encapsulation pour obtenir l'encapsulation c et la clé encapsulée k. Et il préparera le défi en lançant, en lançant une pièce juste et le défi pour l'adversaire sera u, c, et l'objectif de l'adversaire est d'identifier si est généré selon la méthode b égale à 0 ou selon la méthode b égale à 1. Mais comme nous sommes dans le monde de la CCA, l'adversaire est maintenant autorisé à avoir accès au service oracle de décapsulation. Il peut alors soumettre n'importe quelle encapsulation c ’, ce qui est différent de c et c la déapsulation de la c ’ résultante. Donc ce que l'adversaire peut maintenant faire est, il peut choisir arbitrairement un élément c ’ du groupe et dire que c'est un g β ’ et avec cela, il choisit l'élément aléatoire z ’ du groupe et non seulement cela, il calcule aussi la sortie de la fonction de dérivation de clé sur cet élément choisi au hasard z ’ pour obtenir la clé k ’. Maintenant que l'adversaire est autorisé à avoir le service oracle de décapsulation, il peut demander la décasulation de c ’. Comme c ’ est choisi au hasard parmi le groupe, très probablement c ’ va être différent de c. Même s'il n'est pas différent de c, ce que l'adversaire peut faire est, il peut continuer à sélectionner aléa c ’ et très probablement c ’ sera différent de c dès qu'il obtient le c ’ différent de c, il demande la décasulation de c. Et en réponse, le challenger va générer ce k, et si vous voyez la syntaxe de l'algorithme de décapsulation, cette valeur k n'est rien d'autre que la sortie de la fonction de dérivation de clé sur l'entrée g α β ’, car si c ’ est g β ’, le challenger va d'abord calculer g α β ’, puis mappela l'élément g α β β ’ à un élément de l'espace de clé en exécutant, en calculant la sortie de la fonction de dérivation de clé. Maintenant ce que l'adversaire peut maintenant faire est, il peut demander le service d'oracle de décapsulation pour beaucoup de ces c ’, c'est-à-dire qu'il peut effectuer le même calcul qu'il a fait ici, le nombre de temps polynomial, choisir des c ’ aléatoires, z ’, calculer le k ’ correspondant à z ’ et demander le service de décapsulation du composant c ’ et maintenant qu'il est polynomialement formé, il peut soumettre sa réponse, qu'il soit généré selon la méthode b égale à 0 ou selon la méthode b égale à 1. Maintenant vous vous demandez peut-être que l'avantage supplémentaire de l'adversaire ici est de voir la réponse du service oracle de décapsulation. Si vous voyez ici de près, en voyant la réponse du service oracle de décapsulation, l'adversaire vient apprendre si le triplet (u, c ’, z ’) Est un triplet DDH ou non. Plus précisément, si la réponse du service de décapsulation pour c ’ renvoie la clé k, qui est différente de k ’, que l'adversaire a calculé, alors l'adversaire le sait certainement (u, c ’, z ’) Ne constitue pas un triplet DDH. Parce que, par contre, si en effet (u, c ’, z ’) Est un triplet DDH, alors k aurait été égal à k ’. D'autre part, l'adversaire sait aussi que si k ’ est égal à k, à savoir la réponse qui sort comme la réponse du service oracle de décapsulation correspondant à la requête de l'adversaire, la requête est la même que la réponse k ’, qu'elle a calculée, puis avec une probabilité très élevée, le triplet (u, c ’, z ’) Constitue un triplet DDH. En effet, si (u, c ’, z ’) N'est pas un triplet DDH, c'est-à-dire que ce z ’ est différent de g α β ’, alors il est très peu probable que la dérivation de clé soit fonction de deux entrées différentes, à savoir g α β ’ et certains g γ, où γ est différent de α fois β ’ vous donne la même sortie et cette attente, car nous sommes dans le modèle d'oracle aléatoire, où la fonction de dérivation de clé se comporte comme une fonction vraiment aléatoire. Donc ce que nous pouvons maintenant voir ici, c'est que la façon dont l'adversaire ramasse son service oracle de décapsulation et fait un calcul local puis en comparant la réponse du service oracle de décapsulation, fondamentalement l'adversaire a un accès au solveur DDH, qui lui dit si un triplet soumis constitue un triplet DDH ou non. Cela signifie, juste à partir de l'hypothèse de CDH et de l'hypothèse du modèle Oracle aléatoire, nous ne pouvons pas prouver que cette construction du mécanisme d'encapsulation clé est la DPA sécurisée. Parce que par le service oracle decapsulation, l'adversaire a maintenant accès au solveur DDH et cela nous motive à définir maintenant une nouvelle hypothèse. (Reportez-vous à la page Heure de la diapositive: 14 :47) Ou un nouveau problème difficile, que nous appelons le problème de calcul de l'écart Diffie-Hellmen ou l'hypothèse Diffie-Hellman computationnelle de l'écart, et l'intuition sous-jacente derrière cette hypothèse est que nous avons besoin que le problème CDH soit difficile à résoudre dans mon groupe sous-jacent, même si un adversaire a un accès oracle à un solveur DDH. Je souligne ici qu'il n'a qu'un accès oracle au solveur DDH ; il n'a pas de polytime ; il ne connaissait pas les étapes exactes de ce solveur DDH. La façon dont nous le modélisons ici est la suivante: nous appelons cette expérience comme lacune-CDH et fondamentalement le challenger prépare une instance de problème CDH en choisissant un g α et g β, où α et β ont été choisis au hasard de l'ensemble 0 à q – 1 et le défi pour l'adversaire est de calculer la fonction Diffie-Hellman de cette paire u, v, c'est-à-dire qu'elle doit calculer g α β. Mais maintenant pour modéliser le fait que l'adversaire a un accès oracle à un solveur DDH, nous permettons à l'adversaire de soumettre le nombre polynomial de requêtes de la forme (v, w) et en réponse les sorties challenger 1, si et seulement si le challenger constate que ce composant est effectivement ce v α, à savoir que cette paire (v, w) constitue un triplet DDH à l'égard de l'u, ce que l'adversaire a lancé comme un défi. Et l'adversaire est maintenant autorisé à faire le nombre polynomial de telles requêtes ici et une fois qu'il a fait le nombre polynomial de requêtes, l'objectif de l'adversaire est de calculer la fonction CDH du challenge u, v, qui est jeté à l'adversaire, c'est-à-dire qu'il donne un élément de groupe et la définition de l'expérience est que l'adversaire a gagné l'expérience, que nous dénotent en disant que la sortie de l'expérience est 1, si et seulement si l'adversaire est capable de résoudre le problème CDH, c'est-à-dire qu'il est égal à g α β. Nous disons que l'hypothèse de l'écart CDH tient dans mon groupe sous-jacent g par rapport auquel ce jeu est joué est pour chaque adversaire polytime participant à cette expérience, la probabilité qu'elle gagne l'expérience est bornée par une fonction négligeable. Vous vous demandez peut-être que ce que l'écart de préfixe signifie exactement ici. Eh bien, l'écart signifie ici que nous voulons qu'un problème CDH soit difficile même si le problème de DDH est facile à résoudre dans ce groupe. Cela signifie que nous voulons saisir l'essence de l'existence d'un fossé entre la difficulté du problème du CDH et le problème de la DDH, et il s'avère qu'il y a plusieurs groupes de candidats, où nous pensons que l'hypothèse de la CDH d'anticipation, à savoir le problème de l'écart CDH, est effectivement difficile à résoudre. Par exemple, le groupe basé sur les points sur les courbes elliptiques modulo prime est un de ces groupes de candidats. Vous pouvez également prendre le sous-groupe de premier ordre du groupe multiplicatif Zp *. Dans ces deux groupes de candidats, nous croyons que l'hypothèse de l'écart-CDH tient compte des valeurs suffisamment importantes du paramètre de sécurité. (Référez-vous à la diapositive: 18 :04) Maintenant, voyons comment nous pouvons instancier un mécanisme d'encapsulation clé sous l'hypothèse de l'écart-CDH et il s'avère que la construction n'est pas une nouvelle construction. La construction est exactement la même que celle que nous avons vue, lorsque nous avons discuté d'une instanciation sécurisée CPA du mécanisme d'encapsulation clé sous l'hypothèse du CDH et de l'hypothèse DDH. La seule différence maintenant est que depuis que nous essayons de modéliser un adversaire actif, chaque fois que le récepteur reçoit l'encapsulation c avant de le désensuler, il suffit de vérifier si l'encapsulation c est l'élément de groupe ou non. Parce que, dans l'idéal, si l'encapsulation c vient d'un parti honnête ou d'un expéditeur honnête, comme par les étapes de l'algorithme d'encapsulation, le composant c de l'encapsulation doit être un élément de groupe. D'autre part, si c est en fait venir comme une requête d'oracle de décapsulation, alors ce qu'un adversaire peut essayer de faire est, il peut demander la décapsulation d'un élément, qui n'est pas un élément du groupe et si le récepteur n'effectue pas le contrôle de l'intégrité et procède aveuglément à la décapsuler et renvoyer la sortie, alors il peut conduire à une violation de sécurité ici. C'est donc le seul contrôle supplémentaire que nous faisons ici. Le reste des étapes de l'algorithme de génération de clé, l'algorithme d'encapsulation et l'algorithme de décapsulation sont exactement les mêmes, comme c'était le cas auparavant. Maintenant ce que nous pouvons prouver ici, si l'hypothèse CDH de l'écart tient dans mon groupe sous-jacent, alors cette instanciation du mécanisme d'encapsulation clé est la DPA sécurisée dans le modèle d'oracle aléatoire. Et voyons un aperçu très haut de la preuve. Nous n'allons pas entrer dans les détails formels. Si vous êtes intéressé, vous pouvez voir le livre de Katz & Lindell pour les détails formels. Donc si on pense à n'importe quel adversaire, un adversaire polytime qui participe au jeu CCA contre ce mécanisme d'encapsulation, alors ma prétention est que la décapsulation, les requêtes d'oracle decapsulation, donne fondamentalement à l'adversaire l'accès au solveur DDH et ce que nous avions vu plus tôt, pas vrai. Mais si ma prise de déficit-CDH tient dans le groupe sous-jacent, à droite, alors cela signifie que même si l'adversaire a accès au solveur DDH implicite, le problème CDH reste difficile pour l'adversaire à résoudre. Cela signifie, l'oracle decapsulation, les requêtes de décapsulation ne sont d'aucune utilisation pour l'adversaire. Cela ne l'aiderait pas à résoudre le problème CDH et maintenant ce que nous faisons ici, c'est essentiellement que les requêtes de décapsulation ne sont d'aucune aide pour l'adversaire, alors nous savons déjà qu'en l'absence de requêtes de décapsulation, une instance de jeu CCA contre le mécanisme d'encapsulation clé est exactement la même qu'une instance du jeu CPA contre le même mécanisme d'encapsulation clé, que nous avions déjà prouvé être CPA sécurisé sous l'hypothèse de CDH dans le modèle d'oracle aléatoire. Cela signifie que nous n'avons pas à ajouter d'étapes sophistiquées dans ce mécanisme d'encapsulation des clés existantes pour garantir la sécurité de l'ACC. Ce que nous avons juste à faire, c'est que, nous instancions les étapes de l'algorithme d'encapsulation et de décapsulation dans un groupe où l'hypothèse de l'écart CDH tient et dans l'hypothèse de l'écart tient, nous sommes en sécurité parce que le service oracle de décapsulation est complètement inutile pour l'adversaire et qu'il n'a pas d'avantage supplémentaire par rapport à un adversaire de CPA. (Référez-vous à la diapositive: 21:54) Donc, cela signifie que maintenant nous avons une instanciation du mécanisme d'encapsulation de clé sécurisé CCA, donc ce que nous allons faire, c'est que nous allons l'utiliser pour trouver des versions hybrides sécurisées de la CCA de chiffrements à clé publique basés sur des problèmes Diffie-Hellman et il y a deux instanciations bien connues de ce cadre, on s'appelle DHIES et ECIES et l'idée ici est essentiellement d'utiliser le cadre générique que nous avons discuté lors de la dernière conférence. Lorsque nous avons vu que si on nous donne un mécanisme d'encapsulation de clé sécurisé de la DPA et si on nous donne un processus de chiffrement symétrique à clé symétrique à l'ACC, le processus de chiffrement hybride qui en résulte est protégé par la DPA. Ce que nous devons maintenant faire, c'est que nous devons trouver l'instanciation sécurisée de la CCA du mécanisme d'encapsulation des clés. Ce que nous pouvons faire, c'est que nous pouvons utiliser le mécanisme d'encapsulation clé, qui est la sécurité du CCA basée sur l'hypothèse de l'écart-CDH, que nous venons de voir. Et pour instancier le chiffrement de clé symétrique sécurisé CCA, ce que nous pouvons faire, c'est que nous pouvons utiliser n'importe quel schéma de chiffrement authentifié, que nous avons vu lors de notre discussion sur le processus de chiffrement de clé symétrique, à savoir que nous pouvons utiliser la construction générique basée sur le chiffrement puis l'approche d'authentification, ce qui nous donne toujours la garantie que le schéma qui en résulte est un schéma de cryptage authentifié. Rappelez-vous donc dans le chiffrement, puis authentifie l'approche, nous prenons un processus de chiffrement sécurisé CPA, un processus de chiffrement de clé symétrique et un code d'authentification de message sécurisé et combinons-les à l'aide de ce chiffrement, puis authentifie l'approche, où nous chiffrons d'abord le message à l'aide du chiffrement de clé symétrique sécurisé CPA et le texte de chiffrement qui en résulte est authentifié selon le code d'authentification du message pour obtenir la balise. Et (le texte de chiffrement, balise) est considéré comme le texte global de chiffrement et nous avons prouvé rigoureusement que cette approche générique nous donne toujours un processus de chiffrement symétrique par chiffrement symétrique et nous savons que dans le monde clé symétrique, le chiffrement authentifié implique la sécurité de la CCA, car l'une des conditions du schéma de chiffrement authentifié à satisfaire est que, il devrait avoir la notion de sécurité de la CCA. Pour instancier ce chiffrement de clé symétrique sécurisée CCA, nous pouvons utiliser n'importe quel schéma de chiffrement authentifié. Donc maintenant, nous avons l'instanciation des deux gadgets dont nous avons besoin dans notre système de cryptage hybride. Si nous utilisons ces deux instanciations, nous obtenons ce que nous appelons schéma de cryptage intégré Diffie-Hellman ou DHIES en bref et lorsque nous instancions cette DHIES où le groupe sous-jacent est basé sur les points sur courbe elliptique, alors l'instanciation DHIES résultante est appelée ECIES, à savoir le schéma de chiffrement intégré de courbe elliptique. Il s'agit de deux normes bien connues, qui sont utilisées dans la pratique pour instancier des algorithmes hybrides de clé publique basés sur des problèmes Diffie-Hellman. Cela m'amène à la fin de cette conférence. Pour résumer, dans cette conférence, nous avons vu des instanciations du mécanisme d'encapsulation des clés sécurisées de la CCA. Pour cela, nous avons introduit une notion de "gap-CDH and gap-CDH hypothèse" et nous avons vu que si nous combinons un KEM sécurisé de CCA basé sur l'hypothèse de l'écart-CDH avec n'importe quel schéma de chiffrement authentifié dans le monde de la clé symétrique, qui est la clé symétrique, alors la construction qui en résulte nous donne un processus de chiffrement de clé publique sécurisé CCA, que nous appelons comme