Digital Signatures & Integrity — Explain digital signatures...

SECTION 1

Historical Context & Motivation

Long before the Internet existed, people authenticated documents with handwritten signatures and wax seals—physical artifacts that were difficult (though not impossible) to forge. As communication shifted to electronic channels in the latter half of the twentieth century, a fundamental problem emerged: how can a recipient verify that a digital message truly originates from the claimed sender and has not been tampered with during transit? Unlike a physical letter, a bitstream can be copied, modified, and retransmitted without leaving any visible trace of alteration.

The quest for a solution drew on decades of research in public-key cryptography and cryptographic hash functions. The result—digital signatures—provides three security guarantees that are now woven into every layer of modern computing: authentication (proof of origin), integrity (proof that the data is unmodified), and non-repudiation (the signer cannot credibly deny having signed). Understanding this timeline helps situate the technology within the broader arc of cryptographic research.

1976

Diffie–Hellman Key Exchange

Whitfield Diffie and Martin Hellman publish New Directions in Cryptography, introducing the concept of asymmetric (public-key) cryptography and first proposing the idea of digital signatures, though without a concrete construction.

1977

RSA Algorithm

Ron Rivest, Adi Shamir, and Leonard Adleman devise RSA, providing the first practical scheme that can perform both encryption and digital signing using modular exponentiation and the difficulty of integer factorization.

1991

DSA Proposed by NIST

The U.S. National Institute of Standards and Technology proposes the Digital Signature Algorithm (DSA) as a federal standard, based on the discrete-logarithm problem, offering signature-only functionality without encryption.

2001

SHA-2 Family Released

NIST publishes the SHA-256 and SHA-512 hash functions, addressing weaknesses in MD5 and SHA-1, and establishing the dominant hash family used inside modern digital-signature pipelines.

2020s

Post-Quantum Signatures

NIST begins standardizing post-quantum signature schemes such as CRYSTALS-Dilithium and FALCON, anticipating the threat that large-scale quantum computers would pose to RSA and ECDSA.

The central question this lesson addresses is deceptively simple: given a message m received over an untrusted channel, how can the recipient be cryptographically certain that m was authored by the claimed sender and that no bit was changed en route? Digital signatures answer this by combining hash functions with asymmetric key pairs.

SECTION 2

Core Principles & Definitions

Before diving into algorithms, it is essential to formalize the foundational concepts that make digital signatures possible. A digital signature scheme relies on the interaction of several primitives: a key-generation algorithm that produces a private–public key pair, a signing algorithm that produces a signature from the message and the private key, and a verification algorithm that accepts or rejects the signature using the public key. The security of the entire scheme rests on computational hardness assumptions—problems that no known efficient algorithm can solve.

Authentication

Only the holder of the private key can produce a valid signature, proving the message's origin.

Integrity

Even a single-bit change in the message causes the hash digest to avalanche, making any tampering immediately detectable upon verification.

Non-Repudiation

Because the private key is (ideally) known only to its owner, the signer cannot later deny authorship—a property that symmetric MACs cannot provide.

Asymmetric Key Pair

A mathematically linked pair: a secret private key (sk) used for signing, and a publicly distributed public key (pk) used for verification.

Cryptographic Hash Function

A deterministic, one-way function H that maps arbitrary-length input to a fixed-length digest, satisfying collision resistance and pre-image resistance.

✦ KEY TAKEAWAY

Think of a digital signature like a tamper-evident, biometric seal on a package. Only you possess your fingerprint (private key), so anyone who sees the seal (public key verification) knows the package came from you. And if someone opens the package and changes the contents, the seal visibly breaks (hash mismatch). Unlike a shared password between you and a courier, the seal proves to any third party—including a court—exactly who sealed it. That is the leap from symmetric MACs to asymmetric digital signatures.

SECTION 3

Visual Explanation — The Signing & Verification Pipeline

The diagram below illustrates the complete lifecycle of a digitally signed message, from the sender's signing operation through transmission to the recipient's verification check. Pay particular attention to the two parallel paths on the verifier side: one recomputes the hash of the received message, and the other recovers the hash from the signature using the sender's public key. A match between these two values confirms both authenticity and integrity.

