ElGamal

Veröffentlicht 1985 von Taher Elgamal, der ein Jahrzehnt später bei Netscape SSL entwarf. Das System beruht auf demselben schweren Problem wie Diffie-Hellman — dem diskreten Logarithmus in einer endlichen Gruppe —, beherrscht aber sowohl Verschlüsselung als auch Signatur.

Die Verschlüsselung ist randomisiert: Derselbe Klartext ergibt jedes Mal einen anderen Chiffretext, weil bei jeder Operation ein frischer Zufallswert einfließt. Das ist zugleich Stärke und Falle. Wird der Zufallswert wiederverwendet, lässt sich der private Schlüssel berechnen — genau das brach 2010 Sonys Signierung der PS3. Der Chiffretext wird doppelt so groß wie der Klartext, und DSA, der US-Signaturstandard, ist im Kern ElGamals Signaturteil in gestraffter Form.