Explore
For Enterprise
Join for Free
Log In

Гуманитарные науки и искусства
Бизнес
Компьютерные науки
Наука о данных
Информационные технологии
здоровье
Математика и логика
Личное развитие
Естественные и технические науки
Социальные науки
Изучение языков
Степени и сертификаты

Полный обзор Coursera

Обзор
Поиск
Для организаций
Войти
Присоединиться бесплатно

Public-Key Encryption

Loading...

Криптография I

Стэнфордский университет

4.8 (оценок: 2,624) | Зарегистрировано учащихся: 210K

Cryptography is an indispensable tool for protecting information in computer systems. In this course you will learn the inner workings of cryptographic systems and how to correctly use them in real-world applications. The course begins with a detailed discussion of how two parties who have a shared secret key can communicate securely when a powerful adversary eavesdrops and tampers with traffic. We will examine many deployed protocols and analyze mistakes in existing systems. The second half of the course discusses public-key techniques that let two parties generate a shared secret key. Throughout the course participants will be exposed to many exciting open problems in the field and work on fun (optional) programming projects. In a second course (Crypto II) we will cover more advanced cryptographic tasks such as zero-knowledge, privacy mechanisms, and other forms of encryption.

Просмотреть программу курса

Получаемые навыки

Cryptography, Cryptographic Attacks, Public-Key Cryptography, Symmetric-Key Algorithm

Рецензии

4.8 (оценок: 2,624)

5 stars
2,212 ratings
4 stars
352 ratings
3 stars
39 ratings
2 stars
13 ratings
1 star
8 ratings

DT

Jul 27, 2017

A really interesting and in-depth course. It is pretty challenging and requires good math/proof skills, but still quite fun. The course could use more study materials, for example lecture notes.

FP

Jul 15, 2017

Really interesting, provides the basic grounds for understanding a lot of discussions out there. Wikipedia can be useful as a reference, but here I was able to learn about semantic security etc.

Из урока

Basic Key Exchange

Week 5. This week's topic is basic key exchange: how to setup a secret key between two parties. For now we only consider protocols secure against eavesdropping. This question motivates the main concepts of public key cryptography, but before we build public-key systems we need to take a brief detour and cover a few basic concepts from computational number theory. We will start with algorithms dating back to antiquity (Euclid) and work our way up to Fermat, Euler, and Legendre. We will also mention in passing a few useful concepts from 20th century math. Next week we will put our hard work from this week to good use and construct several public key encryption systems.

The Diffie-Hellman Protocol19:00

Public-Key Encryption10:56

Преподаватели

Dan Boneh
Professor

Текст видео

In this module I want to show you another approach to key exchange

based on the concept of public key encryption.

So again, just to remind you of the settings, we have our friends Alice and

Bob as usual and their goal is to exchange a secret key, K.

The eavesdropper gets to see the message they send to one another, but

even though, he shouldn't learn anything about the key K that they exchanged.

And as usual in this module,

we're only gonna be looking at eavesdropping security.

That is, we don't allow the attackers to tamper with data or

to mount any other form of active attack.

So just to remind you, earlier in this module we saw an inefficient mechanism

based on generic blog cyphers.

In the previous segment, we saw the Diffie-Hellman key exchange mechanism,

which has an exponential gap between the work that the participants have to do

versus the work that the attacker has to do.

And in fact, this Diffie-Hellman protocol is used all over the web very frequently.

In this segment,

I want to show you a different approach based on public key encryption.

So what is public key encryption?

So just as in the case of symmetric encryption,

there's an encryption algorithm and a decryption algorithm.

However, here the encryption algorithm is given one key, which we're gonna call

a public key, let's call this the public key that belongs to Bob.

And the decryption algorithm is given a different key,

we'll call it a secret key, that also belongs to Bob.

So these two keys are sometimes called a key pair.

One half of the pair is the public key, and

the other half of the pair is the secret key.

Now, the way you encrypt this as usual, a message would come in.

The encryption algorithm would generate a cipher text

that is the encryption of this message using the given public key.

And then when the cipher text is given to the decryption algorithm,

the decryption algorithm basically outputs the corresponding message.

