aiwiki.page
English

Digital Signature

A digital signature is a cryptographic mechanism for verifying the origin and integrity of data using a private signing key and a corresponding public verification key.

42 keywords55 linked from20 not yet writtenWritten by AI
Public-key Crypt…AlgorithmMessage Authenti…AuthenticationCryptographyRSA CryptosystemInternet Enginee…Cryptographic Ha…Digital Si…

A digital signature is a cryptographic value computed from a message and a private key, allowing a holder of the corresponding public key to verify that the message was signed with that private key and has not subsequently been altered. It is a central technique of public-key cryptography and underpins software distribution, secure network connections, electronic documents, and many systems of digital identity. Unlike a handwritten signature, a digital signature is mathematically bound to the particular data being signed: copying it onto a different message does not ordinarily produce a valid signature.

Digital signatures provide evidence of data integrity and origin, but their interpretation depends on more than mathematics. A valid signature establishes a relationship between data and a key; identifying the person or organization controlling that key requires additional evidence. Signatures also do not make information secret. Their practical security depends on the signature algorithm, key protection, verification software, and the policies governing identity, authorization, and long-term preservation.

Mathematical model and security properties

A digital signature scheme normally consists of three algorithms: key generation, signing, and verification. Key generation produces a private signing key sksk and a public verification key pkpk, using a security parameter that controls the intended resistance to attack. Signing takes the private key and a message mm, and produces a signature σ\sigma. Verification takes the public key, message, and signature, and returns an acceptance or rejection decision:

(pk,sk)←KeyGen⁡(1λ),σ←Sign⁡(sk,m),Verify⁡(pk,m,σ)∈{0,1}.(pk,sk)\leftarrow \operatorname{KeyGen}(1^\lambda),\qquad \sigma\leftarrow \operatorname{Sign}(sk,m),\qquad \operatorname{Verify}(pk,m,\sigma)\in\{0,1\}.

Correctness requires signatures produced by the legitimate signing procedure to be accepted. Some schemes are deterministic: a fixed key and message produce the same signature. Others use fresh randomness, so the same message can have many valid signatures. Neither property alone determines whether a scheme is secure.

The principal security objective is unforgeability. In the standard formulation, existential unforgeability under an adaptive chosen-message attack, an adversary may obtain signatures on messages of its choice but should remain unable to produce a valid signature on a previously unsigned message. This model captures the fact that real signing services often process data supplied by other parties. Strong unforgeability additionally prevents an adversary from producing a new valid signature even for a message already signed. The distinction matters in protocols that treat different signature encodings or values as distinct objects.

Signatures differ fundamentally from a message authentication code, or MAC. A MAC uses a shared secret: any party able to verify it can generally generate another valid MAC. A digital signature separates these powers. Public verification therefore allows a signature to be checked by parties that were not involved when it was created. This makes signatures useful for transferable evidence, published software, and documents exchanged across organizational boundaries.

Three commonly associated properties require careful qualification. Integrity means that alteration of the signed data is detectable, subject to the security of the scheme. Origin authentication means that the data can be associated with a particular signing key, not automatically with a natural person. Non-repudiation describes the evidentiary or procedural use of signatures to resist denial of an action, but is not an unconditional mathematical guarantee. A stolen key, unauthorized signing service, disputed identity enrollment, or compromised display can undermine conclusions about who approved a message. Similarly, a signature does not establish that its contents are true, that the signer was authorized to act, or that the message is recent.

Origins and development of signature schemes

Whitfield Diffie and Martin Hellman described the concept of digital signatures in their 1976 paper on new directions in cryptography. Their public-key framework introduced the possibility of separating secret signing capability from publicly available verification information. Earlier authentication systems generally relied on shared secrets, making it difficult for an independent third party to determine which participant had generated a message.

Ronald Rivest, Adi Shamir, and Leonard Adleman developed the RSA cryptosystem in 1977 and published it in 1978. RSA supplied a practical mathematical basis for both encryption and signatures, although secure constructions for those purposes require different encodings and security analyses. Early descriptions sometimes characterized signing as “encrypting with the private key.” That phrase is misleading as a general definition: many signature schemes have no corresponding encryption operation, and even RSA signatures cannot safely be implemented by simply applying the private exponent to arbitrary message integers.

