Easier to read with cream paper, a tint, more contrast or larger text? Choose your colours and text, once, for every page.

Free lesson

The Schnorr protocol: proving you know a key

After this lesson: I can run and verify the Schnorr protocol with small numbers.

65 min lesson3 commandsZero-knowledge proofs lab: commitments, Schnorr, Fiat-Shamir and Merkle proofs in Python

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

WordWhat it meansExample
Secret keythe number x that only the prover knows
Public keyy, which is G to the power x, mod P
Noncea random number used for one proof onlyk
Responsethe prover's answer to the challenges = k + c * x mod Q
Simulatora 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.

  1. Commit: the prover picks a random k and sends t = G to the k.
  2. Challenge: the verifier sends a random c.
  3. 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

Command
docker exec jupyter python3 steps/schnorr.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

Worked example: what the lab printed

StepWhoValue
Secret and public keyProverx = 65, y = 227
CommitProver sendst = 504
ChallengeVerifier sendsc = 77
ResponseProver sendss = 38
CheckVerifierTrue

The cells students fill in are left blank in this preview.

Try it: a proof with secret 11

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

Command
docker exec jupyter python3 steps/simulate.py

Shown 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

Command
docker exec jupyter python3 steps/bruteforce.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

About this lab and its source: Zero-knowledge proofs lab: commitments, Schnorr, Fiat-Shamir and Merkle proofs in Python

Teaching a class? Set this module for your students with a teacher guide, marked assignments and a lab for every student.