Elliptic Curve Diffie Hellman

[@trogdorstrngbd]

Many have said this already, but this is by far the best explanation I have seen for Elliptic Curve Diffie-Hellman in any medium ever. The world needs more people like you to be teachers.

[@robertpierce5142]

Thanks for the compliment! It made my day!

[@3rdman99]

Agreed. I scoured Internet all over today the whole day to find anything that gives me the basic understanding of ECDH, and this is the only one that made sense to me so far.

[@fuzzywzhe]

It's quite clear governments don't want people to understand cryptography, much less use it in my opinion. What screwed me up is that this is very different than RSA in that in RSA, the secret key is recovered, and in this, it's not. I'm doing some work with the libsodium library BTW - if anybody knows if their mailing list is still up, let me know. I've tried to sign onto it many times with no success.

[@mtare8942]

I wish all teachers would be able to put something like this for everything . THIS IS THE SIMPLEST SIMPLEST EXPLANATION By Far. Thank you.

[@robertpierce5142]

Wow, thank you!

[@garry137]

This is the most concise explanation of ECC that I ever learned. Great video! Thanks for taking time to put it together.

[@zes7215]

wrg

[@fantaaa61]

Even after six years... Still the best, and by far, simple explanation of elliptic curve cryptography. No way too complicated math statements and no oversimplified kids drawing explaining what a public key is. Many thanks :D

[@fantaaa61]

Not sure if it already has been mentioned but at 11:27 bob computer P with small a and b. This is impossible, right? As bob has no access to small a. It should be big A if I am correct.

[@robertpierce5142]

@@fantaaa61 Sorry for the late reply ... You are correct, Bob does not know what small a (alpha) is. Bob only sees big A. I just show that big A = alpha*G to demonstrate that Bob and Alice are indeed computing the same thing since the point addition operation is commutative.

[@omargaber3122]

Even after seven years... Still the best simple explanation of elliptic curve cryptography , thank you very much

[@94rainbowx33]

Let's be honest, this guy has a real talent for explaining things.

[@SusheelAryarocks]

Agreed

[@PawanBathe]

I am not a person who typically comments on videos on youtube, but this is really concise and clear definition on one of the most difficult topics on ECC, you deserved appreciation Robert, big thank you!

[@robertpierce5142]

Thanks Pawan, I really appreciate it.

[@MMABeijing]

This video is the clearest explanation of ECC. I was starting to give up on getting the big picture and I am grateful to having found this gem. Thank you Sir

[@lappdev5071]

The Best Explaination in under 20 minutes EVER. Salute brother ;)

[@robertpierce5142]

Thanks!

[@WTHNoSpam]

Excellent. I always enjoy the magical feeling of explaining to people about how the modularity of the multiplied secret at the end for Bob and Alice and watching people 'get it' (if only for a short while.)

[@slobodandobrijevic1374]

I have been looking for some clear explanation related to ECC and this is by far the best I have found.

[@robertpierce5142]

Thanks, I’m glad it helped

[@drone2369]

I cannot like this video enough. Better than any textbook explanation! Thank you Rob!!!!

[@rahulgomes4823]

By far the best example of elliptic curves out there..

[@robertpierce5142]

Thanks!

[@asilbekergashev6788]

Someone is going to impress their maths teacher tomorrow

[@youtubepooppismo5284]

did you impress your maths teacher 5 yeas ago?

[@quickyummy8120]

😅😅😅

[@joshcampbell402]

Thank you for this, I've understood how to do Diffie Hellman and can whiteboard it from memory, but this finally made ECDH click for me.

[@riccardoandreetta9520]

low levels details of this magic stuff is probably not really understandable by normal people, but this video makes it appear to be so simple (even though I still believe it's just not). Thank you !!!

[@donha475]

I still don't get it. How do you add two positive y coordinates together and end up with a negative y coordinate!?? WTH!

[@philippdolomit4830]

Best explanation ever and I have seen many videos already. Thanks 👍

[@pkpio]

The best ECDH video! Short, to the point and the depictions and font are neat!

[@shubhamshourya7518]

concise and clear. thanks a lot for this video. helped a lot for tomorrow's cryptography exam.

[@SusheelAryarocks]

Man Best explanation of ECC. I am subscribing😄

[@jeankhawand5539]

Great explanation. Thank you for taking the time to provide a simple explanation.

[@robertpierce5142]

Thanks for watching

[@NoNTr1v1aL]

Absolutely amazing video! Subscribed.

[@hanskessock3941]

Excellent resource :) - was searching for something advanced maths students in middle school and this was perfect. Thanks! BTW, small typo on Alice/Bob page "Elliptic Curce Diffie Hellman" - typo. Apologies if people have reported this previously. Thanks again for making this.

