1
00:00:04,525 --> 00:00:08,500
In Segment 1.3, we're going to
talk about digital signatures.

2
00:00:08,500 --> 00:00:13,480
This is the second cryptographic primitive
along with hash functions that we need

3
00:00:13,480 --> 00:00:17,270
as building blocks for
the crypto currency discussion later on.

4
00:00:17,270 --> 00:00:21,850
So a digital signature is supposed to
be just like a signature on paper,

5
00:00:21,850 --> 00:00:24,750
only in digital form and
what that means is this.

6
00:00:24,750 --> 00:00:27,540
What we want from
signatures is two things.

7
00:00:27,540 --> 00:00:31,864
First, that just like
an idealized paper signature,

8
00:00:31,864 --> 00:00:34,684
only you can make your signature but

9
00:00:34,684 --> 00:00:39,482
anyone who sees your signature
can verify that it's valid.

10
00:00:39,482 --> 00:00:42,312
And then, the second thing you
want is that the signature is

11
00:00:42,312 --> 00:00:43,848
tied to a particular document.

12
00:00:43,848 --> 00:00:47,960
So that somebody can't take your signature
and snip it off one document and glue it

13
00:00:47,960 --> 00:00:51,850
on to the bottom of another one because
the signature is not just a signature.

14
00:00:51,850 --> 00:00:57,190
It signifies your agreement or
endorsement of a particular document.

15
00:00:57,190 --> 00:01:00,730
So the question is, how can we build this
in a digital form using cryptography?

16
00:01:03,550 --> 00:01:04,970
So let's get in to the nuts and bolts.

17
00:01:04,970 --> 00:01:06,970
Here's an API for digital signatures.

18
00:01:08,020 --> 00:01:12,080
There are three things, three operations
that we need to be able to do.

19
00:01:12,080 --> 00:01:15,650
The first one is we need in the beginning
to be able to generate keys.

20
00:01:15,650 --> 00:01:19,110
And so we have a generate keys
operation and we tell it the key size.

21
00:01:19,110 --> 00:01:21,080
How big in bits should the keys be?

22
00:01:21,080 --> 00:01:24,620
And this produces two keys, sk and pk.

23
00:01:24,620 --> 00:01:26,750
Sk will be a secret signing key.

24
00:01:26,750 --> 00:01:30,980
This is information you keep secret,
that you use for making your signature.

25
00:01:30,980 --> 00:01:35,080
And pk is a public verification key that
you're going to give to everybody, and

26
00:01:35,080 --> 00:01:37,996
that anybody can use to verify
your signature when they see it.

27
00:01:39,850 --> 00:01:43,290
The second operation
is the sign operation.

28
00:01:43,290 --> 00:01:47,400
The sign operation you take your secret
signing key and you take some message that

29
00:01:47,400 --> 00:01:51,740
you want to put your signature on and
it returns sig, which is a signature.

30
00:01:51,740 --> 00:01:55,100
It's just some string of bits
that represents your signature.

31
00:01:55,100 --> 00:01:59,500
And then the third operation is
a verify that takes something that

32
00:01:59,500 --> 00:02:02,790
claims to be a valid signature and
verifies that is correct.

33
00:02:02,790 --> 00:02:05,870
It takes the public key of the signer.

34
00:02:05,870 --> 00:02:09,500
It takes the message that
the signature is supposedly on and

35
00:02:09,500 --> 00:02:11,510
it takes the supposed signature.

36
00:02:11,510 --> 00:02:13,760
And it just says yes or no,
is this a valid signature?

37
00:02:15,250 --> 00:02:20,030
So these three operations, these three
algorithms constitute a signature scheme.

38
00:02:20,030 --> 00:02:23,500
And I'll note that the first two
can be randomized algorithms.

39
00:02:23,500 --> 00:02:26,010
The verification won't be,
it will always be deterministic.

40
00:02:26,010 --> 00:02:29,410
And in fact, if you think about it
generate keys had better be randomized

41
00:02:29,410 --> 00:02:31,900
because it ought to be generating
different keys for different people.

42
00:02:34,360 --> 00:02:37,280
So the requirements for the signatures and

