Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
Degrees and Certificates

Explore all of Coursera

Browse
Search
For Enterprise
Log In
Join for Free

Digital Signatures

Loading...

Bitcoin and Cryptocurrency Technologies

Princeton University

4.7 (1,980 ratings) | 340K Students Enrolled

To really understand what is special about Bitcoin, we need to understand how it works at a technical level. We’ll address the important questions about Bitcoin, such as: How does Bitcoin work? What makes Bitcoin different? How secure are your Bitcoins? How anonymous are Bitcoin users? What determines the price of Bitcoins? Can cryptocurrencies be regulated? What might the future hold? After this course, you’ll know everything you need to be able to separate fact from fiction when reading claims about Bitcoin and other cryptocurrencies. You’ll have the conceptual foundations you need to engineer secure software that interacts with the Bitcoin network. And you’ll be able to integrate ideas from Bitcoin in your own projects. Course Lecturers: Arvind Narayanan, Princeton University All the features of this course are available for free. It does not offer a certificate upon completion.

Skills You'll Learn

Bitcoin Network, Blockchains, Cryptocurrency, Bitcoin

Reviews

4.7 (1,980 ratings)

5 stars
1,504 ratings
4 stars
375 ratings
3 stars
71 ratings
2 stars
20 ratings
1 star
10 ratings

LB

Jan 15, 2017

I find this course prepared very well. There are many perspectives and this course does not concentrate on the technology only. I find this course very helpful. The level is more then just beginner.

AG

Feb 08, 2017

Loved this course! It was very thorough. However I think assignments could have been made more clearer as it was often hard to figure out what needed to be done without checking discussion forums.

From the lesson

Introduction to Crypto and Cryptocurrencies

Learn about cryptographic building blocks ("primitives") and reason about their security. Work through how these primitives can be used to construct simple cryptocurrencies.

Cryptographic Hash Functions18:42

Hash Pointers and Data Structures8:59

Digital Signatures9:45

Public Keys as Identities5:33

A Simple Cryptocurrency14:04

Taught By

Arvind Narayanan
Associate Professor

Transcript

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.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates