Video - Bitcoin 101 - Elliptic Curve Cryptography - Part 4 - Generating the Public Key in Python
Welcome to part four in our series on Elliptic Curve Cryptography. In this episode we dive into the development of the public key. In just 44 lines of code, with no special functions or imports, we produce the elliptic curve public key for use in Bitcoin. Better still, we walk you through it line by line, constant by constant. Nothing makes the process clearer and easier to understand than seeing it in straight forward code. If you've been wondering about the secp256k1 (arguably the most important piece of code in Bitcoin), well then this is the video for you.
TRANSCRIPT
Hello, this is James D'Angelo. And welcome to the Bitcoin 101 blackboard series. Today we are diving into Part 4 of this five-part series on Bitcoins bedrock, the Elliptic Curve. And in particular we are diving into this specific curve y2=x3+ax+b where a=0 and b=7. That's the specific curve, the Secp 256 K1 that Bitcoin uses in a number of all coins use. And today's code, all we're going to be doing is doing one specific multiplication. We're going to be generating the public key from the private key given the design parameters which includes the generator point of this curve right here. And you'll notice in our code which is only around 40 lines, there is no SHA256 and there is really nothing else so you won't see any imports. You won't see any special functions. The only thing that's really in there is this which is equivalent to mod. And if you aren't familiar with modular arithmetic you have to catch up on that to understand everything that's going on today.
But this is important stuff, okay. You don't need to understand it to use it any more than you need to understand the Bernoulli effect when you get up in an airplane or a transmission. If you're driving a car angular momentum which may or may not exist. When you're riding a bicycle but this is what protects your Bitcoins. Okay. So, when you go to sleep at night there is no SHA256 protecting. In fact, the thing that protects your Bitcoins and allows no one else to spend it is the elliptic curve. So, with all that said let's just dive into the code.
So here right at the top we're hit with the design parameters, really just constant set every specific elliptic curve must have and must make public. So, all of these constants that you see up here, this is the prime number, this is the N which is the number of points in the field. This is the A and the B which we already showed right here. So here is the A and here is the B that come out of this equation right here. And then this is our generator point and this is an ungodly big point, right, because here is the X coordinate of our point and here is the Y coordinate. And then because it's codes in Python you can just stuff them in there. So, I take the GX and stuff it there, the GY stuff is there and then I get my G point right here. So, these numbers right here are five of the six numbers that you need when you design a curve. And the one we're leaving out H which is the cofactor, right. H=1 and it's a multiplier so you don't really need it so we've left it out of our programming altogether. But you can verify these points right here just by going to the SEC which is the Standards for Efficient Cryptography, okay.
So, you can look at the link right here and you see they're recommended elliptic curve domain parameters which are the six points we're talking about already. And they have a number of curves that you can choose but the one that we're dealing with is about halfway down and here it is. It's the recommended parameters for the Secp 256K1. And here is your P, here is your A, here is your B, here's your G in a compressed form, right. And I want to show you how to do that later. And here is your N and here is the H which is the cofactor we leave out.
Now, you'll notice pretty quickly that they aren't all in the same format that we're using. Okay. So, B we just typed in seven because we left out all those leading zeros. A, we typed in a zero. Okay, G they're having the compressed form which takes this 02 at the beginning to let you know it's compressed form but the point itself is actually the numbers that follow it. Here is G4 telling you it's an uncompressed form but it's all one hex and we can verify that these numbers are the same pretty quickly just by copying, opening up our little console here and typing in that number. Okay, and seeing what Python says. Well, it gives you that number now in the base 10 and if we want it in hex we just paste that same thing inside of hex and indeed we end up with the same number that the SEC recommends. Of course, it has the little Python L there to let you know that it's long.
The same is true of these G coordinates. Okay. So, we can just stuff that into a little hex wrapper here and let it go and we get the 79BE6 blah, blah, blah, blah which is exactly the same as you see right here. Okay. And the compressed form is actually just leaving out the Y coordinate because you're dealing with point on a curve and if you have the X point you have the Y point, it's actually you have two possible Y points but they're just the negative of each other. So, if you added them up they'd be zero but what they're basically saying is that if you know X on any point of a curve you'll know the absolute value of Y. So, you really basically know Y. Okay.
And then here is N which we actually keep in the exact same format so you see it right here. Okay. So, these are constants up to here. Of course, this is not a constant. This is your individual private key, the one that you want to keep secret so if you want to try this out and play with it you can substitute in different private keys. Okay. So now, before we get too deep into the other lines of the code which isn't even that many, okay. So, we've got another 25 lines of real active code and then we're just kind of printing out the results at the end. Okay. So, the total of this is 44 lines. Before we go any further, let's just run it. So here in subline text it just say, command B. Okay. So, let's move this up so I can see the results and then I basically get the results of these print statements right here. Okay.
So the private key which is the one that we had at the very top right here is just typed out into a decimal form. So, Python the default value is base 10. So, the private key is this number right here. And then the results your uncompressed public key which is just the result of this simple singular multiplication. Okay, your public key is just your private key times the generator point. Okay, very important, understand that we're just doing one multiplication to generate a public key. Okay, and remember our generator point is right here and then a private key is right here. So, we're just multiplying these two together and we get this point right here your uncompressed public key and here is the X coordinate and here is the Y coordinate of our public key. And that makes sense because our private key though it's a big long number is just one big integer. So, we're just multiplying a point times an integer and the result is a point. And then the compressed version as we already mentioned is taking the X coordinate turning it into hex format which is right here and then slapping a 02 on the beginning just to let you know which format it is. Okay.
And just to verify that let's take this and hopefully remember it and we get the hex version right here. Right. And we can just run this whole code again to get our number again. So 791DC. Okay and here we go we've got 791DC. So, this is the public key, okay. And it's really important to remember here and we'll make a quick aside to know that your public key is not your public address. Okay. And you can go to the technical background of version one Bitcoin addresses here in the Bitcoin Wiki and you'll see all the steps of turning a private key into a public address which is this number down here, right. And that's the one we're more familiar with, with the one and it's sort of 31, 32 or 33 characters long. Okay. And what we're generating today is just the public key. Okay. And so it's just this first step on how to create a Bitcoin address. All the rest of this, it turns out is pretty easy, okay. You're taking a RIPEMD and a SHA256 to different hashing algorithms and then just hashing it and doing some checksums until you end up with the final result. And we're definitely going to do a video on all of that in the upcoming weeks. Okay.
So let's get back to our code. Now, we really have to take a look and see exactly what's happening. Okay. So, we've got a few functions going on here the mod inverse, ECadd, ECdouble and then finally sort of the main function which is ECmultiply. Okay. That's what we call when we want to actually print our public key. We say give me my public key. So, I want you to multiply just as we talked about before. The generator point times the private key. And inside of ECmultiply you see that we've got calls to ECdouble and ECadd and inside of both of those you have calls to mod inverse. Okay. And really all this is, is this is the invented mathematics that we talked about in part 3. Mod inverse is the invented elliptic curve math for division. Okay, so this is just division and elliptic curves. ECadd is addition in elliptic curves and ECdouble is sort of point doubling, right. These are invented so if you try and do regular math say you take the generator point multiply the X and Y by the private key you're not going to come up with the right thing. You have to be doing elliptic curve multiplication, elliptic curve addition and most importantly which is the mod inverse elliptic curve division.
And so this is the modular inverse also known as the Extended Euclidean Algorithm and this code right here is old code. This code is used by anyone doing these types of operations use so much in cryptography where they just love, love, love, big numbers and they love modular arithmetic. And without the modular inverse you cannot do almost all cryptography. And just for fun, we can go and see on the regular Wikipedia, there is a page on the Extended Euclidean Algorithm. Okay, and it's also known as modular inverse, mod inverse and it's used a lot in cryptography, right. But even on a regular Wiki you'll find that they're dumping and some pseudocode which is basically the code that we're using. And there's a number of videos online which walking through this old theorem and how to get the GCD modular inverse of a number, GCD meaning greatest common denominator.
So this code right here is pretty much taken straight out of Wikipedia or wherever else you see the modular inverse. The next step which we call is elliptic curve addition and we'll review that really quickly right here. So, here's our function ECadd in the software, right. And it's basically just running through these calculations right here. Here it sets up the lambda right. And you might be familiar with this. Okay. This is really just the slope. Okay, so you take the first point that you want to add and the second point that you want to add in this invented math and then you draw the straight line through them and where it intersects for the third time on the elliptic curve that is considered the inverse of the sum point. So, this is that invented math and this is defined as the sum. Again, they could have defined this as apples. They could have defined it as waka, waka. They happened to call it addition, which leads to a little bit of confusion for sure. Okay, because it's just not addition. And so, they generate the lambda, which we have in our code right here, okay. So here is Y of the second point because X is actually when you put a zero in there and here is Y at the first point and then you multiply a times the modular inverse. Okay, which is really divided by the X and the X mod it again by the prime number, the big prime number, the P curve, okay.
And then when you get the whole quantity, well, you go ahead and mod the whole thing again. Okay, lots of moding going on. And then once you have lambda right you basically follow the same things that we see here. You're going to square lambda, then you're going to subtract the two X coordinates and then you've got the Y coordinate that you want to get. So, you're going to take lambda, multiply it by the difference of the two X coordinates. And then you're going to subtract Y of P. Okay. And so this is the invented math and you'll see it all right here so here's the squaring of lambda, here is a subtraction of the two X coordinates. All moded with our big prime number, all right, doing clock math on the big prime number so you're actually just taking the remainder and then you generate Y right here and you're actually stuffing this X back into the Y right there. Okay.
And so that's EC addition and that is just invented addition so if it doesn't make a lot of sense to you well, that's because it was invented for elliptic curves. Okay. And the same is true with point doubling. We can change colors here use bitcoin orange. Okay. So, point doubling which is EC double in my program is actually taking just this one-point P and defining this idea of doubling. Okay, and that idea right, this invented doubling is just taking the limits. So, the tangent at the curve of this P and whatever point that intersects with is the inverse of your sum, right. So, the doubling of P, so this is two P by definition and the equations basically figure out the tangent having intersect with the curve right here is basic algebra stuff and it all breaks down to this. Where once again you determine the slope of the line, lambda and then you just do this math on it. Okay, and we have all that stuff done over here. Okay. So here is lambda with the 3X2+ACurve and remember a curve is actually zero. Okay. If we go all the way up here a curve A zero, B curve a seven, these are the coefficients of the specific curve Y2 = XQ+AX+B and so there's are A curve times the modular inverse because you can't do division with elliptic curves. You have to do multiplication with the modular inverse and this is times 2 A moded by the P curve and then the whole thing moded by the P curve and then you get your X and you get your Y, according to those very same formulas.
So now you have addition and doubling which we talked about in the previous video you can do the real stuff. You can do multiplication. And again, all we're going to be doing is multiplying the generator point times the private key. And so, all we do is put our original generator point here, original private key here and that gets stuffed here and here into the scalar hex is where your private key goes and then we do this dummy check, real important dummy check. If scalar hex is equal to zero, if your private key is zero or your private key is greater than N. And remember N is this crucial, crucial number and in this particular curves' case it's slightly less than P. It's very difficult to figure out the N but you need it for very good cryptography. The good news about it is once you've got it figured out, well it's very easy to check for. Okay. And the check is really just one calculation to see if the line that you generated by multiplying the generator point by this number goes straight up and down. And if it does then you know you've got what's known as the Infinity Point in elliptic curves in that your N is a good N. And it's very important to realize that these curves are so simple that always talk about the NSA and back doors inside of this particular elliptic curve. There is just no room for it, there's no fact. Okay, random number generators are kind of shady and weird and they're very complex. You could see that being an issue there so you have to be careful of your random number generator.
But inside the Secp 256K1 with your curve of zero and seven it just seems impossible to put a backdoor into this thing. Okay, so let's go back down to where we're doing our one idiot check, to make sure that our private key is not bigger than N. N tells you how many private keys you can have in Bitcoin. You can go from one all the way up to here and they're all valid private keys. But even a number two greater than that starts to wreck the math, okay, and they're not valid private keys. So, you want to make sure that your private key is always less than this. If you're rolling dice the odds of you actually rolling a number greater than N is next to nothing so I won't worry about too much. Okay, so we're done with our idiot check.
And now we start doing the math. And this particular multiplication math right here is all about efficiency. Elliptic curves to speed up the multiplication you actually do this thing called Double and Add which is just the same thing as standard modern protocols do to speed up multiplications in current computers which is known as Square and Multiply. And this is just a more efficient way to do multiplication on a computer than just adding the numbers until you've got the multiplication especially for large numbers, the savings is immense. If you're using square, multiply and regular computing or if you're using double and add on elliptic curves. Okay, because as we know we could do our multiplication by just doing a lot of addition, but by adding in point doubling things really speed up and it's really fortunate that this invented math, right, holds the same properties. So, the addition, the multiplication, the division, all work out, right, so if you multiply something and then divide it, it always comes out to be the correct number. So that is the beauty of elliptic curves, right. It's got the cyclical group which limits the number of numbers which is beautiful. Then you do the mod math on it which limits the numbers again. So you're actually doing a lot of remainders and circling around which is really great for trapdoor functions and all the math works out so it's really great.
Okay, so this particular scheme that's being done here which is double and add relies on turning the number, your private key into its binary form and then using the ones and zeros to trigger how many times you're going to do doubling and how many times you're going to do adding to get your final output. So, what we're doing is we're stuffing in a loop right here which is the length of your private key. Okay. And remember, it's 256 bits so when we turned our key into a binary format it's 256 characters long. So, if we did that right now binary version of this big hex number we get 256 zeros and ones and this triggers the double and add that's going on right here. Every time you go through the loop you'll notice you do a doubling. But if the character you run into is a one, okay, then you also add. Okay. So, in this system you actually skip your first character and do all the rest. The first time around you would just do a doubling of the point and that point is the generator point. So, this Q right here is just our generator point which get stuffed N.
So, the first thing we're going to do is we're going to double the generator point by this function right here and then we're going to loop around again. And the next thing we do is a one. Well, a one we do a doubling and we also do an adding. So, Q gets incremented both by the doubling and Q gets incremented by the adding. And remember when we're done with this loop that's 256 times we return our private key. And each time you do this loop, right, you're doing basically modular math, you're throwing away information, you're keeping remainders, you're winding around this clock, you're doing tons and tons of math. And just to get a picture of that I actually have these prints in here. So every time that we double, I print out the X coordinate of the intermediate point and every time we add I printout the X coordinate of the intermediate add.
So when I run this we haven't seen what takes place up here but this is all the doubles and adds. These are all the intermediate steps, right, of this process that takes place just to generate one public key. And so, we've got 256 doubles and then we have about half as many adds. These are all the intermediate steps. This is how much mass going on. This is why your Bitcoins are protected. Okay. So, there is the 256. And if I run it my computer does it pretty fast, right. So, it does the whole thing, that fast. And I think somewhere oh, yeah finished in 0.7 seconds. Okay, and it's much faster if you're not doing prints or anything like that. So, a good processor can make a lot of public keys really quickly. Okay.
So after we do that whole process, right, so the last thing we do is we do a doubling of the previous point and the doubling of this last intermediate X coordinate and Y coordinate which we aren't even showing leads to your uncompressed public key. Okay, and we can check this, right. We can take our private key and stuff it in a bit address. It doesn't take our decimal version of it but we can go grab our hex version of it and copy it right here and then we can go to bitaddress.org and to the wallet details tab right here and we stuff in our hex version of our private key. Remember, hex is the raw format. It's the one where you can mess up the most so you don't want to use a lot of hex. Okay, we say view details and boom, we get our standard very famous Bitcoin address but the thing we generated today is the public key and there is the compressed public key and we can go and see if that's our compressed public key. And indeed, it is. Okay, and it's right there and we can do the opposite, right. We can go generate a brand-new address right here, we can copy the compressed private key go to wallet details, stuff that here, say view details and grab the raw hex version of the private key right here and paste that into our code and we can run our code with a new private key. And we get a public key of A64224 and we can go and see if that's right. Okay.
And there it is A64224 and know this if you're playing around with this, you'll have to be very careful of the formatting when using this code because we didn't want to put in any extra lines to decode different forms of public and private keys. This is the most stripped down elliptic curve key generation that we could come up with. Okay. So, we wanted to be super clear and super basic. So, you just get standard hex private keys that you're allowed to put in. Of course, you could put it in the decimal version or the binary version but nothing compressed or strange. But there it is our working public key generation. Remember the software is for educational purposes only. We didn't do any real bug testing on it but it's really great for understanding this very, very important step of Bitcoin. This first step how to create a Bitcoin address. In fact, it might be the most important step. This novelty, being able to create this sort of digital signatures, public keys as we've spoken about already is integral to all forms of modern cryptography and it's completely integral to Bitcoin. Okay. So, I hope that helps. I hope now you're starting to get comfortable with elliptic curves, public keys and how the inner guts of Bitcoin works. Please remember to comment, like, subscribe, do whatever it is you do and we'll check at the next video.