Digital signatures: how a message proves who wrote it and that nobody changed it

You get a message that says "Pay Sam 10 dollars". Two things could be wrong with it. Somebody other than the sender might have written it, or somebody might have changed it on the way. A digital signature is a small number attached to a message that lets anyone check both things at once, without ever learning the sender's secret.

Two keys instead of one

Earlier we saw, in Diffie-Hellman, that strangers can build a shared secret in public. Signatures use a related idea called public-key cryptography: you make a pair of keys. The private key stays with you. The public key goes to everyone. The pair is built so that something done with the private key can be checked with the public key, but the public key can't be used to redo it.

Signing is that "something". Only the owner of the private key can produce a valid signature. Anyone holding the public key can verify it.

The recipe: hash, then lock

Signing a whole message directly would be slow, so the first step is to squeeze the message into a short fingerprint with a hash function (a recipe that turns any text into a fixed-size number, and gives a completely different number if even one character changes). Then the signer applies their private key to that fingerprint. The result is the signature.

To verify, the checker does two separate things: hash the message they received, and apply the public key to the signature. If the two numbers match, the message is untouched and it was signed by the matching private key.

A toy you can run

Real keys use numbers hundreds of digits long. To see the mechanism with your own eyes, here is RSA, one common signature scheme, with tiny numbers. This is for learning only: numbers this small can be broken in a blink, and real systems add padding rules this toy skips.

import hashlib
p, q = 61, 53
n = p * q                 # 3233, part of both keys
phi = (p - 1) * (q - 1)   # 3120
e = 17                    # public exponent
d = pow(e, -1, phi)       # 2753, the private key

def digest(msg):
    return int.from_bytes(hashlib.sha256(msg.encode()).digest(), "big") % n

def sign(msg):            # needs the private key d
    return pow(digest(msg), d, n)

def verify(msg, sig):     # needs only the public values e and n
    return pow(sig, e, n) == digest(msg)

s = sign("Pay Sam 10 dollars")
print(digest("Pay Sam 10 dollars"), s, verify("Pay Sam 10 dollars", s))
print(verify("Pay Sam 90 dollars", s))
print(verify("Pay Sam 10 dollars.", s))

Running it prints:

758 1848 True
False
False

The public key is the pair (e, n) = (17, 3233). The private key is d = 2753. pow(x, k, n) means "x multiplied by itself k times, keeping only the remainder after dividing by n". The signature 1848 is the fingerprint 758 raised to the private power; raising 1848 to the public power 17 brings 758 back.

Try it: forge a message

What a signature does not do

A signature does not hide the message. Anyone can still read it; encryption is a separate tool. It also only proves that the holder of a particular private key signed it. How you know that the public key really belongs to Sam is a different problem, and it's the one that HTTPS certificates solve: a trusted organisation signs a statement saying "this public key belongs to this website".

Where you meet this

Software updates are signed so your computer can reject a tampered download. Git can sign commits so others can see who made them. Websites present certificates so your browser can check it reached the right server. In each case the check is the same two-step: hash, then compare with what the public key reveals.

So what for your code

Never write your own signature scheme for real use. Use a well-reviewed library, keep private keys out of your code and out of Git, and remember that a failed verification means reject the message, no matter how reasonable it looks.