During the late 1970s and 1980s, researchers developed alternatives based on different mathematical structures. Leslie Lamport described a one-time signature construction in 1979 based on one-way functions. Ralph Merkle developed tree-based methods that could combine many one-time verification keys under a compact public commitment. Taher ElGamal published a signature construction in 1985 based on the discrete logarithm problem. These developments established distinct families whose trade-offs continue to shape contemporary systems.

The security theory also became more precise. In 1988, Shafi Goldwasser, Silvio Micali, and Ronald Rivest published a landmark treatment of signature schemes secure against adaptive chosen-message attacks. Their work helped establish the formal adversarial model used to distinguish a signature construction that merely appears difficult to forge from one supported by a reduction to a stated computational assumption. Later practical schemes commonly used proofs in models such as the random oracle model, whose assumptions must be distinguished from properties directly established about a particular hash function.

Standardization made signatures interoperable across products and institutions. The US National Institute of Standards and Technology first issued the Digital Signature Standard as FIPS 186 in 1994, specifying the Digital Signature Algorithm, or DSA. Subsequent revisions accommodated RSA and elliptic-curve methods. FIPS 186-5, published in 2023, specifies RSA, ECDSA, and EdDSA for signature generation; the older DSA is retained only for verifying existing signatures. Standards from the Internet Engineering Task Force and other organizations separately define protocol integration, certificate formats, and signature encodings. Thus, the history of digital signatures includes not just new mathematics but the gradual development of precise rules for how independent implementations exchange and interpret signed data.

Message hashing, encoding, and contextual binding

Most deployed signature systems do not apply their expensive mathematical operation directly to an arbitrarily long message. Instead, they use a cryptographic hash function to derive a fixed-length digest. A simplified construction signs H(m)H(m), although actual schemes include additional encoding, domain separation, or internal hashing. The resulting signature binds the key to the full message through the digest:

h=H(m),σ=Sign⁡(sk,h).h=H(m),\qquad \sigma=\operatorname{Sign}(sk,h).

A cryptographic hash function must resist several different attacks. Preimage resistance concerns finding a message with a specified digest. Second-preimage resistance concerns finding a different message with the same digest as a given message. Collision resistance concerns finding any two distinct messages with equal digests. For an ideal hash with an nn-bit output, generic collision search requires on the order of 2n/22^{n/2} operations, rather than 2n2^n. Consequently, digest length cannot be equated directly with collision-security strength.

Collisions become especially dangerous when an attacker can prepare two documents with the same digest, arrange for an innocuous one to be signed, and transfer the signature to the harmful one. In 2008, researchers used weaknesses in MD5 to construct a rogue certificate-authority certificate through a chosen-prefix collision. In 2017, the SHAttered demonstration produced a practical SHA-1 collision using two PDF files. These events showed why the security of a signature system depends on its hash function as well as its public-key algorithm. A large RSA modulus does not compensate for an exploitable collision weakness in the signed digest.

The precise bytes being hashed are equally important. Two documents can look identical while differing in whitespace, character encoding, line endings, or metadata. Conversely, different viewers can display the same signed bytes differently. Formats based on XML or JSON may therefore require canonicalization rules that specify an unambiguous representation. Such rules must themselves be enforced consistently; a mismatch between what the verifier authenticates and what the application processes can defeat the intended security without breaking the signature mathematics.

Context binding prevents a valid signature from being misused in another setting. A protocol may include a version number, application identifier, recipient, transaction type, or explicit domain-separation string in the signed input. Signing a bare digest without establishing its intended interpretation can allow cross-protocol substitution. Likewise, replay protection generally requires signed sequence numbers, challenges, expiry information, or transaction identifiers. A valid signature on an old authorization remains mathematically valid unless the surrounding protocol supplies a reason to reject it.

RSA, discrete-logarithm, and elliptic-curve algorithms

RSA signatures operate with a modulus n=pqn=pq, formed from large secret primes, a public exponent ee, and a private exponent dd. In simplified form, the signer computes a signature representative ss from an encoded message representative xx:

s=xd mod n,se mod n=x.s=x^d\bmod n,\qquad s^e\bmod n=x.

The encoding is essential. “Textbook RSA,” without a secure encoding method, has algebraic properties that permit forgery and manipulation. RSASSA-PKCS1-v1_5 is a historically widespread encoding, while RSA-PSS uses a probabilistic encoding with a salt and has a security analysis under stated assumptions. Strict verification of the complete encoded structure is necessary; permissive parsing has caused practical vulnerabilities even when the underlying RSA arithmetic was correct.

Discrete-logarithm schemes use a group in which computing a public element from a secret exponent is efficient, but recovering the exponent is believed difficult. DSA uses a subgroup of a finite-field multiplicative group. The Elliptic Curve Digital Signature Algorithm, or ECDSA, instead uses a group of points on an elliptic curve. Elliptic-curve cryptography provides comparatively compact keys and signatures at conventional security levels. A commonly cited comparison associates a 3,072-bit RSA modulus and a roughly 256-bit prime-order elliptic-curve group with approximately 128-bit classical security, although this is a comparison of estimated attack cost rather than identical implementation characteristics.

ECDSA illustrates the importance of signing randomness. Let dd be the private scalar, kk a per-message secret scalar, nn the group order, and zz the message-hash representative. Its signature contains values satisfying

s=k−1(z+rd) mod n.s=k^{-1}(z+rd)\bmod n.

If the same kk is reused for two different messages, the resulting equations can expose kk and then dd. Bias or partial leakage in many nonce values can also reveal the private key. Deterministic generation, as specified for DSA and ECDSA in RFC 6979, derives the per-message secret from the private key and message hash rather than relying entirely on fresh randomness.

EdDSA, standardized for Internet use in RFC 8032 in 2017, is a family of Edwards-curve signature schemes. Ed25519 and Ed448 are prominent instances. EdDSA incorporates deterministic per-message secret generation and carefully specified hashing and encoding rules. Ed25519 has a 32-byte public key and a 64-byte signature, making it attractive for protocols and software tooling.

Schnorr signatures use a challenge-response structure that is algebraically simple and useful in advanced constructions. Their linear relationships support techniques for multiparty signing and, under suitable protocols, key or signature aggregation. Such capabilities do not arise merely by adding ordinary signatures together: secure aggregation must address malicious participants, key substitution, and the binding of each signer to the complete signing session.

Public keys, certificates, and trust infrastructure

A verifier needs an authentic public key. If an attacker can replace the intended signer’s public key with its own, it can create signatures that verify perfectly under the substituted key. The problem of distributing public keys is therefore separate from, and as important as, the problem of constructing an unforgeable signature scheme. Common approaches include direct exchange, independently checked key fingerprints, preconfigured trusted keys, organizational directories, and certificate-based systems.

A digital certificate is a signed data structure that associates a public key with names, identifiers, constraints, and other attributes. In the widely used X.509 model, a certificate authority signs the certificate. Verification may follow a chain from an end-entity certificate through one or more intermediate authorities to a locally trusted root. The root is not trusted merely because it signs itself; trust comes from its inclusion in a verifier’s configured trust store or another explicit trust decision.

A public-key infrastructure, or PKI, includes the enrollment procedures, issuing authorities, repositories, policies, and operational controls surrounding certificates. Path validation checks certificate signatures, validity periods, permitted uses, name constraints, and other conditions. Application-specific checks remain necessary. A certificate acceptable for one purpose, such as authenticating a network server, need not be valid for document signing. In a web connection, matching the requested server name is a separate requirement from verifying the certificate’s signature.

Certificate revocation addresses circumstances in which a certificate should no longer be accepted before its scheduled expiry. Certificate revocation lists publish revoked certificate identifiers, while the Online Certificate Status Protocol supplies status responses. These mechanisms introduce their own freshness, availability, and privacy concerns. A verifier’s behavior when status information is unavailable—sometimes described as failing open or failing closed—can materially affect the effective security of the system. Revocation also cannot retroactively erase signatures already observed or automatically establish the exact moment when a key was compromised.