[@jawadhussain8175]

One word for the video. AWESOME. I needed to know exactly this. Most concise explanation of ECC DH that i ever got to know. I thank you very much for the bottom of the heart for taking the time out to put together such an outstanding video. Please post more videos. And Yeah you have another subscriber :-)

[@averagesoup8432]

Man this video was amazing. Thank you for all that work. Crystal clear

[@robertpierce5142]

Thanks! Glad it helped!

[@anjalichaudhri8455]

Best explanation ever. Thank you very much.

[@robertpierce5142]

Thanks!

[@hsharma3933]

You’re right that it’s a key exchange protocol but more specifically it’s a key agreement protocol, where both parties contribute more or less, equally toward the creation of the symmetric key. On the other hand with RSA it’s more of a key transport, because (at least for server auth) it’s more along the lines of the client using the server public key along with the client and server random vectors to generate the premaster secret, which is then sent over to the server so the server and client both independently generate the master secret (symmetric key).

[@arunkumarsaravanan7875]

Single video with more contents...wow...looks awesome

[@Devashish18081]

Thank you sooo much! This helped my major doubt. I was struck on how to perform scalar multiplication of end. This helped me clear it.

[@parwinderdhillon4094]

thank you so much for such a simple and easy understanding on ECC... great video...

[@chandravaranasi2535]

Absolutely great video. Never watched a better explanation!

[@vikas_chaube]

Great video, love the way things have been explained. Thank you.

[@lance3401]

I'm learning refreshing my math knoledge, this is more like calculus and albregra II, will take time to fully do all the pre-requisites to fully implement in a crypto, but I love it, it almost has all the incredients but then transform to programming language algorithnms.

[@IqbalSyamil]

Thanks, this video really helps me to understand ECC.

[@andrewclarke598]

Fantastic! Great job. Thanks for taking the time to make this video.

[@mrvargarobert]

I think it is y_p = 0 at 5:27 instead of x_p.

[@robertpierce5142]

You are correct. That correction was made, but unfortunately it doesn't show up on mobile devices.

[@lemague]

@@robertpierce5142 Emmm, but if you are doing P+P, then obviously you fall in the first case, since x_p is always equal to x_p. So P+P is always infinity? Or the first rule only applies when P != Q?

[@KristofVydt]

@@lemague 1) P+Q=O if xp=xq and yp!=yq This is when the line connecting P and Q is parallel to the Y axis. In case both xp=xq and yp=yq, that implicates P=Q making P+Q=2P. 2P with xp=0 coincides with the Y axis and hence =O. 2) P+P=O if yp=0 The line representing 2P runs tangential to the curve at P. Only if P is located at the spot where the curve crosses the Y axis, then the tangential line is parallel to the Y axis.

[@adde362]

Very good video, first complete explanation I found!

[@Jonasonweb]

Great Video and very good Explanation of ECDH!! Thumbs up.

[@a7medFCI]

Excellent explanation thank you for This great toturial

[@prabavathihariharan147]

an excellent method of explaining ECC, thanks

[@fuzzywzhe]

For people not too familiar with modular math: At 12:39 - modular division. 1/2 mod 17 is really this problem: What must x be for (2 * x) mod 17 == 1. In this case, it's 9. 2*9 = 18, 18 mod 17 == 1. There isn't always a solution depending on the modulo number, but I believe there always is provided that the modulo is prime.

[@robertpierce5142]

Thanks for that explanation. You are exactly correct. The modular arithmetic is what trips a lot of people up on this.

[@fuzzywzhe]

