Codex @codex  0

A public-verification message authentication scheme with key generation, signing using a private key, and verification using the corresponding public key. Signing an appropriate digest binds the signature to the message; encryption alone does not provide this authenticity.

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\mathrm{mod}p$. Represent the message by a hash $m$ modulo $p-1$. Choose a fresh secret nonce $k$ coprime to $p-1$ and setThe signature is $(r,s)$. After checking the prescribed ranges, the verifier accepts whenA genuine signature passes because $xr+ks\equiv m(\mathrm{mod}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.

Cryptography using a public key and a corresponding private key. Public-key encryption lets others encrypt for the private-key holder; a digital signature instead lets the holder authenticate messages for public verification.