A signature must be verifiable and unforgeable, and the message authentication code of the last section is neither. Verifying it requires holding the very secret that was supposed to be unique to the signer.
Words you will meet
-
Digital signature digital signature Simple Signing a message with your private key, so anybody can check it was you. Precise Bob's signature of a document m is K_B^-(m), the document encrypted with his private key. Anyone can verify it by applying his public key. In practice the hash of the document is signed rather than the document itself. introduced in ch. 8 — open in glossary — K⁻(m), the message encrypted with the signer’s private key.
-
Nonrepudiation — the signer cannot later deny having signed.
-
Message digest — the hash that gets signed, instead of the whole document.
-
Certification authority certification authority Simple A trusted third party that vouches for whose public key is whose. Precise A CA validates an entity's identity and issues a certificate binding that identity to its public key, signing the certificate with the CA's own private key. X.509 and RFC 1422 define the certificate format. introduced in ch. 8 — open in glossary — a trusted third party that binds a public key to an identity.
-
Certificate — that binding, signed by the certification authority.
-
Public key infrastructure — the whole arrangement of authorities and certificates that makes signatures usable.
Why this matters
Section 8.2.2 ended with a loss. Public key encryption gave up sender identity, because anyone can encrypt to Bob using his published key.
Section 8.3.2 recovered some of it with a shared secret, but only some. A valid message authentication code proves the sender was somebody holding the key — and if a whole autonomous system shares one key, that is not saying much.
This section closes the gap, and then immediately opens a new one. A signature proves who signed — provided you know whose public key you are holding. The second half of the section is about the fact that you usually do not.
Signing with the wrong key on purpose
To sign a document m, Bob applies his private key: the signature is K⁻_B(m).
That looks backwards at first. In section 8.2.2 the private key was for decrypting. But encryption and decryption are only mathematical operations — exponentiation to the power e or d — and Bob’s goal here is not to hide the document. It is to mark it in a way that is verifiable and unforgeable.
Alice verifies by applying Bob’s public key. If K⁺_B(K⁻_B(m)) produces the
original document, then two things follow:
- Whoever signed it used the private key
K⁻_B. - The only person who could know
K⁻_Bis Bob, because knowing the public key is of no help in learning the private one.
The assumption inside that second point
It holds only if Bob has neither given his private key away nor had it stolen.
The whole apparatus of digital signatures rests on one person keeping one number secret. That is a smaller assumption than a shared key needs, but it is not no assumption.
Because K⁺_B(K⁻_B(m)) will not produce m′ if the document was altered to
m′, a signature also provides message integrity — the same property section
8.3.2 built separately.
Sign the fingerprint, not the document
Public key operations are expensive, so signing a long document by encrypting all of it is overkill.
Instead Bob hashes the message first and signs the hash: K⁻_B(H(m)). Since
H(m) is far smaller than m, the work drops sharply.
Bob computes K⁻(m) over the whole message. It is verifiable and unforgeable — and public key operations are expensive, so signing a long document this way is overkill.
The hash is not decoration. Without it Bob would have to run public key encryption over the entire message.
Read all steps as text
- The naive signature: encrypt the whole document — Bob computes K⁻(m) over the whole message. It is verifiable and unforgeable — and public key operations are expensive, so signing a long document this way is overkill.
- Hash first, then sign the hash — Bob puts the long message through a hash function and signs the fixed-length result: K⁻(H(m)). Since H(m) is far smaller than m, the effort drops sharply.
- Send the message in the clear, with the signature attached — The original message travels as cleartext. The signature travels beside it. Nothing here is confidential — signing is not encrypting.
- Alice computes two hashes and compares them — She applies Bob's public key to the signature, giving one hash. She applies the hash function to the cleartext message, giving another. If the two match, she knows both the author and that nothing was altered.
Alice’s check is one comparison that proves two things at once. She applies Bob’s public key to the signature, getting one hash. She applies the hash function to the cleartext message, getting another. If the two match, she knows both the author and that nothing was altered.
In plain words
Signing is not encrypting. The message travels in the clear, readable by anyone.
What the signature adds is a claim about where the message came from that nobody but Bob could have made. That claim stops being true the moment the message changes.
| Message authentication code§8.3.2 | Digital signature§8.3.3 | |
|---|---|---|
| How it is built | ||
| Encryption involved? | ||
| What must exist first | ||
| Unique to one person? | ||
| Can the sender later deny it? | ||
| Used by |
Cells marked ⓘ have a reason behind them — click to read it.
Both start with a message and produce something short that proves it. The differences underneath are what decide which protocol uses which. Click any cell.
The row that decides everything is the fourth. A message authentication code cannot be a signature, because Alice needs the key to verify it, and once she has the key it is no longer unique to Bob.
The row underneath is the reward for paying that cost: nonrepudiation. Alice can prove in court that Bob signed the document, because nobody else could have produced something his public key undoes.
The gap this opens: whose key is it?
Here is the pizza prank, and it is worth taking seriously because every cryptographic check in it passes.
Every cryptographic check Alice performs passes. That is what makes this failure worth studying.
Click any arrow to see what that message says and why it is sent.
The same four messages both times. In the first run Alice checks a signature and is completely satisfied; the pizza still goes to the wrong house. Switch scenarios to see what fixes it.
Read this diagram as text
- Trudy sends order + "I am Bob" + a public key + a signature to Alice — the pizza shop — undefined. Trudy sends Bob's home address and an order for a pizza. She includes her OWN public key, which Alice naturally assumes is Bob's, and a signature made with her own private key.
- Alice — the pizza shop sends verify the signature with the key supplied to Alice — the pizza shop. Alice applies the public key she was given to the signature. It verifies perfectly — because the key and the signature really do belong to one another. They just belong to Trudy.
- Alice — the pizza shop sends pepperoni and anchovies to Bob — undefined. Bob will be very surprised when the delivery arrives at his home. Alice did nothing wrong by the rules she was following.
Lifelines, left to right: Bob (host), Trudy (middlebox), Alice — the pizza shop (server), Certification authority (server).
Alice runs a pizza shop and accepts orders over the Internet. Trudy sends an order in Bob’s name, to Bob’s address. She includes her own public key, which Alice assumes is Bob’s, and a signature made with her own private key.
Alice applies the key she was given to the signature. It verifies perfectly, because the key and the signature genuinely belong together. They just belong to Trudy. Bob receives a pizza with pepperoni and anchovies.
What actually failed
Not the mathematics. The signature check did exactly what it promises: it confirmed that the message was signed by the holder of the private key matching the public key supplied.
The unexamined step is “the public key supplied”. Alice never had any reason to believe that key was Bob’s, and nothing in section 8.2 or 8.3 gives her one.
For public key cryptography to be useful at all, you must be able to verify that you hold the actual public key of the entity you want to talk to.
Certification authorities
Binding a public key to an entity is the job of a certification authority, and it has two roles.
First, it verifies that an entity is who it says it is. The book is blunt about what this is worth: there are no mandated procedures for how certification is done. If Trudy can walk into the Fly-by-Night authority, announce “I am Alice”, and receive certificates in Alice’s name, then keys certified by Fly-by-Night are worth nothing. You can trust an identity only as far as you trust the authority and its verification techniques.
Second, it creates a certificate binding that public key to that identity. The certificate holds the key and globally unique identifying information about its owner, such as a name or an IP (Internet Protocol) Internet Protocol The network-layer protocol that defines the datagram format and addressing every Internet device must use. introduced in ch. 1 address. The authority then signs the whole thing with its own private key.
Click any box to read what that part of the message is for.
Every field, as text
Click any field. Notice how much of it is about the issuer and the validity period rather than about the key itself.
Now the prank fails. Bob sends his CA-signed certificate along with his order. Alice uses the certification authority’s public key to check the certificate’s validity and extract Bob’s public key from it. Trudy has no certificate binding Bob’s name to her key, and cannot make one.
Switch the ladder above to the second scenario to watch that happen.
The regress, and where it stops
Notice what just happened. Alice could not trust a public key, so she checked a certificate — using another public key, the authority’s.
That key has to be trusted too, and the chain has to end somewhere. In practice it ends in a set of authority keys that arrive with your browser or operating system. Those are trusted because of where they came from, not because of a signature.
The book’s own phrase for this is worth keeping: what a tangled web of trust we spin.
Both the ITU (International Telecommunication Union) International Telecommunication Union The United Nations body that standardises telecommunications. Its X.509 recommendation defines the certificate format used across the Internet. introduced in ch. 8 and the IETF (Internet Engineering Task Force) Internet Engineering Task Force The body that develops Internet standards. introduced in ch. 1 have standardised this. ITU X.509 specifies an authentication service and a certificate syntax. RFC (Request For Comments) Request For Comments The name of an IETF standards document. There are currently nearly 9000 of them. introduced in ch. 1 1422 describes authority-based key management for secure Internet e-mail — compatible with X.509, and adding conventions for a key management architecture.
Public key certification is used by IPsec (IP Security) IP Security The network-layer security suite, most often used in tunnel mode to build VPNs. introduced in ch. 8 in section 8.7 and by TLS (Transport Layer Security) Transport Layer Security Encryption, integrity and authentication added above TCP, in the application layer. introduced in ch. 2 in section 8.6, so it will appear again twice before the chapter ends.
The mental model
A signature is the key pair used backwards: private to make, public to check. That asymmetry is what makes it unique to one person, which is exactly what a shared secret can never be.
Hashing first makes it affordable. Certification makes it meaningful.
And the certificate is not a cryptographic idea at all — it is an institutional one. The arithmetic proves that a key and a signature match. Only an authority, and your willingness to trust it, connects that key to a person.
Check yourself
Check yourself
0 of 7 answered1.Why can a message authentication code not serve as a digital signature?
2.Bob signs with his private key — the same key section 8.2.2 used for decryption. Why is that not a mistake?
3.Why does Bob sign H(m) rather than m?
4.predictIn the pizza prank, Alice applies the public key she was given to the signature she was given. What happens?
5.What does a certification authority actually add?
6.The book warns about the "Fly-by-Night" certification authority. What is the point of that warning?
7.Alice verifies Bob's certificate using the certification authority's public key. What has this solved, and what has it moved?
What to remember
-
A message authentication code cannot serve as a signature, because Alice must hold the shared key to verify it — and a key two people hold is not unique to either. Only a private key gives nonrepudiation.
-
Bob signs the hash, not the document. Public key operations are expensive, so the fixed-length fingerprint is what gets encrypted — and the signed message still travels entirely in the clear, because signing is not encrypting.
-
The pizza prank passes every cryptographic check. What fails is the unexamined assumption that the supplied public key belongs to whom it claims, and repairing that needs an institution rather than an algorithm.