Elliptic Curve Cryptography Overview
Вставка
- Опубліковано 15 гру 2024
- 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.c...
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.
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
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!!!
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: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!
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
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!
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!
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.
I have read about this before, but this is clearly explained! Well done.
glad you enjoyed it!
This is a great easy-to-understand intro to ECC!
glad you enjoyed it!
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!
The best explanation that I got on Elliptic Curve Cryptography , great work John
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.
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.
I almost got an idea wats was it all about...thank you John Wagnon
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!
I could not get this concept at all until I watched you're video. Thank you very much.
That was one very clear explanation of ECC. How can there be any thumbs down AT ALL?
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
i'm very impressed about your skills writing backward
Thanks for the comment and here's how we produce these: ua-cam.com/video/U7E_L4wCPTc/v-deo.html
You have saved my math project. Thank you
glad you enjoyed it!
This video broke it down so well!! Thank you!!
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.
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: ua-cam.com/video/U7E_L4wCPTc/v-deo.html
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!
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 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!
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]
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.
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.?
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.
Above all, thanks for keeping the vid titles short
Great video! You explained this better than my uni prof XD
Glad you enjoyed it!
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!
Amazingly efficient explanation. How does this channel have so few viewers?
thanks! feel free to help spread the word about our channel and videos!
Fantastic work John!
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 very clear and interesting explanation! Thanks!
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!!
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
i have problems understanding from the point where he draws the curve... i wonder if there are better resources on ecc?
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 I thought ECC stood for ERP Central Component :). Thanks for the great presentation!
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!
I'm sorry i don't understand how can u deal with values which are higher than the max value ?
Thanks
Hi Bot 505...great question! The way this works is that, if a number goes beyond the max value, then it essentially "wraps around" to the beginning and continues from there. So, in a very simple example, if you were counting to 12 and the "max value" is 10, then you would count to 10 and then wrap around to the beginning and finish the counting...leaving you at the value of 2. That's the idea behind how you can use values that extend beyond the max value. Hope this helps!
Thanks you , i understand the idea.
Very good introduction. I do get the basic idea of it now.
i'm glad it was helpful for you!
I never knew John Wagnon was so good at writing mirror image of letters
Thanks for providing this really useful intuition on the algorithm.
glad you enjoyed it!
I couldn't find the article. What is the name? HELP
great explanantion sir,for such complicated topic ..i hv exam tomorow and this gonna help me loooottttttt thnxaaaa tunssss.god bless u
Fantastic overview! Thank you!
thanks!
You can merge RSA and ECC to become RSA more effective?
Great question! Many web servers do utilize both RSA and ECC. The RSA part is used for server authentication (make sure you know that the server you are accessing is actually the correct server) and then utilize ECC for key exchange (much faster than RSA). Both of these functions must take place (authentication and key exchange), so it's nice to use each one in the way that makes the most sense. Hope this helps!
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!
I don't understand when it stops iteration?
How do you measure the equivalence in length of keys of both algorithms?
You don't! It's based on difficulty of solving the problem with known algorithms. The question is, how long the key should be, if you want same level of security as n-bit symmetric cipher(for example AES).
Well and simply explained, good job!
Thank you for this wonderful video !
glad you enjoyed it!
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 :)
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.
The glass cleaner needs a raise.
talk to our boss before our compensation talks this fall :)
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!
Perfect. Thanks and great job.
Glad you enjoyed it!
Great Video! Going to write a paper about ECC, this helped a lot.
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
Thank you! You have satisficed my curiosity
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.
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 UA-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!
I didn't follow any of that because I was too impressed by your ability to write backwards! 😊
...
...
...
...
...
(Yes, I know.)
:-)
this is extremely well explained, thanks
very outstanding explanation sir
so is Z the public key ?
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!!
Are you writing all of the stuff on the screen backwards??
Can you please provide c#code to encrypt / decrypt string using ECC
Found this on codeproject: www.codeproject.com/Tips/1071190/Encryption-and-Decryption-of-Data-using-Elliptic-C, hope that helps.
very complex topic ... how do you encryp or decrypt messages then ? even though you only SIGN messages, most of the times ?
Hi Riccardo! I wrote an article that explains this in a little more detail: devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832.
This should help explain the encryption/decryption process for ECC.
Great explanation.
glad you enjoyed it!
Do you use RSA to lock down that n?
hi Hung...great question! the value for "n" is secure based on the fundamental way that the Elliptic Curve Discrete Logarithm function operates. It seems trivial that you could track the value for "n" but it turns out to be very difficult. Here's an article that I wrote that goes into more detail on all of this: devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
hope this helps...thanks!
How does it mean to dot?
Hey Eirin...great question! Here's an article I wrote that goes into more detail...including the "dot" operation.
devcentral.f5.com/s/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
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.
Hello sir
How can I encoded the message to a point in ECC over the prime field?
Here's an article I wrote that goes into more detail about encrypting messages using ECC: devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
Thank you! Beautifully explained.
glad you enjoyed it!
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!
What would the public key be in this case?
+K Milhouse The short answer is that the public key is a randomly-chosen point on the curve, and the (x,y) coordinate values of that random point are used to derive the public key. It's interesting because all this encryption ultimately relies on the ability to properly choose a truly random point on the curve. I'm writing a paper that goes into more detail, and I'll post the link here when I'm done.
+F5 DevCentral but in this example would A be the public key?
Here's a link to the article I wrote that explains this in more detail: devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
is there any relation between discrete logarithm and integer factorization?
This was really well explained
Thanks for the comment!
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.
how this dot function works ?
Excellent overview.
A good way to get a general idea of ECC
glad you enjoyed it!
But how do you actually encrypt something with that private key?
thank you so much, you explained it so well
Glad you liked it and we appreciate the comment!
that was a really, really good intro to this topic
And what is the public key in ecc?
Great question! Keep in mind that ECC can be used in conjunction with more than one type of public key cryptosystem, but it is generally used for key exchange purposes in conjunction with the Diffie Hellman key exchange protocol. In Diffie Hellman, the public key is the calculated point on the curve that is derived from their private key and a point "G" which is the generator point on the curve (their private key is a random number chosen by each of the client and server...not the same random number, but each one chooses their own random number). That public key (point on the curve) is calculated by each side and then sent to the other. Then, the other can use their own private key to calculate a shared key value that can be used for bulk encryption.
But if we keep gradually increasing the number of time of "dot" function and try every output as it goes, doesn't it mean we could eventually reach the right Z? My impression is the only thing Z depends on is just the number of "dot" function, while I'm aware that factoring a number into primes in RSA is hard since it's a combinatorial problem. Am I missing something?
great question! it would seem like an easy task to start at the starting point and then keep track of how many times you conducted the operation and then when you hit the end point, you have the answer of how many times it took. while it appears trivial, it actually is hard to do that because of the modulo portion of these operations. if you recall the "max" portion of these operations, it sets a limit on the available space to operate, so if a value falls beyond the max number, then you wrap it around and continue from the beginning to find the answer to that specific operation. so if you were trying to find "N" and you kept track of the number of times you conducted the operation and then you found yourself landing on the number "Z" you would think that you now know the value for "N". but, it's entirely possible that the value for "Z" is hit once or twice (or more) during the "N" operations. So, let's say you hit "Z" after 3 operations, you would assume "N" is 3. but, it may be true that "Z" is also hit on operations 10, 20, and 30 (and maybe even more than that). So, it becomes hard to know which number for "N" you are dealing with. I know these examples seem trivial as well, but when you start dealing with large numbers, it gets very complex and difficult to solve. Here's an article I wrote that goes into more detail: devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
Also, on the RSA thing, it's true that factoring large numbers is the foundation for the security of RSA. The reason most people like ECC is that you don't have to have as large a key size to achieve the same level of security. Here's a video I did on RSA that goes into a little more detail on how it works: ua-cam.com/video/rVQpK6NcYIE/v-deo.html
Hope all this helps...thanks!
F5 DevCentral Thanks in advance for your answer. I just have 1 more question according to your reply, doesn't it mean the smaller the "max" value, the more time Z "cycle", hence the harder to break the encryption?
great question! on one hand, it makes sense that the more times "Z" can cycle through, the harder it would be to find "n", but it turns out that the more space you have to work with (the larger the max size), the harder it is to compute everything and so the harder it is to break the encryption. obviously, this is a very complex subject and it's hard to break it down into simple terms, but you are asking great questions! i guess the easiest way to put it is...the larger the "max" size (meaning, the larger the key size), the harder it is to break; therefore, the stronger the encryption. i hope this helps!
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: ua-cam.com/video/U7E_L4wCPTc/v-deo.html