43
00:02:37,280 --> 00:02:40,350
on a slightly more technical level
are the following two requirements.

44
00:02:40,350 --> 00:02:44,388
First of all,
that valid signatures we'll verify.

45
00:02:44,388 --> 00:02:49,690
If a signature is valid, that is if I sign
a message with sk, with my secret key,

46
00:02:49,690 --> 00:02:54,440
that if someone then later tries to
validate that using my public key and

47
00:02:54,440 --> 00:02:58,870
the same message that,
that will validate correctly.

48
00:02:58,870 --> 00:03:02,291
So this says,
that signatures are useful at all.

49
00:03:02,291 --> 00:03:06,123
But then the second thing you want, is
that it's impossible to forge signatures.

50
00:03:06,123 --> 00:03:12,126
That is an adversary who knows your public
key, who knows your verification key,

51
00:03:12,126 --> 00:03:15,867
and gets to see signatures
on some other messages,

52
00:03:15,867 --> 00:03:21,190
can't forge your signature on some
message that he wants to forge it on.

53
00:03:21,190 --> 00:03:24,100
In order to explain this property
in a little bit more detail, it's

54
00:03:24,100 --> 00:03:28,940
normally formulated in terms of assorted
game that we play with an adversary.

55
00:03:28,940 --> 00:03:31,830
So the game,
I'll depict it here with this diagram.

56
00:03:31,830 --> 00:03:35,420
So over here on the left you have
the challenger who's a TV judge, and

57
00:03:35,420 --> 00:03:40,360
the challenger is going to
test a claim by an attack.

58
00:03:40,360 --> 00:03:43,830
The attacker claims that he
can forge signatures, and

59
00:03:43,830 --> 00:03:47,020
we're going to test that claim and
the judge will pass judgement on it.

60
00:03:47,020 --> 00:03:50,410
The attacker here,
this guy is actually Whit Diffie, who is

61
00:03:50,410 --> 00:03:54,760
one of the inventors of digital signatures
of the concept of digital signatures, and

62
00:03:54,760 --> 00:03:56,060
a distinguished cryptographer.

63
00:03:56,060 --> 00:03:57,920
So I thought I'd let him
play the attacker role here.

64
00:03:59,400 --> 00:04:01,210
So the game works like this.

65
00:04:01,210 --> 00:04:05,540
The first thing we do is we use
generate keys to generate a secret key,

66
00:04:05,540 --> 00:04:08,360
a secret sign in key, and
a public verification key that match up.

67
00:04:09,990 --> 00:04:13,220
Now, we give the secret key to
the challenger, to the judge, and

68
00:04:13,220 --> 00:04:15,880
we give the public key to both parties.

69
00:04:15,880 --> 00:04:17,750
Both to the challenger and
to the attacker.

70
00:04:17,750 --> 00:04:20,090
So the attacker only knows
information that's public,

71
00:04:20,090 --> 00:04:21,830
he only knows the public key.

72
00:04:21,830 --> 00:04:24,500
And his mission is going to
be to try to forge a message.

73
00:04:24,500 --> 00:04:28,685
The challenger knows the secret key,
so he can make signatures.

74
00:04:28,685 --> 00:04:31,476
Now, if you think about
a real life application, and

75
00:04:31,476 --> 00:04:35,446
a real life attacker would be able to
see valid signatures from there would be

76
00:04:35,446 --> 00:04:38,120
victim on a number of different documents.

77
00:04:38,120 --> 00:04:41,820
And maybe the attacker could even
manipulate the victim into signing

78
00:04:41,820 --> 00:04:45,430
innocuous looking documents,
if that's useful to the attacker.

79
00:04:45,430 --> 00:04:49,410
So in our game,
we're going to allow the attacker to

80
00:04:49,410 --> 00:04:52,670
get signatures on some
documents of his choice.

81
00:04:52,670 --> 00:04:54,710
And we see that in the diagram, like this.

82
00:04:54,710 --> 00:04:59,060
The attacker's going to send over
a message m0 to the challenger.

83
00:04:59,060 --> 00:05:03,000
And the challenger is going to sign that
message and send the signature back.

