Elliptic Curve Diffie Hellman

แชร์
ฝัง
  • เผยแพร่เมื่อ 30 ต.ค. 2024

ความคิดเห็น • 500

  • @trogdorstrngbd
    @trogdorstrngbd 5 ปีที่แล้ว +126

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

    • @robertpierce5142
      @robertpierce5142  5 ปีที่แล้ว +14

      Thanks for the compliment! It made my day!

    • @3rdman99
      @3rdman99 2 ปีที่แล้ว +1

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

    • @fuzzywzhe
      @fuzzywzhe ปีที่แล้ว

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

  • @garry137
    @garry137 9 ปีที่แล้ว +99

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

    • @zes7215
      @zes7215 ปีที่แล้ว

      wrg

  • @mtare8942
    @mtare8942 8 หลายเดือนก่อน +4

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

  • @fantaaa61
    @fantaaa61 3 ปีที่แล้ว +9

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

    • @fantaaa61
      @fantaaa61 3 ปีที่แล้ว +1

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

    • @robertpierce5142
      @robertpierce5142  3 ปีที่แล้ว +1

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

  • @omargaber3122
    @omargaber3122 ปีที่แล้ว +4

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

  • @PawanBathe
    @PawanBathe 6 ปีที่แล้ว +5

    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!

  • @MMABeijing
    @MMABeijing ปีที่แล้ว +1

    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

  • @WTHNoSpam
    @WTHNoSpam 6 ปีที่แล้ว +5

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

  • @94rainbowx33
    @94rainbowx33 2 ปีที่แล้ว +2

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

  • @asilbekergashev6788
    @asilbekergashev6788 9 ปีที่แล้ว +104

    Someone is going to impress their maths teacher tomorrow

  • @lappdev5071
    @lappdev5071 3 ปีที่แล้ว +4

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

  • @slobodandobrijevic1374
    @slobodandobrijevic1374 3 ปีที่แล้ว +1

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

  • @drone2369
    @drone2369 2 ปีที่แล้ว +1

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

  • @joshcampbell402
    @joshcampbell402 2 ปีที่แล้ว +2

    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.

  • @mrvargarobert
    @mrvargarobert 8 ปีที่แล้ว +38

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

    • @robertpierce5142
      @robertpierce5142  8 ปีที่แล้ว +16

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

    • @lemague
      @lemague 3 ปีที่แล้ว

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

    • @KristofVydt
      @KristofVydt 3 ปีที่แล้ว +1

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

  • @riccardoandreetta9520
    @riccardoandreetta9520 8 ปีที่แล้ว +2

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

    • @donha475
      @donha475 6 ปีที่แล้ว

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

  • @rahulgomes4823
    @rahulgomes4823 5 ปีที่แล้ว +1

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

  • @pkpio
    @pkpio 9 ปีที่แล้ว +1

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

  • @shubhamshourya7518
    @shubhamshourya7518 6 ปีที่แล้ว +2

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

  • @NoNTr1v1aL
    @NoNTr1v1aL 2 ปีที่แล้ว +2

    Absolutely amazing video! Subscribed.

  • @a7medFCI
    @a7medFCI 2 ปีที่แล้ว +1

    Excellent explanation thank you for This great toturial

  • @hanskessock3941
    @hanskessock3941 5 ปีที่แล้ว +3

    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.

  • @arunkumarsaravanan7875
    @arunkumarsaravanan7875 6 ปีที่แล้ว +1

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

  • @lance3401
    @lance3401 6 หลายเดือนก่อน +1

    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.

  • @SusheelAryarocks
    @SusheelAryarocks 2 ปีที่แล้ว +1

    Man Best explanation of ECC. I am subscribing😄

  • @jeankhawand5539
    @jeankhawand5539 6 ปีที่แล้ว

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

  • @Devashish18081
    @Devashish18081 5 ปีที่แล้ว +2

    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.

  • @hsharma3933
    @hsharma3933 2 ปีที่แล้ว +1

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

  • @parwinderdhillon4094
    @parwinderdhillon4094 6 ปีที่แล้ว +2

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

  • @vikas_chaube
    @vikas_chaube 8 ปีที่แล้ว +6

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

  • @prabavathihariharan147
    @prabavathihariharan147 4 ปีที่แล้ว +1

    an excellent method of explaining ECC, thanks

  • @Jonasonweb
    @Jonasonweb 9 ปีที่แล้ว +1

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

  • @averagesoup8432
    @averagesoup8432 7 ปีที่แล้ว +1

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

  • @philippdolomit4830
    @philippdolomit4830 ปีที่แล้ว

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

  • @jawadhussain8175
    @jawadhussain8175 6 ปีที่แล้ว +1

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

  • @chandravaranasi2535
    @chandravaranasi2535 5 ปีที่แล้ว +1

    Absolutely great video. Never watched a better explanation!

  • @IqbalSyamil
    @IqbalSyamil 2 ปีที่แล้ว +1

    Thanks, this video really helps me to understand ECC.

  • @anjalichaudhri8455
    @anjalichaudhri8455 3 ปีที่แล้ว +1

    Best explanation ever. Thank you very much.

  • @appapurapu
    @appapurapu 7 ปีที่แล้ว

    Great Video explaining the elliptic curve fundamentals

  • @andrewclarke598
    @andrewclarke598 7 ปีที่แล้ว +1

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

  • @TimJSwan
    @TimJSwan 8 ปีที่แล้ว +9

    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
      @nimo1993 8 ปีที่แล้ว +9

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

    • @ThatNateGuy
      @ThatNateGuy 8 ปีที่แล้ว +1

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

    • @riccardoandreetta9520
      @riccardoandreetta9520 8 ปีที่แล้ว +5

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

    • @beback_
      @beback_ 7 ปีที่แล้ว +1

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

    • @henrybirge-lee709
      @henrybirge-lee709 7 ปีที่แล้ว +1

      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.

  • @adde362
    @adde362 6 ปีที่แล้ว +1

    Very good video, first complete explanation I found!

  • @iomat9727
    @iomat9727 8 ปีที่แล้ว

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

  • @fuzzywzhe
    @fuzzywzhe ปีที่แล้ว +1

    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
      @robertpierce5142  ปีที่แล้ว

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

    • @fuzzywzhe
      @fuzzywzhe ปีที่แล้ว

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

    • @fuzzywzhe
      @fuzzywzhe ปีที่แล้ว

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

    • @fuzzywzhe
      @fuzzywzhe 11 หลายเดือนก่อน

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

    • @fuzzywzhe
      @fuzzywzhe 19 วันที่ผ่านมา

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

  • @simiouch5128
    @simiouch5128 6 ปีที่แล้ว +1

    Amazing explanation! Thank you for explaining this!

  • @Prvosienko
    @Prvosienko 5 ปีที่แล้ว +1

    Very good explanation. Thanks.

  • @streetfighter1kz
    @streetfighter1kz 7 ปีที่แล้ว

    Good job! Thank you! Hello from Kazakhstan!

  • @haikalhawari1298
    @haikalhawari1298 9 ปีที่แล้ว +1

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

  • @gurbraj
    @gurbraj 6 ปีที่แล้ว +10

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

    • @robertpierce5142
      @robertpierce5142  6 ปีที่แล้ว +5

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

    • @princeOalgeria
      @princeOalgeria 3 ปีที่แล้ว

      That's what I was thinking of

    • @Crowz
      @Crowz 3 ปีที่แล้ว

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

    • @princeOalgeria
      @princeOalgeria 3 ปีที่แล้ว

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

    • @_Redu
      @_Redu 2 ปีที่แล้ว +1

      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.

  • @user-rz1vm9fh3l
    @user-rz1vm9fh3l 9 ปีที่แล้ว +1

    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)

  • @nitin-hp6ug
    @nitin-hp6ug 8 ปีที่แล้ว +1

    Very informative video. Thanks!

  • @bluekaioken5924
    @bluekaioken5924 9 ปีที่แล้ว +4

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

    • @jenspettersen7837
      @jenspettersen7837 6 ปีที่แล้ว

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

    • @jenspettersen7837
      @jenspettersen7837 6 ปีที่แล้ว

      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

  • @samliao2393
    @samliao2393 3 ปีที่แล้ว +2

    concise teaching video !

  • @HajiAkhundov
    @HajiAkhundov 8 ปีที่แล้ว +1

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

    • @robertpierce5142
      @robertpierce5142  8 ปีที่แล้ว +1

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

    • @HajiAkhundov
      @HajiAkhundov 8 ปีที่แล้ว

      challenging indeed

  • @OKeefeist
    @OKeefeist 2 ปีที่แล้ว +1

    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?

  • @anuppatil3427
    @anuppatil3427 9 ปีที่แล้ว +1

    Really Nice Video. Thanks a lot

  • @gundabalf
    @gundabalf 4 ปีที่แล้ว +3

    this is some clearly explained shit right here

  • @itamarnov
    @itamarnov 10 วันที่ผ่านมา +1

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

    • @robertpierce5142
      @robertpierce5142  10 วันที่ผ่านมา +1

      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.

  • @moshekollmar6573
    @moshekollmar6573 5 ปีที่แล้ว +2

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

    • @robertpierce5142
      @robertpierce5142  5 ปีที่แล้ว

      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

  • @RoBuceo
    @RoBuceo 3 ปีที่แล้ว

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

    • @RoBuceo
      @RoBuceo 3 ปีที่แล้ว

      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?

  • @achilleslpt5576
    @achilleslpt5576 2 ปีที่แล้ว +1

    Thanks from VietNam

  • @ahasdasetodu6304
    @ahasdasetodu6304 10 หลายเดือนก่อน +1

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

    • @robertpierce5142
      @robertpierce5142  10 หลายเดือนก่อน +1

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

    • @ahasdasetodu6304
      @ahasdasetodu6304 10 หลายเดือนก่อน

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

  • @Multihuntr0
    @Multihuntr0 9 ปีที่แล้ว +3

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

    • @robertpierce5142
      @robertpierce5142  9 ปีที่แล้ว

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

  • @NYFL2156
    @NYFL2156 8 ปีที่แล้ว +5

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

    • @robertpierce5142
      @robertpierce5142  8 ปีที่แล้ว +2

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

    • @robertpierce5142
      @robertpierce5142  8 ปีที่แล้ว +2

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

  • @niteshjain1231
    @niteshjain1231 6 ปีที่แล้ว +4

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

    • @robertpierce5142
      @robertpierce5142  6 ปีที่แล้ว

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

    • @johndebord7802
      @johndebord7802 6 ปีที่แล้ว

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

  • @lamureon
    @lamureon 5 ปีที่แล้ว +1

    thanks for the great explanation

  • @yuvrajsakshith9405
    @yuvrajsakshith9405 3 ปีที่แล้ว

    Very insightful! Thank you! :)

  • @solmindaudy
    @solmindaudy 8 ปีที่แล้ว +1

    Thanks Alot Robert Sir. :)

  • @jeremydavie4484
    @jeremydavie4484 7 หลายเดือนก่อน

    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?

  • @2777kk
    @2777kk 5 ปีที่แล้ว +2

    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?

    • @ronnykuckuck4390
      @ronnykuckuck4390 4 ปีที่แล้ว

      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.

  • @purnimasaikia7776
    @purnimasaikia7776 7 ปีที่แล้ว

    Very helpful for my exam, thank u so much

  • @miketurner3461
    @miketurner3461 3 ปีที่แล้ว +1

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

    • @typingcat
      @typingcat 2 ปีที่แล้ว

      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.

  • @MercuryTheWhite
    @MercuryTheWhite 9 ปีที่แล้ว +1

    Very helpful. Thank you! :)

  • @husseinsuhail7961
    @husseinsuhail7961 9 ปีที่แล้ว +1

    thank you very much,explain very clearly.

  • @hishamalassedy
    @hishamalassedy 5 ปีที่แล้ว +2

    thank you for this video, but I didn't understand how 27G=8G ? at 16:44

    • @robertpierce5142
      @robertpierce5142  5 ปีที่แล้ว +1

      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.

    • @hishamalassedy
      @hishamalassedy 5 ปีที่แล้ว +1

      @@robertpierce5142 thank you very much

  • @omar778
    @omar778 5 ปีที่แล้ว +2

    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

    • @robertpierce5142
      @robertpierce5142  5 ปีที่แล้ว +2

      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.

    • @omar778
      @omar778 5 ปีที่แล้ว +1

      @@robertpierce5142 thank you so much

    • @ilovekog
      @ilovekog 3 ปีที่แล้ว +1

      @@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 :)

  • @nathanstene3601
    @nathanstene3601 2 ปีที่แล้ว +1

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

    • @robertpierce5142
      @robertpierce5142  2 ปีที่แล้ว

      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.

  • @wella907
    @wella907 7 ปีที่แล้ว +1

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

    • @robertpierce5142
      @robertpierce5142  7 ปีที่แล้ว +2

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

    • @jasoncoombs7097
      @jasoncoombs7097 6 ปีที่แล้ว

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

  • @shrutipatkar3256
    @shrutipatkar3256 9 ปีที่แล้ว

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

  • @pineneedle
    @pineneedle 7 ปีที่แล้ว

    Best video on ECC.

  • @TomAtkinson
    @TomAtkinson 6 ปีที่แล้ว +1

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

    • @robertpierce5142
      @robertpierce5142  6 ปีที่แล้ว +1

      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.

  • @rslitman
    @rslitman 2 ปีที่แล้ว

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

    • @robertpierce5142
      @robertpierce5142  2 ปีที่แล้ว

      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.

  • @whatyouwantyouare
    @whatyouwantyouare 5 ปีที่แล้ว +1

    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
      @whatyouwantyouare 5 ปีที่แล้ว +1

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

    • @robertpierce5142
      @robertpierce5142  5 ปีที่แล้ว

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

  • @beback_
    @beback_ 7 ปีที่แล้ว +1

    That was awesome. Amazing.

  • @zhiyizhu3040
    @zhiyizhu3040 5 ปีที่แล้ว +2

    How do Bob and Alice agree on the Domain parameter(a, b, G, etc.), so that they are actually using the same elliptic curve?

    • @robertpierce5142
      @robertpierce5142  5 ปีที่แล้ว +3

      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.

  • @munkh-erdenez2117
    @munkh-erdenez2117 7 ปีที่แล้ว

    Great tutorial.

  • @dormariel1409
    @dormariel1409 6 ปีที่แล้ว +1

    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?

  • @mauisstepsis5524
    @mauisstepsis5524 2 ปีที่แล้ว +1

    Is it a typo at 5:34, did you mean y_P =0 for the point doubling?

  • @MoshMoshProf
    @MoshMoshProf 6 ปีที่แล้ว +1

    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?

  • @jackzhp
    @jackzhp 9 ปีที่แล้ว +1

    nicely done!

  • @Whateverrrr863
    @Whateverrrr863 3 หลายเดือนก่อน +1

    14:20 - how is 13 square 16? Reduced by 17?

    • @robertpierce5142
      @robertpierce5142  3 หลายเดือนก่อน

      13 mod 17 == -4. (-4)^2 mod 17 == 16. One way of looking at it.

  • @RobertM949
    @RobertM949 8 ปีที่แล้ว

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

    • @robertpierce5142
      @robertpierce5142  8 ปีที่แล้ว

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

    • @RobertM949
      @RobertM949 8 ปีที่แล้ว

      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!

  • @thefirstfishadvancetheland8980
    @thefirstfishadvancetheland8980 7 ปีที่แล้ว

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

  • @tynansigg5472
    @tynansigg5472 8 ปีที่แล้ว +1

    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?

    • @robertpierce5142
      @robertpierce5142  8 ปีที่แล้ว

      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.

  • @tayyabakhtar6157
    @tayyabakhtar6157 7 ปีที่แล้ว +1

    why the R is negative on the first place ???

  • @alibaba888
    @alibaba888 3 ปีที่แล้ว +2

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

    • @robertpierce5142
      @robertpierce5142  2 ปีที่แล้ว +1

      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.

  • @leesweets4110
    @leesweets4110 3 ปีที่แล้ว +1

    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.

    • @robertpierce5142
      @robertpierce5142  3 ปีที่แล้ว

      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.

  • @shridharjoshi9028
    @shridharjoshi9028 7 ปีที่แล้ว +1

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

  • @richa2921
    @richa2921 6 ปีที่แล้ว +1

    great work !!!!

  • @t33d33
    @t33d33 7 ปีที่แล้ว

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