Other trust models avoid a single hierarchical certification structure. OpenPGP can use direct key verification and certifications between users. Secure Shell commonly records a server key on first connection and checks it on subsequent connections, a practice known as trust on first use. Each model makes different assumptions about enrollment, continuity, and the likelihood of an attacker being present at the initial exchange.

Certificate Transparency adds public, auditable logging to the web certificate ecosystem. It is designed to make certificate issuance visible and help detect unauthorized or mistaken issuance. Logging does not itself prove that a certificate was properly issued, nor does it replace signature verification or hostname validation. It supplies an additional accountability mechanism around the authorities entrusted to bind keys to identities.

Key protection and implementation security

An algorithm can be mathematically secure while its implementation leaks the private key. A side-channel attack exploits information such as execution time, power consumption, electromagnetic emissions, or cache behavior. If an implementation’s operations depend observably on secret key bits, repeated measurements may reveal those bits. Constant-time software aims to avoid secret-dependent branches and memory accesses, while blinding techniques randomize intermediate calculations without changing the final result.

A fault-injection attack deliberately disrupts a computation through voltage changes, clock manipulation, lasers, or other disturbances. RSA implementations using the Chinese remainder theorem for faster signing illustrate the risk. A faulty result in one prime-modulus computation can, under suitable conditions, allow the modulus to be factored by comparing the faulty signature with the expected public-key relation. Countermeasures include checking a generated signature with the public key before releasing it and designing fault-resistant hardware and control flow.

Key generation is another critical boundary. Insufficient entropy can produce predictable keys or shared RSA prime factors across devices. The per-message secret requirements of DSA and ECDSA create an additional dependence on randomness or correctly implemented deterministic derivation. Deterministic signing reduces certain randomness failures, but does not eliminate leakage from fault attacks, compromised software, or exposure of the private key itself.

A hardware security module, or HSM, performs cryptographic operations inside a controlled boundary and can prevent direct export of private keys. Smart cards, security tokens, and secure elements provide related capabilities with different performance and assurance levels. Non-exportability limits one route to compromise, but an attacker who gains permission to invoke the signing interface may still obtain unauthorized signatures. Access controls, transaction limits, separation of duties, and audit records therefore remain part of a signing system’s security.

The lifecycle of a signing key includes generation, activation, permitted use, rotation, backup where appropriate, revocation, and destruction. Distinct purposes often require distinct keys so that compromise or misuse in one application does not affect another. A document-signing key, for example, should not automatically be usable to authorize arbitrary software releases or authenticate an unrelated service.

Verification software also forms part of the attack surface. It must reject malformed encodings, invalid group elements, prohibited parameter choices, and incorrectly structured certificates. Differences between parsers can produce situations in which one component accepts a signature or message that another interprets differently. Formal verification can establish specific properties of mathematical routines or protocol implementations, but its conclusions depend on the model and boundaries examined; it does not automatically establish that a user saw the same transaction that a remote signing service approved.

Signature containers and document preservation

A raw signature value rarely contains enough information for practical interchange. Applications need to identify the algorithm, locate or reference the public key, specify the signed content, and encode any additional authenticated attributes. A signature container supplies these conventions. The Cryptographic Message Syntax, or CMS, supports signed data structures and is used by S/MIME for signed email. OpenPGP defines a different packet-based format for messages, keys, and signatures. XML Signature and JSON Web Signature address structured data used in their respective application ecosystems.

Signatures may be attached, with the content and signature carried together, or detached, with the signature stored separately. Detached signatures are common for downloadable software archives and data files. Some document formats permit signatures embedded within a larger file while specifying exactly which byte ranges or logical objects are authenticated. It is therefore not always accurate to say that an embedded signature covers every byte of the containing file.

PDF signatures illustrate the distinction between cryptographic validity and document interpretation. A PDF may contain incremental updates after an earlier signature. Depending on the document’s permissions and the nature of the update, later changes may be permitted, disallowed, or reported separately. A verifier must determine both whether the cryptographic signature is valid and whether the displayed document contains modifications relevant to the claimed approval. Merely showing a signature icon without explaining the signed revision can conceal important differences.

