Schnorr-Identifikation

aus Wikipedia, der freien Enzyklopädie

Die Schnorr-Identifikation ist ein 1989/91 vom deutschen Mathematikprofessor Claus-Peter Schnorr entworfenes kryptographisches Identifikation-Schema. Die Sicherheit beruht auf der Komplexität des Diskreten Logarithmus in endlichen Gruppen. Die Schnorr-Signatur leitet sich aus der Schnorr-Identifikation ab, indem wie bei der Fiat-Shamir-Identifikation die Interaktion durch den Einsatz einer kryptographischen Hashfunktion ersetzt wird. Das Verfahren ist von Schnorr patentiert.^[1] Es ist exklusiv an RSA lizenziert (Siemens hat aber eine nicht-exklusive Lizenz).

[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

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] Drei-Schritt-Protokoll

Die Prover P identifiziert sich gegenüber Verifier V durch ein Protokoll bestehend aus 3 Schritten:

Hinterlegung (Commitment): P wählt $k$ zufällig mit $0 < k < q$ und senden $r : = g k$ .
Frage (Challenge): V $e$ zufällig mit $0 < e < q$ und sendet $e$ ans P.
Antwort(Response): P sendet $s := (k + xe) \mod q$ an V.

V akzeptiert die Antwort genau dann, wenn $g s = r y e$

[Bearbeiten] Sicherheitsdiskussion (informell)

Die Sicherheit der Schnorr-Identifikation ist auf die Komplexität des diskrete Logarithmus' beweisbar zu reduzieren, d.h. wer das Schema bricht, kann auch effizient den diskrete Logarithmus berechen. Von diesem Problem nimmt man allerdings nach Jahrzehnten intensiver Forschung an, dass dieses effizient nicht zu lösen ist. Diese beweisbare Reduktion auf bekannte, als schwierige eingestufte Probleme ist typisch für Public-Key-Verfahren.

Angenommen, es gäbe einen erfolgreichen Betrüger. 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 zur Identifikation, speichere den Zustand vor dem Senden der Frage $e 1$ an den Betrüger.
Wiederhole die Simulation an gespeicherten Zustand, wähle ein zufälliges $e 2$ als Frage (mit großer Wahrscheinlichkeit $1 / q$ ist dies ungleich $e 1$ ).

Seien $s 1$ und $s 2$ die beiden (verschiedenen) Antworten zum gleichen 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.