84
00:05:03,000 --> 00:05:05,350
The attacker can look at that
scratch his head a little bit and

85
00:05:05,350 --> 00:05:09,150
send over another message and
one the challenger will sign that.

86
00:05:09,150 --> 00:05:11,120
And we do that for
as long as the attacker wants.

87
00:05:11,120 --> 00:05:14,290
The attacker can send over any
sequence of messages he wants and

88
00:05:14,290 --> 00:05:15,359
get signatures on them.

89
00:05:17,110 --> 00:05:20,430
Once the attacker is satisfied that
he's seen enough signatures, and

90
00:05:20,430 --> 00:05:24,330
we're going to let him see
only a plausible number

91
00:05:24,330 --> 00:05:29,510
then he's going to pick some message M
that he wants to forge his signature on.

92
00:05:29,510 --> 00:05:31,160
And he's going to try
to forge his signature.

93
00:05:31,160 --> 00:05:35,050
And of course, there's a rule that says
that this M, this message that he's trying

94
00:05:35,050 --> 00:05:40,155
to forge his signature on isn't one of
the messages that he's already seen.

95
00:05:40,155 --> 00:05:44,320
because it would be really easy for
him to send over a valid signature on m0,

96
00:05:44,320 --> 00:05:47,060
we sent him a valid
signature on m0earlier.

97
00:05:47,060 --> 00:05:50,150
So he's going to pick some other message
that he hasn't seen a signature for

98
00:05:50,150 --> 00:05:55,370
already, and he's going to send over what
he claims is a signature on that message.

99
00:05:55,370 --> 00:05:57,310
And the question is can he succeed?

100
00:05:57,310 --> 00:06:00,210
So the challenger is going
to run the verify algorithm,

101
00:06:00,210 --> 00:06:05,520
use the public verification key,
and on that message and

102
00:06:05,520 --> 00:06:09,270
the signature that the attacker provided,
and is going to check whether it verifies.

103
00:06:09,270 --> 00:06:12,600
And if it does verify, if this
returns true then the attacker wins.

104
00:06:12,600 --> 00:06:14,949
The attacker has forged a message.

105
00:06:16,420 --> 00:06:20,450
And so this game is what we use
to define what it means for

106
00:06:20,450 --> 00:06:23,900
a digital signature scheme to
have the unforgeability property.

107
00:06:23,900 --> 00:06:26,630
And if we want to get
really precise what we say,

108
00:06:26,630 --> 00:06:31,100
is that the attackers probability of
winning this game is negligible and

109
00:06:31,100 --> 00:06:34,140
that's true no matter what
algorithm the attacker is using.

110
00:06:34,140 --> 00:06:37,700
In other words, we're going to say that
the signature scheme is unforgeable,

111
00:06:37,700 --> 00:06:41,040
if no matter what algorithm
the attacker is using

112
00:06:41,040 --> 00:06:45,850
the attacker has only a negligible chance
of successfully forging the message.

113
00:06:45,850 --> 00:06:51,016
And if we have that property together
with the much easier property that valid

114
00:06:51,016 --> 00:06:56,026
messages verify then we have a digital
signature scheme that is suitable.

115
00:06:56,026 --> 00:07:00,030
Now, there's a bunch of practical
things that we need to do to turn that

116
00:07:00,030 --> 00:07:05,000
algorithmic idea into a more practically
implementable signature mechanism.

117
00:07:05,000 --> 00:07:05,624
For example,

118
00:07:05,624 --> 00:07:08,851
the algorithms we talk about are
randomized at least some of them will be.

119
00:07:08,851 --> 00:07:11,370
And so
we need a good source of randomness.

120
00:07:11,370 --> 00:07:14,900
And the importance of this
really can't be underestimated.

121
00:07:14,900 --> 00:07:18,070
Band randomness will sink you,
your algorithm will be insecure.

122
00:07:18,070 --> 00:07:21,213
And I'll just point out here that
attacks on the source of randomness

123
00:07:21,213 --> 00:07:23,597
are a favorite trick of
intelligence agencies, and

