Elliptic Curves - Computerphile

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

[@zusurs]

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.

[@jimkd3147]

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.

[@michaelpound9891]

Very nicely corrected, Jim. Thanks!

[@baatar]

Is that why the y value is compressed as a 0 or 1?

[@frigga]

hey Jim, could you explain in a a very basic mathematical way how EC is used for encrypting/signing data, and retrieving it?

[@Pimp-Master]

frigga They never say why this system is better than any other system!

[@frigga]

@@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.

[@Petertronic]

He just loves saying "Diffie-Hellman" 😆

[@6612770]

ForestCat_Peter I think the name came from the initial attempts at solving this problem... "Golly, this one sure is a diffie. Hell, man..."

[@damejelyas]

Saying it is so satisfying to the lipse

[@Wabajak13]

and I love hearing him say it....

[@charlespustejovsky7187]

I mean... don't you? :P

[@jag831]

we all do

[@ElagabalusRex]

I always appreciate new entries in the Diffie-Hellman Cryptographic Universe.

[@ewenchan1239]

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. :)

[@xdmeister]

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!

[@alemutasa6189]

Finally a new Mike Pound video. I missed you, man

[@literallybiras]

Brailsfor so good too. And Mike is just sharp on theese topics

[@wesleyesterline7454]

Would love to see a video about the back door mentioned!

[@daggawagga]

Didn't they already made a video about that one?

[@Toschez]

Daggawaggaboof Yeah, there’s one on Numberphile.

[@ChaimS]

It's on computerphile now too.

[@christiandalton6496]

Amazing instructor who has the very unique ability to break very technical topics into an easily understandable video. Thank you!

[@StreuB1]

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!

[@cade2770]

Algebraic geometry and algebraic number theory doesn't use calculus much

[@benjaminwilson9007]

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.

[@AdamReece87]

I really like these videos from Dr Pound. Already looking forward to a video on different curves. :)

[@Acid113377]

Yet another great explanation by Dr. Mike Pound. Great stuff, thanks so much!

[@Roberto-dd1te]

Love this series about cryptography. Please keep on with it.

[@LightTheMars]

Yeah, it's Mike again! Always glad to see that cheeky guy.

[@richardjohnson4729]

Thanks for another cracking explanation.

[@YannStoneman]

Could you recommend any audiobooks on this topic, or cryptography in general, that are available on Audible?

[@lirothen]

I've been thrown into an encryption project at work and these videos are massively helpful, thanks!

[@kaushikdey6333]

4 years later Amen

[@kaushikdey6333]

@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!

[@RoxusRemo]

What systems were you implementing it?@@kaushikdey6333

[@JeaneAdix]

I love these types of videos so much

[@amandacapsicum686]

A cryptographer, flirting with someone in a monogamous relationship: "Other curves are available..."

[@zes3813]

wrrr

[@thijmenketel]

Gotta love computerphile: I was just studying the eliptic curve diffie hellman protocol and this video shows up!

[@michaelmulligan5192]

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

[@GegoXaren]

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.

[@lukepapapetrou1234]

I'd love to see a video about security backdoors! And please be as long and thorough as possible.

[@LittleRainGames]

i just got a server in the mail yesterday, his videos are so helpful.

[@ArjunSutar]

I am become FAN of you now. You are amazing in explaining the concepts. Awesome.

[@sasamilic720]

damn ... i've read so many explanations/papers/articles on ECC and this is by-far the best explanation i've come across. thanks :))

[@atulsharma4501]

Finally!!!!. We need IKev2 video !!!!!

[@parbelloti3767]

WOW you explain that in such a simple way , that everybody can understand it ( thank you so much )

[@alejandroamoros5339]

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?

[@tomassavenas1266]

as always, great explanation!

[@jsridhar72]

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.

[@SuperElephant]

Very nice and informative video! Loved it!

[@leonjones7120]

Great clarity love it!

[@SiddheshNan]

I badly needed this

[@nakulghate9448]

the way he drew the curve was sick!

[@okeuwechue9238]

Thnx for the vid. Nice & clear explanation.

[@nullptr.]

Thanks I was wondering about this elliptic curve thing

[@MMABeijing]

guys at computerphile all look so happy to do what they do

[@anon8109]

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?

[@benjaminlieser8148]

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

[@SpeakShibboleth]

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?

[@alexanderf8451]

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.

[@raphi72]

@@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.

[@AndrewTaylorPhD]

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.

[@vrushabhpatil2867]

thanx for this beautiful content

[@Jako1987]

You need to tell us EVERYTHING!

[@theslightlyhillyrider969]

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?

[@andrewxc1335]

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...

[@JWY]

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.

[@alexanderf8451]

Elliptic curves can also be used in factoring numbers. Not the same algorithm.

[@GamerTheTurtle]

"elliptic" pops up a lot of places in maths and doesnt always relate!

[@crogersdev]

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."

[@mopitz199]

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

[@leon-do]

because 2²⁵⁶-1 is a bigggggg number.

[@airex12]

@@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?

[@davidgillies620]

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.

[@nikanj]

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?

[@jacobshin4279]

I understand elliptic curves better now!!! Thanks!!

[@chriswilson1853]

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?"

[@mietschj]

When are we getting a video on Simultaneous Authentication of Equals?

[@pierreabbat6157]

Can you explain how to find the number of points on big elliptic curves?

[@lukecage1725]

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 ?

[@lesthompson608]

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!

[@unvergebeneid]

Are those floating-point operations though or is it all done with integers? And how aren't rounding errors a problem either way?

