Digital signature

A signature scheme is a triple of algorithms: KeyGen produces (sk, pk), Sign(sk, m) produces σ, and Verify(pk, m, σ) returns accept or reject. The security goal is existential unforgeability under chosen-message attack (EUF-CMA): even after obtaining signatures on messages of their choice, an attacker cannot produce a valid signature on any new message. In practice the message is first hashed (hash-then-sign), so the scheme is only as strong as the collision resistance of the hash; the Flame malware (2012) used an MD5 chosen-prefix collision to forge a Microsoft code-signing certificate.

The popular description of a signature as "encrypting the hash with the private key" is only loosely true for textbook RSA and wrong for everything else. Real RSA signatures require padding: PKCS#1 v1.5 or the provably secure RSA-PSS (RFC 8017), and lax parsing of v1.5 padding enabled Bleichenbacher's 2006 low-exponent forgery. ECDSA and EdDSA are not encryption at all. FIPS 186-5 (February 2023) approves RSA, ECDSA and EdDSA (Ed25519, Ed448) and withdraws DSA for generating new signatures. ECDSA needs a fresh, secret, uniformly random nonce per signature; reusing it, as Sony's PS3 firmware signing did in 2010, reveals the private key with simple algebra, and even a few biased bits allow lattice attacks. RFC 6979 deterministic nonces and EdDSA's hash-derived nonces remove that dependency on the RNG.

Shor's algorithm breaks RSA and elliptic-curve signatures on a large quantum computer, so NIST published FIPS 204 (ML-DSA, lattice-based) and FIPS 205 (SLH-DSA, stateless hash-based) in August 2024; stateful hash-based schemes LMS and XMSS (NIST SP 800-208) are already used for firmware signing. Post-quantum signatures are much larger (an ML-DSA-65 signature is about 3.3 KB versus 64 bytes for Ed25519), which affects certificate chains and TLS handshakes.

Operationally, a signature proves only that someone with access to the private key signed the bytes, so the guarantees rest on key protection (HSMs, smart cards) and on binding the public key to an identity through a certificate. Long-term validity needs a trusted timestamp (RFC 3161) proving the signature existed before the certificate expired or was revoked. Code signing (Authenticode, Apple notarisation, Sigstore for open-source artefacts) and document signing (PAdES, XAdES) build on this. Legally, eIDAS (Regulation (EU) No 910/2014) distinguishes electronic, advanced (Art. 26) and qualified electronic signatures, and Art. 25(2) gives a qualified electronic signature the equivalent legal effect of a handwritten one. A digital signature differs from a MAC such as HMAC, which uses a shared symmetric key and therefore provides integrity and authentication between the parties but no non-repudiation towards third parties.