A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A digital signature scheme lets a signer with a private key produce a signature on a message that anyone with the corresponding public key can verify. Unlike MACs, signatures provide non-repudiation: the signer cannot deny having signed because only they possess the private key. Security requires existential unforgeability under chosen-message attack (EUF-CMA). RSA-PSS, DSA, and ECDSA are the main schemes. Signatures are applied to message hashes (not raw messages) for efficiency and to prevent algebraic attacks. They are foundational to PKI, code signing, certificates, and blockchain transactions.
A digital signature is the public-key analog of a handwritten signature: it binds a message to the identity of the signer in a way that anyone can verify but only the signer can produce. A signature scheme consists of three algorithms: key generation (produce a public-private key pair), signing (use the private key to compute a signature on a message), and verification (use the public key to check whether a signature is valid). The security goal is EUF-CMA (existential unforgeability under chosen-message attack): an adversary who can obtain signatures on any messages of their choosing still cannot forge a valid signature on any new message.
The simplest conceptual scheme is RSA signatures. The signer computes s = H(m)d mod n, where d is the private key and H is a cryptographic hash. The verifier checks that se mod n = H(m), where e is the public key. Hashing is essential for two reasons: it compresses the message to a fixed size for the RSA operation, and it prevents algebraic forgery attacks that exploit RSA's multiplicative homomorphism. In practice, RSA-PSS adds randomized padding to the hash before signing, providing a tighter security proof. DSA and ECDSA use a different approach based on discrete logarithms in a prime-order group (or elliptic curve group), where the signature is a pair (r, s) computed using the private key and a per-signature random nonce.
The nonce in DSA/ECDSA is a critical security parameter. If the same nonce is ever reused for two different messages, the private key can be algebraically recovered from the two signatures. This is not a theoretical curiosity — Sony's PlayStation 3 ECDSA implementation used a constant nonce, allowing hackers to recover the signing key and run unauthorized software. Deterministic signatures (Ed25519, or ECDSA with RFC 6979) eliminate nonce-related risks by deriving the nonce deterministically from the private key and the message, ensuring it is unique per message without relying on a random number generator.
The most transformative application of digital signatures is Public Key Infrastructure (PKI), the trust system underlying HTTPS. A certificate authority (CA) signs a binding between a domain name and a public key, producing a certificate. When your browser connects to a website, it verifies the certificate's signature using the CA's public key (which is pre-installed in the browser's trust store). If the signature checks out, the browser trusts that the public key belongs to the claimed domain and proceeds with a DH key exchange. This chain of trust — from CA to certificate to session key — is what makes secure web browsing possible. It also creates a concentration of trust: a compromised CA can forge certificates for any domain, which is why the security of CAs is one of the most critical (and fragile) aspects of internet infrastructure.