00:00:00
we talked a bit about end-to-end
00:00:01
encryption already and
00:00:03
a lot of the assumption is that we have
00:00:05
some kind of symmetric key that we can
00:00:06
use to talk privately so you and me have
00:00:08
some kind of secret key and we use that
00:00:10
to talk securely diffie-hellman is how
00:00:13
we get that secret key
00:00:17
diffie-hellman was first published in
00:00:19
1976 and has become
00:00:22
pretty much a staple for any kind of
00:00:24
cryptography at all right whenever we
00:00:26
use cryptography we usually need to have
00:00:28
a symmetric key and to get that we often
00:00:30
have to perform some kind of diffi
00:00:32
helmet it's so prevalent that your phone
00:00:34
is probably doing it right now right you
00:00:36
when you're logged onto the browser to
00:00:38
watch this video you perform the
00:00:39
diffie-hellman key exchange
00:00:41
when you open up your phone and it
00:00:43
connects to any server it'll almost
00:00:44
certainly perform a diffie-hellman key
00:00:46
exchange if not now then in the next few
00:00:48
minutes right it's it's unbelievably
00:00:50
important and unbelievably common the
00:00:52
problem with diffie-hellman is it's
00:00:53
quite mathematically complex it depends
00:00:55
on your level of mathematics so what i
00:00:57
thought we'd do is i thought we'd cover
00:00:58
the mathematics in extra bits and then
00:01:00
we'd look at a kind of worked example of
00:01:02
what actually happens as an overview for
00:01:05
those people who just not interested in
00:01:06
mathematics because they don't need to
00:01:07
implement it and they don't really
00:01:09
really mind
00:01:10
so we'll do both and that way hopefully
00:01:12
there's something for everyone we shall
00:01:13
see so perhaps diffie-hellman key
00:01:15
exchanges is slightly misnamed in the
00:01:17
sense that um what we don't actually do
00:01:19
is exchange a key
00:01:21
because then it would be out in the
00:01:22
public and we would see it what we
00:01:24
actually do is exchange some public
00:01:25
variables and we combine them with some
00:01:28
private variables we've kept hidden so
00:01:29
that we can both create the same key
00:01:31
right so we're actually creating a key
00:01:33
together in some sense
00:01:35
so as always we'll go back to alice and
00:01:37
bob for this so let's have alice over
00:01:39
here
00:01:40
right and bob over here i'm going to
00:01:41
sort of spread this out a bit because
00:01:43
we're going to bring these in and
00:01:44
i don't want to run out of space right
00:01:46
so alice and bob are here these are
00:01:47
their own machines
00:01:48
and this
00:01:50
is the kind of public area
00:01:52
so anything that alice and bob send to
00:01:53
each other or agree on in public is
00:01:55
going to be in this area so as an
00:01:57
attacker if we want to break this key
00:01:59
exchange if we want to find out what the
00:02:00
secret key is we have to use these
00:02:02
variables to do it right and that
00:02:04
hopefully will explain why
00:02:06
that's difficult to do
00:02:08
okay so the first thing
00:02:10
is
00:02:11
right at the beginning of the tv helmet
00:02:13
key exchange alice and bob have to agree
00:02:15
some mathematical parameters that
00:02:16
they're going to use this is a value g
00:02:19
or a generator and a big prime number n
00:02:22
right now for this example i'm going to
00:02:25
use color mixing to try and explain this
00:02:27
i'm going to write the letters in as
00:02:28
well n won't have a color for the sake
00:02:30
of this analogy
00:02:32
g does right so g is going to be
00:02:34
um let's go with yellow right now i'm
00:02:37
going to sort of squirt this in and hope
00:02:38
that it doesn't go everywhere in fact we
00:02:40
kind of need two copies of g really so
00:02:41
let's just sort of fill it up here
00:02:43
up to about i want to get them the same
00:02:46
so far so good so far it's not all over
00:02:48
my desk all right close enough right
00:02:50
um
00:02:51
well it's kind of yellowy
00:02:53
[Music]
00:02:54
often they're shared at the very
00:02:55
beginning of the handshake sometimes
00:02:57
they're just
00:02:58
embedded in standard or everyone always
00:02:59
uses the same one it depends on the on
00:03:02
the situation
00:03:03
it can take a little time an extra
00:03:05
message to send these things across so
00:03:06
sometimes having them stashed ahead of
00:03:09
time is a good idea so we've got g right
00:03:11
this is this is g now alice to begin
00:03:14
with needs to calculate a private key
00:03:16
right or private variable i'm going to
00:03:18
choose red for alice there we go
00:03:20
probably could use more food coloring
00:03:21
it's kind of pale red is that red yeah
00:03:24
close enough what do you think it's rose
00:03:26
coloured now bob is going to do the same
00:03:28
thing he's going to have a private value
00:03:29
which is going to be blue
00:03:30
right now i haven't chosen very
00:03:32
interesting colors that's simply because
00:03:34
there aren't that many colors available
00:03:35
in the shops for food coloring um and i
00:03:38
didn't go through that much effort there
00:03:39
we go i suppose blue now
00:03:41
these two colors are in their private
00:03:42
area this is this is a and this is b so
00:03:45
i'm going to label these this is little
00:03:46
a this is little b now the important
00:03:49
thing is that these are never shared
00:03:50
with anyone alice doesn't share this
00:03:51
with the public alice doesn't share this
00:03:53
with bob now the first thing that
00:03:54
happens is that we need to combine the
00:03:56
private key with the generator to before
00:03:59
to produce a public key right now the
00:04:01
point is that once we've combined them
00:04:03
we can't unmix it right that's why
00:04:05
people like to use this color analogy
00:04:07
once we pour two colors together it's
00:04:09
difficult to know what colors went in
00:04:11
right because it yes okay so if i pour
00:04:13
red into yellow it maybe make orange but
00:04:15
it could be but it was a bit more yellow
00:04:17
and a bit less red or you know it's
00:04:19
difficult to know right so it's kind of
00:04:21
orange for alice and bob's gonna take
00:04:23
his blue
00:04:25
i can't need them to be the same level
00:04:26
really
00:04:28
and it does kind of make green
00:04:30
this is a bit orangy let's not critique
00:04:32
me too much so yeah they're very
00:04:33
different to the originals and the
00:04:35
important thing is that we don't know
00:04:37
what went into here right we know g
00:04:40
but we don't know a and we can't find
00:04:42
out so this is actually this here this
00:04:44
public key here
00:04:46
is a g in some sense it's got an a in it
00:04:48
it's got a g in it right this one has
00:04:51
got a b in it and it's got a g in it and
00:04:54
we can't extract the a's we can't
00:04:56
reverse this process
00:04:58
now
00:04:59
they then are going to exchange these
00:05:01
two public variables but keep the
00:05:03
private ones back so we're going to sort
00:05:05
of draw an arrow over here
00:05:07
and an arrow over here
00:05:09
and they're gonna switch them like this
00:05:12
right so they get sent out in clear text
00:05:14
these are now in the public area because
00:05:16
they've been sent in plain text
00:05:18
everyone's seen them right so now
00:05:21
as an attacker i know
00:05:23
bg or
00:05:24
bob's public part of his key a g alice's
00:05:27
public component and g and n right i
00:05:30
don't know anything else i don't know
00:05:31
what a and b are
00:05:33
now this is the final part
00:05:35
diffie-hellman it's not actually very
00:05:36
long you can do all this in three
00:05:37
messages alice is going to take the
00:05:39
public component that bob sent her and
00:05:42
add her private key
00:05:44
and bob is going to take alice's public
00:05:47
component and add his private key so
00:05:49
we're going to get
00:05:50
in essence a mixture of a and b and g
00:05:55
all right that's the idea so let's do
00:05:56
that now so is that in the private
00:05:58
domain
00:05:59
um yes this will be done privately
00:06:00
because these are never neither never no
00:06:02
so these go into the private domain now
00:06:04
i mean i could make a copy of them let's
00:06:05
not um so alice is going to add her red
00:06:07
in
00:06:08
so let's go let's just add some red up
00:06:10
to about there it doesn't really work
00:06:12
because they're ready to be faint and
00:06:14
then bob adds in his blue
00:06:16
which is going to be like
00:06:20
that
00:06:21
and hopefully
00:06:23
this is where it all doesn't work or
00:06:24
does work
00:06:25
these two values are kind of the same
00:06:28
i mean they're not they're pretty close
00:06:30
that's a little bit darker perhaps
00:06:31
because the blue's a bit stronger
00:06:32
considering you've done that without
00:06:34
actually measuring anything yeah i mean
00:06:36
obviously
00:06:37
you would do this normally with
00:06:38
mathematical
00:06:40
with mathematical functions that are
00:06:42
much more precise than my random
00:06:43
squirting of liquids now
00:06:45
so those two are now in in the private
00:06:48
these are yeah this is private so alice
00:06:49
has taken bob's bg and added her a so
00:06:52
that gets a
00:06:54
b g
00:06:55
and bob takes
00:06:57
alice's a g and gets a b g by putting
00:07:01
his b in there right now the order
00:07:03
doesn't matter remember just like mixing
00:07:04
colors the mathematics is such that if
00:07:06
we add in b first to g and then we add
00:07:09
an a it's the same as adding an a first
00:07:11
so these two values are exactly the same
00:07:13
if you wanted to try and recreate this
00:07:15
as an attacker you can't do it because
00:07:18
you have
00:07:19
a g
00:07:20
and b g
00:07:21
and g and so you could mix these two
00:07:24
together and you would get a b
00:07:26
g g in some sense mathematically this is
00:07:28
a little bit tenuous but we'll talk
00:07:30
about that in the extra bits the point
00:07:32
is nothing in this public area can be
00:07:33
combined in any way
00:07:35
to get
00:07:36
this value or this value which are the
00:07:38
same the only way to do that is to find
00:07:41
out what a and b are and the only way to
00:07:43
do that is to split up one of these two
00:07:45
public components which is very very
00:07:47
difficult to do right and that's what's
00:07:49
so cool about diffie-hellman in a few
00:07:51
messages we've sent some public but some
00:07:54
public numbers around and we've used our
00:07:56
private numbers to get a shared secret
00:07:58
that no one else can know
00:08:00
now
00:08:01
you would generally do this at the
00:08:02
beginning of every conversation and you
00:08:04
would use this number combined with
00:08:06
perhaps some session variables something
00:08:08
like this to
00:08:10
derive secret keys for using things like
00:08:12
aes right so this is actually just going
00:08:13
to be a number which would vent her hash
00:08:16
to turn into an aes key or something
00:08:17
like that
00:08:20
now the mathematics behind
00:08:21
diffie-hellman is usually
00:08:24
modular arithmetic recall that we have
00:08:26
our public numbers g
00:08:27
and n g is often very small it's usually
00:08:29
a small prime number n is often very big
00:08:32
and needs to be big for the security of
00:08:33
this to work n is often 2 000 bits long
00:08:36
or 4 000 bits is more common now
