Public-key certificates and X.509

The four ways of distributing a public key and why certificates won out, how a certificate is created and verified, and what X.509 standardises about the certificate format itself.

Name the four public-key distribution schemes and state each one's main weakness.
Reproduce a certificate's creation and verification equations and explain what the timestamp is for.
State what X.509 defines and what it deliberately leaves unspecified.

15 min read

Intuition

Section §3 assumed A and B had already exchanged public keys reliably, without saying how. This page covers the actual options for that exchange, and why the industry standardised on one of them.

Mechanism

Virtually every proposal for distributing public keys falls into one of four schemes:

Public announcement. Any participant can send or broadcast their own public key, e.g. PGP users appending theirs to messages on public forums. Convenient, but anyone can forge such an announcement.
Publicly available directory. A trusted authority maintains a dynamic directory mapping names to public keys. More secure than a bare announcement, but if the authority’s private key is compromised, or its records tampered with, an adversary can hand out counterfeit keys and impersonate anyone.
Public-key authority. Tighter control over distribution, based on the Needham-Schroeder protocol: a user appeals to the authority for every other participant’s key. More secure again, but the authority becomes a bottleneck, since every contact requires appealing to it, and its directory is still open to tampering.
Public-key certificates. The best option: participants exchange keys directly, without contacting an authority for every lookup, while remaining as reliable as if they had gone through one. This is what X.509 standardises.

Mechanism

A certificate consists of a public key ( $PU$ ), an identifier of the key’s owner ( $ID$ ), with the whole block signed by a trusted third party, typically a Certificate Authority (CA): a government agency or financial institution the user community trusts. A user presents their public key to the authority in person, or by secure authenticated communication, and receives back a certificate. For A, that certificate is:

Formula

Certificate creation

C_A = E(PR_{auth}, [T \Vert ID_A \Vert PU_a])

$PR_{auth}$: the certificate authority's private key
$T$: a timestamp, used to judge whether the certificate is still valid
$ID_A, PU_a$: the holder's identifier and public key

Mechanism

Anyone who receives A’s certificate, whether A sent it directly or it was pulled from a directory, verifies it the same way:

Formula

Certificate verification

D(PU_{auth}, C_A) = (T \Vert ID_A \Vert PU_a)

$PU_{auth}$: the authority's public key, known to the verifier in advance

Success is the proof: only the authority holds PR_auth, so a certificate that decrypts cleanly under PU_auth genuinely came from that authority.

Exam detail

Two things routinely lost in a rushed answer: this is a binding, between $ID_A$ and $PU_a$ , not just a copy of the key, and the trust comes from the recipient already holding $PU_{auth}$ correctly, which just moves the original problem, “how do I trust a public key?”, one level up to trusting the authority’s key instead of every individual’s.

Mechanism

The timestamp $T$ is not decorative. Suppose A’s private key is stolen. A generates a new key pair and applies for a new certificate, but an adversary can still replay the old certificate to B. If B encrypts under that old, compromised public key, the adversary reads everything. The notes compare this directly to a stolen credit card: cancelling the card number does not retroactively protect anyone who has not yet heard it was cancelled. The timestamp works the same way an expiry date does: once a certificate is old enough, it is treated as expired regardless of whether anyone has explicitly revoked it.

Mechanism

X.509 is the standard that formalises all of this. A digital certificate is defined as a cryptographic binding between an identifier and a public key associated with that identifier, created by an issuer acting as a trusted third party, exactly the role Boyd’s theorem requires. X.509 is used in IP security, TLS and S/MIME, and is built on public-key cryptography and digital signatures, but the standard itself does not mandate any specific signature algorithm or hash function; those are chosen independently. A certificate is created by hashing the holder’s identifying information, their public key, and identifying information about the issuing CA, then signing that hash with the CA’s private key.

EXTRACTION DEFECT: Figures 5 (exchange of public-key certificates), 6 (the overall X.509 certificate-generation scheme) and 7 (an example X.509 version 3 certificate) did not survive extraction. The construction of a certificate is fully described above from the notes’ own text; the specific field-by-field layout an actual X.509 v3 certificate uses is not reconstructed here, since that layout is exactly what was in the missing figures.

Aside

One field the lecture does name outside the missing figures: every certificate carries a serial number, an integer unique within the issuing CA that unambiguously identifies that one certificate. It matters most on the next page, where revocation lists identify revoked certificates by exactly this number.

Recall

Four distribution schemes exist; certificates win because they need no live authority contact per lookup while staying as trustworthy as one.
A certificate binds an identifier to a public key: $C_A = E(PR_{auth}, [T \Vert ID_A \Vert PU_a])$ , verified with $D(PU_{auth}, C_A)$ .
The timestamp limits how long a certificate stays trusted if replayed after its private key is compromised.
X.509 standardises the certificate format and is signature-algorithm-agnostic; it does not dictate which algorithm signs the certificate.

Source

Week 7 Notes PDF