Digital Signatures

A digital signature uses a private key to produce a value that anyone holding the corresponding public key can verify, providing authenticity, integrity, and non-repudiation for a message.

Definition

A digital signature scheme is a public-key primitive consisting of algorithms to generate a key pair, sign a message with the private key, and verify a signature with the public key, such that only the holder of the private key can produce signatures that verify.

Scope

This topic covers digital-signature schemes — RSA-PSS, DSA, ECDSA, and EdDSA — the security goal of existential unforgeability under adaptive chosen-message attack, the hash-then-sign paradigm, and the role of signatures in certificates and software distribution. It addresses the distinction from message authentication codes (public verifiability and non-repudiation). It excludes the public-key encryption and key-exchange schemes that share the same underlying assumptions, and the certificate infrastructure that distributes verification keys.

Core questions

• How does a private key let only its holder produce a verifiable, unforgeable signature?
• What does existential unforgeability under adaptive chosen-message attack guarantee?
• Why are messages hashed before signing rather than signed directly?
• How do signatures provide non-repudiation that symmetric MACs cannot?
• How are signatures used to anchor trust in certificates and software updates?

Key concepts

• key pair (signing and verification keys)
• existential unforgeability
• adaptive chosen-message attack
• hash-then-sign
• RSA-PSS
• DSA and ECDSA
• EdDSA
• non-repudiation
• certificate signing

Key theories

Existential unforgeability under chosen-message attack

The gold-standard security definition for signatures: even an adversary who obtains signatures on many messages of its choosing cannot forge a valid signature on any new message; the GMR scheme first achieved this provably.

Hash-then-sign and non-repudiation

Practical schemes sign a cryptographic hash of the message, enabling signing of arbitrary-length data and binding the signature to the content; because only the private-key holder can sign, signatures provide non-repudiation, which a shared-key MAC cannot.

Mechanisms

To sign, the holder applies a private-key operation to a hash of the message: RSA-PSS exponentiates the padded hash with the private exponent, while (EC)DSA and EdDSA combine the hash with a per-message nonce and the private scalar to produce two values. Verification recomputes the hash and applies the public-key operation, accepting only if the relation holds. Security reduces to the underlying hardness assumption and the collision resistance of the hash.

Clinical relevance

Digital signatures are the trust anchor of the internet: certificate authorities sign TLS certificates, operating-system vendors sign software updates and drivers, app stores sign applications, and document platforms provide legally recognized e-signatures. Cryptocurrencies authorize every transaction with a signature, and code-signing prevents tampered software from being trusted.

Evidence & guidelines

Signature schemes are standardized in FIPS 186 (DSA, ECDSA), RFC 8032 (EdDSA), and PKCS #1 / RFC 8017 (RSA-PSS). Legal frameworks (the EU eIDAS regulation, the U.S. ESIGN Act) give qualified digital signatures legal weight. Best practice favors deterministic or hedged nonces (as in EdDSA and RFC 6979) to avoid the catastrophic key leakage that nonce reuse causes in ECDSA.

History

The digital-signature concept was introduced alongside public-key cryptography by Diffie and Hellman (1976) and first realized by RSA (1978). Goldwasser, Micali, and Rivest gave the first scheme provably secure against adaptive chosen-message attacks in 1988, establishing the modern security definition. DSA was standardized in the 1990s, with elliptic-curve ECDSA and later the misuse-resistant EdDSA becoming dominant.

Key figures

• Shafi Goldwasser
• Silvio Micali
• Ronald Rivest
• Whitfield Diffie
• Martin Hellman

Seminal works

• goldwasser1988
• rivest1978
• katz2020

Frequently asked questions

How is a digital signature different from a scanned handwritten signature?

A scanned image is just a picture and can be copied onto any document. A cryptographic digital signature is computed from the message content and a private key, so it is unique to both the signer and that exact document and is invalidated by any change to the content.

Why do signatures provide non-repudiation but MACs do not?

A MAC uses a shared secret, so either party could have produced a valid tag — neither can prove the other made it. A digital signature can only be created with the private key, which the verifier does not possess, so the signer cannot credibly deny having signed.