@@robertpierce5142 OK, since you responded to me, how do you compute Q=kP at 5:58? It can't just be repeated addition, how does multiplication actually work in this? This is all theory, and I know there are a ton shortcuts with modular math. What are they? You can't be doing just repeated addition, because that would be trillions or trillions of operations and Eve can do the same thing, it would be insecure. ALSO - what makes a weak curve? It would be interesting to know a curve that is ENTIRELY unsuitable for cryptography. No offense, but this might be beyond your knowledge, but it's certainly beyond mine. It's so hard to get information about cryptography. Also, is the modulo number always prime? Is it CERTAIN to be prime, or just pretty likely to be prime? I know in RSA, you have a very good chance of the numbers being prime, but they aren't proven to be prime. I was always curious if RSA would completely break if the numbers went through the battery of tests to assure the number was prime, but it wasn't. I guess I should review the math in RSA again, I've never tested it with relatively small numbers.

[@fuzzywzhe]

I understand how scalar multiplication can be done now, although it took a few days. if Y = X+X+X and Z = X+X+X+X+X+X also Z = Y+Y Is that correct? If so, then multiplication is being done the same way a computer did multiplication back in the 1980s and I see how that can be translated to an elliptic curve although I cannot see how the order is of the curve at generator point G is determined.

[@fuzzywzhe]

@@robertpierce5142 Well, I was hoping for some free information, and didn't get it. That's fine, this tutorial did help, and it does seem that if: X = 2P and Y = 4P Z = 8P that Y also can be computed with 2X and Z can be computed as 2Y or 4X. If this is true, then I understand how numbers like 485728378320273X is computed with the distributive property where you calculate just powers of 2,4,8,16 etc, and then use those powers to do point addition until you get the result. The distributive property was used extensively in multiplication on early machines lacking an FPU or ALU.

[@fuzzywzhe]

@@robertpierce5142 You won't likely see this, but I think I will do a write up on this now that I (think) I completely understand this. Now I'm wondering if you do NOT do modulo math during the process, until the very end, of the calculation, if you'll come up with the same result as if you did modulo math at each step. I have the distinct feeling that there is effort to prevent people from easily understanding how this precisely works. If people better understood how this worked, they would be free from libraries, and I know from experience many of them have been infiltrated by the NSA. For example I know the NSA bribed a company to weaken the the random number generation in their library, I think it was BSAFE, but I'm not positive that was the corporation. Their "random numbers" for private keys weren't really random. I'm working in NaCL (LibSodium), and I can control the random number generation with that. OpenSSH is a mess by the way, basic errors like buffer overflows. It's difficult not to imagine the "errors" are intentional, but they are unfixable in that the code is so convoluted and just simply terrible, no offense to the original authors, I think it's adulterated. It's overly complex, which isn't surprising with OLD code, but, my goodness, it's insanely complex and when working with security, you have to be very careful and knowledgeable, and I'm not there yet. Side channel attacks are interesting, but not realistic unless somebody has direct access to your device. You know how the NSA actually breaks into MOST devices? How they "crack" encryption? They install malware through back doors and just grab data directly. They don't actually crack the encryption at all. They just illegally break into your computer without a warrant with the cooperation of corporations that provide backdoors. Welcome of East Germany circa 1985, with modern technology.

[@TimJSwan]

If Eve is in control of the network, she can fake a public key that she generated herself for Bob's, giving Alice a public key that she generated. She does the same to Bob and from there, not only can read the conversation, but alter it as she pleases.

[@nimo1993]

+Tim-J.Swan That's why we need a signature from trustable authority to prove their identities.

[@ThatNateGuy]

+nimo1993, alternatively, social media (or perhaps personnel records e.g. in an enterprise) as a platform to host identity assertions. Have you heard of this concept of "social crypto"?

[@riccardoandreetta9520]

public/private key cryptography is not about solving the "man in the middle" (MITM) attack, which is the one you are describing. To solve this, you will need anyway to "trust" e third "entity", which provides certificates that are installed already in your browsers, to solve this kind of problem.

[@beback_]

All "textbook" Diffie Hellman constructions are vulnerable to Man in the Middle attacks. Does anybody know of a good source explaining how Diffie Hellman is done in practice? I really like to learn.

[@henrybirge-lee709]

