Fiat-Shamir-Protokoll

Das Fiat-Shamir-Protokoll i​st ein Protokoll a​us dem Gebiet d​er Kryptografie, m​it dem m​an sich jemandem gegenüber authentisieren kann. Dazu z​eigt man, d​ass man e​ine Quadratwurzel (privater Schlüssel) e​iner vorher veröffentlichten Quadratzahl (öffentlicher Schlüssel) kennt. Bei d​em Verfahren w​ird nur e​in einziges Bit d​es privaten Schlüssels preisgegeben, nämlich d​as Vorzeichen. Eine Variante i​st das Feige-Fiat-Shamir-Protokoll, b​ei dem k​eine Information über d​en privaten Schlüssel preisgegeben wird. Man spricht deswegen v​on einem Zero-Knowledge-Protokoll. Insbesondere i​st das Protokoll perfekt zero-knowledge. Das heißt, e​s gibt e​inen Simulations-Algorithmus, d​er in polynomieller Zeit e​ine Mitschrift erzeugt, d​ie von e​iner echten Interaktion n​icht zu unterscheiden ist.

Das Fiat-Shamir-Protokoll w​urde im Jahr 1986 v​on Amos Fiat u​nd Adi Shamir vorgestellt. An d​er Entwicklung d​es Feige-Fiat-Shamir-Protokolls w​ar auch Uriel Feige beteiligt.

Das Verfahren arbeitet interaktiv, das heißt, es finden mehrere Runden zwischen Geheimnisträger und dem Prüfer statt. In jeder Runde kann die Kenntnis der Zahl zu 50 % bewiesen werden. Nach zwei Runden bleibt eine Unsicherheit von 25 %, nach der dritten Runde nur noch 12,5 % usw. Nach ${\displaystyle n}$ Runden beträgt die Unsicherheit ${\displaystyle 2^{-n}}$.

Die Sicherheit des Fiat-Shamir-Protokolls beruht auf der Schwierigkeit, Quadratwurzeln im Restklassenring ${\displaystyle \mathbb {Z} _{n}}$ zu berechnen. Diese Berechnung ist genauso schwierig, wie die Zahl ${\displaystyle n=p\cdot q}$ (${\displaystyle p}$ und ${\displaystyle q}$ sind Primzahlen) zu faktorisieren und damit praktisch nicht durchführbar, wenn die Zahlen hinreichend groß sind.

Protokoll

Beim Fiat-Shamir-Protokoll wird eine vertrauenswürdige dritte Partei benötigt. Diese veröffentlicht einen RSA-Modul ${\displaystyle n=p\cdot q}$, dessen Primfaktoren ${\displaystyle p}$ und ${\displaystyle q}$ sie geheim hält. Die Beweiserin (Geheimnisträgerin) Peggy wählt eine zu ${\displaystyle n}$ teilerfremde Zahl ${\displaystyle s}$ als persönliches Geheimnis, mit dem sie sich Victor (V wie Verifizierer) gegenüber authentisieren will. Diese darf sie niemandem weitergeben. Sie berechnet ${\displaystyle v\equiv s^{2}{\bmod {n}}}$ und registriert ${\displaystyle v}$ als öffentlichen Schlüssel bei der dritten Partei.

Eine einzelne Runde im Fiat-Shamir-Protokoll besteht aus den folgenden Aktionen:

1. Peggy wählt eine Zufallszahl ${\displaystyle r}$, berechnet ${\displaystyle x\equiv r^{2}{\bmod {n}}}$ und sendet ${\displaystyle x}$ an Victor.
2. Victor wählt zufällig ein ${\displaystyle e\in \{0,1\}}$ und sendet dies an Peggy.
3. Peggy berechnet ${\displaystyle y\equiv r\cdot s^{e}{\bmod {n}}}$ und sendet ${\displaystyle y}$ an Victor.
4. Victor überprüft, ob ${\displaystyle y^{2}{\pmod {n}}\equiv x\cdot v^{e}{\pmod {n}}}$ gilt.

Dieses Protokoll ist noch nicht Zero-Knowledge, da es ein Bit Information über ${\displaystyle r\,{\bmod {n}}}$ preisgibt: Würde Viktor auf irgendeine Weise erfahren, dass ${\displaystyle r\equiv \pm \,c\,{\bmod {n}}}$ für eine Zahl ${\displaystyle c}$ gilt, könnte er nach Ausführung des Protokolls sicher entscheiden, ob ${\displaystyle r\equiv c\,{\bmod {n}}}$ oder ${\displaystyle r\equiv -c\,{\bmod {n}}}$ gilt; er hätte das fehlende Bit Information (das Vorzeichen von ${\displaystyle c}$ bzw. ${\displaystyle r}$) also aus den Daten des Protokolls gewonnen.

Im Feige-Fiat-Shamir-Protokoll[1] sendet Peggy im ersten Schritt entweder ${\displaystyle x}$ oder ${\displaystyle -x\,{\bmod {n}}}$ an Victor. Die Wahl, welchen Wert sie sendet, trifft sie zufällig. Viktor prüft dann im letzten Schritt, dass entweder ${\displaystyle y^{2}\equiv x\cdot v^{e}{\bmod {n}}}$ oder ${\displaystyle y^{2}\equiv -x\cdot v^{e}{\bmod {n}}}$ gilt. Dadurch wird auch das Vorzeichen von ${\displaystyle c}$ nicht preisgegeben und das Protokoll ist Zero-Knowledge.

Schwächen

Für die Sicherheit des Protokolls ist die Wahl der Zufallszahl r von großer Bedeutung.
Wird dasselbe ${\displaystyle r}$ zweimal verwendet und ist ${\displaystyle e}$ dabei einmal 0 und einmal 1, lässt sich der private Schlüssel berechnen.

Beispiel

In beiden Fällen hat ${\displaystyle x\equiv r^{2}{\bmod {n}}}$ denselben Wert.

1. Runde
   • ${\displaystyle e_{1}=0}$
   • Peggy überträgt: ${\displaystyle y_{1}\equiv r\,{\bmod {n}}}$
2. Runde
   • ${\displaystyle e_{2}=1}$
   • Peggy überträgt: ${\displaystyle y_{2}\equiv r\cdot s{\bmod {n}}}$

Ein Angreifer kann nun einfach ${\displaystyle s}$ berechnen. Damit ist ${\displaystyle s}$ kein Geheimnis mehr, das nur Peggy kennt.
${\displaystyle s\equiv y_{2}\cdot r^{-1}\equiv y_{2}\cdot y_{1}^{-1}{\bmod {n}}}$

Quellen

• Albrecht Beutelspacher, Jörg Schwenk, Klaus-Dieter Wolfenstetter: Moderne Verfahren der Kryptographie. Vieweg+Teubner, Braunschweig/Wiesbaden 2010, 7. Auflage, ISBN 978-3-8348-1228-5, S. 49–50
• Amos Fiat, Adi Shamir: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Proceedings on Advances in Cryptology - CRYPTO '86. Springer-Verlag, 1987, ISBN 0-387-18047-8, S. 186–194

Einzelnachweise

1. Uriel Feige, Amos Fiat, Adi Shamir: Zero-knowledge proofs of identity. In: Journal of Cryptology. Band 1, Nr. 2, 1. Juni 1988, ISSN 1432-1378, S. 77–94, doi:10.1007/BF02351717.