Cryptosystème ElGamal

tbowan

8 Avril 2018

Conçu à partir de l'échange de clé Diffie-Hellman, le chiffrement ElGamal est une alternative libre de droit au standard RSA et qui propose, bonus, une implémentation sur courbes elliptiques.

Introduction

Pour continuer notre périple en cryptographie, je vous propose d'aborder aujourd'hui le Cryptosystème de ElGamal (wikipedia).

Présenté en août 19841 par Taher Elgamal, d'où l'algorithme tiens son nom, il propose un protocole de chiffrement asymétrique construit à partir de l'Échange de clés Diffie-Hellman.

Principe

Le plus simple pour comprendre ElGamal, c'est encore de partir de l'échange de clé Diffie-Hellman. Pour rappel, voici les étapes du protocole :

  1. Alice et Bob se mettent d'accord publiquement sur un groupe (G, ×) et un générateur g ;
  2. Ils choisissent chacun un nombre aléatoire (leur clé secrète), a pour Alice et b pour Bob, ;
  3. Ils calculent leur partie publique et se l'envoie l'un l'autre ; Alice envoie donc ga à Bob et reçoit gb en retour ;
  4. Ils calculent enfin le secret partagé ; Alice calcule gba et Bob calcule gab.
  5. Ils peuvent ensuite utiliser ce secret partagé pour sécuriser leurs communications suivantes.

Pour Elgamal, le protocole est plus simple. Seule Alice ayant besoin d'écrire à Bob, ils peuvent se répartir le protocole et prendre des initiatives.

Pour permettre à tout un chacun de lui envoyer des mots gentils, Bob se charge de la première moitié du protocole :

  • choix du groupe (G, ×),
  • choix du générateur g,
  • choix d'un nombres aléatoire secret b,
  • calcul de la partie publique gb.

Les informations publiques (groupe, générateur et gb) constituent la clé publique et peuvent être envoyées à l'avance à Alice ou carrément publiées sur un annuaire.

Pour envoyer un message à Bob, Alice récupère ces informations publiques et se charge de la seconde moitié du protocole :

  • choix de son nombre aléatoire secret a,
  • calcul de sa partie publique ga,
  • calcul du secret partagé gba,

Alice peut alors se servir du secret partagé pour chiffrer son message. Dans l'article original d'Elgamal, cette opération s'effectue dans un groupe fini additif ou multiplicatif, l'important étant qu'elle soit facilement inversible. C'est habituellement une multiplication qui est choisie.

  • chiffrement du message m′=m.gba

Elle n'a plus qu'à envoyer sa partie publique et le message chiffré à Bob qui pourra le déchiffrer :

  • calcul du secret partagé gab
  • déchiffrement du message m = m′/gab

Système hybride

L'opération de chiffrement et déchiffrement est possible sur des messages arbitrairement longs mais cette opération reste plus lente que les algorithmes de chiffrement symétriques ayant une sécurité équivalente.

On aurait pu remplacer la multiplication par un algorithme symétrique, le secret partagé étant alors la clé de cet algorithme, mais l'usage en a choisi autrement (et a bien fait).

En effet, on préfère utiliser l'algorithme d'Elgamal, inchangé, conjointement à un algorithme symétrique. On parle alors d'algorithme hybdide. On choisi alors une clé pour chiffrer le message et c'est cette clé qui sera chiffrée avec Elgamal.

L'avantage de cette méthode, est de découpler l'algorithme asymétrique qui établi la communication (Elgaml, RSA, ...), et l'algorithme symétrique qui sécurise le contenu (AES, 3DES, ...). Il est alors possible de choisir la combinaison la plus adaptée ou de faire évoluer une partie en fonction des dernières avancées2.

Nonce Reuse

Lorsqu'Alice veut envoyer un message à Bob, elle doit générer un nombre aléatoire secret a spécifique pour le message à envoyer. Elle pourrait bien sûr réutiliser la clé précédente, voir utiliser sa clé secrete mais ce faisant, elle mettrait en péril la sécurité de tous ses échanges.

En effet, admettons qu'Alice envoie deux messages m1 et m2 à Bob en utilisant le même nombre aléatoire a. Bob n'ayant pas changé sa clé publique, le secret partagé (K = gba) sera le même pour le chiffrement des deux messages :

  • m1′=m1.K
  • m2′=m2.K

