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]

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.

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 \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 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]

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 Exponentation. 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]

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 ggT(k,p-1)=1 (so dass k^{-1} \pmod{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[Bearbeiten]

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.

Einzelnachweise[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.