Alice hashes the original message m, signs the digest with her private key, and transmits both m and the signature σ. Bob independently hashes the received message m′ and uses Alice's public key to recover the digest from σ. If the two digests match, the signature is valid.

Several details in the diagram merit emphasis. First, the message itself is not encrypted—digital signatures provide authenticity and integrity, not confidentiality (encryption is a separate concern). Second, the hash function acts as a compressor: signing a short, fixed-length digest is far more efficient than signing the entire (potentially gigabyte-scale) message directly with a public-key algorithm. Third, the equality check digest′ ≟ digest is the linchpin: any alteration to m during transit produces a different digest′, causing verification to fail.

SECTION 4

Mathematical Framework

A digital signature scheme is formally defined as a triple of probabilistic polynomial-time algorithms (KeyGen, Sign, Verify). We will use RSA signatures as the canonical example because its mathematics is the most transparent, though the conceptual structure generalizes to DSA, ECDSA, and post-quantum schemes.

KEY GENERATION

n = p × q, φ(n) = (p − 1)(q − 1), e × d ≡ 1 (mod φ(n))

Choose two large primes p and q. Compute modulus n and Euler's totient φ(n). Select public exponent e and compute private exponent d as the modular inverse. Public key = (e, n); private key = (d, n).

SIGNING

σ = H(m)^d mod n

The signer computes the hash digest H(m) of the message and raises it to the private exponent d modulo n. The result σ is the signature transmitted alongside the message.

VERIFICATION

σ^e mod n ≟ H(m′)

The verifier raises the received signature σ to the public exponent e modulo n to recover the original digest. If this equals H(m′), the signature is valid. This works because (H(m)^d)^e ≡ H(m)^de ≡ H(m) (mod n), by Euler's theorem.

HASH FUNCTION PROPERTIES

H: {0,1}* → {0,1}^k (e.g., k = 256 for SHA-256)

The hash function must satisfy three properties: pre-image resistance (given y, hard to find x s.t. H(x) = y), second pre-image resistance (given x₁, hard to find x₂ ≠ x₁ with same hash), and collision resistance (hard to find any pair with the same hash).

The security of RSA signatures rests on the RSA assumption: given n, e, and σ^e mod n, it is computationally infeasible to compute d (i.e., factor n) in polynomial time. If a hash-then-sign paradigm with a secure padding scheme (e.g., RSA-PSS) is used, existential unforgeability under chosen-message attack (EUF-CMA) is provably guaranteed under the RSA assumption.

SECTION 5

Signature Algorithm Classification

Multiple families of digital signature algorithms exist, each relying on a different mathematical hardness assumption. The choice of algorithm involves trade-offs among key size, signature size, computational cost, and resilience to quantum attacks. The following diagram organizes the major schemes by their underlying mathematical problem, and the table below provides a comparative summary.

Taxonomy of major digital signature algorithms. RSA relies on integer factorization; DSA, ECDSA, and EdDSA rely on variants of the discrete-logarithm problem; and Dilithium and FALCON are lattice-based post-quantum candidates.

Comparative overview of selected signature algorithms

Algorithm	Hardness Basis	Key Size (bits)	Signature Size	Quantum-Safe?
RSA-2048	Integer factorization	2048	256 bytes	No
ECDSA (P-256)	Elliptic-curve DLP	256	64 bytes	No
EdDSA (Ed25519)	Twisted-Edwards curve DLP	256	64 bytes	No
Dilithium-3	Module-LWE lattices	≈ 15,488	≈ 3,293 bytes	Yes

SECTION 6

Worked Example — Toy RSA Signature

To make the abstract machinery concrete, we will walk through a miniature RSA signature using intentionally small primes. In practice, key sizes of 2048 bits or more are required; here we use tiny values so every modular exponentiation can be verified by hand or with a pocket calculator.

Signing and Verifying a Message with Toy RSA

