Secret Key Exchange (Diffie-Hellman) - Computerphile

we talked a bit about end-to-end encryption already and a lot of the assumption is that we have some kind of symmetric key that we can use to talk privately so you and me have some kind of secret key and we use that to talk securely diffie-hellman is how we get that secret key diffie-hellman was first published in 1976 and has become pretty much a staple for any kind of cryptography at all right whenever we use cryptography we usually need to have a symmetric key and to get that we often have to perform some kind of difficult it's so prevalent that your phone is probably doing it right now right you're you when you logged on to the browser to watch this video you performed a diffie-hellman key exchange when you open up your phone and it connects to any server it'll almost certainly perform a difficult and key exchange if not now then in the next few minutes right it's it's unbelievably important and unbelievably common the problem with difficult is it's quite mathematically complex it depends on your level of mathematics so what I thought we'd do is I thought we'd cover the mathematics in the next row bits and then we look at a kind of worked example of what actually happens as an overview for both people who just not interested in the mathematics because they don't need to implement it and they don't really really mind so we'll do both and that way hopefully there's something for everyone we shall see so perhaps diffie-hellman key exchanges it's slightly miss named in the sense that what we don't actually do is exchange a key because then it will be out in the public and we'd see it what we actually do is exchange some public variables and we combine them with some private variables we've kept hidden so that we can both create the same key all right so we're actually creating a key together in some sense so as always we'll go back to Alice and Bob for this so this have Alice over here right and Bob over here I'm gonna sort of spread this out a bit because we're going to bring these in I don't wanna run out of space right so Alice and Bob are here these are their own machines and this is the kind of public area so anything that Alice and Bob send to each other or agree on in public is going to be in this area so as an attacker if we want to break this key exchange if we want to find out what the secret key is we have to use these variables to do it right and that hopefully will explain why that's difficult to do okay so the thing is right at the beginning of per ticket Hellman key exchange Alice and Bob have to agree some mathematical parameters that they're going to use this is a value G or a generator and a big prime number in all right now for this example I'm going to use color mixing to try and explain this I'm going to write the letters in as well n won't have a color for the sake of this analogy G does right so G is going to be let's go with yellow right now I'm going to sort of squirt this in and hope that it doesn't go everywhere in fact we kind of need two copies of G really so let's just sort of fill it up here up to about I'm gonna get them the same so far so good so far it's not all over my desk close enough right well it's kind of yellowy often they're shared at the very beginning of the handshake sometimes they're just embedded in a standard or everyone always uses the same one it depends on the on the on the situation it can take a little time and extra message to send these things across so sometimes having them stashed ahead of time is a good idea so we've got G right this is this is G now Alice to begin with needs to calculate a private key right will private variable I'm gonna choose red for Alice there we go probably couldn't use more food coloring it's kind of pale red is that red close enough what do you think it's rose-colored yeah Bob is going to do the same thing he's gonna have a private value which is going to be blue now I haven't chosen very interesing colors that's simply because there aren't that many colors available in the shops for food coloring and I didn't go to that much effort here we go blue now these two colors are in their private area this is this is a and this is B so I'm going to label these this is little a this is little B now the important thing is that these are never shared with anyone Alice doesn't share this with the public Alice doesn't share this with Bob now the first thing that happens is that we need to combine the private key with the generator to before to produce a public key right now the point is that once we've combined them we can't I'll mix it right that's why people like to use this color analogy once we pour two colors together it's difficult to know what colors went in right because yes okay so if I pour red into yellow it maybe make orange but it could be but it was a bit more yellow and a bit less red or you know it's difficult to know right so it's kind of orange for Alice and Bob's gonna take his blue I can't need them to be the same level really and it does kind of make green this is a bit orange II let's not critique me too much and so yeah they're very different to the originals and the important thing is that we don't know what went into here right we know G but we don't know a and we can't find out so this is actually this here this public key here is a G in some sense it's got an A in it it's got a G in it right this one has got a B in it and it's got a G in it and we can't extract the A's we can't reverse this process now they then are going to exchange these two public variables but keep the private ones back so we're going to sort of draw an arrow over here and an arrow over here and they going to switch them like this all right so they get sent out in clear text these are now in the public area because they've been sent in plain text everyone seen them all right so now as an attacker I know BG or Bob's public the part of his key AG Alice's public component and G and n I don't know anything else I don't know what a and B are now this is the final part difficulty can do all this in three messages alice is going to take the public component that Bob sent her and add her private key and Bob is going to take Alice's public component and add his private key so we're going to get in essence a mixture of a and B Angie right that's the idea so let's do that now so is that in the private domain yes this will be done privately because visa never needs in there were no tents so these go into the private domain now I mean I could make a copy of them that's not so as it gonna add her read in so let's go let's just add some wedge up to about there it doesn't really work because the register key faint and then Bob adds in his blue which is going to be like that and hopefully this is where it all doesn't work or does work these two values are kind of the same I mean they're not they're pretty close that's a little bit darker perhaps because the blue is a bit stronger considering you've done that without measuring everything yeah I mean obviously good you would do this normally with mathematical mathematical functions that are much more precise in my random squirting of liquids now so those two are now in in the private VZ yeah this is PO so Alice has taken Bob's BG and added her a so that gets a B G and Bob takes Alice is a G and gets a the G by putting his be in there all right now the order doesn't matter remember just like mixing colors the mathematics is such that if we adding B first to G and then we add an A it's the same as adding an a first so these two values are exactly the same if you wanted to try and recreate this as an attacker you can't do it because you have a G and VG's and G and so you could mix these two together and you would get a B G G in some sense mathematically this is a little bit tenuous but we'll talk about that any extra bits the point is nothing in this public area can be combined in any way to get this value or this value which are the same the only way to do that is to find out what a and B are and the only way to do that is to split up one of these two public components which is very very difficult to do all right and that's what's so cool about difficult man in a few messages we've sent some public but some public numbers around and we've used our private numbers to get a shared secret that no one else can know now you would generally do this at the beginning of every conversation and you would use this number combined with perhaps some session variables something like this to derive secret keys for use in things like AES I said this is actually going to be a number which would vent her hash to turn into an AES key or something like that now the mathematics behind diffie-hellman is usually modular arithmetic we call that we have our public numbers G and M G is often very small is usually a small prime number n is often very big and needs to be big for the security abyss to work and is often 2,000 bits long or 4,000 bits is more common now

Channel: Computerphile

Views: 593,603

Rating: 4.943212 out of 5

Keywords: computers, computerphile, computer, science, Computer Science, University of Nottingham, Dr Mike Pound, Diffie Hellman, Diffie Hellman Key Exchange, Diffie Helman, Encryption, Color Mixing

Id: NmM9HA2MQGI

Length: 8min 40sec (520 seconds)

Published: Fri Dec 15 2017

Reddit Comments

[u/Trevo525]

So what kind of math would you do to combine a and g to make ag? Because it if it was as simple as addition you could subtract the public key to get the private keys so that doesn't work. But alot of other things would give you different numbers depending on the order?