So as I said, PK is called the public key, and SK is called the secret key.

So more precisely, what is public key encryption?

Well, public key encryption is actually made up of three algorithms, G, E, and D.

Algorithm G is what's called the key generation algorithm.

When you run algorithm G, it will output two keys, the public key and

the secret key.

The encryption algorithm basically, given the public key in a message,

will output the corresponding cypher text, and

the decryption algorithm, given the secret key in the cypher text,

will output the message or it will output bottom if an error occurred.

And as usual, we have the usual consistency properties that say that for

any public key and secret key that could have been output by the key

generation algorithm, if we encrypt a message using a public key, and

then decrypt using the secret key, we should get the original message back.

Now what does it mean for a public key system to be secure?

Well, we use the same concept of semantic security that we used before,

except the games now are a little bit different.

So let me explain how we define semantic security for a public key system.

So here, the challenger is going to run the key generation algorithm to generate

a public key and a secret key pair, and

he's going to give the public key to the adversary.

The challenger keeps the secret key to himself.

What the adversary will do is he will out put two equal length messages, m0 and

m1 as before.

And then the challenger will give him the encryption of m0 or m1.

As usual, we define two experiments, experiment zero and experiment one.

In experiment 0, the adversary is given the encryption of m0, in experiment 1,

the adversary is given the encryption of m1.

And then the adversary's goal is to guess which encryption he was given.

Was he given the encryption of m0, or was he given the encryption of m1?

And we refer to his guess as the output of experiment zero or experiment one.

One thing I wanna emphasize is that in the case of public key encryption, there's no

need to give the attacker the ability to mount a chosen plain text attack.

Why is that?

Well, in the case of a symmetric key system,

the attacker had to request the encryption of messages of his choice.

In the case of a public key system, the attacker has the public key and therefore,

he can by himself encrypt for himself any message that he wants.

He doesn't need the challenger's help to create encryptions of

messages of his choice.

And as a result, in a public key settings, a chosen plaintiff attack is inerrant.

There's no reason to give the attacker extra power to mount a chosen plain

text attack.

And that's why we never discuss chosen plaintiffs' queries

in the context of defining semantic security for public key systems.

Now that we've defined the game, we're gonna say that a public key system,

GED, is semantically secure.

It's basically,

the attacker cannot distinguish experiment zero from experiment one.

In other words, the adversary's probability of opening one and experiment

zero is about the same as its probability of opening one in experiment one.

So again, the attacker can't tell whether he was given the encryption of m0 or

the encryption of m1.

Now that we understand what public key encryption is,

let's see how to use it to establish a shared secret.

So here are our friends, Alice and Bob.

Alice will start off by generating a random public key, secret key pair for

herself, using the key generation algorithm.

And then she's going to send to Bob, the public key, pk.

And then she also says, hey, this message is from Alice.

What Bob will do is he will generate a random 128-bit value x and

he will send that to Alice saying, hey, this message is from Bob.

And he'll send back the encryption of x under Alice's public key.

Alice will receive the cypher text.

She'll decrypt it using her secret key.

And that will give her the value x.

And now this value x can be used basically as a shared secret

between the two of them.

I want to emphasize that this protocol is very different from the Diffie-Hellman

protocol that we saw in the last segment in the sense that here,

the parties have to take turns, in the sense that Bob

cannot send his message until he receives the message from Alice.

In other words, Bob cannot encrypt x to Alice's public

key until he receives the public key from Alice.

In a Diffie-Hellman protocol, however, the two parties could send their messages

at arbitrary times, and there was no ordering enforced on those messages.

As a result, we have this nice application of Diffie-Hellman where

everybody could post their messages to Facebook, for example, and

then just by looking at Facebook profiles, any pair would already have a shared key

without any need for additional communication.

Here this is not quite true,

even if everybody posts their public keys to Facebook, there would still

be a need to send this message before a shared key can be established.

So now that we understand the protocol, the first question we need to ask is,

why is this protocol secure?

And as usual, we're only gonna look at eavesdropping security.

So in this protocol, the attacker gets to see the public key and the encryption of

