= Solution
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\bmod p$. To sign a message whose hash is represented by $m\bmod(p-1)$, choose a fresh secret nonce $k$ coprime to $p-1$ and set
$$
\boxed{r=g^k\bmod p,\qquad s=k^{-1}(m-xr)\bmod(p-1).}
$$
Transmit $(r,s)$ with the message. Verification checks the permitted ranges and $\boxed{g^m\equiv y^r r^s\pmod p}$. Correctness follows from $xr+ks\equiv m\pmod{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.
Back to article page