Step 1 — Key GenerationChoose primes p = 61 and q = 53. Compute n = 61 × 53 = 3233. Compute φ(n) = 60 × 52 = 3120. Choose public exponent e = 17 (coprime to 3120). Find d such that 17 × d ≡ 1 (mod 3120). Using the extended Euclidean algorithm, d = 2753.

Public key: (e = 17, n = 3233). Private key: (d = 2753, n = 3233).

Step 2 — Hash the MessageSuppose our message is the integer m = 65 (in practice, this would be the output of SHA-256 reduced mod n). For this toy example, we treat H(m) = 65 directly.

digest = 65

Step 3 — Sign the DigestCompute σ = 65²⁷⁵³ mod 3233. Using modular exponentiation (repeated squaring), this yields σ = 2790.

σ = 2790

Step 4 — TransmitAlice sends the pair (m = 65, σ = 2790) to Bob over an insecure channel. The message is not encrypted; only the signature accompanies it.

Step 5 — Verify the SignatureBob computes σ^e mod n = 2790¹⁷ mod 3233 = 65. Bob also computes H(m) = 65 from the received message. Since 65 = 65, the signature is valid.

Verification: PASS ✓ (recovered digest 65 matches computed digest 65)

⚠️ Tampering Detection

If an attacker modifies the message to m′ = 66 during transit, Bob would compute H(m′) = 66, but 2790¹⁷ mod 3233 still equals 65, not 66. The mismatch causes verification to fail, immediately revealing the tampering.

SECTION 7

Strengths, Limitations & Comparisons

Digital signatures are extraordinarily powerful, but they are not a silver bullet. Understanding both their capabilities and their limitations is essential for correctly applying them in system design. The table below contrasts digital signatures with Message Authentication Codes (MACs), a symmetric-key primitive that provides integrity and authentication but not non-repudiation.

Digital Signatures vs. MACs

Property	Digital Signatures	MACs (e.g., HMAC)
Key type	Asymmetric (public/private pair)	Symmetric (shared secret)
Authentication	Yes	Yes
Integrity	Yes	Yes
Non-repudiation	Yes	No
Key distribution	Public key can be freely shared; requires PKI or trust model	Shared key must be pre-established over secure channel
Performance	Slower (modular exponentiation or scalar multiplication)	Faster (symmetric-key operations)
Publicly verifiable?	Yes	No — only key holder can verify

Key Limitations

Private key compromise: If an attacker obtains the signer's private key, they can forge arbitrary signatures. Key storage (HSMs, secure enclaves) is critical.
Trust in public keys: A signature is only meaningful if the verifier trusts that the public key belongs to the claimed signer. This requires a Public Key Infrastructure (PKI) with Certificate Authorities, or a web-of-trust model.
Hash function vulnerability: If the hash function is broken (e.g., practical collision attacks on MD5 and SHA-1), an adversary can craft a second document with the same hash, rendering the signature transferable to a forged document.
No confidentiality: Digital signatures do not encrypt the message. Confidentiality requires a separate encryption layer (e.g., AES-GCM or hybrid encryption).

✦ KEY TAKEAWAY

Digital signatures occupy the same role in cyberspace that notarized signatures occupy in the physical world: they bind an identity to a document in a way that third parties can independently verify. However, just as a notary stamp is worthless if the notary's seal has been stolen, a digital signature is worthless if the private key is compromised or if the public key's binding to an identity is not trustworthy. The cryptographic math is necessary but not sufficient—operational security and infrastructure (PKI) complete the picture.

SECTION 8

Connection to Advanced Cryptographic Theory

The high-level signing–verification pipeline you have learned generalizes into a rich landscape of advanced constructions. Each addresses specific real-world requirements that basic signature schemes do not satisfy. The table below summarizes how each advanced topic extends or refines the foundational model.

Advanced Digital Signature Constructions

