Schnorr-Identifikation – Wikipedia

Die Schnorr-Identifikation ist ein 1989/91 von Claus-Peter Schnorr entworfenes kryptographisches Identifikations-Schema, das auf der Schwierigkeit beruht, den diskreten Logarithmus zu berechnen. Aus der Schnorr-Identifikation leitet sich die Schnorr-Signatur ab. Diese digitale Signatur erfordert eine kryptographische Hashfunktion, eine mehrstufige Interaktion wie bei der Fiat-Shamir-Identifikation ist dagegen nicht erforderlich. Schnorr-Identifikation und Schnorr-Signatur wurden patentiert^[1][2] und exklusiv an RSA sowie nicht-exklusiv an Siemens lizenziert; das Patent ist am 23. Februar 2010 abgelaufen.

Alle Benutzer können diese Parameter gemeinsam nutzen:

• Eine Gruppe ${\displaystyle G}$ primer Ordnung ${\displaystyle q=|G|}$. Diese ist zyklisch, ${\displaystyle g}$ sei ein Generator.

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

Der nur dem Prover P bekannte private Schlüssel besteht aus einer zufällig gewählten Zahl:

• ${\displaystyle x}$ mit ${\displaystyle 0<x<q}$

Der öffentliche Schlüssel ist das ${\displaystyle x}$ entsprechende Gruppenelement ${\displaystyle y}$:

• ${\displaystyle y=g^{x}}$

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

1. Hinterlegung (Commitment): P wählt ${\displaystyle k}$ zufällig mit ${\displaystyle 0<k<q}$ und sendet ${\displaystyle r:=g^{k}\mod q}$ an V.
2. Frage (Challenge): V wählt ${\displaystyle e}$ zufällig mit ${\displaystyle 0<e<q}$ und sendet ${\displaystyle e}$ an P.
3. Antwort (Response): P sendet ${\displaystyle s:=(k+xe)\mod q}$ an V.

V akzeptiert die Antwort genau dann, wenn ${\displaystyle g^{s}=ry^{e}}$

Die Sicherheit der Schnorr-Identifikation ist auf die Komplexität des diskreten Logarithmus beweisbar zu reduzieren, d. h. wer das 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 schwierige eingestufte Probleme ist typisch für Public-Key-Verfahren.

Angenommen, es gäbe einen erfolgreichen Betrüger – einen Betrüger also, der also aus dem öffentlichen Schlüssel effizient ${\displaystyle y=g^{x}}$ den geheimen Schlüssel ${\displaystyle x}$ bestimmen kann –, so müsste dieser Betrüger dazu in der Lage sein, effizient den diskreten Logarithmus ${\displaystyle x}$ von ${\displaystyle y}$ zu berechnen – im Widerspruch zur Annahme, der diskrete Logarithmus sei schwierig.

1. Simuliere den Algorithmus zur Identifikation, speichere den Zustand vor dem Senden der Frage ${\displaystyle e_{1}}$ an den Betrüger.
2. Wiederhole die Simulation an gespeicherten Zustand, wähle ein zufälliges ${\displaystyle e_{2}}$ als Frage (mit großer Wahrscheinlichkeit ${\displaystyle 1/q}$ ist dies ungleich ${\displaystyle e_{1}}$).

1. Seien ${\displaystyle s_{1}}$ und ${\displaystyle s_{2}}$ die beiden (verschiedenen) Antworten zum gleichen Zufallswert ${\displaystyle k}$ bzw. ${\displaystyle r}$
2. Es gilt ${\displaystyle s_{1}-s_{2}=(k+xe_{1})-(k+xe_{2})=x(e_{1}-e_{2}){\bmod {q}}}$, also ${\displaystyle x=(s_{1}-s_{2})/(e_{1}-e_{2}){\bmod {q}}}$. Die Division durch ${\displaystyle e_{1}-e_{2}}$ ist möglich, da die Differenz modulo q ungleich 0 ist da ${\displaystyle q}$ prim ist, auch ein Inverses modulo q existiert.

1. ↑ Patent EP0384475: Angemeldet am 22. Februar 1990.‌
2. ↑ Patent US4995082: Angemeldet am 23. Februar 1990.‌