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
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!
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."
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.
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!
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!
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.
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.
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!!!
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.
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.
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.
Did he really just say if you multiple two big primes together you get a really big prime number? By definition that doesn't even make sense, the number n is the product of two prime numbers, p and q, but isn't prime itself.
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!
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!
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!
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 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.
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]
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 RUclips is it descripted but I can'find it... Can you divulge it to me? :)
@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 :)
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!
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!
@young inventors, great catch on this! I've replied to others on this same question... 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!
Great explanation of how EC works, but how does someone actually use this to encrypt something, say like a message or a string? Would the receiving party need the same private key to decrypt?
Hi Karen...great question! Typically, Elliptic Curve is used as a means to share keys between client and server but then the client and server use a different type of encryption to then encrypt all the messages between the two of them. AES is a very common encryption type for communicating between client and server. But, in order to use AES, the client and server must share keys, and Elliptic Curve can do that. Here's an article I wrote that explains in more detail: devcentral.f5.com/s/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
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.
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!
I'm impressed by writing the mirror images of text on the screen but this doesn't actually explain how anything is calculated. The dots are an operator which represents the number of intersections? How does the straight line re-intersect with the curve after it wraps around?
great question...thanks for asking! I wrote up an article that goes into much more detail on how the "dot" or point operations work. Here's the article: devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832 Hope this helps!
Hi sir is such encryption has to base in such C shape curve with a curve at upper + y axis and another curve at lower - y axis which in contact with the C that position at the middle of XY in 0.?
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.
Great video! there's a lack of accessible introductory videos about ECC, especially considering it's significance, so this video was very welcome. Just one correction though - the Elliptic Curve you are describing is *not* a function. For it to be a function it must be the case that for *every* x there is *at most* one y such that f(x)=y. But as you can see from the graph, this is not the case, as every x value corresponds to 2 distinct y values (except for maybe the x such that f(x)=0). This has to do with how an elliptic curve is defined, namely by the equation y^2 = x^3 + ax + b. So for example, when x=0, y^2=b, meaning y is plus or minus root b, and these two values are not identical whenever b≠0.
Borat, 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!
Actually I think what you drawn is a function. For a function to be bijective (finding x knowing y) we need it to be injective (for every x at most one y) and surjective (for every y only one x) what the function you drawn doesn't. We don't want that kind of functions in cryptography because that would basically mean if y is the crypted message you can "possibly easily" find x by finding the inverse bijection of the function. (Sorry for my English I'm a french speaker)
Yes, that curve is a manifold. Functions are mathematical abstractions. Mathematics is full of simplifying abstractions. Most things are manifolds. If you limit this particular curve to y>0, it becomes a function. Notice that the line representing the keys are in the space of y>0, so the relevant mathematical entities are functions. The elliptic curve is the manifold. The straight lines would be functions.
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.
What would be SUPER useful in my opinion is show that if G is the generator point demonstrate that 1G + 2G + 8G = 11G - becuase it's the commutative property that MUST be used to do multiplication, right? If it is, I think people will see why point multiplication is so easy, but point division is basically so difficult. In the example I gave, 11 would be the secret key, wouldn't it? You know the final point, but you don't know what the original number was for scalar multiplication. This was my difficulty in understanding this.
WELL it would have been nice to get a response, but I have all the information I need. G doesn't matter, as long as it's on the curve of course, It's commutative and associative and that can be demonstrated (to the satisfaction) of somebody studying this, but I don't think most people trying to understand this wants to understand the number theory behind it. 17 is small enough to calculate all points, and doing efficient scalar multiplication can easily be demonstrated on a small scale. The only reason we ever used RSA/RKS is because ECC was under patent, even though it was as far as I know, discovered or at least published first.
how did the sender created the encrypted message without knowing "n"?how many times did he run a through the function? the sender and the receiver must meet to share the value of n so this isn't PGP encryption
Here's an article I wrote that goes into more detail...I think you'll find more here: devcentral.f5.com/s/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
And what exactly is then the “dot” operation algorithmically? A . B means find another point on the intersection of the line connecting A and B with the elliptic curve?
Hi rewtnode...thanks for the question. For a further discussion on all the functions related to this, I wrote an article that goes into more detail. Here's the article...I think you'll find what you are looking for there: devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
There are a few confusing remarks such as "dotting A with itself" and "dotting the curve with itself", neither of which appears to have any clear meaning. The latter was probably just a slip of the tongue in trying to finish up in a hurry, but the other is repeated a few times. If we start with the curve and point A how can we possibly know where dotting A with itself will place B? Don't we need two points to get started? Or is the dot operation given by some formula that wasn't specified? That wouldn't seem to make much sense either because then the whole path A -> Z is completely determined by just the curve and A.
I wrote this article that goes into much more detail about how the math functions of ECC works: devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832 Hope you enjoy!
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.
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
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
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
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!!!
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!
found this while prepping for the interview. thank you for such simple and yet practical explanation!
I have read about this before, but this is clearly explained! Well done.
glad you enjoyed it!
@2:26 -- when you take two prime numbers and multiply them, you WILL not get a BIG prime number. Sorry about that.
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!
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!
This is a great easy-to-understand intro to ECC!
glad you enjoyed it!
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.
The best explanation that I got on Elliptic Curve Cryptography , great work John
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.
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!
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!
This was a fantastic intro to ECC, thanks for the clear explanation!
Glad you liked it! We appreciate the comment!
Easy, crisp explanation, loved 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.
You have saved my math project. Thank you
glad you enjoyed it!
I almost got an idea wats was it all about...thank you John Wagnon
I could not get this concept at all until I watched you're video. Thank you very much.
This video broke it down so well!! Thank you!!
glad you enjoyed it!
Great video! You explained this better than my uni prof XD
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!
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.
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.
Thanks, brother, you're a huge help in my Crypto class!
glad you enjoyed it!
this recursion is glossed over often, thanks
thanks for the comment!
Did he really just say if you multiple two big primes together you get a really big prime number? By definition that doesn't even make sense, the number n is the product of two prime numbers, p and q, but isn't prime itself.
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!
i'm very impressed about your skills writing backward
Thanks for the comment and here's how we produce these: ruclips.net/video/U7E_L4wCPTc/видео.html
Thank you! You have satisficed my curiosity
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!
am i the only one impressed by the way this guy is writing backward with such ease
see how we do it here: ruclips.net/video/U7E_L4wCPTc/видео.html
Well and simply explained, good job!
Very good introduction. I do get the basic idea of it now.
i'm glad it was helpful for you!
2:21 If you multiply two random prime numbers and multiply them together, you DON'T get a really big prime number.
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!
Above all, thanks for keeping the vid titles short
this is extremely well explained, thanks
Amazingly efficient explanation. How does this channel have so few viewers?
thanks! feel free to help spread the word about our channel and videos!
A very clear and interesting explanation! Thanks!
glad you enjoyed it!
Fantastic overview! Thank you!
thanks!
Thanks for providing this really useful intuition on the algorithm.
glad you enjoyed it!
Perfect. Thanks and great job.
Glad you enjoyed it!
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.
very outstanding explanation sir
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 didn't follow any of that because I was too impressed by your ability to write backwards! 😊
...
...
...
...
...
(Yes, I know.)
:-)
Great explanation.
glad you enjoyed it!
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 RUclips 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!
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!!
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 :)
Thank you for this wonderful video !
glad you enjoyed it!
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!!
thank you so much, you explained it so well
Glad you liked it and we appreciate the comment!
I never knew John Wagnon was so good at writing mirror image of letters
And I thought ECC stood for ERP Central Component :). Thanks for the great presentation!
This was really well explained
Thanks for the comment!
You said something incorrect around 2.26. Multiplying two prime numbers, you don't get a prime number back, you said we do.
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!
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!
great explanantion sir,for such complicated topic ..i hv exam tomorow and this gonna help me loooottttttt thnxaaaa tunssss.god bless u
2:25 did I hear "multiply two prime numbers and get a big prime number"??
@young inventors, great catch on this! I've replied to others on this same question...
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 information! And yeah it makes sense now... anyways, your lectures are really good! Keep up the good work!
@@younginventors5917 thanks so much!
This video is really interesting! Keep up the good work.
cool...glad you liked it!!
Great Video! Going to write a paper about ECC, this helped a lot.
The glass cleaner needs a raise.
talk to our boss before our compensation talks this fall :)
Excellent overview.
Thank you! Beautifully explained.
glad you enjoyed it!
Great video
glad you enjoyed it!
Great explanation of how EC works, but how does someone actually use this to encrypt something, say like a message or a string? Would the receiving party need the same private key to decrypt?
Hi Karen...great question! Typically, Elliptic Curve is used as a means to share keys between client and server but then the client and server use a different type of encryption to then encrypt all the messages between the two of them. AES is a very common encryption type for communicating between client and server. But, in order to use AES, the client and server must share keys, and Elliptic Curve can do that. Here's an article I wrote that explains in more detail: devcentral.f5.com/s/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
This video was super helpful thanks so much
glad you enjoyed it!
Very nicely explained sir thanku
Thanks for the comment and glad you enjoyed the video!
Great informative video!
glad you enjoyed it!
Brilliant Introduction
When he started writing on the board, that got my attention right away !
Yeah mine too
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.
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?
A good way to get a general idea of ECC
glad you enjoyed it!
Awesome video!
Appreciate the note!
sorry should have said that was awesome. Any chance you could please do a follow up discussing the maths of ZKP I'm confused with proofs and things.
This is the best explanation!
glad you enjoyed it!
I'm impressed by writing the mirror images of text on the screen but this doesn't actually explain how anything is calculated. The dots are an operator which represents the number of intersections? How does the straight line re-intersect with the curve after it wraps around?
great question...thanks for asking! I wrote up an article that goes into much more detail on how the "dot" or point operations work. Here's the article: devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
Hope this helps!
Fantastic work John!
Hi sir is such encryption has to base in such C shape curve with a curve at upper + y axis and another curve at lower - y axis which in contact with the C that position at the middle of XY in 0.?
Man i love your videos,Thank you so much
glad you enjoy them!
that was a really, really good intro to this topic
Multiplication of 2 random prime numbers does not yield (quote) "a really big prime number" 2:20
Hi Peter, thanks for the feedback! We added a correction card for that, appears a few seconds after your timecode.
Thanks ...
glad you enjoyed it!
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.
Great video! there's a lack of accessible introductory videos about ECC, especially considering it's significance, so this video was very welcome. Just one correction though - the Elliptic Curve you are describing is *not* a function. For it to be a function it must be the case that for *every* x there is *at most* one y such that f(x)=y. But as you can see from the graph, this is not the case, as every x value corresponds to 2 distinct y values (except for maybe the x such that f(x)=0). This has to do with how an elliptic curve is defined, namely by the equation y^2 = x^3 + ax + b. So for example, when x=0, y^2=b, meaning y is plus or minus root b, and these two values are not identical whenever b≠0.
Borat, 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!
Actually I think what you drawn is a function. For a function to be bijective (finding x knowing y) we need it to be injective (for every x at most one y) and surjective (for every y only one x) what the function you drawn doesn't. We don't want that kind of functions in cryptography because that would basically mean if y is the crypted message you can "possibly easily" find x by finding the inverse bijection of the function.
(Sorry for my English I'm a french speaker)
Thanks for the great perspective on this!
Yes, that curve is a manifold. Functions are mathematical abstractions. Mathematics is full of simplifying abstractions. Most things are manifolds. If you limit this particular curve to y>0, it becomes a function. Notice that the line representing the keys are in the space of y>0, so the relevant mathematical entities are functions. The elliptic curve is the manifold. The straight lines would be functions.
This was incredibly helpful. Thank you!
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.
I kept getting thrown by how great he can write clearly for us backwards. Just struck me that it makes way more sense that it's just a mirror image 🤣
Thanks for the comment! This is how we do lightboards: ruclips.net/video/U7E_L4wCPTc/видео.html
Very good video
glad you enjoyed it!
great, good content
Glad you enjoyed it and we appreciate the comment!
What would be SUPER useful in my opinion is show that if G is the generator point demonstrate that 1G + 2G + 8G = 11G - becuase it's the commutative property that MUST be used to do multiplication, right? If it is, I think people will see why point multiplication is so easy, but point division is basically so difficult. In the example I gave, 11 would be the secret key, wouldn't it? You know the final point, but you don't know what the original number was for scalar multiplication. This was my difficulty in understanding this.
WELL it would have been nice to get a response, but I have all the information I need. G doesn't matter, as long as it's on the curve of course, It's commutative and associative and that can be demonstrated (to the satisfaction) of somebody studying this, but I don't think most people trying to understand this wants to understand the number theory behind it. 17 is small enough to calculate all points, and doing efficient scalar multiplication can easily be demonstrated on a small scale.
The only reason we ever used RSA/RKS is because ECC was under patent, even though it was as far as I know, discovered or at least published first.
Thanks for your wonderful presentation.
how did the sender created the encrypted message without knowing "n"?how many times did he run a through the function? the sender and the receiver must meet to share the value of n so this isn't PGP encryption
Here's an article I wrote that goes into more detail...I think you'll find more here: devcentral.f5.com/s/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
Are you writing all of the stuff on the screen backwards??
And what exactly is then the “dot” operation algorithmically? A . B means find another point on the intersection of the line connecting A and B with the elliptic curve?
Hi rewtnode...thanks for the question. For a further discussion on all the functions related to this, I wrote an article that goes into more detail. Here's the article...I think you'll find what you are looking for there: devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
There are a few confusing remarks such as "dotting A with itself" and "dotting the curve with itself", neither of which appears to have any clear meaning. The latter was probably just a slip of the tongue in trying to finish up in a hurry, but the other is repeated a few times. If we start with the curve and point A how can we possibly know where dotting A with itself will place B? Don't we need two points to get started? Or is the dot operation given by some formula that wasn't specified? That wouldn't seem to make much sense either because then the whole path A -> Z is completely determined by just the curve and A.
I wrote this article that goes into much more detail about how the math functions of ECC works: devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
Hope you enjoy!
Thanks, that cleared it up!