Signing in without sending your key
The Schnorr protocol is a zero-knowledge proof that you know the secret number behind a public key. You prove it in three short messages, and the secret never leaves your device.
It is the base of Schnorr signatures, used in real systems today.
By the end of this lesson
Note
I can run and verify the Schnorr protocol with small numbers.
Key words
| Word | What it means | Example |
|---|---|---|
| Secret key | the number x that only the prover knows | |
| Public key | y, which is G to the power x, mod P | |
| Nonce | a random number used for one proof only | k |
| Response | the prover's answer to the challenge | s = k + c * x mod Q |
| Simulator | a program that fakes a transcript without the secret |
The cells students fill in are left blank in this preview.
Schnorr takes three moves
The prover knows x, and everybody knows y = G to the x, mod P.
- Commit: the prover picks a random k and sends t = G to the k.
- Challenge: the verifier sends a random c.
- Response: the prover sends s = k + c times x, mod Q.
The verifier checks that G to the s equals t times y to the c, mod P. Both sides come to G to the power k + c x.
Run one Schnorr proof
docker exec jupyter python3 steps/schnorr.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.
Worked example: what the lab printed
| Step | Who | Value |
|---|---|---|
| Secret and public key | Prover | x = 65, y = 227 |
| Commit | Prover sends | t = 504 |
| Challenge | Verifier sends | c = 77 |
| Response | Prover sends | s = 38 |
| Check | Verifier | True |
The cells students fill in are left blank in this preview.
Try it: a proof with secret 11
P = 1019
Q = 509
G = 4
x = 11 # the secret
y = pow(G, x, P) # the public key
print("public key y =", y)
k = 30 # the prover's random number, used once
t = pow(G, k, P)
c = 5 # the verifier's challenge
s = (k + c * x) % Q
print("t =", t, "c =", c, "s =", s)
left = pow(G, s, P)
right = t * pow(y, c, P) % P
print("G ** s =", left, "and t * y ** c =", right)
# Change s to s + 1 and run again. Does the check still pass?
Why the challenge must come last
Suppose the prover knew c before sending t. They could pick any s and set t = G to the s divided by y to the c. The check would pass, and they never needed x.
That is exactly what a simulator does. The lab's simulator picked c = 77 and s = 300 first, made t = 880, and the check passed. So a transcript proves nothing to anybody who did not choose the challenge, which is why it gives nothing away.
Fake a transcript without the secret
docker exec jupyter python3 steps/simulate.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.
A nonce used twice gives the secret away
The lab then answered a second challenge with the same k. Two answers, s and s2, for two challenges, c and c2, give x = (s minus s2) divided by (c minus c2), mod Q. It printed 65.
This is not only a toy problem. Real signing systems have leaked keys because a random number repeated. A nonce is used once and thrown away.
A common mistake
Warning
Many people think the random k only needs to look random. It must also never repeat. If the same k answers two different challenges, anybody holding both transcripts can work out the secret key with one division.
Find the toy secret by trying every number
docker exec jupyter python3 steps/bruteforce.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.