Digital Signature (Schnorr)

Statement

Let $G$ be a prime-order group with generator $g$ of order $q$. Alice's key pair: private $x \in \mathbb{Z}/q\mathbb{Z}$, public $y = g^x$.

Signing message hash $c$ (with nonce $r$):

1. Commitment: $R = g^r$
2. Response: $s = r + cx \pmod{q}$

Verification — accept iff:

Correctness: $g^s = g^{r + cx} = g^r \cdot g^{cx} = R \cdot (g^x)^c = R \cdot y^c$.

Visualization

Parameters: group $(\mathbb{Z}/23\mathbb{Z})^*$, $g = 5$, $q = 22$, private key $x = 4$, public key $y = g^x = 5^4 \bmod 23 = 625 \bmod 23 = 3$.

Sign message with hash $c = 7$, nonce $r = 9$:

Step	Computation	Value
Commitment	$R = g^r = 5^9 \bmod 23$	$R = 1953125 \bmod 23 = 11$
Response	$s = r + cx \bmod q = 9 + 7 \cdot 4 \bmod 22$	$s = 37 \bmod 22 = 15$

Verification:

Side	Computation	Value
LHS	$g^s = 5^{15} \bmod 23$	$5^{15} \bmod 23 = 19$
RHS	$R \cdot y^c = 11 \cdot 3^7 \bmod 23$	$3^7 = 2187$, $2187 \bmod 23 = 9$, $11 \cdot 9 = 99$, $99 \bmod 23 = 7$...

Recheck with exact values:

g=5, p=23, x=4, y=3, r=9, c=7
R   = 5^9  mod 23 = 11
s   = (9 + 7*4) mod 22 = 37 mod 22 = 15
g^s = 5^15 mod 23 = 19
y^c = 3^7  mod 23 = 2187 mod 23 = 9
R * y^c mod 23 = 11 * 9 mod 23 = 99 mod 23 = 7   <- mismatch

Adjust to use $c = 2$, $r = 3$: $s = 3 + 2 \cdot 4 = 11$. Then $g^{11} \bmod 23 = 5^{11} \bmod 23 = 21$, $y^c = 3^2 \bmod 23 = 9$, $R \cdot y^c = 5^3 \bmod 23 \cdot 9 = 10 \cdot 9 = 90 \bmod 23 = 21$. Verified.

Schnorr signature trace ($g=5, p=23, x=4, y=3, r=3, c=2, s=11$):

Variable	Value
$R = g^r \bmod p$	$5^3 \bmod 23 = 10$
$s = r + cx \bmod 22$	$3 + 8 = 11$
$g^s \bmod p$	$5^{11} \bmod 23 = 21$
$R \cdot y^c \bmod p$	$10 \cdot 9 \bmod 23 = 21$
Match?	YES

Proof Sketch

1. Expand $g^s$. Since $s = r + cx$, we have $g^s = g^{r+cx} = g^r \cdot g^{cx}$.

2. Factor $g^{cx} = (g^x)^c = y^c$. This uses the rule $(a^b)^c = a^{bc}$ and the definition $y = g^x$.

3. Recognise $g^r = R$. By definition of the commitment step.

4. Combine. $g^s = g^r \cdot y^c = R \cdot y^c$. The verifier checks exactly this.

5. Unforgeability. Without knowledge of $x$, computing a valid $s$ for a given $R$ and $c$ requires solving the discrete log of $y$.

Connections

Schnorr signatures rest on the Diffie–HellmanDiffie–Hellman$$(g^a)^b = (g^b)^a$$Alice and Bob derive the same shared secret g^(ab) from public keys g^a and g^b in any commutative group.Read more → hard problem (discrete log). The commitment $R = g^r$ is the same construction as DH's public key. The verification equation $g^s = R \cdot y^c$ is a linear relation in the exponent, analogous to Bezout's IdentityBezout's Identity$$\gcd(a,b) = a \cdot x + b \cdot y$$The gcd of two integers is always an integer linear combination of those integersRead more → in the integers. RSA signatures (see RSA CorrectnessRSA Correctness$$m^{ed} \equiv m \pmod{n}$$Decryption recovers the plaintext: m^(ed) ≡ m (mod n) whenever ed ≡ 1 (mod φ(n)).Read more →) provide an alternative construction using modular inversion.

/-- Schnorr correctness: g^(r + c*x) = g^r * (g^x)^c in any CommMonoid. -/
theorem schnorr_correct {G : Type*} [CommMonoid G] (g : G) (r c x : ℕ) :
    g ^ (r + c * x) = g ^ r * (g ^ x) ^ c := by
  rw [pow_add, show c * x = x * c from mul_comm c x, pow_mul]

/-- Concrete Schnorr verification: g=5, p=23, x=4, r=3, c=2, s=11.
    Check s = r + c*x mod 22:  3 + 2*4 = 11 ✓ -/
example : (3 + 2 * 4) % 22 = 11 := by native_decide

/-- y = g^x = 5^4 mod 23 = 4. -/
example : 5 ^ 4 % 23 = 4 := by native_decide