Zero knowledge example
Fiat-Shamir proof of identity

1.

A trusted center chooses n=pq, and publishes n but keeps p and q secret.

2.

Each prover A chooses a secret s with gcd(s,n)=1, and publishes v=s² mod n.

3.

A proves knowledge of s to B by repeating:

(a)

A chooses random r and sends r² mod n to B.

(b)

B chooses random e in {0,1}, and sends it to A.

(c)

A responds with a=rs^e mod n.

(d)

B checks if a² = v^e r² mod n.

1.

if A follows the protocol and knows s, then B's check will always work

2.

if A does not know s, then they can only answer the question with probability 1/2.