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
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Geheimer Schlüssel | die Zahl x, die nur der Beweiser kennt | |
| Öffentlicher Schlüssel | y, also G hoch x, modulo P | |
| Nonce | eine Zufallszahl für genau einen Beweis | k |
| Antwort | was der Beweiser auf die Challenge zurückgibt | s = k + c * x mod Q |
| Simulator | ein 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.
- Commit: Der Beweiser wählt ein zufälliges k und sendet t = G hoch k.
- Challenge: Der Prüfer sendet ein zufälliges c.
- 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
docker exec jupyter python3 steps/schnorr.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.
Beispiel: was das Lab gedruckt hat
| Schritt | Wer | Wert |
|---|---|---|
| Geheimnis und öffentlicher Schlüssel | Beweiser | x = 65, y = 227 |
| Commit | Beweiser sendet | t = 504 |
| Challenge | Prüfer sendet | c = 77 |
| Antwort | Beweiser sendet | s = 38 |
| Prüfung | Prüfer | True |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Probieren Sie es: ein Beweis mit Geheimnis 11
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
docker exec jupyter python3 steps/simulate.pyHier 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
docker exec jupyter python3 steps/bruteforce.pyHier angezeigt, nicht ausgeführt. Mit „Lab starten“ geben Sie ihn im Terminal Ihres eigenen Labs ein.