Lecture 30: What is a Digital Signature? The Math of Unforgeable Authenticity

Sequentia Explores: The Mathematics of Crypto

Part III: Historical Ciphers & the Dawn of Cryptanalysis

Lecture 30: What is a Digital Signature? The Math of Unforgeable Authenticity

In our journey through public-key cryptography, we’ve focused almost exclusively on solving the problem of Confidentiality. We’ve seen how systems like RSA and protocols like Diffie-Hellman allow Alice to send a secret message to Bob, or for them to agree on a secret key, without Eve being able to listen in.

But what about the other pillars of information security we discussed? What about Authenticity and Integrity? How can Bob be certain that the message he received actually came from Alice and wasn’t altered in transit by Mallory?

To solve this, we need a digital equivalent of a handwritten signature. But it needs to be far more powerful. A physical signature can be forged. A digital signature must be mathematically unforgeable.

Today, we’ll see how the same public-key systems we use for encryption can be cleverly “flipped” to create these powerful digital signatures.

Flipping the Script: Encrypt with Private, Decrypt with Public

Let’s revisit the core idea of RSA.

• For Encryption (Confidentiality): Anyone can use Alice’s Public Key to encrypt a message. Only Alice can use her Private Key to decrypt it.
  • Lock -> Public Key
  • Unlock -> Private Key

To create a signature, we reverse this flow.

• For Signing (Authenticity): Only Alice can use her Private Key to “sign” a message (a form of encryption). Anyone in the world can use her Public Key to “verify” the signature (a form of decryption).
  • Sign -> Private Key
  • Verify -> Public Key

This reversal is profound. Since Alice is the only person in the world who possesses her private key, any message that can be successfully “unlocked” or verified by her public key provides mathematical proof that it must have been signed by her. This is the foundation of unforgeable authenticity.

The Problem with Signing the Whole Message

Alice could, in theory, take her entire message, encrypt it with her private key, and send it. Bob could then decrypt it with her public key to verify it. However, this is incredibly inefficient for two reasons:

1. Speed: Asymmetric cryptography (like RSA) is computationally slow. Using it to encrypt a large document would take a long time.
2. Size: The encrypted message would be at least as large as the original document.

We need a more efficient way. Instead of signing the entire document, we sign a small, unique “fingerprint” of it.

Enter the Hash Function

This is where another one of our cryptographic tools comes into play: the cryptographic hash function (like SHA-256). As a quick reminder, a hash function takes any input data (of any size) and produces a fixed-size, unique output called a hash digest.

• It’s a one-way function: easy to compute the hash, impossible to reverse.
• It’s deterministic: the same input always produces the same hash.
• It’s collision-resistant: changing even one bit in the input drastically changes the hash.

This hash acts as the perfect, compact fingerprint for our message.

The Digital Signature Process: Step-by-Step

Let’s walk through how Alice signs a document and sends it to Bob.

Part 1: Signing (done by Alice)

1. Create the Message: Alice writes her message (e.g., a contract, an email, a transaction).
2. Hash the Message: She runs the entire message through a hash function (like SHA-256) to produce a short, fixed-size hash digest (e.g., a 256-bit number). This hash is the unique fingerprint of her message.
3. Encrypt the Hash with Her Private Key: Alice takes this hash digest and encrypts it using her RSA private key. This encrypted hash is the digital signature.
4. Send the Package: Alice sends Bob three things over the insecure channel:
   • The original message (the plaintext).
   • The digital signature (the encrypted hash).
   • A certificate identifying which public key to use (her public key).

Part 2: Verification (done by Bob)

Bob receives the message, the signature, and Alice’s public key. He now needs to verify that the message is authentic and has not been altered.

1. Separate the Components: Bob separates the plaintext message from the digital signature.
2. Hash the Received Message: Bob takes the plaintext message he received and runs it through the exact same hash function (SHA-256) that Alice used. This produces a hash digest, let’s call it Hash_B.
3. Decrypt the Signature with Alice’s Public Key: Bob takes the digital signature he received and decrypts it using Alice’s public key. Because of the “flipped” RSA logic, this decryption will work and will reveal the original hash digest that Alice encrypted. Let’s call this Hash_A.
4. Compare the Hashes: Bob now compares the two hashes he has:
   • Hash_B (the one he calculated himself from the message).
   • Hash_A (the one he recovered by decrypting the signature).

The Moment of Truth:

• If Hash_A is identical to Hash_B, the signature is VALID. This provides two powerful guarantees:
  • Authenticity: The signature could only have been created with Alice’s private key, so the message must be from her.
  • Integrity: The fact that the hashes match proves that the message has not been altered one single bit since Alice hashed it. If Mallory had changed the message in transit, Bob’s calculated Hash_B would be completely different, and the check would fail.
• If Hash_A is not identical to Hash_B, the signature is INVALID. This means either the message was tampered with, or it wasn’t signed by Alice in the first place.

The Bitcoin Connection

This exact mechanism is what secures transactions on the Bitcoin network. When you “send” bitcoin, you are not actually sending a file. You are creating a transaction message that says, “Move X amount of bitcoin from my address to this other address.” You then use your Bitcoin private key to create a digital signature for that specific transaction.

This signed transaction is broadcast to the network. Everyone on the network can use your corresponding public key (which is linked to your Bitcoin address) to verify that the signature is valid. This provides mathematical proof that the owner of the private key—and only that owner—authorized that specific transaction. It’s how the network achieves authenticity and integrity without a central authority.

Digital signatures are the final, brilliant application of our public-key toolkit. They don’t provide confidentiality, but they provide the unforgeable proof of origin and integrity that is the foundation of digital identity and trust.