Schnorr-Signatur

Claus Peter Schnorr

Die Schnorr-Signatur ist eine kryptographische Methode zur Berechnung und Prüfung digitaler Signaturen. Sie wurde in den Jahren 1989 bis 1991 von dem deutschen Mathematiker Claus Peter Schnorr ausgehend von der Schnorr-Identifikation entwickelt und publiziert. Das Signaturverfahren ist aus dem verwandten Identifikationsverfahren, auch Zero-Knowledge-Beweisverfahren genannt, entstanden. Im Gegensatz zur Fiat-Shamir-Identifikation ist keine mehrstufige Interaktion notwendig. Anders als bei der Schnorr-Identifikation wird beim Signaturverfahren eine Hashfunktion benötigt. Es wird nicht zwingend eine kollisionsresistente Hashfunktion benötigt, anders als beim Digital Signature Algorithm. Die Sicherheit beruht praktisch allein auf der Schwierigkeit den sogenannten diskreten Logarithmus in endlichen Gruppen zu berechnen. Ist diese Berechnung praktisch nicht möglich, kann die Signatur nur geprüft, aber ohne den privaten Schlüssel nicht berechnet werden.

Die Verfahren zur Identifikation und zur Signatur wurden von Claus Peter Schnorr patentiert. Die Schutzfrist ist inzwischen abgelaufen. Das Patent war exklusiv an das Unternehmen RSA lizenziert. Auch das deutsche Unternehmen Siemens hat eine nicht-exklusive Lizenz erworben. Schnorr warf im Rahmen der Standardisierung IEEE P1363 dem amerikanischen National Institute of Standards vor, mit dem von ihm entwickelten Signatur-Verfahren, Digital Signature Algorithm (DSA), sein Patent zu verletzen.

Die Sicherheit des Verfahrens ist nur gegeben, wenn die Ordnung der Untergruppe hinreichend groß ist. Die Signatur kann sonst mit der Pollard-Rho-Methode gefälscht werden. Die von Professor Schnorr vorgeschlagene Größenordnung für die Gruppenordnung q mit 140 Bits kann heute nicht mehr als ausreichend bewertet werden.

Parameter des Signatur-Verfahrens

Systemweite Parameter

Alle Benutzer können diese Parameter gemeinsam nutzen:

• Eine Gruppe $G$ primer Ordnung $q=|G|$. Diese ist zyklisch, sei $g$ ein Generator
• Eine kryptografische Hash-Funktion $H$ mit Wertebereich $[0,q-1]$.

Schnorr schlägt vor, eine Untergruppe $G$ von $Z_{p}^{*}$ für ein primes $p$ zu wählen. Um eine Untergruppe von $Z_{p}^{*}$ zu finden, muss (p-1), die Ordnung von $Z_{p}^{*}$, in Primzahlen faktorisiert werden. Dann kann (p-1) als $q=|G|$ mal einem Cofaktor h geschrieben werden. Wenn g ein Generator von $Z_{p}^{*}$ ist, kann ein Generator von $G$ als $g^{h}$ bestimmt werden.

Die Länge des privaten Schlüssels und der Signatur werden allein durch die Ordnung der Untergruppe $q=|G|$ bestimmt.

Privater Schlüssel zur Signaturerstellung

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

• $x$ mit $0<x<q$

Öffentlicher Schlüssel zur Prüfung der Signatur

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

• $y=g^{x}$

Berechnung der Signatur

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.
4. Setze $s:=(k+xe){\bmod {q}}$.

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

Für elliptische Kurven formuliert

Wir betrachten eine elliptische Kurve der Ordnung q über GF(p). Der Generator G ist ein Punkt auf der Kurve und es sei $Y=x\cdot G$ der öffentliche Schlüssel.

1. Wähle $k$ zufällig mit $0<k<q$.
2. Setze $R:=k\cdot G$
3. Setze $e:=H(R_{x}||m)$. Dabei ist $||$ die Konkatenation und $R_{x}$ die $x$-Koordinate des Punktes $R$.
4. Setze $s:=(k+xe){\bmod {q}}$. Falls die Bitlänge von $e$ größer als die Bitlänge von $q$ ist, werden vor der Berechnung von $s$ die überzähligen (rechten) Bits von $e$ gestrichen.

Die Unterschrift der Nachricht $m$ ist das Tupel $(e,s)$ oder $(R,s)$.

Verifizieren der Signatur

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.

Wenn die Unterschrift im Format $(r,s)$ ist, kann es wie folgt verifiziert werden:

1. Setze $r_{v}:=g^{s}\cdot y^{-H(r||m)}$
2. Akzeptiere die Unterschrift genau dann, wenn $r_{v}=r$ ist.

Mit elliptischer Kurve

1. Berechne $R=(s\cdot G)-(e\cdot Y)$
2. Setze $e_{v}:=H(R_{x}||m)$
3. Akzeptiere die Unterschrift genau dann, wenn $e_{v}=e$ ist.

Wenn die Unterschrift im Format $(R,s)$ ist, kann es wie folgt verifiziert werden:

1. Berechne $R_{v}:=s\cdot G-H((R_{x}||m)\cdot Y$
2. Akzeptiere die Unterschrift genau dann, wenn $R_{v}=R$ ist.

Multi-Signatur

Mit Schnorr-Signaturen ist es möglich, eine Nachricht mit mehreren Schlüsseln in einer Signatur zu unterschreiben.

Ein-Partei-Signaturen

1. Der Unterschreiber ist im Besitz von mehreren privaten Schlüsseln $x_{i}$, womit auch mehrere öffentliche Schlüssel $y_{i}$ existieren
2. Der Unterschreiber berechnet $s:=(k+x_{1}\cdot e+x_{2}\cdot e+x_{3}\cdot e+\dotsb )$
3. Beim Verifizieren ist $r_{v}:=g^{s}\cdot y_{1}^{-e}\cdot y_{2}^{-e}\cdot y_{3}^{-e}\cdot \ldots$

Batch verification

Wenn mit $(r,s)$ unterschrieben wird, so ist es möglich, Signaturen und öffentliche Schlüssel zusammen zu rechnen.

$s:=s_{1}+s_{2}+s_{3}+\dotsb$

$r:=r_{1}\cdot r_{2}\cdot r_{3}\cdot \ldots$

$y:=y_{1}\cdot y_{2}\cdot y_{3}\cdot \ldots$

Dies kann verwendet werden, um mehrere Signaturen gleichzeitig zu verifizieren. Das könnte in der Bitcoin-Blockchain verwendet werden, damit nicht alle Nodes alle Transaktionen validieren müssen.

Rogue key attack

Man sollte $y$ nicht als Signatur vertrauen, da nicht erkennbar ist, ob es die Summe der öffentlichen Schlüssel ist oder nur der öffentliche Schlüssel einer Partei.

Bellare-Neven-Verfahren

Eine Lösung ist, dass jede Partei den Hash aller öffentlichen Schlüssel mit-unterschreibt.

1. $L:=H(y_{1}||y_{2}||y_{3}||\dotsb )$
2. $r$ bleibt das Produkt der einzelnen noncen: $r:=r_{1}\cdot r_{2}\cdot r_{3}\cdot \ldots$
3. $s_{i}$ ist eine partielle Signatur die jeder für sich berechnet $s_{i}:=k_{i}+x\cdot H(L,y_{i},r,m)$
4. die danach zusammen addiert werden: $s:=s_{1}+s_{2}+s_{3}+\dotsb$

Mit $g^{s}=r\cdot y_{1}^{-H(L,y_{1},r,m)}\cdot y_{2}^{-H(L,y_{2},r,m)}\cdot y_{3}^{-H(L,y_{3},r,m)}\cdot \ldots$ kann man es verifizieren.

MuSig

1. $L:=H(y_{1}||y_{2}||y_{3}||\dotsb )$
2. $a_{i}:=H(L||y_{i})$
3. $y:=y_{1}^{a_{1}}\cdot y_{2}^{a_{2}}\cdot y_{3}^{a_{3}}\cdot \ldots$ so dass: $y:=g^{x_{1}\cdot a_{1}+x_{2}\cdot a_{2}+x_{3}\cdot a_{3}+\dotsb }$
4. $r:=r_{1}\cdot r_{2}\cdot r_{3}\cdot \ldots$ so dass: $r:=g^{k_{1}+k_{2}+k_{3}+\dotsb }$ Man sollte $r_{i}$ erst mit den anderen Parteien teilen, wenn man ein Commitment auf deren $r_{i}$ erhalten hat.
5. $c:=H(y||r||m)$
6. $s_{i}:=r_{i}+ca_{i}x_{i}$
7. $s:=s_{1}+s_{2}+s_{3}+\dotsb$

Dieses Verfahren hat den Vorteil, dass nur die involvierten Parteien die einzelnen öffentlichen Schlüssel kennen müssen. Ein Außenstehender kann mit dem kombinierten öffentlichen Schlüssel bestätigen, dass es sich um eine valide Signatur handelt. Besonders bei Blockchain-Anwendungen, in denen Privatsphäre wertvoll und Speicherplatz knapp ist, könnte das Schnorr-Verfahren, am Beispiel der Bitcoin-Blockchain bis zu 25 % Speicherplatz einsparen.

Sicherheitsdiskussion (informell)

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 das Schnorr-Signatur-Schema berechnen kann, kann auch den Diskreten Logarithmus berechnen. 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 ein Orakel für die Funktionswerte berechnen. Mit Hilfe eines Widerspruchsbeweises 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 am 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$.

Anforderung an die Zufallszahlen

Aus den obigen Ausführungen folgt, dass sich die Zufallszahlen k, die zur Berechnung der Signatur verwendet werden, 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.

Fälschung der Signatur ohne Kenntnis des privaten Schlüssels

In den meisten Betrachtungen zur digitale Signatur wird eine Fragestellung ganz ausgeklammert. Es wird unterstellt, dass die Signatur nur zu fälschen sei, wenn der private Schlüssel x vom Angreifer ermittelt werden kann. Es ist jedoch auch denkbar zu einer vorgegebenen Signatur, zu einem Wertepaar (e,s), eine gefälschte Nachricht m zu finden, so dass die Prüfung der Signatur erfolgreich ist. Dazu genügt es, wenn der Hashwert H(r || m) den gewünschten, vom Fälscher erwünschten Wert, nämlich den vorgegebenen Wert e ergibt. Um dies auszuschließen, muss die Hashfunktion Preimage-resistent sein.

Eine solche Fälschung würde jedoch nur die Fälschung einer einzigen Nachricht ermöglichen. Wichtiger ist daher die Geheimhaltung des privaten Schlüssels x. Die Geheimhaltung ist mathematisch beweisbar sichergestellt, wenn der Zufallswert k echt zufällig und gleichverteilt ist.

Literatur

• Claus Peter Schnorr: Efficient Signature Generation by Smart Cards. Journal of Cryptology, Vol. 4, 1991, S. 161–174. Online (PDF; 0,7 MB).
• Bruce Schneier: Angewandte Kryptographie. Addison-Wesley 1996, ISBN 3-89319-854-7, S. 583.

Weblinks

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