[@__mk_km__]

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.

[@vytah]

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.

[@sundhaug92]

Cryptography always uses integers, though usually with special implementations of basic arithmatic operations to handle large numbers (larger than 64 bit)

[@PvblivsAelivs]

That's why it's done modulo a large prime. With the modular arithmetic, there are no rounding errors.

[@JonJon2040]

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

[@razvanpaulbirgaoanu2768]

Could you please do a video on Elliptic Curves Pairings?

[@krisstenxd98]

thanks for these videos

[@JMacSD]

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?

[@DANJONPEARCE]

thanks for bringing some life to my S+ research, i appreciate it, trying to build an OpenVPN Server in Ubuntu 20.04 now

[@sharwaribaikar2864]

Can u make a video on how to implement Elliptic curve cryptography and explain the code ? 🙏🏻

[@kinloo3778]

which video covers more of the ECDH's Ephemeral

[@matt-in8td]

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

[@MacoveiVlad]

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... :)

[@dillonmaggiano5415]

Any thoughts on the security/vulnerability of secp256k1?

[@kvelez]

0:53 Elliptic Curve 2:04 Generator and dimensions. 4:56 Elliptic Curve security. 6:44 Generators. 7:51 Backdoors.

[@marcandreservant8824]

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?

[@m1ddleagemadness]

Can you please do a video on lattice cryptography?

[@cfsscfsshk]

How to generate my own curves? What do I need to consider/limitation/consequence when I do so?

[@alexanderf8451]

Generating elliptic curves is easy if you known a little about modular arithmetic and finite fields. If you're using them for actual encryption? Don't. You shouldn't be doing that unless you're a professional cryptographer. The details are well beyond YT comments.

[@cfsscfsshk]

For actual encryption, any reference for me to start with? Actually, I want to try my best to understand it before I give up. When I look around, all references say don't. But seems there is no reference on why don't. So I asked this question. Maybe the consequence is easy to crack? Or even don't work as the number may not be uniquely mapping to one another? Or the points would end up repeating sooner than expected as the curve is too symmetric, that's why? If it is easy to crack, maybe I want to try to crack it myself, and try the same method against standard curve and feel the difference myself.

[@GeoffryGifari]

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?

[@thebobbrom7176]

8:02 Got to love for shadowing

[@TG-vy3vs]

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?

[@aravindpallippara1577]

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

[@jpp59]

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.

[@chiquiflautro]

+Computerphile "a" and "b" in the elliptic curve equation are not the same as the "a" and "b" secrets, right?

[@Dsiefus]

a and b are the curve parameters, and they are public. He should've used other letters for the secrets.

[@jarredallen3228]

That is correct. The a and b in the equation of the curve are publicly agreed upon values (just like the n in regular diffie-helman).

[@jarredallen3228]

thom1218 Alice does not get to Bob's secret. That's why it's called a secret.

[@thom1218]

+Okay Jarred.... how do they derive their ...shared... secret?

[@thom1218]

For anyone who cares: Multiplying both private keys and the base point together will produce a point along the curve (since it is multiplied with G). As long as both Alice and Bob receive each others public keys, multiplication will be commutative and they will both compute the same point R without ever explicitly knowing each others secret integer.

[@vaibhavsingh9x]

Love the prof's rubicks cubes.

[@An.Individual]

8:03 I would like to see the video about the random number generator backdoor

[@arjitsrivastav555]

Explanation was spectacular, But the facial expression @ 4:51 😂 was the best part

[@bartvancampenhout2989]

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?

[@Stars-Mine]

Yea that precedent for being suspicious is a pretty big one, damn NSA

[@dannyniu4268]

Since we've talked about elliptic curve, let's also talk about Ed25519 and Curve25519 as well!

[@MrWazzup987]

talk about Dual Elliptic Curve Deterministic Random Bit Generator

[@icedragon769]

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?

[@eideticex]

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.

[@heni1233212]

Can you alsow make a vidio aboout Elliptic Curve Digital Signature Algorithm (ECDSA)?

[@eatbolt42]

More, please. More.

[@brickbuffalo6147]

3:50 GIFed it😂

[@Ribby00]

Mike Pound yesssssss

[@jasdfpasdfakdsjhfa]

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.

[@PawelKraszewski]

Thank you!

[@suhaibkhan4956]

please, someone, explain to me how to map the message with the co-ordinates of an elliptic curve.

[@ginobean737]

was that elliptic curve random number generator backdoor intentional or accidental? if intentional, do we know who or what group intended it?

[@gustavoisaza2729]

Perfect !!!!

[@nicohambauer]

If basically encryption is a g^a mod q operation. And basically hash functions, to my knowledge, also include a mod operation. Why do we say public key encryption is not relying on hash functions, because „they need to be reverse able“? They are not right? At least for someone who does not have the corresponding key

[@reidflemingworldstoughestm1394]

I like the fact that the more animated he gets, the more he sounds like he's about to start a soccer riot

[@regimantasvaineikis980]

Make a video on the maths please

[@oscarsmith3942]

GO INTO MATHS. PLEASE!!!

[@alexanderf8451]

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.

[@lydiaowusu9603]

How do you apply ellipitical curve cryptogrphy on your mobile device

[@jmlt-zb8px]

Watching computerphile for the first time made me miss numberphile too much.

[@yash1152]

hey computerphile? please make a playlist out of these cryptograpy videos.

[@TednTin]

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

[@FlumenSanctiViti]

That face at 4:50 should have been used as a thumbnail! :D