Rechnernetze

Zero-Knowledge-Protokolle

Problemstellung

Eine wichtige Frage stellt sich bei der Authentisierung einer Person durch ein Passwort. Sobald ein Passwort einmal genannt wurde, ist es nicht mehr geheim. Beispielsweise kann das Verfahren zur Authentisierung ein Passwort nur einmal schützen. Wird dieses Passwort jemanden mitgeteilt, so kann dieser es in Zukunft selbst verwenden und somit missbrauchen. Mögliche Vorkehrungen sind die Verwendung von Einmalpasswörtern (z.B. Transaktionsnummern im Bankverkehr) oder Methoden, die die Kenntnis eines Passworts belegen ohne dem Frager dieses offen zu legen (d.h. dem Frager keine Information über das Passwort übermitteln, daher auch Zero-Knowledge-Protokolle).

Ein Lösungsbeispiel

Ein Beispiel hierfür ist ein geheimes Lösungsverfahren für ein spezielles Problem, z.B. zur Lösung von Gleichungen höheren Grads. Zur Lösung kubischer Gleichungen wurde von Nicolò Tartaglia (1456-1526) ein Verfahren entwickelt und zunächst geheim gehalten. Den Nachweis der Kenntnis eines Lösungsverfahrens konnte er jederzeit erbringen, indem er eine entsprechende Aufgabe in angemessener Zeit löste.

Das Fiat-Shamir-Protokoll

Von Fiat und Shamir ist ein Verfahren entwickelt worden, welches lediglich eine bestimmte Zahl s als Geheimnis besitzt. Veröffentlicht wird lediglich das Quadrat dieser Zahl gerechnet modulo einer Zahl m. Es ist ein schwieriges, rechenzeitaufwendiges Problem zu einer Zahl die Quadratwurzel (mod m) zu finden, wenn m=p*q das Produkt zweier großer Primzahlen ist.

Um die Kenntnis der Zahl s nachzuweisen, ohne diese offen zu legen, verwendet man folgendes Protokoll.

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=s² 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=r² 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=r² mod m ist.
Fordert Bert y, so kann Bert prüfen, ob y²*x=s²/r²*r²=v das Quadrat des Geheimnisses ist.

Dieser Vorgang wird solange wiederholt, bis Bert mit ausreichender Wahrscheinlichkeit sicher ist, dass Alf das Geheimnis s kennt.

Kennt Alf das Geheimnis nicht, so kann er zwar zu v und einem beliebigen y einfach x=v/y² berechnen, aber aus x=r² kann Alf nicht einfach r bestimmen; oder Alf kann zu einem beliebigen r einfach x=r² bestimmen, aber aus diesem x nicht einfach y bestimmen. Bert überprüft also, ob Alf wirklich die Quadratwurzel aus x kennt, und ob y²*x=v ist. Allerdings darf Alf nicht gleichzeitig y und r senden, da sonst aus y=s/r einfach s berechnet werden könnte. Da nur eine der beiden Zahlen r oder y gefälscht werden kann, kann Bert sich durch zufällige Auswahl von der Richtigkeit einer dieser beiden Zahlen überzeugen. Wegen der zufälligen Wahl ist Bert jedoch bei jedem Durchgang nur zu 50% überzeugt, dass Alf nicht betrügt. Wird diese Überprüfung jedoch mehrfach wiederholt, so kann nach n Schritten davon ausgegangen werden, dass Alf nur mit einer Wahrscheinlichkeit von 0,5ⁿ betrügt, also nach 10 Schritten zu 0,1%, nach 20 Schritten zu 0,0001% usw. Bert kann also selbst bestimmen, mit welcher Sicherheit er Alfs Legitimität nachweisen will.

Sind zu m=p*q die Primfaktoren p und q bekannt, so kann zu einer beliebigen Zahl v mit großer Wahrscheinlichkeit und relativ effizient die Quadratwurzel s berechnet werden. Wird v beispielsweise aus einer Identifikation wie Name, Kartennummer usw. hergeleitet, so lässt sich (u.U. mit freier Zusatzzahl) ein quadratischer Rest v bestimmen, zu dem es eine Quadratwurzel gibt. Auf diese Weise lassen sich Chipkarten vor Fälschungen schützen.

Die Sicherheit des Verfahrens beruht also darauf, dass große Zahlen nur schwierig zu faktorisieren sind, also zu m die Primfaktoren p und q zu finden.