Elliptic Curve Diffie Hellman
ฝัง
- เผยแพร่เมื่อ 29 ก.ย. 2024
- 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'.
Even after seven years... Still the best simple explanation of elliptic curve cryptography , thank you very much
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
This is the most concise explanation of ECC that I ever learned. Great video! Thanks for taking time to put it together.
wrg
Absolutely amazing video! Subscribed.
Great video, love the way things have been explained. Thank you.
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
thanks for the great explanation
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!
Thanks
Thank you!
How did 27G become 8G?
The order of the curve is 19. This means we are working in modulo 19 when dealing with points on the curve. For example 20G = 19G + 1G = 1G because you wrap around. So 27G = 19G + 8G = 8G. Key fact here is 19G is congruent to 0G since the curve is modulo 19. If this is confusing then research modular arithmetic. Also important is to distinguish between the modulus that comes from the order of the curve and the modulus that comes from the field the curve is defined over (17 in this case). When calculate points we use mod 17 to produce a point on the curve. But the points on the curve themselves are mod 19 due to the order being 19 (order is number of curve points in the cyclic subgroup generated by G)
I see, thank you for the reply.
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.
Someone is going to impress their maths teacher tomorrow
did you impress your maths teacher 5 yeas ago?
😅😅😅
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.
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.
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.
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.
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?
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
Is it a typo at 5:34, did you mean y_P =0 for the point doubling?
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.)
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.
Nice video. Would have been even nicer if you could have plug in the "algebraic solution of the product" into the equation so the people would see that this is actually on the curve. Otherwise it just falls from the sky
I would have liked to do that, but I didn’t have the time. I also needed to keep the video as short as possible. It was discussed briefly somewhere in the comments.
Can anyone plz send me the c or c++ code which implement the above small example? At least Flowchart. Thanks in advance.
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.
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.
Man Best explanation of ECC. I am subscribing😄
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!
The Best Explaination in under 20 minutes EVER. Salute brother ;)
Thanks!
At 16:40 Alice discovers 27.G as 3.9.G ; but Alice does not know b , she only knows B. Now what?
So Alice never really discovers that 27G = 3*9G because 9 is Bob's secret key. So you are correct that Alice does not know b. She only sees B=27G. But in the video it is broken out into its factors as 3*9G for demonstration purposes. It shows that Alice and Bob end up with the same point at the end. Bob computes 27G = 9(3G). Alice compute 27G = 3(9G). But since these group operations are commutable (order of multiplication doesn't matter) we can be assured they indeed compute the same point 27G.
Sorry, if I didn't understand it properly but how do I calculate 3G from G + 2G?
Use the point addition formulas. In the example I demonstrate point addition only. Also remember this is modular arithmetic, and the rules are different than what you may be used to.
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.
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.
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.
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 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?
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
Excellent explanation thank you for This great toturial
this is some clearly explained shit right here
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 from VietNam
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.
Isnt the formula for slope meant to be (Yq-Yp)/(Xq-Xp)
It doesn't matter you get the same answer either way: (Yq-Yp)/(Xq-Xp) = (Yp-Yq)/(Xp-Xq)
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! :)))
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
Is it common notation to say P=αβG? Surely it should be P=αΒG. Since Alice knows Β, not β. 11:25
Alexei Barnes B = beta*G. So the alternate notation would be P = alpha*B This is equivalent to P = alpha*beta*G. As far what is more common I'm not sure. I chose to do it this way bc I thought it would be more transparent.
Right, that makes sense, so P=αΒG is like saying P=αβG². Thanks :)
Just saw a couple other videos talking about this and they did use the same notation, so it is pretty common.
at 11.45: shouldnt it be P = βAG instead of P = βαG? Since Bob doesnt know Alices private key?
Joost Meeuwissen2 beta*AG would algebraically translate to beta*alpha*G*G which is not correct. You are correct though when stating that Bob does not know Alice’s private key. What Bob receives from Alice is A. So Bob computes beta*A. But we know that A = alpha*G. So Bob does indeed compute P = beta*alpha*G. But what is important, and where I think you are getting tripped up, is that although Bob receives A, he has no efficient way to determine what alpha is. He knows A is G times alpha but there is no good way to figure what Alice had to “multiply” G by to get A. This is the discreet logarithm problem and is the key point to the entire algorithm.
Like if I gave you the number 10 and told you it was some multiple of 5 you would immediately know the missing factor was 2. But in modular arithmetic it’s not so easy bc many things can be multiplied by 5 to get 10. I suggest reading up on modular arithmetic and the discreet log problem if this is still giving you problems.
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.
but how do i transmit a message using this?
Let´s say I want to tell alice the message "5", how do i go about that?
How is this information contained in a*b*G ?
This protocol only deals with key exchanges. Once you exchange keys then you can use those keys how ever you wish to encrypt the message and be confident that only you and the other party have that key. To see an example of how to send messages look up the `encrypting` and `decrypting` section of the RSA algorithm (en.wikipedia.org/wiki/RSA_(cryptosystem))
But an example: compute m^e (mod n) where `m` is the message (in this case '5'), e is the key you exchanged, and n is the order of the curve (not 100% sure n being the order of the curve is correct, but you hopefully get the idea).
@@robertpierce5142, yes that makes sense. thank you for explaining!
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.
Why can't eve find the alpha and beta values?
The answer is the discrete logarithm problem. There is no easy way to figure out how many hops from the generator point a value is. In other words if I give you K = x*G (mod p) and I ask you to find x there is not an easy way to do it. (That's the general idea anyway)
thank you so much for such a simple and easy understanding on ECC... great video...
concise and clear. thanks a lot for this video. helped a lot for tomorrow's cryptography exam.
why the R is negative on the first place ???
So do bob and alice also sum up their numbers? I didn't understand that part very well.. But then i started thinking:
P = P
2P = P+P
4P =2P+2P
8P =4P+4P
so If Bob or Alice pick any number from 0 to 15, say 11, then
Q = 11P = 8P + 2P + P.
This part was missing for me.. Otherwise great!
This type of question has been asked a lot. If I were to go back and do the video over again I would add some info on how to effectively calculate points without having to add up everything. What you hit on and just demonstrated is how it is done in practice (I think). It is called fast modular exponentiation.
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.
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).
Best explanation ever. Thank you very much.
Thanks!
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 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 :)
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.
pikapika@
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?
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!
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.
With the above example I have calculated 27G and I got the coordinate (7,11) which is 10G , but in your solution u have said 27G is 8G , where did I go wrong please help me out .
How to determine the order of the curve directly
Great Video and very good Explanation of ECDH!! Thumbs up.
Thanks, this video really helps me to understand ECC.
Does anyone know what software was used to produce this video? The author does not recall - but it seems pretty fantastic.
Hey, sorry for bothering, I'm just a college student that's interested in ECDH, wondering if in your example, 8G is calculated correctly?
I tried making a program and it always said that P(0,6)+Q(5,1) = R(13,15) and not R(13,7).
Then I decided to do it manually:
S = (Yp-Yq)/(Xp-Xq) = (6-1)/(0-5) = 5/5 = 5*7 = 35%17 = 1
Xr = S^2-(Xp+Xq) = 1^2-(0+5) = 1-5 = -4%17 = 13
Yr = S(Xp-Xr)-Yp = 1(0-13)-6 = -13-6 = -19%17 = 15
Can you please correct me if I'm wrong, your video did really helps though, thanks!
Your slope 'S' is incorrect.
(6-1)/(0-5) = 5/-5 = 5/12 = 5*10 = 50%17 = 16 = -1
With the correct slope (-1) I get the same answer presented in the video when working it out manually
concise teaching video !
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.
I cannot like this video enough. Better than any textbook explanation! Thank you Rob!!!!
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)
I feel like you should have a degree in mathematics to understand this - in high school I learned to do vector operations, but now summing points always leads to another point on the curve? Why? It's not in the video.
You don't need a mathematics degree, but some college math courses beyond your general calculus would probably help. At a minimum a viewer would probably need some exposure to modular arithmetic. If you are used to modular arithmetic then you start to realize that it is very similar to what is going on here. You are used to dealing with one set of rules regarding arithmetic growing up. Adding, subtracting, whatever. Modular arithmetic is just doing math with a different set of rules. Thus, you could make up any set of rules. This is what is happening here. They are using an algebraic structure, the elliptic curve, and they have developed a set of rules, or operations, for acting on that structure. One of the things these specific set of rules say that when you get two points on a curve, you can add them together to get a third point on the curve. That's not strange, when you get two points on the number line, say 3 and 4, and you add them together you get another point on the number line, 7. If you want more information about this look up Group Theory or Abstract Algebra. en.wikipedia.org/wiki/Group_(mathematics)
When you add two points on the number line you get a third point on the number line. Since this is a different form of arithmetic then it should seem strange at first. However, it would actually be quite weird if you added two points on a curve and didn't get back a third point on the curve. It would almost be a meaningless operation in my opinion. For example, adding two points on a number line and getting back a color.
It works out that way because of the constraints under which the curve must be created (it doesn't work if you draw a curve by hand for example - or if you just any mathematical description of a curve.) The curves in question exhibit this behavior as a property of their equation.
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).
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.
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?
What is the difference between ECC and ECDH
Priya A ECC is Elliptic Curve Cryptography. It is just a term for referring to the different methods of utilizing elliptic curves for cryptographic protocols and algorithms. ECCDH is Elliptic Curve Diffie-Hellman which is a specific protocol using elliptic curves to cryptographically exchange keys over a public channel. Therefore ECCDH is a concrete example of ECC.
@@robertpierce5142 sir I have one doubt.is it ECDH is secure compared to ECC?
Thank you so much for this explanation! Nicely done :)
Let's be honest, this guy has a real talent for explaining things.
Agreed
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 :-)
Very informative video. Thanks!
Thanks Alot Robert Sir. :)
Very good video, first complete explanation I found!
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 77*2^-1 ≡ 9 * 9
2^-1 (mod 17) === 9 because 2*9 = 18 === 1 (mod 17). research how to find the inverse in modular arithmetic if still confused
By far the best example of elliptic curves out there..
Thanks!
IF there is only 19 points on the curve and Eve knows that there is no need to guess, you need to bruteforce. I imagine n for real curves are much higher, but again this does not look like secret. "I choose something from a set you know, just guess."
Yeah the order (n) of curves used in practice are MUCH higher.
Here is a curve used in bitcoin: en.bitcoin.it/wiki/Secp256k1.
Here is the order of that curve (in decimal, in the link the order is given in hex):
115,792,089,237,316,195,423,570,985,008,687,907,852,837,564,279,074,904,382,605,163,141,518,161,494,337.
This is 78 digits.
The number of atoms estimated to be in the visible universe is around 10^78 to 10^82.
As you can see the order for that curve is massive. This drives home the point that just b/c you are "choosing something from a set you know", which is true, doesn't mean that it is at all feasible to iterate over that set.
Fantastic! Great job. Thanks for taking the time to make this video.
The best ECDH video! Short, to the point and the depictions and font are neat!
an excellent method of explaining ECC, thanks
How is the value of h=1?
The value of H can be 1 when the size of the cyclic subgroup encompasses all points on the curve. This is ideal since having the subgroup smaller results in less points available to use. As for how the value of h=1 I am not sure what you are referring to. I don't think I ever introduced a concrete value for h in the example.
I think this comment refers to 15:41.
Single video with more contents...wow...looks awesome
Really Nice Video. Thanks a lot
If eve knows G then she can also find the order of G =n and also the cyclic points generated by G .Looking the values of Point A and B in the group she can easily find alpha beta??
+kanwarkajla
This is what we call a brute force attack. A brute force attack is always a weakness of these crypto-systems. However, this is why very large curves are used. If you look at the end of the video (17:30) you will see an example of an old curve that Microsoft used. These curves are so large that it would take at least 1000s of years to check every possibility given today's technology. Therefore this attack is not feasible.
+Robert Pierce I am sorry but I did not understand your answer. The question is: based on the video, whatever the Microsoft's curve is, since every party knows p, a, b, G, n, and h, every party can calculate G, 2G, ... (n-1)G. So, as every party knows B, every party knows beta! Also alpha as A. Finally, there is no secret to every party and I do not know why "it would take at least 1000s of years to check every possibility"?
+Dongyin Wu So the entire system depends on the fact that everyone can see A, B, and G but they have no way of knowing what multiple of G A and B are (how many hops on the curve does it take to go from G to A). One way of figuring this out is for an attacker to take the curve and the generator G and actually generate the entire curve. If they did this, then whenever an attacker saw A being transmitted then they would just have to look up the point A and read off what alpha was (the number of hops from G). In theory there is nothing wrong with this attack. This isn't just an attack for elliptic curve cryto, it is an attack for almost every public key cryptosystem. The problem is with moving from the theoretical attack to an actual real world attack.
I counted the number of decimal digits in the Microsoft curve mentioned in the video. I counted 48 digits. Think how long it would take you to count to a million.
th-cam.com/video/NwU3P6CM61Q/w-d-xo.html
Here is a link to a guy that counted to a million on youtube. It took him three months counting 16 hours a day. A million is 7 decimal digits long! Think how long it would take you to count to a number that has 48 decimal digits in it! It would probably take you longer than the entire universe has existed. Now, instead of just counting, try actually calculating the group operations listed around 15:20. It would take you much, much longer.
Now, computers will be doing this, so it shouldn't take no time at all right? Well no, computers are fast, but not that fast. If you want, you should probably do some research into how many CPU operations it takes to calculate on of these points. Take that number and multiply it by 10^48. Then divide that number by the speed (in flops per sec) of the computer you would be using. This should give you a rough estimate of how long it would take to generate that curve.
+Robert Pierce
Thank you for your quick response. My question is exactly about the first sentence in your answer: "So the entire system depends on the fact that everyone can see A, B, and G but they have no way of knowing what multiple of G A and B are (how many hops on the curve does it take to go from G to A)."
To make it clear, we can easily conclude that:
C1. Bob knows how to compute B (B=beta*G);
C2. Bob does not know how to find out alpha from A (since Bob faces the same difficulty as Eve).
From C2, I can further conclude that:
FC1. Bob computes P =beta*alpha*G not by simply computing B=G+G+...+G(repeating beta * alpha times), since Bob does not know alpha.
FC2(drawn from FC1). Bob computes P =beta*alpha*G by the other way.
Then, from FC2 I GUESS that:
GC. Bob computes P = beta*alpha*G by computing P= beta*A = A+A+...+A(repeating beta times; A=alpha*G given by Alice)
IF GC. is true, I can conclude that:
FC1. Bob does not really have to compute beta times to get P, just as he does not have to compute beta times to get B.
FC2: Also, Alice does not really have to compute alpha times to get P, just as she does not have to compute alpha times to get A.
Finally, I conclude that:
Conclusion1 (drawn from C1 and GC): Elliptic Curve has Associative Property. I.e., a*b*G = a*(b*G)=a*B (if B=b*G);
Conclusion2 (drawn from Conclusion1, FC1 and FC2): as computing X*G (where X is a huge integer ), Bob (Alice as well) can
(step1.)break X into X = A0*2^0+A1*2^1+...An*2^n; (A0...An could be either 0 or 1; 2^n means power(2,n)).
I.e. 65537=2^0+2^16;
(step2.)let P0=G, compute P1=2*P0, P2=2*P1, ... Pn=2*Pn-1=2^n*G;
(step3.)compute X*G = (A0*2^0+A1*2^1+...An*2^n)*G = A0*G+A1*2*G+...An*2^n*G = A0*P0+A1*P1+...An*Pn.
I.e. 65537*G =2^0*G+2^16*G=G+P16*G;
So, Bob (Alice as well) can easily compute B=beta*G (A=alpha*G) no matter how big beta (alpha) is.
That is, at most (2 * log2 n); (log2 n) for step2 plus (log2 n) for step 3.
Conclusion3: Eve does not know alpha and beta in advance, so she does not know how to break them and calculate A or B in a shortcut (like in Conclusion 2). Therefore, she has to brute force A or B; but since both alpha and beta are huge numbers, there is almost no hope unless she has a quantum computer.
Am I right?
+Dongyin Wu
Wow, very well presented argument. First the process you describe is sometimes called "fast modular exponentiation", and it is fundamental to implementing a lot of public key crypto-systems (RSA, El Gamal, and Elliptic Curve Crypto). Your conclusion 3 is correct (as far as I know). What makes the system work is that Bob knows beta. He can then use the shortcut as you mentioned. Same with Alice, she knows alpha. Eve sees A and B, but without beta or alpha she is kinda stuck. If she computes A*B then she gets beta*alpha*G*G which is not the point she is after. I am sure Eve has some more sophisticated attacks than just brute force, but I do not know enough about the subject to know what they are at this time. However, if she were to try brute force then the large size of the cyclic group would make the attempt futile.
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
thank you very much,explain very clearly.
Time 3:21.
It is very strange that you're calculating X_R=S^2 - (X_P + X_Q), where S is a slope S = (y_P - y_Q)/(x_P - x_Q).
Do you understand this?
How to prove this equation?
Here is no explanation...
My intention of the video was to not prove the equations, but to merely demonstrate the algorithm. I know someone in the comments about a year ago asked about how to derive the equations, and I supplied a link to some presentation that did just that. Maybe you can find that comment.
I had the same question. Slides 20 - 26 in this presentation will help. www.math.brown.edu/~jhs/Presentations/WyomingEllipticCurve.pdf
The magic happens on slide 23 when solving for the intersections of the the line and the curve. Set the curve equation to zero by moving y_R to the other side with everything else, substitute the line equation for y_R. Since we know that a third order equation with three factors will also have zero at these same points (x1, x2, and x3), set it up, expand it, then take careful observation. It looks really similar to the original curve equation. Equate the the coefficients and voila! This is where the values for A and B drop out of the solution and are expressed in terms of the known points. Brilliant!
Very helpful. Thank you! :)