Skip to content

✒️ 07-07: Digital Signatures

📌 What Problem Do Digital Signatures Solve?

You've now seen two separate tools:

Digital signatures solve integrity and authenticity too — but without requiring a shared secret at all. Instead, they flip RSA's usual roles: the private key signs, and the public key verifies.

This matters enormously in practice: HMAC only works between two parties who've already exchanged a key. Digital signatures let anyone in the world, using nothing but a widely published public key, verify that a message genuinely came from the claimed sender and wasn't altered — which is exactly the property you need for things like verifying a software update or a TLS certificate (Module 09), where the verifier and the signer have never directly communicated.

🔄 The Reverse of Encryption

Recall RSA's normal use for confidentiality:

Encrypt with recipient's PUBLIC key  -> only recipient's PRIVATE key can decrypt
(anyone can encrypt TO you; only you can read it)

Digital signatures use the same key pair, but for the opposite purpose:

Sign with your own PRIVATE key  -> anyone with your PUBLIC key can verify
(only you can produce it; everyone can check it's really yours)
Confidentiality (encryption) Authenticity (signing)
Who has the key that's used to "lock"? Anyone (public key) Only the owner (private key)
Who has the key that's used to "unlock"/check? Only the owner (private key) Anyone (public key)
Purpose Keep it secret Prove who made it

💡 Padlock analogy revisited: encryption is "anyone can lock the box, only I can open it." Signing is "only I can apply this special seal, but anyone can check the seal is really mine." Same padlock-and-key concept, opposite direction of use.

🧾 Why Signatures Combine Hashing + Asymmetric Crypto

You might assume "signing" just means running RSA's private-key operation directly over the entire message. In practice, that's inefficient (asymmetric operations are slow, see 07-04: Asymmetric Encryption (RSA)) and unnecessary for large messages. Instead, real digital signature schemes work in two steps:

Step 1: Hash the message
        digest = SHA-256(message)

Step 2: Sign the (small, fixed-size) hash with the private key
        signature = RSA_sign(digest, private_key)

The sender transmits the original message plus the signature. The verifier does the matching two steps in reverse:

Step 1: Hash the received message the same way
        digest_check = SHA-256(received_message)

Step 2: Use the sender's public key to "unlock" the signature
        digest_from_signature = RSA_verify(signature, public_key)

Step 3: Compare
        If digest_check == digest_from_signature -> valid signature
        If they differ                            -> reject (tampered or fake)

Why Hash First?

  • Efficiency: signing a fixed-size 256-bit hash is dramatically faster than running slow asymmetric math over an entire multi-gigabyte file.
  • Consistency: RSA signing mathematically operates on numbers of a specific size range; a hash's fixed output size fits that requirement regardless of the original message's length.
  • Security: because SHA-256 has the avalanche effect and is collision-resistant (07-06: Hashing & Message Integrity), any change to the message — even one bit — produces a completely different digest, which will fail verification.

💡 This is why you'll often hear signature schemes described as "sign the hash, not the message" — it's standard practice, not a shortcut.

🕵️ Worked Example (Conceptual)

Let's trace through a simplified example using the toy RSA keys from 07-04: Asymmetric Encryption (RSA) — public key (n=55, e=3), private key (n=55, d=27) — just to see the shape of the process (real signature schemes add padding and use vastly larger numbers, so treat this as illustrative, not production-accurate):

Alice wants to sign the number m = 9 (standing in for "hash of message")

Signing (Alice, using her PRIVATE key d=27):
    signature = m^d mod n = 9^27 mod 55 = 4

Alice sends: message (which hashes to 9) + signature (4)

Verification (Bob, using Alice's PUBLIC key e=3):
    recovered = signature^e mod n = 4^3 mod 55 = 64 mod 55 = 9

Bob independently hashes the received message and gets 9.
recovered (9) == independently computed hash (9)  -> signature is valid!

If an attacker had altered the message in transit, Bob's independently computed hash would no longer be 9 — it would be some unrelated number due to the avalanche effect — and it would not match the 9 recovered from the signature. The mismatch immediately reveals tampering.

💡 Notice the key difference from encryption: here, Alice used her private key to produce the signature, and Bob used Alice's public key to check it. Anyone with Alice's public key can perform this same check — no secret sharing required, and no prior relationship between Alice and Bob needed.

✅ What a Signature Actually Proves

It's important to be precise about what digital signatures guarantee — and what they don't:

Property Does a valid signature prove this?
Authenticity — the claimed sender really produced this ✅ Yes (assuming their private key wasn't stolen)
Integrity — the message wasn't altered after signing ✅ Yes (via the hash)
Non-repudiation — the sender can't credibly deny signing it ✅ Yes (only they had the private key)
Confidentiality — nobody else can read the message ❌ No — a signed message is not automatically encrypted

💥 A common beginner mistake is assuming "signed" implies "secret." It doesn't. Signing and encrypting are separate operations serving separate goals — a message can be signed only (publicly readable, but verifiably authentic), encrypted only (secret, but not provably from anyone in particular), or both (sign, then encrypt, for maximum protection).

💡 This entire signature mechanism — proving that a specific private-key holder vouches for a specific piece of data — is the foundation of digital certificates. In 07-08: Digital Certificates & PKI, you'll see how a trusted authority signs other people's public keys, which is exactly how your browser knows a website's public key is genuine before it even starts a TLS handshake.

📌 Key Takeaways

  • Digital signatures flip the usual asymmetric encryption roles: the private key signs, and the public key verifies — the opposite of encrypting-with-public/decrypting-with-private.
  • Signatures solve authenticity and integrity without requiring a pre-shared secret, unlike HMAC — anyone with the public key can verify, even strangers who've never communicated before.
  • Real signature schemes hash the message first, then sign the hash — this is faster than signing the whole message directly and works regardless of message size.
  • Verification recomputes the hash of the received message and compares it against the hash recovered from the signature; a mismatch means the message was altered or the signature is invalid.
  • The toy example (private key d=27, public key e=3, n=55) signs 9 to produce 4, and verification recovers 9 back from 4 using the public key — mirroring RSA encryption but in reverse.
  • A valid signature proves authenticity, integrity, and non-repudiation — but it does not provide confidentiality; signing does not equal encrypting.
  • Signing and encryption are independent operations that can be combined (sign-then-encrypt) when a message needs both secrecy and provable authenticity.
  • Digital signatures are the mechanism that makes digital certificates possible — a trusted authority signing someone else's public key is exactly how PKI establishes trust, covered next in 07-08: Digital Certificates & PKI.