Placeholder Image

Subtitles section Play video

  • 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

So when we looked in the last video my security overview for a particular website we noticed he actually wasn't using Diffie Hellman

Subtitles and vocabulary

Operation of videos Adjust the video here to display the subtitles

B1 curve generator shorter private mathematics point

Elliptic Curves - Computerphile

  • 3 0
    林宜悉 posted on 2020/03/27
Video vocabulary