Bitcoin part 6: Digital Signatures

It is time to introduce the most important application of trapdoor one-way functions: Digital signatures. (Be sure to have read at least part 3 and part 5.)

Suppose you want to send me a message, but (1) I am very far away and (2) we have an enemy who wants to pretend to be you. How can I know that, say, an Email message apparently from you really is from you and not from our enemy?

Here is how. First, you create a trapdoor one-way function g(x) such that you know its private key. You publish g to the world, including me, one time. From then on, any time you want to send me a message, you encode it as a big number y, invert g to find x such that g(x)=y, and transmit both x and y to me.

Here, x is called a digital signature for the message y. I can verify (or authenticate) the message simply by computing g(x) and confirming that it equals y, because only you have the power to invert g.

Now, as with most of my examples, this cryptographic protocol has some flaws. (Have I mentioned this happens a lot when you invent your own protocols?) Can you spot any?

One problem is that our enemy can start with a signature and generate a message. Remember that g(x) is public; or at least, not explicitly secret. So the enemy can pick any signature x, calculate a message y=g(x), and send the pair to me. This will pass my authentication, appearing to be a legitimate message from you. Note that the adversary has no control over the message y (else he could invert the function), so the message will be effectively random… But if he tries enough values for x, he might eventually stumble across a y that looks vaguely meaningful. At the very least, he might confuse me into thinking you had gone crazy and starting babbling. (This is called an “existential forgery”.)

This protocol has another flaw that is far more dangerous. Suppose you are in the habit of signing messages produced by someone else. You know, like contracts. In part 4 — which you probably skipped — we saw the Rabin trapdoor one-way function where n is the product of two large primes. If you are willing to invert that function for people, and one of them is hostile, after a few rounds they will be able factor your n and thus learn your private key. (They can do this by using you yourself as a “clever technique” for extracting square roots modulo n; see part 4 if you want the details.) This is called a chosen-message attack, and many trapdoor one-way functions have some vulnerability to them.

Can we fix these flaws, using the tools we have already seen?

Yes, by adding one more ingredient to the mix: a cryptographic hash function f. The corrected protocol goes like this. We agree on a cryptographic hash f(x). You generate your personal trapdoor one-way function g(x) as before. To send a signed message m, you first compute y=f(m). Then you invert your g to find an x with g(x)=y. Finally, you send me m (the message) and x (the signature).

To authenticate the message, I check that g(x)=f(m).

Our adversary can still try starting from a signature x and computing g(x)… But at that point, he is stuck, because he cannot invert f. (He also cannot perform a chosen-message attack on g, even if you are signing his documents, because another way of saying “f is hard to invert” is to say “nobody can control the output of f“.)

By the way, it is important for f to be a cryptographic hash, not just a one-way function. Otherwise, the adversary might be able to construct two messages m and m' with f(m)=f(m'). Then when he asks you to sign m, he can later convince me that you really signed m'.

The corrected digital signature protocol above actually works. In fact, your Web browser uses precisely this protocol every time you connect to an https URL, like your bank (or self-evident.org). These digital signatures are how your browser knows it is connected to your bank and not somebody pretending to be your bank. Not that it helps in practice since everyone always clicks “Ignore” on security warnings.

Well, if you have made it this far, congratulations. We finally have enough tools in the kit to build Bitcoin, starting next time.

Leave a Reply