ElGamal

Portail > Algorithmes

ElGamal (1985) est un schéma de chiffrement à clé publique fondé sur le logarithme discret, étroitement lié à Diffie-Hellman. Sa variante de signature a donné naissance à DSA.

Clés

Paramètres publics : un générateur g et un module premier p.

• Clé privée : un entier x.
• Clé publique : y = gˣ mod p.

Chiffrement

Pour chiffrer un message m, l'émetteur tire un aléa k et calcule :

c1 = gᵏ mod p
c2 = m · yᵏ mod p
chiffré = (c1, c2)

Le destinataire retrouve m grâce à sa clé privée : m = c2 · (c1ˣ)⁻¹ mod p.

Propriétés

• Probabiliste : grâce à l'aléa k, un même message chiffré deux fois donne des chiffrés différents — bonne propriété de sécurité.
• Expansion : le chiffré est environ deux fois plus gros que le clair (deux composantes).
• Aléa critique : k doit être unique et imprévisible à chaque chiffrement ; sa réutilisation compromet la confidentialité (même piège que les nonces).

Usage

Moins répandu que RSA, ElGamal a été notamment utilisé dans GnuPG/PGP. Son intérêt aujourd'hui est surtout théorique et historique : il éclaire le lien entre log discret, chiffrement et signature, et reste une brique conceptuelle (chiffrement homomorphe, schémas avancés).

Lien avec DSA

La variante de signature d'ElGamal a inspiré DSA, qui en est une optimisation normalisée. On retrouve dans les deux la dépendance critique à un aléa par opération.

Sécurité

• Repose sur le log discret → mêmes exigences de taille que DH.
• Sensible à la réutilisation ou la prévisibilité de l'aléa k.
• Cassé par Shor (Cryptographie asymétrique et post-quantique).

Points clés à retenir

• Chiffrement à clé publique fondé sur le log discret, proche de Diffie-Hellman.
• Probabiliste (bon), mais chiffré ~2× plus gros et aléa k critique.
• Surtout historique (GnuPG) ; sa variante de signature a donné DSA.

Voir aussi

• Diffie-Hellman et ECDH
• DSA
• RSA
• Problèmes mathématiques difficiles