124
00:07:23,597 --> 00:07:28,190
those are the people who know what kinds
of attacks are likely to be successful.

125
00:07:28,190 --> 00:07:31,990
In practice, there's a limit on
the message size that you're able to sign

126
00:07:31,990 --> 00:07:36,200
because real schemes are going to operate
on bit strings of limited length.

127
00:07:36,200 --> 00:07:39,110
The fix to that is simply to
use the hash of the message

128
00:07:39,110 --> 00:07:40,730
rather than the message itself.

129
00:07:40,730 --> 00:07:44,630
That way the message can be really big but
the hash will be only 256 bits.

130
00:07:45,660 --> 00:07:50,110
And because hash functions are collision
free, it's safe to use the hash of

131
00:07:50,110 --> 00:07:54,300
the message as the input to the digital
signature scheme rather than the message.

132
00:07:54,300 --> 00:07:55,028
And by the way,

133
00:07:55,028 --> 00:07:58,118
a fun trick which we'll see used
later is that you can sign a hash.

134
00:07:58,118 --> 00:08:00,787
And if you sign a hash pointer
then the signature covers or

135
00:08:00,787 --> 00:08:03,958
protects the whole structure,
not just the hash pointer itself but

136
00:08:03,958 --> 00:08:06,890
everything it points to and
everything it points to.

137
00:08:06,890 --> 00:08:10,870
For example, if you were to sign
the hash pointer that was at

138
00:08:10,870 --> 00:08:15,420
the end of a block chain, the result
is that you would effectively be

139
00:08:15,420 --> 00:08:18,850
digitally signing the entire
contents of that block chain.

140
00:08:18,850 --> 00:08:20,580
That's a useful trick that
we'll see used later.

141
00:08:22,390 --> 00:08:24,340
Now, let's get into the nuts and bolts.

142
00:08:24,340 --> 00:08:28,980
Bitcoin uses a particular digital
signature scheme that's called ECDSA.

143
00:08:28,980 --> 00:08:32,110
That's the Elliptic Curve
Digital Signature Algorithm and

144
00:08:32,110 --> 00:08:34,380
it's a US government standard.

145
00:08:34,380 --> 00:08:38,670
And we won't go into all
the details of how ECDSA works.

146
00:08:38,670 --> 00:08:41,190
It relies on some extremely hairy math.

147
00:08:41,190 --> 00:08:44,800
And trust me, you don't want to see
all the details of how that works.

148
00:08:44,800 --> 00:08:47,530
You can look it up if you're interested.

149
00:08:47,530 --> 00:08:48,910
So let's skip that.

150
00:08:48,910 --> 00:08:53,120
One thing I'll note though, with ECDSA
good randomness, I said this before but

151
00:08:53,120 --> 00:08:55,360
I'll say it again,
because it's really essential.

152
00:08:55,360 --> 00:08:59,260
Good randomness is especially
essential with ECDSA.

153
00:08:59,260 --> 00:09:03,020
If you use bad randomness in
generating keys or even in signing.

154
00:09:03,020 --> 00:09:05,270
You probably leaked your private key.

155
00:09:05,270 --> 00:09:08,560
It stands to reason that if you use
bad randomness in generating a key,

156
00:09:08,560 --> 00:09:11,620
that the key that you
generate is maybe not secure.

157
00:09:11,620 --> 00:09:16,180
But it's a quirk of ECDSA that even if
you use bad randomness just in making

158
00:09:16,180 --> 00:09:20,600
a signature using your perfectly good key,
that also will leak your private key and

159
00:09:20,600 --> 00:09:21,720
then it's game over.

160
00:09:21,720 --> 00:09:24,090
So we need to be especially
careful about this in practice.

161
00:09:24,090 --> 00:09:26,130
This is a common mistake.

162
00:09:26,130 --> 00:09:28,930
So that completes the discussion
of digital signatures as

163
00:09:28,930 --> 00:09:30,570
a cryptographic primitive.

164
00:09:30,570 --> 00:09:34,155
And in the next segment we'll move on and
talk about some applications of

165
00:09:34,155 --> 00:09:38,292
digital signatures that will turn out to
be useful in building cryptocurrencies.