Video - Bitcoin 101 - Elliptic Curve Cryptography - Part 5 - The Magic of Signing and Verifying
There is nothing more magical in Bitcoin, or all of cryptography than digital signatures. And the most magical step of all is the verification. This is the step we focus on in this video, generating the entire process in just 50 lines of code (no imports or special function calls!) and watching as the Private Key falls out of the math entirely! So beautiful. The receiver is left with proof of the sender, confirmation of the message and no way of retrieving the senders private key.
TRANSCRIPT
Hello, this is James D'Angelo and welcome to the Bitcoin 101 blackboard series. Today, we are diving into part 5 of our five-part series on Bitcoins bedrock, the elliptic curve. Okay, and specifically we've been talking about this curve y2 = x3+ ax + b where a = 0 and b = 7. And today we're doing something really special that before 1976 did not exist at all. The modern age of cryptography was brought in by this ability to do public key cryptography specifically once you have the public key you can do this thing that we call the magic step. Where you've signed the transaction or you've signed the message whatever it is and now you're going to verify it. But you're going to verify it without having the private key. And so, in the math by simply having the public key, a hash of the message and all the parameters of the elliptic curve that you're working on, you can actually verify whether the message was sent by the person with the private key and know for sure that the person who sent the message is in possession of the private key. But you yourself do not have it, okay.
So let's just jump in the code and start taking a look at how all this happens. So here is the code that we spiffed up a little bit from our last version and added just a couple sections, right. So, most of the code is the same for generating the public key you still need all these things, modular inverse. ECaddition, which is not real addition. Remember this is the invented elliptic curve mathematics, ECdouble and ECmultiply. Okay again, this isn't real multiplication. This is multiplication on elliptic curves. And in the previous video part four we did public key generation which is simply just multiplying the generator point times the private key. So, the private key is just this big integer and the generator points a point on the curve and you end up bouncing all over the curve until you land on a new point and so the public key is really just a point here we have the X and Y coordinates. And for our spiff up version of the software we separated everything that our points in two points.
So you have the X and Y coordinates whenever you're dealing with actual points. So, this is the public key and here the public key is printed out with a 04 at the beginning which is just the code and then you get the X and Y coordinates there. So, let's just run our code and then start to get more familiar with the ideas of signature generation and signature verification. So, this is really all we're adding to our code today to add this really magical step. Okay, so let's run the code.
Here we've got public key generation. Okay, so the private key which we've just typed in a private key right here and you can put it in hex format as long as you put the 0X at the beginning. Here we have it just in decimal format. Private key just gets spit out in base 10 format. Below that we have the uncompressed public key. Remember it starts with the 04 and it's just the two coordinates on the elliptic curve that correspond to the public key. So here is the big X coordinate, here is the big Y coordinate and then we've got the 04 and if you take out the spaces that's exactly what the public key looks like if you go to bitaddress.org.
You can compress this mostly just by taking this coordinate converting it to hex and adding a 02 to or a 03 depending upon the polarity of the Y over here. And then we have the magic where we're actually starting to get into signature generation and signature verification. And in our case we've got a signature verification of true. Okay so, let's go back up to the top of the code, walk through it and see how exactly this all works. So again, like the last video of our domain coefficients really sort of the six constants that are specific to the Secp 256K1 which is the actual curve Bitcoin uses. So, using this prime number it has this many points on the field that are valid. It's really at the endpoint when you've actually multiplied the original generator point N times that you reach the infinity point. Which is really the beginning sort of the clock nature of this cyclical group that makes elliptical curves unique.
Okay, and then as we said y2 = x3 + ax + b, well, here is A and that's 0. And here is B which is seven and a lot of people commented that nowhere in the code here do we see B again. This has a lot to do with if you have a generator point. You really don't need to have all the information of a line or a curve. So, for example, if you have a line and you have a point on that line and you actually have the slope of that line you know everything about that line so you don't need to know exactly where it intersects with the X or Y axis. The same is true when you're dealing with curves or whatever.
And so here is that generator point that we just mentioned. And here is the big X coordinate and here is the big Y coordinate. Okay and you can stuff them in together and get G point but we're just going to use them as Gx and Gy. And as we spoke about the last video H which is another domain coefficient of this curve. The H is the cofactor and that is one and so we've left it out of our code entirely because it's just a multiplier but multiplying by one is pointless, okay. And so, for almost all practical purposes you could erase this and since this is 0 and it gets added in you really could just erase this as long as you take it out of the equation right here, okay.
Then we get things that are not constant at all okay, so this is a private key so you have to put that in. This is a random number so we wanted to keep our code really slim so we didn't want to put a random number generator in here which is really complex and really hefty. And so, we just brought in a random number. Of course, every time you do assigning you need a brand new random number okay. So this is really just kind of a fake random number that we use to show how the code works. Each time you run it you could just change these numbers or put in a new random number and you'll see that it works just fine. But again, we didn't want to put in the code for generating a random number and we didn't want to have all these imports and all this complex stuff. One of the code run by itself, okay.
And this is the message that you're sending. Well, it's really the hash of the message that you're sending. So whatever message you have be it the U.S. Constitution you take a SHA256 hash of it and you stuff that in here. And here we have it in decimal but you can put it here in hex as well. But in terms of Bitcoin this is often going to be the transaction itself. And we're not going to do a Bitcoin transaction, we're just going to show you how the magic of Bitcoin elliptic curve works, okay. And so how this message can be verified without the receiver knowing this private key. And so, here again we have our mod inverse which is the extended Euclidean algorithm and it's really just division and elliptic curves. Here we have elliptic curve addition which is not true addition, it's invented for elliptic curves. And all it does is it adds points P with point Q. So here is point P the X and Y coordinates and here is point Q which is the X and the Y coordinates. This is the same code as last time we just cleaned it up to make this idea of separate coordinates more clear.
So now you can see that this is the Y coordinate of point Q and this is the Y coordinate of point P and it all makes sense. So here you have the X coordinate of the result Xr which is actually brought into Yr and then you're returning X result and Y result. And this all corresponds the ECaddition and ECdouble with the image that we put up last time. But now it's more cleared because you can actually see that this is point P with its X and Y coordinates. And this is point Q and this right here is the inverse not the modular inverse just the inverse of the result because it's just flipped over the X axis to get the final point R here, okay.
And so now it all corresponds with the software that we wrote. And again, if your point doubling you're just putting in the X and Y coordinates of point P and you're ending up with an R which comes down here. Which again is just flipped over the X axis so -R and R right here. It just a little note, it really doesn't matter when you're using the ECaddition whether you put the P point in first to the Q point. They really will end up just drawing the same line and spit out your R. Which is all the way down here. And again, we spoke about this more in detail in the last video but ECmultiplication you could do simply by just repeating these operations over and over and over or you can make it more efficient by combining doubling and adding in sort of this looped algorithm right here.
And this is analogous to square and multiply in the regular world for doing regular computing multiplication. This speeds up how even regular computer's not using elliptic curves do multiplication. Okay, so we've discussed a little bit ECmultiply, double, add and mod inverse. And last time we did this one multiplication which gave us our public key, and remember a public key is just the X and Y coordinates.
Now, we come to the fun stuff. The signature generation and signature verification. So, in Bitcoin or wherever you use elliptic curves, one party the sending party is going to generate the signature. And in that signature, you're going to have a hash of the message. So again, we have our hash of thing to sign and they're going to have to generate a new random number. So, a lot of times where there is backdoors involved with elliptic curves so there is real problem sort of like with the Sony PlayStation issue. There were issues with the generation of the random number. So, this code right here doesn't have issues. There will be no room for any issues but when you generate this random number or if you're not generating the random number and just using the same number each time like the Sony PlayStation mistake. You will end up with problems with your cryptography.
So one group the party who's sending the Bitcoins of the transaction generates the signature and to generate it they run through these equations right here and the real results of signature generation is you send the receiver an R and an S. And we've written this all up here so it's a little bit more clear so signature generation are these steps right here. And the output that you're handing to the receiver or in Bitcoins world you're broadcasting to the network is going to be R and S. And you'll notice that inside of S is the hash of the message. So, this would be a hash of the transaction or whatever you're dealing with in Bitcoin. If you just want to prove that you have access to an account. You might put a message in there. You might go, look I've got these coins and you might put your name in there and then you send a signature with that message and these steps of signature generation and signature verification will prove that you have this private key associated with this public key and that message was indeed sent by you.
So let's clear this off and we'll go through these magic steps one by one and you'll see how the pseudocode over here corresponds almost one-to-one with lines, direct lines from our code over here. So, the first thing you do is you just create a public key and in our code case we're creating the X and Y values of the public key because the public key is a point. And you do that just by multiplying your private key which is a big integer by a very big point, your generator point and that point is defined by the Secp 256K1. So that's a constant. Every time you send a transaction with Bitcoin you're going to use the same generator point.
Then the next step is you create another point and in some circles people call this the ethereal private key sort of the temporary private key. And this is just a random number make sure it's very random times the generator point. So, it's very similar to the public key so it's a big integer multiplied by the generator point and this is x1 y1. Then you generate R of the signature which is just x1 moded by N. And remember N is the number of valid points in an elliptic curve field and it's not equal to P. Which is the prime number. It's close but it's not equal. So, N is a very important number to have if you want really good cryptography. So x1 is generated. Right here are a serial private key and it's moded with the N and you get R. R is very important. Then you take the message which you want to hash which corresponds in our code right here and then you add it with R which is generated right here times the private key. And you'll notice that all of this stuff, this is actual regular addition and regular multiplication so this is not ECmath. This is regular math inside there but as soon as you step out of it this multiplying right here is multiplying by the mod inverse so it's really division inside of elliptic curves. And you are multiplying by the modular inverse of this random number and it's almost clear here in the code and the mod there is N. And then you're actually moding that whole quantity again by N. And that's how you generate S, also very important.
And then you just spit out the signature the signature is R and S and this is what you'll send and this is what's broadcast on the Bitcoin network. So now you've got R and S which is just information based on the hash of the message, the private key, this ethereal private key. And other coefficients of the Secp 256K1 so it's a very unique R and S. And here is where all the fun happens. And it's very important to notice that down here you'll see that here we're using the public key and here we're using the private key. So that the person who verifies whether that signature is valid does not need the private key and this is why modern cryptography is so powerful. You do not need a shared key to send a private message. These are different, this of course obviously is public and this is private and you see the same thing right here in the code public key, public key, private key, okay.
And so what you're going to do here is you're going to generate some other little numbers you know w u1 u2 which is all just kind of fun math we're actually swirling around the elliptic curve and you end up with an x coordinate of a point that is equal to the original r1 or at least if it is equal then the signature is valid. So, what you're doing here is you're just taking the s from up here and you're taking the modular inverse of s and you're moding it with N, then you're taking the hash of the message and remember a hash of a message is very important. It's like a fingerprint it shows you that the message has not been altered and you're stuffing that here into u1 and you're multiplying it by the w from the previous step and then you're moding everything again with N. And again, everything over here corresponds to something over here. We separated these points out into X and Y coordinates but it's really the same thing going on, you see a w being generated this is the modular inverse of s and it's moded over N right here. And here is our hash of the message.
And again, this message can be a transaction or it can be just a message that you're sending saying I own these coins or I was here on this date or whatever it is and it will be provable that you had the private key and were able to sign that message. And then we generate u1, u2 and then we create a point right here. Remember this is all elliptic curve mathematics right, and we see that very clearly over here. We end up with this point x2 and y2 where the X coordinate comes down here for our verification and if that all works out the message is verified. So, this is everything. This is the math of elliptic curves. This is the real secret. This is why public key cryptography is changing the universe. Okay, so it's used in everything. So all your Gmail, Email stuff, Facebook stuff everything now is public key cryptography. So, calling Bitcoin crypto currencies when it actually uses cryptography light is a little bit unfair, right, you really should be calling Gmail, cryptomail and Facebook, cryptophotos because they're all using cryptography for everything. Banks use way more cryptography than Bitcoin. Remember Bitcoin uses a public ledger. So, it can't encrypt everything. It needs to be public and it needs to be readable but this is what protects the individual persons' coins from being spent by anyone else. You can generate your own private key and from that you can create a public key where someone can mail funds to. And since you generated that private key by your lonesome. No one else has access to it so no government, no one can tell you what to do with it unless you decide to use it.
This is really revolutionary stuff and this is old stuff so remember 1976 the RSA and all that was built the Diffie-Hellman key exchange, ten years later we get the elliptic curve version of it which is just a better implementation. It's faster, it's more secure. Okay, so let's jump back in our code and just make sure that we've walked through everything. So again, here is signature generation, here is all the equations we saw, here is a random number which really should be random, we and this point use the same random number here is R and here is S okay. And then here all we do is say if R is equal to x. So the double equals is basically a question, are they equal. If it is, it's going to print out true and if it's not it's going to print out false.
So let's run it one more time with a private key and random number and message we have and we'll even change it and see how it works. So, let's run it. Public key generation okay, so here is my private key, here is my uncompressed public key, here is my signature generation of R and S which are going to be made public. So, they hide the private key. You can't pull the private key out of those and then those are sent and if R equals X of the new point that we generate then our verification is true. And this can be done with any elliptic curve. These are the same equations for all elliptic curves and this is the same equations for anything done in Bitcoin, Ethereum,, Litecoin. They're all using the exact same stuff. They may use script on one side but they're still using elliptic curves for all of this stuff. Okay, so let's change our private key. Let's make it a goofy private key. It really shouldn't make a difference, right. You have the private key you run it and our signature verifications true. Let's change our random number, okay. We can do anything to this number we want. Let's put in 777 instead of all those numbers okay. And run that. True, hash of thing to sign. Because this is our individual thing that we're signing it. We really don't know what's included in there and we can mess with that hash. Okay, so let's put a bunch of zeros on it. So, this code works regardless of what private key you have. What random number you put in and what message you're sending. Well, you can break it pretty quickly by changing your generator point which is very sensitive issue in Bitcoin. And now we just change that to an 8 and now we'll run it. And we get an immediate false. Right. We're now messing with our generator point and elliptic curves very sensitive this point because it generates all the other points and hits the infinity point N times later.
So unless you've got a really exact point it's not going to do that and not every point on the elliptic curve is a good generator point. Okay, so let's undo till we get back to where we were and then I can paste that code to GitHub and everyone can play around with it. And I really hope you see that all of this is really just kind of like high school level math. All right, there is no hashing in here. We're squaring stuff, we're multiplying a couple things, we're doing a couple things with modular arithmetic. The real difficulty here is we're using enormous, enormous numbers and that's one of the big secrets of cryptography. The other big secret is this mod in the circular generation where things go around and you take the remainder. So you're throwing away a lot of information which makes your steps unrecoverable. So that's it. I really hope this code helps as you're trying to explore Bitcoin or even any of the other crypto currencies and please remember to like, comment, subscribe, do whatever it is you do and we'll see you at the next video.
(END OF AUDIO)