Proving you know a secret key

The Schnorr identification protocol

How can you convince someone that you know a password without saying it? That is exactly what the Schnorr identification protocol, published in 1989, solves.

The mathematical setting

We work in a group where the discrete logarithm is hard: we are given a generator g and a large prime order. Everyone holds a key pair:

a private key x, a secret number;
a public key y = g^x, distributed freely.

Computing y from x is easy. Doing the reverse — recovering x from y — is the discrete logarithm problem, out of reach for large parameters. It is the same asymmetry that protects RSA, but founded on a different hard problem.

The prover (let's call him Peter) wants to convince the verifier (Valerie) that he knows the x corresponding to y, without revealing x.

The three exchanges

The protocol fits in three messages, a pattern called commitment – challenge – response.

   Pierre (connaît x)                Valérie (connaît y)
   ------------------                -------------------
1. choisit un aléa r
   calcule t = g^r
                        --- t --->        (engagement)

2.                                     choisit un défi
                                       aléatoire c
                        <--- c ---
3. calcule s = r + c*x
                        --- s --->
                                       vérifie que
                                       g^s = t * y^c ?

Let's detail each step:

Commitment. Peter draws a random number r (a nonce), computes t = g^r and sends t. He commits to r without disclosing it.
Challenge. Valerie draws a random number c and sends it. She still knows nothing.
Response. Peter computes s = r + c*x and sends it.

The verification

Valerie accepts if and only if:

g^s = t * y^c

Let's check that the equality holds when Peter is honest. We replace s by r + c*x:

g^s = g^(r + c*x) = g^r * g^(c*x) = g^r * (g^x)^c = t * y^c

The equality is indeed satisfied. Peter never sent x. He sent only t (which masks r) and s (which mixes r and x). The secret key stays invisible.

Why a cheater fails

Imagine Marc, who does not know x. He can send any t, but he will then have to produce an s such that g^s = t * y^c, for a c he does not yet know at the moment he chooses t. Without x, he is stuck: either he cheats on t by betting on a c, or he fails the verification. We will see in the next lesson why this trap is solid.

In summary