Die folgenden Ausführungen basieren auf diesem hervorragenden Skript der TU Dresden.
Man hat eine Prooferin (Pia) und einen Verifizierer (Viktor). Pia will Viktor - und nur Viktor - davon überzeugen, dass sie ein bestimmtes Wissen hat, ohne jedoch dieses Wissen an Viktor zu vermitteln. Wichtig sind solche Beweissysteme z.B. für Verifizierungsverfahren.
In Quisquater / Guillou: "How to Explain Zero-Knowledge-Protocols to Your Children" wird ein Höhlengleichnis beschrieben:
Wir sehen eine Höhle: Eingang oben, kurzer Quergang, anschliessend eine Verzweigung. Die beiden Gänge vereinigen sich unten zu einen Kreis, die Verbindung ist jedoch durch eine Geheimtür verschlossen. Diese Tür kann nur durch einen Geheimcode geöffnet werden.
Pia will Viktor beweisen, dass sie den Geheimcode zum Öffnen der blauen Tür in der Höhle besitzt, ohne diesen Code jedoch zu verraten. Sie betritt die Höhle, wählt an der Verzweigung beliebig einen der Gänge (rechts oder links) und begibt sich vor die blaue Türe. Nun geht Viktor, der am Eingang gewartet und nicht gesehen hat, welchen Gang Pia gewählt hat, zur Verzweigung und ruft Pia einen der beiden Befehle zu: "Erscheine durch den rechten Gang!" bzw. "Erscheine durch den linken Gang!" (Viktor kann dazu eine Münze werfen.) Je nach Befehl muss Pia nun entweder umkehren (ohne die Geheimtür öffnen zu müssen) oder durch die Geheimtür via Geheimcode in den andern Gang wechseln, um Viktors Befehl zu erfüllen. Falls Pia den Code nicht kennt, beträgt die Wahrscheinlichkeit 0.5, dass sie Viktors Wunsch trotzdem erfüllen kann. - Nun wird dieses Vorgehen jedoch viele Male (zum Beispiel 40-mal) wiederholt. Die Wahrscheinlichkeit, dass Pia jedesmal Glück hat und die Türe nicht öffnen muss, beträgt dann bei 40 Wiederholungen 0.540 = 9.1⋅10-13, ist also praktisch null. Sofern Pia diese 40 Versuche erfolgreich besteht, kann Viktor fast sicher annehmen, dass Pia den Tür-Code tatsächlich kennt, ohne diesen jedoch verraten zu haben.
Kann Viktor dieses fast sichere Wissen, dass Pia den Türcode kennt, auch an eine Drittperson, die nicht anwesend war, weitergeben? Er könnte ja seine Befehle und das Auftauchen von Petra im richtigen Gang filmen und diesen Film als Beweis für Pias Fähigkeit vorführen. Dies wäre jedoch kein Beweis, denn der Film könnte ja manipuliert worden sein (die Fails könnten herausgeschnitten worden sein, oder Viktor und eine code-unwissende Lia (eine Betrügerin) könnten sich abgesprochen haben). Die mit dem Code vertraute Pia kann also nur Viktor - als Live-Beteiligten - überzeugen.
Ein gefälschtes Video kann von einem echten Video, das den wirklichen Vorgang aufzeichnete, nicht unterschieden werden. Da man aus einem gefälschten Video keinerlei Information über den Tür-Code erlangen kann und dieses Video ununterscheidbar zum echten Video ist, kann man folgern, dass man auch aus dem echten Video keinerlei Information über den Tür-Code erhält: Der Vorgang ist ein Zero-Knowledge-Prozess.
Könnte Pia nicht einfach direkt beweisen, dass sie den Code kennt, indem sie Viktor zeigt, in welchen Gang sie eintritt und anschliessend aus dem andern Gang wieder erscheint? Viktor wäre dann direkter Zeuge, dass sie den Tür-Code kennt.
Antwort: Dieser direkte Vorgang könnte aufgezeichnet werden. Pia verlöre dann, wenn sich das Video verbreitete, die Kontrolle darüber, wer wirklich wissen darf, dass sie den Code kennt.
Gilt dies nicht auch für eine Aufzeichnung der oben beschriebenen komplizierteren Art? - Nein, denn Pia könnte behaupten, den Code nicht zu kennen und sich mit Viktor abgesprochen zu haben, und diese Behauptung könnte nicht widerlegt werden (ein gefälschtes Video kann von einem echten nicht unterschieden werden). Viktor allein weiss, ob eine Absprache stattgefunden hat oder nicht, d.h. nur er weiss wirklich, ob Pia den Code kennt oder nicht kennt.
Commitment-Verfahren
Pia legt sich zu Beginn der Interaktion mit Viktor auf einen sogenannten Commitment-Wert fest, der nicht mehr geändert werden kann; Viktor kennt diesen Wert zunächst nicht. Beispiel Höhle: Pia wählt einen der beiden Gänge. Sie kann diesen Wert ("links" bzw. "rechts") nicht mehr ändern, da Viktor sich nachher an den Ort der Verzweigung begibt.
Oft werden für solche Commitments "Einwegfunktionen" verwendet, d.h. Funktionen die mit keinem Computer der Welt invertiert werden können. Beispiel: Man nimmt zwei riesige Primzahlen p und q (mit je ca. 200 - 400 Dezimalstellen; dazu braucht es einen effizienten Algorithmus, der feststellt, ob diese Zahlen überhaupt Primzahlen sind) und multipliziert p mit q. pq ist der Commitment-Wert. Kein Computer kann aus dem Produkt die Faktoren p und q rekonstruieren - die Rechenzeit wäre länger als das Alter des Universums. Das Geheimnis "p" und "q" bleibt gewahrt, aber der Wert pq wird als verpflichtendes Commitment abgegeben.
Interaktive Beweise
Sie entstehen aus einem Dialog zwischen Pia (proofer) und Viktor (verificator). Viktor soll von der Gültigkeit einer bestimmten Behauptung Pias überzeugt werden. Eine 100%-ige Gewissheit kann nicht erreicht werden, jedoch eine beinahe 100%-ige, falls Pia ehrlich spielt. Falls eine betrügerische Lia, die das Geheimnis nicht kennt, daherkommt, soll diese Lia mit einer ebenfalls fast 100%-igen Wahrscheinlichkeit scheitern.
Pia habe etwa ein geheimes Wissen w (etwa die sehr grossen Primzahlen p und q) und daran gekoppelt einen Wert x (z.B. das Produkt von p und q), den auch Viktor erfährt (ohne dass er daraus p und q rekonstruieren kann). Zudem muss in einem Zero-Knowledge-Verfahren die Interaktion so sein, dass Viktor kein zusätzliches Wissen über die Behauptung erhält (ausser dass er am Schluss "fast sicher" entscheiden kann, ob die Behauptung zutrifft oder nicht).
Der Beweisablauf zwischen Pia und Viktor besteht aus sehr vielen Runden, von denen jede in drei Schritten abläuft:
- Pia legt zuhanden Viktors das Commitment fest. Höhlenbeispiel: Sie wählt - von Viktor unbesehen - einen der Gänge - ohne Änderungsmöglichkeit!
- Viktor übermittelt an Pia eine sogenannte "Challenge" c. Höhlenbeispiel: Viktor bittet Pia von links bzw. von rechts wieder zu erscheinen.
- Pia reagiert auf Viktors Bitte, mit Erfolg oder Misserfolg, jedoch immer mit Erfolg, wenn sie das Geheimnis wirklich kennt und sie korrekt spielt.
Unmöglich ist es für Viktor auch, durch Betrug und Protokollverletzungen an Informationen über das Geheimnis zu gelangen. Zudem kann Viktor keine Drittpersonen davon überzeugen, dass Pia das Geheimnis kennt, denn die Filmaufzeichnung könnte gefälscht sein.
Ein Beispiel für ein Zero-Knowledge-Protokoll findet sich hier (Graphenisomorphismus als "Geheimnis").
Das Zero-Knowledge-Beweissystem für quadratische Reste (Fiat-Shamir-Verfahren)
Gearbeitet wird in der Restklassengruppe ℤ*pq, wobei p und q zwei riesige Primzahlen sind.
ℤ*pq besteht aus den zu pq teilerfremden Zahlen g mit 1 ≤ g < pq zusammen mit der Multiplikation modulo pq. Diese Gruppe hat folglich (p-1)(q-1) Elemente. Einige dieser Elemente sind Quadrate ("Quadratische Reste" genannt).
Das Ziehen von Quadratwurzeln in ℤ*pq ist gleich komplex wie das Zerlegen von pq in die beiden Faktoren p und q und für riesige Primzahlen p und q unmöglich.
Pias Geheimnis w ist eine solche Quadratwurzel. x: = w2 mod pq ist öffentlich, ebenso das Produkt n:= pq. Dieses Produkt wird von einer vertrauenswürdigen Drittpartei erzeugt. p und q selber bleiben geheim (auch für Pia!). Pia wählt also ihr Geheimnis w aus ℤ*pq und veröffentlicht x: = w2 mod pq. Viktor kennt also nur x und n = pq. Es ist für ihn unmöglich aus x die Quadratwurzel zu ziehen; p und q kann er ebensowenig eruieren.
Das Protokoll verläuft nun so:
- Pia wählt ein s aus ℤ*pq und sendet a:= s2 mod n an Viktor.
- Viktors Challenge geht so: Er wählt entweder c = 0 oder c = 1 und fordert: "Berechne z: = s⋅wc mod n." (Also: Falls c=0: z=s; falls c=1: z=s⋅w.)
- Pia übermittelt das Resultat z an Viktor, und Viktor prüft, ob z2 = a⋅xc mod n. (Also: Falls c=0 war: z2 =? a; falls c=1 war: z2 =? a⋅x.)
Im Fall der Challenge c = 1 benötigt Pia also das Geheimnis w. Warum wählt dann Viktor überhaupt auch manchmal die Challenge c = 0? Der Grund liegt darin, dass eine betrügerische Lia in Schritt 1 statt a:= s2 mod n in Abweichung vom Protokoll den Wert a:= s2⋅x-1 an Viktor senden könnte, und damit die Challenge c = 1 auch ohne Kenntnis von w erfolgreich, wenn auch betrügerisch, meisterte: Sie übermittelt dann in Schritt 3 einfach z = s (sie weicht also in Schritt 1 und Schritt 3 vom Protokoll ab, um zu betrügen). Viktor prüft dann: ax = (s2⋅x-1) x = s2 = z2, was ihm zutreffend erscheint. Viktor wurde erfolgreich getäuscht. Dieser Betrug (a:= s2⋅x-1 statt a:= s2) fliegt jedoch auf, wenn die Challenge c = 0 (und damit z = s) lautet. Denn dann ist a = s2⋅x-1 ≠ s2 = z2.
Beispiel: ℤ*pq = ℤ*21, d.h. pq = 21.
ℤ*21 hat (3-1)(7-1) = 12 Elemente und die Gruppentafel sieht wie folgt aus:
| ⋅ | 1 | 2 | 4 | 5 | 8 | 10 | 11 | 13 | 16 | 17 | 19 | 20 |
| 1 | 1 | 2 | 4 | 5 | 8 | 10 | 11 | 13 | 16 | 17 | 19 | 20 |
| 2 | 2 | 4 | 8 | 10 | 16 | 20 | 1 | 5 | 11 | 13 | 17 | 19 |
| 4 | 4 | 8 | 16 | 20 | 11 | 19 | 2 | 10 | 1 | 5 | 13 | 18 |
| 5 | 5 | 10 | 20 | 4 | 19 | 8 | 13 | 2 | 18 | 1 | 11 | 16 |
| 8 | 8 | 16 | 11 | 19 | 1 | 17 | 4 | 20 | 2 | 10 | 5 | 13 |
| 10 | 10 | 20 | 19 | 8 | 17 | 16 | 5 | 4 | 13 | 2 | 1 | 11 |
| 11 | 11 | 1 | 2 | 13 | 4 | 5 | 16 | 17 | 8 | 19 | 20 | 10 |
| 13 | 13 | 5 | 10 | 2 | 20 | 4 | 17 | 1 | 19 | 11 | 16 | 8 |
| 16 | 16 | 11 | 1 | 18 | 2 | 13 | 8 | 19 | 4 | 20 | 10 | 5 |
| 17 | 17 | 13 | 5 | 1 | 10 | 2 | 19 | 11 | 20 | 16 | 8 | 4 |
| 19 | 19 | 17 | 13 | 11 | 5 | 1 | 20 | 16 | 10 | 8 | 4 | 2 |
| 20 | 20 | 19 | 18 | 16 | 13 | 11 | 10 | 8 | 5 | 4 | 2 | 1 |
Die violett hinterlegten Zahlen sind quadratische Reste modulo 21. Man sieht: Jeder quadratische Rest kommt vier Mal vor, d.h. hat 4 Quadratwurzeln. Die violette Diagonale wird ab der MItte gespiegelt fortgesetzt, denn es ist z.B. 5⋅5 = (-5)⋅(-5) = (21-5)⋅(21-5) = 16⋅16 = 4.
Dass jeder quadratische Rest genau vier Mal vorkommt, gilt allgemein in ℤ*pq, wo p und q zwei Primzahlen sind.
Zudem gilt: Das Berechnen solcher Quadratwurzeln ist - zwar nicht in unserem Beispiel, jedoch für riesige Werte pq - genau so schwierig (rechenaufwändig) wie das Zerlegen von pq in die Faktoren p und q (für riesige pq-Werte also innert nützlicher Zeitspanne unmöglich).
| Begründungs-Skizze: Sei das Ziehen von Quadratwurzeln in ℤ*pq einfach zu berechnen. Man habe eine Quadratzahl u2 mod pq. Seien u und v zwei nicht entgegengesetzt gleiche Quadratwurzeln dieser Quadratzahl (u2=v2). Im Beispiel der Gruppentafel oben stünden zur Quadratzahl 16 zwei nicht entgegengesetzt gleiche Wurzeln aus {4, 10, 11=(-10), 17=(-4)} zur Auswahl. Es gilt: (u+v)(u-v) = u2-v2 = 0 mod pq => pq teilt (u+v)(u-v) => ohne Beschränkung der Allgemeinheit gilt: p teilt (u+v) und q teilt (u-v) [ansonsten vertausche p und q]. Berechne mithilfe des Euklidschen Algorithmus den ggT von u+v und pq, das ist aber p. Damit hat man p berechnet und durch pq/p auch q. Damit wäre die Faktorisierung von pq ebenso einfach zu berechnen wie das Quadratwurzelziehen modulo pq. Das ist aber nicht so, also ist auch das Quadratwurzelziehen modulo pq genau so schwierig zu berechnen wie das Faktorisieren von pq, nämlich für riesige Primzahlen p und q innert nützlicher Zeitspanne mit heutiger Theorie und Technologie unmöglich. Das Beispiel oben mit pq=21 wäre allerdings sehr unglücklich, da alle violetten Zahlen auch "gewöhnliche" Quadratzahlen in ℤ sind. Im Fall pq=21 kann Pia nämlich die Zerlegung pq berechnen: Sie findet z.B. 52 = 4. Also ist 5 eine Quadratwurzel aus 4. Aber da 4 eine gewöhnliche Quadratzahl ist, findet Pia noch eine zweite Quadratwurzel aus 4, nämlich 2. Sie findet somit: 5 und 2 sind Quadratwurzeln mod 21. Gemäss der Überlegung oben folgt: p teilt (5+2) => ggT(7,21)=7=p => q=3. Dies ist allgemein nicht so. Nehmen wir z.B. pq=13⋅11=143. Pia wählt dann z.B. s=14. 142=53 mod 143 ist keine gewöhnliche Quadratzahl. Bei riesigen Werten pq ist es dann für niemanden, also auch für Pia und Viktor nicht, möglich, eine weitere, nicht entgegengesetzt gleiche Quadratwurzel zu finden - und so sollte es auch sein! Neben pq=21 wäre z.B. auch pq=35 ungünstig: 172=9 mod 35. Zudem ist natürlich auch 32=9 => ggT[(17+3),35]=5=p: Die Faktorzerlegung ist dann für Pia durchführbar. - Dies ist für riesige und gut gewählte pq unmöglich. |
Beispielrechnungen für das Kommunikationsprotokoll (pq = 143, w = 87):
Wir wählen als Beispiel pq = 13⋅11 = 143.
ℤ*143 hat 12⋅10 = 120 Elemente, wir verzichten deshalb auf das Erstellen der Gruppentafel und berechnen die benötigten Werte modulo 143 jeweils ad hoc.
Pias Geheimzahl sei w = 87. Es folgt x = w2 = 133. Wir rechnen stets modulo 143.
In den Beispielen unten ist jeweils eine Runde beschrieben. Es werden sehr, sehr viele Runden gespielt, um die Authentifizierung zu gewährleisten, d.h. die Kenntnis von w zu akzeptieren.
Beispiel 1a: Pia kennt w und spielt ehrlich: w = 87 => x = w2 = 133.
1)
Pia wählt s = 14 (commitment) => a = s2 = 53 (a wird an Viktor gesendet.)
2) Viktor sendet die Challenge c = 1
3) Pia sendet z =
s⋅w = 14⋅87 = 74 (Hier tritt zwar die Geheimzahl auf; sie wird jedoch durch die Multiplikation mit s verschleiert, und s ist für Viktor rechnerisch nicht zu ermitteln.)
4) Viktor prüft: z2 = 742 = 42 =? a⋅x = 53⋅133 = 42: richtig. Viktor akzeptiert die Runde.
Beispiel 1b: Pia kennt w und spielt ehrlich: w = 87 => x = w2 = 133.
1)
Pia wählt s = 14 => a = s2 = 53
2) Viktor sendet c = 0
3) Pia sendet z = s = 14 (Hier wird s übermittelt, dafür taucht im Gegensatz zu 1a die Geheimzahl w nicht auf.)
4) Viktor prüft:
142 = 53 =? a = 53: richtig. Viktor akzeptiert die Runde.
| Achtung: Wählt Pia in verschiedenen Runden zweimal dasselbe s (hier s = 14 in 1a und in einer späteren Runde 1b) und ist c dabei einmal 1 (Beispiel 1a) und einmal 0 (Beispiel 1b), so kann w eruiert werden: Wir haben aus Runde 1a: z1 = 74 = s⋅w und aus Runde 1b: z2 = s = 14 mit demselben s wie in Runde 1 => 74 = 14⋅w => 14-1⋅74 = w = 92⋅74 = 87 = Geheimzahl w. Die Wahl von stets verschiedenen Zahlen s als Zufallszahlen in jeder Runde ist deshalb wichtig; s soll nicht wiederholt werden! Das muss Pia unbedingt sicherstellen! |
Beispiel 2: Eine betrügerische Lia kennt w nicht und spielt unehrlich: x = 133 ist öffentlich, und dies hat auch die Betrügerin Lia erfahren.
1) Lia wählt z.B. s = 16, übermittelt aber in Abweichung vom Protokoll
a = s2⋅x-1 = 113⋅133-1 = 113⋅100 = 3
Bemerkung:
133-1 berechnen wir mithilfe des erweiterten euklidischen Algorithmus'.
2) Viktor sendet c = 1
3)
Lia sendet z = s = 16 in Abweichung vom Protokoll (sie mogelt)
4) Viktor prüft: 162 = 113 =? 3⋅133 = 113: richtig. Viktor akzeptiert die Runde fälschlicherweise, d.h. Lia konnte durch betrügerische Daten die Runde gewinnen, ohne w zu kennen.
Beispiel 3: Lia kennt w nicht und spielt unehrlich: x = 133 ist öffentlich.
1) Lia wählt s = 16, übermittelt aber in Abweichung vom Protokoll a = 3 wie oben
2)
Viktor sendet c = 0
3) Nun ist Lia aufgeschmissen: Um die Runde zu gewinnen, müsste Lia eine √3 modulo 143 finden, was sie - bei riesigen pq-Werten - nicht kann (in unserem "kleinen" Beispiel wäre dies natürlich möglich). Sie sendet z.B. z = s = 16:
4) Viktor prüft:
z2 =? a, d.h. 162 = 113 =? 3: falsch. Der Betrug ist aufgeflogen; das Spiel ist aus.
Dadurch dass Lia statt a=s2 den Wert a = s2⋅x-1 übermittelte, verlor sie die Möglichkeit des Wurzelziehens: Aus s2 hätte sie die Wurzel ziehen können, da sie selber ja von s ausgegangen war; aus dem veränderten Wert s2⋅x-1 findet sie hingegen keine Wurzel (es ist nicht einmal sicher, ob dazu überhaupt eine Wurzel existiert) und verliert im Fall der Challenge c = 0. Lias "Trick" hilft ihr nur bei Challenge c = 1; da kann sie auf das ihr bekannte s zurückgreifen.
| Die Beispiele 2 und 3 zeigen, warum auch die Challenge c = 0 benützt werden soll. Um auch ohne Kenntnis von w zu bestehen, müsste Lia in die Zukunft blicken können, um vorherzusehen, ob Viktor c = 0 oder c = 1 wählen wird. Im Falle c = 0 könnte sie ehrlich spielen, da w nicht benötigt wird, im Fall c = 1 müsste sie unehrlich spielen. Wie immer sie auch spielt, besteht für sie, die w nicht kennt, je nach Challenge-Wahl von Viktor, die Möglichkeit zu scheitern. Immer gewinnen wird sie nur, wenn sie w kennt und ehrlich spielt. |
Beispiel 4: Lia kennt w nicht, spielt aber ehrlich und wählt auf gut Glück die falsche Geheimzahl v, z.B. v = 10; x ist öffentlich = 133.
Bei riesigen Primzahlen p und q ist es für Lia unmöglich, eine √x zu berechnen. So wählt Lia aufs Geratewohl eine Zahl v, in unserem Beispiel v = 10.
1) Lia wählt z.B. s =
20 => a = 114
2) Viktor sendet c = 1
3) Lia sendet z =
s⋅v = 20⋅10 = 200 = 57
4) Viktor prüft:
572 = 103 =? 114⋅133 = 4: falsch; die Zahl v wird zurückgewiesen, das Verfahren erfolglos beendet.
Wir können das Verhalten einer Lia, welche die Geheimzahl w nicht kennt und folglich die blaue Tür nicht öffnen kann, im Höhlengleichnis etwa so darstellen:
Unehrliches Spiel: Damit ist das protokollwidrige Vorgehen von Lia gemeint, wie es oben in den Beispielen 2 und 3 beschrieben ist.
Lia wählt an der Verzweigung einen der Wege ("ehrlich spielen" oder "unehrlich spielen") und muss, da sie an der blauen Tür auf jeden Fall umkehren muss, darauf hoffen, dass Viktors Challenge sie aus demjenigen Gang zurückruft, in dem sie sich gerade befindet (Challenge 0 bei "ehrlich" bzw. 1 bei "unehrlich").
Da Viktors Challenge c = 0 oder c = 1 erst nach der Entscheidung von Lia über "ehrlich" oder "unehrlich" kommt, hat Lia in jedem Durchgang eine Erfolgswahrscheinlichkeit von 0.5. Bei einer sehr grossen Zahl von Durchgängen sinkt die Erfolgswahrscheinlichkeit auf nahezu null. Beim ersten Misserfolg wird die Authentifizierung abgebrochen und das Spiel beendet.
Anmerkung:
Die Produkte pq, wo p und q Primzahlen sind, heissen auch Semiprimzahlen (siehe hier). Und hier die Folge der ersten Semiprimzahlen bis 187.
Werden die riesigen Semiprimzahlen pq als verwendete Schlüssel etwas nachlässig generiert, kann es sein, dass zwei Schlüssel einen gemeinsamen Faktor p aufweisen, Dann kann ein ggT-Programm, das einen neuen Schlüssel mit je einem bisherigen vergleicht, den ggT p und damit auch q in kurzer Zeit herausfinden. Die Faktoren p und q sollten also nur einmal verwendet werden, was bei der riesigen Zufallsauswahl auch wahrscheinlich ist (in der Praxis aber leider schon missachtet wurde).
Weitere Informationen zu Semiprimzahlen, deren Faktorisierung und zum RSA-Verfahren hier.