Fiat-Shamir-Protokoll

kryptografisches Verfahren

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 (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 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 polynomieller Zeit eine 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 Runden beträgt die Unsicherheit .

Die Sicherheit des Fiat-Shamir-Protokolls beruht auf der Schwierigkeit, Quadratwurzeln im Restklassenring zu berechnen. Diese Berechnung ist genauso schwierig, wie die Zahl ( und sind Primzahlen) zu faktorisieren und damit praktisch nicht durchführbar, wenn die Zahlen hinreichend groß sind.

Protokoll

Bearbeiten

Beim Fiat-Shamir-Protokoll wird eine vertrauenswürdige dritte Partei benötigt. Diese veröffentlicht einen RSA-Modul  , dessen Primfaktoren   und   sie geheim hält. Die Beweiserin (Geheimnisträgerin) Peggy wählt eine zu   teilerfremde Zahl   als persönliches Geheimnis, mit dem sie sich Victor (V wie Verifizierer) gegenüber authentisieren will. Diese darf sie niemandem weitergeben. Sie berechnet   und registriert   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  , berechnet   und sendet   an Victor.
  2. Victor wählt zufällig ein   und sendet dies an Peggy.
  3. Peggy berechnet   und sendet   an Victor.
  4. Victor überprüft, ob   gilt.

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

Im Feige-Fiat-Shamir-Protokoll[1] sendet Peggy im ersten Schritt entweder   oder   an Victor. Die Wahl, welchen Wert sie sendet, trifft sie zufällig. Viktor prüft dann im letzten Schritt, dass entweder   oder   gilt. Dadurch wird auch das Vorzeichen von   nicht preisgegeben und das Protokoll ist Zero-Knowledge.

Schwächen

Bearbeiten

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

Beispiel

Bearbeiten

In beiden Fällen hat   denselben Wert.

  1. Runde
    •  
    • Peggy überträgt:  
  2. Runde
    •  
    • Peggy überträgt:  

Ein Angreifer kann nun einfach   berechnen. Damit ist   kein Geheimnis mehr, das nur Peggy kennt.
 

  • 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

Bearbeiten
  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.