(zu , Kryptographie)

Eine wesentliche Frage stellt sich bei der Authentifizierung einer Person durch ein Passwort: Sobald das Passwort einmal genannt wurde, ist es nicht mehr geheim!

Abhilfe schafft beispielsweise die Verwendung von Einmalpasswörtern (z.B. Transaktionsnummern beim Electronic Banking). Daneben bestehen Methoden, die die Kenntnis eines Passwortes belegen, ohne dass dieses genannt werden muss. Solche Protokolle heißen deshalb Zero-Knowledge-Protokolle.

Das Fiat-Shamir-Protokoll ist ein solches Zero-Knowledge-Protokoll. Es wurde von Amos Fiat und Adi Shamir 1986 vorgestellt. Es erlaubt, seinem Gegenüber zu beweisen, dass man eine geheime Zahl s kennt, ohne diese Zahl selbst preiszugeben.

Das Verfahren arbeitet interaktiv, d.h. es finden mehrere Runden zwischen dem Geheimnisträger und dem Prüfer statt: In jeder Runde kann die Kenntnis der Zahl zu 50 % bewiesen werden, nach 2 Runden bleibt eine Restunsicherheit von 25 %, nach der 3. Runde nur mehr 12,5 % …usw.

Nehmen wir also an, Alice möchte Bob von der Kenntnis der geheimen Zahl s überzeugen, ohne die Zahl selbst zu nennen. Dazu geht sie so vor: Alice wählt einen Modul m = p · q und veröffentlicht m und v = s² (mod m). Das Paar (m, v) bildet den öffentlichen Schlüssel des Verfahrens. Um Bob von der Kenntnis von s zu überzeugen geht Alice nun so vor:

• Alice wählt eine zufällige Zahl r.

• Alice sendet deren Quadrat x = r² (mod m) an Bob.

• Bob darf jetzt genau eine der Zahlen r oder y = r · s (mod m) von Alice anfordern. Um dies zu entscheiden, wählt er ein Zufallsbit, also 0 oder 1. Fordert Bob r, os kann Bob prüfen, ob r eine Quadratwurzel von x = r² (mod m) ist. Fordert Bob y, so kann Bob prüfen, ob y² = r² · s² = x · v gilt (x und v sind ja bekannt).

• Dieser Vorgang wird solange wiederholt, bis Bob mit ausreichender Wahrscheinlichkeit sicher ist, dass Alice das Geheimnis s kennt.

Zurück zu Lernpfad Kryptographie | GeoGebra 3.2: Texte codieren, Listen bearbeiten, Restklassenarithmetik ...