Digital Signatures

A handwritten signature, but unforgeable

A signature on paper says “I wrote this”, but it is easy to copy and doesn’t stop someone changing the text above it. A digital signature does better. It is a number computed from the message and a secret key, so it:

It does not hide the message. For secrecy, encrypt as well.

Hash, then sign

With RSA, Alice has a private key d and a public key (e, n). Signing is RSA used “backwards”:

Alice:  h  = SHA-256(M)            fingerprint of the message
        s  = h^d mod n             sign with the PRIVATE key
        send (M, s)
Bob:    h' = SHA-256(M)            hash what he received
        v  = s^e mod n             open the signature with Alice's PUBLIC key
        valid  if and only if  v = h'

Why hash first? SHA-256 turns a message of any size into 256 bits, so one exponentiation signs a whole file. And because finding two messages with the same hash is infeasible, signing the hash is as good as signing the message.

Worked example

The model uses a toy key, p = 61 and q = 53, so n = 3233, e = 17 and d = 2753. Because n is tiny, the hash is reduced mod n first. Real keys have n of 2048 bits or more and sign the full hash with a padding scheme such as RSA-PSS.

What happens if Eve interferes?

• Tampering. Eve changes the text to “Pay Bob 900” and keeps s = 2331. Bob’s hash changes completely: h′ = 116. But the signature still opens to 2914, the hash of the original message. 2914 ≠ 116, so the signature is invalid.
• Forgery. Eve signs her own message with her private key. Bob checks with Alice’s public key, and it doesn’t match. Without Alice’s private key, Eve can’t make a signature that Alice’s public key accepts. That would require breaking RSA.

Where signatures are used

• HTTPS certificates. A certificate authority signs “this public key belongs to example.com”, and your browser checks it.
• Software updates and app stores. Your device installs only code signed by the developer.
• Email (S/MIME, PGP), PDF documents, Git commits and India’s e-Sign.
• Cryptocurrencies. Every transaction is signed. Bitcoin and Ethereum use ECDSA on elliptic curves rather than RSA.

Code

import hashlib

n, e, d = 3233, 17, 2753          # toy RSA key: n = 61 x 53

def h(message):
    """SHA-256 of the message, reduced mod n (real RSA signs the full padded hash)."""
    return int(hashlib.sha256(message.encode()).hexdigest(), 16) % n

def sign(message):
    return pow(h(message), d, n)          # uses the PRIVATE key d

def verify(message, s):
    return pow(s, e, n) == h(message)     # uses the PUBLIC key (e, n)

s = sign('Pay Bob 500')
print(s)                                  # 2331
print(verify('Pay Bob 500', s))           # True
print(verify('Pay Bob 900', s))           # False: the message was changed

Common mistakes

• Signing with the public key. You sign with your private key and verify with the public key. (Encryption is the other way round: encrypt with the receiver’s public key.)
• Thinking a signature hides the message. It proves origin and integrity, not secrecy.
• Signing without hashing (textbook RSA). Raw RSA signatures can be combined and forged. Always hash and pad.
• Trusting any public key. A signature only proves the signer owns that key. Certificates are what link keys to real identities.