up:: Foundations MOC

Digital Signature

A digital signature is a public-key cryptographic primitive that proves a message, certificate, or piece of software was produced by the holder of a specific private key and has not been altered since, giving a verifier three guarantees at once: authenticity (who signed it), integrity (that nothing changed), and non-repudiation (the signer cannot credibly deny signing). The signer creates the signature with a private key that only they hold, and anyone can check it with the matching public key that is shared openly. The classical signature algorithms that carry this job across the internet today, RSA, ECDSA, and Ed25519, all rest on math that a large quantum computer running Shor’s algorithm solves efficiently, which is why the post-quantum transition has to retire and replace every one of them.

The short version:

1. A digital signature does one job: it proves authenticity, integrity, and non-repudiation. Sign with the private key, verify with the public key.
2. It differs from a MAC by being asymmetric. A MAC uses one shared secret both parties hold, so it can’t prove which party signed; a signature uses a private key only one party holds, so it can.
3. It differs from encryption by aim and by key direction. Encryption hides data; a signature proves origin and does not hide anything.
4. Signatures are the trust layer of almost everything: TLS certificates, code and firmware signing, signed documents, JWT and SAML tokens, and SSH keys.
5. Classical signatures are quantum-vulnerable in real time. A forgery risk, not a harvesting one: once a quantum computer exists, an attacker recovers the private key from the public key and forges anything. The standardized replacements are ML-DSA (general purpose), SLH-DSA (conservative), and FN-DSA (compact).

Think of a wax seal pressed from a signet ring. Anyone who receives the letter can recognize the crest and trust that it’s genuine, but only the person holding the ring can press that exact seal, and if someone rewrites a line of the letter the seal stops matching the contents. A digital signature is the mathematical version of that ring. The private key is the ring itself, the public key is everyone’s shared knowledge of what the crest looks like, and the math makes the impression impossible to counterfeit. The quantum problem is that Shor’s algorithm hands a forger a perfect copy of the ring, cut from the public knowledge of the crest alone.

What is a digital signature?

A digital signature is a value computed over a message with a private key, such that anyone with the matching public key can confirm two things: that the value could only have been produced by the private-key holder, and that the message is byte-for-byte what was signed. It belongs to the family of public-key (asymmetric) primitives, alongside public-key encryption and key exchange, and it’s the primitive responsible for trust rather than secrecy.

NIST states the intended uses of a signature scheme plainly in its standards: detecting unauthorized modifications to data, authenticating the identity of the signer, and supporting non-repudiation so a signer can’t later credibly deny having signed. Those three map to the three properties every signature delivers together:

1. Authenticity. The signature ties the message to a specific private key, and therefore to whoever controls it. A valid signature is evidence the message came from the expected source.
2. Integrity. Because the signature is computed over the message content, changing even one bit of the message makes the signature fail verification. A passing check means the content is exactly what was signed.
3. Non-repudiation. Only the private-key holder could have produced the signature, so they can’t plausibly deny it afterward. This is the property that makes signatures usable for contracts, audit trails, and legal instruments.

The umbrella US standard for classical signatures is the Digital Signature Standard, FIPS 186-5, which approves three algorithm families: RSA, ECDSA, and EdDSA (the scheme behind Ed25519).

Source: NIST, “Digital Signature Standard (DSS),” FIPS 186-5, February 2023, FIPS 186-5.

NIST, “Module-Lattice-Based Digital Signature Standard,” FIPS 204, August 2024, FIPS 204.

How does a digital signature actually work?

A digital signature relies on a key pair where the two keys are mathematically linked but the private one can’t be derived from the public one by any efficient classical method. The signer keeps the private key secret and publishes the public key freely, and the whole scheme runs in three steps:

1. Key generation. The signer generates a linked pair: a private signing key kept secret, and a public verification key shared openly (usually inside a certificate that binds the key to an identity).
2. Signing. The signer first hashes the message down to a fixed-size digest with a cryptographic hash function, then computes the signature over that digest using the private key. Signing the hash rather than the raw message is what lets a signature cover a document of any size efficiently, and it’s why the strength of a signature also depends on the strength of the hash underneath it.
3. Verification. Anyone with the public key recomputes the message hash and runs the algorithm’s verification equation against the signature. If it checks out, the verifier learns both that the private-key holder produced it and that the message wasn’t altered.

