Elliptic Curve Diffie Hellman 

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.

Wow, thank you!

wrg

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.

did you impress your maths teacher 5 yeas ago?

😅😅😅

Agreed

Thanks!

Thanks Pawan, I really appreciate it.

Thanks!

Thanks, I’m glad it helped

Thanks for watching

Thanks! Glad it helped!

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

Thanks!

Hello there!

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.

Thank you

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?

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.

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.

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

challenging indeed

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.

_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

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

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.

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

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.

Are you doing modular arithmetic? The curve isn't y^2 = x^3 + 2x + 2. It is y^2 = x^3 + 2x + 2 (mod 17). I am not sure if that is what you meant and you are indeed doing modular arithmetic or if you are trying to just plot points as if this curve were over the real numbers. This distinction is crucial though.

What curve are you referring to? The one in the video but over the real numbers: y^2 = x^3 + 2x + 2 ? When I plugged this into wolfram-alpha with the line y = 10 - 9x I received two real valued solutions and one complex. The two real valued solutions were approximately (0.877259, 2.10467 ) and (1.4194, -2.77461). There is also a complex solution, but there are indeed two real valued. So if you are on one of these points then there will be a point of intersection. If the line is not vertical then there should always be a point of intersection (I may be wrong, but my intuition tells me this. I am not an expert).

Robert Pierce let’s say the two real intersections are my P and Q. What is P+Q? The rule is to find a third intersection, then reflect it. But, the third intersection is complex valued.

+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.

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

RFC 5114

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.

Thanks!

No I have not put out any code for this project.

Yes that was a mistake.