Zero-Knowledge-Protokolle
Problemstellung
| Authentisierung einer Person durch Passwort
| Passwort einmal genannt: nicht mehr geheim |
| Verfahren zur Authentisierung
kann Passwort nur
einmal schützen |
| Wird Passwort offen gelegt |
| in
Zukunft missbrauchbar |
| Mögliche Abhilfen
| Verwendung
von Einmalpasswörtern
(z.B. Transaktionsnummern im Bankverkehr) |
| andere Methoden, |
| belege Kenntnis eines Passworts ohne dieses offen zu legen
(d.h. keine Information über Passwort übermitteln |
|
| Zero-Knowledge-Protokolle |
|
Ein Lösungsbeispiel
| Beispiel
| geheimes Lösungsverfahren für spezielles Problem
| z.B. Lösung von Gleichungen höheren Grads |
| Lösung kubischer
Gleichungen von Nicolò Tartaglia (1456-1526) entwickelt |
|
zunächst geheim gehalten |
| Nachweis der Kenntnis eines Lösungsverfahrens
konnte er jederzeit erbringen, indem er entsprechende Aufgabe in
angemessener Zeit löste. |
|
|
Das Fiat-Shamir-Protokoll
| Verfahren Fiat und Shamir
| bestimmte Zahl s als Geheimnis |
| Veröffentlicht wird das
Quadrat modulo m |
| schwieriges,
rechenzeitaufwendiges Problem zu einer Zahl die Quadratwurzel (mod m) zu finden,
wenn m=p*q das Produkt zweier großer Primzahlen ist. |
|
| Weise Kenntnis der Zahl s nach, ohne diese offen zu legen, |
| folgendes Protokoll leistet diese |
Alf kenne das Geheimnis s und will Bert
beweisen, dass er s kennt, ohne Bert s zu nennen. |
Alf wählt ein Modul m=p*q und veröffentlicht m und v=s2 mod m. |
Um Bert von der Kenntnis von s zu überzeugen, geht Alf
folgendermaßen vor: |
- Alf wählt eine zufällige Zahl r.
- Alf sendet deren Quadrat x=r2 mod m an Bert.
- Bert darf jetzt genau eine der Zahlen r oder y=s/r mod m von Alf
anfordern
Fordert Bert r, so kann Bert prüfen, ob r eine Quadratwurzel von x=r2
mod m ist.
Fordert Bert y, so kann Bert prüfen, ob y2*x=s2/r2*r2=v
das Quadrat des Geheimnisses ist.
- Dieser Vorgang wird solange wiederholt, bis Bert mit ausreichender
Wahrscheinlichkeit sicher ist, dass Alf das Geheimnis s kennt.
|
| Alf kennt das Geheimnis nicht
| entweder
| zu v und beliebigem y
einfach x=v/y2 berechnen, |
| aus x=r2 nicht
einfach r bestimmen |
|
| oder
| Alf kann zu beliebigem r einfach x=r2
bestimmen |
| aber aus x nicht einfach y bestimmen |
|
| Bert überprüft
| kennt Alf
wirklich Quadratwurzel aus x |
| ist y2*x=v |
|
| nicht gleichzeitig y und r offen legen
| s einfach aus y=s/r berechnbar |
| nur eine der beiden Zahlen r oder y fälschbar |
|
| Bert überzeugt sich durch zufällige Auswahl von Richtigkeit einer dieser beiden
Zahlen
| Wegen zufälliger Wahl ist Bert
nur zu 50% überzeugt |
| Überprüfung wird
mehrfach wiederholt
| n Schritten geht Bert davon aus
| Alf betrügt nur mit Wahrscheinlichkeit 0,5n
| nach 10
Schritten zu 0,1% |
| nach 20 Schritten zu 0,0001% |
| usw. |
|
|
| Bert bestimmt Sicherheit selbst |
|
|
|
| m=p*q, Primfaktoren p und q bekannt
| effizient die Quadratwurzel s berechenbar |
| v bspw. aus Identifikation hergeleitet
| Name, |
|
Kartennummer |
| freie Zusatzzahl |
| usw. |
|
| Quadratwurzel von v bestimmbar |
|
quadratischer Rest v bestimmbar |
| Chipkarten vor Fälschungen schützbar |
|
| Sicherheit des Verfahrens beruht auf
| Schwierigkeit große Zahlen zu faktorisieren |
| zu m=p*q die Primfaktoren p und q finden |
|
|