Digital Signatures and PKI

Definition: Digital signatures provide message authenticity, integrity, and non-repudiation using asymmetric cryptography; Public Key Infrastructure (PKI) is the system of Certificate Authorities, certificates, and trust chains that binds public keys to verified identities.

How It Works

Signing: the sender hashes the message, then encrypts that hash with their private key. This encrypted hash is the signature, appended to or sent alongside the original message.
Verifying: the receiver decrypts the signature using the sender’s public key, recomputes the hash of the received message independently, and compares the two. A match proves the message came from the holder of the private key and wasn’t altered in transit.
Certificates: a public key alone doesn’t prove identity, anyone can generate a keypair and claim to be anyone. A certificate binds a public key to an identity (a domain name, an organization) and is itself signed by a Certificate Authority (CA), vouching for that binding.
Chain of trust: a leaf certificate (e.g. for example.com) is signed by an intermediate CA, which is signed by a root CA. Operating systems and browsers ship with a preinstalled list of trusted root CA certificates; verification walks the chain from the leaf up to a trusted root.
Revocation: if a private key is compromised, its certificate must be invalidated before expiry via a Certificate Revocation List (CRL) or the faster Online Certificate Status Protocol (OCSP), which clients check before trusting a certificate.

Under the Hood

Signature algorithms don’t encrypt the whole message, only its hash, because asymmetric operations are computationally expensive; hashing first (with SHA-256 or similar) keeps signing fast regardless of message size, and also means the signature has a fixed, small size.
RSA signatures use the same trapdoor math as RSA encryption, but with keys used in reverse: signing uses the private key where encryption would use the public key. ECDSA and the newer EdDSA (Ed25519) use elliptic curve math instead, producing much shorter keys and signatures at equivalent security levels, with Ed25519 additionally avoiding the weak-randomness pitfalls that have caused real-world ECDSA key recovery incidents.
A CA doesn’t just sign a public key blindly. Domain Validation (DV) checks control of the domain (e.g. via a DNS TXT record or HTTP challenge, the mechanism ACME/Let’s Encrypt automates); Organization Validation (OV) and Extended Validation (EV) additionally verify legal business identity through manual vetting.
X.509 is the standard certificate format: it encodes the subject’s public key, identity fields, validity period, issuer, and the issuer’s signature over all of it, all ASN.1-encoded.
TLS uses this machinery only during the handshake, to authenticate the server (and optionally the client) and to establish a shared symmetric session key; the bulk data transfer that follows uses fast symmetric encryption, not the signature scheme itself.

ECDSA Signing, Step by Step

ECDSA (Elliptic Curve Digital Signature Algorithm) signing over a curve with base point G and order n, for a private key d and message m:

Compute e = H(m), the hash of the message, truncated to the bit length of n if needed.
Generate a random (or, per RFC 6979, deterministically derived) nonce k in the range [1, n-1]. This nonce must never repeat for a given key, and must not be predictable.
Compute the elliptic curve point (x1, y1) = k × G (scalar multiplication of the base point by k).
Set r = x1 mod n. If r = 0, discard this k and restart from step 2.
Compute s = k⁻¹ × (e + r × d) mod n. If s = 0, restart from step 2.
The signature is the pair (r, s).

Verification, given the signer’s public key point Q = d × G:

Compute e = H(m) the same way.
Compute w = s⁻¹ mod n.
Compute u1 = e × w mod n and u2 = r × w mod n.
Compute the point (x1, y1) = u1 × G + u2 × Q.
The signature is valid if x1 mod n == r.

The critical failure mode is nonce reuse: if the same k is ever used to sign two different messages with the same key, subtracting the two signature equations cancels out the private key’s masking and lets an attacker solve directly for d, recovering the private key entirely from two public signatures. This is exactly what happened in the Sony PS3 firmware signing incident, where a fixed (non-random) k across multiple signatures let researchers recover Sony’s ECDSA signing key. EdDSA (Ed25519) exists specifically to make this failure mode structurally impossible by deriving k deterministically from the message and private key rather than requiring fresh randomness per signature.

Signing and Verification Flow

The sender never encrypts the whole message, only its hash. The receiver independently rehashes the received message and checks it against what the signature decrypts to:

Certificate Chain of Trust

Verifying example.com’s certificate means walking this chain until it terminates at a root the client’s trust store already holds:

Why It Matters

Prevents man-in-the-middle attacks: a forged certificate for a domain won’t validate against any trusted root, so a browser warns or blocks the connection instead of silently trusting an impostor.
Establishes non-repudiation: because only the private key holder could have produced a valid signature, they can’t credibly deny having signed the message, which matters for contracts, code releases, and financial transactions.
Prevents software and firmware tampering: package managers and OS updaters verify a signature before installing, so a compromised mirror or CDN can’t silently substitute malicious binaries.

Common Pitfalls

