Elgamal-Signaturverfahren

Grundidee und Einsatz

Das Elgamal-Signaturverfahren ist ein Verfahren für digitale Signaturen. Es beruht auf dem mathematischen Problem des diskreten Logarithmus und dient dazu, die Echtheit einer Nachricht anhand einer Signatur zu prüfen. Es ist vom Elgamal-Verschlüsselungsverfahren zu unterscheiden, auch wenn beide Verfahren 1984 von Taher Elgamal im selben Artikel veröffentlicht wurden.

Eine Variante wurde später als Digital Signature Algorithm (DSA) standardisiert und weit verbreitet. Das ursprüngliche Verfahren wird wegen seines vergleichsweise hohen Rechenaufwands und großer Signaturen, besonders im Vergleich zu DSA, nur selten eingesetzt. Es war beispielsweise nie Bestandteil von TLS und wurde weder von OpenSSL noch von GnuTLS implementiert.

Öffentliche Grundlagen

Wie bei Verfahren mit diskretem Logarithmus wird in einer abelschen Gruppe G mit einem Erzeuger g gearbeitet. Ein Erzeuger ist ein Gruppenelement, mit dessen Potenzen alle Elemente der betreffenden Gruppe erzeugt werden können.

In der Originalversion ist G eine Untergruppe großer Primordnung q der multiplikativen Gruppe ℤₚ* modulo einer Primzahl p. Das Verfahren kann aber auch auf anderen endlichen Gruppen beruhen, insbesondere auf einer elliptischen Kurve.

Für die Elgamal-Signatur wird eine Primzahl q so gewählt, dass p = 2q + 1 ebenfalls prim ist. Dann erzeugen alle Elemente außer 1 und −1 von ℤₚ* entweder die gesamte Gruppe der Ordnung 2q = p − 1 oder die Untergruppe der Ordnung q. Als g wird ein Element gewählt, das die Untergruppe multiplikativ erzeugt; üblicherweise die Restklasse von 2 oder 3 in ℤₚ*.

Die Werte p, q und g können für alle Teilnehmer gleich sein. Die Größe von q bestimmt die Sicherheit. Außerdem wird eine kollisionsresistente Hashfunktion H festgelegt; sie soll es schwer machen, zwei verschiedene Nachrichten mit demselben Hashwert zu finden.

Schlüsselpaar bilden

Ein Teilnehmer wählt gleichverteilt zufällig einen geheimen Wert a ∈ {2, …, p − 2}. Anschließend berechnet er mittels modularer Exponentiation

A = gᵃ mod p.

A beziehungsweise das Tripel (p, g, A) ist der öffentliche Schlüssel und darf bekanntgegeben werden. Der Wert a ist der private Schlüssel und muss geheim bleiben. Dasselbe Schlüsselpaar kann auch zur Verschlüsselung mit dem Elgamal-Verschlüsselungsverfahren verwendet werden.

Nachricht signieren

Für jede zu signierende Nachricht m wählt der Unterzeichner eine Zufallszahl k mit 0 < k < p − 1 und ggT(k, p − 1) = 1. Dadurch existiert das modulare Inverse k⁻¹ mod (p − 1), das mit dem erweiterten euklidischen Algorithmus berechnet werden kann.

Dann werden die beiden Signaturwerte berechnet:

• r ≡ gᵏ mod p
• s ≡ (H(m) − a · r)k⁻¹ mod (p − 1)

Falls s = 0 ist, müssen diese Schritte wiederholt werden. Das Paar (r, s) ist die digitale Signatur der Nachricht m. Die Schritte, insbesondere die Wahl von k, werden für jede Signatur erneut ausgeführt.

Signatur prüfen

Der Empfänger prüft zunächst, ob 0 < r < p und 0 < s < p − 1 gilt. Außerdem muss die Gleichung

gᴴ⁽ᵐ⁾ ≡ Aʳrˢ mod p

erfüllt sein.

Treffen beide Bedingungen zu, akzeptiert der Empfänger die Signatur; andernfalls weist er sie zurück.