Cryptosystème de ElGamal

La première étape du schéma de chiffrement consiste à produire une paire de clefs : la clef publique, et la clef secrète. La première servira à chiffrer les messages et la deuxième à les déchiffrer.

• Pour générer sa paire de clefs, Alice va commencer par prendre un groupe cyclique ${\displaystyle G}$ d’ordre q dans lequel le problème hypothèse décisionnelle de Diffie-Hellman est difficile, ainsi qu'un générateur ${\displaystyle g}$ de ce groupe.
• Alice va ensuite tirer un élément ${\displaystyle {\mathsf {sk}}\triangleq x\hookleftarrow U(\mathbb {Z} _{q}^{*})}$ qui va être sa clef privée, et va calculer ${\displaystyle h=g^{x}}$.
• Pour terminer, Alice va publier ${\displaystyle {\mathsf {pk}}\triangleq (G,q,g,h)}$ comme étant sa clef publique.

Bob a donc accès à la clef publique d'Alice : ${\displaystyle {\mathsf {pk}}=(G,q,g,h)}$. Pour chiffrer un message ${\displaystyle m}$ encodé comme un élément du groupe ${\displaystyle G}$, Bob commence par tirer un aléa ${\displaystyle r\hookleftarrow U(\mathbb {Z} _{q}^{*})}$ et va l'utiliser pour couvrir le message ${\displaystyle m}$ en calculant ${\displaystyle c_{2}=m\cdot h^{r}}$. Pour permettre à Alice de déchiffrer le message, Bob va adjoindre à cette partie du message une information sur l'aléa : ${\displaystyle c_{1}=g^{r}}$.

Enfin le chiffré sera composé de ces deux morceaux : ${\displaystyle C=(c_{1},c_{2})}$, et Bob envoie ${\displaystyle C\in G^{2}}$ à Alice.

Ayant accès à ${\displaystyle C=(c_{1},c_{2})}$ et à ${\displaystyle {\mathsf {sk}}=x}$, Alice peut ainsi calculer :

${\displaystyle {\frac {c_{2}}{{c_{1}}^{x}}}={\frac {m\cdot h^{r}}{g^{r\cdot x}}}={\frac {m\cdot {\cancel {g^{x\cdot r}}}}{\cancel {g^{r\cdot x}}}}=m}$

Et est donc en mesure de retrouver le message ${\displaystyle m}$.

En observant les informations publiques : ${\displaystyle g^{x},g^{s}}$; on se rend compte que seuls des éléments de ${\displaystyle G}$ sont rendus visibles et non pas les exposants (ici x et s respectivement). Informellement on peut remarquer que le problème du logarithme discret peut s'interpréter comme le fait qu'il est difficile de retrouver les informations secrètes (${\displaystyle {\mathsf {sk}}=\log _{g}(h)}$ par exemple) qui permettraient de retrouver le message.

De manière plus précise, c'est le problème de décision de Diffie-Hellmann (ou DDH) qui permet de garantir la sécurité sémantique du schéma.

Démonstration

Réduction

En supposant qu'on ait un adversaire ${\displaystyle {\mathcal {A}}}$ contre la sécurité sémantique du chiffrement ElGamal qui gagne avec une probabilité non négligeable ε. Il devient alors possible de construire un adversaire ${\displaystyle {\mathcal {B}}}$ contre DDH, ce qui contredirait la difficulté supposée de ce problème. Cette réduction que l'on vient de décrire va former la preuve de sécurité du schéma.

Pour construire cet adversaire, qui sera appelé dans la suite « la réduction », on suppose qu'il reçoive un triplet DDH : ${\displaystyle (g^{a},g^{b},g^{c})}$, son but est alors de décider si ${\displaystyle c=a\cdot b}$ ou si ${\displaystyle c\in _{R}\mathbb {Z} _{p}}$ avec une probabilité non négligeable. Pour cela il dispose d’une interface avec l'adversaire décrit plus haut face à la sécurité sémantique du cryptosystème ElGamal.

La réduction va donc envoyer à l’adversaire contre ElGamal la clef publique ${\displaystyle {\mathsf {pk}}=(G,q,g,h=g^{a})}$. Au moment de produire le challenge pour l'adversaire contre la sécurité sémantique du cryptosystème, la réduction va envoyer comme chiffré : ${\displaystyle C=(g^{b},m_{i}\cdot g^{c})}$ pour ${\displaystyle i\in \{0,1\}}$ de son choix. Si jamais le triplet est un triplet DDH, c'est-à-dire si ${\displaystyle c=a\cdot b}$, alors ${\displaystyle C=(g^{b},m_{i}\cdot (g^{a})^{b})=(g^{b},m_{i}\cdot h^{b})}$ serait formé comme un chiffré valide pour ElGamal au regard de la clef publique ${\displaystyle {\mathsf {pk}}}$. En revanche, si l'exposant ${\displaystyle c}$ est aléatoire, alors l'adversaire contre ElGamal ne sera pas en mesure de distinguer les deux messages du challenge autrement qu'en répondant au hasard.