Concept	What It Adds	Use Case Example
Blind Signatures	Signer signs a message without seeing its content, preserving privacy.	Anonymous digital cash (e-voting, eCash).
Multi-Signatures	Multiple parties jointly produce a single compact signature on a shared message.	Multi-party cryptocurrency wallets (MuSig2 in Bitcoin).
Threshold Signatures	Any t-of-n keyholders can produce a valid signature; fewer than t cannot.	Distributed key management in cloud HSMs.
Ring Signatures	Proves the signer is a member of a group without revealing which member.	Privacy-preserving cryptocurrencies (Monero).
Post-Quantum Signatures	Security based on lattice or hash-based problems believed resistant to quantum algorithms (Shor's).	NIST PQC standards: ML-DSA (Dilithium), SLH-DSA (SPHINCS+).

Looking forward, the most pressing challenge is the quantum threat. Shor's algorithm, if run on a sufficiently large quantum computer, can factor integers and compute discrete logarithms in polynomial time, breaking RSA, DSA, and ECDSA entirely. NIST's post-quantum standardization effort (finalized in 2024) provides migration paths to lattice-based and hash-based schemes. Understanding today's classical digital signatures is prerequisite to grasping why the transition is necessary and how post-quantum schemes differ structurally while preserving the same sign–verify abstraction.

🔮 Harvest Now, Decrypt Later

Adversaries may record today's digitally signed traffic and store it until a quantum computer becomes available. While this primarily threatens encryption (confidentiality), it also means that any long-lived signed artifact (e.g., a 30-year software signing certificate) could have its key factored in the future, enabling signature forgeries retroactively. This motivates 'crypto-agility'—designing systems that can swap out signature algorithms without architectural overhaul.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

Explain why a Message Authentication Code (HMAC) cannot provide non-repudiation, whereas a digital signature can. What structural difference in key management accounts for this?

PROBLEM 2 — BASIC CALCULATION

Given the toy RSA parameters p = 11, q = 3 (so n = 33, φ(n) = 20), and public exponent e = 3, compute the private exponent d. Then sign the hash digest H(m) = 7 and verify the resulting signature.

PROBLEM 3 — INTERMEDIATE

Alice signs a 1 MB document using RSA-SHA256. She sends the document and the signature to Bob. During transit, a single byte in the middle of the document is flipped by a noisy channel. Describe step by step what happens when Bob runs the verification algorithm. At which specific step does failure manifest, and why is it computationally infeasible for an attacker to modify the document in a way that evades detection?

PROBLEM 4 — APPLIED

You are designing a software update system for IoT devices with limited CPU and memory. Each firmware image is ≈ 2 MB. You must ensure that devices only install authentic, untampered firmware from your company. Choose an appropriate digital signature scheme, explain your choice, and outline the verification steps the device performs before applying the update.

PROBLEM 5 — CRITICAL THINKING

Suppose a Certificate Authority (CA) issues a code-signing certificate to Alice using RSA-2048 with SHA-1 as the hash algorithm. An adversary finds a SHA-1 collision: two different executables that hash to the same SHA-1 digest. Analyze how this collision could be exploited to forge a valid signature on a malicious executable, and argue whether upgrading only the hash function (to SHA-256) is sufficient to restore security or whether additional measures are needed.

SUMMARY

Lesson Summary

A digital signature is produced by hashing a message with a cryptographic hash function (e.g., SHA-256) and then encrypting the resulting digest with the signer's private key. The recipient verifies the signature by decrypting it with the signer's public key and comparing the recovered digest against a freshly computed hash of the received message. This pipeline delivers three guarantees: authentication (proving the signer's identity), integrity (detecting any modification), and non-repudiation (preventing the signer from denying authorship).

Major algorithm families include RSA (based on integer factorization), ECDSA / EdDSA (based on the elliptic-curve discrete-logarithm problem), and emerging post-quantum lattice-based schemes such as Dilithium. While digital signatures ensure authenticity and integrity, they do not provide confidentiality—encryption must be layered separately. The system's overall trustworthiness depends not only on the cryptographic algorithm but also on operational factors: secure key storage, a trustworthy Public Key Infrastructure (PKI), and the ongoing strength of the chosen hash function against collision attacks.