Digital signature

• 1. Introduction

  ›

  Digital signatures are a mathematical scheme for verifying the authenticity of digital messages or documents, and their story begins in 1976 with a thought experiment that most experts believed was impossible. Whitfield Diffie and Martin Hellman proposed the idea that you could verify the source of a message without ever sharing a secret password. They could not prove it would work, but they described what such a scheme would need to do. What followed was a decades-long effort to turn that conjecture into a technology trusted enough to govern software distributed to millions of computers, to validate laws published by the United States Government Printing Office, and to underpin the legal weight of contracts signed across dozens of countries. How does mathematics substitute for a handwritten mark? What makes a digital signature unforgeable when so much of what is digital can be copied and altered in seconds? And what happens when the system, despite its elegance, meets the imperfections of the real world?

• 2. From Conjecture to Algorithm

  ›

  Ronald Rivest, Adi Shamir, and Len Adleman answered the challenge Diffie and Hellman had posed when they invented the RSA algorithm shortly after 1976. RSA could produce what the field called primitive digital signatures, though those early implementations were described only as a proof of concept, because plain RSA signatures on their own are not secure enough for real use. The technology sat largely in research circles until 1989, when Lotus Notes 1.0 became the first widely marketed software package to offer digital signatures to ordinary users. It used RSA.

  Other schemes developed in parallel. Lamport signatures, Merkle signatures (known also as Merkle trees or hash trees), and Rabin signatures arrived in the wake of RSA. Then in 1988, Shafi Goldwasser, Silvio Micali, and Ronald Rivest produced something that went beyond any particular algorithm. They were the first to rigorously define what security actually meant for a digital signature scheme. Their paper described a hierarchy of attack models and presented the GMR signature scheme, the first that could be proved to prevent even an existential forgery against a chosen message attack. That standard of security remains the accepted definition today. A separate contribution came from Moni Naor and Moti Yung, who presented the first such scheme built not on trapdoor functions but on a family of functions requiring only the weaker property of one-way permutation.

• 3. How the Mathematics Works

  ›

  Every digital signature scheme rests on three distinct algorithms that must work together. A key generation algorithm selects a private key at random from a set of possible private keys and outputs both that private key and a corresponding public key. A signing algorithm takes a message and the private key and produces a signature. A verification algorithm takes the message, the public key, and the signature, then either accepts or rejects the message's claim to authenticity.

  The RSA-based version illustrates the underlying mechanics. A signer generates a key pair using a modulus N that is the product of two random secret large primes, together with integers e and d satisfying the relationship e times d is congruent to 1 modulo Euler's totient function of N. The public key is N and e; the secret key contains d. Used without further processing, this setup is vulnerable to forgery, so in practice the message is first hashed to produce a short digest, then padded, then signed using the reverse trapdoor function.

  Hashing serves three purposes. It makes signing faster, because hashing is generally much quicker than signing. It makes signatures compatible across different input types, since a hash function converts any input into the format the signing scheme requires. And it preserves the order and completeness of a message: without hashing, a message split into blocks could be received with blocks missing or rearranged, and the recipient would have no way to detect the problem. In the formal framework, the security requirement is called existential unforgeability under chosen-message attack, abbreviated EUF-CMA. It demands that generating a valid signature for a party is computationally infeasible without knowing that party's private key.

• 4. Where Signatures Are Used

  ›

  The United States Government Printing Office publishes electronic versions of the federal budget, public and private laws, and congressional bills using digital signatures, making every published document verifiable without a physical stamp or notary. Universities including Penn State, the University of Chicago, and Stanford publish electronic student transcripts with digital signatures, allowing graduates to share credentials that a recipient can independently verify.

  Software distribution is one of the most consequential applications. When a software author publishes a patch for all existing installations to apply, the patch itself is not secret. But every computer applying it must verify the patch's authenticity before installation, or risk installing malware instead. Digital signatures provide that verification at scale, invisibly, without requiring any human review.

  Financial institutions use them to solve a specific and longstanding forgery problem. If a bank's central office receives a letter from a branch office requesting a change to an account balance, the central bankers need to confirm the instruction actually came from the branch before acting on it. A digital signature scheme lets the central office keep a public key whose private counterpart is held only by the branch. A forger who does not know the branch's private key cannot sign a different message, and cannot alter even a single digit in an existing message without causing the verification check to fail. Encryption alone does not solve this: encrypted messages can still be selectively modified in transit without detection.