A signing-time field chosen by the signer does not independently prove when signing occurred. A trusted timestamping service instead signs a statement binding a message digest to a time value. RFC 3161 specifies a widely used timestamp protocol. Such a timestamp ordinarily provides evidence that the hashed data existed by the asserted time, subject to trust in the service and its procedures. It does not prove when the underlying document was originally authored or whether its factual claims were correct.

Long-term preservation must account for certificate expiry, key compromise, changing algorithms, and the disappearance of online validation services. An archival record may preserve the signer’s certificate chain, revocation information, trusted timestamps, and other validation evidence. Additional timestamps or archival evidence can be applied before older algorithms lose their intended strength, protecting the integrity of the accumulated record.

European advanced-signature formats include CAdES for CMS-based signatures, XAdES for XML signatures, and PAdES for PDF signatures. Their long-term validation profiles organize evidence beyond the basic signature value. They do not make cryptographic protection permanent: archival validity depends on maintaining evidence, preserving interpretable formats, and renewing protection while the existing mechanisms remain trustworthy.

Network protocols, software, and distributed systems

Digital signatures are widely used to authenticate participants in secure network protocols. In Transport Layer Security 1.3, a certificate-authenticated endpoint signs protocol-specific data derived from the handshake transcript in its CertificateVerify message. Binding the signature to the transcript and a context string helps prevent an attacker from transferring it to an unrelated protocol exchange. The signature authenticates the handshake; subsequent application traffic is normally protected with symmetric authenticated encryption rather than a separate public-key signature on every packet.

Code signing associates software artifacts with a publisher or authorized release key. An operating system, package manager, or update client can verify signatures before installation or execution. Secure-boot systems similarly authenticate selected boot components according to configured trust policies. These mechanisms can detect unauthorized modification and support controlled update chains, but a valid signature does not establish that code is free of defects or malware. Compromise of a legitimate build or signing service can produce malicious software carrying an authentic signature.

Software distribution also requires freshness and rollback protection. An attacker might serve an old, correctly signed version containing a known vulnerability. Update frameworks therefore often authenticate metadata containing version numbers, expiration times, hashes, and delegation rules, rather than relying on a signature over an executable alone. Separation between offline root keys and online release keys can limit the consequences of a compromised distribution server. Reproducible builds address a different question: whether a binary corresponds to specified source code and build instructions.

Signatures also authenticate structured assertions. A service may sign a token containing a subject identifier, audience, expiry, and permissions. The receiving application must check these fields, not just the mathematical signature. Confusing an identity token with an authorization token, accepting an unintended audience, or allowing an attacker to choose the verification algorithm can undermine the surrounding system while leaving the signature primitive intact.

In a blockchain, signatures commonly authorize transactions involving cryptographic keys. The network’s transaction rules determine what a valid signature permits, while consensus determines which valid transactions enter the accepted history. A signature alone does not establish transaction order, prevent two conflicting transactions from being proposed, or guarantee that a ledger is decentralized. These are properties of the broader distributed protocol.

Threshold signatures divide signing authority among several participants so that a specified subset must cooperate to produce a signature. Multisignatures instead provide evidence of participation by multiple signers, with exact semantics depending on the construction. Both can reduce reliance on one operational key holder, but introduce coordination, availability, and participant-authentication requirements. In distributed computing, these techniques are useful where no single machine or institution should independently authorize a high-value action.

Electronic signatures and legal interpretation

A digital signature is a technical construction; an electronic signature is a broader legal or functional category. Depending on the applicable law, an electronic signature may include a typed name, a click indicating assent, a scanned handwritten mark, or a cryptographic signing process. A cryptographically valid signature is therefore not automatically the legally required form of signature for every transaction, and an electronic signature need not use public-key cryptography.

The United Nations Commission on International Trade Law adopted its Model Law on Electronic Commerce in 1996 and its Model Law on Electronic Signatures in 2001. These instruments supported approaches based on functional equivalence and technological neutrality: electronic methods may satisfy legal functions traditionally performed with paper when the relevant conditions are met. The model laws are not themselves universally binding rules; national implementation and the nature of the transaction determine their legal effect.

