Bitcoin Cryptography: Elliptic Curves over Finite Fields Explained

[00:00:00]hello and welcome to bitcoin explained well I break down some of the more technical aspects of Bitcoin in a simple way in this video I'll be teaching you about elliptic curves over finite fields and it's actually the third video in a five-part series on the cryptography behind Bitcoin elliptic curves over finite Fields combine finite fields and elliptic curves over real numbers which we learned about in the first two videos of this series and it's really what's at the heart of the mathematics behind and elliptic curve cryptography the cryptography that Bitcoin uses once you understand what I cover in this video you understand all of the mathematics that's required to understand bitcoin's curve how you do transaction signing and verification on the Bitcoin blockchain and a lot of other cool stuff now with all that said let's talk about elliptic curves over finite fields in this video I'll once again be sharing my screen and showing you a Jupiter notebook the Jupiter notebook once again allows me to visualize what I'm talking about a lot because elliptic curves over finite Fields just like elliptic curves over real numbers in my opinion are best understood visually and intuitively rather than just looking at the abstract mathematics and some formulas this video will be split into four sections first I'll be visualizing elliptic curves over finite fields and showing you what they actually look like over a graph and why they look the way that they look then I will talk about Point addition over finite Fields remember Point addition is what we did for elliptic curves over real numbers now we'll be doing it over finite fields and then we'll move on to point multiplication which builds upon the logic of Point addition similar to elliptic curves over real numbers as well and then lastly I'll be teaching you about one really important problem or property of elliptic curves over finite field which is called the elliptic curve discrete logarithm problem all right let's get started okay let's actually visualize an elliptic curve over a finite field for this example I've chosen the following elliptic curve y^2 is equal to X Cub + 8 over the finite field of order 127 27 is a prime number and when we actually compute all of the points that fall onto this elliptic curve over this finite field meaning we get all of the X and Y coordinates that satisfy this curve equation here and plot them on a scatter plot then what we get is the following now this looks completely different to the visualization of the elliptic curves over real numbers that we saw as you can see this is just a scatter plot meaning they're just some blue dots on this plot but there's no curve so how is this an elliptic curve we don't have the smooth graph anymore the continuous graph that we had for elliptic curves over real numbers that's the first thing to know let's look at this scatter plot a little bit and then I'll explain why it looks the way that it looks in a second now a few other things that you might notice are that both the X and the Y coordinates are zero or positive so there aren't any negative values and you might also notice that they are bound to be between zero and somewhere above 120 one other thing that you might notice when closely looking at this is that there seems to be some symmetry in this scatter plot and the symmetry appears to be somewhere around this axis here so there's some kind of imaginary axis right in the middle of this scatter plot about which there is some symmetry as you can see a lot of these points are basically just mirrored over this axis here now why is all of this the case why does this look the way that it looks why don't we have a smooth smooth continuous graph anymore or curve anymore why do we only have a few points in a scatter plot and that is the entire elliptic curve now the reason for that is that we're not dealing with real numbers and a coordinate system with real numbers here anymore we're dealing with finite field elements and as you remember from the video about finite Fields finite field elements are only allowed to be integer values and they only allow to be in the range from 0 to P minus one now in this case because the order of the finite field is 127 the x and y coordinate values are only allowed to be integer values and they're only allowed to be between 0 and 126 meaning that only certain points that have integer and like really clean integer coordinate values for X and Y coordinates and that fall within the range of allowed values will actually be valid points that satisfy the curve equation over finite field Elements which is why we don't get a curve anymore we don't get a continuous graph anymore but this is still the representation of an elliptic curve just over finite field elements remember we're doing abstract mathematics here so this is a little bit AB abstract but the cool thing is and I will show this later in the video that despite this looking nothing like the elliptic curve over real numbers all of the intuition and the logic behind the math of things like Point addition and point multiplication are actually exactly the same and they still work exactly the same which is kind of miraculous because it doesn't look anything like it but it still works we'll see how that works in a second now before I move on to talking about Point addition and point multiplication let's get a bit more of an understanding of how maybe even the same elliptic curve just over a finite field of a different order would look like and how the order of the finite field changes the points on the curve so I've done exactly that using some python code here um I'm always using the same elliptic curve so y^2 is = X Cub + 8 and I'm just choosing different orders of the finite field that they are over from 11 to 31 to 41 to 89 and visualizing all of the Scatter Plots or the resulting points that satisfy the elliptic curve over the finite field of that respective order for the order of 11 we get this scatter plot here you can see there's only a handful of points that actually satisfy the elliptic curve over this finite field for the finite field of order 31 we get this here there's a lot more points for 41 we get this here and then for 89 we get this scatter plot here now they all share the same properties meaning that they all have X and Y values that have to be from 0 to P minus one and they all have this symmetry as well now one thing that I haven't touched upon is why this symmetry is there this is similar to how we get the Symmetry for elliptic curves over real numbers it's just that the Symmetry there is at y equal to Z or around the xais because we've got the y s term on the left hand side of the elliptic curve equation meaning that there's usually always two y values for a certain x value because of this y s on the left hand side but because we're dealing with finite field elements here we can't have any negative values for the y-coordinate anymore so we can't actually have the Symmetry at the um xais or yal zero meaning that there's a positive and a negative value um of 4 y for each x value here it needs to be in the middle of the area of the curve which actually happens to be P / two so the order of the finite field divided by two and um yeah it it's basically just shifted to be above the x-axis and still happens in the middle of the curve so to say now before we actually talk about Point addition let's try to build a connection between these elliptic curves over finite field elements and elliptic curves over real numbers because there actually is a connection it's not completely straightforward but using a specific example I'll explain to you how you can actually map some of the points on an elliptic curve over real numbers to points on the same elliptic curve over fin and field elements to do this I've chosen the following example which is y^2 = X Cub + 8 same elliptic curve over the finite field of order 11 now we've already seen this scatter plot but just to show it once again we get all of these points that lie on the curve over this finite field here now one thing that we can actually see is that if we plot the same elliptic curve over real numbers instead of finite fi elements then the13 which clearly falls on the elliptic curve over this finite field and the point 24 which is also one of the point that lies on the curve are both also on the elliptic curve over real numbers now in this case here I'm showing the 13 but the point 24 as you can roughly see is also on this elliptic curve now in this this case this is the case because these are both points that have perfect integer coordinates for both X and Y and those integer coordinate values for X and Y are both below 11 which is the order of this finite field which this is over here meaning that if we do all of the computations uh modul 11 then both 1 3 and 2 4 modulo 11 just remain 13 and 24 so those points actually integer uh coordinate value solutions for both the elliptic curve over real numbers and for the finite field but there's another interesting point that we can look at which is the point 46312 which on the elliptic curve over real numbers as you can see falls on the curve here so it's 46 312 are the coordinates but now here's the interesting thing 46 and 312 modulo 11 are actually congruent to um to two and four meaning that when you basically take the the values of this X and Y uh of these X and Y coordinates of this point here and compute the modular 11 then they collapse down to 2 and four because those are the remainders after dividing the x and y coordinate by 11 meaning that for the elliptic curve over the finite field of 11 this point here with coordinates 46 and 312 is actually congruent to the point 24 which is also on the same curve so there's two different points that when we collapse the entire space of infinite points on the elliptic curve over real numbers into the finite number of points on the elliptic curve over finite Fields then we collapse multiple different points from the elliptic curve over real numbers onto one point for the elliptic curve over the finite field this point 24 here so this point here is sort of like how in finite fields we have add buckets or slices or elements um of the finite field that technically are congruent to many other values that fall outside of the range of allowed values for the finite field elements that just get collapsed into one of the buckets in the finite field by doing the modular operation same concept here this is how you can link elliptic curves over real numbers to elliptic curves over finite field elements now that we understand this link we can actually move on to point addition over a finite field before I show what point Edition over a finite field looks like let's quickly recap and look at what this look like for elliptic curves over real numbers so in this case if we wanted to add two points that lie on the curve and aren't the same point um then for A and B for example then what we did is we got this straight line that connects these two points and then found the third point on the curve that as long as these two points are not the inverses of each other and this straight line is perfectly vertical there will always be a third point we talked about this in the previous video video there's a mathematical proof for that as well but anyway so we find the third point where this straight line intersects again and then flip over the x-axis and remember the x-axis here is the axis of of symmetry and then where that point then ends up is basically the inverse of the third intersection and the result of a plus b is down here for elliptic curves over real numbers now for elliptic curves over finite Fields the logic is exactly the same it just looks slightly different so if we have this scatter plot in this case I'm using the same elliptic curve over finite field of order 19 and we want to add two points A and B then the logic for doing the point addition is once again find the straight line that goes through the two points that you want to add a and b and then find the third point where this straight line intersects the elliptic curve now in this case we are limited to the x and y space from 0 to 18 because we've got the order of 19 so pus one is the highest values to 18 but what happens here is that when we draw this straight line through A and B and it hits one of the one of the borders of the possible values which could be 0 or 18 on both the X and Y AIS then we just wrap around to the other side of the axis where it hit the limit and continue the straight line with exactly the same slope so you can see we get the straight line through a and b hit the limit here we wrap around to down here same slope straight line still haven't found another point we hit the limit up here go down here we just missed the point that's down here and then the straight line with the same slope now it hits the 18 on the x axis so it wraps around to the other side of the xaxis starting at zero still continues with the same slope hasn't hit a point yet wraps around at the Y AIS back down to Z same slope and then it finally connects to a third point on the elliptic curve this point C here and then once we find that point then all we need to do is we need to reflect over the axis of uh of the mirroring axis which remember for finite field elements isn't the x-axis anymore but it's the axis that's right in the middle of the finite field so here we have a finite field of order 19 so 19 / 2 is 9.5 so the axis of symmetry is somewhere around here and when we reflect this point over the axis of symmetry to get the other point on the inverse of this point the result of A and B is down here so the logic and the intuition behind doing the point addition for an elliptic curve over a finite field is exactly the same as it was for the elliptic curve over real numbers it's just a bit more abstract but it works exactly the same and the interesting thing is the mathematics to compute the slope of the straight line and all of that stuff still works exactly the same we're just doing modular arithmetic here but the logic is exactly the same and if you write a good python Library like I've done to do all this where all of the values that you use so even A and B and all of the coordinates for the elliptic curve points that you want to add are finite f field elements and you construct this class in a way in Python for example where it handles finite field math using modular arithmetic then this becomes really really easy to do and visualize so that's how Point addition works now let's talk about adding a point to itself so if we take the point here Point p with coordinates 11 and 16 and we want to add the point to itself before we talk about that let let's quickly recap how that looked over real numbers again I'm going to have to scroll down a little bit adding a point to itself so again over real numbers the way that this worked was that instead of um connecting two different points we thought about this similar to bringing two points infinitesimally close to each other um until they become the same point and then we just need to find the tangent line to the curve at that point that we want to add to itself and then find the point where that tangent line which is a straight line and which we've proven needs to intersect the elliptic curve again um we find the point where that straight line the tangent line intersects again and then mirror over the x-axis or the axis of reflection or Mir mirroring which in this case is the x-axis for real numbers and for finite fields that will be P / 2 right in the middle of the scatter plot and then we get a added to itself to be down here now for elliptic curves of finite Fields once again logic is exactly the same the intuition is exactly the same this is the beautiful thing about abstract mathematics if you construct the field and the field elements or to all follow the properties that we talked about infinite fields and elliptic curves then all of the math will still work exactly the same just a bit more abstractly to visualize so here we've got the point p with coordinates 11 and 16 now to add this point to itself we just need to find the straight line as tangent to this point now visualizing this is a bit difficult because we don't have a smooth plot here so there's not really a tangent line that we can draw but the math like I said earlier is exactly the same so we just compute the slope of the tangent line the way that you compute the slope of any tangent line to a curve and then once again we take this straight line until it intersects or hits another point that falls on this elliptic curve and then reflect over the reflection axis so for this point P that just means we take the straight line up here until it hits 18 wrap around it just passes through these two points hits the limiting again wraps around and then finally it intersects another point on the curve and then we just reflect over this reflection axis which would be here at this point and then get the result of adding this point P to itself down here beautiful this all works exactly the same as we learned previously now that we've seen how um how you can add a point to itself let's talk about Point multiplication finite Fields we're finally ready to talk about Point multiplication of a finite Fields before I show you how this works over finite Fields let's quickly recap Once Again how we did this for altic Curves over real numbers now we didn't necessarily visualize this too much we just walked through how you can do efficient um addition or repeated additions which is what point multiplication in the end just is um the one thing that we did do is we visualized taking the same um point a added to itself to get 2 a down here added to itself another time to get 3A down here to visualize that point multiplication is just repeated Point addition or adding a point to itself a given number of times now for elliptic curves over finite Fields this works exactly the same way now if we use the same point that we used to add to itself above with the coordinates 11 and 16 and we point multiply that point to itself a given number of times and visualize how often we point multiplied it we get the following scatter plot now here it's important to remember that one is equal to just the point itself two is equal to the point added to itself once which gets us down here and three is equal to the point added to itself twice so 3 p is p added to itself twice so that might be a bit confusing but that's just how this works so what we then get if we point multiply this point a given number of times are all of these points down here now what you can see is that the highest number or the highest point multiple next to any of the points here is 13 but if you remember what the elliptic curve over this finite field looked like like up here it seems like there's a few points that were in the on the elliptic curve over the finite field that we don't have in this plot here and why do we stop at 13 what happens if we want to go past 13 so if we go past the value 13 then what happens is we wrap around and start again at the same point that we started with you can see there's a number 15 here now the reason for that is that for an elliptic curve over a finite field every point on the curve has its own order in a way now the order is defined as the the integer value that you need to point multiply this point by to get the point at Infinity this sounds a bit complicated but I'll explain this so for this starting point here you can see the one next to it as well when we point multiply it 13 times we get this Point down here but then as soon as we add it to itself one more time so Point multiply it to itself 14 times we actually get to the point at Infinity which we also call the point that is nowhere which we can't visualize in this curve here because it's the point that's nowhere and then as soon as we add it to itself once more so if we add the original point to the point at Infinity the point that is nowhere we start again at the same starting point and then if we add it to itself another time we get to the same point as two if we add it to itself another Point another time we get to 17 which is also three so once again there there seems to be some cyclical pattern in this which we are used to from finite fields and there's also I guess a little bit of congruency of these points as we showed earlier how you can map different points over elliptic curves over real number to the same point on an elliptic curve over finite fields now if we choose another point from the same elliptic curve let's choose the point 2 and 15 which you can see on this curve here is on the curve then what happens is you get the starting point here 215 and then when you add it to itself once you get this point here when you add it to itself another time you get this point down here and when you add it to itself you get this point another time you get this point here then here then here then you get the point at infinity and then you wrap around another time um to the starting point up here but that's really interesting because now depending on which point from the original elliptic curve we chose if we point multiply it with increasing integers we can only generate a subgroup of all of the points that we had on the entire elliptic curve over the finite field that we started with and why does this happen so the reason that this happens is that like I said each point on the elliptic curve of a finite field has its own order and that order can be different to the order of all of the points that fall on the elliptic curve over the finite field so the original curve that we had here let's look at that um has a certain order which isn't actually 19 that's that's the order of the finite field that's different the order of the group of points that fall on this elliptic curve is how many points we actually have on this elliptic curve which is 27 in this case so we can have 27 different points so 26 different points plus the point at Infinity um for the entire group of points that satisfy the curve equation but then if we choose some of the points that fall on this curve and point multiply them we're not able to generate all of the other points that fall in the elliptic curve but only a subgroup of them and that subgroup or how many other points we're able to generate on that same elliptic curve using Point multiplication of the starting point is the order of that point but if that order isn't Prime then what happens is when we point multiply this starting point by increasing number of integers until we get the point at Infinity we reduce the possible size of the group of elements that we can reach by using that starting point and point multiplying it a lot in this case not as much as in this case down here now why is this important in elliptic curve cryptography we need something that's called a generator point a generator point is a point from the elliptic curve over the finite field which can either generate all other points on the elliptic curve over the finite field or almost all other points on the curve which is only the case if the generator point or the point that we start with has an order that is the same or very close to the order that the entire group of points on the elliptic curve has and that order has to be prime as you remember from the video on finite Fields if we do multiplication of every element in the finite field and the finite doesn't have a prime order then we collapse the size of the finite field if we do the multiplication by one of the divisors of the order of the finite field so we need a prime order and we need it to be ideally very large and very close to the order of the entire group of points on the elliptic curve over the finite field now let's actually have a look at an example of that so in this case I've chosen the elliptic curve y^2 = X Cub + 28x + 1 over the finite field of order 29 when we plot all of the points that satisfy the elliptic curve equation over this finite field we get this scatter plot here now let's just pick any of the points let's say five and 18 and use that as a starting point to then do the point multiplication if we do that we've got the starting point here um and then we add it to itself on to get the point over here then we added to S another Point time to get the point over here and then you can step through that but what you will see and I'm trying to find the number right now here the highest multiple that you will see in here is 36 this means that because the original group also has 36 points plus the point in Infinity this starting point here with coordinate 518 is actually able to generate every other point that falls on this elliptic curve over this finite field through Point multiplication using increasing integers and then if we choose another Point let's say 12 and 21 the same thing works again so using this point as a starting point here we can add that point to itself once to get the point down here then we get to up here and then um yeah we move on until we get the number 36 which in this case is down here meaning that both of these points are really good generator points because they both have the same order as the full group of all of the points that fall on this curve and then if we if we want to add it to itself more than 37 times what happens is we wrap around to the same Point again so one becomes equivalent or congruent to the 38 on the Curve um now why does this matter why is it important that we have a good generator point now one of the key reasons for this is that we want to be able to do Point multiplication using increasing numbers uh or increasing values of integers using a generator point so in Bitcoin we have a generator point I'll talk about all this in the next video but this is a little preview in Bitcoin we have a generator point which is a point on an curve over a finite field we just have an elliptic curve over a finite field with an order that is really really large astronomically big and then that generator point is the same for everyone and then we generate a private key which is just a really large integer essentially you'll learn more about this in the next video and then point multiply the generator point with that really large integer and the point where we end up with that becomes our public key but now what's important is that for the security of Bitcoin and for the security of the private public key cryptography there needs to be a guaranteed one: one mapping from the generator point to the number that you use to multiply to the public key and the reason why we want to have this onetoone mapping is so that there are no private keys that when multiplied with a generator point lead to the same public keys but that's only possible if we have a really large finite field because as soon as we get a small one there's not enough space in this elliptic curve or there's not enough points on this elliptic curve but also we want to restrict the value of the private key to be smaller than the order of the generator Point um because then if we have that we never have this wrapping around so we never have this congruency of one point to another point of or one multiple of the point to another multiple of a point because remember here in this case these multiples 1 and 38 would be the private key um that we use and we don't want the same private or different private keys to lead to the same point which is actually what the public key is so in Bitcoin as long as we have something like this here with a really good generator Point that's able to generate a lot of the points or all of the points that fall on the elliptic curve through Point multiplication using different integer values and as as long as the finite field is really large then this is really secure another reason why we want to have something like this is that point multiplication on elliptic curves over finite Fields actually distributes points uniformly over the elliptic curve this means that this appears pretty much random meaning that if you only know the starting point so this point one here and somebody else gives you just the coordinates of this point down here which is the point of Point multiplying the starting point 22 times but they don't tell you the 22 then there's no way to back solve for this number 22 here because this isn't easily predictable this is basically what's considered a one-way function and there's no way of reversing Point multiplication on an elliptic curve over finite Fields because it's so secure and uniformly distributed meaning that if somebody wanted to find out how many times this point was multiplied to get from the starting point to the point down here the only way to do it would be to brute force it which would be to Loop over every possible integer value that could be used for the point multiplication until you get the point down here and then you can say ah it had to be 22 which in Bitcoin would be a private key so somebody could back s for your private key but because we're using uh lipic curves over finite fields that are so large it's computationally completely infeasible to go through every possible integer value and actually break the private public key cryptography we'll talk a lot about this in the next video but this is a bit of a heads up as to why this is so important so what I just explained here is actually What's called the elliptic curve discreete logarithm problem so I've basically already described it but let's look at it formally and then I'll go back to talking about what this really means what the elliptic curve discreete logarithm problem States is that given a point P so a starting point and a multiple of it Q where the multiple is just K multipli or P multiplied K by K or added to itself Kus 1 * where K is a secret integer the challenge is to find K so basically finding 22 by only having the starting point P here and the resulting Point Q here despite knowing both p and Q Computing K is computationally infeasible for a large K and this is what makes elliptic curve cryptography so secure so what I just explained before is exactly what makes this so secure there is no mathematic iCal way to solve for 22 given the starting point and the ending point you have to do it using brute force and if you start having elliptic curves over finite Fields with orders of magnitudes that aren't even in the billions or trillions like we're talking way way larger orders of magnitudes as you'll find out in the next video then this becomes completely impossible and you're probably more likely to win the lottery 10 times in a row than to solve for private key successfully now to finish up the video I want to talk about one other thing that's quite interesting and important which is why do we actually do elliptic curves over finite Fields why don't we just use elliptic curves over real numbers the ones that we learned about in the previous video there's basically five really important reasons for that the first one is that um over real numbers operations like Point addition and multiplication can lead to points with coordinates that require infinite Precision to represent them accurately this complicates the computation but can also complicate the storage of the values but also can lead to different results on different machines and using different programming languages for example whereas if you only use integer values and modular arithmetic which is what we do with finite field elements then everything is just integer values and it becomes really discrete and predictable and also repeatable this is similar to the efficiency of the computation so efficiency goes up a lot when you do finite field mathematics because you use modular arithmetic for operations like addition multiplication and division um which can be computed a lot faster this way in terms of security the good thing about having elliptic curves over finite Fields is that for a finite field the the size of the field so the number of the elements in the field field directly influences the security of the cryptography that you use meaning that a larger size of the field means that you have to Brute Force more possible integer values in order to backs solve for something like the the private key or the point multiple that was used to get from a starting point to an end point and then once again if you use a really large finite field size then this becomes really really secure and basically Unbreakable um the uniform distribution as we talked about the finite field structure ensures that points generated by Point multiplication are uniformly distributed across the curve which contributes to the security because um it's it's super random and there's no predictability in it then the deterministic operations um using finite Fields makes all the operations on tic curves completely deterministic and repeatable which is super super crucial for the cryptographic protocols that we use in Bitcoin and other cryptography applications because you want to be able to always get to the same public key if you point multiply the generator Point by a certain private key but you also want to be able to um really verify the signature of a transaction using a public key and always everybody across the network should always get to the same result and this is guaranteed if you use modular arithmetic and finan field elements now just to make a point about the discrete and predictable here in Python for example if we were to use real numbers and not uh restrict ourselves to finite field elements or integer values then if we did something like take the number eight and compute the square root of that we would get this floating point value down here which would technically require infinite Precision to store but python doesn't do that so what then happens when we we Square this square root again is we don't actually get back the number eight but we get 8.00 and so on two meaning that this isn't actually eight and this result could be different for different computers using different levels of precision different um computer programs so python versus C++ or something like that um and that's why we don't use any real numbers for the cryptography in between coin because it can just lead to these complications and doing everything using integer values or finite field elements and modular arithmetic is way more discrete predictable and secure and that's why we do that okay you've now understood everything that there is to know about elliptic curves over finite fields and we can finally talk about the actual curve that Bitcoin uses I'll see you in the next video