Disabling certificate validation in custom API clients (verify=False, curl -k, NODE_TLS_REJECT_UNAUTHORIZED=0) to work around an error instead of fixing the underlying trust chain issue
Letting certificates expire on production systems, causing outages that a monitoring alert on expiry date would have prevented
Treating DV certificates as proof of organizational legitimacy, when DV only proves control of the domain, not who runs it
Reusing the same keypair across multiple certificates or purposes, which widens the blast radius if the private key is ever compromised
Storing private keys unencrypted on disk, or checking them into source control, instead of using an HSM or a secrets manager

Comparison

	RSA	ECDSA	EdDSA (Ed25519)
Underlying math	Integer factorization	Elliptic curve discrete log	Elliptic curve (Edwards form)
Typical key size (128-bit security)	3072-bit	256-bit	256-bit
Signature size	Larger	Smaller	Smaller, fixed
Randomness requirement	Not per-signature	Per-signature nonce, catastrophic if reused/weak	Deterministic, avoids nonce-reuse failures
Performance	Slower	Faster	Fastest of the three
Nonce failure risk	N/A (no per-signature nonce)	High, reused/predictable `k` leaks the private key	None, nonce is deterministic by design
Adoption	Legacy-compatible, still widest support	Common in TLS, Bitcoin, government standards	Growing, used in SSH, Signal, newer TLS suites

Example

Browsers validating https://example.com walk the certificate chain from the site’s leaf certificate up through an intermediate to a trusted root like DigiCert or ISRG (Let’s Encrypt’s root), rejecting the connection if any link is invalid or expired. Code signing certificates from Apple and Microsoft let operating systems verify that an installer wasn’t modified after the developer signed it. openssl req -new -x509 -key private.pem -out cert.pem generates a self-signed certificate for testing, using exactly the same X.509 format a CA-issued certificate uses.

Real-World Case Study

Stuxnet, the worm discovered in 2010 that targeted industrial control systems, used device drivers signed with legitimate, stolen code-signing certificates from real hardware vendors (including Realtek and JMicron). Because Windows trusts kernel-mode drivers signed by a valid, trusted certificate without further prompting, the stolen signatures let Stuxnet’s malicious drivers load silently instead of triggering the security warnings an unsigned or self-signed driver would raise. The incident is a canonical example of PKI’s trust model being subverted not by breaking the cryptography, but by compromising the identity-vetting and key-custody side of the system: the signing keys themselves were exfiltrated from the vendors, not mathematically forged.

History

1976: Diffie and Hellman’s paper first proposed the concept of a digital signature as a consequence of public-key cryptography, before a practical signature algorithm existed.
1977–1978: RSA, published by Rivest, Shamir, and Adleman, became the first practical algorithm usable for both encryption and signing.
1990s: X.509 and the modern CA hierarchy model were standardized as the web needed a scalable way to authenticate servers over SSL, the predecessor to TLS.
2008: the DigiNotar and later Comodo CA breaches demonstrated that a single compromised CA can undermine trust across the entire web, driving development of Certificate Transparency logs.
2015: Let’s Encrypt launched with the ACME protocol, automating domain validation and making free, short-lived certificates the default for most of the web.
2015 onward: Certificate Transparency became mandatory in major browsers, requiring newly issued certificates to be logged publicly so misissuance can be detected quickly.

PKI Components

Certificate Authority (CA): the trusted entity that issues and signs certificates, forming the root of a chain of trust.
Registration Authority (RA): handles identity verification on behalf of a CA before issuance, separating vetting from signing in larger PKI deployments.
Certificate Revocation List (CRL): a periodically published list of serial numbers for revoked certificates, checked by clients before trusting a certificate.
OCSP (Online Certificate Status Protocol): a faster, real-time alternative to CRLs, letting a client ask “is this specific certificate still valid” without downloading an entire list.
Hardware Security Module (HSM): dedicated hardware that generates and stores private keys so they never exist in plaintext outside a tamper-resistant boundary, standard practice for root and intermediate CA keys.
Certificate Transparency (CT) log: an append-only public log of issued certificates, letting domain owners and researchers detect mis-issued or fraudulent certificates quickly.

FAQ

Does a digital signature encrypt the message? No, unless combined separately with encryption. A signature proves authenticity and integrity; it doesn’t hide the message content. Confidentiality requires encrypting the message as a separate step.

What actually happens when a certificate is “not trusted”? The chain from the leaf certificate up to a root couldn’t be validated, either because an intermediate is missing, the chain ends at a root not in the trust store, the certificate expired, or the domain name doesn’t match what the certificate was issued for.

Why do CAs matter if anyone can generate a keypair? Because a keypair alone proves nothing about identity. The CA’s signature is what turns “here is a public key” into “here is a public key verified to belong to example.com,” which is the actual trust being purchased.

Can a certificate be un-revoked? No. Revocation is one-way; a compromised or mis-issued certificate must be reissued from scratch with a new keypair, not restored.

Referenced by

Dig deeper

Spot an error in this note?