Diffie Hellman alone will never be secure against a active adversary performing a Man in the Middle attack. As a key exchange algorithm, it is intended to bootstrap confidentiality given that the messages already have integrity. To secure a communication channel against MITM attacks the messages in the key exchange protocol are usually signed with the private key of the person sending the message using a digital signature algorithm. This way, anybody with Alice's public key can be sure that Alice not the adversary generated that message. Distributing these public keys is the role of the PKI and that is where the trusted third parties come in. In short, the missing theoretical piece of the puzzle worth to learn about is how a digital signature algorithm works. If you are really want to know the dirty secrets behind implementation, you should turn to the TLS protocol and how it is actually implemented.

[@appapurapu]

Great Video explaining the elliptic curve fundamentals

[@iomat9727]

Very instructive! Thank you very much for giving me a good lecture.

[@streetfighter1kz]

Good job! Thank you! Hello from Kazakhstan!

[@robertpierce5142]

Hello there!

[@haikalhawari1298]

Thank you so much for this explanation! Nicely done :)

[@user-rz1vm9fh3l]

Thanks for the very nice video. Overall, the basic concepts is explained well. Just got stuck briefly with the 2^(-1)mod17. Thanks to Chris de Corte for bringing that up. Now, I have to dig deeper to understand group theory as you mentioned in the comments. (*haven't tried to compute 3G,4G...19G, yet)

[@simiouch5128]

Amazing explanation! Thank you for explaining this!

[@samliao2393]

concise teaching video !

[@gundabalf]

this is some clearly explained shit right here

[@pineneedle]

Best video on ECC.

[@nitin-hp6ug]

Very informative video. Thanks!

[@RoBuceo]

Thx thx thx thx, This video is awesome, really nice explanation!

[@RoBuceo]

I have a doubt at minute 11:07. Bob computes P = Beta*Alfa*G, but Alfa is Alice private key. P shouldnt be P = Beta*A*G? and the same for P = B * Alfa * G?

[@Prvosienko]

Very good explanation. Thanks.

[@robertpierce5142]

Thank you

[@HajiAkhundov]

A great, succinct introduction! Thanks. p.s. I need to implement this in hardware.

[@robertpierce5142]

+Haji Akhundov Thanks! That sounds like a fun (but challenging) project.

[@HajiAkhundov]

challenging indeed

[@bluekaioken5924]

Awesome Video, nicely explain, understood everything, how about a video on Finite Fields, I can't find a good video, they're all over the place with their explanations, you sir explain everything very clearly.

[@jenspettersen7837]

_Lets just take it from the bottom. First you need to know what a group is._ A group is a set of elements with *one* operation (usually denoted # (operation that is similar to or is adding) or * (operation that is similar to or is multiplying)) The set have to fulfill these 4 requirements under the operation. 1. *There have to excist an identity e so that e*a = a.* Example multiplicative identity is 1 and additive identity is 0 since a*1=a and a+0=a. 2. *Every element have to have an inverse aˉ¹ so that a*aˉ¹=e.* Example multiplicative inverse of 2 is 1/2 and additive inverse of 2 is -2. 3. *The set have to be closed under the operation.* if the set is whole numbers then when you add two whole numbers you get a new whole number so it's a group. Multiplication is not a group on the set of whole numbers since the inverses are fractions. 4. *The set have to be assosiative under the operation which means (a*b)*c=a*(b*c)* A field is a special kind of ring, and a ring is a set with two operations (R, +, *) with the following requirements. 1. *The set is an abelian group under the + operation.* Abelian means a*b = b*a. 2. *The set is assosiative and have a multiplicative identity.* 3. *The set is left and right distributive under multiplication.* a*(b+c)=ab+ac and (a+b)*c=ac+bc For a field every non-zero element have to have a multiplicative inverse and multiplication have to be commutative too. A finite field is a field with a finite number of elements. Lets see if the elliptic curve operations define a field Group 1 axiom: The identity have to be "point at infinity" O, since if you do P+O the line would go straight up to O and come straight down to P again, so P+O=P. Difficult to show algebraically, but I think it must be so. Group 2 axiom: The inverse of P is -P Group 3 axiom: Since O is included in the set you will eigther end up on the elliptic curve or at O, thus it's closed. However I'm not sure where you have P+Q where P=(x_P, y_P) and Q=(x_Q, y_Q) where y_P = y_Q, but x_P is not equal to x_Q. Does that go to O too? Group 4 axiom: My gut feeling tells me (P+Q)+R=(P+Q)+R Abelian: just draw an elliptic curve and do the operation P+Q and Q+P and you'll see tha P+Q=Q+P Ring 1 axiom: see above Ring 2 axiom: Multiplicative identity is 1, assosiativity is more of a challenge. Ring 3 axiom: This is challenging too. Sorry for the lazyness of not calculating it. I mainly wrote this post to understand ECC my self.

[@jenspettersen7837]

TL;DR A field requires: Associativity of addition and multiplication: a + (b + c) = (a + b) + c and a · (b · c) = (a · b) · c. Commutativity of addition and multiplication: a + b = b + a and a · b = b · a. Additive and multiplicative identity: there exist two different elements 0 and 1 in F such that a + 0 = a and a · 1 = a. Additive inverses: for every a in F, there exists an element in F, denoted −a, called additive inverse of a, such that a + (−a) = 0. Multiplicative inverses: for every a ≠ 0 in F, there exists an element in F, denoted by aˉ¹ or 1/a, called the multiplicative inverse of a, such that a · aˉ¹ = 1. Distributivity of multiplication over addition: a · (b + c) = (a · b) + (a · c) . Since it is a finite field it have a finite amount of elements. Look at 1:08, bigger field means more elements and more secure encrytion

[@Multihuntr0]

Very nicely explained. Although, at 2:50 I believe you mean Geometrically :P

[@robertpierce5142]

+Multihuntr0 Ha ha ... you are right! I hadn't caught that until now!

[@shrutipatkar3256]

Thanks a lot... This was the fastest way of understanding ECDH. :D

[@purnimasaikia7776]

Very helpful for my exam, thank u so much

[@anuppatil3427]

Really Nice Video. Thanks a lot

[@achilleslpt5576]

Thanks from VietNam

[@thefirstfishadvancetheland8980]

Thank you for this video! you saved my life:) Robert!!

[@RobertM949]

There are two typos in the presentation. At 11:07 it shows Bob computing the shared secret P using "alpha" from Alice. It should be "A" since "alpha" is Alice's private key. The error is also repeated later for Alice's computation of P. Alice uses Bob's public key B and not "beta", his private key. Still an excellent presentation!

[@robertpierce5142]

I wouldn't really call it a typo. In the audio I call it out correctly, and in the graphic I am trying to demonstrate that A = alpha*G. You are correct, Bob never sees alpha, he just sees alpha*G. In hindsight I probably should have written it as P = beta * A = beta * alpha * G.

[@RobertM949]

OK, thanks Yes typo is not the right word. It just jumps out at me when I see Bob with "alpha". Also, I prefer to call this a key "agreement" or key "establishment" technique as it clarifies that the main objective of this protocol is to arrive at a common shared secret. The public keys that happen to be exchanged are simply part of the protocol and not the desired end result. It also aligns with the NIST definitions. I realize that sounds a bit nit-picky but helps keep everyone straight about the end-goal. Thanks again for an excellent tutorial!

[@yuvrajsakshith9405]

Very insightful! Thank you! :)

