SIGMA Protocol — Zero-Knowledge Proof Challenge

Challenge

Prove knowledge of secret w in y = g^w mod p without revealing w itself. This is a classic Schnorr zero-knowledge proof (SIGMA protocol).

p = 25831195985826749773988131568...94930322927
q = 12915597992913374886994065784...65161463
g = 2
w = 4716768581834028438509101691...82648696451

Protocol Steps

• Commitment: Generate random r ∈ [1, q-1], compute a = g^r mod p, send to verifier
• Challenge: Server responds with random challenge value e
• Response: Compute z = (r + e·w) mod q, send to verifier
• Verification: Server checks pow(g, z, p) == a * pow(y, e, p) % p

Mathematical Proof

The verification equation holds because:

g^z mod p = g^(r + e·w) mod p
           = g^r · g^(e·w) mod p
           = g^r · (g^w)^e mod p
           = a · y^e mod p   ✓

Security properties: Completeness (prover always succeeds), Soundness (cheater cannot forge), Zero-Knowledge (verifier learns nothing except that prover knows w).

Implementation

import os

r = int.from_bytes(os.urandom(256), byteorder='big') % (q - 1) + 1
a = pow(g, r, p)  # → Submit to server

# Server returns challenge e

z = (r + (e * w) % q) % q  # → Submit response

# Submit verification equation:
# pow(g, z, p) == a * pow(y, e, p) % p

Flag