chiffre ElGamal

Alice laisse un cadenas ouvert à la disposition de tous, mais garde seule la clé qui l'ouvre. Bob peut ainsi enfermer son message sans avoir rencontré Alice pour échanger un secret. Avec ElGamal, ce cadenas est un calcul public dans un ensemble fini de nombres.

Bob ajoute à chaque chiffrement un nombre choisi au hasard. Le même message ne prend donc pas toujours la même apparence. Alice combine sa clé secrète avec la première moitié du chiffré pour annuler ce masque et retrouver le message.

Le chiffre ElGamal, proposé par Taher ElGamal en 1985, est un schéma de chiffrement asymétrique dans un groupe cyclique fini. Dans la présentation modulo un nombre premier, Alice choisit un nombre premier p, une racine primitive g modulo p et un exposant secret a. Elle publie p, g et le nombre α défini par $\alpha =g^{a}p\backslash alpha=g^a\backslash bmod\; p$, mais conserve a.

Pour chiffrer un message représenté par un élément non nul m modulo p, Bob choisit un nouvel exposant aléatoire b. Il produit deux composantes : $(\beta ,c)=(g^b,{\alpha }^{b}m)p(\backslash beta,c)=(g^b,\backslash alpha^b\; m)\backslash bmod\; p$. Alice calcule le même masque sous la forme β^a, puis le retire grâce à son inverse. Dans la notation de la source, elle peut aussi poser x = p − 1 − a et calculer β^xc modulo p.

Retrouver a à partir de p, g et α demande de résoudre un logarithme discret, supposé difficile lorsque les paramètres sont assez grands. Chaque chiffré contient deux éléments du groupe, d'où une expansion par rapport à un message représenté par un seul élément. Le lien exact entre cette difficulté et celle de casser le chiffrement demande toutefois des hypothèses supplémentaires : la source précise qu'aucune équivalence stricte n'est prouvée. ElGamal possède aussi une construction de signature. DSA est un schéma de signature standardisé et apparenté, mais distinct de la construction de signature ElGamal.

Alice et Bob travaillent modulo p = 23, avec la racine primitive g = 5. Alice choisit l'exposant secret a = 6 ; Bob veut chiffrer le message m = 10 et choisit l'exposant aléatoire b = 3.

1. Clé publique. Alice calcule α = 5⁶ mod 23 = 8. Sa clé publique est donc (23, 5, 8).
2. Première composante. Bob calcule β = 5³ mod 23 = 10.
3. Masque et seconde composante. Il obtient α³ mod 23 = 8³ mod 23 = 6, puis c = 6 × 10 mod 23 = 14. Il envoie (10, 14).

4. Déchiffrement. Alice retrouve le masque par β^a mod 23 = 10⁶ mod 23 = 6. L'inverse de 6 modulo 23 vaut 4, car 6 × 4 = 24 ≡ 1. Elle calcule alors 14 × 4 mod 23 = 10.

Le contrôle est indépendant : avec x = 23 − 1 − 6 = 16, on trouve 10¹⁶ mod 23 = 4, puis 4 × 14 mod 23 = 10. Le résultat coïncide bien avec le message initial.

Pour transmettre un secret sans partager d'abord une clé secrète, l'expéditeur utilise la clé publique du destinataire. La clé privée reste du côté du destinataire et sert au déchiffrement.

ElGamal convient lorsque l'on accepte qu'un message représenté par un élément du groupe devienne une paire d'éléments. Si la taille du chiffré est déterminante, cette expansion doit être prise en compte dans le choix du système.

Pour authentifier un message plutôt que le garder secret, on emploie une construction de signature. ElGamal peut être adapté à cet usage ; DSA appartient à cette famille standardisée, mais signer et chiffrer restent deux opérations différentes.

Clé publique et clé privée. La clé publique (p, g, α) permet à Bob de chiffrer ; l'exposant a reste privé et permet à Alice de déchiffrer. Le message m est la donnée que le chiffrement cherche à cacher ; a est le secret de la clé privée.

Chiffrement et signature ElGamal. Le chiffrement produit une paire destinée à cacher m, tandis qu'une signature sert à attester un message. DSA est un schéma de signature standardisé et apparenté, fondé lui aussi sur le logarithme discret ; il est distinct du chiffrement ElGamal et n'est pas le nom du chiffré (β, c) décrit ici.

Logarithme ordinaire et logarithme discret. Ici, chercher a signifie résoudre g^a ≡ α modulo p dans un groupe fini. Ce n'est pas calculer un logarithme réel avec une calculatrice.

Paramètres trop petits. Avec p = 23, l'exemple se calcule à la main et n'offre aucune sécurité réelle. La difficulté du logarithme discret ne protège le système que dans un groupe et avec des paramètres de taille suffisante.

Message hors du groupe. Le calcul multiplicatif suppose que m a été représenté par un élément non nul modulo p. La valeur m = 0 donnerait toujours une seconde composante nulle et révélerait ce cas ; il faut donc employer un encodage adapté au groupe choisi.

Aléa de chiffrement absent. Le nombre b doit être choisi aléatoirement pour chaque chiffrement. Une valeur fixe ferait disparaître la variation annoncée du chiffré ; le même message sous la même clé produirait alors la même paire.

Conclusion de sécurité trop forte. La difficulté de retrouver a par logarithme discret motive la construction, mais elle ne suffit pas à établir une équivalence stricte avec toutes les façons de casser le chiffrement. Il faut conserver la nuance explicitement donnée dans la source.

La fiche clé publique replace la publication d'une clé et la conservation de sa clé privée dans le cadre général de la cryptographie asymétrique.