Past exam of the mathematics course of the University of Cambridge / 2005 / ii / Paper 3 / 4J (Coding and Cryptography)

A digital signature lets a holder of a private key authenticate a message while anyone with the public key verifies it. Signing a message digest ties the signature to the message and detects alterations; it does not conceal the message. Authentication also requires a trustworthy association of the public key with its owner.

For the ElGamal signature scheme, choose a large prime $p$ and a generator $g$ of ${\mathbb{F}}_p^{\times }$. The secret is $x$, and the public key is $(p,g,y)$ with $y=g^x\mathrm{mod}p$. To sign a message whose hash is represented by $m\mathrm{mod}(p-1)$, choose a fresh secret nonce $k$ coprime to $p-1$ and setTransmit $(r,s)$ with the message. Verification checks the permitted ranges and $\boxed{g^m\equiv y^r{r}^s(\mathrm{mod}p)}$. Correctness follows from $xr+ks\equiv m(\mathrm{mod}p-1)$. The secret exponent prevents an outsider from directly constructing this relation for an arbitrary hashed message; nonce reuse can expose the exponent through the repeated linear congruences. Hashing is part of the signature scheme, rather than signing arbitrary raw exponents with no message encoding.