B1 中級 6 分類 收藏
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
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
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


Elliptic Curves - Computerphile

6 分類 收藏
林宜悉 發佈於 2020 年 3 月 28 日
  1. 1. 單字查詢


  2. 2. 單句重複播放


  3. 3. 使用快速鍵


  4. 4. 關閉語言字幕


  5. 5. 內嵌播放器


  6. 6. 展開播放器


  1. 英文聽力測驗


  1. 點擊展開筆記本讓你看的更舒服

  1. UrbanDictionary 俚語字典整合查詢。一般字典查詢不到你滿意的解譯,不妨使用「俚語字典」,或許會讓你有滿意的答案喔