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 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 SSL bzw. TLS und wurde weder von OpenSSL noch von GnuTLS implementiert (DSA hingegen schon).

VorbereitungBearbeiten

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   der multiplikativen Gruppe   des Restklassenkörpers modulo einer Primzahl  . 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.[2]

In der Praxis heißt das, dass man 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   entweder die gesamte Gruppe (der Ordnung  ), 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  .

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üsselerzeugungBearbeiten

Zum Erzeugen eines Schlüsselpaars wählt ein Teilnehmer ein   (gleichverteilt zufällig), und berechnet daraus   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 NachrichtBearbeiten

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

  • Man bestimmt eine Zufallszahl k, so dass   und   (so dass   existiert und mittels des erweiterten euklidischen Algorithmus' berechnet werden kann).
  • Man berechnet  .
  • Man berechnet  
  • Wenn  , 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 NachrichtBearbeiten

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

  •   und  .
  •  

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

EinzelnachweiseBearbeiten

  1. T. ElGamal: A public key cryptosystem and a signature scheme based on discrete logarithms Archiviert vom Original am 5. März 2012. In: IEEE Trans inf Theo. 31, Nr. 4, 1985, S. 469–472., vorher veröffentlicht in Proceedings of CRYPTO '84.
  2. Neal Koblitz: Elliptic curve cryptosystems, S. 205.