Lässt es sich mit cremefarbenem Papier, einer Tönung, mehr Kontrast oder größerer Schrift besser lesen? Wählen Sie Ihre Farben und Ihre Schrift, einmalig für alle Seiten.

Kostenlose Lektion

Fiat-Shamir: ein Beweis, den alle prüfen

Nach dieser Lektion: Ich kann eine Fiat-Shamir-Challenge berechnen und einen nicht interaktiven Beweis prüfen.

Lektion, 60 Min.2 BefehleZero-Knowledge-Lab: Commitments, Schnorr, Fiat-Shamir und Merkle-Beweise in Python

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

BegriffWas er bedeutet
Interaktivmit Nachrichten hin und her
Nicht interaktiveine einzige Nachricht, die alle prüfen können
Fiat-Shamirdie Challenge durch einen Hash ersetzen
Protokollalles, was während eines Beweises gesendet wurde
Fälschungein 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

Befehl
docker exec jupyter python3 steps/fiatshamir.py

Hier 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 SchnorrSchnorr mit Fiat-Shamir
Wer wählt cDer Prüfer, zufälligEin Hash aus y, t und der Nachricht
NachrichtenDrei, hin und herEine, t und s zusammen
Wer prüfen kannNur der Prüfer, der c gewählt hatAlle, jederzeit
Wen es überzeugtEinen PrüferAlle, die prüfen

Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.

Probieren Sie es: Fälschung gegen einen schwachen Hash

Code: python
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

Befehl
docker exec jupyter grep -n def zk.py

Hier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.

Über dieses Lab und seinen Quellcode: Zero-Knowledge-Lab: Commitments, Schnorr, Fiat-Shamir und Merkle-Beweise in Python

Sie unterrichten eine Gruppe? Weisen Sie dieses Modul Ihren Studierenden zu, mit Handbuch für Lehrende, automatisch geprüften Aufgaben und einem Lab für jede Person.