How digital signatures work

Question

I understand how public/private key cryptography works, and I understand how one-way hashing algorithms work.

I have read through this explanation of how digital signatures work, but something still isn't clear to me. Can someone please help me understand how the receiver of a message that has been digitally signed can be sure that the message has come from the claimed sender, unaltered.

Here's my own breakdown of the explanation in the linked article, which assumes the receiver is using some sort of program ("the program") to receive the message, and verify the signature.

The SENDER of the message sends to the RECEIVER:

1. A PLAINTEXT copy of the original message

2. A digital signature which consists of an ENCRYPTED hash of the original document, encrypted using the signer's private key

3. A PLAINTEXT copy of the signer's public key

The RECEIVER receives the message, and verifies that it is unaltered and from the claimed sender by:

1. Using the PLAINTEXT public key received in the message, the receiver decrypts the hash. The receiver then re-hashes the original document, and ensures that both hashes match

2. The program also validates that the public key used in the signature belongs to the signer

What's going on in step 2, above? How does the receiver perform this verification step? I can follow everything up to this point, but based on what's been explained up to that point, it would very easy for someone to intercept the message being sent, rip out the signature, create a new hash, attach a new public key, and send it on its way. So at step 2 above, how can the RECEIVER be sure that the message they are looking at is both unaltered and from the intended sender? How do they "verify" it at that point in the process?

Thanks in advance.

Answer 1

The article is oversimplifying matters. In a real-world scenario, either…

1. The recipient already has a copy of the public key, or can retrieve a copy from a trusted source. Either way, they can confirm the key is correct by comparing it with the "known good" copy they already have. (This is roughly how PGP works.) Or…

2. The key has a signature attached to it, signed by a trusted central authority. (This is roughly how SSL/TLS works.)

Either way, your analysis is entirely correct -- attaching a signature and public key to a message doesn't confirm anything on its own.

Answer 2

The article misses an important step about how you can trust that a public key actually represents the party you think it does. This is the job of a Certificate Authority (CA) (such as VeriSign).

They have widely distributed and verifiable public keys which can be used to sign other keys that connect them to verified identities. In order for the system to work you need a trusted third party, which is what CAs are. A certificate will contain the sender's public key, but it will also have other information such as the CA identity, expiration date, and the CA's signature.

With that you can verify that you trust the CA (probably because you can connect it with root certificates on your computer), the certificate is current, and the public key of the sender have been vouched for.

Honestly, it's amazing that it works.

Answer 3

The other day I wrote an answer to a similar question that you may find helpful, with specific details about a simple RSA-based signature scheme.

The quick answer is that for any document hash, there only a very small number (sometimes, exactly one) of valid signatures among more possibilities than you can count on all the hands in the world (in unary, anyway). While the receiver can test whether a candidate signature is valid, using a known-good public key,* nobody but the sender can find a valid signature.

The sender, in contrast, has secret knowledge of the mathematical structure of the public key which enables them to efficiently compute a valid signature given a document.

For secure signature schemes, cryptographers demonstrate that if someone who doesn't have that secret knowledge had a method of forging a signature, then they could use their method of forging a signature as a subroutine in a program that recovers the secret knowledge. And in the cryptosystems we use, the problem of recovering the secret knowledge from the public key are conjectured to be hard because lots of smart people have tried to find efficient algorithms to solve them and failed—e.g., factoring products of large secret prime numbers, computing discrete logarithms, etc.

The use of a document hash prevents a clever forger from exploiting relations between structured documents and the mathematical structure of the public-key cryptosystem to forge signatures. For example, in a naive broken RSA-based signature scheme where a public key is a product $n = p\cdot q$ of two large secret primes $p$ and $q$, a ‘document’ is an integer $m$ with $0 \leq m < n$, and a ‘signature’ is an integer $s$ with $0 \leq s < n$ and $s^3 \equiv m \pmod n$, it is trivial for a forger to make signatures without knowing the secrets $p$ or $q$: e.g., $s = 0$ is a signature on the document $m = 0$, and $s = 3$ is a signature on the document $m = 9$.

Unfortunately, GlobalSign's marketing team promulgated a harmful misconception about public-key signatures, which is that they have something to do with ‘encrypting with the private key’ and ‘decrypting with the public key’. Only in naive broken RSA-based cryptosystems does this even resemble what's going on. Outside the modular exponentiation, or in any other settings for cryptosystems like elliptic curves, everything else is completely different in signature schemes versus encryption schemes.

---

_{* Of course, as the other commentators noted, the receiver's confidence in the authenticity of a signed document is only at most as high as the receiver's confidence in the authenticity of the public key they use to verify it.}