x under the public key, and what he wants to get is basically this value x.

Now we know that the system, the public use system that we used,

is semantically secure.

What that means is that the attacker cannot distinguish the encryption of x

from the encryption of something random.

In other words, just given the encryption of x, the attacker can't tell whether

the plain text is x or just some random junk that was chosen from M.

And because of that, that basically says that,

just by looking at messages in this protocol, the value of

x is indistinguishable in the attacker's view from a random element in M.

And as a result, x can be used as a session key between the two parties.

It's just a random value which the attacker cannot actually guess

other than by trying all possible values of M.

And I should say that showing that these two distributions are distinguishable

follow directly from semantic security, and in fact this is a simple exercise to

show that if the attacker could distinguish this distribution from that

distribution, then the attacker could also break semantic security.

And as usual, even though this protocol is secure against eavesdropping,

it's completely insecure against the man-in-the-middle attack.

So let's see a simple man-in-the-middle attack.

Well, so here we have Alice generating her public key, secret key pair.

At the same time the man in the middle is still going to generate his own public

key, secret key pair.

Now when Alice sends her public key over to Bob, the man in the middle will

intercept that and instead he'll say, yeah this is a message from Alice,

but Alice's public key really is really pk prime.

So now Bob will receives this message.

He thinks he got a message from Alice.

What he'll send back is, well, he's gonna choose his random x, and

he'll send that encryption of x under pk prime.

The man in the middle is gonna intercept this message, and

is gonna replace it with something else.

So his goal is to make sure that the key exchange succeeds.

In other words, Alice thinks that she got a message from Bob, and

yet the man in the middle should know exactly what the exchange secret is.

So what should the man in the middle send to Alice in this case?

So here, let's call this cypher text C.

What the man in the middle will do,

is he will decrypt the cypher text C, using his own sequence key.

And that will reveal x to the man in the middle.

And then he's gonna go ahead and

encrypt x under Alice's public key, send the value back to Alice.

Alice will obtain this x and as far as she's concerned,

she just did a key exchange with Bob where both of them learned the value x.

But the problem, of course, is that the man in the middle also knows the value x.

So this protocol becomes completely insecure once the man in the middle can

tamper with messages from Alice to Bob and from Bob to Alice.

So again, we have to do something to this protocol to make it secure,

and we're gonna see how to do that actually in two weeks,

after we introduce digital signatures.

So now that I've shown you that public encryption implies key exchange

secure against eavesdropping, the next question is,

how do we construct public key encryption systems?

And it turns out that these constructions generally rely on number theory and

some algebra, and just like the Diffie-Hellman protocol relied on some

algebra, and so before we go into these protocols in more detail,

what I'd like to do is kind of take a quick detour.

In the next module, we're going to look at the relevant number theoretic background.

We'll just do one module on this and then we'll come back and

talk about these public key constructions and more constructions for key exchange.

So this is the end of this module, and as further reading, I just wanted to point to

this paper that shows that if, in fact, all we do is rely on symmetric ciphers and

hash functions, then Merkle Puzzles are optimal for key exchange.

And in fact, we cannot achieve more than a quadratic app as long as we treat

the primitives we're given as a black box.

So basically this shows that a quadratic app is the best possible.

And also, I wanted to point to another paper that kind of summarizes

some of these key exchange mechanisms that we talked about.

Key exchange using public key cryptography, and

key exchange using the Diffie-Hellman.

You can take a look at this paper and it kind of will give you a look ahead

into what's coming and how to make these key exchange protocols

secure against man in the middle and not just secure against eavesdropping.

Okay, so that's the end of this module and the next module, we'll take a brief detour

and do a kind of a brief overview of algebra and number theory.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play

Coursera
О проекте
Руководство
Карьера
Каталог
Сертификаты
Сертификаты MasterTrack™
Степени
Для организаций
Для правительственных организаций

Сообщество
Learners
Partners
Developers
Beta Testers
Translators

На связи
Блог
Facebook
LinkedIn
Twitter
Instagram
YouTube
Технический блог

Еще
Условия
Конфиденциальность
Помощь
Доступность
Пресса
Контакты
Справочник
Филиалы