The security rests entirely on the private key staying secret and on the underlying hard problem being genuinely hard to reverse. For RSA that hard problem is integer factorization; for ECDSA and Ed25519 it’s the elliptic-curve discrete logarithm problem. Both of those are exactly the problems a quantum computer dissolves, which is the whole reason this primitive is on the migration list.

Source: NIST, “Digital Signature Standard (DSS),” FIPS 186-5, February 2023, FIPS 186-5.

How is a digital signature different from a MAC?

Both a digital signature and a Message Authentication Code (MAC) prove that a message is authentic and unaltered, but they do it with different kinds of keys, and that difference decides what each one can promise. A MAC (such as HMAC) is symmetric: the sender and receiver share one secret key, and the same key both produces and checks the tag. A digital signature is asymmetric: the signer holds a private key nobody else has, and verifiers use a separate public key.

That single structural difference produces the property that matters most in disputes. Because both parties in a MAC relationship hold the identical secret, either one could have produced a given tag, so a MAC proves the message came from someone holding the key but can’t single out which party. A signature can single out the signer, because only they hold the private key, and that’s what gives signatures non-repudiation and MACs none.

Property	Digital signature	MAC (e.g. HMAC)
Key model	Asymmetric (private signs, public verifies)	Symmetric (one shared secret)
Who can create it	Only the private-key holder	Anyone holding the shared key
Who can verify it	Anyone with the public key	Only holders of the shared key
Non-repudiation	Yes	No
Typical cost	Slower, larger output	Fast, small output
Quantum status	Classical schemes broken by Shor’s algorithm	Hash-based, only mildly weakened by Grover’s algorithm

The practical read is that you reach for a MAC when the same trusted parties share a secret and just need speed (protecting data in transit inside a single session), and for a signature when many independent parties need to verify origin without sharing any secret, and when the proof has to hold up as evidence.

Source: NIST, “The Keyed-Hash Message Authentication Code (HMAC),” FIPS 198-1, July 2008, FIPS 198-1.

How is signing different from encryption?

Signing and encryption are separate jobs that use the key pair in opposite directions, and confusing them is one of the most common sources of security bugs. Encryption protects confidentiality, keeping data secret; a signature protects authenticity and integrity, proving origin without hiding anything. A signed message is fully readable to everyone; the signature just travels alongside it as proof.

The key direction flips between the two operations:

1. Public-key encryption. To send someone a secret, you encrypt with their public key, and only they can decrypt with their private key. The public key locks; the private key unlocks.
2. Digital signing. To prove you produced something, you sign with your own private key, and anyone verifies with your public key. The private key stamps; the public key checks the stamp.

A single system usually needs both, handled by separate primitives. A TLS session, for example, uses a signature to authenticate the server’s certificate and a key-exchange mechanism to set up the confidential channel. In the post-quantum world these split even more cleanly into two different standards: signatures move to ML-DSA, while key establishment moves to ML-KEM. Treating “post-quantum” as one switch is a mistake, because signing and key exchange are different problems with different replacements.

Where are digital signatures used?

Digital signatures sit inside the trust machinery that decides whether a system should believe a certificate, a program, a login, or a document. They’re so woven into ordinary infrastructure that most of them are invisible until one fails. The high-stakes surfaces:

1. TLS and web PKI. Every certificate behind the browser padlock is a signed statement (“this really is your bank”), and the server proves control of its key with a signature during the TLS handshake. The entire public-key infrastructure is a tree of signatures, each Certificate Authority signing the certificates below it.
2. Code and firmware signing. Operating systems, app stores, and secure-boot chains verify a signature before trusting a software update or letting firmware run. The signature is what separates a legitimate update from malware.
3. Documents and legal instruments. Signed PDFs, e-signature platforms, and government records rely on signatures for authenticity and non-repudiation, so a document’s origin holds up later.
4. Tokens and federated identity. JWTs and SAML assertions are signed so an API or identity provider can prove a token is authentic and unmodified, which is what holds single sign-on together.
5. SSH and infrastructure access. SSH host keys and user keys authenticate servers and administrators, gating remote access to infrastructure.
6. Blockchains and wallets. Transactions are authorized by signatures; the private key is the wallet and a signature is the spend authorization.

