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<ref>{{#if:{{#ifexpr:{{#if:EP|0|1}} or {{#if:0384475|0|1}}|1}}||}}{{#if: {{#invoke:Expr|TemplateBooland}}|{{#ifeq:|Patentanmeldung|Patentanmeldung|{{#ifeq:|Gebrauchsmuster|Gebrauchsmuster|Patent}}}} {{#if:{{#invoke:TemplUtl|faculty|}}|EP0384475|{{#switch: {{{DB}}} | DEPATIS =EP0384475 | WIPO = EP0384475 | Google = EP0384475 | #default =EP0384475 }}}}{{#if:1990-02-22|:|.}}{{#if:| {{{Titel}}}.}}{{#if:1990-02-22| Angemeldet am {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}{{#if:|,}}}}{{#if:|{{#if:1990-02-22| veröffentlicht am | Veröffentlicht am }}{{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}{{#if:|,}}}}{{#if:| Anmelder: {{{Anmelder}}}{{#if:|,}}}}{{#if:| Erfinder: {{{Erfinder}}}}}{{#if:| ({{{Kommentar}}})}}{{#if:1990-02-22|.}}‌}}{{#invoke:TemplatePar|match |template= Vorlage:Patent |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Patent}} |format= |preview= |1=Land= ABC+ |2=V-Nr= /^[0-9A-Z]+$/ |3=Titel= * |4=Erfinder= * |5=Anmelder= * |6=A-Datum= * |7=V-Datum= * |8=Typ= ASCII |9=Code= ASCII |10=Kommentar= * |11=KeinLink= ASCII |12=DB=ASCII }}</ref><ref>{{#if:{{#ifexpr:{{#if:US|0|1}} or {{#if:4995082|0|1}}|1}}||}}{{#if: {{#invoke:Expr|TemplateBooland}}|{{#ifeq:|Patentanmeldung|Patentanmeldung|{{#ifeq:|Gebrauchsmuster|Gebrauchsmuster|Patent}}}} {{#if:{{#invoke:TemplUtl|faculty|}}|US4995082|{{#switch: {{{DB}}} | DEPATIS =US4995082 | WIPO = US4995082 | Google = US4995082 | #default =US4995082 }}}}{{#if:1990-02-23|:|.}}{{#if:| {{{Titel}}}.}}{{#if:1990-02-23| Angemeldet am {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}{{#if:|,}}}}{{#if:|{{#if:1990-02-23| veröffentlicht am | Veröffentlicht am }}{{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}{{#if:|,}}}}{{#if:| Anmelder: {{{Anmelder}}}{{#if:|,}}}}{{#if:| Erfinder: {{{Erfinder}}}}}{{#if:| ({{{Kommentar}}})}}{{#if:1990-02-23|.}}‌}}{{#invoke:TemplatePar|match |template= Vorlage:Patent |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Patent}} |format= |preview= |1=Land= ABC+ |2=V-Nr= /^[0-9A-Z]+$/ |3=Titel= * |4=Erfinder= * |5=Anmelder= * |6=A-Datum= * |7=V-Datum= * |8=Typ= ASCII |9=Code= ASCII |10=Kommentar= * |11=KeinLink= ASCII |12=DB=ASCII }}</ref> und exklusiv an RSA sowie nicht-exklusiv an Siemens lizenziert; das Patent ist am 23. 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 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:

1. 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.
2. Frage (Challenge): V wählt <math>e</math> zufällig mit <math>0 < e < q</math> und sendet <math>e</math> an P.
3. 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 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 <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 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, 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 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 />