Schnorr signatures

How it works

Schnorr signatures work in a subgroup of prime order $q$ of $\mathbb{Z}_p^*$, generated by $g$. The private key is $x$ and the public key $y = g^x \bmod p$. To sign a message $m$, pick a secret nonce $k$, compute the commitment $r = g^k$, the challenge $e = H(r \| m) \bmod q$ and the response $s = k - xe \bmod q$. The signature is $(e, s)$. The verifier recomputes $r_v = g^s y^e$, which equals $g^{k - xe} g^{xe} = g^k = r$ for a genuine signature, and checks that $H(r_v \| m) = e$.

This is the Fiat-Shamir transform of Schnorr’s identification protocol: the hash plays the role of the verifier’s random challenge. In the random oracle model the scheme is unforgeable if discrete logarithms in the group are hard. Here the hash input is $r$ as a fixed number of bytes followed by the UTF-8 bytes of the message; the toy hash simply reads those bytes as a number modulo $q$, which is easy to recompute by hand but offers no security.

The nonce is critical: reusing $k$ for two messages reveals $x = (s_1 - s_2)(e_2 - e_1)^{-1} \bmod q$, and even a slightly biased nonce can leak the key through lattice attacks. EdDSA (Ed25519), the elliptic curve form of Schnorr signatures, therefore derives $k$ deterministically from the key and the message.