Elliptic Curves - Computerphile
HTML-код
- Опубликовано: 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
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.
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 always appreciate new entries in the Diffie-Hellman Cryptographic Universe.
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. :)
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
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.
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!
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
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.
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!
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.
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 am become FAN of you now. You are amazing in explaining the concepts. Awesome.
Gotta love computerphile: I was just studying the eliptic curve diffie hellman protocol and this video shows up!
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.
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.
A cryptographer, flirting with someone in a monogamous relationship:
"Other curves are available..."
wrrr
WOW you explain that in such a simple way , that everybody can understand it ( thank you so much )
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
I love these types of videos so much
I'd love to see a video about security backdoors! And please be as long and thorough as possible.
i just got a server in the mail yesterday, his videos are so helpful.
damn ... i've read so many explanations/papers/articles on ECC and this is by-far the best explanation i've come across. thanks :))
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...
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?
Could you recommend any audiobooks on this topic, or cryptography in general, that are available on Audible?
Great clarity love it!
Thanks I was wondering about this elliptic curve thing
Thnx for the vid. Nice & clear explanation.
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?
Very nice and informative video! Loved it!
as always, great explanation!
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.
the way he drew the curve was sick!
guys at computerphile all look so happy to do what they do
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 ?
I understand elliptic curves better now!!! Thanks!!
You need to tell us EVERYTHING!
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.
Finally!!!!.
We need IKev2 video !!!!!
I badly needed this
was that elliptic curve random number generator backdoor intentional or accidental? if intentional, do we know who or what group intended it?
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
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
0:53
Elliptic Curve
2:04
Generator and dimensions.
4:56
Elliptic Curve security.
6:44
Generators.
7:51
Backdoors.
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?
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?"
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.
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!
thanks for these videos
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!
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
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?
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?
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?
3:50
GIFed it😂
Any thoughts on the security/vulnerability of secp256k1?
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?
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.
Love the prof's rubicks cubes.
Can you explain how to find the number of points on big elliptic curves?
Thank you!
Mike Pound yesssssss
When are we getting a video on Simultaneous Authentication of Equals?
which video covers more of the ECDH's Ephemeral
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... :)
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."
Perfect !!!!
Can you alsow make a vidio aboout Elliptic Curve Digital Signature Algorithm (ECDSA)?
how come it's slower then? (talking about the backdoor video)
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.
8:02 Got to love for shadowing
Explanation was spectacular, But the facial expression @ 4:51 😂 was the best part
It's backbone of all our computer security, yet almost no one really understands it. Furthermore there are curves that are practically universally considered secure by experts from different sides of the debate, yet those are the ones that are used less, while there's controversy around the more popular ones like NIST P-256. Not that it's proven to be insecure, but we can't be sure.
So why use it then? That's the opposite of safety, that's faith in a government agency to not be lying, despite common sense and historical precedents indicating we should do the opposite.
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?
More, please. More.
How do you apply ellipitical curve cryptogrphy on your mobile device
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
Can u make a video on how to implement Elliptic curve cryptography and explain the code ? 🙏🏻
please, someone, explain to me how to map the message with the co-ordinates of an elliptic curve.
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.
Since we've talked about elliptic curve, let's also talk about Ed25519 and Curve25519 as well!
Yay finally!
Yea that precedent for being suspicious is a pretty big one, damn NSA
Could you please do a video on Elliptic Curves Pairings?
talk about Dual Elliptic Curve Deterministic Random Bit Generator
Watching computerphile for the first time made me miss numberphile too much.
Thanks for the video =)
That face at 4:50 should have been used as a thumbnail! :D
8:03 I would like to see the video about the random number generator backdoor
How is that both parties (alice and bob) agree on the same point G?
Can you release the python source code for generating both elliptic and the older key method?
pycharm nice!
Take a shot every time he says "Diffie-Hellman" 😆