So when we looked in the last video my security overview for a particular website we noticed he actually wasn't using Diffie Hellman it was using elliptic curve diffie-hellman, so this is just going to be a short video that explains broadly the difference between the two without going into too much maths although actually the maths of elliptic curves isn't that difficult. Let's not go over Diffie-Hellman a third time 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. Every time I talk about Diffie-Hellman and use any kind of analogy people were like oh show us the maths so this is for the maths people We had a few interesting questions on the Diffie-Hellman video so let's explore Remember that Alice here has some public variable g ^ a mod n now what's important about this is that in some sense a has been mixed into this generator, so what we can't split it up She can send this around, without everyone working out what a is, which is the important thing. So really what the mathematics behind Diffie-Hellman does, is allow the protocol to send messages where you can't extract this private variable and that's exactly what elliptic curves do, they just do it in a slightly different way I'll draw a picture elliptic curve ish.
Right so this is an elliptic curve Elliptic curves are curves in two dimensions Cameraman: We need colors on this mark, colors, couple colors Mark: It's the future, right! So the formula for an elliptic curve is y^2 = x^3 + ax + b. and that's the last time we were to talk about it. So the parameters of the curve are a and b and then the curve will look something like, hold on I'm going to sort take a bit of artistic license with this but something a bit like that.
Now they vary in shape depending on what a and b are. The thing about an elliptic Curve is in our modular arithmetic we had numbers going around modulo n, right which is just a list of numbers it's a cycle of numbers. Here we have a cycle of points somewhere on this curve, so our generator will be a point on this curve Let's use blue, shall we. This is our generator That's not a good place for my generator It's not a good place my generator, because then my next example of adding things to the generator won't work Let's let's do it Let's do it there all right ignore that point that can be a different point for later now if this is our generator G What we can do, instead of raising things to powers, we just add G to itself. We have 2G 3G 3G is G Plus G Plus G. Yeah, so what we can do is we can add G to itself. To do that what you do is you draw a line At the tangent of this curve all the way until it hits another point on the curve You flip it over to the other dimension, and this is 2g over here 3G would be the line between these two.
Find out where it intersects and flip it over here So this is 3G. 3G plus G, would be, it goes along here like this Intersects the curve somewhere else flips over and it's over here, so this is 4G. Now we won't look at it anymore right the actual formula for this is just mathematics to do with lines and the tangent of this curve It's actually not very complicated the point is what we're doing is by multiplying G By various numbers or adding it to itself this point addition. We're moving around this curve sort of seemingly at random Right a bit like how we were moving around our clock face seemingly at random so the nice thing is that if you're adding points together one elliptic curve You will always intersect only one other point Which means that you've never got a choice of two or three points where you could go so that helps a lot? When you're doing this so if I give you a point on the curve here And I say question mark G right how many multiples of G Is that then any ideas no no idea at all right? It could be 50 G.
It. Could be 5 billion G We don't we you know it There's no way of knowing that is our private number, and that's the thing we can't extract back out here We couldn't get our a if I give you a G That's all I'm gonna capitalize it now G. Plus G Plus G Plus G a times on this curve I give you that point and ask you to tell me what the private variable was oh No idea, you know for a small curve. You might get it off a few attempts for a big curve You're never going to get it. Oh, it's going to take you so long and you won't bother So what? Elliptic curves, do is literally a plug in replacement for the mathematics that a modular arithmetic mathematics involved in normal difficulty late B G and their shared secret will end up being a B G and it's very very similar now Just to give you someone. We also do this all modulo n because why wouldn't you? Know because that's how the mathematics works. That's what we do so in fact.
It doesn't really look like a curve anymore I'll show you a picture of one so this is an example of elliptic curve. I just looked on internet right modulo something like 460 this is some curve I don't know what the parameters are now you can see if this was a generator The points are just gonna dot around all over the place eventually They'll go back to the start and cycle background again But not for a long long time so if I give you this point and tell you what was my private number That's how it's secure. It's very hard to undo that and in fact It's very mathematically quite easy to calculate some multiple of G and move around But it's difficult to undo that process that's the private part of elliptic curves.
You know I'm going to ask you though Why why, would you bother with this? So this looks like it's are being unnecessary complication. Yeah well It's a notice in some sense slightly more complicated, but actually Mathematically, it's much more efficient the so elliptic curves are a little bit harder to solve this elliptic curve discrete logarithm problem Which is what we call it? It's slightly harder to solve in some sense than the regular discrete logarithm problem Which means that elliptic curves can get away with shorter key sizes? And that just means less computation when you're calculating a to the G or B to the G To give you an example, so let's imagine that I use a different key was three thousand bits long I would get the same security from an elliptic curve where my prime n is only 256 bits long which is much much shorter the matter is much easier to compute much much faster, so There was a strong tendency to use elliptic curves for that reason if you've got to imagine if you're a server Performing these key exchanges all the time because people come into your shop or something like this Then that kind of savings actually quite useful.
It doesn't really matter if you're doing on your home PC But you know that many You might as well use it with the flip side of that question that yeah is anyone still using the other way Yep so there are a few people who are a little bit suspicious of elliptic curves and certain elliptic curves for example the NIST P 256 curve has its disk trap Detractors because they're not absolutely sure where things like this a and B came from and so on okay Maybe I mean for what it's worth big companies are also using that curve, and they seem to be fond of it Other curves are available to give you an example I've used a publicly available cryptography library to generate a couple essentially equivalent to G to the a and a G just so you can see the difference in this sort of size We're talking about here if I run this Python script We've established a generator and a large prime And this prime is 2048 bits so this is our a and this is our G to the a mod N And you can see I mean this will be slightly shorter, but the idea you can see they're there They're quite long approaching two thousand bits so that on a fast version you can see it didn't take very long to compute But it took a little time to compute if I've run the same thing using elliptic curve.
Cryptography on the NIST P 256 curve We'll see it should be a lot shorter, okay There we go right much shorter the missing 256 bit number much much shorter. You can see our private key is actually a number Because it's a number a the number of times We've jumped around our elliptic curve, and this is our actual XY coordinate of our point on the curve So you can see it's split into here's the first part, and then the second part here So this is X and this is y? What you would normally do in this kind of situation if you were driving a key from this is Scrap the Y and just use the X because it's long enough and secure enough But that will depend on your situation there are debates that I had over What curves are safe to use a lot of people use the NIST PT five six curve? But some people other researchers don't think that secure because it may be made they've taken shortcuts on some of the parameters for efficiency reasons They're not sure where somebody's parameters came from and that isn't without precedent There was a situation where an elliptic curve random number generator was found to essentially have a backdoor Which might be for a different video so the x.25 five one nine.
Curve is quite well-regarded because they've gone to great lengths to Demonstrate how they came up with their variables, and why it's used you know if you're if you're intricate to graphic research This is something that comes concern. You who's just using the web probably don't worry about it Heed the message hello computer file pop up, so it's getting the data of various things and we see here hello computer file We've been able to do this by accessing a value that we shouldn't be able to access this code this if statement should stop us Being able to access this past the end of this array.