Admettons maintenant qu'une attaquante (Eve) ai mis la main sur un message en clair3 (prenons m1), elle pourra alors déchiffrer tous les autres essages :

  • m1′/m2′=(m1.K)/(m2.K)
  • m2 = m1.m2′/m1

Mais à ce compte là, elle peut aussi retrouver le secret partagé K :

  • K = m′/m

Heureusement, même en possession des parties publiques et du secret partagé, obtenir les clés privées reste difficile puisqu'il s'agit de résoudre le problème du logarithme discret4.

Attaque sur le chiffré

Tel que défini et utilisé, ce chiffrement possède la propriété de malléabilité : il est possible, dans un certaine mesure, de modifier le message clair en n'opérant que sur le chiffré.

Précisément, l'opération de chiffrement étant une multiplication, multiplier le chiffré par une constante a le même effet que si la multiplication avait eu lieu sur le clair :

  • n.m′=n.m.K = (n.m)′

Si Elgamal est utilisé pour chiffrer un message, et que Eve à la possibilité d'intercepter les communication, elle peut alors modifier le contenu même des messages et en fonction des contextes, en changer le sens à son avantage.

Pour éviter ce type d'attaque, on peut soit ajouter un système de signature au messages ou directement au protocole5.

Si Elgamal est utilisé pour chiffrer une clé symétrique, cette propriété n'a plus trop d'utilité puisque changer la clé symétrique rendra le message illisible, ce que Eve aurait tout aussi bien pu obtenir en remplaçant le message par des données aléatoires.

Enfin, il faut noter que cette propriété n'est pas spécifique à Elgamal mais touche aussi d'autres protocoles comme RSA ou dans une moindre mesure le mode CBC.

Utilisation

Au moment de sa publication, RSA était couvert par un brevet6 et la communauté a été bien contente d'accueillir un nouvel algorithme libre de droits. GnuPG, le clone libre de PGP implémente donc ce cryptosystème pour les échanges de messages.

Elgmal ne proposant pas nativement de méthode de signature7, il n'est pas utilisable pour certaines applications comme SSL/TLS pour lesquels RSA garde l'avantages, surtout depuis l'expiration du brevet en septembre 2000.

Par contre, comme on peut implémenter Elgamal sur n'importe quel groupe fini, une version sur courbes elliptique a pu voir le jours8 et propose, à taille de clé équivalente, une sécurité largement suppérieure.

Pour terminer, voici les recommandations de l'ANSSI9 en matière de ongueur de clés pour les chiffrements asymétriques :

En vrai, on utilise rarement ElGamal, mais sa filiation avec Diffie-Hellman le rend facilement compréhensible et lui permet une implémentation via courbes elliptiques, plutôt à la mode et bien pratique.


  1. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, ElGamal T. Lecture Notes in Computer Science, vol 196. (PDF).

  2. C'est ce qui est fait au travers des cypher suites de TLS et qui a encore été renforcé dans la version 1.3 du protocole.

  3. Ce qui peut arriver plus souvent qu'on le croit... L'attaque Krack sur le WPA2 suit cette même logique (même si le chiffrement utilisé est différent). Forcer les clients WIFI à utiliser un nonce plusieurs fois puis, grâce à la connaissance (partielle) d'un message clair, déchiffrer les autres.

  4. En fait, il s'agit de résoudre le problème de Diffie-Hellman (wikipedia) qui en l'état actuel de nos connaissance est en fait aussi difficile que celui du logarithme discret.

  5. comme avec le cryptosystème de Cramer-Shoup.

  6. brevet US4405829A, valable uniquement aux US parce qu'ayant publié leurs travaux un mois avant la demande de brevet, les autres pays ne l'ont pas jugé recevable.

  7. Techniquement, on utilise alors DSA pour signer. L'algorithme s'inspire d'un algorithme également publié par Taher Elgamal, mais reste différent.

    Contrairement à RSA ou signer et chiffrer nécessitent simplement d'inverser les clés.

  8. Implémentée entre autre par GnuPG

  9. Référentiel Général de Sécurité, Annexe B1, ssi.gouv.fr.