Elliptic Curve Cryptography Overview
ฝัง
- เผยแพร่เมื่อ 13 ต.ค. 2015
- John Wagnon discusses the basics and benefits of Elliptic Curve Cryptography (ECC) in this episode of Lightboard Lessons.
Check out this article on DevCentral that explains ECC encryption in more detail: community.f5.com/articles/rea...
Corrections:
02:24 As we all know, a prime number only has itself and 1 as factors. So, if you multiply two numbers together, the resultant number will at least have the two numbers you multiplied as factors…thus not making it prime. Technically speaking, the product of the two prime numbers in RSA is called a “semiprime” number because its only factors are 1, itself, and two prime numbers. - วิทยาศาสตร์และเทคโนโลยี
![[UNCUT] ฝันรักห้วงนิทรา | EP.8 (4/4)](http://i.ytimg.com/vi/RDYJYiDwsj0/mqdefault.jpg)
how is this guy so good at writing backwards...
That's is an awesome observation !
Vid is flipped, kek.
Shirt button on left side
Ring, watch and shirt pocket on right side, lol
...cause he's left handed.
I never knew Matthew McConaughey was so good at math
alright alright alright
56 bits? Those are rooky bits, you need to get that bit count way up! 256 bits at least!
well he was an engineer or something in interstellar
Looks more like Chris Martin
LMAO!!!
found this while prepping for the interview. thank you for such simple and yet practical explanation!
Good introduction to ECC. In you intro to RSA you mention taking random prime numbers and multiplying them to get a really big prime number. The result is a really big composite number(not prime) that is hard to factorize.
I think he meant to say semi-prime number, ie a number which only factors are two prime numbers. It is easily provable that by multiplying two prime numbers you get semi-prime number.
Protip: doing G + G is the equivalent of finding the point tangent to the curve at G! And since we already have added "two" points (the curve doesn't care if the points are different), the curve will only intersect at one other point!
Fantastic work John!
this is by far the best video i have come across. Simple, explained in layman's terms to beginners and under 15 minutes. rate this 10 out of 10
Love how you have to plug the BIG-IP thing at the end (someone has to pay for the Light Board. Well done, sir. You are a great presenter. One of the best I've come across.
glad you enjoyed the video!
I have read about this before, but this is clearly explained! Well done.
glad you enjoyed it!
This video broke it down so well!! Thank you!!
glad you enjoyed it!
This is a great easy-to-understand intro to ECC!
glad you enjoyed it!
This was a fantastic intro to ECC, thanks for the clear explanation!
Glad you liked it! We appreciate the comment!
A very clear and interesting explanation! Thanks!
glad you enjoyed it!
The best explanation that I got on Elliptic Curve Cryptography , great work John
Thanks, brother, you're a huge help in my Crypto class!
glad you enjoyed it!
2:20 wrong; the product of two prime numbers is always non-prime - because it has the two prime numbers as factors.
great observation! I put some clarification info on this in another comment section from another user below. Here's the info:
During my quick explanation of RSA, I said that two prime numbers are multiplied together to produce a really big prime number (at 2:20 - 2:25 in the video). As we all know, a prime number only has itself and 1 as factors. So, if you multiply two numbers together, the resultant number will at least have the two numbers you multiplied as factors…thus not making it prime. Technically speaking, the product of the two prime numbers in RSA is called a “semiprime” number because its only factors are 1, itself, and two prime numbers. Here’s a more detailed explanation of semiprimes: en.wikipedia.org/wiki/Semiprime
For each RSA number "n", there exist prime numbers “p” and “q” such that n = p × q
The problem is to find these two primes, given only n. The salient point for RSA is that “n” will always be semiprime.
All that said, I should have said “a really big semiprime number” in the video, but I didn’t want to take up too much time discussing RSA since this video is targeted for ECC.
Thanks again for the great catch on this!
EI Radon : Nice observation however please be humble and polite while pointing out the mistake.
I think he was direct and to the point. Nothing too bad about that. Rather than saying "wrong", maybe saying 'Great work on the video, however I've noticed a minor mistake."
If you are in a prime space the product of to prime numbers is still a prime number
Thanks
Thanks for your wonderful presentation.
I could not get this concept at all until I watched you're video. Thank you very much.
I almost got an idea wats was it all about...thank you John Wagnon
Thank you for this wonderful video !
glad you enjoyed it!
Thank you! Beautifully explained.
glad you enjoyed it!
This video is, by far, the best video on eliptic curve criptography availiable... wish you could do more videos about this subject, congratulations for the amazing work!!!
glad you enjoyed it!
Excellent presentation. The Elliptic Curve in the video is drawn based on y^2=x^3-3x+5. The actual elliptic curve used in the algorithm will have much bigger prime numbers and will look much different. The same logic applies to either case, so it doesn't quite matter. Just for your information.
thank you
Thanks for this! I was contemplating asking if the initial elliptic curve was a static one that remained the same.
Thanks for providing this really useful intuition on the algorithm.
glad you enjoyed it!
Fantastic work on the video! A lot of smart people forget that it is hard to learn things when they make it super complicated; I hope that I can be as good as you one day :D. I thought I would summarize the video for myself (and others if they might also benefit from it?) and ask a few questions.
From what I understand, elliptic curve cryptography uses fewer bits to create as complex of a trapdoor function as RSA (which is basically trying to factor a really large semi-prime number).
In elliptic curve cryptography, you start with two points on this elliptic curve (looks like an octopus and is symmetric about y-axis) and you find the third point you find when you draw a line between those to find another point on the graph and then find the point symmetric to that about the x-axis.
E.g. If the initial two points were A and B, the third point would be notated as A + B = C. Then you do A + C to find D. And then you do A * D = E … and so on until you find some point Z on this elliptic curve.
The number of these additions you have to do to acquire Z is the “private key”, which is why this computation is often written as K = k * G, where k is the private key, K is the point we are trying to reach, and G is the generator point (the point we start at and is constant for a certain graph).
Some questions I have are:
1) From what I understand, exponentiation by squaring makes this logarithmically easier and allows one to verify this quickly - but how does one square these “dot products”? These are not just vectors going through some kind of constant transformation when you do A * B (at least from what I understood).
I have now found that addition is commutative in elliptic curves! So doing 4 * G can be simplified as (G + G) + (G + G); or basically that you can break down a multiplication in about log_2(k) steps.
2. How do you encode a point on a graph as one number? Would you just encode the y values? I am not sure that it would be super helpful towards finding the squares of two numbers though.
I found out that that the first half of the bits are the x coordinates and the second half are the y coordinates.
3. What is the reason behind the reduction in bits of elliptic curve cryptography?
Still not sure about this!
4. What exactly happens when a point goes over the maximum? You find how much it is above the maximum, and make it that much more than the x minimum (how do you decide if the new value is positive or negative)? What happens if the new x value is also more than the maximum? Do you just keep on moving the value back until the value is below the maximum?
First off: All of this is just math. Without a proper degree in math it'll be quite difficult to understand. They don't "make it hard", they use existing theorems that may not be simple to a layman to solve problems.
Second: It's not about having a "complicated" trapdoor function, it's about having a secure one. RSA is very simple to implement and understand with some basic number theory, however it's also very secure. Something else that you could devise might be extremely complicated, but not too secure when it comes down to it. Security and complexity are different.
Third: the octopus looking elliptic curves are only a certain family of elliptic curves. there are some where it is broken into two parts.
To answer question three for you: It's a reduction in size, because ECC has more uncertainty than RSA with the same sized keys - that is to say, it's harder to brute force ECC than RSA.
Edit: My answer was slightly unclear, so let me rephrase it: There are "efficient" methods to brute force RSA (even disregarding Shor's metaphorical elephant in the room). There are methods to brute force RSA that are faster than just guessing and checking everything, which actually scale better than encrypting does. ECC on the other hand has no algorithm as a shortcut - the only method to brute force it is the naive method which scales at the exact same rate that the key size does.
Thanks for the nice intuition!
Well and simply explained, good job!
Amazingly efficient explanation. How does this channel have so few viewers?
thanks! feel free to help spread the word about our channel and videos!
very clear explanation. thanks you sir.
Fantastic overview! Thank you!
thanks!
This video is really interesting! Keep up the good work.
cool...glad you liked it!!
It took me a while to realize and appreciate that this dude is writing backwards so we can read it forwards. Also, love your eyeballs. They are grade A, top-shelf eyeballs.
Excellent overview.
Very good introduction. I do get the basic idea of it now.
i'm glad it was helpful for you!
Fantastic, clear and well made video. Got here while reading “Mastering Ethereum” and wanting a more thorough understanding of ECC maths. Got what I wanted!
Appreciate the comment!
Great Video! Going to write a paper about ECC, this helped a lot.
Fun fact, but my integral Calculus teacher in university was one of the creators of this :) Neil Koblitz. Very smart dude.
Wow, very cool! Thanks for the comment!
Thanks for your wonderful presentation
glad you enjoyed it!
It baffles me how people have the knowledge enough to 1) Come up with such ideas and most importantly 2) To code such applications that can do such complex things. The cryptographic world is so unique in so many ways, as us people many times take it for granted to ease of use in such applications since we can freely use them, but lord knows the backend behind all that computation
Thank you! You have satisficed my curiosity
Above all, thanks for keeping the vid titles short
this is extremely well explained, thanks
You have saved my math project. Thank you
glad you enjoyed it!
This video was super helpful thanks so much
glad you enjoyed it!
That was one very clear explanation of ECC. How can there be any thumbs down AT ALL?
glad you enjoyed it!
And I thought ECC stood for ERP Central Component :). Thanks for the great presentation!
Nice Explanation!!
great explanantion sir,for such complicated topic ..i hv exam tomorow and this gonna help me loooottttttt thnxaaaa tunssss.god bless u
Man i love your videos,Thank you so much
glad you enjoy them!
Awesome video!
Appreciate the note!
Great informative video!
glad you enjoyed it!
i'm very impressed about your skills writing backward
Thanks for the comment and here's how we produce these: th-cam.com/video/U7E_L4wCPTc/w-d-xo.html
this recursion is glossed over often, thanks
thanks for the comment!
Very informative. Thank you.
glad you enjoyed it!
Great explanation!
glad you enjoyed it!
I’m an IT undergraduate and I’m currently figuring out quadratic curves and surfaces. I heard about elliptic curve cryptography from some espionage series and I’ve been really thrilled to learn about them ever since. Just putting it out there.
Great video! You explained this better than my uni prof XD
Glad you enjoyed it!
Excellent video, thanks a lot
glad you enjoyed it!
thank you so much, you explained it so well
Glad you liked it and we appreciate the comment!
thanks professor ... well done
Good video.
Thanks
very outstanding explanation sir
Perfect. Thanks and great job.
Glad you enjoyed it!
This was incredibly helpful. Thank you!
Great explanation.
glad you enjoyed it!
This was really well explained
Thanks for the comment!
Interesting topic! Learned a lot. You type backwards really well. :-)
Flipped video my man
This is the best explanation!
glad you enjoyed it!
that was a really, really good intro to this topic
Great video. I have a question, if you have the power potencial to multiply your private key and the "generator point" to get your public key, can you get the private key if you have the public key and the "generator point"? I mean iterating over and over and saving every result until match with your public key (that can be the same process that you used to get it at the first time).
Thanks
great question! this is at the heart of the underlying foundation that it is easy to compute these values going one way, but extremely difficult to compute them going the other. that is, if you have the value of the private key and the generator point, you can easily determine the value of the public key. but, if you only have the public key and the generator point, then it's very difficult to figure out the private key. the fundamental mathematics behind all of this is based on the "Elliptic Curve Discrete Logarithm Problem". at first glance, it sounds fairly trivial to start with a generator point and then keep calculating until you get to the public key value...then you would have your private key value. but it's actually very difficult in real practice to do that.
here's an article I wrote that explains all of this in more detail: devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
I hope this helps!
link goes to a page not found, and link in description seems to go to a black page. Are there new links?
This is super nice and easy. I was trying to understand how encryption and decryption work in web 3.0 and I got just what I need on ECC
Glad you enjoyed and we appreciate the comment!!
am i the only one impressed by the way this guy is writing backward with such ease
see how we do it here: th-cam.com/video/U7E_L4wCPTc/w-d-xo.html
This is awesome!
We appreciate the comment!
Man these videos are so good, even my dumbass is able to understand these topics, thanks John!
He does make technology easy to understand. We appreciate the comment!!
Brilliant Introduction
When he started writing on the board, that got my attention right away !
Yeah mine too
You're best one-way-function-teacher I have ever met. Finally I find out what the point and sense is.
(I saw this super-interactive presentation technique but never discovered what do you use for the transparency and written-in-air effect. I know that somewhere in the TH-cam is it descripted but I can'find it... Can you divulge it to me? :)
here you go! devcentral.f5.com/articles/lightboard-lessons-behind-the-scenes
Thanks! Nice gadget!
Great video
glad you enjoyed it!
Good Explanation
just a technicality: eliptic curve can't be defined as a function, it's more of a formula. That's why it's called a curve, not a math function.
Anna, thanks for the comment. Technically, you are correct because a math function is a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output. So, in the case of the elliptic curve I drew in the video, it's true that, for a given value on the x-axis, there are multiple resulting y-axis values. So, from a technical definition of a function, this elliptic curve is not a function. That said, the concept of function can also be extended to an object that takes a combination of two (or more) argument values to a single result. When I used the term "function" in the video, I didn't take into account the very technical definition of the word. Rather, I used it in a more generic sense whereby it can be graphed on the x/y-axis. Thanks again for the clarification!
Yes, technically the curve he drew represents a mathematical "relation", not a proper "function" [as in a function one f(x) can result in only one value of y, not two or more]
This is very good video to eplain ECC. Thanks
glad you enjoyed it!
I never knew John Wagnon was so good at writing mirror image of letters
awesome vid
thx
glad you enjoyed it!
I have always operated under the knowledge that multiplying two prime numbers will result in a number that is certainly not prime, as it will have factors 1, itself, and the two numbers used to generate it?
+Brian Morgan Great point and great catch! During my quick explanation of RSA, I said that two prime numbers are multiplied together to produce a really big prime number (at 2:20 - 2:25 in the video). As we all know, a prime number only has itself and 1 as factors. So, if you multiply two numbers together, the resultant number will at least have the two numbers you multiplied as factors…thus not making it prime. Technically speaking, the product of the two prime numbers in RSA is called a “semiprime” number because its only factors are 1, itself, and two prime numbers. Here’s a more detailed explanation of semiprimes: en.wikipedia.org/wiki/Semiprime
For each RSA number "n", there exist prime numbers “p” and “q” such that n = p × q
The problem is to find these two primes, given only n. The salient point for RSA is that “n” will always be semiprime.
All that said, I should have said “a really big semiprime number” in the video, but I didn’t want to take up too much time discussing RSA since this video is targeted for ECC.
Thanks again for the great catch on this!
+F5 DevCentral Thanks for the response, sir. That helps clear it up. I just wasn't certain if I had missed something in my formative years, or had been lied to all that time :) You broke down a complex topic very well and made it digestible for those interesting in such processes. Thanks!
Very nicely explained sir thanku
Thanks for the comment and glad you enjoyed the video!
Hold on though... on the Diffie Hellmann algorithm integers are chosen randomly. In the ECC algorithm you have to calculate the nth term by using a sequence of dot operations to arrive at your private number. The point is, calculating your private key is a linear sequence of prescribed operations with a finite terminating point. All an attacker would have to do is run through the operations themselves, which they could do.... they dont know where you stopped but they only need to find the first one that works. And if you can computer yours, surely they can compute it too.
@qwerty ytrewq Why dont they know where it started?
@qwerty ytrewq Dont both parties have to choose the same value though? Or some communication of the value? Seems to me that either it isnt random or, if it is, its publicly accessible information. How do you exchange the starting point between the two parties without risking an unwanted third party also having it? Im sincerely at a loss here understanding how this works...
I'm learning this myself, but ill try to answer as good as I can.
Lets call the secret=x, and the publicly known starting point=P.
The public key x*P is the final point you land on when adding(or dotting) P to itself x times. This is also publicly known.
There are two main operations you can do on points, a) adding two points, b) doubling a point(adding it to itself)
a. In the video he explains how you can add two points by drawing a line, see where it intersects, and reflecting over the x-axis.
b. You can also add a point to itself. This is almost the same as adding two points. This is done by taking the tangent line on that exact point, see where it intersects, and reflecting over the x-axis. Any tangent line on the curve intersects the curve on exactly two points. The point on the tangent line and one other point.
The reason why an attacker can't (easily) run through the same operations is:
Lets say x=44.
Knowing that x=44, you can calculate 44*P this in 7 steps:
1. (using b): 2P = P+P
2. (using b): 4P = 2P + 2P // You have already calculated the point 2P, and know where it is on the curve, so you can just add that point to itself
3. (using b): 8P = 4P + 4P
4. (using b): 16P = 8P + 8P
5. (using b): 32P = 16P + 16P
6. (using a): 40P = 32P + 8P // Two points you already calculated
7. (using a): 44P = 40P + 4P
You can't do this in 7 steps as an attacker, you have to do it in 44 steps, because you have to check every number along the way to see if it matches the point x*P. If x was 9, and you did these 7 steps, you would skip the solution.
If the secret key was a bigger, more realistic number, e.g. x=2^256, you can calculate x*P in 256 steps, which is nothing, your computer will do it in a fraction of a second.
While the attacker has to do it in 2^256 steps, which is about the estimated amount of particles in the observable universe. And impossible to compute in a thousands if lifetimes, even if you put every computer to it.
This is the trap door that makes it a one way function.
In the Diffie Hellman key exchange they do not have to chose the same secret key.
If they were to chose the same key, the would have to communicate it to each other safely somehow. If they already had a safe communication there would be no need for exchanging a key using Diffie Hellmann. They could just use the private key they just shared a the symmetric encryption key instead.
If Allice and Bob were to agree on a key on an unencrypted network using DH:
They both agree on a publicly known starting point P on a publicly known curve.
Lets say Allice chooses the private key SA=5, and Bob chooses the private key SB=7.
They both calculate the public key, which is private key*P, and sends this to each other over the open internet.
So Allice calculates the point PA=5*P, and bob calculates the point PB=7*P
Now they both multiply the public key they get from each other with their own private key.
Allice calculates 5*PB = 35P, and Bob calculates 7*PA= 35P. They both ended up on the same point, so now they can use the x-axis of the point 35P as the symmetric key.
And there is no way of getting to 35P, without knowing the numbers 5 or 7 just by knowing P PA and PB, the attacker would have to guess one of the numbers 5 or 7.
prime number multiplied by another prime will not give you a prime number :] Great videos, keep up the good job!
@dimitar, Great point and great catch! During my quick explanation of RSA, I said that two prime numbers are multiplied together to produce a really big prime number (at 2:20 - 2:25 in the video). As we all know, a prime number only has itself and 1 as factors. So, if you multiply two numbers together, the resultant number will at least have the two numbers you multiplied as factors…thus not making it prime. Technically speaking, the product of the two prime numbers in RSA is called a “semiprime” number because its only factors are 1, itself, and two prime numbers. Here’s a more detailed explanation of semiprimes: en.wikipedia.org/wiki/Semiprime
For each RSA number "n", there exist prime numbers “p” and “q” such that n = p × q
The problem is to find these two primes, given only n. The salient point for RSA is that “n” will always be semiprime.
All that said, I should have said “a really big semiprime number” in the video, but I didn’t want to take up too much time discussing RSA since this video is targeted for ECC.
Thanks again for the great catch on this!
@@devcentral It was clear that you made a verbal mistake. As you mentioned the RSA numbers are semiprimes and the whole RSA cryptography relays on the fact that there is no efficient method for finding the prime factors of a semiprime number (other than brutforcing). If you are to come up with a new theorem solving this problem you can break the RSA encryption :)
This was a very good explanation , really got me clear on my concepts.
glad you enjoyed it!
I'm sorry you feel that this cleared up your concepts as John Wagon's could not be more wrong. He does not understand what a prime number is, he's the definition of a mathematical function is wrong, his "dot" operation is complete none-sens, his RAS/ECC security level comparison has no foundation, his ECC public key of max is a notion that does not exist, he never explained how to dot A with itself so I'm not sure how he got 2A. In summary, the first 2 minutes do not respect the mathematical foundations I learn in middle school and the rest is a pure invention. To be honest, I thought the video was a joke that my cryptography professor directed towards when he asked to explain what was wrong in the explanation.
A good way to get a general idea of ECC
glad you enjoyed it!
Very good video
glad you enjoyed it!
great, good content
Glad you enjoyed it and we appreciate the comment!
I didn't follow any of that because I was too impressed by your ability to write backwards! 😊
...
...
...
...
...
(Yes, I know.)
:-)
This is really great , thank you
Glad you enjoyed the video!
awesome good job.
glad you enjoyed it!
Thank you
glad you enjoyed it!
Great video-At 2.24, you mentioned multiply 2 big prime numbers together and you get a
larger prime number? I think you meant you get a large composite number.
4:50 He detached from reality and literally dreamed of a curve while saying "So we are gonna draw an elliptic curve on this graph" haha
very good
Nice video
Thanks!
I regret wanting to know this information, I watched several videos on the basics of assymetric encryption for a course and everyone of them just uses the "locked mailbox " analogy but I just needed to know or else I wouldnt be able to move past it... I now know enough to know that I should have been happy with the mailbox analogy lol
Nice short explanation of a very complex subject. Actually I am looking at such explanations to help me to understand whether relatively simple 'dotting' is commonly used in implementations or whether 'point doubling' (where the line is a first derivative 'tangent' to the curve rather than a sort of chord) is actually used. IMO you got the distinction wrong there with regard to 'dotting with itself' which is 'point doubling' not exactly the same as 'dotting'. Also, the reflecting across the x axis is, I believe, part of the group operation. That is to say that A dot B gives you an intermediate point which when reflected gives you C.
Anyway, good job with the video. It is difficult to simplify without losing some perhaps trivial distinctions, and you probably know more about it than I do in the long run.
Thanks for the reply, Ray! Here's a more in-depth article that I wrote on this subject...it goes into more detail on the Point Addition and Point Doubling operations: devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
Thanks for that. It is clearer to me now about how point doubling is sometimes used on the first composition and subsequent compositions are all point additions.