Fiat-Shamir-Protokoll

Das Fiat-Shamir-Protokoll ist ein Protokoll aus dem Gebiet der Kryptografie, mit dem man sich jemandem gegenüber authentisieren kann. Dazu zeigt man, dass man eine Quadratwurzel einer vorher veröffentlichten Quadratzahl kennt. Es wird dabei keine Information über die geheime Quadratwurzel preisgegeben; man spricht deswegen von einem Zero-Knowledge-Protokoll. Insbesondere ist das Protokoll perfekt zero-knowledge. Das heißt, es gibt einen Simulator, dessen Ausgabe von einer echten Durchführung des Protokolls nicht unterschieden werden kann.

Das Fiat-Shamir-Protokoll wurde im Jahr 1986 von Amos Fiat und Adi Shamir vorgestellt.

Das Verfahren arbeitet interaktiv, das heißt, es findet ein Austausch zwischen Geheimnisträger und Prüfer statt.

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

Protokoll

Beim Fiat-Shamir-Protokoll wird eine vertrauenswürdige dritte Partei benötigt. Diese veröffenlicht einen RSA-Modul $n=pq$, dessen Primfaktoren $p$ und $q$ sie geheimhält. Die Geheimnisträgerin Peggy (P wie Prover) wählt eine Zahl $s\in \mathbb {Z} *_{n}$ als Geheimnis, mit dem sie sich Victor (V wie Verifier) gegenüber authentisieren will. Sie berechnet $v=s^{2}{\bmod {n}}$ und registriert $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 $r$, berechnet $x=r^{2}{\bmod {n}}$ und sendet $x$ an Victor.
2. Victor wählt zufällig ein $e\in \{0,1\}$ und sendet dies an Peggy. Dabei gibt Victor zu verstehen, ob er ${\sqrt {x}}$ erhalten möchte ($e=0$) oder lieber ${\sqrt {xv}}$ (bei $e=1$).
3. Peggy berechnet $y=r\cdot s^{e}{\bmod {n}}$ und sendet $y$ an Victor.
4. Victor überprüft, ob $y^{2}\equiv x\cdot v^{e}{\pmod {n}}$ gilt.

Quellen

• Albrecht Beutelspacher, Klaus-Dieter Wolfenstetter: Moderne Verfahren der Kryptographie. Vieweg, Braunschweig/Wiesbaden 1995, ISBN 3-528-06590-7, S. 47–49
• 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

Weblinks

• Zero-Knowledge - Fiat-Shamir-Algorithmus