Das EL-GAMAL Verfahren
Das Verschlüsselungsverfahren von El-GAMAL ist im Prinzip nichts anderes als eine Diffie-Hellman-Schlüsselvereinbarung mit anschließendem Senden einer Nachricht, die mit dem vereinbarten Schlüssel verschlüsselt ist. Öffentlich bekannt ist wiederum eine Primzahl p und eine Zahl g. Zunächst wird der Diffie-Hellman-Algorithmus ausgeführt, beide Kommunikationspartner verfügen anschließend über den gemeinsamen Schlüssel K. Danach verschlüsselt der Sender B den Klartext m mit dem gemeinsamen Schlüssel K und sendet den resultierenden Geheimtext c an A. Der Empfänger A entschlüsselt den Geheimtext c mithilfe des gemeinsamen Schlüssels K und erhält den Klartext m zurück.
Ablauf des Verfahrens
Realisierung
In der tatsächlichen Realisierung finden die Berechnungen und Übertragungen von Daten gegenüber dem obigen Diagramm zeitlich versetzt statt.
A erzeugt die Zahlen p, g und a und veröffentlicht diese als seinen öffentlichen Schlüssel, hält aber die Zahl a als privaten Schlüssel geheim. Von diesem Zeitpunkt an kann ein beliebiger Sender B einen Klartext m mit dem öffentlichen Schlüssel des Empfängers A verschlüsseln, indem er zunächst K berechnet und daraufhin m mit K verschlüsselt. Zusätzlich zum eigentlichen Geheimtext c sendet er nun die Zahl B an den Empfänger A. Dieser kann mithilfe seines privaten Schlüssels a die Zahl K-1 berechnen und den Klartext m zurückgewinnen.
Sicherheit
Die Sicherheit des Verschlüsselungsverfahrens von El-Gamal beruht auf der Sicherheit der Diffie-Hellman-Schlüsselvereinbarung. Anhand der obigen Skizze lässt sich erkennen, dass der Klartext m aus dem Geheimtext c nur durch Kenntnis des Schlüssels K zurückgewonnen werden kann. Die Zahl K aber lässt sich aus den öffentlich bekannten Zahlen p, g, A und B nicht effizient berechnen (Problem des diskreten Logarithmus). Durch eine Known-Plaintext-Attack allerdings, also bei Kenntnis eines Klartextes m und des zugehörigen Geheimtextes c, lässt sich K berechnen, nämlich durch: K = c * m-1 mod p Daher ist es wichtig, den Schlüssel K immer nur ein einziges Mal zu verwenden. Dies geschieht dadurch, dass der Sender B bei jeder neuen Verschlüsselung eine neue Zufallszahl b wählt, sodass jedes Mal ein neues K und ein neues B erzeugt werden. Auch wenn ein längerer Klartext in Zahlen m0, m1, m2 usw. zerlegt wird, die einzeln verschlüsselt werden, muss jedes Mal eine neue Zufallszahl b verwendet werden.