Elliptic Curve Diffie Hellman
ฝัง
- เผยแพร่เมื่อ 9 ธ.ค. 2014
- A short video I put together that describes the basics of the Elliptic Curve Diffie-Hellman protocol for key exchanges.
There is an error at around 5:30 where I state that the point at infinity is the result of point-doubling a point whose X coordinate is zero. This is incorrect, it should be when the Y coordinate is zero.
Also I state 'geographically' instead of 'geometrically'.
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 seven years... Still the best simple explanation of elliptic curve cryptography , thank you very much
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.
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
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.
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!
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
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 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
Absolutely amazing video! Subscribed.
Man Best explanation of ECC. I am subscribing😄
The best ECDH video! Short, to the point and the depictions and font are neat!
Absolutely great video. Never watched a better explanation!
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 :-)
concise and clear. thanks a lot for this video. helped a lot for tomorrow's cryptography exam.
By far the best example of elliptic curves out there..
Thanks!
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.
Great explanation. Thank you for taking the time to provide a simple explanation.
Thanks for watching
thank you so much for such a simple and easy understanding on ECC... great video...
Fantastic! Great job. Thanks for taking the time to make this video.
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 👍
Very good video, first complete explanation I found!
Very instructive! Thank you very much for giving me a good lecture.
Single video with more contents...wow...looks awesome
Amazing explanation! Thank you for explaining this!
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!
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.
Great video, love the way things have been explained. Thank you.
an excellent method of explaining ECC, thanks
Thanks, this video really helps me to understand ECC.
Thank you so much for this explanation! Nicely done :)
Great Video explaining the elliptic curve fundamentals
Great Video and very good Explanation of ECDH!! Thumbs up.
Best explanation ever. Thank you very much.
Thanks!
Excellent explanation thank you for This great toturial
Thanks a lot... This was the fastest way of understanding ECDH. :D
Thank you for this video! you saved my life:)
Robert!!
Very informative video. Thanks!
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)
Good job! Thank you! Hello from Kazakhstan!
Hello there!
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?
Very helpful for my exam, thank u so much
Best video on ECC.
thanks for the great explanation
Very good explanation. Thanks.
Thank you
That was awesome. Amazing.
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.
Very insightful! Thank you! :)
thank you very much,explain very clearly.
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).
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'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.
Really Nice Video. Thanks a lot
concise teaching video !
Very helpful. Thank you! :)
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
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?
nicely done!
Great video - thank you!
Great tutorial.
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
Super Clear, Kudos!
That was so helpful!
Is there any mathy way to compute the order of the generator without trying until we find infinity?
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 helpful! Thank you!
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?
Does anyone know what software was used to produce this video? The author does not recall - but it seems pretty fantastic.
great work !!!!
Great video. Thanks
What tools were you using?! amazing animation with hand writing. I wanna make lecture video like this.. So can you tell me what tools did you use??
I can't remember what the actual program was that I used, but that is not my hand. It is an animation provided by the software.
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?
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.
I finally understood it!
Does somebody know a place for getting elliptic curves, and their data neccesary for ECC? I can only find Curve25519 and the one in the video.
RFC 5114
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.
this is some clearly explained shit right here
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...
Thanks Alot Robert Sir. :)
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.
why the R is negative on the first place ???
Can anyone plz send me the c or c++ code which implement the above small example? At least Flowchart. Thanks in advance.
Great video.
Thank you!
I didn't get how do you pass from a curve on R to a curve on Z/pZ from a graphical point of view.
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.
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
FInally I understand it. Thanks!
How does the elliptic curve application works if i need an algorithm to provide an encrypted message to 100 people, give them 100 unique keys, but they need to unite at least 5 of any their keys to decrypt the message?
Dmítrij Ačkásov Check our Shamir’s secret sharing (en.m.wikipedia.org/wiki/Shamir%27s_Secret_Sharing )
I’m not too familiar with this, but the idea would be to divide the key up into 100 pieces. However, also make the key subject to the property that if 5 keys are known then the rest can be easily computed. This is much like drawing a line in 2D space. If you know two points then you can derive a formula to calculate all the other points.
what is the usage of cofactor parameter(h) while doing elliptic curve diffie hellman?
The cofactor tells you how large the group generated by the generator point is in relation to the curve. It isn't actually used to my knowledge in crypto protocols. It is just used as metadata describing a curve. If you were picking curves to use in some sort of application then the cofactor would be important.
I don't get the first part. How can you add two +ve y coordinates together and end up with a negative y coordinate???
It is just the way the group operations are defined. This is not standard arithmetic. Some mathematicians came up with some new arithmetic that have the wonderful properties that allow us to do cryptography. But this is the way they are defined.
Is it a typo at 5:34, did you mean y_P =0 for the point doubling?
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.
question how is point 3g and point 9g calculated by alice and bob? do they iterate on the generator point a or b Times? or is there a direct function to calculate a point based off of a or b?
Yes there are different methods that are used in practice. I am in no way very knowledgable about how this is done in the real world, but one method is repeated doubling i.e. to calculate 9G you just need to know 8G+ 1G. But 8G is is (2G)^3 -> 2G*2G*2G. So 9G = 2G*2G*2G + 1G which gives you the point you want in 4 curve operations. But you probably already knew 4G or even 8G ahead of time so an ad hoc calculation could be done for even less.
Can someone help me understand how s was calculated at 13:45? I don't see how to go from 77/2 to 9*9. Same applies for 14:20 and how he went from 13^2-2(5) to 16-10. Any thoughts?
So in modular arithmetic we never actually 'divide' in the most accepted sense of the word. When we divide we are actually multiplying by the inverse. Thus in this example (13:45) 77/2 (mod 17) is actually 77*2^(-1) (mod 17). 77 (mod 17) is congruent to 9. Hopefully that part is clear. Thus 77*2^(-1) (mod 17) is congruent to 9*2^(-1) (mod 17). So now to figure out 2^(-1) (mod 17). The inverse operation in this algebra (integers modulo 17) is solved by 2x == 1 (mod 17), or what times two modulo 17 gives us 1 (where 1 is the identity element). So hopefully you agree that 2(9) == 18 == 1 (mod 17) is a valid solution. Thus 2^(-1) == 9 (mod 17). Putting this together give us 77/2 (mod 17) is congruent to 9*9 (mod 17)
For the example at 14:20: 13^2 - 2(5) (mod 17) can be simplified to (-4)^2 - 10 == 16 -10 (mod 17).