[@miketurner3461]

It would be cool to do a reupload of this video that explains the group operation behind adding eliptic curve points (P + P)

[@typingcat]

I was confused by P+P=0 when 2P is not 0 and kQ is Q + Q + Q... by k times. I was trying to ask a question, but after seeing your comment, I expanded the description and it said it was an error.

[@niteshjain1231]

Great video and explainations but i wish you wouldn't have skipped the geometry and algebra involved in finding the coordinates while explaining point addition and point doubling. Would have been a complete video tutorial had you covered them as well. Nevertheless nice and simple explaination !!!

[@robertpierce5142]

nitesh jain Thanks for watching. I completely agree with you. I made this video as part of a project for a number theory class at Ga Tech. There was a cap on how long the video could be. Therefore I cut it off where I did. But I would have liked to go more into the geometry and group structure of the curve and how to derive the group operations based off that geometry.

[@johndebord7802]

Just a quick question: Was this video presentation a final project for the class? Or was it just one of many assignments?

[@solmindaudy]

Thanks Alot Robert Sir. :)

[@henrik3141]

Nice video. Would have been even nicer if you could have plug in the "algebraic solution of the product" into the equation so the people would see that this is actually on the curve. Otherwise it just falls from the sky

[@robertpierce5142]

I would have liked to do that, but I didn’t have the time. I also needed to keep the video as short as possible. It was discussed briefly somewhere in the comments.

