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.
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.
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.
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
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.
@@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.
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!
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
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.)
@@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?
@@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.
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 !!!
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.
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.
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).
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 :-)
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, 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"?
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.
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.
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.
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 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.
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.
@@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.
@@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.
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) ?
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.
@@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?
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
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.
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)
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.
_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.
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
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.
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.
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
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?
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
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.
+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.
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 !!!
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.
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?
Awesome! One of the best explanations I ever found on TH-cam one Question however I would like to put forth. Why it is called Elliptical when the equation seems to have eccentricity greater than 1?
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.
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.
The order of G is 19 (see 15:30 in the video). Thus G is modulo 19. Therefore 27G = 19G + 8G = 8G (mod 19). Don’t confuse this with the curve being modulo 17. We are simply talking about G and the group it produces and not the actual curve itself.
very Good explanation... But I have a question Since Eve has the equation and the point (5,1) so he can find all the points then it will be easy for him to get the privates key. Am i right? thank you
Yeah you are right in theory. This would be a brute force attack. However, it is not possible to compute all of the points in practice. The order of real life curves used in cryptography is absolutely massive. So massive that you could never compute all of the points.
@@robertpierce5142 I understand that but i dont get how Bob Alice are doing their computations. I thought the only possible way was to compute nG was to compute 2G, then 2G+G, then 3G+G etc... thus giving us all point until we stop. By th e way this is a very helpful video :)
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?
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.
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
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.
"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.
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.
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.
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 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
The domain parameters are agreed to ahead of time by the communicating parties. So in practice it is based on the application. For example if you are using software to encrypt video files using elliptic curves that software will have already decided on which curve they are using ahead of time.
Useful, thanks. Two spelling corrections on slide at 9:43 'Curve' and 'Hellman'. Q. How to generate a series of shared secret offline using your method? Q. Is the transcript/maple code for the example available online?
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!
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.
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!
Great video! I have a few questions. First, why is it necessary for both parties to know the cofactor? And how can the algebraic formulas for point addition be derived? Also, it seems like the group generated by G would not be cyclic unless infinity plus G is defined to be equal G. Is this the case, or am I missing something?
About the cofactor: As far as I know the cofactor is not necessary to implement the protocol. It is just a parameter of the curve. It is important when designing the curve and understanding its properties. However, I do not know a whole lot about the cofactor, and I may be wrong. It is a more advanced topic then I got into when studying this. The infinity point should be considered the identity element, so yes ... infinity + G should be G. If you try to test this property using the example I gave you can do so. For example, if you do the modular arithmetic correctly, you should see that Infinity + G = G. Here Infinity = 19G. So 19G + G should be equal to G. See if you can verify that. If not let me know. As far as deriving the formulas, someone asked me a question about it, and I gave a link to someone's power point where they derive the formulas. See if you can find that comment.
How does Bob know 9A is 27G? Since Alice didn't share the private key "beta", Bob will only know he has to do 9 * (7,6). So the question is how does Bob calculate 9 * (7, 6) ?
Bob is calculating 9A = 9*3G = 9*(10,6). Bob calculates 9*(10,6) by using the point addition formulas, so 9*(10,6) -> (10,6) + (10,6) + (10,6) .... and so on nine times. In practice there are shortcuts but this demonstrates the idea.
When you “force” x to be an integer and y is not an integer itself then it is defined as simply not being on the curve. If a curve is defined over a set of integers then you can only build points on the curve with those integers. If you run into a situation where it seems like you need a non-integer y to make integer x fit on the curve then that point is undefined and not a part of the curve.
Great, informative video, but I have a question, since all G - points are known to all parties, what prevent Eve, to search in the list of Points which point has Bobs Coordinates 7,6. She can easly find out, that it was 3G also alpha is 3...
![The Most Useful Curve in Mathematics [Logarithms]](http://i.ytimg.com/vi/OjIwCOevUew/mqdefault.jpg)
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.
Thanks for the compliment! It made my day!
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.
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.
This is the most concise explanation of ECC that I ever learned. Great video! Thanks for taking time to put it together.
wrg
I wish all teachers would be able to put something like this for everything . THIS IS THE SIMPLEST SIMPLEST EXPLANATION By Far. Thank you.
Wow, thank you!
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
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.
@@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.
Even after seven years... Still the best simple explanation of elliptic curve cryptography , thank you very much
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!
Thanks Pawan, I really appreciate it.
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
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.)
Let's be honest, this guy has a real talent for explaining things.
Agreed
Someone is going to impress their maths teacher tomorrow
did you impress your maths teacher 5 yeas ago?
😅😅😅
The Best Explaination in under 20 minutes EVER. Salute brother ;)
Thanks!
I have been looking for some clear explanation related to ECC and this is by far the best I have found.
Thanks, I’m glad it helped
I cannot like this video enough. Better than any textbook explanation! Thank you Rob!!!!
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.
I think it is y_p = 0 at 5:27 instead of x_p.
You are correct. That correction was made, but unfortunately it doesn't show up on mobile devices.
@@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?
@@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.
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 !!!
I still don't get it. How do you add two positive y coordinates together and end up with a negative y coordinate!?? WTH!
By far the best example of elliptic curves out there..
Thanks!
The best ECDH video! Short, to the point and the depictions and font are neat!
concise and clear. thanks a lot for this video. helped a lot for tomorrow's cryptography exam.
Absolutely amazing video! Subscribed.
Excellent explanation thank you for This great toturial
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.
Single video with more contents...wow...looks awesome
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.
Man Best explanation of ECC. I am subscribing😄
Great explanation. Thank you for taking the time to provide a simple explanation.
Thanks for watching
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.
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).
thank you so much for such a simple and easy understanding on ECC... great video...
Great video, love the way things have been explained. Thank you.
an excellent method of explaining ECC, thanks
Great Video and very good Explanation of ECDH!! Thumbs up.
Man this video was amazing. Thank you for all that work. Crystal clear
Thanks! Glad it helped!
Best explanation ever and I have seen many videos already. Thanks 👍
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 :-)
Absolutely great video. Never watched a better explanation!
Thanks, this video really helps me to understand ECC.
Best explanation ever. Thank you very much.
Thanks!
Great Video explaining the elliptic curve fundamentals
Fantastic! Great job. Thanks for taking the time to make this video.
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.
+Tim-J.Swan That's why we need a signature from trustable authority to prove their identities.
+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"?
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.
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.
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.
Very good video, first complete explanation I found!
Very instructive! Thank you very much for giving me a good lecture.
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.
Thanks for that explanation. You are exactly correct. The modular arithmetic is what trips a lot of people up on this.
@@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.
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.
@@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.
@@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.
Amazing explanation! Thank you for explaining this!
Very good explanation. Thanks.
Thank you
Good job! Thank you! Hello from Kazakhstan!
Hello there!
Thank you so much for this explanation! Nicely done :)
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) ?
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.
That's what I was thinking of
@@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?
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
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.
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)
Very informative video. Thanks!
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.
_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.
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
concise teaching video !
A great, succinct introduction! Thanks.
p.s. I need to implement this in hardware.
+Haji Akhundov Thanks! That sounds like a fun (but challenging) project.
challenging indeed
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?
Really Nice Video. Thanks a lot
this is some clearly explained shit right here
Why Eve can not start from G to compute 2G, 3G etc. and therefore figure out alpha from A and beta from B?
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.
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.
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
Thx thx thx thx, This video is awesome, really nice explanation!
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?
Thanks from VietNam
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
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.
@@robertpierce5142 oh okay, thanks for the reply that makes a lot of sense, and also great video! :)))
Very nicely explained.
Although, at 2:50 I believe you mean Geometrically :P
+Multihuntr0 Ha ha ... you are right! I hadn't caught that until now!
Please explain the derivation of the equation at 3:36 X subr = s squared minus (xsubp + xsubQ)
+JcJohn Clarke Check out slide 27 at www.math.brown.edu/~jhs/Presentations/WyomingEllipticCurve.pdf
+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.
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 !!!
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.
Just a quick question: Was this video presentation a final project for the class? Or was it just one of many assignments?
thanks for the great explanation
Very insightful! Thank you! :)
Thanks Alot Robert Sir. :)
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?
Awesome! One of the best explanations I ever found on TH-cam one Question however I would like to put forth. Why it is called Elliptical when the equation seems to have eccentricity greater than 1?
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.
Very helpful for my exam, thank u so much
It would be cool to do a reupload of this video that explains the group operation behind adding eliptic curve points (P + P)
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.
Very helpful. Thank you! :)
thank you very much,explain very clearly.
thank you for this video, but I didn't understand how 27G=8G ? at 16:44
The order of G is 19 (see 15:30 in the video). Thus G is modulo 19. Therefore 27G = 19G + 8G = 8G (mod 19). Don’t confuse this with the curve being modulo 17. We are simply talking about G and the group it produces and not the actual curve itself.
@@robertpierce5142 thank you very much
very Good explanation... But I have a question
Since Eve has the equation and the point (5,1) so he can find all the points then it will be easy for him to get the privates key. Am i right? thank you
Yeah you are right in theory. This would be a brute force attack. However, it is not possible to compute all of the points in practice. The order of real life curves used in cryptography is absolutely massive. So massive that you could never compute all of the points.
@@robertpierce5142 thank you so much
@@robertpierce5142 I understand that but i dont get how Bob Alice are doing their computations. I thought the only possible way was to compute nG was to compute 2G, then 2G+G, then 3G+G etc... thus giving us all point until we stop.
By th e way this is a very helpful video :)
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?
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.
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
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.
alpha*G and beta*G are often written parenthetical for clarity, to indicate that the product is known but the factors are unknown.
Thanks a lot... This was the fastest way of understanding ECDH. :D
Best video on ECC.
"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.
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.
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.
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.
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?
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.
@@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
That was awesome. Amazing.
How do Bob and Alice agree on the Domain parameter(a, b, G, etc.), so that they are actually using the same elliptic curve?
The domain parameters are agreed to ahead of time by the communicating parties. So in practice it is based on the application. For example if you are using software to encrypt video files using elliptic curves that software will have already decided on which curve they are using ahead of time.
Great tutorial.
great video, what I did not get it how is it possible that 3G does not appear in the graph? do not all the points should be on the graph?
Is it a typo at 5:34, did you mean y_P =0 for the point doubling?
Useful, thanks. Two spelling corrections on slide at 9:43 'Curve' and 'Hellman'. Q. How to generate a series of shared secret offline using your method? Q. Is the transcript/maple code for the example available online?
Thanks!
No I have not put out any code for this project.
nicely done!
14:20 - how is 13 square 16? Reduced by 17?
13 mod 17 == -4. (-4)^2 mod 17 == 16. One way of looking at it.
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!
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.
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!
Thank you for this video! you saved my life:)
Robert!!
Great video! I have a few questions. First, why is it necessary for both parties to know the cofactor? And how can the algebraic formulas for point addition be derived? Also, it seems like the group generated by G would not be cyclic unless infinity plus G is defined to be equal G. Is this the case, or am I missing something?
About the cofactor: As far as I know the cofactor is not necessary to implement the protocol. It is just a parameter of the curve. It is important when designing the curve and understanding its properties. However, I do not know a whole lot about the cofactor, and I may be wrong. It is a more advanced topic then I got into when studying this.
The infinity point should be considered the identity element, so yes ... infinity + G should be G. If you try to test this property using the example I gave you can do so. For example, if you do the modular arithmetic correctly, you should see that Infinity + G = G. Here Infinity = 19G. So 19G + G should be equal to G. See if you can verify that. If not let me know.
As far as deriving the formulas, someone asked me a question about it, and I gave a link to someone's power point where they derive the formulas. See if you can find that comment.
why the R is negative on the first place ???
How does Bob know 9A is 27G? Since Alice didn't share the private key "beta", Bob will only know he has to do 9 * (7,6). So the question is how does Bob calculate 9 * (7, 6) ?
Bob is calculating 9A = 9*3G = 9*(10,6). Bob calculates 9*(10,6) by using the point addition formulas, so 9*(10,6) -> (10,6) + (10,6) + (10,6) .... and so on nine times. In practice there are shortcuts but this demonstrates the idea.
How can you define this continuous cubic curve only among the integers? If you force x to be integers, y is bound to be irrational at least once.
When you “force” x to be an integer and y is not an integer itself then it is defined as simply not being on the curve. If a curve is defined over a set of integers then you can only build points on the curve with those integers. If you run into a situation where it seems like you need a non-integer y to make integer x fit on the curve then that point is undefined and not a part of the curve.
Can anyone plz send me the c or c++ code which implement the above small example? At least Flowchart. Thanks in advance.
great work !!!!
Great, informative video, but I have a question, since all G - points are known to all parties, what prevent Eve, to search in the list of Points which point has Bobs Coordinates 7,6. She can easly find out, that it was 3G also alpha is 3...