Das ElGamal System [Elg85] ist ein asymmetrisches Kryptosystem, das auf dem diskreten Logarithmus Problem basiert. Es enthält sowohl Verschlüsselungs- als auch Unterschriftsalgorithmen. Der Verschlüsselungsalgorithmus prinzipell mit dem Diffie-Hellman Schlüsseltausch identisch (siehe Frage 24).
Das System wird durch eine Primzahl p und einer Ganzzahl g, deren Potenzen modulo p eine große Anzahl von Elementen umfaßt (wie bei Diffie-Hellman), parametrisiert. Der private Schlüssel von Alice sei a und ihr öffentlicher Schlüssel sei y = ga (mod p). Wenn nun Bob Alice eine Nachricht m schicken will, so wählt er eine Zufallszahl k kleiner als p und berechnet dann:
y1 = gk (mod p) und y2 = m xor (yk mod p), wobei
xor das bitweise ExklusivOder aka Ungleichheit bedeutet. Bob sendet (y1, y2) an Alice. Nachdem diese das Chiffrat empfangen hat, berechnet sie:
m = (y1a mod p) xor y2 .
Der ElGamal Unterschriftsalgorithmus ist dem Chiffrieralgorithmus ähnlich, bei dem öffentlicher und privater Schlüssel die gleiche Form haben, jedoch ist Verschlüsselung und Unterschriftenverifizierung sowie Entschlüsselung und Untershreiben das gleiche, wie in RSA (siehe Frage 8). DSA (siehe Frage 26) basiert teilweise auf dem ElGamal Unterschriftenalgorithmus.
Die Analyse auf Basis der besten verfügbaren Faktorisierungsalgorithmen zeigt, daß RSA und ElGamal bei gleicher Schlüssellänge ähnliche Sicherheit bieten. Der Hauptnachteil von ElGamal ist die Forderung nach Zufallszahlen und die etwas langsamere Geschwindigkeit (speziell beim Unterschreiben) Ein anderer möglicher Nachteil von ElGamal ist, daß das Chiffrat doppelt so groß ist, wie die Nachricht selbst. Dies ist jedoch in Hybridsystemen bei der Verschlüsselung symmetrischer Schlüssel vernachlässigbar.