[@TomAtkinson]

"The point at infinity also acts as the identity element..." wow did you just say that an EC scheme can encode infinity as a point in the private key? Amazeballs. I was expecting you to say it would be excluded like 0. Nice. That would be really tough to crack yeah? If you had infinity in your key? Or same difficulty? Amaze.

[@robertpierce5142]

The point at infinity does act as the identity, but no I am not saying that the point at infinity can be used as a key. The point at infinity is basically what happens when your point addition formula breaks down, i.e. divide by zero. So we have two things here, the algebraic structure, which is the Elliptic curve and the group operations and then we have the crypto scheme built on top of that algebraic structure. The algebraic structure requires an identity element in order to satisfy the definition of a group. The 'point at infinity' satisfies the requirements for an identity element, i.e. x*identity_element == x. Go to 15:23 in the video, pick a point and then multiply it by the point at infinity, i.e. 19G. For example 4G*19G == 4G when you apply the group operations. Now for the crypto scheme, I am not personally sure what you do if someone chooses the point at infinity as a private key or they compute it as the public key. But I am willing to bet that situation is not allowed, i.e. that point is not allowed to be those keys in the crypto scheme. However the point at infinity is very much required for the underlying algebra.

[@lamureon]

thanks for the great explanation

[@OKeefeist]

So now they have a point only they know can this point be hashed into a certain length and used in AES encryption for example? SHA256 for AES256?

[@gurbraj]

Great video! Why can't Eve take G and add it to itself until she gets, for instance, A? And then she would know alfa. I mean in order for Alice to compute A, she would have needed to do the exact same thing (the group operation multiplication with scalar is defined as multiple adds) ?

[@robertpierce5142]

Eve can do what you described. That is the brute force attack. I did not explain this in the video, but there are methods to calculate points on the curve without having to add every point up. If I were to do this video over again I would have added a section explaining this.

[@princeOalgeria]

That's what I was thinking of

[@Crowz]

@@robertpierce5142 Is there a way to know the order and cofactor of G without computing every point on G like is done in the video? I assume for real curves used this has never been done due to the number points, otherwise you could just build a rainbow table... or is the order computed by guessing, and you use the formula you mention thats not in the video to verify (n-1)G is a point, and nG is infinity?

[@princeOalgeria]

The solution is that we can take any point of your previous resulting points and add it to its self, which makes a tangent line that would cross the third point. That would make a confusion instead of iterating regularly

[@_Redu]

Yeah. This is exactly the point and ruins the whole show. As far as what's told in this video nothing stops Eve from doing the same group addition operation alpha many times until it yields A. Of course Eve doesn't know Alpha initially but she knows how to count. How is this brute force since Alice has done exactly the same thing to obtain A in the first place.

[@ahasdasetodu6304]

One thing I don't quite get is what would be so hard about calculating kG until you find such k1 to equal alpha and k2 to equal beta. Although I admit it would be a bruteforce but from what is shown in the video to calculate alphaG you still have to calculate all those that come before it which would make it as hard to encode as to decipher

[@robertpierce5142]

Good question. Yes your concern is the brute force attack. What the video doesn't go into is that there are shortcuts where you can "jump" to your point on the curve without having to calculate all of the previous steps. I've been out of this world for a while, but what I remember is that one approach is to break things down into powers of 2. Example to get to 33G you would calculate G+G = 2G -> 2(2G) = 4G -> 2(4G) = 8G -> 2(8G) = 16G -> 2(16G) = 32G -> 32G +G = 33G. So 6 steps.

[@ahasdasetodu6304]

@@robertpierce5142 oh okay, thanks for the reply that makes a lot of sense, and also great video! :)))

[@beback_]

That was awesome. Amazing.

[@MercuryTheWhite]

Very helpful. Thank you! :)

[@jackzhp]

nicely done!

[@husseinsuhail7961]

thank you very much,explain very clearly.

[@munkh-erdenez2117]

Great tutorial.

[@itamarnov]

Why Eve can not start from G to compute 2G, 3G etc. and therefore figure out alpha from A and beta from B?

[@robertpierce5142]

Eve can absolutely do what you are describing. This would be the brute force attack. For sake of example I chose a curve with a small order (number of elements). In the real world though the order of the groups that are used in these schemes are much, much larger. So large that given the computing power we have today Eve would need more time than the current age of the universe to check every element.

