~2025-20967-3: Tippfehler verbessert

2025-07-16T16:59:00Z

Tippfehler verbessert

Neue Seite

Das '''Fiat-Shamir-Protokoll''' ist ein [[Authentifizierungsprotokoll|Protokoll]] aus dem Gebiet der [[Kryptografie]], mit dem man sich jemandem gegenüber [[Authentifizierung|authentifizieren]] kann. Dazu zeigt man, dass man eine [[Quadratwurzel]] ([[Geheimer Schlüssel|privater Schlüssel]]) einer vorher veröffentlichten Quadratzahl ([[öffentlicher Schlüssel]]) kennt. Bei dem Verfahren wird nur ein einziges Bit des privaten Schlüssels preisgegeben, nämlich das [[Vorzeichenbit|Vorzeichen]]. Eine Variante ist das Feige-Fiat-Shamir-Protokoll, bei dem keine Information über den privaten Schlüssel preisgegeben wird. Man spricht deswegen von einem [[Zero-Knowledge-Protokoll]]. Insbesondere ist das Protokoll [[perfekt zero-knowledge]]. Das heißt, es gibt einen Simulations-[[Algorithmus]], der in [[Polynomialzeit|polynomieller Zeit]] eine [[Mitschrift (Kryptologie)|Mitschrift]] erzeugt, die von einer echten Interaktion nicht zu unterscheiden ist.

Das Fiat-Shamir-Protokoll wurde im Jahr [[1986]] von [[Amos Fiat]] und [[Adi Shamir]] vorgestellt. An der Entwicklung des Feige-Fiat-Shamir-Protokolls war 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 <math>n</math> Runden beträgt die Unsicherheit <math>2^{-n}</math>.

Die Sicherheit des Fiat-Shamir-Protokolls beruht auf der Schwierigkeit, Quadratwurzeln im [[Restklassenring]] <math>\Z_n</math> zu berechnen. Diese Berechnung ist genauso schwierig, wie die Zahl <math>n=p\cdot q</math> (<math>p</math> und <math>q</math> sind Primzahlen) zu faktorisieren und damit praktisch nicht durchführbar, wenn die Zahlen hinreichend groß sind.

== Protokoll ==

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

[[Datei:Fiat-Shamir identification protocol.svg]]
Eine einzelne Runde im Fiat-Shamir-Protokoll besteht aus den folgenden Aktionen:

# Peggy wählt eine [[Zufallszahl]] <math>r</math>, berechnet <math>x \equiv r^2 \bmod n</math> und sendet <math>x</math> an Victor.
# Victor wählt zufällig ein <math>e \in \{0,1\}</math> und sendet dies an Peggy. 
# Peggy berechnet <math>y \equiv r \cdot s^e \bmod n</math> und sendet <math>y</math> an Victor.
# Victor überprüft, ob <math>y^2 \pmod n \equiv x \cdot v^e \pmod n</math> gilt.

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

Im Feige-Fiat-Shamir-Protokoll<ref>{{Literatur |Autor=Uriel Feige, Amos Fiat, Adi Shamir |Titel=Zero-knowledge proofs of identity |Sammelwerk=Journal of Cryptology |Band=1 |Nummer=2 |Datum=1988-06-01 |ISSN=1432-1378 |DOI=10.1007/BF02351717 |Seiten=77–94 |Abruf=}}</ref> sendet Peggy im ersten Schritt entweder <math>x</math> oder <math>-x \, \bmod n</math> an Victor. Die Wahl, welchen Wert sie sendet, trifft sie zufällig. Viktor prüft dann im letzten Schritt, dass entweder <math>y^2 \equiv x \cdot v^e \bmod n</math> oder <math>y^2 \equiv -x \cdot v^e \bmod n</math> gilt. Dadurch wird auch das Vorzeichen von <math>c</math> 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.<br />
Wird dasselbe <math>r</math> zweimal verwendet und ist <math>e</math> dabei einmal 0 und einmal 1, lässt sich der private Schlüssel berechnen.

=== Beispiel ===
In beiden Fällen hat <math>x \equiv r^2 \bmod n</math> denselben Wert.
# Runde
#* <math>e_1 = 0</math>
#* Peggy überträgt: <math>y_1 \equiv r \, \bmod n</math>
# Runde
#* <math>e_2 = 1</math>
#* Peggy überträgt: <math>y_2 \equiv r \cdot s \bmod n</math>

Ein Angreifer kann nun einfach <math>s</math> berechnen. Damit ist <math>s</math> kein Geheimnis mehr, das nur Peggy kennt.<br />
<math>s \equiv y_2 \cdot r^{-1} \equiv y_2 \cdot y_1^{-1} \bmod n</math>

== 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 ==
<references />

[[Kategorie:Identifikationsprotokoll]]

Fiat-Shamir-Protokoll - Versionsgeschichte

~2025-20967-3: Tippfehler verbessert