Schnorr-Signatur

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Die Schnorr-Signatur ist ein 1989/1991 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.[3]

Parameter[Bearbeiten | Quelltext bearbeiten]

Systemweite Parameter[Bearbeiten | Quelltext bearbeiten]

Alle Benutzer können diese Parameter gemeinsam nutzen:

  • Eine Gruppe primer Ordnung . Diese ist zyklisch, sei ein Generator
  • Eine kryptografische Hash-Funktion mit Wertebereich .

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

Privater Schlüssel[Bearbeiten | Quelltext bearbeiten]

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

  • mit

Öffentlicher Schlüssel[Bearbeiten | Quelltext bearbeiten]

Der öffentliche Schlüssel ist das entsprechende Gruppenelement :

Unterschreiben[Bearbeiten | Quelltext bearbeiten]

Um eine Nachricht (Folge von Oktetts) zu unterschreiben, wird folgendermaßen verfahren:

  1. Wähle zufällig mit .
  2. Setze und stelle als Folge von Oktetts dar.
  3. Setze . Dabei ist die Konkatenation.
  4. Setze .

Die Unterschrift der Nachricht ist das Tupel .

Für elliptische Kurven formuliert[Bearbeiten | Quelltext bearbeiten]

Wir betrachten eine elliptische Kurve über GF(p). Der Generator G ist ein Punkt auf der Kurve und es sei .

  1. Wähle zufällig mit .
  2. Setze
  3. Setze . Dabei ist die Konkatenation und die Darstellung der -Koordinate des Punktes als Folge von Oktetts.
  4. Setze . Falls die Bitlänge von größer als die Bitlänge von ist, werden vor der Berechnung von die überzähligen (rechten) Bits von gestrichen.

Die Unterschrift der Nachricht ist das Tupel .

Verifizieren[Bearbeiten | Quelltext bearbeiten]

Um eine Unterschrift einer Nachricht zu verifizieren, wird folgendermaßen verfahren:

  1. Setze
  2. Setze
  3. Akzeptiere die Unterschrift genau dann, wenn ist.

Mit elliptischer Kurve[Bearbeiten | Quelltext bearbeiten]

  1. Berechne
  2. Setze
  3. Akzeptiere die Unterschrift genau dann, wenn ist.

Multi-Signatur-Verfahren[Bearbeiten | Quelltext bearbeiten]

Um mit dem Schnorr-Algorithmus eine Nachricht mit mehreren Schlüsseln gleichzeitig unterschreiben zu lassen, sind folgende Modifikationen notwendig:

  1. Der Unterschreiber ist im Besitz von mehreren privaten Schlüsseln , womit auch mehrere öffentliche Schlüssel existieren
  2. Der Unterschreiber berechnet
  3. Beim Verifizieren ist

Die Multi-Signatur mit dem Schnorr-Verfahren hat den Vorteil, dass lediglich eine Signatur für mehrere Schlüssel benötigt wird. Besonders bei Blockchain Anwendungen, in denen Speicherplatz wertvoll und knapp ist, könnte das Schnorr-Verfahren am Beispiel der Bitcoin-Blockchain bis zu 25 % Speicherplatz einsparen[4].

Sicherheitsdiskussion (informell)[Bearbeiten | Quelltext bearbeiten]

Der Wert xe und damit auch der Wert x wird durch die Zufallszahl k sicher verschlüsselt (One-Time-Pad). Die Sicherheit ist daher unter bestimmten Voraussetzungen über die verwendeten Zufallszahlen (k) und der Hashfunktion (Random-Oracle-Modell) auf die Komplexität des diskreten Logarithmus in der verwendeten Gruppe beweisbar zu reduzieren, das heißt wer die Schnorr-Signatur-Schema berechnen kann, kann auch den diskreten Logarithmus berechnen[5]. 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. 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 den geheimen Schlüssel zu bestimmen, also den Diskreten Logarithmus von zu berechnen – im Widerspruch zur Annahme, der diskrete Logarithmus sei schwierig.

  1. Simuliere den Algorithmus zum Unterschreiben einer Nachricht , speichere Zustand beim Aufruf des Orakels, um zu berechnen.
  2. Wiederhole die Simulation an gespeicherten Zustand, gib allerdings ein anderes zurück (Dies geht im Random-Oracle-Modell)
  3. Seien und die beiden (verschiedenen) Unterschriften zur gleichen Nachricht und gleichem Zufallswert bzw.
  4. Es gilt , also

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

Anforderung an die Zufallszahlen[Bearbeiten | Quelltext bearbeiten]

Aus den obigen Ausführung folgt, dass sich die Zufallszahlen k, die zur Berechnung der Signatur verwendet werden, sich keinesfalls wiederholen dürfen. Würde eine Zufallszahl zur Signatur zweier unterschiedlicher Nachrichten verwendet, könnte der private Schlüssel x aus öffentlich bekannten Werten berechnet werden. Damit könnten dann Signaturen von einem Angreifer gefälscht werden. Weiterhin dürfen die Zufallszahlen für den Angreifer nicht berechenbar sein, da er sonst x berechnen könnte.

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

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

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Patent EP0384475: Angemeldet am 22. Februar 1990.
  2. Patent US4995082: Angemeldet am 23. Februar 1990.
  3. IEEE P1363 Patent Reply from Prof. Dr. Claus Peter Schnorr. (Nicht mehr online verfügbar.) Archiviert vom Original am 13. Oktober 2016; abgerufen am 25. Januar 2018. i Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/grouper.ieee.org
  4. Sam Wouters: Why Schnorr signatures will help solve 2 of Bitcoin’s biggest problems today, 4. Juli 2017. Abgerufen am 30. Dezember 2017.
  5. David Pointcheval und Jacques Stern: Security arguments for digital signatures and blind signatures. Journal of Cryptology, 13(3), pp. 361-396, 2000.