Schnorr-Identifikation

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}{\bmod {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){\bmod {q}}}$ an V.

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

Die Sicherheit der Schnorr-Identifikation basiert beweisbar auf der Komplexität des diskreten Logarithmus. Von diesem Problem nimmt man allerdings nach Jahrzehnten intensiver Forschung an, dass es nicht effizient zu lösen ist.

Einerseits könnte man mit der Möglichkeit, effizient diskrete Logarithmen zu berechnen, das Verfahren brechen, da der geheime Schlüssel ${\displaystyle x}$ sich als Logarithmus des öffentlichen Schlüssels ${\displaystyle y=g^{x}}$ zur Basis ${\displaystyle g}$ in der Gruppe ${\displaystyle G}$ ergibt.

Wäre man andererseits in der Lage, das Verfahren zu brechen, also bei gegebener Gruppe ${\displaystyle G}$ zu beliebigem Generator ${\displaystyle g}$ und öffentlichem Schlüssel ${\displaystyle y}$ auf jede Frage ${\displaystyle e}$ die korrekte Antwort ${\displaystyle s}$ zu geben, könnte man damit effizient diskrete Logarithmen berechnen. Um den diskreten Logarithmus von ${\displaystyle y}$ zur Basis ${\displaystyle g}$ zu berechnen, kann man nämlich als P folgendermaßen das Protokoll mit ${\displaystyle g}$ als Generatorparameter und ${\displaystyle y}$ als öffentlichem Schlüssel nutzen: Man führt das Protokoll mehrmals aus und sendet dabei im ersten Schritt immer dasselbe ${\displaystyle r}$, und zwar wiederholt man das Protokoll so oft, bis V in zwei Durchgängen im jeweils zweiten Schritt zwei verschiedene Fragen ${\displaystyle e}$ gestellt hat. Diese seien ${\displaystyle e_{1}}$ und ${\displaystyle e_{2}}$. (Wenn V die Frage ${\displaystyle e}$ im zweiten Schritt zufällig und gleichverteilt unter den ${\displaystyle q-1}$ infrage kommenden Werten wählt, braucht man im Mittel

${\displaystyle {\frac {2q-3}{q-2}}=2+{\frac {1}{q-2}}}$

Durchläufe, siehe geometrische Verteilung.) Die zugehörigen Antworten, die man auf ${\displaystyle e_{1}}$ bzw. ${\displaystyle e_{2}}$ dann im dritten Schritt gegeben hat, seien ${\displaystyle s_{1}}$ und ${\displaystyle s_{2}}$. Wegen ${\displaystyle e_{1}\neq e_{2}}$ gilt ${\displaystyle e_{1}-e_{2}\neq 0}$ und weil ${\displaystyle q}$ eine Primzahl ist, besitzt ${\displaystyle e_{1}-e_{2}}$ in ${\displaystyle \mathbb {Z} /q\mathbb {Z} }$ ein multiplikatives Inverses, also eine Zahl ${\displaystyle d}$, für die

${\displaystyle d\cdot \left(e_{1}-e_{2}\right)=1{\pmod {q}}}$

gilt (${\displaystyle d}$ lässt sich beispielsweise mit dem erweiterten euklidischen Algorithmus effizient bestimmen). Der diskrete Logarithmus von ${\displaystyle y}$ zur Basis ${\displaystyle g}$ ist jetzt ${\displaystyle d\cdot \left(s_{1}-s_{2}\right){\bmod {q}}}$, denn da ${\displaystyle s_{1}}$ und ${\displaystyle s_{2}}$ korrekte Antworten auf die Fragen ${\displaystyle e_{1}}$ und ${\displaystyle e_{2}}$ sind, gilt

${\displaystyle g^{s_{1}}=ry^{e_{1}}}$

und

${\displaystyle g^{s_{2}}=ry^{e_{2}}}$

und es folgt

${\displaystyle {\begin{aligned}g^{d\cdot \left(s_{1}-s_{2}\right)}&=g^{d\cdot s_{1}-d\cdot s_{2}}\\&=g^{d\cdot s_{1}}\cdot g^{-d\cdot s_{2}}\\&=\left(g^{s_{1}}\right)^{d}\cdot \left(g^{s_{2}}\right)^{-d}\\&=\left(ry^{e_{1}}\right)^{d}\cdot \left(ry^{e_{2}}\right)^{-d}\\&=r^{d}\cdot y^{d\cdot e_{1}}\cdot r^{-d}\cdot y^{-d\cdot e_{2}}\\&=y^{d\cdot e_{1}-d\cdot e_{2}}\\&=y^{d\cdot \left(e_{1}-e_{2}\right)}\\&=y{\text{.}}\end{aligned}}}$

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