Because this is the trust layer rather than the secrecy layer, a broken signature scheme is a forgery problem: certificates, updates, tokens, and transactions that look authentic but are not.

How does the quantum transition affect digital signatures?

The quantum transition hits digital signatures hard and in real time, because the classical schemes rest on exactly the math a quantum computer is good at. A cryptographically relevant quantum computer running Shor’s algorithm efficiently solves both integer factorization and the discrete logarithm problem, which are the hard problems under RSA, ECDSA, and Ed25519. Take a public key, run Shor’s, and out comes the private key. Once an attacker holds the private key, they hold the signet ring and can forge any signature that key was trusted to make.

This is a Non-HNDL threat, and the distinction is worth holding onto:

1. It targets trust rather than secrecy. The harvest-now-decrypt-later threat is about recording encrypted data today and decrypting it after a quantum computer arrives. Signature forgery is different: there’s nothing to record. The attack is real-time impersonation once the machine exists.
2. The material is already public. Every verification key an attacker would target already sits out in the open, inside a certificate or a token, by design. There’s no traffic to intercept and no vault to breach. The attacker needs the public key, which they already have, and the machine, which they’re waiting for.
3. The worst case is PKI collapse. Breaking a single root Certificate Authority’s signing key makes every certificate beneath it forgeable at once, which is effectively arbitrary trust across a whole domain.

The reason this is a present-day problem even though the machine is years out is Mosca’s theorem: migrating signature infrastructure (rebuilding certificate hierarchies, distributing new roots, updating trust stores and vendor signing services) takes years, and it has to finish before the machine arrives, because a forgery after the fact is undetectable and there’s no clean recovery. Anything signed today that still needs to be trusted after a quantum computer exists is already living on borrowed time.

Source: P. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM J. Computing, 1997, quant-ph/9508027.

What replaces classical digital signatures?

Classical signatures get replaced by post-quantum signature standards, not upsized or patched, because there’s no larger key that rescues a scheme once Shor’s algorithm applies (unlike symmetric encryption, where moving from AES-128 to AES-256 restores the margin). NIST finalized two post-quantum signature standards in August 2024 and has a third in draft, and the right choice depends on the role:

Replacement	Standard	Basis	Best fit
ML-DSA	FIPS 204 (final)	Lattice (Module-LWE)	General-purpose default: TLS certificates, code signing, tokens, most everyday signing
SLH-DSA	FIPS 205 (final)	Hash-based	Conservative, long-lived roots of trust where an alternate math assumption is worth a larger signature
FN-DSA	FIPS 206 (draft)	Lattice (NTRU)	Constrained settings where compact signatures matter most

For most environments ML-DSA is the direct successor. SLH-DSA is the deliberately conservative option where a signing key protects something for decades and you want its security resting on plain hash functions rather than lattice math. FN-DSA is the compact choice for size-sensitive roles and was still in draft as of NIST’s late-2024 signature work.

The operational catch is that these are not drop-in swaps. Post-quantum signatures and keys are much larger than elliptic-curve ones (the smallest ML-DSA signature runs over 2,400 bytes versus roughly 64 bytes for ECDSA P-256), so the migration cost lands on certificates, parsers, trust stores, and transport limits rather than on CPU. The common transitional pattern is dual signatures or composite certificates, carrying both a classical and a post-quantum signature so verifiers upgrade at their own pace. Designing for that flexibility is crypto-agility.

Sources: NIST FIPS 204, “Module-Lattice-Based Digital Signature Standard,” August 2024, FIPS 204.

NIST FIPS 205, “Stateless Hash-Based Digital Signature Standard,” August 2024, FIPS 205.

When do classical digital signatures have to be gone?

The deadline for classical signatures is set by NIST IR 8547, NIST’s transition roadmap, which puts every classical public-key algorithm on a deprecation-then-disallowance schedule:

Milestone	Year	What it means
Deprecated	2030	112-bit-strength classical signatures become deprecated, still usable but only with the data owner formally accepting the risk
Disallowed	2035	All classical signature algorithms become disallowed for federal use, with no exceptions

