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 crypto currency 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 idealized 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
on to the bottom of another one because
the signature is not just a signature.
It signifies your agreement or
endorsement of a particular document.
So the question is, how can we build this
in a digital form using cryptography?
So let's get in to 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 generate keys
operation and we tell it the key size.
How big in bits should the keys be?
And this produces 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 want to put your signature on and
it returns sig, which is a signature.
It's just some string of bits
that represents your signature.
And then the third operation is
a verify that takes something that
claims to be a valid signature and
verifies that is 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?
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
generate keys had better be randomized
because it ought to be generating
different keys for different people.
So the requirements for the signatures and
on a slightly more technical level
are the following two requirements.
First of all,
that valid signatures we'll 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
validate 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.
In order to explain this property
in a little bit more detail, it's
normally formulated in terms of assorted
game that we play with an adversary.
So the game,
I'll depict it here with this diagram.
So over here on the left you have
the challenger who's a TV judge, and
the challenger is going to
test a claim by an attack.
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.
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
to 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.
Now, if you think about
a real life application, and
a real life attacker would be able to
see valid signatures from there 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 is 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 and
one 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 going to let him see
only a plausible number
then he's going to pick some message M
that he wants to forge his signature on.
And he's going to try
to forge his signature.
And of course, there's a rule that says
that this M, this message that he's trying
to forge his signature on isn't one of
the messages that he's already seen.
because it would be really easy for
him to send over a valid signature on m0,
we sent him a valid
signature on m0earlier.
So he's going to pick some other message
that he hasn't seen a signature for
already, and he's going to send over what
he claims is a signature on that message.
And the question is can he succeed?
So the challenger is going
to run the verify algorithm,
use the public verification key,
and 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 unforgeability property.
And if we want to get
really precise what we say,
is that the attackers probability of
winning this game is negligible and
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 the message.
And if we have that property together
with the much easier property that valid
messages verify then we have a digital
signature scheme that is suitable.
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 we talk 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.
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 be only 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.
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.
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 let's 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 that 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 cryptocurrencies.