In segment 1.3, we're going to talk about digital signatures. This is the second cryptographic primitive along with hash functions that we need as building blocks for the cryptocurrency discussion later on. So a digital signature is supposed to be just like a signature on paper only in digital form. And what that means is this, what we want from signatures is two things. First, that just like an ideal paper signature, only you can make your signature, but anyone who sees your signature can verify that it's valid. And then the second thing you want is that the signature is tied to a particular document. So that somebody can't take your signature and snip it off one document and glue it onto the bottom of another one because the signature is not just a signature. It signifies your agreement or endorsement of a particular document. Okay, so the question is how can we build this in a digital form using cryptography? So let's get into the nuts and bolts. Here's an API for digital signatures. There are three things, three operations that we need to be able to do. The first one is we need, in the beginning, to be able to generate keys, and so we have a generateKeys operation. And we tell it a keysize, how big in bits should the keys be? And this produced two keys, sk and pk. sk will be a secret signing key, this is information you keep secret that you use for making your signature. And pk is a public verification key that you're going to give to everybody and that anybody can use to verify your signature when they see it. The second operation is the sign operation. The sign operation, you take your secret signing key and you take some message that you wanna put your signature on. And it returns, sig which is a signature. It's just some string of bits that represent your signature. And then, the third operation is a verify, that takes something that claims to be a valid signature and verifies that it's correct. It takes the public key of the signer, it takes the message that the signature is supposedly on and it takes the supposed signature. And it just says yes or no, is this a valid signature? Okay, so these three operations, these three algorithms constitute a signature scheme. And I'll note that the first two can be randomized algorithms. The verification won't be. It will always be deterministic. And in fact if you think about it, generateKeys had better be randomized, because it ought to be generating different keys for different people. Okay, so the requirements for the signatures, at a slightly more technical level, are the following two requirements. First of all, that valid signatures will verify. If a signature is valid, that is, if I sign a message with sk, with my secret key, that if someone then later tries to valid that using my public key and the same message, that that will validate correctly. So this says that signatures are useful at all. But then the second thing you want is that it's impossible to forge signatures. That is, an adversary who knows your public key, who knows your verification key and gets to see signatures on some other messages, can't forge your signature on some message that he wants to forge it on. And in order to explain this property in more detail, it is normally formulated in terms of a game that we play with an adversary. So he game I'll depicted here with this diagram. So over here on the left is the challenger who is a TV judge and the challenger is going to test a claim by an attacker. The attacker claims that he can forge signatures. And we're going to test that claim and the judge will pass judgement on it. The attacker here, this guy, is actually Whit Diffie, who is one of the inventors of digital signatures, of the concept of digital signatures, and a distinguished cryptographer. So I thought I'd let him play the attacker role here. Okay, so the game works like this. The first thing we do is we use generate keys to generate a secret key, a secret sign in key, and a public verification key that match up. Now we give the secret key to the challenger, to the judge. And we give the public key to both parties, both to the challenger and the attacker. So the attacker only knows information that's public, he only knows the public key. And his mission is going to be to try to forge a message. The challenger knows the secret key, so he can make signatures. Right now, if you think about a real-life application, and a real-life attacker would be able to see valid signatures from their would-be victim on a number of different documents. And maybe the attacker could even manipulate the victim into signing innocuous-looking documents, if that's useful to the attacker. So in our game, we're going to allow the attacker to get signatures on some documents of his choice. And we see that in the diagram like this. The attacker's going to send over a message, m0, to the challenger. And the challenger's going to sign that message and send the signature back. The attacker can look at that, scratch his head a little bit, and send over another message, m1. The challenger will sign that. And we do that for as long as the attacker wants. The attacker can send over any sequence of messages he wants and get signatures on them. Once the attacker is satisfied that he's seen enough signatures, and we're gonna let him see only a plausible number. Then he's going to pick some message m that he wants to forge a signature on, and he's gonna try to forge a signature. And of course, there's a rule that says that this m, this message that he's trying to forge a signature on, isn't one of the messages that he's already seen. Cuz it would be really easy for him to send over a valid signature on m0, I mean we sent him a valid signature on m0 earlier. So he's going to pick some other message that he hasn't seen a signature for all ready. And he's going to send over what he claims is a signature on that message. Ant then the question is, can he succeed? So the challenger is going to run the verify algorithm, use the public verification key on that message, and the signature that the attacker provided, and is going to check whether it verifies. And if it does verify, if this returns true, then the attacker wins, the attacker has forged a message. And so this game is what we use to define what it means for a digital signature scheme to have the unforgeablility property. And if we want to get really precise, what we say is that the attacker's probability of winning this game is negligible, and that that's true no matter what algorithm the attacker is using. In other words, we're going to say that the signature scheme is unforgeable if, no matter what algorithm the attacker is using, the attacker has only a negligible chance of successfully forging a message. And if we have that property together with a much easier property that valid messages verify, then we have a digital signature scheme that is suitable. Okay, now, there's a bunch of practical things that we need to do to turn that algorithmic idea into a more practically implementable signature mechanism. For example, the algorithms that we talked about are randomized, at least some of them will be. And so we need a good source of randomness, and the importance of this really can't be underestimated. Band randomness will sink you, your algorithm will be insecure. And I'll just point out here that attacks on the source of randomness are a favorite trick of intelligence agencies. And those are the people who know what kinds of attacks are likely to be successful. In practice, there's a limit on the message size that you're able to sign because real schemes are going to operate on bit strings of limited length. And the fix to that is simply to use the hash of the message rather than the message itself. That way the message can be really big, but the hash will only be 256 bits. And because hash functions are collision free, it's safe to use the hash of the message as the input to the digital signature scheme rather than the message. And by the way a fun trick which we'll see used later is that you can sign a hash pointer. And if you sign a hash pointer then the signature covers or protects the whole structure, not just the hash pointer itself, but everything it points to and everything it points to. For example, if you were to sign the hash pointer that was at the end of a block chain, the result is that you would effectively be digitally signing the entire contents of that block chain. That's a useful trick that we'll see used later. Okay, now let's get into the nuts and bolts. Bitcoin uses a particular digital signature scheme that's called ECDSA. That's the Elliptic Curve Digital Signature Algorithm. And it's a US government standard. And we won't go into all the details of how ECDSA works. It relies on some extremely hairy math. And trust me, you don't want to see all the details of how that works, you can look it up if you're interested. So we'll skip that. One thing I'll note though, with ECDSA good randomness, I said this before but I'll say it again because it's really essential. Good randomness is especially essential with ECDSA. If you use bad randomness in generating keys or even in signing, you probably leaked your private key. It stands to reason that if you use bad randomness in generating a key that the key you generate is maybe not secure. But it's a quirk of ECDSA that even if you use bad randomness just in making a signature using your perfectly good key, that also will leak your private key and then it's game over. So we need to be especially careful about this in practice. This is a common mistake. So that completes the discussion of digital signatures as a cryptographic primitive. And in the next segment, we'll move on and talk about some applications of digital signatures that will turn out to be useful in building crypto-currencies.
