Elgamal-Signaturverfahren

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten | Quelltext bearbeiten]

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 .

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 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[Bearbeiten | Quelltext bearbeiten]

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 Nachricht[Bearbeiten | Quelltext bearbeiten]

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 Nachricht[Bearbeiten | Quelltext bearbeiten]

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.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  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.