ECDSA Explained Part 10 of Cryptography Crash Course

[00:00:02][Applause] welcome to part 10 of crash course cryptography my name is Julian and today we are talking about D discipline at the very top it's the pinnacle that we kind of worked towards in those past 9 episodes we are talking about the elliptic curve digital signature algorithm so we're gonna be talking about how to sign using elliptic curves and I'm telling you already this is gonna be quite some heavy stuff and the only way how we can push this through in less than half an hour is by building on top of a lot of things that we covered in those first episodes so if you don't have some basic understanding of cryptography do you need to watch those first nine episodes otherwise you're gonna be confused out of your pants today this is gonna be very important we're gonna go into some math it's not difficult math but there's gonna be some math and that's important because we need to understand some of the formulas that go in but we're basing a lot of the knowledge on how encryption/decryption in elliptic curve actually works and how cyclic group works in some of the examples and this I think is quite relevant and quite important to understand so as an intro and we're not gonna dive right into the writing pad because we first need to understand some basic ideas when we're trying to do signing so in this case we're talking about a digital signature algorithm using elliptic curves we're talking about making a signature and a signature on a regular document is quite straightforward have a paper and then I sign and obviously forging would be possible by great fortunes that's great movies catch me if you can for example where all this stuff got faked but as soon as we talk about the digital stuff this gets way harder because in the digital world changing something is quite easy so we need to have a signature that has some very special functions we need to have some ideas in how the signature can can kind of do its job individually depending on what we're trying to design because otherwise I just copy paste one signature from here to the next part remember a digital signature is not that I scan it it means that I can sign digitally somehow and if there's just a number of letters for example well I just take the number of letters and copy to the next document so the trick on doing digital signatures is by the signature adapting automatically to what we are trying to sign and this is some really exciting stuff because this means that your signature changes digitally every single time as soon as you try to sign something differently and that's quite cool and that's how basic cryptography actually works the other direction now remember this actually something we discussed in one of the very early episodes where we discussed that yes you can use the public key key to encrypt something and then the private key to decrypt but you can also use your private key to sign for something and then have the public key to prove or verify that you actually signed so let's go into the writing pad now and discuss four key things that we actually need for us to be able to do such digital signing so let's talk about part 10 elliptic curve digital signing algorithm great now we have those four key things that we need four keys for signing functions and we're gonna be discussing those and the key thing and then you will understand straight away so here we have symmetric and here we're gonna have a symmetric so we're gonna write this down because it's gonna be interesting to see if we actually have this so the first thing we need is confidentiality and that's very straightforward by me signing something I don't want to reveal my private key I think that's quite straight forward the second thing is authenticity um authenticity means that the private key must have signed the message it couldn't have been done through something else and so far both these would be working with symmetric and a symmetric algorithm I could sign a message with key and it could be very clear I'm very easy it's actually something that would be possible um I'm telling you why point forward not working but let's talk about this integrity integrity means the process I'm using makes it clear that nothing was fiddled around with and this is important for the entire algorithm so we always need to have confidentiality it's gonna be very interesting especially when we talk about the elliptic curve digital signature algorithm authenticity integrity and the fourth one and that's the most important one is ownership because ownership only exists in asymmetric cryptography in symmetric cryptography both because the key is the same the signer and decrypt they're both people could at the sign of the verify it could both have signed a message so it's not clear who actually had ownership because the same key is owned by both parties so this is something that's very very very relevant interesting so only with asymmetric cryptography we can actually do this signing and this is very very interesting if you want to see some practical applications you can go to my Twitter so go to my twitter my handle is at joy in hospital and what you will see in my little status on the left side is actually my public key and the way I generated this is with a service called key base dot IO you can do it for free if you want to you can also connect with me on their key base allows you to cryptographically verify social media profiles gives you a public key obviously you have the private key and then people can send you messages and encrypt them with your public key and you're the only one to decrypt them but another thing you can do if you have to verify it this is really you and obviously as a business owner and a public figure I have to do this on a regular basis I can then go and I can actually create signatures with my private key verifying that this information really came from me and not from someone else and this is very very interesting if you want to try this out go to my Twitter you can follow me there obviously of course you can get your own stuff at key based on Io they in testing to understand this now before we dive in and look how these schemes work let's ask ourselves first and we do this first now crypt analysis how could this stuff get hacked um and now obviously the very first one how this stuff could get hacked is simply by cracking the cryptography and this is something we discussed in all the individual cryptographic cryptographic algorithms that we have been discussing RSA diffie-hellman elliptic curves in the videos before so just refer back to those so this is quite straightforward um the second one is something called collisions and collisions means that the same signature could or the message that I'm be giving and I'm gonna show you how this works um there's actually different signatures that could be derived from this and this is very very dangerous it could also mean that the same signature could be the right from different messages and these collisions may not occur now just statistically speaking obviously they could occur but they are so rare that we can completely neglect them and this is something we're gonna be discussing actually in the next episode in great detail when we talk about hashing and about collisions there and you will see that the probability of having collisions in a good algorithm and this exactly comes down to integrity number three here um it's in those algorithms that we're discussing are negligible so the important thing is never roll your own crypto use crypto that has been tested and tested and tested and tested because and we see this also in cryptocurrencies some projects try to roll down crypto and then it gets stuck by having collisions or by having problems so always try to stay away from such project is very very dangerous because that many times means that there might still be deeper problems that you haven't seen or that haven't been tested you will see all these algorithms there have been used for decades they've been tested and tested and tested and so this is very important here to understand but now there is an actual problem in cryptanalysis here that we need to percent and that is understanding how the signing actually works is that I cannot as a signer I am not free to choose what I want to sign to prove something this is very very important so let me explain it to you if there's a message and someone tells me I need to produce a signature so I get a signature let's call it s and there's a signature s I am not allowed to choose freely not freely the message and this is something that's very very difficult to understand because every once in a while you see out there that someone says I am satoshi nakamoto from Bitcoin here I can prove because I can generate a signature out of a message and the trick how this works is that these people start with a signature and then they generate the message from it so they go the other way around does that make sense this way sorry I need to actually draw the arrow the other way going from a signature to the message can be easy to verify so this is very very easy to verify but going from the message to the signature is really hard unless you actually know the private key so unless you know the private key unless you know key private and this is very very important and you can imagine it this way imagine if I come to you and I say hey you know what I'm actually a really really really really good dart player really really good and I'm like world-class and then I throw the dart and I throw it dart and I hit exactly a little field on the right right I don't hit it the nurse in the bullseye I hit it exactly in a small field on the right and now I'm telling you and I say you know that's exactly where I wanted to hit that's exactly the place and you see how good I am I exactly wanted to hit this place now here's the thing if I only tell you towards it basically means I have the signature because this is where the error land it but I didn't but I you cannot be sure that I actually wanted to hit it there so what is the only way how to make it clear on where to hit it to well it's very easy obviously I could tell you upfront but then there's only one person that's there and it's only you so if another person would come and check how would this person know that actually wanted to hit the dark there it's very easy I marked the dart up front so I go on the dart and I mark the dart so there's always a couple of things that I need to be able to do in the signature thing I need to mark the dart in this case mark the dart basically where do I wanna where do I want to bring it and the other thing is is actually the target where am i hitting it to and if both can hit together then I'm winning and so this is the key this has to be set up front and the only way this is set up front is by someone else choosing the message not me going and saying hey listen um this is the message I'm just putting it out and this is what many times happens when stuff seemingly gets hacked in people can prove that they are someone but then the trick the actual proper way to do this is by going and me giving you the message and you havin to generate to secret out at the signature of it and this is what is the key thing and many many times this kind of gets overlooked in the crypt analysis in how to attack those things so always be very careful if someone can generate a signature to a seemingly random message but then doesn't manage to generate a signature the signature if you give that person the message so this is very very very very very important in this entire kind of scheme of things so before we go into elliptic curves let's do our as a really quick we kind of discussed our is a a lot RS a the signature system is very very easy remember at the end all we we on this one understand is that the message ^ fee plus 1 equals the message log n and so all we need to do is we need to have this number split up and this number split up is always the decryption key times an encryption key and it doesn't matter which step I go first do I go the encryption step first or the decryption stat first I always end up at the message if I then go the other step right so if this is the entire stretch and this is V plus one then it doesn't matter if I go here first and this is T and then here is e or if I go first and then D I always end up the same thing if I use if someone else uses D first and it's basically as or if someone uses a first then it's this person encrypts it this is encrypting and then this is decrypting if I sign first then I use my private key first so the signing just means I use the private key first and afterwards the public key key always the same thing basically the way it works is someone else who wants me to get verified gives me a message and I use my private key and I generate a secret a signature key private right and so the proof is very simple this person can then just use my public key key key pub and needs to get the message very very simple very very straightforward if this confuses you then just go back to looking into RSA should be very very very straightforward one quick note here is that obviously the signing part is very computationally intensive because we need to do the square and multiply algorithm so it's way more computer intensive than the symmetric encryption but the trick here is and that's something we covered a lot is to use very small public keys small public key keys they are predefined many times so that they're at least this part is intensive but this part then is easy computationally if you understand it if you understand what I mean so this is just as a quick side note here when we talk about RSA a lot of it is pretty much repetition here there should be all very very straightforward I'm not gonna go into details here if we kind of do a quick check confidentiality yes I'm not really my private key is it authentic definitely I can only have done this if I know the private key to the public key key integrity definitely ownership surely because I should be the only one who has the private key so we are making sure that all those four key points have are actually being applied this is always important to understand in in this entire thing let's go to the next one and that's the digital signature algorithm do you say and this is actually something that's based on diffie-hellman a little mouse scheme um and we're not gonna go to detail in this right now simply because you should just check back the video on diffie-hellman it's exactly the same concept just again also a bit flipped around with doing that using the private key first then the public key but I want to go into something that we need for elliptic curves and that is the idea that I need this ephemeral key okay and let me explain you how it works imagine I have this clock and how designing here works in TSA is you give me a starting point called M and I need to tell you an end point that I can prove it's an end point and it becomes clear from this end point this is the signature signature s that I know the amount of steps here I know the amount of steps which is basically my private key and I need to be able to prove this year obviously you also know keep up and by putting this into perspective you understand this now here is where does the important part I cannot do this without ad another key because if I don't add another key and that's why we're gonna get another signature called our our is derive from K times alpha to generate a point we need to do this because if I if you give me another message let's say you give me this message N and then my point is gonna be here so let's call this s1 and this is s2 what you could do is you could actually calculate my private key from seeing the difference of s1 and s2 because it is on this cyclic group so what I need to do is I need to have this ephemeral key which is a temporary key that I constantly change every time I'd make a signature I need to change this key right k needs to be changed every single time needs to be changed every single time this is very important as you will see in a loop the curve cryptography even large companies like Sony make mistakes there and this is something that I'll show you when we discuss this on elliptic curves and will not go too much into detail into DSA first of all it's very straightforward and it is pretty much similar to elliptic curve just here we're using the discrete logarithm problem and on earth the curve we use the elliptic curve so formulas and everything very very similar you will understand it when we're now talking about the curves one quick thing obviously because we have K here we get two signatures R and s is also going to be the same in the curves but and that's also a massive thing these are twice the bit length twice the bit links the bit length compared to the keys so if we have a key that's 2048 bits that's the key then that means in this case we have 4096 bits for the signatures and this is a lot this is a lot of our data so I just want to kind of yeah keep this in mind here so this is digital signature algorithm and now we're going to go away from so this is based on the discrete logarithm problem but now we're gonna go and is actually what we're gonna discuss and we need some of these ideas we're gonna be talking about elliptic curve digital signature algorithm EC D is a great now remember a couple of things to remember here are we're talking about coordinates it's very different not points quite key and I think the key that's also very easy is the key private x and alpha point equals key public right I think very straightforward so let's talk about the signature generation so let's talk about signature signature generation the reason why this is important to understand is because all of the cryptocurrencies pretty much are based on the ECT si and it's very very relevant to understand how transactions work and this is the fundamental to all this so this is the kind of trick here and this is what we really need to understand a signature generation just like in DSA before we're gonna get to signatures because we have this ephemeral key so the first signature is r and r is actually very straightforward it's this ephemeral key times to generate a point alpha and it actually gives us if we discuss large capital R and lowercase R it's just the x-coordinate important K secret and needs to get changed every time otherwise have the same problem as before remember the D curve is nothing else in a cyclic group and in the cyclic group otherwise I could subtract the signatures from each other if K doesn't change and I could calculate someone's private key we're going to be discussing this also at the end so this is something that's very very important secret changed every time and I need to use a random number generator to get K large number two to the to 256 bits very very important great and then we have the second signature s and s needs to basically proof proof that I actually hit the target so that's important needs to proof that I hit the target so me throwing the darts so let's define a couple of things so are very straightforward I have this ephemeral key called K it's secret I'm multiplied with the generator point and I get the x-coordinate which is gonna be lowercase our signature s let's define a couple of things we get M which is a message and this message is hashed we're gonna discuss this in the next video what does this mean many times this is also be called to call the set we just stay with em just for simplicity sake but if you ever see this in other cryptographic papers that too many times means it's the hashed message now we get function and important the message has to come not from the person signing this is the key the other person has to give this person the message there has to be some outside force that's unpredictable for the signer that's really really important now we have u u equals the message m over the signature okay so let's stay let's keep this quite straightforward so s is the signature and now we get another factor and that's V and V equals one signature R remember R is derived from K over s and so now we have something that I'm just going to write down and you will just have to follow me because what I'm trying to prove is that you give me message the message your message is just a point on the curve and that I can give you another point and with this at a point I can prove that I know the private key without you knowing what my private key is so how are we going to do this very straightforward we have u times the generator point plus V times K public and that has to equal different more key times alpha now remember the public key obviously and alpha are publicly known right so let's just mark those green so that we know these are publicly known this is very straightforward what we see from here is K is not publicly known obviously that's very very important V is something we need to kind of figure out because these are over s and u equals M / S so this is kind of there and it would be good to find a U and V so that I can get this other point and remember especially U is something I cannot directly influence because you comes from another person we can see this from the M up there all right so let's mark this blue maybe because here I have the message so I cannot directly influence that so I need to find a V that's directly in relationship to my public key and the V is RNs if you can understand if you can see this so let's make mark this yellow so here I have R and s so I need to find R and s that is in direct relation to my public key that satisfies a you again into another key number that I have which is the ephemeral key that's private out there so let's do some reformulations so that this becomes a bit clearer what we are basically now doing is we write u times alpha so that stays plus V and now we split up the public and we write that this is ke private okay private times that generate a point alpha and that equals K times alpha desert estate so we have alpha all a time so what we can just do now is we could scratch away alpha and what it leaves us with that u plus V times the private key equals K very very straightforward so now you see already a couple of things if you don't know the private key right so let's mark this one red again so that it becomes clear so if you don't know the private key I need to test test test test test to find values because again the U is something that I care influenced you gave me you so I need to find a V and a K that fit together with your you that you are giving me so this is now way it gets very very tricky and so this only works if I know the private key final a private key gets very very easy if I don't know it it's very mathematically intensive and it's actually impossible so let's do some substitutions let's substitute you put em over s because that's just from derived from above let's substitute V that's our OS x key private and that equals okay so what I can do now is I can just put this into brackets and I write M plus R times K private over s equals K very straight forward so again I see that well the message is something you're giving me R is something that I can calculate from K but it is only works if I know the private key and I need to calculate s so let's kind of just reformulate all that we get kind of s so we do M plus R times K private equals K times s so we just brings yes to the other side now let's divide the entire thing by s and then we have s equals I by K we have s equals M plus R times the private key over the femoral key okay and so it's very very straightforward how can I calculate yes well the s is very easy to calculate by you giving me so this is something that you're giving me what color day use blue so I get the blue which is the message um I can calculate the signature other are the others okay I can calculate um are I can make public because it's impossible to back calculate it this is I only know and the little R I can calculate publicly so but I can only do all this if I actually know the private key and I know the ephemeral key because otherwise it's not possible to calculate an S and it's the same as in the digital signature algorithm the entire flow the entire stuff works because you're giving me an M that I cannot predict and I'm the person who actually knows the private key and which is doing mathematically reformulation now remember before we go into verifying the signature because this is gonna be relevant so obviously there's an SN and are coming out right this is one signature in the other let's look first at what happens why do I need kay so let's do this first why do I need kay um and this is just basically coming from reformulating a lot of the things um so if we look at this line here again so we're looking at this line here right I remove this so to make it clear so basically what we have is we have K times s equals M plus R times the private key so now it gets very very tricky um if if you want to calculate the private key then the way you would just do this is you take K times s minus M so I take m to the other side divided by R equals the private key and so now it starts getting very straightforward because if the a femoral key gets known then I can calculate R and s is something that I could calculate both of those actually I could calculate R so R comes from K especially if it's the same key and then I can calculate s as well here and from that I can calculate the private key and the way this works is exactly the same way as described here if I always use the same one that I could just subtract one key R one signature from the other signature and then I know what's gonna be the private key at the end so I always need to use a different K and this K is has to stay private so I need to use a different K and decay has to stay private otherwise I can subtract two signatures from each other subtract the signatures because otherwise I can calculate the private key so it has to be secret and changed and this is a massive mistake that Sony Playstation 3 made in their games they used the same private key at the same ephemeral key for every game so someone just had to buy two games they could just subtract the signatures and well they knew that the difference was gonna be the FML key and that way it was very easy to calculate R calculate s and then they had the private key that Sony used my goodness right interesting how does content works awesome so now it gets from someone I get R and s and the only way they could have calculated this is by having the private key and having K so let's talk about verification now it was actually very straightforward and verification is quite easy we have U which is the message over one signature and we have V which is R over one signature and now it gets very simple this is something we defined on the top that u times the Alpha point plus V times the public key remember the public key has to be in there we just split up the public key and a private key times the Alpha point has to be in this case actually our and remember our is just X if the is the x-coordinate little case is the x-coordinate and in this case our is K times alpha remember this is K private times alpha and this is the entire things so if someone can give me the values for u and u is basically the message the two signatures and then ya x-coordinate they obviously can tell me exactly on this circle if I give them a random starting point which is the message and they're giving me an endpoint here which in this case is a little R they obviously must have known in between the factors how to get there and part of this factor has to be a private key without revealing it because otherwise they wouldn't have known the number of steps and this is only shown here through basic mathematics but it's very very important and very relevant to understand how this works obviously again remember if the message here is not voluntary well then I have a second factor and I could just have any kind of public key here that I know because I can see for example satoshis public key key and I can come up with a message with the generator point that's gonna generate next value for me so it is very important that you becomes random because this is basically the first step so here is the first step and this one is predefined and then I need to know how far how much further do I have to walk and this is only possible by having the private key I hope this makes sense if you like this stuff let me know in the comments below if you have any questions let me know in the comments below this is gonna be this is intense I understand it and it involves a lot of math cyclic group basic knowledge but now we're kind of covering all this we're going to be discussing hashing algorithms in the next episode and if you do understand this give me a thumbs up please you know and give yourself a pat on the back because this is really really some detailed heavy stuff and it shows that you really understand those ten episodes if you don't want to miss anything then click the subscribe button and click the bell button and I'm looking forward to seeing you at the next episodes yours truly Julian [Music]