Schnorr-Signatur

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

Die Schnorr-Signatur ist ein 1989/91 vom deutschen Mathematikprofessor Claus-Peter Schnorr entworfenes kryptographisches Schema für digitale Signaturen. Es leitet sich aus der Schnorr-Identifikation ab, indem wie bei der Fiat-Shamir-Identifikation die Interaktion durch den Einsatz einer kryptographischen Hashfunktion ersetzt wird. Die Sicherheit beruht auf der Komplexität des Diskreten Logarithmus in endlichen Gruppen.

Das Verfahren ist von Schnorr patentiert[1][2], die Schutzfrist ist inzwischen jedoch abgelaufen. Es ist exklusiv an RSA lizenziert (Siemens hat aber eine nicht-exklusive Lizenz). Schnorr warf im Rahmen der Standardisierung IEEE P1363 der NIST vor, mit dem von ihr entwickelten Signatur-Verfahren Digital Signature Algorithm, kurz DSA, sein Patent zu verletzen.

Parameter[Bearbeiten]

Systemweite Parameter[Bearbeiten]

Alle Benutzer können diese Parameter gemeinsam nutzen:

Schnorr schlägt vor, eine Untergruppe G von Z_p^* für ein primes p zu wählen. Er argumentiert, dass Schlüssel- und Signaturlängen sich auf |G| beziehen, das Sicherheitsniveau sich hingegen am größeren |Z_p^*| orientiert.

Privater Schlüssel[Bearbeiten]

Der private Schlüssel besteht aus einer zufällig gewählten Zahl:

  • x mit 0 < x < q

Öffentlicher Schlüssel[Bearbeiten]

Der öffentliche Schlüssel ist das x entsprechende Gruppenelement y:

  • y = g^x

Unterschreiben[Bearbeiten]

Um eine Nachricht m zu unterschreiben, wird folgendermaßen verfahren:

  1. Wähle k zufällig mit 0 < k < q.
  2. Setze r := g^k
  3. Setze e := H(r||m). Dabei ist || die Konkatenation von Zahlen als Bitfolgen.
  4. Setze s := (k + xe) \mod q.

Die Unterschrift der Nachricht ist das Tupel (e,s).

Verifizieren[Bearbeiten]

Um eine Unterschrift (e,s) einer Nachricht m zu verifizieren, wird folgendermaßen verfahren:

  1. Setze r_v := g^s \cdot y^{-e}
  2. Setze e_v := H(r_v||m)
  3. Akzeptiere die Unterschrift genau dann, wenn e_v = e ist.

Sicherheitsdiskussion (informell)[Bearbeiten]

Die Sicherheit der Schnorr-Signatur ist im Random-Oracle-Modell auf die Komplexität des diskreten Logarithmus in der verwendeten Gruppe beweisbar zu reduzieren, d. h. wer das Schnorr-Signatur-Schema effizient bricht, kann auch effizient den diskreten Logarithmus berechnen[3]. Es ist kein Verfahren bekannt, mit dem sich der diskrete Logarithmus in multiplikativen Gruppen von endlichen Körpern mit heutigen Computern effizient berechnen lässt. (Für die Berechnung auf Quantencomputern existiert zwar der (theoretisch) effiziente Shor-Algorithmus[4], die dafür erforderlichen Quantencomputer sind aber mit den erforderlichen Bitlängen in absehbarer Zeit nicht realisierbar.) Diese beweisbare Reduktion auf bekannte, als schwierig eingestufte Probleme ist typisch für Sicherheitsbeweise bei kryptographischen Systemen mit öffentlichen Schlüsseln.

Im Random-Oracle-Modell nimmt man an, die Hashfunktion verhalte sich wie eine zufällige Funktion und ein Angreifer kann die Funktionswerte nur über eine Orakel für die Funktionswerte berechnen. Mit Hilfe eines Widerspruchsbeweis zeigt man nun die Korrektheit des Verfahrens. Angenommen, es gäbe einen erfolgreichen Unterschriftenfälscher für das Signaturverfahren. Dieses kann man nutzen, um aus dem öffentlichen Schlüssel y=g^x den geheimen Schlüssel x zu bestimmen, also den Diskreten Logarithmus x von y zu berechnen – im Widerspruch zur Annahme, der diskrete Logarithmus sei schwierig.

  1. Simuliere den Algorithmus zum Unterschreiben einer Nachricht m, speichere Zustand beim Aufruf des Orakels, um e_1=H(m||r) zu berechnen.
  2. Wiederhole die Simulation an gespeicherten Zustand, gib allerdings ein anderes e_2=H(m||r) zurück (Dies geht im Random-Oracle-Modell)
  3. Seien s_1 und s_2 die beiden (verschiedenen) Unterschriften zur gleichen Nachricht m und gleichem Zufallswert k bzw. r
  4. Es gilt s_1-s_2 = (k + xe_1)-(k + xe_2) = x(e_1-e_2)\mod q, also x=(s_1-s_2)/(e_1-e_2)\mod q

Die Division durch e_1-e_2 ist möglich: Da q prim ist, existiert zu jeder Zahl ungleich 0 auch ein Inverses modulo q.

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

Claus-Peter Schnorr, Vorlesung Kryptographie I/II, Kapitel 1.7, (PDF, 454 kB)

Einzelnachweise[Bearbeiten]

  1. Patent EP0384475: Angemeldet am 22. Februar 1990.
  2. Patent US4995082: Angemeldet am 23. Februar 1990.
  3. David Pointcheval und Jacques Stern: Security arguments for digital signatures and blind signatures. Journal of Cryptology, 13(3), pp. 361-396, 2000.
  4. Peter W. Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. In: SIAM Journal on Computing. 26/1997, S. 1484–1509 (arXiv:quant-ph/9508027).