[@richa2921]

great work !!!!

[@ryanharris9413]

Super Clear, Kudos!

[@jeremydavie4484]

Good explanation! Is there a formula to get the order of an arbitrary elliptic curve over a finite field? I can imagine that if one were to find an isomorphism of an elliptical curve onto a cyclic group (or subgroup) of integers mod n, then it would make the discrete logarithm a lot easier and then elliptical curves would not be secure. Just how hard is it?

[@dharma6662013]

Great video - thank you!

[@2777kk]

Awesome! One of the best explanations I ever found on KZbin one Question however I would like to put forth. Why it is called Elliptical when the equation seems to have eccentricity greater than 1?

[@ronnykuckuck4390]

I would say because he's talking about an elliptic curve, not an elliptic function (which has eccentricity)? So, as you may already see, an elliptic curve is not an ellipse.

[@eurasiantreesparrow7547]

Great video. Thanks

[@moshekollmar6573]

Is there a faster way to calculate alpha*G than adding G together alpha times? If not, then Eve can find alpha and beta by generating a table of multiples of G at the same speed that Alice and Bob encrypt A and B. If alpha is a large number with only small prime factors (for argument's sake, let's say alpha=3840, then generating A can be accelerated by calculating 2G=2*G, 4G=2*2G, 8G=2*4G, ..., 256G=2*128G, 1280G=5*256G, and 3840G=3*1280G, for a total of 13 point additions. However, if alpha was 3833, then this method would require 3832 summations in order to calculate A to send to Bob, which would leave Eve with enough time to generate a significant part of a multiplication table for G.

[@robertpierce5142]

First this is something I should have addressed in the video, but I failed to. One method I am aware of is the fast modular exponentiation (using powers of two) which is exactly what you have demonstrated in your comment. What I disagree with is the claim that 3833 would require 3832 additions. We can write 3833 as 2^11 + 2^10 +2^9 + 2^7 +2^6 +2^5 +2^4 + 2^3 +2^0 = 2048 + 1024 + 512 + 128 + 64 + 32 + 16 + 8 + 1. This is 9 calculations

[@rslitman]

I am an amateur mathematician who has only recently discovered elliptic curves. My question is, why is 4A^3+27B^2=0 not permitted? I graphed y^2=x^3-3*x+2 on my iPad using EduCalc Classic (actually had to break it into halves, upper and lower: y1=sqrt(x^3-3*x+2) and y2=-sqrt(x^3-3*x+2)), and it graphed successfully. Is it due to the upper and lower graphs meeting in a non-differentiable point at (1,0)? A video I watched here used the phrase non-singularity, or maybe it was singularity, to describe this particular graph. Remember, I'm an amateur, still trying to grasp the concepts of fields. rings, groups, and isomorphic.

[@robertpierce5142]

Good question. I am not sure exactly. It's been a while. But it has to do with the discriminate of the curve and it being non-singular.

[@NYFL2156]

Please explain the derivation of the equation at 3:36 X subr = s squared minus (xsubp + xsubQ)

[@robertpierce5142]

+JcJohn Clarke Check out slide 27 at www.math.brown.edu/~jhs/Presentations/WyomingEllipticCurve.pdf

[@robertpierce5142]

+JcJohn Clarke Basically you have two points on the curve. You draw a line through those two points. You want to find the x-coordinate of the third point of intersection on the curve. You take the equation of the line passing through the points and substitute that into the curve equation. You then set the curve equation equal to zero. You know there are three solutions to this equation (the two known points and the third unknown point). You factor out these solutions and solve for the missing third.

[@zhiyizhu3040]

Very helpful! Thank you!

[@wella907]

Very good tutorial ! Thanks a lot. I gues there is a small mistake on the slides 11:00 - 11:40 where Alice & Bob compute P. It says P = alpha*beta*G. But they never exchanged their private key, right? So it should be P = A*beta*G respectively P= alpha*B*G

[@robertpierce5142]

Its not really a mistake. Alice gets B so she computes alpha*B which algebraically is just alpha*(beta*G). Same for Bob. You are correct, they never exchange private keys. They exchange a private key multiplied by G (A or B respectively). But the commutative property tell us that this process exchanges a private key that has been "scrambled" from multiplication by G. The video just showed you algebraically what is going on under the hood.

[@jasoncoombs7097]

alpha*G and beta*G are often written parenthetical for clarity, to indicate that the product is known but the factors are unknown.

[@EmosGambler]

FInally I understand it. Thanks!

[@Herigin]

IF there is only 19 points on the curve and Eve knows that there is no need to guess, you need to bruteforce. I imagine n for real curves are much higher, but again this does not look like secret. "I choose something from a set you know, just guess."

[@robertpierce5142]

Yeah the order (n) of curves used in practice are MUCH higher. Here is a curve used in bitcoin: en.bitcoin.it/wiki/Secp256k1. Here is the order of that curve (in decimal, in the link the order is given in hex): 115,792,089,237,316,195,423,570,985,008,687,907,852,837,564,279,074,904,382,605,163,141,518,161,494,337. This is 78 digits. The number of atoms estimated to be in the visible universe is around 10^78 to 10^82. As you can see the order for that curve is massive. This drives home the point that just b/c you are "choosing something from a set you know", which is true, doesn't mean that it is at all feasible to iterate over that set.

[@mdelatorre]

Great video.

[@LorentzOats]

Great video, even if you only came for an explanation of the EC arithmetics.

[@gundamabalo3309]

Hmm, I got this question in the last example, when Bob receives point A, how does he know that A is made up of 3G, same for Alice when she receives point B, how does she know that B is made up of 9G. Assuming those were bruteforce action, then one: Eve can totally do it since she got everything she needs, and two: if alpha and beta got really big, then how Bob and Alice solve it? If my bruteforcing asuumption is wrong then how do Bob and Alice know A is 3G and B is 9G? Great video by the way man 😍

[@robertpierce5142]

In short Bob doesn't know that A is made up of 3G when he receives A from Alice. All that Bob knows is that A is made up of some unknown multiple of G, let's call it k. Here k is Alice's secret key. So Bob receives A = kG from Alice. Likewise Alice receives B = qG (where q is just some unknown integer to Alice but is Bob's secret key). But when Bob multiplies A by his secret key q then Bob does know he has q*k*G. When Alice multiplies B times her secret key she knows she has k*q*G. And since the group is commutative they know that q*k*G = k*q*G. They have performed a key exchange.

