Digital signatures

Encryption guarantees confidentiality. Hashing guarantees integrity. But how can we prove who wrote a message?

The principle: the public key turned on its head

In RSA, we encrypt using the public key and decrypt using the private key. Signing does the opposite:

1. The sender calculates the hash of the document.
2. They encrypt this hash with their private key: this is the signature.
3. The recipient decrypts the signature using the sender’s public key.
4. They then calculate the hash of the document they have received.
5. If the two hashes match, the signature is valid.

What this proves

• Authenticity: only the holder of the private key could have produced this signature.
• Integrity: if the document had changed by even a single bit, the digital fingerprints would differ.
• Non-repudiation: the sender cannot deny it; only they possess the key.

What the signature does not do: it does not hide anything. The document remains readable by everyone. To ensure confidentiality, additional encryption is required.

Why sign the hash rather than the document

Two reasons:

• Speed. RSA is slow. Signing 256 bits is instantaneous; signing a 4 GB file would take an age.
• Size. The signature remains short, regardless of the document’s size.

Where you come across them every day

• HTTPS certificates: the padlock in your browser relies on a chain of signatures.
• Software updates, signed by their publisher — otherwise anyone could slip you a malicious one.
• The packages in your Linux distribution.

The weak link isn’t the maths; it’s the link between a public key and a real identity. That’s the whole role of certification authorities — and their main vulnerability.