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.
Trusted 3rd Parties
Loading...
Do curso por Stanford University
Cryptography I
2162 classificações
Na lição
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.
Conheça os instrutores
Dan BonehProfessor
Computer Science
Now that we know how two users can protect data using a shared secret key, the next
question is how did these two users generate a shared secret key to begin
with? This question will take us into the world of public key cryptography. In this
module, we will look at a few toy key exchange protocols as a way to introduce
the main ideas of public key cryptography. We're gonna come back and talk about key
exchange and design secure key exchange protocols after we build a few more public
key tools. So imagine for a second that there a N users in the world. And the
question is, how do these users manage these secret keys that they're gonna use
to communicate with one another? So, for example, let's assume N equals four and
there are four users in the world. One option is that basically every pair of
users will share a shared secret key. And so, for example, U1 and U3 will share a
shared, a shared secret key. I'll call it K13. U1 and U2 will share a, a shared
secret key. We'll call it K12 so on and so forth. K24 K34 and so on and so forth. K14
and finally K23. The problem with this approach is that now there are many, many
shared keys that users have to manage. And in particular, every user has to store on
the order of N keys if he's gonna talk to N other parties in this world. So the
question is can we do any better than storing N keys per user? And the answer is
yes. And one way to do that is what's called an online trusted third party. I'll
use TTP to denote that trusted third party. So the way we are going to use the
trusted third party is every user will now share a single key with this trusted third
party. So user one will share a secret key, user two will share a secret key. And
here are our friends Alice and Bob, let's call their secret keys k sub A and k sub B.
Okay, so now the nice thing about this design is that now every user only
has to remember one secret key. The question is now, what happens when Alice
wants to talk to Bob? Somehow the two of them have to engage in a certain protocol,
such that at the end of this protocol they will have a shared secret key KAB that the
attacker wouldn't be able to know. And so the question is how do Alice and Bob
generate this shared secret key KAB. So let's look at an example toy protocol for
doing that. So here we have our friends Alice and Bob. As usual Bob has his key
KB, which is shared with a trusted third party. Alice has her secret key KA,
which is also shared with a trusted third party. So here the trusted third party
has both KA and KB. And the question is, how do they generate a shared key that
they both agree on, but the attacker would have no idea what this shared key is? So
here we're only gonna look at a toy protocol. In particular, this protocol is
only gonna to be secure against eavesdropping. It's not gonna be secure
against more tampering or active attacks. As I said, we're gonna come back and
design secure key exchange protocols later on in the course. But for now, just to
introduce this idea of key exchange, let's look at the simplest, simplest mechanism
that's only secure against eavesdropping. So in other words, adversary that listens
to the conversation won't know what the shared key KAB is gonna be. And so the
protocol works as follows. Alice is going to start by sending a message to the
trusted third party saying, hey I want a secret key that's going to be shared with
Bob. What the trusted third party will do is it will actually go ahead and choose a
random secret key, KAB. So the trusted third party is the one who's gonna
generate their shared secret key. And what it will do with this key is the following.
It's gonna send one message back to Alice. But this message consists of, of
two parts. The first part of the message is an encryption using Alice's secret key,
using the key KA, of the message this key is supposed to be used between parties
Alice and Bob, and she includes the secret key KAB inside the message. Okay? So just
to be clear, what's happening here is that the message that gets encrypted is the key
KAB plus the fact that this key is supposed to be a shared key between Alice
and Bob. Okay. And this whole message is encrypted using Alice's secret key. The
other part of the message that the TTP sends to Alice is what's called a ticket.
And this ticket is basically a message that's encrypted for Bob. So in other
words, the ticket is gonna be an encryption under the key KB of, again, the
fact that this key is supposed to be used between Alice and Bob. And she
concatenates to that the, the secret key, KAB. Okay, so again, the message that's
encrypted inside of the ticket is the fact that this key is to be used by Alice and
Bob. And, the secret key, KAB, is included in the ticket as well. Okay, So these two
messages, Here, let me circle them. These two messages are sent from the trusted
third party to Alice. Now I should mention that the encryption system E that is
actually being used here is a CPA secure cipher and we'll see why that's needed in
just a minute. So, this is the end of the conversation between Alice and this
trusted third party. Basically as we said at the end of this conversation,
Alice receives one message that's encrypted for her and another message
called a ticket that's encrypted for Bob. Now at a later time when Alice wants to
communicate securely with Bob what she will do, is of course, she will decrypt
her part of the message. In other words she will decrypt the cipher text that was
encrypted using the key KA and now she has the key KAB. And then to Bob, she's going
to send over this ticket. Bob is going to receive the ticket and he is going to
use his own secret key KB to decrypt it and then he himself will also recover the
secret key KAB. So now they have the shared secret key KAB that they can use
to communicate securely with one another. And the first question to ask is, Why is
this protocol secure? Even if we only consider eavesdropping adversaries. So,
let's think about that for a minute. So, at the moment all we care about is just
security against an eavesdropper, So let's think. What does an eavesdropper see in
this protocol. Well basically he sees these two cipher texts. Right, he sees the
cipher text that's encrypted for Alice. And then he sees the ticket that's
encrypted for Bob. And in fact he might see many instances of these messages, in
particular if Alice and Bob continuously exchange keys in this way he's gonna see
many messages of this type and our goal is to say that he has no information about
the exchanged key KAB. So this follows directly from the CPA security of the
cipher E D because the eavesdropper can't really distinguish between encryptions of
the secret key KAB from encryption of just random junk. That's the definition of CPA
security and as a result, he can't distinguish the key KAB from, you know,
random junk which means that he learns nothing about KAB. This is kind of a very
high level argument for why this is eavesdropping security but it's enough for
our purposes here. So the bottom line is that in this protocol the eavesdropper
would actually have no information about what KAB is. And therefore it's okay to
use KAB as secret key to exchange messages between Alice and Bob. Now let's think
about the TTP for a minute. So first of all, you notice that the TTP is needed for
every single key exchange. So basically Alice and Bob simply cannot do key change
unless the TTP is online and available to help them do that. And the other property
of this protocol is in fact, the TTP knows all the session keys. So if somehow the
TTP is corrupt, or maybe it's broken into, then an attacker can very easily steal all
the secret keys that have been exchanged between every user of this system. This is
why this TTP is called the Trusted Third Party because, essentially, it knows all
the session keys that have been generated in the system. Nevertheless the beauty of
this mechanism is that it only uses symmetric key cryptography, nothing beyond
what we've already seen and as a result it is very fast and efficient. The only issue is
that you have to use this online trusted party and it's not immediately clear if for
example we wanted to use this in the world wide web who would function as this
online trusted third party. However, in a corporate setting this might actually make
sense if you have a single company with a single point of trust it might make sense
to actually designate a machine as a trusted third party. And in fact a
mechanism like this not quite as the way I described it, but a mechanism like this is
the basis of the Kerberos system. So this is our first example of a key
exchange protocol that allowed Alice and Bob to set up shared keys, however I
really want to point out that this is just a toy protocol. Very, very simple and is
only secure against eavesdropping attack. It's actually completely insecure
against an active attacker. And here's a very simple example of how an active
attacker might destroy this protocol, and so let's just look at replay attacks. So
here imagine the attacker records the conversation between Alice and some online
merchant. Let's call him Merchant Bob. So for example, imagine Alice orders a book
from the merchant Bob and the transaction completes and Bob accepts payment for this
book. And actually sends Alice a copy of this book. What an attacker can do now
is, he can complete, completely record the conversation and simply replay the
conversation to merchant Bob at a later time. Bob will think that Alice just
reordered another, another copy of the book and he'll charge her again for it,
and send her this, this copy again. So essentially by replaying a conversation
you can cause quite a bit of harm to Alice, and as a result this is a simple
example of why this protocol is completely insecure against active attacks, and
should never be used in the real world. As I said we're going to come back in a few weeks
and talk about secure versions of this protocol, and you'll see how to make this
work, in the real world. Nevertheless, you see that this, this very simple protocol
already raises a very interesting question. And the question is, can we
basically design key exchange protocols whether they're secure against
eavesdropping or secure against active attackers. The question is, can we design
key exchange protocols that are secure, but work without an online trusted third
party. So we don't wanna rely on any online trusted party that's necessary to
complete the key exchange protocol. And so the amazing answer is that in fact this is
possible. We can do key exchange without a trusted third party. And this is, in fact,
the starting point of public cryptography. So I'm gonna show you three ideas for
making this happen and we're gonna talk about them in much more detail in the, in
the coming modules. So the first idea is actually due to Ralph Merkle back in 1974.
This was, he was, when he was just an undergraduate student. And already he came
up with this really nice idea for key exchange without an online trusted third
party. So that's one example that we're gonna look at. Another example is
due to Diffie and Hellman. Back in 1976 they both actually, working here at
Stanford University, came up with this idea that launched the world of modern key
cryptography. And the third idea is due to Rivest, Shamir and Adleman working at MIT and
we're going to look in detail exactly how each of these ideas work. But I do want to
mention that the work on public key management hasn't stopped in the late
seventies. In fact there have been many ideas over the years and here I'll just
mention two from the last decade. One is call identity based encryption, which is
another way for managing public keys. And another is called functional encryption,
which is a way of giving secret keys that only partially decrypt a given cipher text.
And so we're gonna talk about the core of public key crypto in this and the next week
and we'll talk about these more advanced ideas later on in the course.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