• 5. Limits and Attack Surfaces

  ›

  A replay attack exposes one of the clearest gaps in what a digital signature can guarantee on its own. A legitimate signed message, such as a branch office's request to issue a bank transfer, can be recorded by an adversary and submitted again and again. If the bank does not use transaction IDs to track which transfers have already been processed, the same signed message can drain an account without ever breaking the signature scheme itself. The signature remains valid; the attack exploits the absence of context around it.

  Malleability creates a related problem. In some signature schemes, a single message has a large number of possible valid signatures from the same signer, and it can be straightforward to transform one valid signature into another without knowing the private key. Bitcoin exchanges have been targeted through this vulnerability when signatures were misused as transaction identifiers.

  Public key authentication introduces a different class of risk. Knowing a signed message does not let you verify that a given public key is legitimate; the direction of trust runs only one way. In some schemes, given only a signed message, it is possible to construct a public key under which that message will pass verification, even without access to the private key used to sign it originally. This is why public key infrastructure (PKI) exists. A certificate authority attests that a public key actually belongs to a named party. Commercial PKI operators have suffered publicly known failures in making such attestations, and when they do, the result is falsely attributed documents.

  Non-repudiation adds yet another layer of complexity. A signer cannot later deny having signed information, which is the point. But this protection depends entirely on the private key remaining secret before and during use. If a key is stolen, the theft is often discovered only after the key has already been used, for instance to sign a bogus certificate for espionage purposes. Revocation is the remedy, but checking revocation status requires an online query against a certificate revocation list or the Online Certificate Status Protocol, much like a vendor checking with a card issuer to learn whether a credit card has been reported stolen.

• 6. Protecting the Private Key

  ›

  Storing a private key on a personal computer protected only by a local password creates two problems. The user can only sign documents on that one machine, and the security of the key is entirely dependent on the security of the computer it lives on. Smart cards offer a more secure alternative. A typical implementation sends the hash calculated from a document to the smart card's own CPU, which signs the hash using the stored private key and returns the signed result. The private key never has to leave the card.

  Activating a smart card requires a PIN, providing two-factor authentication: possession of the card and knowledge of the number. Ross Anderson and his students have broken some smart card designs, but many are engineered to be tamper-resistant. Crucially, private keys generated and stored on smart cards are generally assumed to exist in exactly one copy, making loss detectable. Software-protected keys are easier to copy silently, and such compromises are far harder to discover.

  Card readers that include their own numeric keypads add another layer of defense. A PC-integrated card reader that relies on the computer's keyboard to accept a PIN is vulnerable to keystroke logging software running on that computer. Standalone readers with their own keypads are often EAL3 certified and are harder to compromise through software or hardware tampering. Risk-averse organizations, including governments, financial institutions, and payment processors, often require FIPS 140-2 level 3 and FIPS 201 certification before accepting a signature as validated and secure.

• 7. The WYSIWYS Problem

  ›

  Peter Landrock and Torben Pedersen coined the term WYSIWYS, standing for What You See Is What You Sign, to describe a requirement that is harder to satisfy than it sounds. A digital signature applies to a string of bits. Humans and applications, however, work with the semantic interpretation of those bits, meaning the visual or functional representation produced by software. The problem is that the semantic interpretation of a bit string can change depending on which software processes it.

  An attacker who controls a user's computer can replace the signing application with one that displays the user's intended document on screen while actually presenting a different document to the signing algorithm. The user sees what they expect and approves; the signature attaches to something entirely different. Countermeasures include setting up mutual authentication between the word processor or email client and the signing application, so each can verify the other has not been tampered with. One approach requires all requests to the signing application to come from digitally signed binaries. WYSIWYS is a formal requirement for the validity of digital signatures, but the increasing complexity of modern computer systems makes it genuinely difficult to guarantee.

• 8. Law, Standards, and the Future

  ›

  Utah was the first jurisdiction to enact legislation authorizing digital signatures, followed closely by Massachusetts and California. The 1999 EU digital signature directive extended legal recognition across Europe, with follow-on legislation in 2014. The United Nations has maintained an active model law project in this area. Industries including the automobile sector, through the Automotive Network Exchange, and the healthcare sector, through the SAFE-BioPharma Association, have developed their own interoperability standards for use between members and regulators.

  Legal enactments have frequently outpaced technical standards, and the mismatch has created confusion for users who are not cryptographically knowledgeable. Adoption of technical standards for algorithm choice, key lengths, and interoperability has lagged behind legislation. Signing and encryption keys are often best kept separate precisely because of legal consequences: EU legislation generally means that anything digitally signed legally binds the signer to the terms of that document, so a signing key should never be used casually during an ongoing negotiation.

  The longer horizon belongs to quantum computing. CRYSTALS-Dilithium, Falcon, and SPHINCS+ are quantum-resistant signature schemes already listed among the recognized algorithms. CRYSTALS-Dilithium and Falcon are based on hard problems in lattices; SPHINCS+ relies on hash functions. A scheme attributed to Mihir Bellare and Gregory Neven addresses a different scaling challenge: it supports aggregation, allowing n signatures on n messages from n users to be compressed into a single constant-size signature, a property already finding use with Bitcoin.