This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

Loading...

From the course by University of Maryland, College Park

Cryptography

441 ratings

This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

From the lesson

Week 6

Key Exchange and Public-Key Encryption

- Jonathan KatzProfessor, University of Maryland, and Director, Maryland Cybersecurity Center

Maryland Cybersecurity Center

[SOUND] In the last lectures, we've talked about key exchange and

shown the Diffie-Hellman key exchange protocol.

But in their seminal 1976 paper, Diffie and Hellman also introduced a number of

other primitives that could address the drawbacks of private-key cryptography.

And in particular, one thing they talked about was the public-key setting.

And this is in contrast to the private-key setting,

where two parties must share some secret information in advance.

In contrast, in the public-key setting, we have a party who generates a pair of keys.

A public key, that we'll denote by pk, and a private key that we'll denote by sk.

You can think of s as standing for secret.

The public key is supposed to be widely disseminated, so that anybody who wants to

communicate with this party is able to access that public key.

On the other hand, the private key is kept secret by the party who

generates these pair of keys, and the private key is shared with no one else.

In contrast to the private-key setting, here we have an asymmetry, which is

why the setting is sometimes referred to as the setting of asymmetric cryptography.

And the asymmetry is in the keys used by various entities.

The private key that was generated by this party is used only by that party.

In contrast, the public key that was generated by this

party is used by everyone else.

And that's why it's widely disseminated in the first place.

Now let me just talk a little bit about how the Public-key might be

distributed in practice.

There are really two ways that this could be done.

So the first is where you have a user who generates their private and

public-key pair, pk, sk.

And then, what they can do,

is to simply put their Public-key into some public repository.

You can think about this as a public database.

Maybe it's some other mechanism for publicly announcing the fact that

you've generated a Public-key, and indicating what it is.

At any later point in time, any party who wishes to communicate with

the first party, the one who generated this public/private-key pair

can look in the public repository and get a copy of that user's Public-key.

They can then use that Public-key to communicate with that party.

In the second canonical way of distributing public keys,

we imagine just a different ordering of events.

So now, we have two parties who know they want to communicate with each other.

And at that point in time, one of the parties,

say the one on the right, can generate a public/private-key pair and

simply send their public-key directly to the other party.

This party can now, just like before, use that public-key for

any subsequent communication.

Notice that in both settings, the public-key might potentially be

available to anyone, in particular an attacker looking to,

violate the security of the communication between these two users.

In the former case the public-key was available in a public repository.

There's no reason to assume an attacker wouldn't be able to get access to

that repository as well.

Here the public-key is being sent over an open channel from one party to the other.

The parties don't share any prior information or prior secrets in advance.

And so there's no way for

them to set up a secure channel by which to transmit that public-key.

And so if an attacker were eavesdropping on the channel between those users at

this point in time, they would get access to the public-key as well.

Now, one thing that was implicit in both of the prior figures,

was the assumption that anybody who wanted to

obtain an authentic copy of another party's public-key would be able to do so.

So in the first picture where we had the public repository, the implicit assumption

was, that the public repository is not being messed with by an attacker nor

were the channels between either of the parties to

the public repository being intercepted or interfered with by an attacker.

In the second example, we were assuming that one party was able to

send their public-key to the other party over an open channel.

And although an attacker might have been able to eavesdrop on that channel,

we did assume implicitly that an attacker was not able to interfere with or

modify the contents of the data going across that channel.

So this means, roughly speaking, that we're treating the attacker

as being passive, at least during the key distribution phase.

Now, you might question this assumption, and

you might ask why we're not worried about a stronger attacker, who might try to

actively interfere between the channels that exist among these various parties.

And in fact, we do need to worry about that.

We're going to revisit our assumption about secure distribution of keys, but

we're going to have to wait until the next week's lectures in order to do that.

So for now we're simply going to assume that any party who wants to

obtain an authentic copy of another party's public-key is able to do so.

Now in the public-key setting we have two primitives, corresponding to

counterparts in the private-key setting achieving the same security goals.

So our canonical security goals for secure communication are secrecy and integrity.

