ElGamal-Signaturen

Das ElGamal-Signaturschema basiert ebenso wie das DSA-Signaturschema auf dem Problem der Berechnung von Logarithmen in . Es schreibt jedoch kein konkretes Hashverfahren vor, sondern stellt nur die Anforderung, dass dem Verwendeten eine Abbildung der Form für eine große Primzahl zugrunde liegt.

Schlüsselgenerierung

1. A erzeugt zufällig eine große Primzahl und bestimmt ein erzeugendes Element der multiplikativen Gruppe ; siehe hierzu Satz 37 (iv).
2. A wählt eine Zufallszahl mit .
3. A berechnet .

Der öffentliche Schlüssel von A ergibt sich als Tupel , während als geheimer Schlüssel aufbewahrt wird.

Signatur erstellen

Das Signieren einer Nachricht erreicht A wie folgt:

1. A erzeugt eine geheime Zufallszahl mit und (garantiert die Existenz des Inversen von in ).
2. A berechnet .
3. A bestimmt .
4. A ermittelt .

Nun hat A das Signaturpaar für die Nachricht erhalten.

Signatur prüfen

Möchte B zu einer empfangenen Nachricht die Signatur prüfen, dann muss er folgende Schritte durchführen:

1. B verwirft die Signatur, falls nicht erfüllt ist.
2. B berechnet .
3. B ermittelt .

Falls B nun das Ergebnis erhält, so kann er die Signatur (und damit auch die ursprüngliche Nachricht) als gültig ansehen.

Korrektheit

Wir nehmen an, sei eine gültige Signatur. Daraus folgt

und Bemerkung 42 liefert:

Damit ist gezeigt, dass gilt, falls eine korrekte Signatur für die Nachricht ist.

Sicherheitsüberlegungen

Wir schildern kurz, wie offensichtliche Angriffsversuche auf das ElGamal-Signaturschema scheitern.

Die erste Möglichkeit ist, dass ein Angreifer versuchen könnte, eine Zahl zu wählen und zu diesem ein passendes zu finden, um eine Nachricht zu signieren. Dazu müsste er ein finden, dass die Gleichung

löst. Dies entspricht aber der Berechnung eines diskreten Logarithmus, für die kein effizientes Verfahren bekannt ist.

Ein anderer Ansatz wäre, dass der Angreifer wählt und versucht, ein passendes zu finden, um eine Nachricht zu signieren. Dazu müsste er ein finden, dass die Gleichung

löst, wofür kein effizientes Verfahren bekannt ist.

Die letzte Möglichkeit, die wir diskutieren, ist die folgende. Der Angreifer wählt und und möchte eine passende Nachricht finden, die mit und korrekt signiert wäre. Dazu müsste er die Gleichung

lösen, was wiederum dem Berechnen des diskreten Logarithmus entspricht. Auch hier wird der Angreifer also scheitern.

Beispiel

Angenommen, es wird eine ElGamal-Signatur für den Text "Signaturen können von großer Bedeutung sein." benötigt. Wie üblich ist der erste Schritt die Ermittlung eines Hashwertes, welcher stellvertretend für die eigentliche Nachricht signiert wird. Für dieses Beispiel werden wir den MD5 Hashwert modulo einer auszuwählenden Primzahl verwenden. Dieser Hashwert beträgt 61 ED 8C 44 A3 67 A6 13 AE 7D C6 BD E5 B0 6C 71, umgewandelt in das Dezimalsystem also

Durch die Modulo-Operation dieser Zahl mit der zufällig bestimmten Primzahl erhalten wir als zu signierenden Wert .

Schlüsselgenerierung.
Die große Primzahl wurde schon gewählt, nun benötigen wir ein erzeugendes Element der Gruppe . Ein solches ist . Abschliessend wird noch eine Zufallszahl zwischen und generiert, also , und wir ermitteln

Der erzeugte Schlüssel besteht somit aus dem öffentlichen Teil () und dem privaten Teil ().

Signatur erstellen.
Eine weitere zufällige Zahl mit , die teilerfremd zu ist, muss bestimmt werden, für dieses Beispiel sei . Nun ergibt sich die gesuchte Signatur als

Signatur prüfen.
Um die erzeugte Signatur zu prüfen, müssen wir und berechnen:

Da beide Berechnungen den gleichen Wert liefern, ist die Überprüfung erfolgreich und die Signatur kann akzeptiert werden.