Elgamal-Signaturverfahren

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.

Inhaltsverzeichnis

Vorbereitung

Wie bei allen diskreter-Logarithmus-Verfahren arbeiten wir in einer abelschen Gruppe G mit einem Erzeuger g. In der Original-Version des Verfahrens ist diese Gruppe eine Untergruppe großer Prim-Ordnung *q* der multiplikativen Gruppe \mathbb Z_p^* des Restklassenringes modulo einer Primzahl p.

In der Praxis heißt das, wir wählen eine Primzahl q derart, 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 wir wählen 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

Zur Erzeugung eines Schlüssel-Paars 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 geheimgehalten wird.

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

Signierung einer Nachricht

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

  • Bestimme eine Zufallszahl k, so dass 0 < k < p − 1 und ggT(k,p − 1) = 1 (so dass k − 1(mod p − 1) existiert).
  • Berechne  r \, \equiv \, g^k \pmod p.
  • Berechne  s \, \equiv \, (H(m)-a \cdot r)k^{-1} \pmod{p-1}
  • Wenn s = 0, dann wiederhole die Schritte.

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

Verifikation 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 muss er sie zurückweisen.

Einzelnachweise

  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.

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Elgamal-Kryptosystem — Das Elgamal Kryptosystem (auch al Dschamal Kryptosystem) ist ein Schema zur Verschlüsselung, das auf dem mathematischen Problem des diskreten Logarithmus beruht. Elgamal ist ein asymmetrischer Verschlüsselungsalgorithmus aufbauend auf der Idee… …   Deutsch Wikipedia

  • Elgamal-Verschlüsselungsverfahren — Das Elgamal Kryptosystem (auch al Dschamal Kryptosystem) ist ein Schema zur Verschlüsselung, das auf dem mathematischen Problem des diskreten Logarithmus beruht. Elgamal ist ein asymmetrischer Verschlüsselungsalgorithmus aufbauend auf der Idee… …   Deutsch Wikipedia

  • Merkle-Signatur — Die Merkle Signatur ist ein digitales Signaturverfahren, das auf Merkle Bäumen sowie Einmalsignaturen wie etwa dem Lamport Einmalsignaturen basiert. Es wurde von Ralph Merkle in den späten Siebzigern entwickelt und stellt eine Alternative zu… …   Deutsch Wikipedia

  • Digital Signature Algorithm — Der Digital Signature Algorithm (DSA) ist ein Standard der US Regierung für Digitale Signaturen. Er wurde vom National Institute of Standards and Technology (NIST) im August 1991 für die Verwendung in deren Digital Signature Standard (DSS)… …   Deutsch Wikipedia

  • Jacques Stern (Kryptologe) — Jacques Stern (* 21. August 1949 in Paris) ist ein französischer Kryptologe, Informatiker und Mathematiker. Jacques Stern Inhaltsverzeichnis 1 …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”