On n'a plus qu'à répondre « 1 » (correspondant au fait que le challenger pour DDH a envoyé un triplet DDH) si jamais notre adversaire réussit, et « 0 » (correspondant au fait que le challenger pour DDH a envoyé un triplet aléatoire) dans le cas contraire.

Analyse

On va désormais borner l’avantage de gagner de notre réduction à partir de l’avantage ε de l'adversaire supposé contre notre schéma.

On commence par remarquer que l’on a deux cas: soit le challenge envoyé par notre challenger est un vrai triplet DDH, soit il s’agit d’un triplet tiré uniformément.

${\displaystyle {\begin{aligned}{\textrm {Adv}}^{DDH}({\mathcal {B}})&=|\Pr[{\mathcal {B}}\to 1\mid {\text{DDH}}]-\Pr[{\mathcal {B}}\to 1\mid {\text{Aleatoire}}]|\\&=|\Pr[{\mathcal {A}}\to i\mid {\text{DDH}}]-\Pr[{\mathcal {A}}\to i\mid {\text{Aleatoire}}]|\\&=|\Pr[{\mathcal {A}}\to 0\mid i=0\land {\text{DDH}}]\Pr[i=0]+\Pr[{\mathcal {A}}\to 1\mid i=1\land {\text{DDH}}]\Pr[i=1]-{\frac {1}{2}}|\\&=|{\frac {1}{2}}(1-\Pr[{\mathcal {A}}\to 1\mid i=0\land {\text{DDH}}]+\Pr[{\mathcal {A}}\to 1\mid i=1\land {\text{DDH}}])-{\frac {1}{2}}|\\&={\frac {1}{2}}|-\Pr[{\mathcal {A}}\to 1\mid i=0\land {\text{DDH}}]+\Pr[{\mathcal {A}}\to 1\mid i=1\land {\text{DDH}}]|\\&={\frac {1}{2}}{\textrm {Adv}}^{\text{ElGamal}}({\mathcal {A}})\\&={\frac {\varepsilon }{2}}\end{aligned}}}$

Ainsi on a un avantage qui reste non négligeable : pour atteindre la même sécurité entre DDH et notre cryptosystème, il suffit que le problème DDH reste sûr avec un bit de sécurité supplémentaire.

Dans des modèles avec un attaquant possédant plus de puissance, comme sous attaques à chiffrés choisis, le cryptosystème d'ElGamal n'est pas sûr en raison de sa malléabilité ; en effet, étant donné un chiffré ${\displaystyle C=(c_{1},c_{2})}$ pour le message ${\displaystyle m}$, on peut construire le chiffré ${\displaystyle C'=(c_{1},2\cdot c_{2})}$, qui sera valide pour le message ${\displaystyle 2\cdot m}$.

Cette malléabilité (il s’agit d’un homomorphisme multiplicatif) en revanche permet de l'utiliser pour le vote électronique par exemple[6].

Il existe cependant des variantes qui atteignent la sécurité face aux attaques à chiffrés choisis, comme le cryptosystème de Cramer-Shoup qui peut être vu comme une extension du chiffrement ElGamal.

• [ElGamal 1984] (en) Taher ElGamal, « A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms », Crypto, Springer,‎ 1984 (DOI 10.1007/3-540-39568-7_2, lire en ligne)
• [Katz et Lindell 2014] (en) Jonathan Katz et Yehuda Lindell, Introduction to Modern Cryptography, 2nd Edition, Boca Raton, Chapman and Hall, 2014, 583 p. (ISBN 978-1-4665-7026-9, lire en ligne), « Chapitre 10.5 The El Gamal Encryption Scheme »
• [Menezes, van Oorschot et Vanstone 1996] (en) A. J. Menezes, P. C. van Oorschot et S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996, 810 p. (ISBN 978-1-4398-2191-6, lire en ligne [PDF]), « Chapitre 8.4 ElGamal public-key encryption »
• [Joux et Nguyen 2003] (en) Antoine Joux et Kim Nguyen, « Separating Decision Diffie–Hellman from Computational Diffie–Hellman in Cryptographic Groups », Journal of Cryptology, vol. 16,‎ 2003, p. 239-247 (DOI 10.1007/s00145-003-0052-4)