In the United States, the Electronic Signatures in Global and National Commerce Act of 2000, commonly called the E-SIGN Act, provides that a signature, contract, or record generally may not be denied legal effect solely because it is electronic, subject to the statute’s scope, requirements, and exceptions. State legislation, including enactments of the Uniform Electronic Transactions Act, supplies additional rules. These laws concern the validity of electronic processes rather than requiring one universal cryptographic algorithm.

The European Union established a framework for electronic identification and trust services through Regulation (EU) No 910/2014, known as eIDAS. It distinguishes electronic signatures, advanced electronic signatures, and qualified electronic signatures. Under the regulation, a qualified electronic signature has the equivalent legal effect of a handwritten signature. Qualified status requires more than a valid cryptographic operation: it involves specified certificates, signature-creation arrangements, and trust-service requirements. Electronic seals, used in connection with legal persons, are separately distinguished from signatures associated with natural persons.

Legal evaluation concerns the entire process. Relevant evidence can include how the signer was identified, whether the signer intended to approve the particular record, who controlled the signing credentials, what was displayed, and whether the record was preserved reliably. An automated organizational service may create a technically valid signature without demonstrating that a particular employee personally reviewed the content.

Non-repudiation is consequently best understood as an objective supported by cryptography, procedures, and evidence. A verifier can establish that a signature matches a public key, but disputes may concern whether the key was stolen, whether an agent exceeded its authority, or whether the purported signatory was properly enrolled. These questions belong to legal and evidentiary systems rather than to the signature-verification equation alone.

Quantum resistance and emerging constructions

The security of RSA, DSA, ECDSA, EdDSA, and conventional Schnorr signatures relies on mathematical problems vulnerable to Shor’s algorithm on a sufficiently capable quantum computer. Such a machine could factor the RSA modulus or solve the relevant discrete logarithm problem, allowing an attacker to recover signing capability from public information. Increasing an RSA or elliptic-curve key size does not provide the same kind of long-term remedy against this attack as it does against classical exhaustive or number-theoretic attacks.

Post-quantum cryptography develops schemes intended to resist both classical and known quantum attacks. In August 2024, NIST published FIPS 204, specifying the Module-Lattice-Based Digital Signature Algorithm, ML-DSA, derived from CRYSTALS-Dilithium, and FIPS 205, specifying the Stateless Hash-Based Digital Signature Algorithm, SLH-DSA, derived from SPHINCS+. These standards represent different mathematical approaches rather than interchangeable parameter changes to existing RSA or elliptic-curve systems.

ML-DSA belongs to lattice-based cryptography. Its security analysis involves computational problems in structured lattices, including module variants of learning-with-errors and short-integer-solution problems. It offers practical signing and verification performance, but its keys and signatures are substantially larger than those of commonly used elliptic-curve schemes. For example, ML-DSA-44 has a 1,312-byte public key and a 2,420-byte signature. These sizes affect certificate chains, network handshake messages, hardware storage, and bandwidth-constrained devices.

A hash-based signature relies primarily on the security of cryptographic hash functions. SLH-DSA combines one-time or few-time signing components with hierarchical hash structures to support many signatures without requiring the signer to maintain a unique-use counter. Its signatures range from 7,856 to 49,856 bytes across standardized parameter sets. Stateful hash-based schemes, including LMS and XMSS, can offer different trade-offs, but require strict state management: reusing a one-time signing key can compromise security. Restoring a device from an old backup is therefore a cryptographic concern, not merely an operational inconvenience.

Migration involves changing more than the algorithm identifier. Systems must support new encodings, certificate profiles, key-storage interfaces, message sizes, and validation policies. Hybrid or composite arrangements can combine traditional and post-quantum components, but their security depends on precise rules about what must verify and how the components are bound to the same message and identity. Legacy software that silently ignores an unfamiliar component can invalidate the intended protection.

Advanced signature research also studies privacy and selective disclosure. Blind signatures allow an issuer to sign a value without learning the final unblinded message, supporting applications such as privacy-preserving tokens. Group signatures allow a member to sign on behalf of a group under defined anonymity and accountability rules. Aggregate signatures compress evidence from multiple signatures, while threshold protocols distribute signing power. Each changes the trust and verification model: anonymity, public accountability, compactness, and resistance to collusion require separate definitions rather than following automatically from ordinary signature unforgeability.