Elliptic Curves - Computerphile

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

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

[@ElagabalusRex]

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

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

[@thomasfriedrich2001]

It is video "Elliptic Curve Back Door - Computerphile"

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

[@christiandalton6496]

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

[@alemutasa6189]

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

[@literallybiras]

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

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

[@Daidera91]

As a software developer that is not that math savvy, this was spot on and amazing! Thank you.

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

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

[@harveyp.1949]

This is the best explanation abt ECC I can find in the internet

[@kvelez]

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

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

[@richardjohnson4729]

Thanks for another cracking explanation.

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

[@LikelyToBeEatenByAGrue]

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.

[@fuzzywzhe]

No. The reason is the amount size of the table. To count from just 1 to 2^256 requires more energy than our sun will produce over its existence. That's how many possible combinations there are. You know G, the generator point. You can compute 2G, and 4G, 8G, very easily. When you can to know what 6G is, that's just point addition of 2G and 4G. You can just guess, for small numbers, but you have 256 numbers, and you have modulo arithmetic too. You need to find a combination of those 256 possible numbers that when they are added together, produces the public key. You can't just go through every possible combination, that takes too much time, too much energy and nobody knows if it's possible to simplify the calculation. Maybe it's possible, but nobody has figured it out. That's where the security of ECC rests.

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

[@Roberto-dd1te]

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

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

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

[@LightTheMars]

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

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

[@thijmenketel]

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

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

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

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

[@MMABeijing]

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

[@amandacapsicum686]

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

[@zes3813]

wrrr

[@nakulghate9448]

the way he drew the curve was sick!

[@ArjunSutar]

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

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

[@Ojile]

Actually yes . If you multiply the generator, or any point actually by the order of the curve, you'll return back to zero... Or the origin which is weird... I don't still understand why but that's what the implementation using ecdsa library in python does

[@sparkfrog777]

@Ojile I wonder if it’s similar at all to Fermat’s Little Theorem

[@sparkfrog777]

@Ojile I wonder if it’s similar at all to Fermat’s Little Theorem

[@Ojile]

​@@sparkfrog777 Interesting observation, but actually they aren't related at all... I did a little digging and found why it does this... Think of the elliptical curve as a number line with a prime number of points (the large prime field they're always talking about - actually, the order of the curve...) - with the origin at the beginning and the largest point at the end, the curve is designed in such a way that if you double a large enough point, since there isn't more points left, it'll start back at the beginning. Sort of like a wrap around kind of thing... So no matter the point, whatever it is on the number line, when doubled the number of times as the order of the curve, it'll always come back to the origin... (A little confusing but it'll make sense if you really think about it)

[@parbelloti3767]

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

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

[@unvergebeneid]

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

[@creature_of_fur]

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

[@JeaneAdix]

I love these types of videos so much

[@Jako1987]

You need to tell us EVERYTHING!

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

[@DoTheNeedful0]

Not harder, slower. Hardness is a different definition.

[@atulsharma4501]

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

[@parthivdebnath9941]

Can you please explain Quantum Key Distribution protocols like BB84, B92, and E91 protocols? and Lattice Cryptography?

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

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

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

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

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

[@ginobean737]

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

[@Secrets_of_the_Sun]

It was intentional. I believe the NSA had found exploitable parameters and encouraged people to use them so they could take advantage of the (publicly unknown) special properties of those choices.

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

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

[@paviad]

Do points on the curves always have integer coordinates?

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

[@DoTheNeedful0]

No, little one. Weierstrass functions parameterize a lattice C/A to E/C. L-functions parameterize a modular form f to E/Q. It has got nothing to do with E/F_q

[@An.Individual]

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

[@KirilMilanov-y9x]

Great video. One question. How does a x b x G get converted to a single number that is the actual shared secret

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

[@jacobshin4279]

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

[@SiddheshNan]

I badly needed this

[@DANJONPEARCE]

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

[@dillonmaggiano5415]

Any thoughts on the security/vulnerability of secp256k1?

[@pierreabbat6157]

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

[@MrWazzup987]

talk about Dual Elliptic Curve Deterministic Random Bit Generator

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

[@mietschj]

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

[@vishalmishra3046]

Elliptic curve equation is y^2 - x^3 = a x^2 + b x + c NIST and NSA chose a = 0, but DJB chose c = 0 making X/Ed 25519/448 much safer than P-256/384/521 curves.

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

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

[@okeuwechue9238]

Thnx for the vid. Nice & clear explanation.

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

[@nullptr.]

Thanks I was wondering about this elliptic curve thing

[@OscarAlsing]

🚀 BOB LEAVE ALICE ALONE! 🚀

[@Robertlavigne1]

I'm more worried about Mallory. Not often mentioned, but always lurking in the corner.

[@damejelyas]

Bob and alice and their secret love.

[@pecky1234]

In fairness, it's always Alice trying to talk to Bob...

[@RandomNullpointer]

Actually it's Alice that started the conversation

[@yash1152]

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

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

[@arjitsrivastav555]

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

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

[@KlashLaker]

Nice video...incomparable to "Hello Frans" Indian videos

[@kinloo3778]

which video covers more of the ECDH's Ephemeral

[@JM-us3fr]

Why hasn't numberphile talked about this?

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

[@troglodytto]

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

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

[@Stars-Mine]

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

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

[@regimantasvaineikis980]

Make a video on the maths please

[@Jkauppa]

closed form Integral of the elliptic integral of second kind sqrt(1+c*sin^2(x) ] dz = (2/3)*csc^2(x)*(c*sin^2(x)+1)^(3/2), just make sure the c-variable is negative, c=-k^2. also closed form solution of the elliptic integral of first kind: Integrate (1 + v sin^2(x))^(-1/2) dx = 2 csc^2(x) sqrt(v sin^2(x) + 1).

[@Jkauppa]

stop m00-wing

[@Jkauppa]

no service for you, no more secrets

[@Jkauppa]

thanks, I'll take your keys

[@GammaMatrix]

did he just draw the point g such that he could use the point he drew before in the process of adding g to itself?????????? what a master

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

[@TeflonTelStar]

When you are bouncing around, what if you hit that point where y=0, where you gonna go next?

[@razvanpaulbirgaoanu2768]

Could you please do a video on Elliptic Curves Pairings?

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

[@chrissandi9985]

How is that both parties (alice and bob) agree on the same point G?

[@YannStoneman]

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

[@SuperElephant]

Very nice and informative video! Loved it!

[@dannyniu4268]

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

[@vrushabhpatil2867]

thanx for this beautiful content

[@leonjones7120]

Great clarity love it!

[@sharwaribaikar2864]

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

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

[@DoTheNeedful0]

See modular forms.

[@ducnguyen4973]

I prefer this kind of video than going too deeply into maths. We can read the math details in some books.