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.

Eine Variante dieses Verfahrens wurde später als Digital Signature Algorithm standardisiert und fand weite Verbreitung. Das ursprüngliche Verfahren hingegen wird aufgrund des verhältnismäßig hohen Rechenaufwands und der großen Signaturen (insbesondere gegenüber DSA) nur selten eingesetzt. Beispielsweise war das ElGamal-Signaturverfahren nie Bestandteil von Transport Layer Security (TLS) und wurde weder von OpenSSL noch von GnuTLS implementiert (DSA hingegen schon).

Vorbereitung

Wie bei allen Verfahren mit diskretem Logarithmus arbeitet man in einer abelschen Gruppe G mit einem Erzeuger g. In der Originalversion des Verfahrens ist diese Gruppe eine Untergruppe großer Primordnung $q$ der multiplikativen Gruppe $\mathbb {Z} _{p}^{*}$ des Restklassenkörpers modulo einer Primzahl $p$. Es ist jedoch genauso möglich, das Verfahren auf Grundlage einer anderen endlichen Gruppe zu realisieren. Insbesondere kann zu diesem Zweck eine elliptische Kurve benutzt werden.

Bei der Elgamal-Signatur wird eine Primzahl q derart wählt, 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 man wählt eines als g, welches die Untergruppe (multiplikativ) erzeugt, üblicherweise die Restklasse von 2 oder 3 in $\mathbb {Z} _{p}^{*}$.

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

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

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

Signieren einer Nachricht

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

• Man bestimmt eine Zufallszahl k, so dass $0<k<p-1$ und $\operatorname {ggT} (k,p-1)=1$ (so dass $k^{-1}{\bmod {(}}p-1)$ existiert und mittels des erweiterten euklidischen Algorithmus' berechnet werden kann).
• Man berechnet $r\,\equiv \,g^{k}{\pmod {p}}$.
• Man berechnet $s\,\equiv \,(H(m)-a\cdot r)k^{-1}{\pmod {p-1}}$
• Wenn $s=0$, werden die Schritte wiederholt.

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

Verifizieren 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 weist er sie zurück.