And we've seen already how in the private-key setting,

Secrecy can be obtained using Private-key encryption, and

Integrity can be obtained using Message authentication codes.

In the Public-key setting, the analogous primitives are Public-key encryption for

Secrecy, and what are called Digital signature schemes for Integrity.

We're going to talk about Public-key encryption for the remainder of this week.

And we'll turn to a consideration of digital signature schemes in

the following week.

Now let's see briefly how public-key cryptography can be used

to address the various drawbacks of private-key cryptography that we

spoke about in a previous lecture.

So the first drawback of private-key cryptography that we talked about

was the key distribution problem, namely how did two parties go about

sharing a secure generating it and sharing a key in the first place?

And public-key cryptography addresses this because it allows for

the public keys to be distributed over public channels.

Now, it's true that we are assuming that those channels are authenticated, or

equivalently, that the attacker is passive during the key distribution phase.

But nevertheless, this is still a weaker assumption than was required in

the context of private-key cryptography, where there we required the channel over

which the key was shared to be both authenticated and private.

At least in the public-key setting we can get rid of the requirement for

secrecy of the channel.

The second drawback of private-key crypto was the key management problem.

That is managing and storing these keys in large systems of users where,

where each user might want to pairwise communicate.

And if we use public-key cryptography to address this scenario,

then what we see is that it will suffice for

every party to just generate their own pair of public and private-keys.

And then every other user only needs to know the public keys of

all other parties in order to communicate securely with each of them.

What that means then is that every user in this system is going to

be storing one private-key secretly, right?

It has to be storing that private key in a location of memory that's not

accessible to anybody else.

But then only these to store N minus 1 public keys corresponding to

the other parties.

Now this may look the same as what we had in the private-key setting,

where users were sha, were each storing N minus 1 shared secret keys.

But the point is that it's much easier to store N

minus one keys non-secretly than to store N minus 1 secret keys.

And in particular the storage of those N minus one public keys could be

outsourced to some public directory or

public repository, as we've been talking about so far.

Or even if the user was storing that key locally, it would be much easier for them

to store a key that, where they wouldn't have to worry about secrecy of that key.

And in addition, there are only N keys overall in the system, N private-keys and

N public-keys.

And so if for whatever reason there were some manager who was required, required to

have all keys in the system, they would only have to keep track of N keys overall.

The final drawback of pub, of private-key cryptography that we mentioned,

was its inaclipability, inapplicability in open systems.

And you can see how public-key cryptography circumvents that,

because in the public key world, even parties who have no prior relationship,

are able to find each other's public keys and use those to communicate.

And that's especially true if we assume the model where there is

a public repository of public keys, and that's true also in practice,

as we'll see at the end of next week, that is that parties are able to get

public keys of other people with whom they wish to communicate.

So, given that public-key cryptography addresses all the drawbacks of private-key

cryptography, why did we bother studying private-key cryptography at all?

Well, there are a couple of reasons for this.

So, first of all private-key cryptography is more naturally suitable for

certain applications.

And disk encryption is perhaps the canonical application,

where you really do have the ability to share the key.

Of course, you're sharing it with yourself over time,

as we talked about back in week one or so.

And also, you'd want to it, it just more naturally lends itself to the private-key

world because you only have, again, one party communicating with itself.

Moreover, public-key cryptography is about two to

three orders of magnitude less efficient than private-key cryptography.

It depends a little bit on which systems you're comparing,

it depends on which efficiency measures you're looking at, but

roughly speaking it's about two to three orders of magnitude less efficient.

And what that means is that if you're in a setting where private-key cryptography is

an option, then you would prefer to rely on it.

You'd prefer to use private-key cryptography when possible rather than

public-key cryptography.

And indeed as we'll see later on this week, private-key cryptography,

cryptography is used even in the public-key setting for

efficiency considerations.

And so our study of private-key cryptography was certainly

not a waste of time.

In the next lecture,

we'll turn to a discussion of public-key encryption schemes,

the first of the cryptographic primitives that we'll talk about in this class.

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