Quelltext der Seite Elgamal-Signaturverfahren

Das '''Elgamal-Signaturverfahren''' ist ein Verfahren für digitale Signaturen, welches auf dem mathematischen Problem des [[diskreter Logarithmus|diskreten Logarithmus]] aufbaut. Es ist zu unterscheiden von dem [[Elgamal-Verschlüsselung]]sverfahren, wobei beide Verfahren 1984 von [[Taher Elgamal]] im selben Artikel veröffentlicht wurden.<ref name="ElgamalOriginalArticle">{{cite journal |author=T. ElGamal |date=1985 |title=A public key cryptosystem and a signature scheme based on discrete logarithms |journal=IEEE Trans inf Theo |volume=31 |issue=4 |pages=469–472 |url=http://hereford.homeip.net/ElGamal/ElGamal%20-%20A%20Public%20Key%20Cryptosystem%20and%20a%20Signature%20Scheme%20Based%20on%20Discrete%20Logarithms%20ElGamal.pdf |archive-url=https://web.archive.org/web/20120305103651/http://hereford.homeip.net/ElGamal/ElGamal%20-%20A%20Public%20Key%20Cryptosystem%20and%20a%20Signature%20Scheme%20Based%20on%20Discrete%20Logarithms%20ElGamal.pdf |archive-date=2012-03-05 |language=en}}, vorher veröffentlicht in [http://www.informatik.uni-trier.de/~ley/db/conf/crypto/crypto84.html ''Proceedings of CRYPTO '84''].</ref>

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 [[Abelsche Gruppe|abelschen Gruppe]] ''G'' mit einem Erzeuger ''g''. In der Originalversion des Verfahrens ist diese Gruppe eine Untergruppe großer Primordnung <math>q</math> der [[Multiplikative Gruppe|multiplikativen Gruppe]] <math>\mathbb Z_p^*</math> des [[Restklassenkörper]]s modulo einer Primzahl <math>p</math>. 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.<ref>[[Neal Koblitz]]: [https://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866109-5/S0025-5718-1987-0866109-5.pdf Elliptic curve cryptosystems], S. 205.</ref>

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 <math>\mathbb Z_p^*</math> entweder die gesamte Gruppe (der Ordnung <math>2q = p-1</math>), 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 <math>\mathbb Z_p^*</math>.

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 [[Kollisionsresistenz|kollisionsresistente]] [[Hashfunktion]] ''H'' fixiert werden.

== Schlüsselerzeugung ==
Zum Erzeugen eines Schlüsselpaars wählt ein Teilnehmer ein <math>a \in \{ 2, \ldots, p-2 \}</math> (gleichverteilt zufällig), und berechnet daraus <math>A = g^a \, \bmod \, p</math> mittels [[Diskrete Exponentialfunktion|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üsselung]]sverfahren 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 <math>0<k<p-1</math> und <math>\operatorname{ggT}(k,p-1)=1</math> (so dass <math>k^{-1} \bmod(p-1)</math> existiert und mittels des [[Restklassenring#Invertierbarkeit und Inversenberechnung|erweiterten euklidischen Algorithmus']] berechnet werden kann).
* Man berechnet <math> r \, \equiv \, g^k \pmod p</math>.
* Man berechnet <math> s \, \equiv \, (H(m)-a \cdot r)k^{-1} \pmod{p-1}</math>
* Wenn <math>s=0</math>, 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:

* <math>0<r<p</math> und <math>0<s<p-1</math>.
* <math> g^{H(m)} \, \equiv \, A^r r^s \pmod p.</math>

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

== Einzelnachweise ==
<references />

[[Kategorie:Signaturverfahren]]