Quelltext der Seite Schnorr-Identifikation

Die '''Schnorr-Identifikation''' ist ein 1989/91 von [[Claus-Peter Schnorr]] entworfenes kryptographisches Identifikations-Schema, das auf der Schwierigkeit beruht, den [[Diskreter Logarithmus|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<ref>{{Patent|Land=EP|V-Nr=0384475|A-Datum=1990-02-22}}</ref><ref>{{Patent|Land=US|V-Nr=4995082|A-Datum=1990-02-23}}</ref> und exklusiv an [[RSA Security|RSA]] sowie nicht-exklusiv an [[Siemens]] lizenziert; das Patent ist am 23.&nbsp;Februar 2010 abgelaufen.

== Parameter ==
=== Systemweite Parameter ===
Alle Benutzer können diese Parameter gemeinsam nutzen:
* Eine Gruppe <math>G</math> primer Ordnung <math>q=|G|</math>. Diese ist [[Zyklische Gruppe|zyklisch]], <math>g</math> sei ein Generator.

Schnorr schlägt vor, eine Untergruppe <math>G</math> von <math>Z_p^*</math> für eine Primzahl <math>p</math> zu wählen. Er argumentiert, dass Schlüssel- und Signaturlängen sich auf <math>|G|</math> beziehen, das Sicherheitsniveau sich hingegen am größeren <math>|Z_p^*|</math> orientiert.

=== Privater Schlüssel ===
Der nur dem Prover P bekannte private Schlüssel besteht aus einer zufällig gewählten Zahl:
* <math>x</math> mit <math>0 < x < q </math>

=== Öffentlicher Schlüssel ===
Der öffentliche Schlüssel ist das <math>x</math> entsprechende Gruppenelement <math>y</math>:
*<math>y = g^{x}</math>

== Drei-Schritt-Protokoll ==
Der Prover P identifiziert sich gegenüber dem Verifier V durch ein Protokoll bestehend aus 3 Schritten:
# Hinterlegung (Commitment): P wählt <math>k</math> zufällig mit <math>0 < k < q</math> und sendet <math>r:=g^k \bmod q</math> an V.
# Frage (Challenge): V wählt <math>e</math> zufällig mit <math>0 < e < q</math> und sendet <math>e</math> an P.
# Antwort (Response): P sendet <math>s := (k + xe) \bmod q</math> an V.

V akzeptiert die Antwort genau dann, wenn <math>g^s = ry^e</math>.

== Sicherheitsdiskussion (informell) ==
Die Sicherheit der Schnorr-Identifikation basiert [[Beweisbare Sicherheit|beweisbar]] auf der Komplexität des [[Diskreter Logarithmus|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 <math>x</math> sich als Logarithmus des öffentlichen Schlüssels <math>y=g^x</math> zur Basis <math>g</math> in der Gruppe <math>G</math> ergibt.

Wäre man andererseits in der Lage, das Verfahren zu brechen, also bei gegebener Gruppe <math>G</math> zu beliebigem Generator <math>g</math> und öffentlichem Schlüssel <math>y</math> auf jede Frage <math>e</math> die korrekte Antwort <math>s</math> zu geben, könnte man damit effizient diskrete Logarithmen berechnen. Um den diskreten Logarithmus von <math>y</math> zur Basis <math>g</math> zu berechnen, kann man nämlich als P folgendermaßen das Protokoll mit <math>g</math> als Generatorparameter und <math>y</math> als öffentlichem Schlüssel nutzen: Man führt das Protokoll mehrmals aus und sendet dabei im ersten Schritt immer dasselbe <math>r</math>, und zwar wiederholt man das Protokoll so oft, bis V in zwei Durchgängen im jeweils zweiten Schritt zwei verschiedene Fragen <math>e</math> gestellt hat. Diese seien <math>e_1</math> und <math>e_2</math>. (Wenn V die Frage <math>e</math> im zweiten Schritt zufällig und gleichverteilt unter den <math>q - 1</math> infrage kommenden Werten wählt, braucht man [[Erwartungswert|im Mittel]]
:<math>\frac{2q-3}{q-2} = 2 + \frac{1}{q-2}</math>
Durchläufe, siehe [[geometrische Verteilung]].) Die zugehörigen Antworten, die man auf <math>e_1</math> bzw. <math>e_2</math> dann im dritten Schritt gegeben hat, seien <math>s_1</math> und <math>s_2</math>. Wegen <math>e_1 \neq e_2</math> gilt <math>e_1 - e_2 \neq 0</math> und weil <math>q</math> eine Primzahl ist, besitzt <math>e_1 - e_2</math> in <math>\Z/q\Z</math> ein multiplikatives [[Inverses Element|Inverses]], also eine Zahl <math>d</math>, für die
:<math>d \cdot \left(e_1 - e_2\right) = 1 \pmod q</math>
gilt (<math>d</math> lässt sich beispielsweise mit dem [[Restklassenring#Invertierbarkeit und Inversenberechnung|erweiterten euklidischen Algorithmus]] effizient bestimmen). Der diskrete Logarithmus von <math>y</math> zur Basis <math>g</math> ist jetzt <math>d \cdot \left(s_1 - s_2\right) \bmod q</math>, denn da <math>s_1</math> und <math>s_2</math> korrekte Antworten auf die Fragen <math>e_1</math> und <math>e_2</math> sind, gilt
:<math>g^{s_1} = ry^{e_1}</math>
und
:<math>g^{s_2} = ry^{e_2}</math>
und es folgt
:<math>
\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}
</math>

== Einzelnachweise ==
<references />

[[Kategorie:Identifikationsprotokoll]]