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

Das Schnorr-Protokoll: einen Schlüssel beweisen

Nach dieser Lektion: Ich kann das Schnorr-Protokoll mit kleinen Zahlen ausführen und prüfen.

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

Anmelden, ohne den Schlüssel zu senden

Das Schnorr-Protokoll ist ein Zero-Knowledge-Beweis dafür, dass Sie die geheime Zahl hinter einem öffentlichen Schlüssel kennen. Der Beweis braucht drei kurze Nachrichten, und das Geheimnis verlässt Ihr Gerät nie.

Auf ihm beruhen Schnorr-Signaturen, die heute in echten Systemen laufen.

Am Ende dieser Lektion

Notiz

Ich kann das Schnorr-Protokoll mit kleinen Zahlen ausführen und prüfen.

Schlüsselwörter

BegriffWas er bedeutetBeispiel
Geheimer Schlüsseldie Zahl x, die nur der Beweiser kennt
Öffentlicher Schlüssely, also G hoch x, modulo P
Nonceeine Zufallszahl für genau einen Beweisk
Antwortwas der Beweiser auf die Challenge zurückgibts = k + c * x mod Q
Simulatorein Programm, das ein Protokoll ohne das Geheimnis fälscht

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

Schnorr braucht drei Züge

Der Beweiser kennt x, und alle kennen y = G hoch x, modulo P.

  1. Commit: Der Beweiser wählt ein zufälliges k und sendet t = G hoch k.
  2. Challenge: Der Prüfer sendet ein zufälliges c.
  3. Antwort: Der Beweiser sendet s = k + c mal x, modulo Q.

Der Prüfer kontrolliert, ob G hoch s gleich t mal y hoch c ist, modulo P. Beide Seiten ergeben G hoch k + c x.

Einen Schnorr-Beweis ausführen

Befehl
docker exec jupyter python3 steps/schnorr.py

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

Beispiel: was das Lab gedruckt hat

SchrittWerWert
Geheimnis und öffentlicher SchlüsselBeweiserx = 65, y = 227
CommitBeweiser sendett = 504
ChallengePrüfer sendetc = 77
AntwortBeweiser sendets = 38
PrüfungPrüferTrue

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

Probieren Sie es: ein Beweis mit Geheimnis 11

Code: python
P = 1019
Q = 509
G = 4

x = 11              # das Geheimnis
y = pow(G, x, P)    # der öffentliche Schlüssel
print("öffentlicher Schlüssel y =", y)

k = 30              # die Zufallszahl des Beweisers, nur einmal benutzt
t = pow(G, k, P)
c = 5               # die Challenge des Prüfers
s = (k + c * x) % Q
print("t =", t, "c =", c, "s =", s)

links = pow(G, s, P)
rechts = t * pow(y, c, P) % P
print("G ** s =", links, "und t * y ** c =", rechts)
# Setzen Sie s + 1 statt s ein. Besteht die Prüfung noch?

Warum die Challenge zuletzt kommen muss

Angenommen, der Beweiser kennt c, bevor er t sendet. Dann wählt er irgendein s und setzt t = G hoch s geteilt durch y hoch c. Die Prüfung besteht, und x braucht er nie.

Genau das tut ein Simulator. Der Simulator im Lab wählte zuerst c = 77 und s = 300, berechnete t = 880, und die Prüfung bestand. Ein Protokoll beweist also nur dem etwas, der die Challenge selbst gewählt hat. Deshalb verrät es nichts.

Ein Protokoll ohne Geheimnis fälschen

Befehl
docker exec jupyter python3 steps/simulate.py

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

Eine doppelt benutzte Nonce verrät das Geheimnis

Danach beantwortete das Lab eine zweite Challenge mit demselben k. Zwei Antworten s und s2 auf zwei Challenges c und c2 ergeben x = (s minus s2) geteilt durch (c minus c2), modulo Q. Das Lab druckte 65.

Das ist kein reines Spielzeugproblem. Echte Signatursysteme haben Schlüssel verloren, weil sich eine Zufallszahl wiederholte. Eine Nonce wird einmal benutzt und dann weggeworfen.

Ein häufiger Fehler

Warnung

Viele glauben, das zufällige k müsse nur zufällig aussehen. Es darf sich aber auch nie wiederholen. Beantwortet dasselbe k zwei verschiedene Challenges, berechnet jede Person mit beiden Protokollen den geheimen Schlüssel mit einer Division.

Das Spielzeuggeheimnis durch Ausprobieren finden

Befehl
docker exec jupyter python3 steps/bruteforce.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.