= Solution
A <digital signature> lets the holder of a <private key> authenticate a message so that anyone with the corresponding trusted <public key> can verify its origin and integrity. The signature does not conceal the message. Public-key certification, a suitable message hash and protection of the signing key are needed for that interpretation.
For the <ElGamal signature scheme>, choose a large prime $p$ and a <primitive root> $g$ modulo $p$. The secret key is $x$, and the <public key> is $(p,g,y)$ with $y=g^x\bmod p$. Represent the message by a hash $m$ modulo $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).}
$$
The signature is $(r,s)$. After checking the prescribed ranges, the verifier accepts when
$$
\boxed{g^m\equiv y^r r^s\pmod p.}
$$
A genuine signature passes because $xr+ks\equiv m\pmod{p-1}$. The security aim is that someone without $x$ cannot efficiently produce a valid signature on a new authenticated message. Nonce secrecy and freshness matter: reuse gives linear congruences relating two message hashes, the nonce and the secret key. Signing unhashed arbitrary messages also permits algebraic forgeries, so the hash is part of the practical scheme.
Back to article page
