#Bitcoin #Elliptic #Curve #Cryptography #Part #Generating #Public #Key #Python
Hello, this is James DAngelo and welcome to the Bitcoin 101 blackboard series. Today, we are diving into part 4 of this 5-part series on Bitcoin’s Bedrock – The Elliptic Curve. In particular, we are diving into this specific curve y2=x3+ax+b where a=0 and b=7.
That is the specific curve the secp256K1 that Bitcoin uses and a number of alt coins use. And today’s code, all we are going to be doing, is doing one specific multiplication. We are 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. You will notice in our code, which is only around 40 lines, there is no SHA256 and there is really nothing else. So you will not see any imports; you will not see any special functions.
The only thing that is really in there is this which is equivalent to mod. If you are not familiar with modular arithmetic, you have to catch up on that to understand everything that is going on today. But, this is important stuff.
You do not need to understand it to use it anymore than you need to understand the Bernoulli Effect when you get up in an airplane, or a transmission if you are driving a car, or angular momentum which may or may not exist when you are riding a bicycle.
But, this is what protects your Bitcoins. When you go to sleep at night, there is no SHA256 protecting. In fact, the thing that protects your Bitcoins allows no one else to spend is the Elliptic Curve. So, with all that said, let us just dive into the code.
Here, right at the top, we are hit with the design parameters. Really just constants that every specific Elliptic Curve must have and must make public. 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 un-godly big point, right?
Because here is the X coordinate of our point and here is the Y coordinate. Then, because this code is in Python, you can just stuff them in there. So, I take the Gx and stuff it there; the Gy and stuff it there. And then I get my GPoint right here.
So, these numbers right here are five of the six numbers that you need when you design a curve. The one we are leaving out H which is the co-factor, right, H is equal to 1 and it is a multiplier so you do not really need it.
So, we have left it out of our programming all together. 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 up the link right here, and you will
See there Recommended Elliptic Curve Domain Parameters which are the six points we are talking about already. And, they have a number of curves that you can choose but the one that we are dealing is about half way down and here it is.
It is the Recommended Parameters for the secp256k1 and here is your P; here is your a; here is your b; here is your G in a compressed form, right and we will show you how to do that
Later; and here is your n; and here is the h which is the co-factor we leave out. Now, you will notice pretty quickly that they are not all in the same format that we are using.
So, b we just typed in 7 because we left out all those leading 0╒s; a, we typed in a zero. Okay, G, they have in compressed form which takes the 02 at the beginning to let you know
It is a compressed form but the point itself is actually at the numbers that follows it. Here is 04 telling you it is an uncompressed form but it╒s also in Hex. 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 and seeing what Python says. 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
Because it has the little Python L there to let you know that it is long. The same is true of these G coordinates, okay. So, we can just stuff that into our 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. The compressed form is actually just leaving out the Y coordinate because you are dealing with point on a curve. If you have the X point you have the Y point.
It is actually you have two possible Y points but there are just negative of each other so if you added them up they would be zero. But what they are basically saying is that if you know X on any point of the curve, you will know the absolute value of Y.
So, you really basically know Y. Then here is ╥n╙ which we actually keep in the exact same format so you see it here. These are all 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 one and play with it, you can substitute in different private keys. Now, before we get too deep into the other lines of the code which is not even that many,
Okay, so we got another 25 lines of real active code and then we are just kind of printing out the results at the end. The total of this is 44 lines. Before we go any further, let us just run it.
So here in Sublime Text, I just hit ╘command-B.╒ Let us move this up so I can see the results and then I basically get the results of these print statements right here. The private key which is the one that we had at the very top right here is just typed out
Into decimal form. Python, the default value is base 10. The private key is this number right here. And then the result, your uncompressed public key which is just the result of this simple singular multiplication. Your public key is just your private key times the generator point.
Very important to understand that we are just doing one multiplication ro generate a public key. Remember, our generator point is right here and then our public key is right here. So, we are just multiplying these two together and we get this point right here — your uncompressed public key.
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 is a big long number, is just one big integer. So we are 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.
Just to verify that, let us take this and hopefully remember it and we get the Hex version right here. And we can just run this whole code again to get our number again — 791dc. Here we go; we have got 791dc. So, this is the public key.
It is really important to remember, I will make a quick insight, to know that your public key is not your public address. You can go to the Technical background of version 1 Bitcoin addresses here on the Bitcoin
Wiki, and you will see all the steps of turning a private key into a public address which is this number down here, right, and that is the one we are more familiar with the 1 and a sort of 31, 32, or 33 characters long.
What we are generating today is just the public key. It is just this first step on how to create a Bitcoin address. All the rest of ths, it turns out as pretty easy. Okay, you are taking RIPEMD and SHA256, two different hashing algorithms and then just
Hashing it and doing some checksums until you end up with the final result. We are definitely going to do a video on all of that in the upcoming weeks. Let us get back to our code. Now, we really have to talk a look and see exactly what is happening.
So, we have got a few functions going on here; the modinverse, ECadd, ECdouble and then finally sort of the main function which is EccMultiply. That is what we call when we want to actually print our public. He would 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. Inside of Eccmultiply you see that we have calls to ECdouble and ECadd. Inside to both of those, you have caused the modinverse.
Really, all this is, is this is the invented mathematics that we talked about in Part 3. Modinverse is the invented elliptic curve math for division. This is just division in elliptic curves. ECadd is addition in elliptic curves and ECdouble is sort of point doubling. These are invented.
So if you try and do regular math say you take the generator point and multiply the X and Y by the private key, you are 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 this modinverse elliptic curve division. 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 using these types of operations you so much in cryptography
Where they just love, love, love big numbers and they love modular arithmetic. 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
And it is also known as modular inverse, modinverse and it is used a lot in cryptography. But even on regular Wiki, you will find that they are dumping in some pseudocode which is basically the code that we are using.
There are number of videos online which walk you through this old theorem and how they get the GCD modular inverse of a number. GCD meaning greatest common denominator. 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 will review that really quickly right here. So here is our function ECadd in the software, right? And it is basically just running through these calculations right here. Here, it sets up the lambda and you might be familiar with this.
This is really just the slope so you take the first point that you want to add and the second point that you want in this invented math and then you draw the straight line theorem and where it intersects for the third time on the Elliptic Curve that is considered the
Inverse of the sum point. This is that invented math and this is defined as the sum. Again, they could have defined these as ╥apples,╙ they could have defined it as ╥wacka wacka,╙ they happened to call it ╥addition╙ which leads to a little bit of confusion, for sure, because it is just not addition.
And, so, they generate the lambda which we have in our code right here. Here is Y of the second point because X is actually when you put a zero in there and here is Y of the point and then you multiply it times the modular inverse which is really
Dividing by the X and X modded again by the big prime number — the Pcurve. Then, when you get that whole quantity well you go ahead and mod the whole thing again. Okay, lots of modding going on. Then, once you have lambda, you basically follow the same things that we see here.
You are going to square lambda, then you are going to subtract the two X coordinates. Then, you have got the Y coordinate that you want to get so you are going to take lambda and multiply it by the difference of the two X coordinates.
And then, you are going to subtract Y of P. And, so this is the invented math and you will see it all right here. So, here is the squaring of lambda; here is the subtraction of the two X coordinates,
All modded with our big prime number doing clock math on the big prime number. You are actually just taking the remainder. Then, you generate Y right here and you are actually stuffing this X back in to the Y right there. That is EC addition and that is just invented addition.
If it does not make a lot of sense to you, well that is because it was invented for Elliptic Curves. Okay, and the same is true with point doubling. We can change colours here. Use Bitcoin orange. Point doubling which is ECdouble in my program is actually taking just this one point P and
Defining this idea of doubling. That idea, this invented doubling, is just taking the limits of the tangent at the curve of this P and whatever point that intersects with is the inverse of your sum. So, the doubling of P, so this is 2P by definition, and the equation is 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 and we have all that stuff done over here.
Here is lambda with the three X square plus Acurve and remember Acurve is actually zero if we go all the way up here Acurve is zero, Bcurve is 7. These are the co-efficients of the specific curve y2 = x3+ax+b and so there is our Acurve
Times the modular inverse because you cannot do division with Elliptic Curves. You have to do multiplication of the modular inverse and this is times 2a moded by the Pcurve and then the whole moded by the Pcurve and then you get your X and you get your Y according to those very same formula.
Now, that you have addition and doubling which we talked about in the previous video. You can do the real stuff. You can do multiplication. Again, all we are going to be doing is multiplying the generator point times the private key.
So, all we do is put our original generator point here, original private key here and that gets stuffed here and here into the ScalarHex is where your private key goes and then we do this dummy check, real important dummy check if ScalarHex is equals zero — if your
Private key is zero or your private key is greater than N. Remember, N is this crucial, crucial number and in this particular curve’s case it is slightly less than P. It is very difficult to figure out the N but you need it for very good cryptography.
The good news about it is once you have got it figured out it is very easy to check for and the check is really just one calculation to see if the line that is generated by multiplying the generator point by this number goes straight up and down.
If it does, then you know you have got what is known as the infinity point in Elliptic Curves and that your N is a good N. It is very important to realize that these curves are so simple. All this talk about the NSA and backdoor is inside of this particular Elliptic Curve.
There is just no room for it. There is no fat. Random number generators are kind of shady and weird and they are very complex. You could see that being an issue there so you have to be careful of your random number generator.
But inside the secp256k1 with your curve of zero and seven, it is just seems impossible to put a backdoor into this thing. Okay, so let╒s go back down to where we are 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 1, all the way up to here, and they are all valid private keys.
But even a number 2 greater than that starts to wreck the math, okay and they are not valid private keys. So, you want to make sure that your private key is always less than this. If you are rolling dice, the odds of you actually rolling a number greater than N is next to
Nothing so I would not worry about it too much. Okay, so we are done with our idiot check and now we start doing the math and this particular multiplication math right here is all about efficiency. In Elliptic Curve, 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.╙ This is just a more efficient way to do multiplication on a computer than just adding the numbers until you got the multiplication especially for large numbers.
The savings is immense. If you are using square and multiply in regular computing or if you are using double and add on Elliptic Curves because as we know we could do our multiplication by just doing a lot of addition.
But by adding and point doubling, things really speed up and it is really fortunate that this invented math holds the same properties. So the addition, the multiplication, the division all work out. 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. It has got this 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 are actually doing a lot of remainders and circling around which is really great
For trap door functions. And all the math works out, so its really great. This particular scheme that has been done here which is double and add relies on turning the number, your private key, into its binary form and then using the 1╒s and 0╒s to
Trigger how many times you are going to do doubling and how many times you are going to do adding to get your final output. So, what we are doing is we are stuffing in a loop right here which is the length of your private key.
Remember, it is 256 bits and so when we turned our key into a binary format, it is 256 characters long. So, if we did that right now, binary version of this big Hex number, we get 256 0’s and 1’s. This triggers the double and add that is going on right here.
Every time you go through the loop you will notice you do a doubling but if the character you run into is a 1, then you also add. In this system, you actually skip your first character and do all the rest.
The first time around you were just doing doubling of the point and that point is the generator point. This Q right here is just our generator point which gets stuffed in. The first thing we are going to do is we are going to double the generator point by this
Function right here and then we are going to loop around again. The next thing we do is a 1. Well, 1 we do a doubling and we also do an adding. So, Q gets incremented by the adding.
Remember, when we are done with this loop that is 256 times we return our private key. Each time you do this loop, you are doing basically modular math. You are throwing away information. You are keeping remainders. You are winding around this clock.
You are 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 everytime we add, I print out the X coordinate of the intermediate add.
When we run this, we have not seen what takes place up here. But these are all the doubles and adds. These are all the intermediate steps of this process that takes place just to generate one public key. We have got 256 doubles and then we have about half as many adds.
These are the intermediate steps. This is how much math is going on. This is why your Bitcoins are protected. There is the 256 and if I run it, my computer does it pretty fast. It does the whole thing that fast — finished in 0.7 seconds.
It is much faster if you are 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, the last thing we do is we do a doubling of
The previous point and the doubling of this intermediate X coordinate and Y coordinate which we are not even showing leads to your uncompressed public key. We could check this. We can take our private key and stuff it into gitaddress.org.
It does not 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, into the Wallet Details tab right here and we stuff in our Hex version of our private key. Remember, Hex is the rawest format.
It is the one where you can mess up the most so you do not want to use a lot of Hex. Okay, and 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 is our compressed public key and indeed it is; it is right there. We can do the opposite. 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 the new private key and we get a
Public key of ╥A64224╔╙ and we can go and see if that is right. There it is A64224. And notice, if you are playing around with this, you have to be very careful of the formatting when you are using this code because we did not 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 want it to be super clear and super basic. You just get standard Hex private keys that are allowed to put in.
And of course you could put it in decibel 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 did not do any real bug testing on it but it is 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 have spoken about already is integral to all forms of modern cryptography and it is completely
Integral to Bitcoin. Okay, so I hope that helps. I hope now you are 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 will check you in the next video.
0 Comments