Diffie Hellman -the Mathematics bit- Computerphile

Every time I talk about diffie-hellman And use any kind of analogy people were like oh show us the math show us the math I could have taken the maths So this is for the maths people where if you want to know how? Mathematically diffie-hellman works watch this video if you don't want to know that there's a nice clothes button in the top corner or a back Button you know be my guest so that this is for mathematically inclined people Let's go back to where we were before so we have Alice and we've got Bob And we've got our public area here sort of public Public and we go draw down here now the mathematics behind diffie-hellman is usually modulo arithmetic recall 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 of this to work and is often 2,000 bits long or 4,000 bits is more common now So n is very very big it can't be too big because you won't gain much in security But you lose in efficiency So you know you have to think about that Alice and Bob need to pick their numbers a and B so Alice picks a number a Bob picks a number B. These are the ones they're going to keep private now a Is somewhere between 1, and n but it's random and n is so vast, but it's not going to be 1 It's gonna be a very big number. It's not worry about what it is She's not gonna. Tell anyone what that is same for Bob the first thing else does if she calculates G to the power of a mod n right now modulo if you do any programming you'll be familiar with it's a percent symbol is the remainder after division so Another way of looking at modulo is to have this kind of clock face, so if we have a clock face Which should be a circle and we go from 1 2 3 all the way round? To n these are the numbers modulo n 4 when we perform some arithmetic in this space We just go around and man the clock face. We don't ever leave and go above in or below 0 in fact If this should be 0 as well this should be a 0 in here So when you do G to the power of a mod n? What happens is you're raising G to the power of some massive number which would be very normally very big? but in actual fact It just goes round around this clock face and ends up somewhere So let's say G to the a mod n arrived somewhere here on the clock face now. What's important about? This is it's very difficult given this to work out What a was we know g let's say three right if I say we are here on the clockface and we started at three what number is a It's just impossible to know right because it's position on this clock has no bearing on how many times has gone round Or what a was at all right? The only way to do. This is essentially to brute force it to go Well is it a ^ 1 no It's not is it a 2 the power to know and and so on and so forth for an infeasible amount of time well We did a little bit of this with the hashing video didn't we there was a little bit of the modulo function there in in? Calculating the hash yes, so that was used to shorten something at the end But it's the same kind of principle mojo is very useful for taking something But it could be any length and putting it into a sort of finite loop with a finite group of actual numbers now Bob We're going to take G to the B mod n so let's say that turns off over here somewhere So this is G to the B mod n so again what we've done is we've taken G we've raised it to the power of B, and we've done all of this modulo N which means that it just if it ever goes above in it Just loops back down to 0 and keeps going so this is somewhere else these are very public components So they share these like this so now these are public but again calculating a and B from this is very very difficult it's called solving with discrete log problem and Practically very very difficult for even a supercomputer all right now Alice is going to take this I'm just going to simplify the notation slightly to make it fit on the page But as it's going to take the G to the B but Bob sent and raised it again to the power of a mod N and Bob is going to take G to the a that Alice sent and raise it to the power of B mod N and Anyone, that's done any exponentiation knows that if you do something to the power of something to the power of something else It's actually just those two things multiplied so G It's G to the a B Mod n that's the answer so that will put you that will come somewhere around you know let's say here so this is G to the a B mod n now this will be some number between 0 and n Bob's done the same thing he's also got G to the a B mod n and They're exactly the same briefly two identical colors We were looking at in our color example So they've both arrived at the exact same position in this group Despite the fact that neither the knew what each other's private key was that's what's really cool about Diffie Hellman To try and reverse this process we have to know a or B We know publicly G to the a and we also know G to the B if we try and multiply them together for example We'll get G to the a plus B. Which is not the same, right? That's me sort of mixing my public colors together in the hope of getting to my answer. I haven't done it That would be somewhere else a completely different number remember. This is cryptography if you're one Position out it not going it's not going decrypt Okay So you know you have to get it exactly right the fact that she's got G to be To the AE is no different to GT v8 in a bit. It's exactly the same I mean you could you could look at an example if you went to to the power of 2 to the power of 3 That's 2 times 2 times 2 times 2 times 2 times 2 Right which is 2 to the 6 because? There's this stick to them you can do it in any order? It doesn't matter you get the same number out at the end whereas that is a completely different thing. Yeah, so that is equivalent of 2 2 power of 2 times 2 to power 3 which is 2 times 2? Times 2 times 2 times 2 which is 2 to the 5 entirely different number now those numbers are fairly similar because these examples are Small you guys going to be somewhere else completely honest on this model you take clockface you're not gonna It's not gonna work at all the N number is kind of important though is it right It's mostly important that n is big because if n is small Then in essence this clock face is going to have only a few numbers on it You can brute-force that very quickly Right you can find the value of a or the value of B and reverses process if n is you know Astronomically large like 2,000 or 4,000 bits the amount of time It's going to take you to find the correct the correct values for a or B is I mean it essentially is long enough that you won't bother that's the argument It's technically possible, but you would be long dead by the time you did it and so you're you finding out What image they send each other is not about useful? Actually, this is this is quite simple right? I mean let's not under play This is incredibly important for computer science and mathematics But it's actually not that complicated in some sense very elegant If you want to see some worked examples of this Wikipedia and other websites have lots of small examples with small numbers So that you can work this through if you want to have a go at the math yourself right and you'll get the same answer Out and it's you know it's impressive

Channel: Computerphile

Views: 344,045

Rating: 4.9727712 out of 5

Keywords: computers, computerphile, computer, science, Computer Science, Diffie-Hellman, University of Nottingham, Dr Mike Pound, Key Exchange

Id: Yjrfm_oRO0w

Length: 7min 5sec (425 seconds)

Published: Wed Dec 20 2017