“Deprecated” and “disallowed” are different instructions. Deprecated means you may still use it while you own the documented risk; disallowed is a hard stop. Because insurers, sector regulators, and procurement programs align to NIST, these federal dates function as the practical industry timeline even for organizations that never touch a government contract. The roots of trust (Certificate Authorities, firmware anchors, code signing) take the longest to migrate, so they’re the ones to sequence first.

Source: NIST IR 8547 (Initial Public Draft), “Transition to Post-Quantum Cryptography Standards,” November 2024, NIST IR 8547 ipd.

Common misconceptions

1. “A digital signature encrypts the message.” It doesn’t. A signature proves authenticity and integrity while leaving the message fully readable. Confidentiality is a separate job handled by encryption, so a broken signature scheme is a forgery risk, not a data-leak risk.
2. “A signature and a MAC are basically the same thing.” Both prove integrity, but a MAC uses a shared secret that both parties hold, so it can’t prove which party produced it. Only a digital signature, built on a private key one party holds, delivers non-repudiation.
3. “Quantum-breaking signatures only affects future documents.” Anything long-lived that’s signed today (a root certificate, a firmware image, an archived legal record) has to stay trustworthy for years, so today’s classical signatures on long-lived artifacts are already exposed to a future forger.
4. “A bigger key will save my signatures from quantum.” For RSA and elliptic-curve signatures, increasing key size buys almost nothing against Shor’s algorithm. The fix is switching to a post-quantum signature algorithm, not enlarging a classical one.
5. “Post-quantum signatures are a drop-in replacement.” Same role, very different dimensions. The much larger keys and signatures ripple into certificates, parsers, and trust stores, so it’s a planned migration rather than a swap.
6. “If the signature checks out, the signer must be trustworthy.” A valid signature only proves the message came from the holder of that private key and wasn’t altered. It says nothing about whether that key holder is honest, or whether the key was stolen. Trust in the key itself comes from PKI and key management.

Questions people ask

What’s the difference between a digital signature and an electronic signature? An electronic signature is any electronic mark of intent to sign, including a typed name or a scanned image, and it carries no cryptographic guarantee by itself. A digital signature is a specific cryptographic mechanism that mathematically proves authenticity and integrity. Reputable e-signature platforms use digital signatures underneath to make their electronic signatures verifiable.

Does a digital signature keep my data secret? No. Signing proves who produced a message and that it wasn’t changed, but the message stays fully readable to anyone. If you also need secrecy, you pair the signature with encryption, which is a separate primitive with a separate key.

Which classical signature algorithms are quantum-vulnerable? All of the widely deployed ones: RSA, ECDSA, and Ed25519 (EdDSA). They all rest on integer factorization or the discrete logarithm problem, both of which Shor’s algorithm solves efficiently on a quantum computer.

Do I need to replace my signatures right now? Not overnight, but you should be inventorying them now and moving the high-stakes, long-lived uses first. NIST’s schedule disallows classical signatures for federal use by 2035, and the roots of trust (CAs, firmware, code signing) take the longest to migrate, so they start earliest.

What is the direct replacement for a classical digital signature? ML-DSA for general-purpose signing, SLH-DSA for conservative long-lived roots of trust, and FN-DSA (still in draft) where compact signatures matter most.

Why do signatures sign a hash of the message instead of the message itself? Public-key operations are slow and work on fixed-size inputs, so signing a short hash lets one signature cover a document of any size efficiently. It also means the security of a signature depends on the hash function underneath it, which is why signature schemes pair with strong hashes like SHA-256.

Is a digital signature the same as a certificate? No, but they work together. A signature is the cryptographic proof; a certificate is a signed document that binds a public key to an identity, so a certificate is itself an application of signatures. The PKI that issues certificates is a hierarchy of signatures, each authority signing the layer below.

How big are post-quantum signatures compared to classical ones? Much bigger. An ECDSA P-256 signature is about 64 bytes; the smallest ML-DSA signature is over 2,400 bytes. That size jump is the main engineering cost of the migration, landing on certificates, parsers, and transport limits.

---

Everything here is the map, given freely. When your team needs its own signatures and certificates found, sized, and sequenced onto a post-quantum path, that’s the work I do. Request an alignment briefing.

Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.