Schnorr-Signatur

aus Wikipedia, der freien Enzyklopädie

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

[Bearbeiten] Parameter

[Bearbeiten] 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. Er argumentiert, dass Schlüssel- und Signaturlängen sich auf $| G |$ beziehen, das Sicherheitsniveau sich hingegen am größeren $|Z_p^*|$ orientiert.

[Bearbeiten] Privater Schlüssel

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

$x$ mit $0 < x < q$

[Bearbeiten] Öffentlicher Schlüssel

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

$y = g x$

[Bearbeiten] Unterschreiben

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

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

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

[Bearbeiten] Verifizieren

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

Setze $r_v := g^s \cdot y^e$
Setze $e v : = H (m | | r v)$
Akzeptiere die Unterschrift genau dann, wenn $e v = e$ ist.

[Bearbeiten] Sicherheitsdiskussion (informell)

Die Sicherheit der Schnorr-Signatur ist auf die Komplexität des diskreten Logarithmus beweisbar zu reduzieren, d. h. wer das Schnorr-Signatur-Schema bricht, kann auch effizient den diskreten Logarithmus berechnen. Von diesem Problem nimmt man allerdings nach Jahrzehnten intensiver Forschung an, dass es effizient nicht zu lösen ist. Diese beweisbare Reduktion auf bekannte, als schwierig eingestufte Probleme ist typisch für Verfahren 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. Angenommen, es gäbe einen erfolgreichen Unterschriftenfälscher. 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.

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

Die Division durch $s 1 - s 2$ ist möglich, da die Differenz modulo q ungleich 0 ist da $q$ prim ist, auch ein Inverses modulo q existiert.

[Bearbeiten] Weblinks

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

[Bearbeiten] Einzelnachweise

↑ Patent EP 0384475 vom 22. Februar 1990, Patent US 4995082 vom 23. Februar 1990

Kategorie: Signaturverfahren

See also ebooksgratis.com: no banners, no cookies, totally FREE.