Ein Beweis ohne Gespräch
Die Fiat-Shamir-Transformation macht aus einem interaktiven Beweis einen nicht interaktiven. Der Beweiser erstellt den ganzen Beweis allein, und alle können ihn später prüfen. Ein Hash übernimmt die Rolle des Prüfers.
So wird aus Schnorr eine Signatur. Und so werden die meisten Zero-Knowledge-Beweise heute veröffentlicht und geprüft.
Am Ende dieser Lektion
Notiz
Ich kann eine Fiat-Shamir-Challenge berechnen und einen nicht interaktiven Beweis prüfen.
Schlüsselwörter
| Begriff | Was er bedeutet |
|---|---|
| Interaktiv | mit Nachrichten hin und her |
| Nicht interaktiv | eine einzige Nachricht, die alle prüfen können |
| Fiat-Shamir | die Challenge durch einen Hash ersetzen |
| Protokoll | alles, was während eines Beweises gesendet wurde |
| Fälschung | ein Beweis, der ohne das Geheimnis besteht |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Hash kann die Challenge wählen
Interaktives Schnorr braucht einen Prüfer, der live dabei ist. Das passt schlecht zu einem Beweis, den später viele prüfen.
Fiat-Shamir setzt c auf den Hash aus öffentlichem Schlüssel, t und einer Nachricht, modulo Q. Der Beweiser kann c nicht wählen, denn c hängt von t ab, und einen Hash kann man nicht steuern. Er muss sich also weiterhin zuerst auf t festlegen. Alle können dasselbe c nachrechnen.
Einen nicht interaktiven Beweis erstellen und prüfen
docker exec jupyter python3 steps/fiatshamir.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.
Lesen Sie, was das Lab gedruckt hat
Der Beweis besteht aus zwei Zahlen, t = 718 und s = 501. Die Challenge, aus dem Hash berechnet, ergab 14. Der Beweis besteht mit True.
Dieselben zwei Zahlen mit einer anderen Nachricht ergeben False. Die Nachricht steckt im Hash und führt zu einer anderen Challenge. Ein Schnorr-Beweis, der an eine Nachricht gebunden ist, ist eine Signatur auf ihr.
Beispiel: interaktiv und nicht interaktiv
| Interaktives Schnorr | Schnorr mit Fiat-Shamir | |
|---|---|---|
| Wer wählt c | Der Prüfer, zufällig | Ein Hash aus y, t und der Nachricht |
| Nachrichten | Drei, hin und her | Eine, t und s zusammen |
| Wer prüfen kann | Nur der Prüfer, der c gewählt hat | Alle, jederzeit |
| Wen es überzeugt | Einen Prüfer | Alle, die prüfen |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Probieren Sie es: Fälschung gegen einen schwachen Hash
import hashlib
P = 1019
Q = 509
G = 4
y = 227 # der öffentliche Schlüssel einer Person: ihr Geheimnis kennen wir nicht
def schwache_challenge(nachricht):
# Absichtlich falsch: t fehlt im Hash.
return int(hashlib.sha256(nachricht.encode()).hexdigest(), 16) % Q
nachricht = "Pat schuldet Kim 5"
c = schwache_challenge(nachricht)
s = 123
t = pow(G, s, P) * pow(pow(y, c, P), -1, P) % P
print("c =", c, "gefälschtes t =", t, "s =", s)
print("Prüfung besteht:", pow(G, s, P) == t * pow(y, c, P) % P)
# Reparieren: str(t) + nachricht hashen, dann muss t vor c feststehen.
Alles hashen, was der Prüfer sehen würde
Der Code oben ließ t im Hash weg. Also berechnete der Fälscher zuerst c, wählte irgendein s und baute ein passendes t, genau wie der Simulator. Die Prüfung bestand ganz ohne Geheimnis.
Die Regel lautet: Hashen Sie jeden Wert, den der Prüfer vor seiner Wahl gesehen hätte. Das sind die Gruppe, der öffentliche Schlüssel, t und die Nachricht. Echte Systeme wurden mit diesem Fehler ausgeliefert, ein prüfender Blick lohnt sich also.
Ein häufiger Fehler
Warnung
Viele glauben, jeder Hash mache Fiat-Shamir sicher. Sicher ist es nur, wenn der Hash t und die Aussage umfasst. Fehlt t, wählt ein Fälscher zuerst die Challenge und fälscht den Beweis, so wie der Simulator.
Die Funktionen in zk.py auflisten
docker exec jupyter grep -n def zk.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.