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.
Public-Key Encryption
Loading...
From the course by Stanford University
Cryptography I
2045 оценки
From the lesson
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.
Meet the Instructors
Dan BonehProfessor
Computer Science
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., 2018 Все права защищены.
