Fiat-Shamir-Protokoll - LinkFang.de





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 (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 [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 vertrauenswürdige dritte Partei benötigt. Diese veröffentlicht einen 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) 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.

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

  1. Peggy wählt eine Zufallszahl [math]r[/math], berechnet [math]x \equiv r^2 \bmod n[/math] und sendet [math]x[/math] an Victor.
  2. Victor wählt zufällig ein [math]e \in \{0,1\}[/math] und sendet dies an Peggy.
  3. Peggy berechnet [math]y = r \cdot s^e \bmod n[/math] und sendet [math]y[/math] an Victor.
  4. Victor überprüft, ob [math]y^2 \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 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.
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.

  1. Runde
    • [math]e_1 = 0[/math]
    • Peggy überträgt: [math]y_1 \equiv r \, \bmod n[/math]
  2. 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.
[math]s \equiv y_2 \cdot r^{-1} \equiv y_2 \cdot y_1^{-1} \bmod n[/math]

Quellen


Kategorien: Identifikationsprotokoll

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Fiat-Shamir-Protokoll (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.