Elliptic Curves - Computerphile
ฝัง
- เผยแพร่เมื่อ 15 ม.ค. 2018
- Just what are elliptic curves and why use a graph shape in cryptography? Dr Mike Pound explains.
Mike's myriad Diffie-Hellman videos: • Cryptographic Key Exch...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
![[Teaser EP.2] “MasterChef Junior Thailand Season 3” วันอาทิตย์ที่ 9 มิ.ย. นี้ 6 โมงเย็น ทางช่อง 7HD](http://i.ytimg.com/vi/KojBzrifbWg/mqdefault.jpg)
Up till now Tom Scott was hands down my favourite Computerphile presenter, but Mike is now taking over that role. :) as always - great video and nice simplified explenation.
I always appreciate new entries in the Diffie-Hellman Cryptographic Universe.
He just loves saying "Diffie-Hellman" 😆
ForestCat_Peter
I think the name came from the initial attempts at solving this problem...
"Golly, this one sure is a diffie. Hell, man..."
Saying it is so satisfying to the lipse
and I love hearing him say it....
I mean... don't you? :P
we all do
7:32 "What you would normally do in this kind of situation if you're were deriving a key from this, is scrap the y and just use the x cuz it's long enough and secure enough." That's wrong! It got nothing to do with x being long end secure enough. It's just that x holds all information necessary to describe what point on the curve you're talking about when the curve you're using is known (which it is) when you just add the information of which side of the curve the point is on. This is why you don't just use x but also add a single bit denoting the side of the curve the point is on. If you look at the formula he wrote down, you can see that you can calculate y^2 when given x, a, and b. a and b are just publicly known parameters. After calculating y^2, you can calculate y except for its sign. If you're given x, a, b, and the sign of y, you can calculate y.
Very nicely corrected, Jim. Thanks!
Is that why the y value is compressed as a 0 or 1?
hey Jim, could you explain in a a very basic mathematical way how EC is used for encrypting/signing data, and retrieving it?
frigga They never say why this system is better than any other system!
@@Pimp-Master Well they often do, you need a shorter key compared to RSA and way less resources, but nobody can give a real example, just theory all the time.
I LOVE the fact that he's able to take something that is really, quite complicated, and break it down into vastly simpler terms so that the knowledge is more accessible to a wider range of audience members.
This is how you truly know your stuff -- the test of it is how well can you "dumb it down" so that other people who don't do this daily, would understand this, at least conceptually.
This is what I strive for with some of the stuff that I've learned, is to be able to learn it enough to be able to pass on that knowledge (correctly) to other people. :)
Wow, I just got out of my 2 hour lecture where the professor attempted to explain elliptic curves and this 8 minute video explained it much better. Quite impressive!
Would love to see a video about the back door mentioned!
Didn't they already made a video about that one?
Daggawaggaboof Yeah, there’s one on Numberphile.
It's on computerphile now too.
Finally a new Mike Pound video. I missed you, man
Brailsfor so good too. And Mike is just sharp on theese topics
As a 1st year Calculus student, the maths and geometry was extremely EXTREMELY beneficial to me. It tied several different things I have learned into one real application.....derivative.....mirror about x axis......corresponding x coordinate......derivative.....mirror about the x axis......etc. VERY cool!
Algebraic geometry and algebraic number theory doesn't use calculus much
Amazing instructor who has the very unique ability to break very technical topics into an easily understandable video. Thank you!
Yet another great explanation by Dr. Mike Pound. Great stuff, thanks so much!
Thank you for making these videos. I assume making those Diffie-Hellman videos was annoying but seeing the math all the way through really helped me. Thanks again.
Love this series about cryptography. Please keep on with it.
I really like these videos from Dr Pound. Already looking forward to a video on different curves. :)
Thanks for another cracking explanation.
Yeah, it's Mike again! Always glad to see that cheeky guy.
I am become FAN of you now. You are amazing in explaining the concepts. Awesome.
A cryptographer, flirting with someone in a monogamous relationship:
"Other curves are available..."
wrrr
Wow! Got the point. For people who do not know Discrete logarithm and Diffie Hellman, first learn that. Then come back to this. Thank you Sir for the upload.
I've been thrown into an encryption project at work and these videos are massively helpful, thanks!
4 years later
Amen
@Typical Gamer fyi I failed terribly, the project was on implementing a specific attribute based encryption policy, and I couldn't get thru step 1: UNDERSTAND THE PAPER!
What systems were you implementing it?@@kaushikdey6333
Gotta love computerphile: I was just studying the eliptic curve diffie hellman protocol and this video shows up!
damn ... i've read so many explanations/papers/articles on ECC and this is by-far the best explanation i've come across. thanks :))
WOW you explain that in such a simple way , that everybody can understand it ( thank you so much )
Please please please please more about cryptography. In today's day and age we should (we'll I do, any way) want to know everything we can about how it works. Perhaps more about SSL or GPG keys, what they are, their structure, and how signing and verification works with them and how they work. I've always wanted a little more in depth explaination on how Private and Public keys work too. How exactly can you encrypt with one, but NOT decrypt with the same key?? Mind boggling. You guys are fantastic, keep it up. I watch videos where I already know the broadstrokes answers, and I still can't help but learn more. Fantastic. Ty
I love these types of videos so much
Read _Dual EC: A Standardized Back Door_ by Daniel J. Bernstein
, Tanja Lange ,and Ruben Niederhagen. If you want to know more about the backdoor.
i just got a server in the mail yesterday, his videos are so helpful.
I'd love to see a video about security backdoors! And please be as long and thorough as possible.
Great video, thanks for posting! I was wondering how do you find the cofactor of the eliptic curve? Is it the "n" number from "modulo n" divided by the order of "G" you can multiply by until you get to infinity?
Very nice and informative video! Loved it!
Great clarity love it!
as always, great explanation!
Thnx for the vid. Nice & clear explanation.
I understand elliptic curves better now!!! Thanks!!
I badly needed this
guys at computerphile all look so happy to do what they do
Finally!!!!.
We need IKev2 video !!!!!
Could you recommend any audiobooks on this topic, or cryptography in general, that are available on Audible?
Thanks I was wondering about this elliptic curve thing
Is this interchangeability between the modulus and eliptic curve something to do with Taniyama-Shimura? As that also talks about modular forms and elliptic curves?
the way he drew the curve was sick!
4:43 - "Eventually they will cycle back around..."
At this point, you can also use the number of complete cycles that your number goes around as an additional verification element. All those which have the right modulus, but have a different number of cycles should automatically get locked out, because, c'mon... They're trying to break in...
You need to tell us EVERYTHING!
thanx for this beautiful content
thanks for bringing some life to my S+ research, i appreciate it, trying to build an OpenVPN Server in Ubuntu 20.04 now
Is elliptic curve cryptography vulnerable to attack from sufficiently powerful quantum computers? If so then what are some asymmetric cryptographic methods that are secure against quantum computers?
I'm a bit confused by the end of the video where we're told that people choose a particular curve. Does that mean that the constants a, b, and N are publicly known?
If you know a, b, and N, couldn't someone with lots of computing power, say a large government, pre-compute a table that will help them crack the code?
Yes and no, the curve is fixed, because it takes a whole lot of effort to generate a curve, that is secure (meaning g, does not cycle to early, and some other things).
But precomputing is not really an issue because this would take to much time.
Same goes for classic Diffie Hellman and the prime number and g
anon8109 with modular arithmetic many, many inputs can produce the same output. Remember the clock face? You know where the clock started and where it stopped, but how many times did it go around? 1? 1 million?
Yes pre-computing is possible and its a serious problem. Usually its not practical but if many people use the same curve then the effort needed is worth it. Unfortunately generating a new curve that doesn't have any inherent flaws is a problem. I believe there are security companies working on creating a diverse set of strong elliptic curves.
@@alexanderf8451 No, it's not. Remember we are talking about 256 bits numbers, which is about 10^77. Remember that the number of atoms in the milky way are "just" 10^68. You couldn't pre-compute that many numbers in a thousand years.
was that elliptic curve random number generator backdoor intentional or accidental? if intentional, do we know who or what group intended it?
The "number of jumps" number at the end looks to be high enough you couldn't reasonably compute that many jumps even if it's very fast, so I'd like to see something about how that's done.
Can someone tell me where I can find the code he uses to show the difference between Diffie Hellmann protocol and DIffie Hellman to Elliptic Curves? Thanks
Is this related to the Taniyama-Shimura Conjecture and Andrew Wiles' proof of Fermat's last theorem? I seem to recall that he proved that all elliptic curves were modular, or something similar. Or is this a different use of the term "modular?"
As far as I understand the nth G point can be calculated fastest only in linear complexity ? So we cant go for( n>>1e10~12) , am I right ?
When are we getting a video on Simultaneous Authentication of Equals?
thanks for these videos
Great video. I have a question, if you have the power potencial to multiply your private key and the "generator point" to get your public key, can you get the private key if you have the public key and the "generator point"? I mean iterating over and over and saving every result until match with your public key (that can be the same process that you used to get it at the first time)
Thanks
because 2²⁵⁶-1 is a bigggggg number.
@@leon-do is that the number of iterations? I presume, then, that the public key can be computed directly with an easy calculation, even for such a big number, and that iterating each point by adding the generator to itself is *not* the calculation being done in the protocol. Am I right?
In the late 90s I remember using Mathematica to factor a huge number that Knuth had put in his book and believed to be unfactorably large. Well, Mathematica's factoring routine claimed a basis in "elliptic curve" analysis. So the name of this cryptographic technique here masks a very powerful cracking technique, it seems.
Elliptic curves can also be used in factoring numbers. Not the same algorithm.
"elliptic" pops up a lot of places in maths and doesnt always relate!
Any thoughts on the security/vulnerability of secp256k1?
I like the FIPS 186-3 521 bit curve secp521r1 for ECDSA SSH keys because it's using a Mersenne prime and Mersenne primes are cool.
Can you explain how to find the number of points on big elliptic curves?
3:50
GIFed it😂
If you just send the x coordinate and not the y, shouldn't you also send the parity or sign of y? Looking at the equation, it looks like there are two solutions for y. How do you distinguish between them?
Love the prof's rubicks cubes.
Thank for this nice introduction to ECDH concepts, showing tangents from real numbers on a curve. 5 years later, can we get a part 2 describing how it actually works, please?
At 4:18 "we also do this all modulo N, because that's how the math (really) works, in fact it doesn't look like a curve any more"
We saw how standard DH is done modulo N, maybe after seeing ECDH done with the actual modulo N steps we can understand why (at 5:18) it's harder to solve than the DLP.
Skipping the math detail for now, is this (harder to solve) why the 256-bit ECDH key is "the same thing" (7:06) as the almost 2000-bit DH key? If so, there must be algorithms that solve the DLP in much fewer steps then doing it "brute force" (try all numbers 1 at a time until 1 works), but the best known ways to reverse ECDH are not much quicker than brute force - right?
which video covers more of the ECDH's Ephemeral
Are those floating-point operations though or is it all done with integers? And how aren't rounding errors a problem either way?
I think integers are more commonly used because they can be calculated faster.
If rounding rules are the same for both parties this shouldn't be a problem.
It's all integers. Calculating a sum of two points uses only multiplication and addition, and if do it modulo N, everything works as expected.
Cryptography always uses integers, though usually with special implementations of basic arithmatic operations to handle large numbers (larger than 64 bit)
That's why it's done modulo a large prime. With the modular arithmetic, there are no rounding errors.
The calculations are being done over a finite field (Integers modulo P). Thus, division is done by calculating the modular inverse of a number. For example, over Z_5, 2^-1 = 3 since 2*3 = 1 mod 5
What happens if g is at the intersect with the x-axis? No other tangent points right? But still the probabilitity it reaches exactly that point is zero and therefore this does not pose a problem right?
I heard that NIST modified the s-boxes in DES when it was first adopted and, in hindsight, those modifications made its longevity much greater as new encryption breaking algorithms were invented. It was the last man standing for a while. Shows that NIST could break it before it was even adopted!
I've always been curious what characteristics of mathematics produce functions that are easy to go "in" but hard to go "out," like what he's getting at here. Hashes, too. What steps did the originally folks who came up with this take to determine how to construct the math such that we get these... "diodes."
Could you please do a video on Elliptic Curves Pairings?
Mike Pound yesssssss
Explanation was spectacular, But the facial expression @ 4:51 😂 was the best part
Watching computerphile for the first time made me miss numberphile too much.
Can u make a video on how to implement Elliptic curve cryptography and explain the code ? 🙏🏻
Can you please do a video on lattice cryptography?
More, please. More.
with elliptic curves, is it guaranteed that "adding g's" over and over will never hit the same point?
I’m guessing no, but as long as the number of iterations is kept private it doesn’t matter because there’s no way of knowing what that is (unless it’s 1 which isn’t very useful).
Wait a minute, you glossed over something important. Why does this work? Why do Alice and Bob arrive at the same final value? What does "modulus" mean when it's performed on an x,y coordinate?
Modulo is the same on coordinates as it is on scalers. Just instead of looping about a number line your loop around a geometric shape. As far as what shape, depends on the rest of the math involved as this video demonstrates.
0:53
Elliptic Curve
2:04
Generator and dimensions.
4:56
Elliptic Curve security.
6:44
Generators.
7:51
Backdoors.
The talk about the curve with a backdoor is about than number that was calculated by the NSA and presented as a large prime number but it actually had a divisor? Or something like that... :)
Yay finally!
GO INTO MATHS. PLEASE!!!
I'm not sure if a whole video of finite fields would be better on Numperphile or Computerphile. Definitely one of my personal favorite topics in math, though. Beautiful and totally unexpected.
Thank you!
how come it's slower then? (talking about the backdoor video)
hmmm... maybe if we know the endpoint nG *and* the previous point (n-1)G, we can iteratively reverse this whole thing to get the original point?
these type of stuff is what make me want to do lots and lots of math but i was never shown any applications in my education time
Perfect !!!!
8:03 I would like to see the video about the random number generator backdoor
I like the fact that the more animated he gets, the more he sounds like he's about to start a soccer riot
How do you apply ellipitical curve cryptogrphy on your mobile device
Since we've talked about elliptic curve, let's also talk about Ed25519 and Curve25519 as well!
Yea that precedent for being suspicious is a pretty big one, damn NSA
talk about Dual Elliptic Curve Deterministic Random Bit Generator
Question: why it's easy to encrypt (finding the end point) when given the secret number "a", but hard to break the encryption by brute-force finding out "a". Dont they require the same amount of computation?
They don't some calculations are easier to go in one direction than in reverse - a simple example, square root and squares of a number, see which one is easier to do
You can factory aG with the nearest power of 2. This is the trick with ecc you can multiply by 2 or add 2 point easily. Example for a=1024, instead of adding 1024time, you multiply only 10 times, using the last discovered point everytime. To brute force you would need to do it 1024 time instead of 10.
hey computerphile? please make a playlist out of these cryptograpy videos.
Take a shot every time he says "Diffie-Hellman" 😆
8:02 Got to love for shadowing
For anyone wondering, the elliptic curve discrete logarithm problem is MUCH harder to solve than the diffie hellman problem. A 512 bit elliptic curve modulus has around the same security as a 15,360 bit diffie-hellman or RSA modulus.
That face at 4:50 should have been used as a thumbnail! :D
Thanks for the video =)
Can you alsow make a vidio aboout Elliptic Curve Digital Signature Algorithm (ECDSA)?