Cryptosystème de ElGamal

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.

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

L’article fondateur par Taher 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
 
Chiffrement d'El Gamal.

L'algorithme est décrit pour un groupe cyclique au sein duquel le problème de décision de Diffie-Hellman (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 problème DDH est facile, mais où on n'a pas d'algorithme efficace pour résoudre le logarithme discret[4].

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 ElGamal est souvent utilisé en pratique dans le cadre d'un chiffrement hybride, comme pour sa spécification PGP[2].

Une manière de voir ce schéma de chiffrement, est de faire un parallèle avec le protocole d’échange de clefs de Diffie-Hellman. L’algorithme de chiffrement consiste alors à envoyer un message chiffré   par masque jetable sous la clef partagée  , qui peut-être calculé par Alice vu qu’elle dispose de   (voir illustration ci-contre).

Génération de clefs

modifier

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   d’ordre q dans lequel le problème hypothèse décisionnelle de Diffie-Hellman est difficile, ainsi qu'un générateur   de ce groupe.
  • Alice va ensuite tirer aléatoirement un élément   qui va être sa clef privée, et va calculer   dans  .
  • Pour terminer, Alice va publier sa clef publique  , notée  .

Algorithme de Chiffrement

modifier

Bob a donc accès à la clef publique d'Alice :  . Pour chiffrer un message   encodé comme un élément du groupe  , Bob commence par tirer un nombre aléatoire   et va l'utiliser pour couvrir le message   en calculant  . Pour permettre à Alice de déchiffrer le message, Bob va adjoindre à cette partie du message une information sur l'aléa :  .

Enfin le chiffré sera composé de ces deux morceaux :  , et Bob envoie   à Alice.

Algorithme de Déchiffrement

modifier

Ayant accès à   et à  , Alice peut ainsi calculer :

 

Et est donc en mesure de retrouver le message  .

Sécurité

modifier

Face aux attaques à texte clair choisi

modifier

En observant les informations publiques :  ; on se rend compte que seuls des éléments de   sont rendus visibles et non pas les exposants (ici   et   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 (  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.

Face aux attaques à chiffré choisi

modifier

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é   pour le message  , on peut construire le chiffré  , qui sera valide pour le message  .

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.

Exemple

modifier

Pour l'exemple, on peut prendre le groupe  , avec comme générateur g = 5[7].

Une clef publique possible pourrait donc être:  , et comme clef secrète  .

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   pour nos deux chiffrés, on obtiendra bien 42 en sortie.

Notes et références

modifier
(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).
  1. ElGamal 1984.
  2. a et b RFC4880, (en) « OpenPGP Message Format »
  3. Journal des modifications de GnuPG 2.1
  4. Joux et Nguyen 2003.
  5. Katz et Lindell 2014, Chapitre 10.5 The ElGamal Encryption Scheme.
  6. Belenios, (en) « Spécifications de Belenios »
  7. Ce n'est pas un groupe sûr, ces valeurs ont été prises uniquement pour produire un exemple simple

Annexes

modifier

Bibliographie

modifier