[@robertpierce5142]

"If my bruteforcing asuumption is wrong then how do Bob and Alice know A is 3G and B is 9G?" --- It is a wrong assumption. What you describe is the brute force attack and it would work for Eve as well. And this is why we choose very large group sizes such that the brute force attack effectiveness becomes practically zero. Bob and Alice utilize the commutative nature of point addition and the fact that they and only they know their own secret keys.

[@gundamabalo3309]

@@robertpierce5142 Ah yes now I realize where I misunderstood. When I first saw 9A=9(3G) I thought Bob knew that A=3G, but he only needs to calculate directly from A without knowing A=3G right? Same for Alice. Thanks for your response man!

[@takeru1442]

Awesome!! thank you!

[@shridharjoshi9028]

Can anyone plz send me the c or c++ code which implement the above small example? At least Flowchart. Thanks in advance.

[@nathanstene3601]

Hi everyone, I'm struggling to understand why it is so hard to find the secret key alpha or beta from the public key and the generator G. Couldn't we try alpha = 1,2,3,... until we find A?

[@robertpierce5142]

Yes you could try alpha = 1,2,3.... until you find A. That is the brute force attack. In practice this approach becomes effectively impossible since the order of the curves used in the real world are extremely large, and the amount of time it would take to find the solution would be absurdly long.

[@whatyouwantyouare]

Very clear! Thank you. Only thing that might improve it slightly is to elaborate on how it is helpful that bob and Alice have the same point 8G at the end. How do they use this to send messages?

[@whatyouwantyouare]

Ok I googled me some Diffie Hellman and now I get the goal is to establish a common private key for some other code unspecified.

[@robertpierce5142]

@@whatyouwantyouare Hey Joseph ... yeah you are right, this protocol only establishes the key exchange process and doesn't address what we actually do with that key to encrypt messages. I am not an expert by any means, but I think most of the time they use one of the coordinates and throw the other one away. That number is then used in some other encryption protocol

[@zhaenu6225]

Thanks! This is actually English!