Elgamal-Signaturverfahren

Das Elgamal-Signaturverfahren ist ein Verfahren für digitale Signaturen, welches auf dem mathematischen Problem des diskreten Logarithmus aufbaut. Es ist zu unterscheiden von dem Elgamal-Verschlüsselungsverfahren, wobei beide Verfahren 1984 von Taher Elgamal im selben Artikel veröffentlicht wurden^[1].

Eine Variante dieses Verfahrens wurde später als Digital Signature Algorithm standardisiert.

Vorbereitung

Wie bei allen diskreter-Logarithmus-Verfahren arbeiten wir in einer abelschen Gruppe G mit einem Erzeuger g. In der Original-Version des Verfahrens ist diese Gruppe eine Untergruppe großer Prim-Ordnung *q* der multiplikativen Gruppe $\mathbb Z_p^*$ des Restklassenringes modulo einer Primzahl p.

In der Praxis heißt das, wir wählen eine Primzahl q derart, dass p = 2q+1 ebenfalls eine Primzahl ist (mittels zufälliger Wahl von q und Testen von p, wiederholen bis eine gefunden wird). Dann erzeugen alle Elemente (außer 1 und -1) von $\mathbb Z_p^*$ entweder die gesamte Gruppe (der Ordnung 2q = p − 1), oder die Untergruppe der Ordnung q, und wir wählen eines als g, welches die Untergruppe (multiplikativ) erzeugt, üblicherweise 2 oder 3.

Diese Auswahl von p, q und g kann für alle Teilnehmer gemeinsam getroffen werden. Die Größe von q bestimmt die Sicherheit des Verfahrens. Außerdem muss eine kollisionsresistente Hashfunktion H fixiert werden.

Schlüsselerzeugung

Zur Erzeugung eines Schlüssel-Paars wählt ein Teilnehmer ein $a \in \{ 2, \ldots, p-2 \}$ (gleichverteilt zufällig), und berechnet daraus $A = g^a \, \bmod \, p$ mittels modularer Exponentation. A (bzw. das Tripel (p, g, A) kann dann als öffentlicher Schlüssel des Teilnehmers bekanntgegeben werden, während a als privater Schlüssel geheimgehalten wird.

Ein solches Schlüsselpaar kann auch für die Verschlüsselung mit dem Elgamal-Verschlüsselungsverfahren verwendet werden.

Signierung einer Nachricht

Um eine Nachricht m zu signieren, sind vom Unterzeichner folgende Schritte zu vollführen:

• Bestimme eine Zufallszahl k, so dass 0 < k < p − 1 und ggT(k,p − 1) = 1 (so dass k ^{− 1}(mod p − 1) existiert).
• Berechne $r \, \equiv \, g^k \pmod p$.
• Berechne $s \, \equiv \, (H(m)-a \cdot r)k^{-1} \pmod{p-1}$
• Wenn s = 0, dann wiederhole die Schritte.

Das Paar (r,s) ist die digitale Signatur von m. Diese Schritte müssen vom Unterzeichner für jede Signatur wiederholt werden.

Verifikation einer signierten Nachricht

Eine Signatur (r,s) einer Nachricht m wird verifiziert, indem die folgenden Bedingungen überprüft werden:

• 0 < r < p und 0 < s < p − 1.
• $g^{H(m)} \, \equiv \, A^r r^s \pmod p.$

Der Empfänger der Nachricht akzeptiert die Signatur, falls diese Bedingungen zutreffen. Andernfalls muss er sie zurückweisen.

Einzelnachweise

1. ↑ T. ElGamal: A public key cryptosystem and a signature scheme based on discrete logarithms. In: IEEE Trans inf Theo. 31, Nr. 4, 1985, S. 469–472., vorher veröffentlicht in Proceedings of CRYPTO '84.