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

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

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

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

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

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

[@alemutasa6189]

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

[@literallybiras]

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

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

[@christiandalton6496]

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

[@amandacapsicum686]

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

[@zes3813]

wrrr

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

[@JeaneAdix]

I love these types of videos so much

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

[@ArjunSutar]

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

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

[@thijmenketel]

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

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

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

[@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 :))

[@LittleRainGames]

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

[@leonjones7120]

Great clarity love it!

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

[@parbelloti3767]

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

[@lukepapapetrou1234]

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

[@tomassavenas1266]

as always, great explanation!

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

[@okeuwechue9238]

Thnx for the vid. Nice & clear explanation.

[@SiddheshNan]

I badly needed this

[@MMABeijing]

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

[@arjitsrivastav555]

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

[@nakulghate9448]

the way he drew the curve was sick!

[@Jako1987]

You need to tell us EVERYTHING!

[@troglodytto]

Take a shot every time he says "Diffie-Hellman" 😆

[@atulsharma4501]

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

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

[@jacobshin4279]

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

[@nullptr.]

Thanks I was wondering about this elliptic curve thing

[@vrushabhpatil2867]

thanx for this beautiful content

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

[@kvelez]

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

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

[@YannStoneman]

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

[@mietschj]

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

[@krisstenxd98]

thanks for these videos

[@brickbuffalo6147]

3:50 GIFed it😂

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

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

[@pierreabbat6157]

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

[@ginobean737]

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

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

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

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

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

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

[@DANJONPEARCE]

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

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

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

[@vaibhavsingh9x]

Love the prof's rubicks cubes.

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

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

[@dillonmaggiano5415]

Any thoughts on the security/vulnerability of secp256k1?

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

[@sharwaribaikar2864]

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

[@razvanpaulbirgaoanu2768]

Could you please do a video on Elliptic Curves Pairings?

[@kinloo3778]

which video covers more of the ECDH's Ephemeral

[@reidflemingworldstoughestm1394]

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

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

[@ramdas363]

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.

[@Ribby00]

Mike Pound yesssssss

[@PawelKraszewski]

Thank you!

[@GeoffryGifari]

with elliptic curves, is it guaranteed that "adding g's" over and over will never hit the same point?

[@jackdavenport5011]

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

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

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

[@Stars-Mine]

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

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

[@FlumenSanctiViti]

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

[@jmlt-zb8px]

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

[@eatbolt42]

More, please. More.

[@thebobbrom7176]

8:02 Got to love for shadowing

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

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

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

[@m1ddleagemadness]

Can you please do a video on lattice cryptography?

[@lydiaowusu9603]

How do you apply ellipitical curve cryptogrphy on your mobile device

[@An.Individual]

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

[@Verrisin]

how come it's slower then? (talking about the backdoor video)

[@dannyniu4268]

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

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

[@MrWazzup987]

talk about Dual Elliptic Curve Deterministic Random Bit Generator

[@gustavoisaza2729]

Perfect !!!!

[@yash1152]

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

[@OthmanAlikhan]

Thanks for the video =)

[@ismetpilev869]

Yay finally!