Cryptosystème de ElGamal

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le cryptosystème d'ElGamal, ou chiffrement El Gamal (ou encore système d'El Gamal) est un protocole de cryptographie asymétrique inventé par Taher Elgamal en 1984[1] et construit à partir du problème du logarithme discret. Il possède la particularité d'être probabiliste, ce qui permet d’effectuer les preuves de sécurité sans avoir à recourir à de la complétion[2].

Ce protocole est utilisé par le logiciel libre GNU Privacy Guard[3] dont les versions récentes implantent jusque sa version sur les courbes elliptiques[4]. Contrairement au chiffrement RSA, il n’a jamais été sous la protection d’un brevet.

L’article séminal d'Elgamal présente un protocole de chiffrement, mais aussi une signature numérique, qui malgré leurs similarités (ils sont tous deux construit sur le problème du logarithme discret) ne sont pas à confondre. Cet article traite uniquement du protocole de chiffrement.

Description de l’algorithme[modifier | modifier le code]

L'algorithme est décrit pour un groupe cyclique fini au sein duquel le problème de Décision de Diffie-Hellman (en) (DDH) est difficile. Des informations plus précises sont données dans la section Résistance aux attaques CPA.

On peut remarquer que DDH est une hypothèse de travail plus forte que celle du logarithme discret, puisqu’elle tient si jamais le problème du logarithme discret est difficile. Il existe par ailleurs des groupes où le décider DDH est facile, mais où on n'a pas d'algorithme efficace pour résoudre le logarithme discret.[5]

Comme il s'agit d'un schéma de chiffrement asymétrique, le cryptosystème est composé de trois algorithmes (probabilistes) : GenClefs, Chiffrer et Déchiffrer.

Pour l'illustration, on va considérer que Bob veut envoyer un message à Alice. Mais ce message contient des informations sensibles, Bob ne veut donc pas qu'il soit compréhensible par une autre personne qu'Alice. Ainsi Bob va chiffrer son message.

Comme les schémas de chiffrement asymétrique sont en règle générale plus lents que leurs analogues symétriques, le chiffrement El Gamal est souvent utilisé en pratique dans le cadre d'un chiffrement hybride, comme pour sa spécification PGP[3].

Génération de clefs[modifier | modifier le code]

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 G d’ordre p dans lequel le problème DDH (en) est difficile, ainsi qu'un générateur g de ce groupe.
  • Alice va ensuite tirer un élément sk \triangleq x \in_R \mathbb{Z}_p^* qui va être sa clef privée, et va calculer  h = g^x .
  • Pour terminer, Alice va publier pk \triangleq (G, p, g, h) comme étant sa clef publique.

Algorithme de Chiffrement[modifier | modifier le code]

Bob a donc accès à la clef publique d'Alice : pk = (G, p, g, h). Pour chiffrer un message m encodé comme un élément du groupe G, Bob commence par tirer un aléa r \in_R \mathbb{Z}_p^* et va l'utiliser pour couvrir le message m en calculant 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 : c_1 = g^r.

Enfin le chiffré sera composé de ces deux morceaux : C = (c_1, c_2), et Bob envoie C \in G^2 à Alice.

Algorithme de Déchiffrement[modifier | modifier le code]

Ayant accès à C=(c_1, c_2) et à sk=x, Alice peut ainsi calculer :

\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 m.

Sécurité[modifier | modifier le code]

Face aux attaques à texte clair choisi[modifier | modifier le code]

En observant les informations publiques : g^x, g^s; on se rend compte que seules des éléments de 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 (sk = \log_g(h) par exemple) qui permettraient de retrouver le message.

De manière plus précise, c'est le problème DDH qui permet de garantir la sécurité sémantique du schéma.


Réduction[modifier | modifier le code]

En supposant qu'on ait un adversaire contre la sécurité sémantique du chiffrement El Gamal qui gagne avec une probabilité non négligeable ε. Il devient alors possible de construire un adversaire contre DDH, ce qui contradirait la difficultée 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, que nous appellerons dans la suite notre réduction, on suppose qu'il reçoive un triplet DDH : (g^a, g^b, g^c), son but est alors de décider si c = a \cdot b ou si c \in_R \mathbb{Z}_p avec une probabilité non négligeable.

Notre réduction va donc envoyer à l'adversaire contre ElGamal la clef publique pk=(G, p, g, h=g^a). Au moment de produire son challenge, la réduction va envoyer comme chiffré : C = (g^b, m_i \cdot g^c). Si jamais c=a \cdot b, alors C = (g^b, m_i \cdot (g^a)^b) = (g^b, m_i \cdot h^b) sera formé comme un chiffré valide pour El Gamal au regard de la clef publique pk. En revanche, si l'exposant c est aléatoire, alors l'adversaire contre El Gamal 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 « DDH » si jamais notre adversaire réussis, et « Aléa » dans le cas contraire.

Analyse[modifier | modifier le code]

On va désormais borner la probabilité de gagner de notre réduction à partir de la probabilité de gain ε 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. Par la formule des probabilités totales, en appelant W l’événement « Notre réduction gagne. », on obtient :

\begin{align}
\Pr[W] & = \Pr[W \mid \text{DDH}] \cdot \Pr[\text{DDH}] + \Pr[W \mid \text{Aléatoire}] \cdot \Pr[\text{Aléatoire}] \\
       & \geq \Pr[W \mid \text{DDH}] \cdot \Pr[\text{DDH}] \\
       & = \frac{\varepsilon}{2}.
\end{align}

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.

Face aux attaques à chiffré choisi[modifier | modifier le code]

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é C=(c_1, c_2) pour le message m, on peut construire le chiffré C' = (c_1, 2\cdot c_2), qui sera valide pour le message 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 (en) qui peut être vu comme une extension du chiffrement ElGamal.

Exemple[modifier | modifier le code]

Pour l'exemple, on peut prendre le groupe G = (\Z/100000007\Z^*, \times), avec comme générateur g=5 (Mise en garde: ce n'est pas un groupe sûr, ces valeurs ont été prises uniquement pour produire un exemple simple).

Une clef publique possible pourrait donc être: pk=(G,100000006,5,29487234), et comme clef secrète sk=81996614.

On remarquera que comme le chiffrement est un algorithme probabiliste, il y a différentes sorties possibles pour le même message. Un chiffré possible pour le message 42 pourrait donc être (58086963, 94768547), mais aussi (83036959, 79165157) pour les aléas r valant 6689644 et 83573058 respectivement.

Néanmoins, si on fait le calcul \dfrac{c_2}{c_1^{sk}} pour nos deux chiffrés, on obtiendra bien 42 en sortie.

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « ElGamal encryption » (voir la liste des auteurs).

Références[modifier | modifier le code]

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (en) Taher ElGamal, « A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms », Crypto, Springer,‎ (DOI 10.1007/3-540-39568-7_2)
  • (en) A. J. Menezes, P. C. van Oorschot et S. A. Vanstone, Handbook of Applied Cryptography, CRC Press (lire en ligne [PDF]), « Chapter 8.4 ElGamal public-key encryption »
  • (en) Antoine Joux et Kim Nguyen, « Separating Decision Diffie–Hellman from Computational Diffie–Hellman in Cryptographic Groups », Journal of Cryptology, vol. 16,‎ , p. 239-247 (DOI 10.1007/s00145-003-0052-4)