Loading
Notes d'étude
Study Reminders
Support
Text Version

Chiffrement d'El Gamal

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 Dr. Ashish Choudhury Department of Computer Science Indian Institute of Science-Bangalore Lecture-44 El Gamal Public Key Encryption Scheme (Référez-vous à la diapositive: 00:33) Bonjour à tous. Bienvenue à cette conférence. Pour récapitulation, lors de la dernière conférence, nous avons vu la syntaxe du système de chiffrement à clé publique. La feuille de route pour cette conférence est la suivante. Au cours de cette conférence, nous verrons un système de cryptage des clés publiques des candidats, à savoir le système cryptographique à clé publique d'El Gamal, et nous prouverons formellement sa sécurité CPA et nous terminerons la conférence avec certaines des questions de mise en œuvre, auxquelles nous sommes confrontés lors de la mise en œuvre du système de cryptage d'El Gamal dans la pratique. (Voir Diapositive Heure: 00 :56) Alors essayons de comprendre l'intuition du schéma de cryptage d'El Gamal. Pour cela, rappeles-vous le protocole d'échange de clés Diffie – Hellman. Et pour la simplicité, supposons que nous envisageons un groupe cyclique multiplicatif. Les paramètres publics sont donc la description d'un groupe cyclique, d'un générateur et de la taille du groupe, qui est. Et dans le protocole de change Diffie – Hellman, disent Sita et Ram, ils veulent s'entendre sur une clé, chacun d'entre eux ramasser leur propre contribution pour la clé globale. Donc Sita choisit sa contribution, et elle envoie à Ram. Et indépendamment, Ram choisit sa contribution et envoie. Et la clé globale qui est convenue entre l'expéditeur et le récepteur est. Et nous avons officiellement prouvé la sécurité du protocole d'échange de clés Diffie – Hellman. Maintenant, considérons le processus de chiffrement suivant. Ainsi, l'expéditeur et le destinataire exécutent d'abord une instance du protocole d'échange de clés Diffie – Hellman pour obtenir une clé partagée, indiquée par, qui est un élément de groupe. Et nous savons que si l'hypothèse DDH tient dans le groupe sous-jacent, cela signifie que si le problème DDH est difficile à résoudre dans le groupe sous-jacent, alors la clé convenue est indiscernable de n'importe quel élément aléatoire du groupe. Maintenant imaginez, Ram a un message, disons un texte en clair, qui est un élément de groupe, qu'il veut chiffrer et l'envoyer à Sita. Donc ce que Ram peut faire est, du point de vue de Ram, Ram sait qu'en exécutant le protocole d'échange de clés Diffie – Hellman, Sita va aussi avoir la même clé et Ram sait aussi que s'il y a une écoute, qui a des écoutes de la communication entre Sita et Ram, puis du point de vue de cet adversaire, la clé, qui est disponible avec Ram, est une sorte d'indiscernable de n'importe quel élément aléatoire du groupe. Donc ce que Ram peut faire est, pour chiffrer le texte en clair, il peut utiliser la clé pour masquer sa tâche simple et puisque nous exécutons des opérations dans le groupe, pour masquer le texte en clair, ce que Ram peut faire, il peut effectuer l'opération de groupe sur le message et la clé et le résultat est signalé par, qui est également envoyé avec le message, que Ram aurait envoyé dans le cadre du protocole d'échange de clés Diffie – Hellman. Maintenant que Sita reçoit les messages de Ram, elle reçoit maintenant deux éléments du groupe. Le premier élément est la contribution de Ram ’ dans le protocole d'échange de clés Diffie – Hellman, que Sita utilise pour générer la clé selon les étapes du protocole d'échange de clés Diffie – Hellman. Comme une fois qu'elle a reçu la clé, pour déchiffrer le texte de chiffrement, ce que Sita a à faire est, elle doit juste annuler l'effet de la clé ou elle doit démasquer la clé. Et pour démasquer la clé, ce qu'elle peut faire, c'est qu'elle peut effectuer l'opération de groupe sur le texte de chiffrement et l'inverse multiplicatif de l'élément. Donc, puisque l'élément est connu de Sita et qu'elle connaît la description du groupe, elle peut calculer l'inverse multiplicatif en temps polynomial, que je dénote par − 1. Et si elle effectue l'opération de groupe sur le texte de chiffrement et − 1, l'effet de l'annulation. Et Sita finit par obtenir le texte en clair. Maintenant, je veux dire ici que le texte de chiffrement, qui est le résultat de l'opération de groupe sur le texte en clair et la clé, va être indépendant du texte sous-jacent. Je le prouverai très bientôt, mais pour le moment, je suppose que cette affirmation est vraie. Si cette affirmation est vraie, alors tout ce protocole, tout ce processus de cryptage et de décryptage ressemble à un schéma de cryptage des candidats. Parce que si la distribution du texte de chiffrement est indépendante de la clé, alors même après avoir vu le texte de chiffrement, l'adversaire ne sera pas en mesure de comprendre ce qui est exactement chiffré dans, s'il s'agit d'un chiffrement de 0, 1, 2, il ne peut pas comprendre. C'est donc l'intuition globale du système de cryptage d'El Gamal. (Référez-vous à la diapositive: 05 :09) J'ai donc rédigé le schéma directeur du schéma de chiffrement dont j'ai discuté dans la dernière diapositive. La question est maintenant de savoir comment nous pouvons visualiser l'ensemble du processus dont nous venons de discuter en tant qu'instanciation du système de chiffrement à clé publique? Parce que, rappelez-vous, conformément à la syntaxe du schéma de chiffrement à clé publique, nous avons besoin d'un algorithme de génération de clé, qui extrait une paire de clés publiques, de clé secrète, nous devrions avoir un algorithme de chiffrement et nous devrions avoir un algorithme de déchiffrement. Nous savons donc que nous avons maintenant un plan d'un processus de cryptage, mais maintenant nous devons tout mettre dans la syntaxe du processus de chiffrement à clé publique. Et ce processus de visualisation du processus de cryptage en tant qu'instance de chiffrement à clé publique a été identifié par Taher El Gamal. Et c'est pourquoi ce processus de cryptage dont nous allons discuter maintenant est appelé le système de cryptage d'El Gamal. Vous vous demandez peut-être comment il est différent de ce protocole d'échange de clés Diffie – Hellman? Eh bien, nous ne faisons rien d'autre que Diffie – le protocole d'échange de clés Hellman. Donc cette partie de la communication, que j'ai mise en évidence est exactement Diffie – le protocole d'échange de clés Hellman. Mais en plus de cela, nous faisons une communication supplémentaire du côté de l'expéditeur, qui permet au récepteur de déchiffrer le texte du code de chiffrement et de récupérer le texte en clair. Donc ce que nous allons faire, c'est tout le processus de cryptage que nous avons discuté jusqu'à présent visuellement, nous pouvons l'imaginer comme une instance de chiffrement à clé publique comme suit. Nous pouvons donc imaginer que le message du récepteur ’ ici, à savoir le message de Sita ’ dans le cadre du protocole d'échange de clés Diffie – Hellman, est sa clé publique.Et nous pouvons visualiser cela comme si, c'est sa contribution pour le protocole d'échange de clés Diffie – Hellman avec chaque expéditeur potentiel, une fois pour tous. Cela signifie que l'algorithme de generayion clé que Sita peut exécuter ici est le suivant. Dans le cadre de la clé secrète, elle peut choisir au hasard un index de 0 à et elle peut rendre sa clé publique. Et on s'assure qu'il s'agit d'une copie authentifiée. Cela signifie, en effet, cela est généré par le nom de Sita. Comment exactement il est assuré, nous verrons ou résouterons ce problème plus tard. Mais pour le moment, supposons que Sita a généré une clé secrète comme ça et qu'elle a calculé la clé publique pour être et la rendre disponible dans le domaine public. Ensuite, nous pouvons imaginer comme s'il s'agit de sa contribution ou de sa part du message pour le protocole d'échange de clés Diffie – Hellman avec chaque Ram possible, qui voudrait faire une communication sécurisée avec Sita. Maintenant, supposons que nous avons un tel appelé Ram ou un expéditeur qui veut chiffrer un texte en clair, par exemple, en utilisant la clé publique. Donc ce que Ram va faire, Ram va choisir un aléatoire dans l'intervalle 0 à et maintenant il va maintenant calculer deux éléments de groupe. Le premier élément de groupe est 1, ce qui n'est rien d'autre que. Et un deuxième élément de groupe 2 est essentiellement l'opération de groupe effectuée sur le texte en clair et la clé, où la clé est, qui est obtenue en élevant la clé publique à l'index. Donc les deux messages ou les deux éléments que Ram envoie, peuvent être visualisés comme suit. Le premier message, vous pouvez interpréter comme s'il s'agit de la contribution de Ram ’ ou de la contribution de l'expéditeur ’ pour le protocole d'échange de clés Diffie – Hellman, car si Ram aurait participé à une instance du protocole d'échange de clés Diffie – Hellman, alors 1 est le message que Ram aurait envoyé à Sita en réponse au message, que Sita a déjà envoyé et est passé hors ligne. Le deuxième message 2 ou le deuxième élément de groupe 2, vous pouvez imaginer comme s'il masquant le texte en clair avec la clé Diffie – résultante Hellman, que Sita et Ram auraient accepté d'utiliser et comme la transcription du protocole. Donc maintenant, si nous imaginons ce procédé de cryptage en analysant les messages de Sita et Ram comme ceci, alors il s'inscrit automatiquement dans le cadre de notre processus de chiffrement à clé publique. Pour faire le décryptage, ce que Sita a à faire est, à partir du premier élément de groupe, que Ram a envoyé, en utilisant cette clé publique que Sita a déjà envoyée à la dite Ram, Sita peut effectuer ses pas de la Diffie – le protocole d'échange de clés Hellman et accepter ou conserver la même clé, que Ram a utilisé pour masquer le message. Et une fois qu'il récupère la clé, pour déchiffrer le texte de chiffrement, il prend le second composant du texte de chiffrement, à savoir 2 et il exécute l'opération de groupe sur 2 et l'inverse multiplicatif de − 1 pour récupérer le texte en clair. Ma prétention ici est que dans tout ce processus, la distribution du second composant du texte global de chiffrement, à savoir 2 est indépendante du texte sous-jacent. Nous prouverons donc bientôt ce fait, mais maintenant, si nous imaginons tout cela, comme je l'ai dit, vous pouvez maintenant voir que nous avons maintenant une instance de chiffrement à clé publique. (Référez-vous à la diapositive: 10:31) Maintenant, mettons à jour les détails formels du processus de cryptage d'El Gamal. Donc l'espace de texte en clair et l'espace de clé publique vont tous deux être le groupe. Et l'espace secret-clé va être Z, c'est-à-dire qu'il va être l'ensemble { 0, …. Et le texte de chiffrement global sera composé de deux éléments de groupe. Il s'agit donc d'une paire d'éléments du groupe sous-jacent. L'algorithme de génération de clé génère une clé publique et une clé secrète comme suit. La clé secrète est une clé aléatoire comprise entre 0 et une clé publique. Donc, vous pouvez imaginer comme si Sita faisait sa part du protocole d'échange de clés de Diffie – Hellman avec chaque récepteur potentiel une fois pour tous. L'algorithme de chiffrement, que Ram ou n'importe quel expéditeur va suivre pour le chiffrement d'un texte en clair, est le suivant. L'expéditeur choisira un échantillon aléatoire compris entre 0 et 1. Et calculer, c'est le premier composant du texte de chiffrement. Et le chiffrement réel du message est l'opération de groupe effectuée sur le texte en clair et la clé publique élevée au pouvoir. Ainsi, vous pouvez imaginer que le premier composant du texte du code de chiffrement n'est rien d'autre que la contribution de l'expéditeur ’ pour la clé Diffie – Hellman, à laquelle l'expéditeur et le destinataire vont se mettre d'accord. Et le second composant du texte de chiffrement est le masquage du texte en clair avec la clé Diffie – Hellman. Maintenant l'opération de déchiffrement est, vous recevez un texte chiffré composé de deux éléments de groupe. Donc vous calculez d'abord une clé commune de Diffie – Hellman, qui va être établie entre l'expéditeur et le récepteur, en élevant l'élément de groupe 1 à la clé de sécrétion, afin que vous obteniez également, trouvez un inverse multiplicatif. Ensuite, effectuez l'opération de groupe avec le second composant du texte de chiffrement, de sorte que l'effet des éléments disparait et que vous finiez avec le texte en clair. C'est donc la syntaxe formelle du système de cryptage d'El Gamal. Maintenant, nous voulons prouver formellement que ce système de cryptage d'El Gamal est en effet sécurisé par l'AOC. Comme nous en avons discuté lors de la dernière conférence, dans le monde de la clé publique, la sécurité de l'ACO, le message unique CPA security et multi message CPA security sont tous équivalents. Il suffit donc de prouver la sécurité de l'ACO pour ce processus de cryptage. Donc, comme je le revendique au cours des dernières diapositives, la distribution du composant de texte de chiffrement 2, à savoir l'opération de groupe avec la clé Diffie – Hellman, va être indépendante du texte en clair sous-jacent. Cela signifie, du point de vue d'un adversaire délimité par ordinateur, s'il voit 2, puis de son point de vue, 2 pourrait être le résultat de l'application de l'opération de groupe sur n'importe quel. Et si c'est le cas, cela signifie que si cette affirmation est vraie, elle implique automatiquement la sécurité de l'ACO. Intuitivement c'est parce que pour chaque instance de l'algorithme de cryptage dans ce schéma de cryptage d'El Gamal, l'expéditeur va choisir au hasard. Ce n'est pas le cas qu'il choisira la même situation à chaque fois. Et si l'ifis est choisi indépendamment pour chaque instance du chiffrement, cela signifie automatiquement que la clé Diffie – Hellman, qui est utilisée pour masquer le message, sera également indépendante pour chaque instance. En raison de l'ensemble de la clé Diffie – Hellman. Donc même si l'exposant dans le résultat Diffie – Hellman qui en résulte, que l'expéditeur et le récepteur utilisent pour effectuer le chiffrement et le déchiffrement est le même, c'est le qui déclenche le caractère aléatoire ici et depuis est choisi indépendamment ici, pour chaque instance du chiffrement, la clé Diffie – Hellman, qui est utilisée dans chaque instance est indépendante. Et maintenant en supposant que cette affirmation est vraie, cela signifie que la distribution de 2 est indépendante du texte sous-jacent, nous obtenons la sécurité de l'ACO. (Référez-vous à la diapositive: 14:34) Nous formalisons maintenant cette intuition par une preuve rigoureuse. Et avant d'entrer dans la preuve, faisons un chaud ici et réfléchissons à une variante du schéma de cryptage d'El Gamal. Principalement, nous allons envisager une variante parfaitement sécurisée du système de cryptage d'El Gamal. Je souligne ici que ce n'est pas la façon dont nous allons mettre en œuvre le système de cryptage d'El Gamal et ce n'est pas la façon dont nous utilisons le système de cryptage d'El Gamal. Cette variation du schéma de cryptage d'El Gamal dans le cadre de la clé privée est juste pour rendre la preuve plus simple. Donc, le schéma de chiffrement El Gamal modifié dans le paramètre de clé privée, je suis dénotant en tant que Π, possède son propre algorithme de génération de clés, algorithme de chiffrement et algorithme de déchiffrement. Les paramètres publics sont le groupe cyclique, la description de groupe et un élément de groupe uniformément aléatoire, où l'on ne sait pas. Nous pouvons donc imaginer comme s'il s'agit d'une sorte d'ensemble, qui a été fait par un tiers de confiance et qui n'est connu de personne. Comme il s'agit d'un processus de chiffrement de clé symétrique, l'algorithme de génération de clé va générer une clé uniformément aléatoire et la clé est un élément du groupe. Pour chiffrer un message dans cette variante du processus de cryptage d'El Gamal, nous calculons deux éléments de groupe, à savoir 1 et 2. Où 1 est une partie, où est choisi au hasard à partir de l'ensemble Z. Et le texte de chiffrement 2 est essentiellement le masquage du message avec la clé. Puisqu'il s'agit d'un système de chiffrement à clé symétrique, nous allons utiliser la même clé pour le déchiffrement également. Et pour récupérer le texte en clair, nous prenons essentiellement le second composant du texte de chiffrement et effectuez l'opération de groupe par rapport à l'inverse multiplicatif de la clé. Notez que dans cette variante du processus de cryptage El Gamal, le premier composant du texte de chiffrement, à savoir 1 et le public connu, ils ne sont pas du tout utilisés pour le processus de cryptage et pour le processus de décryptage. Mais je les conserve, pour s'assurer que la syntaxe globale du texte de chiffrement que nous obtenons ici ressemble à la même que celle que nous allons obtenir lors de l'instanciation réelle du schéma de cryptage d'El Gamal. Maintenant, je demande ici que la variante de clé privée du processus de cryptage d'El Gamal est parfaitement sécurisée si mon texte sous-jacent est le groupe. Et c'est parce que cette variante de clé privée du système de cryptage d'El Gamal est exactement similaire au schéma de remplissage unique sur le groupe. La seule différence est que dans le schéma de remplissage unique, nous réalisons la XOR de la clé avec le texte en clair. Mais comme nous sommes dans le groupe, nous allons juste remplacer cette opération XOR par l'opération de groupe. Plus formellement, supposons que nous avons un texte de chiffrement arbitraire, disons (1, 2) et nous disons que nous considérons une paire de texte en clair arbitraire, à savoir 0 et 1, qui sont des éléments de groupe, car ici mon espace de texte en clair est le groupe sous-jacent. Je vais montrer que ce processus de cryptage répond à la définition du secret parfait. Il faut considérer la probabilité que ce texte de chiffrement arbitraire (1, 2) soit un chiffrement du texte en clair 0. Et de la même façon, considérons la probabilité que ce texte de chiffrement arbitraire (1, 2) soit un chiffrement de 1. Il s'avère que ce texte de chiffrement arbitraire (1, 2) est un chiffrement de 0, seulement si l'algorithme de génération de clé aurait produit une clé, ce qui est le résultat d'une opération de groupe effectuée sur 2 et l'inverse multiplicatif de 0. Mais comme l'algorithme de génération de clés génère des éléments uniformément aléatoires du groupe comme clé, il s'avère que l'algorithme de génération de clé génère effectivement une clé, qui est identique à 2 opération de groupe 0 − 1 est égal à 1 sur la taille du groupe. Maintenant, en exécutant exactement le même argument, nous pouvons prétendre que la probabilité que le texte en clair 1 soit crypté dans le texte de chiffrement (1, 2) est exactement la même, que mon algorithme de génération de clé génère une clé, qui est la même que l'opération de groupe effectuée sur 2 et 1 − 1.Et la probabilité que ma clé soit celle-ci, est de 1 sur la taille du groupe. Cela signifie que, pour n'importe quel adversaire, même s'il est sans limite de calcul, s'il participe à une expérience d'indistinction parfaitement sécurisée dans le cadre de la clé symétrique ou dans l'expérience de l'ACO, alors la probabilité qu'elle puisse distinguer si elle voit un chiffrement de l'élément de groupe 0 ou si elle voit un chiffrement de l'élément de groupe 1, est exactement la moitié. Cela signifie que vous ne pouvez pas faire de distinction ; avec une probabilité égale, il s'agit d'un chiffrement de 0 ainsi que du chiffrement de 1. Et c'est pourquoi cette variante modifiée ou symétrique du processus de cryptage d'El Gamal est parfaitement sécurisée. (Reportez-vous à la page Heure de la diapositive: 19:38) Passons maintenant à la sécurité de l'ACO du système de cryptage d'El Gamal que nous avons conçu dans le cadre de la clé publique. Donc, avant d'aller plus loin, souvenons-nous encore de ce que nous avons prouvé tout à l'heure. Nous avons donc envisagé une variante du schéma de chiffrement d'El Gamal dans le paramètre de clé symétrique et voici l'algorithme de chiffrement. L'algorithme de chiffrement génère deux éléments de groupe (1, 2), où 1 est aléatoire et 2 le masquage du message. Et à part cela, l'adversaire a aussi une information publique, à savoir, où l'adversaire n'est pas connu. Donc si je considère la vue de l'adversaire, la vue de l'adversaire ’ se compose essentiellement de trois distributions de probabilité, à savoir qu'il a un élément, où est choisi au hasard à partir de Z.Il connaît la valeur de, où est choisi au hasard à partir de Z. Et il connaît le masquage du message avec le texte en clair, où la clé est choisie au hasard à partir du groupe sous-jacent. Et nous avons prouvé que ce processus de cryptage est parfaitement sécurisé. D'autre part, le schéma de chiffrement réel de la clé publique d'El Gamal, que nous avons conçu, il y a aussi le texte chiffré se compose de deux éléments de groupe. Le second composant du texte de chiffrement est le masquage du message avec la clé Diffie – Hellman, à savoir. Par conséquent, si je considère la vue de l'adversaire ’ dans cette instanciation réelle ou l'instanciation réelle du schéma de chiffrement El Gamal dans le paramètre de clé publique, sa vue est la suivante. Il connaît la valeur de, où est inconnu et uniformément aléatoire de l'ensemble Z. Il connaît la valeur de, où est uniformément aléatoire à partir de l'ensemble Z. Et il connaît le masquage du message avec la clé Diffie – Hellman, où la clé Diffie – Hellman n'est rien d'autre que, et elle appartient au groupe sous-jacent. Maintenant, si vous voyez ici de près, qu'est-ce qui diffère exactement ici, si je considère les points de vue des deux adversaires ici? La distribution à la fois dans le monde ou pour les adversaires est parfaitement la même. Elles sont parfaitement indiscerne. Ici aussi l'alpha est aléatoire, ici aussi l'alpha est aléatoire, pas connu de l'adversaire et l'adversaire sait la valeur de. De la même façon, la distribution des deux mondes est exactement identique. Ce qui est différent ici, c'est la nature de 2 que l'adversaire voit dans la variante clé symétrique du schéma d'El Gamal et la distribution de 2, ce que l'adversaire voit dans le schéma de cryptage réel d'El Gamal. Dans le monde clé symétrique, le masquage est avec un élément de groupe uniformément aléatoire, alors que dans la clé publique El Gamal, le masquage du texte en clair est avec la clé pseudo-aléatoire, qui est une clé Diffie – Hellman. Et si je suppose que l'hypothèse DDH se trouve dans mon groupe sous-jacent, alors nous savons que selon les valeurs Diffie – Hellman, Diffie – Hellman triplet et un triplet non Diffie – Hellman, elles sont impossibles à distinguer du point de vue de n'importe quel adversaire délimité par ordinateur. Cela signifie que si je suis uniformément aléatoire, cela signifie que si je suis dans ce cas, alors dans ce cas, c'est un peu, où est totalement aléatoire, non lié à et. Alors que si je considère le texte de chiffrement 2 comme par la clé publique Diffie – Hellman pulic-key de chiffrement d'El Gamal, alors ma clé n'est rien mais si mon adversaire ne peut pas faire la distinction entre un triplet DH et un triplet non DH, alors je peux dire que la distribution du composant de texte de chiffrement 2, que l'adversaire voit dans les deux mondes, est aussi indiscernellement impossible à distinguer et cela prouvera automatiquement que notre processus de cryptage El Gamal est sécurisé par l'AOC. (Référez-vous à la diapositive: 23:45) C'est donc la déclaration officielle que nous allons prouver maintenant. Nous allons prouver que si l'hypothèse DDH tient dans mon groupe sous-jacent, alors le processus de cryptage d'El Gamal est effectivement garanti par l'AOC. Et nous avons formellement établi ce fait en donnant une réduction. Donc supposons que vous avez un adversaire polytime qui peut attaquer votre système de chiffrement de la clé publique d'El Gamal. A l'aide de cette attaque, nous allons concevoir un solveur DDH, un solveur DDH poly time qui peut distinguer un triplet Diffie – Hellman d'un triplet non Diffie – Hellman. Il participe donc à une instance de l'expérience DDH. L'expérience DDH prépare un défi pour le solveur DDH en lui donnant (, où et sont des éléments de groupe aléatoires. Et le troisième élément du triplet est soit, soit il s'agit d'un élément uniformément aléatoire, selon que le challenger a ou. Et la tâche du solveur DDH est de savoir s'il s'agit d'un triplet DH ou d'un triplet non DH. Pour résoudre cela, le solveur DDH appelle notre attaquant, qui peut attaquer le schéma de cryptage d'El Gamal et participe à une instance du jeu COA et il configure la clé publique à être. Maintenant, conformément aux règles du jeu de l'ACO, l'attaquant de l'ACO soumettra une paire de textes en clair à partir du groupe sous-jacent et ce solveur de DDH choisira de façon aléatoire un de ces deux messages et il prépare le texte de l'algorithme de chiffrement comme suit. La deuxième composante du triplet, qui est donnée comme le défi de ce solveur DDH, est définie comme la première composante du texte de chiffrement et le chiffrement réel du message est défini comme, masqué avec le troisième composant du triplet, qui est jeté comme un défi pour le solveur DDH. Alors, avant d'aller plus loin, essayons de comprendre ce qui se passe dans cette réduction globale. Si vous voyez ici que si ce triplet est un triplet non-DDH, cela signifie dans ce cas dans certains, où n'est pas lié à et, puis la distribution du texte de chiffrement (1, 2), qui est donné à cet attaquant contre le schéma El Gamal, a exactement la même distribution si cet attaquant aurait participé au jeu de l'ACO contre la variante de clé symétrique du schéma de cryptage El Gamal. Parce que c'est ainsi que ce type de texte de chiffrement ressemblerait à celui de l'agresseur dans cette expérience. Alors que, si le triplet qui est donné à ce solveur DDH est un triplet DH, alors la distribution de (1, 2) que cet adversaire voit est exactement la même distribution que si cet adversaire aurait pu voir en participant à une instance du jeu COA contre le processus de cryptage El Gamal. Nous revivirons donc sur ce point. Donc maintenant, cet adversaire doit déterminer s'il a vu un chiffrement de 0 ou 1. Donc il soumet sa production. Et la réponse du solveur DDH est que, elle dit qu'elle voit un triplet DH, si et seulement si l'adversaire EG a correctement identifié si elle est 0 ou si elle est 1, qui est cryptée dans le texte de chiffrement challenge (1, 2). Alors, analysons l'avantage, c'est-à-dire avec quelle probabilité ce solveur de DDH va résoudre une instance aléatoire du problème DDH. Je demande donc que si, cela signifie que ce triplet est un triplet non-DDH. Ensuite, la probabilité que mes sorties de solveur DDH de manière incorrecte, à savoir les sorties ′ = 1, est exactement la même avec laquelle cet attaquant de l'ACO aurait gagné le jeu COA contre la variante de clé symétrique du schéma de chiffrement El Gamal. Et nous avons déjà prouvé qu'il s'agit de 1 ⁄ 2. C'est parce que si nous sommes dans le cadre où, alors que j'ai déjà prouvé que le texte de chiffrement, que notre adversaire EG voit, a exactement la même distribution que ce qu'il aurait pu voir en participant à une instance de jeu de l'ACO contre le schéma de cryptage El Gamal modifié. D'autre part, je demande que si mon cas est, alors la probabilité que mon solveur DDH génère ′ = 1 est exactement la même que mon adversaire EG gagne le jeu COA contre le schéma de cryptage El Gamal. Et ceci découle du fait que si nous sommes dans le cas où, alors cela signifie que le triplet qui est donné est un triplet DDH ou un triplet Diffie – Hellman triplet, ce qui signifie que la distribution du texte de chiffrement, quel que soit l'adversaire, est exactement la même que la distribution du texte de chiffrement que cet adversaire aurait pu voir en participant à une instance de jeu de l'ACO contre le schéma de cryptage El Gamal. Donc en résumé, ce que nous concluons maintenant, c'est que, si vous voyez l'avantage distinctif de notre solveur DDH, alors c'est exactement 1 ⁄ 2 moins la probabilité avec laquelle notre adversaire aurait pu gagner le jeu de l'ACO contre le système de cryptage El Gamal. Mais comme je suppose que l'hypothèse de DDH tient dans le groupe sous-jacent, alors je sais que l'avantage distinctif de n'importe quel solveur de DDH est délimité par une probabilité négligeable. Donc je ne connais pas le texte en clair, mais je connais la clé publique et j'ai un cryptage d'El Gamal de ce texte de la plaine inconnue, qui se compose de deux éléments de groupe, que je dénote par et. Et conformément à la syntaxe du processus de cryptage El Gamal, aura cette propriété, donc 1 est le caractère aléatoire sous-jacent utilisé par l'expéditeur. Et de la même façon, imaginez que j'ai un cryptage d'El Gamal ou un texte chiffré d'un message inconnu, à nouveau composé de deux éléments de groupe. Maintenant, supposons que je multipliais la première composante des deux textes de chiffrement. Et indépendamment, je multiplierai le second élément des deux textes de chiffrement. Et ceci produira deux éléments de groupe, qui auront mathématiquement la propriété suivante. Le premier élément de groupe ne sera rien d'autre que le caractère aléatoire de l'alimentation utilisé dans le premier texte de chiffrement ainsi que le caractère aléatoire utilisé dans le second texte de chiffrement. Et le second élément sera le produit des deux textes simples, multiplié par les temps de clé publique de puissance la sommation des deux aléatoires. Et si vous regardez de près, ceci n'est rien d'autre que vous pouvez imaginer comme s'il s'agit d'un texte de chiffrement d'El Gamal pour le texte en clair, sous le hasard 1 + 2. Et c'est pourquoi je dis que mon processus de cryptage d'El Gamal est homomorphe multiplicative. La raison pour laquelle il est homomorphique multiplicatif c'est que si je multiplie deux textes de chiffrement d'El Gamal, alors même sans connaître les textes fondamentaux sous-jacents (je souligne que je ne connais pas les textes de fond sous-jacents et le caractère aléatoire sous-jacent 1 et 2, qui sont utilisés individuellement), j'ai fini par obtenir un texte de chiffrement d'El Gamal d'un texte en clair, à savoir, sous un caractère aléatoire inconnu, à savoir 1 + 2. Donc c'est une sorte de propriété très intéressante du processus de cryptage d'El Gamal. Et plus tard,