Cryptocurrency Signatures: Hash-Based to Elliptic Curve Systems

[00:00:00]the following content is provided under a Creative Commons license your support will help MIT OpenCourseWare continue to offer high quality educational resources for free to make a donation or to view additional materials from hundreds of MIT courses visit MIT opencourseware at ocw.mit.edu today I'm going to talk about signatures and all sorts of different signature kind of things in the in the problem set you're you're working with signatures but you're working with hash based signatures which are not actually used in Bitcoin at all but we'll talk about those okay so if you've gotten through the homework there's Lamport signatures right these are hash based signatures and they use hash functions so it's fairly straightforward like you know you can understand them there's nothing super crazy going on the code is fairly compact so that's cool what are some disadvantages of these Lamport signatures does anyone like yeah yeah okay so okay plus ashes that's cool one-time use other possible disadvantages of them relative to other systems you're aware another is they're kind of huge kind of big right not you know you can deal with it but if you are looking in the like Forge or that that file with the signatures but it's like what eight eight K first signature eight kilobytes kind of big keys are 16 kilobytes kind of annoying private keys are also 16 kilobytes so yes sig 8k 16 K proved palm key so that's some disadvantages so since I don't have slides you make this sort of more fun and interactive what are some solutions for these problems so we can actually mitigate solve both of these things to a pretty pretty good extent so how about the first one one time use what would be a fairly obvious way to mitigate the one-time use problem and like don't think the answer is is too stupid like it may be a fairly stupid answer into I work yeah there's probably some clever way but that might be too clever like something really simple for okay I can only use a key once how can I use a key quote-unquote more than once yeah so you can say well I've got this 16 kilobyte public key well I'm gonna make a 32 kilobyte public key and it's just two public keys stuck together and now when I mean you know and now when I make a signature I just put an extra bit in the front and I say well this signature is using key 0 or this signature is using key 1 and it's got the whole signature after and then you look through this 32 kilobyte public keen you say okay well it starts with a 0 so that means it's using the first key you know the first sub key in this 32 byte public key block and in this case that's using 1 so that means it's using the second you know the latter sub key so that would work that would let you use the signature the your public key twice at the cost of doubling your public key size which is not really great right it that's not a great if it's not very efficient but it does sort of work okay any any clever ways to do it more efficiently or wait so okay also so I'll give you sort of a hint in this case let's say this is you know pub sub 0 and pub sub 1 right and then like you're 32 byte pump key is the stem concatenated together right of 0 1 what would happen to the private keys in this case right how would private keys work here same expansion of size I guess and you can anyone think of a way to to mitigate the expansion of size of private keys in this case so the private keys are sort of you know the Prima here right they lead into these public key blocks so you could just say okay well I have twice the size private key leading into twice the size public key could you do that more efficiently yeah yes so how would you tell let's say you have this 16 K block and you want this to turn into two public keys so that's that's the that's the basic good way to do it and it sort of like turns in like that how exactly like what's a way you did that yeah so so this is a hash function right and so before we just said okay hash of you know this is like block 0 this is block 1 this is block 2 so the idea of you know pub let's say this is invisible this might be kind of too small right yes okay let me let me put this bigger okay so in these in these diagrams you've got your your private key right now and it's in these big blocks and there's 256 of them but let's keep it small and the idea is these are 32 byte blocks with random numbers in it and then you hash it to get your public key and this is you know so we say okay pub 2 and this is you know public this is private let's say secret pub 2 is just the hash of secret - right well yeah what we could do is we could put them to have two different hash functions and then a a real simple way to make a whole bunch of different hash functions is we sort of define okay well hash 0 is defined as the hash function of you know whatever your input X is concatenated with the number 0 and then the hash 1 we define as just X comma 1 and so on and this is this is actually secure you could do this any questions or possible objections yes so so this is like you know there's no real entropy or secrets in this zero and one so but it's it's purely riding on X right so but the idea is well if I do this and like you know I say okay well pub to you is secret to concatenated with zero yeah if you no secret to you can go back because zero is obvious but the idea is if you don't know secret to the fact that you know the last you know bite of this what the hash input doesn't really help you because there's all this you know all this data that you don't know and so you're not going to be able to find a pre-image you're like okay I know the preimage to public to ends with a zero byte what are the other 32 bytes that come before that like you can't you still can't go back to make a pre-image the second to last byte is gonna be in so the attack is I've got pump two which is a 32 byte hash output I want to find what this thing is now I do know what the last byte is right it's gonna be let's say 33 bytes and the last fight is a 0 and this is gonna be some you know random numbers all the way back so I have sort of you know I have some insight into what the preimage is I know the last byte is a zero but that doesn't help because I don't know all the the bytes before that so I can't really do any you know I can't I can't sign because I don't I need to be able to reveal all these things and the way the hash function if it's a good hash function the fact that you know some part of the preimage shouldn't give you insight into the other parts of the preimage because it's like looks really random and you know adding adding stuff to the end here like reveal and thing there are hash functions where this can be dangerous and you can consider those like broken hash functions where if I if I concatenate a lot of known data at the end it might give me you know properties of the public key that I can find shot to v6 as far as we know doesn't you know it works fine most of the hash functions work fine this way so yeah you can do this and then you can say okay well I'm gonna use hash function 1 or hash function 0 to make pub keys 0 right this is funky 0 and if I use hash function 1 I make punky one now I have a 16 kilobyte this so now what I can do is I can say okay well I have a 16 kilobyte secret key private key but I have a 32 kilobyte public key that's that I can use twice that is two sub keys so I don't have to store as much of my private key data so that's cool that makes it quite a bit more efficient does anyone have an idea of how to get it even more efficient for private key storage you can actually get it very efficient using this kind of idea it is what would you you so some hints this is pretty useful right the idea is well even if you know what the sort of suffix of all these things are if you don't know X you're not gonna be able to find the preimage right so maybe add some more stuff here any idea of so another big yeah right right so instead of just saying 0 & 1 we can say like we can say here well why not just have one chunk and you say hash 0 you know hash hash like let's list one chunk and it's got you know random number X well this is hash x comma 0 this is hash x comma 1 this is ash x comma 2 okay so yeah so what you can do is you can this was before right where I said okay yeah but this is basically how to do a 32 byte private key where your private key is actually quite small and you just derive all of the public keys by adding numbers at the end concatenating them into your hash and now you're like okay cool I have a 32 byte private key and I can make enormous public keys from them and it's still secure right because I can add whatever number I want here and I can do this a million times and no one will be able to find the preimage even though I'm giving you all these related hashes right it's X comma zero X comma 1 X comma a million I can give you millions of them and it each time I do it it doesn't give you any insight into how to find what X is if it's a good hash function so that's really powerful and now I can say okay the private key problem is solved I have like o of one growth in my private key I can make as many public keys as I want never gets any bigger cool still have this problem with the public key so let's say I want to sign for x okay while I make a 64 64 kilobyte pump key now I can sign four times great but my my public key size expands with the number of signatures I ever wanted to any any ideas on how you could mitigate that or how you could still make a usable system despite this fact there's a there's a couple sort of different techniques any ideas okay so one would be every time I sign I also sign my next pub key you can do that it's got some some downsides right so the idea is I just commit you know I first published one 16 kilobyte pub key and then I say okay when I sign I'm going to sign my message and concatenated that message will be my next pub key and so I'm signing something and also indicating what my next public key will be that I signed with then I can still maintain a small private key and then keep signing the problem is in order for someone to verify they're gonna need to look at all of my previous signatures right so if I if I'm saying hey here's my 500th public key that I'm signing with here's the message you're gonna have to go back and look at my entire history of signing it's not great okay so other ideas of how to how to deal with large pump keys what's the way you could do this so hints is there any kind of data function we've seen here where it takes an arbitrary sized amount of data and outputs a fixed size in fact it's the only thing we've been talking about so far so what would you do to make your public he's smaller - yeah right okay so you say well yeah 32 byte pump key well you just commit to the pump key with the hash of the whole thing right and I say well I've got I've got my I've got my 16 kilobyte pump key I just hash it right and now I have a 32 byte public key and I've committed that that works right I've committed to my public key however when I sign I need to provide the whole public key in order for you to verify you know I need to provide this whole 16 original pub key you know original version pub key after when I sign so now my signature goes from 8k to what 24 K so I haven't really made it more efficient right in that like the total thing with like public keys and signatures stays the same size actually slightly larger but this is kind of a gain because the public key I mean it might be like I'm showing it to you beforehand and it we're space constrained there and then when I'm doing the signature have more space or time or something like that so this is actually useful and actually this technique is used in you know Bitcoin and all different crypto currencies where you know you can call this a punky punky hash or they say pkh and the main benefit is size right you could say well if I've got a really big punky I can commit to it by sending to the hash of the pub key and then when I later want to sign I reveal the actual pub key you do it that way okay so then this is pretty cool right we've now got we've taken our system which had fairly large 16 kilobyte private keys turn them into 32 byte private keys great and also this is o of 1 never expands awesome we've taken a system with large potentially you know huge 32 kilobyte 64 kilobyte public keys we've got it down to 32 bytes awesome ok we've now made this thing much more efficient much more useful the problem the signatures are still big they actually got a little bit bigger because they include the full public key in the signature and let's say we had a you know one of the things where we make a bunch of public keys and commit to them at the outset so he said okay I've got a 64 kilobyte pub key I can commit to the whole thing by hashing it however then when I reveal and want to give you a signature my signature is now whatever it'll be like 72 right signature would be 72 kilobytes kind of huge so I can add a bunch of keys but I'm just sort of like pushing the problem somewhere else into the signature right there's a better way to commit too many public keys it's maybe not super obvious unless you've seen it before but if you have do you know what the better way to commit to many public keys is or you could come up with a day on the spot and to be like wow you should have gotten this stuff named after you any idea okay so what you can do it like it's a little non-obvious you can make a tree right so the idea is instead of just saying oh I'm going to take all four of my big pub keys stick them all in a row take the hash of that whole thing and publish that as my public key hash I'm gonna have a little bit more complex design and that design is a binary tree okay so the idea is here are my four public keys that take up you know 64 KH I can make these intermediate hashes so I make a binary tree where I say okay this is the hash of the first two keys stuck together this is the hash of the second two keys stuck together the top is the hash of these two intermediate hashes stuck together and then this top is sort of my root which is equivalent to my pub key hash and so I can publish this and it is committed it commits me to all four of my public keys so what it might not be obvious are there do you see any advantages that this could have over just concatenating all four of the keys and hashing it the private key is down here right the private key is not shown but it turn you know I have a private key turns into this bump keys and we can use the technique here where we just have really one 32 byte private key and create all the different chunks of all the public keys right by concatenating different indices yeah so if I want to exactly I can prove that hey this is public key zero which is in here this root hash and I don't have to reveal all four in order to do it so yeah then II did someone else have probably the same idea yeah okay okay so how are we going to do that maybe I mean you obviously know anyone else have ya right yeah and then you can prove up to the top so I have little colors the idea is the the receive you know the verifier who's verifying a signature and already he already knows the route right because you've sort of pre published that as your public key it's your public key route your public key hash and then you're provided that verifier is provided with public key zero saying hey here's a signature here's the message here's public key zero so you've got both of these things now the prover needs to prove that public key zero is contained within the route and to do that the only two things you need to add the prover needs to add is pub one okay so the prove ourselves once the verifier to compute this and then the prover says hey here's hash two three which allows the verifier to compute the route and then check that it's equal so yeah you only need two extra hashes instead of all four so save some space it doesn't save that much space when you only have four it saves a lot of space when you have a thousand right so you can add you know event n elements and the route the route stays the same size the route say is 32 bytes regardless of how many Leafs leaf nodes you have and you can prove an element with login no parentheses are wrong Oh login intermediate hashes so if you have a thousand keys your route stays 32 bytes and your proofs are going to be not too too big right 320 bytes of overhead which is somewhat like a bunch smaller than a signature right so this is really cool and you can use this much more practically than the sort of raw Lamport signatures that were in the first problem set because those you know if you're just doing one key in one signature it's about the same size but this actually lets you use it multiple times lets you store a much smaller private key commit to much smaller public keys it's a more usable system the signatures though still are of huge right you'd have your signatures are gonna be a little over eight kilobytes which is okay right computers can be able to eight kilobytes that's called a Merkel tree and made by Ralph Merkle in like seventy six or something and it was originally made for exactly that purpose anyway so these are called Merkel trees Ralph Merkle he doesn't really work on Krypton I work something like biotech stuff and I think cool and he gets like everything named after I'm so you will see the word Merkel like everywhere and it's like you know he invented something cool awesome this is one of the kind of things though where it seems like yeah I might have been able to think of that right it's sort of a binary tree and hash functions like it's nothing that crazy but so there's all sorts of you know Merkel trees you can make it different you know it's used in Bitcoin it's used in a bunch of different crypto currencies it's a very cool it's a very you know powerful way to take a whole bunch of different things and commit to them in one small thing okay so this is very cool but we can do better and so the next things are things that I definitely would never have thought of because it's much more complex than just like hey let's use a binary tree with hashes and I will mention RSA and then go into ECDSA and I left a curve blare in evidence signatures which do different things and are not based on just ash functions so I'll talk about RSA for a few minutes and then we'll have a look a little break like intermission and then we'll go into the elliptic curve stuff okay so RSA was invented by locals the are is is Ron no I think the R stands for Rivest but Ron Rivest is at csail and he's you know working on still working on cool crypto stuff it's not used in Bitcoin or any currency actually that well any currently operating cryptocurrency because they the signatures and keys are a bit larger than the later systems will see smaller than the hash based things but still a bit larger was used in cha me and blinded cash because you can do what blinded signatures where you say okay I'm gonna have you sign something for me and then after you give me the signature I can sort of pull apart the signature and you won't because you I'll have you sign something that you don't know what you're signing right I'm gonna like mask this message and blind it so that you sign the message and then I can get your signature on the real message without you knowing what you signed so basically the idea is well I actually have you know message prime equals message plus randomness and I say hey can you sign em Prime and you say okay I produce a signature on M Prime with my you know private key and we'll call that s Prime and then what I can do is I can sort of s equals s prime minus the randomness or really some function of that randomness and now I have a signature and this is a valid signature on em so that's kind of cool it's like hey can you sign this message for me and I'm not gonna tell you what you're signing and then it seems sort of useless like why would I sign something I have no idea what I'm saying but it can be used in that that Chou Mian blinded cache because I then have a proof that well this bank didn't know what they were signing but they they signed this and this is their signature and they gave it to me and I can use that as like a thing to represent money that there's all sorts of cool things you can do with this um the basic setup of RSA is make two prime numbers P and Q and then compute n which is the product P times Q so this seems fairly straightforward right it's not too hard everyone knows the prime numbers are now you have this composite number P times Q what how do I like make a leading question for the next slide does this have any relation to things we've looked at like does this look this doesn't look at all like a hash function right but are there any properties similar to a hash function here yeah yeah it's a one-way function in that if I know if he and Q I can compute n right but given n I can't necessarily find P and Q right if they're small sure I just sort of check and there's all sorts of algorithms to find factors but if P and Q are pretty big like hundreds of bits long thousands of bits long finding it may be impractical whereas if P and Q are really long finding the product of both of them will be very practical even if even if huge multiplying two integers is like really easy so this is a one-way function but not a hash function and so a lot of these signature systems use one-way functions but trickier one-way functions that aren't hash functions and still have things that you like cool things that you can do so I'm not gonna go into RSA in super detail I'm going to sort of like run through it really quick and you'll be like huh how does that work but if you think it's interesting you can look it up and then maybe go to C cell and ask Ron how it works although maybe try to look it up first he's probably explained it a lot of times and but it has different properties so you could say I'm gonna use this P times Q equals n as like a hash function and make a Lamport signature out of it where my private key is a whole bunch of P and Q pairs and my public key is a whole bunch of ends and I reveal them and stuff you could do that that would work but you can do much more powerful things because of the mathematical properties of these things so yeah I'm just gonna go through it really fast cos but if you think it's you know if you if you know anything that's kind of cool the idea is you can do a bunch of multiplication and exponentiation modulo n and so because n is like almost prime there's some interesting properties where if you know the factors of n you have these shortcuts you can do and if someone who doesn't know the factors of n can't do these shortcuts so you publish E which is a constant this is sort of a parameter system usually today so RSA is used today all over the place if you're on if your computer is open and you've been using the web in the last five seconds your computer has performed RSA calculations every time you connect to a website you're doing RSA so generally at six five five three seven they just make this up you can do also use three some small number and then D is a number that you can compute if you know what P and Q are so this is sort of the private key right P and Q itself can be seen as the private key but you can actually compute this demon number and then discard P and Q and then yeah so this is how you compute D or whatever but the idea is n is their public key and D is your private key E is always the same and P and Q you can discard afterwards and then what you can do and this is like not going to get into it but you can say okay my signature s is message right I can take the hash and make a message message to the D power modulo N and if I verify if I take that signature to the e power modulo n it should equal M again which is like crazy and kind of awesome because the idea is to sign okay I just raised to the D power mod n it's gonna be some some number on you know the same size as n right and then I give that to someone they take that signature to the six hundred you know six five five three seven power modulo and again and see if n comes back out em the message comes back out and if it does they know I signed and I have the private key the private key that corresponds to n now this the cool thing is I can use this any number of times I can use it the same thing a bazillion times with different M's and that doesn't give any help on to how to factor n or how to compute D so this was you know late 70s also RSA and sort of one of the first like hey we you know we can do better than hash functions it sort of was developed at around the same time as hash based signatures all of these things were sort of coming out of the same time you can do lots of cool stuff because there's like these properties where we can you know make em you know M prime plus m and like take the exponentiation of all that and still it works ok so that's really cool you can do lots of cool stuff but this is also not used in Bitcoin one of the things that sighs Sookie sizes are smaller than then with Lamport signatures and they're often about two kilobits or 256 bytes which is fine and that's about the same size as signatures so if you use your like web browser secure well how secure certificate valid no this browser might not show me okay anyway well in Firefox that tells you more okay well anyway anyway anyway but yeah you there's RSA keys in basically every certificate for web browsers and websites and they're generally 2048 bits long that scene is like pretty secure that's like you know even a thousand four thousand twenty four bits has not been hacked but people think it probably could be by a very motivated actor so this is decent size one thing about RSA is that it's a little tricky to implement right there's a whole bunch of weird math there it's not like the Lamport signatures where it's like okay I have a hash function use it right it's it's kind of hard to shoot yourself in the foot with the Lamport signature scheme you can write but it's sort of obvious if you do so like if you're doing the homework and it just like doesn't work at all and you're like oh I was hashing twice or oh I was like reversing the order or you know things that were like it it it just didn't work but there's no like subtle ways where like oh I was off by one and now it reveals all my private keys that's hard to do whereas an RSA it's actually quite easy if if your P and Q values for example what's it what's a really crazy gotcha if P or Q minus one so if like P minus 1 or Q minus 1 is smooth essentially a number that's highly composite has many small factors you can find someone's private key you can factor it so it's not just that P and Q have to be prime P minus 1 and Q minus 1 have to be not two unprimed not like it can't be like a power of two or something otherwise you can lose your project so there's all sorts of like you know crazy things that happen with RSA Bitcoin and other coins use elliptic curve signatures which I'll talk about next that have our sort of displacing RSA in many cases so it hasn't really taken off for for like web certificates but a lot of other types of encryption signing things like that like crypto currencies are also one of the big uses of elliptic curve signatures because they're somewhat more powerful and somewhat smaller and really cool and we will talk about those in three minutes so intermission three minutes stretch ask random questions talk to the neighbors okay so they're using these elliptic curves which are curves of the form y squared plus X cubed plus X some coefficient x squared plus some constant and in the case of Bitcoin it's very simple it's y squared equals x cubed plus seven and that's the curve bitcoin uses and this is what it looks like if you plot it and that seems really simple like we can totally understand that but it gets a little weird with elliptic curves you have these points on the curves right and another property is if you draw a straight line that intersects this curve you could also draw a line which doesn't intersect at all fine but if you draw a line that intersects the curve it will intersect in three places so if I draw a line here it intersects these three dots if I draw a line here and intersects here here and then it'll intersect somewhere down here it'll intersect in three places unless I take a tangent if I draw and I like try to be like oh I'm gonna only intersect in two well I can take a tangent here and it'll intersect in one more place what we can do those we can say well if you intersect at a tangent that's kind of like intersecting twice or you know we can we can deal with that if you draw a vertical oh yeah vertical line then there's like a point at infinity which shouldn't happen yeah yeah it there's a point up there sort of it in the practice of signing and stuff you probably shouldn't hit it like if you yeah but so what we do is we say okay well three points in a line equals zero and so if we take this point plus this point plus this point that's zero another way to say that is P plus Q minus R equals 0 or P plus Q equals negative R and another property is the negation of a point is just that same point with the you know y-coordinate flipped so this is you know if this is negative R we just go down to the bottom side of this and this is positive R similarly you know minus P would be here minus Q would be here and if you had a point you know Z here negative Z would be up here this is how it's constructed however we don't actually use these nice curves we sort of chop them up and modulo something yeah no in this case are as I hit right P in this case P wait hold on people speak equals R right sorry okay normally yeah the this picture is correct but so basically P plus Q equals R because R is down here sorry yeah that's why okay this is our this is negative R so so yeah people ask you equals negative if equals are not negative R sorry when you want to multiply a point you can because you can take a tangent right so you can add these points right you can say okay I want the sum of P and Q which will be down here are I want to pee for example well with two P I can take a tangent and then find where it intersects and then go down below okay so for example if this is you know G I say okay well G starts here take the tangent find where it intersects and then drop down and this is to G so I can you know it's a simple way to say well I'm not I'm not really multiplying I'm just adding it to itself which is sort of what multiplication is and I can do this again and again so I say oh I want for G I take the tangent at to G find the intersection here drop down okay here's for G take the tangent here it'll go you know I can keep doing that and get to g4 g AG and if I want intermediate things like well I want three G well I'm draw a line between G and two G find the intersection and find the sum so what we yeah yes yeah yeah so so it looks I the pictures look nice in this case right it's like a this is this curve and it looks so simple and we can like graphically do it on graph paper but when you're actually doing it on the computer it looks more like this everything is modulo some giant prime number the you could still draw lines it's just that the curve is now all these crazy-looking dots and you still have that symmetry from the y-axis but the way the computer does it is all modulo number so you can't it doesn't actually map to a nice like curve however all the properties so the fun thing about when you're doing modulo is all the properties stay the same right like you can still do with with regular numbers you can still do addition multiplication and division all modulo some number and it still all works right so same with this you still have the same you know draw a line between P and Q and you get to here and then you flip over the y-axis and now this is R similarly you can like take a tangent although tangent is harder to visually see because there's no like obvious curve here but the equations work the same okay so you don't need to like know exactly why these things work or curves but we're gonna go through what you can do with these and what properties you have okay so we've now have we've defined these points on a curve and like how this curve works and then we also have regular old numbers right so a and well what we'll do from now on is say like a and B are lowercase numbers these are scalars scalars just means regular old numbers the upper case a and B will refer to points on the curve okay so from now on lower case is regular number upper case is point on this curve or point on this mashed-up thing that we still call a current okay so I'll go through what operations we can do and then we can see what use those that so first scalars you can add subtract multiply divide you can do ever you want right these are just regular numbers like five or 17 or 20 - everything is okay right easy everything here is integers we're doing modulo some big prime number so there's no decimal points you know you never have to use I think in this class we'll probably never have to use floating-point which is great because floating-point always scares me it's like it's also like you int these are like unsigned integers you can do it with sine but since you're modulo some big number it's like unsigned numbers that loop around so it's really nice for computers computers deal very well with these things computers are good at floating-point as well but the thing is in cryptography a lot of times floating-point ends up with error right where you're like pretty close but like you're you've got some you know fixed amount of decimal places you can store your floating-point goes out to some precision and then air can sort of accumulate and in a lot of cryptography you want zero error right like in a hash function it's pretty exact so in a lot of times the cryptography you you use integers instead of floating-point or rational numbers okay so with scalars these are just regular integers natural numbers even you can do these all the operations you're familiar with that's fairly straightforward with points so you can add and subtract the points right we showed how you sort of do that visually and then the equations for it the computer can do that pretty quick however these this is not defined multiplication and division with two points is undefined it's just not it's not clear how you do it like it's it's not something in this system right it's a group you've got one operation you don't have this other one so you can add them subtract points if you can't multiply them any questions about this this is a pretty important yeah make sense yes when you adding points what is defined as addition are you adding them either you use both the x and y coordinates to add right so right so when you're doing it in the computer saying okay well what are the x and y coordinates of P what are the x and y coordinates of Q draw you know find the slope find the slope here and the like where it intersects the axis and then see where it'll intersect the curve at another point you know but the equation would be like you don't the sense the computer doesn't actually look at the curve you just say okay find the PX and y coordinate find the Q X&Y coordinate like find the slope and then find where it intersects and then like you know compute for that Ferrar okay so yeah you can add and subtract you cannot multiply and divide these points sounds good any other questions you just go down right so if I want P minus Q I just say P plus negative Q and negative Q is just right here right down on the y axis so I say okay I want people ask you go here but it's gonna be up there somewhere so yeah you just add the negative of the number I guess that's another thing I you know B minus B like negative B is also an operation I can do I can negate something which lets me do subtraction okay natural numbers modulo and just some easy birthday curve so this is a and the only things to find is addition and subtraction or not right you can do the same group operations without using elliptic curves and so you can just do exponentiation modulo a big prime number I'm gonna use curves because it's what is used in all the actual systems and it's but but you you can sort of forget about the curve after this right if you say well look we just have these uppercase numbers and these you know these uppercase variables and these lowercase variables and the fact that it's on a curve we can sort of abstract away and just know that we have these different types essentially and when you do when you're in the computer you're just like yeah that's the point that's a scalar here are the operations I can do and I just run the functions okay so the next part when you mix scalars and points so mixed operations you cannot add a point and an integer or subtract a point in an integer like that's not defined right you say okay here's this point P minus seven like well does that mean move the x axis does that move do y like it's not defined however you can do this right you can multiply and divide so you can say well a times two what you know you take the tangent right it's just a plus a or a times seven is we just break it out as a plus a plus a plus a 17 times we can also divide which is a little weird because we have to find the the sort of like inverse of B and then multiply by that like the multiplicative inverse of B modulo the the order but anyway you can do these this is a little trickier because you have to compute what sort of like B to the negative one is and multiply by that you can do it so you can do these things where you have points times scalars but you cannot have yep yep to it so that was here you know if this is G this is to G find the tangent find the intersection and then the gate okay so you can do you can do that that's cool you cannot do that okay so roster of operations we can do this is it and this is sort of if you think of that you can do all these cool things it's sort of amazing all the crazy things you can do with just these operations right with regular numbers you can do whatever you want that's obvious and with these points you can add them subtract them and when you mix you can multiply and divide and that's it okay any questions so far you don't you don't have to worry too much about the curves and all the math and stuff but you just sort of say okay here's my sort of toolbox here's what I can do okay any questions good so now what we can do is we can define a one way function sort of like a hash function sort of like multiplying P times Q to get n what we will need in addition to this is everyone picks some point on the curve and we call it G and it's random and we want it to be somewhat verifiably random we just all have to agree on a point and we'll call this the generator point another property is that if you keep since it's all modulo this number if B is too big you'll sort of wrap around right because it's all modulo let's like n so it's called the generator point because and every point on the curve can be one if you keep you know say 2g 3G 4G 5g eventually you'll get back to G right it's all finite okay so does anyone have an idea okay how would we make some cool one-way function given these operations and the fact that we have an agreed upon point it's not super obvious but it's actually fairly straightforward once you see it any ideas yeah scaler yep yep okay so your private key let's say you private private key lowercase a it's just some 256 bit random number scaler exactly the same as you know it's 32 bytes like in a LAN port signature and your public key is just eight times G and your public key is now a point on a curve we're gonna call it uppercase a and you have a 32 by x-coordinate right because the the x dimension is 256 bits 32 byte y-coordinate so it's 64 bytes pretty small anyone have a another quick optimization on how you could reduce this so like there's a lot of optimization going on in like all these different cryptocurrency systems because they don't scale too well but any idea of how to get that down you could so you can hash it keep making them 32 bytes there's a cooler there's a more sort of useful way because but if you hash it you still have to reveal it later right so like it helps making a funky hash and that's that's what Bitcoin did initially is you'd have the 64 byte public keys and then you'd sent to the hash and then there's a nicer way any ideas okay so the thing is its symmetric right so the curve is symmetric about the y axis or sorry x axis any ideas and then let them figure out exactly where it is right so you can encode the x coordinate only and one bit for Y and then you're down to 33 bytes it's a little annoying because the 33 bytes well one of those bytes is gonna be like empty they're just gonna have one bit in it for like up or down but whatever um so you can do that and that's also really cool okay any questions so far probably but I don't think would be smaller I think you'd have to probably have the same size if you use some other coordinate system I haven't eivin yeah you could sort of encode a slope and you say it intersects and it's at the slope and which side of the axis you probably could I think it would end up the same size but yeah then but it might be faster for some things there's all sorts of different encoding yeah so you might not be on the curve but there's a similar problem here where it might not be on the curve you can encode a point that's also off the curve and so when you actually get a public key like over the wire in these systems the first thing you usually do is make sure like this is a valid public key and it's actually on the curve because there's a lot of points that aren't and sometimes you can screw around with the code that way yeah okay so scalar multiplication a times G is basically break it out as G Plus G Plus G Plus G Plus G a times and G Plus G is find the tangent of G and then find the intersection right so this is G this is to G right tangent intersect and then go to the negation and so you just do that a bazillion times however since you can find two G and then you can double to G to get for G and double for G to get a chi you can come up with like powers of two of G and then add those powers of two to do a much more efficient addition so that you can practically make you know his little a is gonna be some huge you know 50 digit you know decimal 50 digit number or whatever so you're gonna have to do this like sort of two four six eight binary expansion and then add them all up okay so yeah if you're chucking everything into into some green says to get to get these your district I think opinions curve yes it feels like you do a 32-bit you use basically originally you should be able to get all the way down to 32 bits yeah or you can do some a little what you can do is you can just say look I'm only going to allow public keys that are on the top you know on the positive have positive Y component and everything else is disallowed you could you could have that as like a rule of your system and then you can get rid of the Y bit but the thing is some of the things do you know the y coordinate does affect some of the things like signatures things that you'll later use so you can just say okay look implicitly Y bit is positive and you you lose them like one bit of security because there is a difference between the positive and negative thing if you're doing signing oh but yeah it's it's so some systems do do that and makes things easier there's some signing systems that do that okay I'm gonna go to the next part there's ECDSA is used in Bitcoin I'm actually not going to explain it it's a worse signature system so the reason why this was used was the better system was patented and so there's a clearer sort of more like obvious cleaner more powerful signature system that was patented by this german guy Klaus noir and so no one used it or maybe a few people used it but in general with like open-source things and and like web standards patents are sort of really hard to work with and so all the cryptographers said well we'll make this other system that's different enough that it doesn't infringe on the patent and it's kind of ugly it does work as a signature scheme but actually I'm going to explain the Schnoor signatures which make a lot more sense are easier to understand and manipulate and the patent has expired so we can all use it and it will probably be going into Bitcoin and some some cryptocurrencies use our signatures I think Manero uses a snore like signature but Bitcoin will probably be it will be they'll be putting it into a Bitcoin in the next year or so so all these things will be much more applicable and you can use them and you can and there's code out you can use them now okay yeah sorry patent expired free to use the better I'll go that must not be named so yeah we're maybe not like people don't call it Schnoor signature as much because it's like well this is the guy who prevented us from using this for 20 years and like and and there's modifications to it okay so the elliptic curve signature for lack of a better name and this is something of a simplification and there's like reading about how you can really do it the right way but this does give you the right idea and for a single signer this is also this is secure and it works but later things you might want to actually adds other stuff so the idea is you've got your message M right same as in Lamport same as in RSA you've got a message m in a private key lowercase a and your public key is a times G like we said and then when you want to sign you actually make a one-time use key pair for the signature only and they usually call that K and K is a new random number it's the private key and you're gonna multiply it by G and so R is sort and they call this R I don't know why they use these letters but anyway K times G is our R is sort of the other public key you're using just for this signature and then the signature itself is quite straightforward as the signer you compute S which is K this new private key you just made up - the hash of your message concatenated with are this public key so you encode the public key and 33 bytes stick it in there multiplied by a your your you normal private key and then your signature is the pair the R point and the S scalar this is you know a little bit of a bunch of the process but it's actually not too bad right this is scalar 32 bytes you made up the hash when you you know this is a message also gonna be however long this is 33 bytes you concatenate them together hash you end up with another 32 byte scalar you multiply those two scalars so actually there's no the only elliptic curve operation here is calculating what are s when you're actually calculating s this is all just scalar so it's very fast so in terms of practical computer stuff doing these operations is a little bit on the slow side because you're doing those point additions quite a number of times so come so a decent code can and like a decent CPU can do 10 like foul on the order of thousands of these types of operations per second which is decent you know like you can do a decent amount but it is kind of slow and it's it's considerably slower than hash functions you can do you know a million iterations of hash function for a second on a core or you can do maybe a thousand or two thousand of this kind of thing so still pretty fast but slower and so this signing procedure this takes a bit of time this takes actually very little time because you're just subtracting and multiplying scalar you know 32 bytes scalar integers which is much faster ok so does this make sense we'll go a little bit about how you can't Forge this okay sorry first verification sorry so how would you if anyone knows how I can think about how would you verify this right I know I know their public key capital a which is a you know a little a times G and then they're giving me a message m and they're giving me a signature which is R and s and they've computed it this way I can't verify this equation myself because I don't know what K is I don't know what little a is right I'm just given R s M and so how would I verify this so the basic idea yeah you're right multiply this side by G then you also have to multiply the other side by G right so you say okay well I'm gonna multiply it I I'm as the verifier I've got our got s I multiply F by G and now I have to multiply this side by G and what will that look like well what's K times G all right what's little a times G big a so so yeah I want to verify I want to verify this that this equation was used right s equals K minus this hash times little a multiply both sides by G I get s times G equals to K times G minus the hash thing times little a times G this is big a this is our hey now I know everything here as the verifier right I know what s time she is I know what R is I know what big a is I know what's going into this hash function and so I just say okay well you know I rearranged it a little and say is R equal to this and if it is that's a good signature if it's not it's not a good signature any questions about this is this make sense mostly so for the verification there's a bit it's a bit more CPU intense right you're you're given a scaler you multiply by G you're also you also have to multiply a this is actually more costly you have to multiply a by this hash the reason that's more costly it's still a scalar times a point the thing is since G is used for multiplying a lot you pre compute all sorts of coefficients times G and you store them like in RAM or in your like CPU somewhere so so multiplying by G is a little bit faster because you you do it a lot you can pre-compute a lot whereas multiplying by a is different each time for all the different signatures so this is a little bit slower in general so it's a little bit it takes a little bit more CPU time to verify a signature than to create one something like twice as much but still you can do this pretty fast on a modern computer you can do thousands of these a second okay any questions so far and I'll go a little bit into why this is not for Jim all right so I want to forge a signature well why don't I make up a kit you know I don't know little a but why don't I make up a K and compute SNR but I need a right so I'm gonna say okay I this is the equation I want I'll just make up my own K and make up my own K s that solved that you know that's the satisfy this without a I really can't make a valid s right I can make something up here but I can't compute it cuz I don't know here right I can try keep I can try to grind through hash functions but it won't work the basic problem is if I make up an S and solve for R right I can say well I know what R is but the thing is are is in the hash function as well it's the it's the one-wayness of the hash function that actually breaks this right so let me solve for R well R is the hash of M our times a plus s times G if I can come you know if I can come up with a random with a valid are here I can do this the problem is R is defined by the hash of R in this case I can't compute this and I can't cancel this out right so if you can see this like okay I need to solve for R well but it's already in here like I'm stuck if I don't know K I can't come up with a signature either one okay there is one sort of foot gun with EC signatures if you use the same R value for different signatures with the same pump key you reveal your private key so K has to be random and new every time I you you mean that if you if you look through the question you'll see how you can solve if you know if you have to live the same case with differences you can solve for K and then once you solve for K given given this if you know what K is you can find what little a is right as a verifier you can say well I know you you gave me s that's part of the signature I know this whole coefficient if I know K I can solve for a little a by dividing this out so always use a new K value there have been many cases where people don't probably the most famous one is Playstation 3 used ECDSA and they used a fixed K value for signing all their code and that allowed people to calculate their private keys and then run pirated games that was actually the first time I learned it occurs like 2010 or sup so actually there's there's kind of interesting tutorials written by like the hackers who broke a Playstation 3 about how this works and that's what I first write about it okay we're almost out of time any questions about this stuff so far okay so other so this is this is a signature algorithm it's like okay fine this works I can sign same as Lamport signatures same as RSA what's really nice about the elliptic curve stuff is you can do more than just signatures there's all sorts of fun things you can do and it seems like a fairly unexplored area in that like I've found fun things that you can do that are you guess our novel and like I don't I'm not an expert on this at all it's just that it's a fairly new area of research and like how to do cool Bitcoin e cryptocurrency things with these curves and points and stuff so I'll go through a couple fun things you can do fun with points okay so I'm not using an asterisk so I'm just you know B times G so let's say Alice has a public key a Bob has a public key B right which is little a times G or little B times G well this is weird little a times big B Alice's private key multiplied by Bob's public key you can do that right is equal to Bob's private key times Alice's public key right it's commutative the multiplication is commutative that's weird right it's just a times G times B which is the same or you know it doesn't matter the order it's the same as B times G times a which is the same as a times B times G and let's call that C see this is called the diffie-hellman key exchange point Diffie and Hellman are two also like late 70s PhD students who came up with all this cool stuff no wait if he was a PhD student Hellman was his advisor I don't remember anyway they came up with this idea and this is this is like a shared point what would this be useful for it's actually super useful and can you think of like oh okay we can do this we can compute C why would we want to do that like any applications you can think of yeah yeah it's really cool to share keys so this is also done if you have a web browser I think it's all looked a curve diffie-hellman now mostly but if you have a web browser and you go to a website this is happening basically for every HTTP request because you can use see as they sort of shared key and encrypt things with it the idea is a can be public big a can be public big beep can be public point C will not be public the only way to compute it is to know either a is private you know Alice's private key little a or Bob's private key little B even though you can see you can see the public keys you can't compute C by from just the public keys right because big a times big B that's not defined and that would that wouldn't even be that like you can't multiply the points you have to multiply the point by a scalar and since you don't know the scalars from viewing this exchange you can't compute C but Alice and Bob can both compute C so this is really useful you can compute C you can use it for encryption you can use it to prove you are who you say you are you can use it as like an interactive verification where you say okay I'm gonna I'm Bob I'm gonna make a random point I'm gonna give that to you prove you know your private key little a by telling me what C is right so I can I can I can make like a random key here give it to you you return see I verify that that's the right C I say okay well you must know little a you haven't shown me little a but I even that you know it so proof of knowledge of the private key so you can use that for like logins instead of passwords and it's like much simpler than a signature so that's really cool all sorts of things you can do with that the last part you can have fun with points and I use this in my software so you say ok well there's a public key a there's a public key B and well we'll define D as the sum of these two public keys the thing is if it's if you're selling these two public keys it's community it's the same as saying the sum of the two private keys times G right a times G Plus B times G is the same as a plus B times G which is another really cool property so what if I compute this prior to this public key D and I say I want a signature from public key D you can and you saw the private key little D which can sign for this is just little a plus a little B so you can make a combined key and then either party you know Alice has a little a Bob has little B and they could reveal it to each other and allow the other person to make a signature with D later this is this is yet like I use this in the lightening up network software I've had where basically you say look we'll compute D and like I can give you the private key right I know I'm you know I'm Bob and I say okay here's here's point be yours point a we add them together and then Alice I if I give you my private key now you can sign but I can't write so I'll like sort of give you the private key to D from some information I have or you could give me the private key to D by sharing a little a with me so this is another useful thing where you can have something where both parties know that neither party can sign unless they give them something and you can use that for like Bitcoin addresses things like that this is like sort of before you even get to signatures you can share keys and stuff there's a there's all sorts of super fun things you can do with these points and curves and systems multi signatures is like the the reading I put a link to a PDF file it's like very recent and like kind of overkill and like over my head as well but you can do signatures where you a great the signatures but there's ways to sort of say okay well I'm gonna add all these are points and I'm gonna add all these s points and I can have signatures that are from a bunch of different people that collapse into the same size as a single signature and I can verify that they're all signing the same thing or possibly that they're all signing different things so I have you know ten different signatures from different people signing different messages but I can add up all the s values I have to keep the R values but now these ten signatures instead of being 64 bytes each are more like 32 bytes each and there's one extra 32 byte value for all of them so there's a lot of really cool ways you can like combine things make things smaller make things really versatile where we can share keys things like that which you can't do with hash based signatures hash functions and so it's really fun one worry is that if quantum computers ever become really a thing all this stuff stops working all the elliptic curve stuff doesn't work anymore you can you can figure out what people's private keys are whereas hash stuff hash things like limp or signatures still work so there's some some talk of like hey we should sort of prepare for if that ever happens and make you know efficient effective hash based signatures and use them in something like Bitcoin or aetherium people haven't yet because the overhead is really high it's really big but and it's the the real thing is all these fun things might disappear in the next 10 20 years who knows but there's lots of cool stuff what do we do with this so we we're not gonna do anything yep in terms of problem sets it's a little hard to program it directly but there's libraries and the libraries have fairly easy use where it's like you know x G is a function and like x this point as a function so this is ground worth for cool stuff you can do and it's really nice because it's a new area and like I'm not an expert on this but I've come up with stuff that I don't know people have sighted me on and they're like yeah I guess no one thought of that before there's a lot of things there's one very recent one called taproot where it's like one line you're like oh yeah that works and it's just these sort of elliptic curve operations it's like yeah that works that's really useful how did it know one thing is that like it's one line like wow so there's just not a ton of people working on this kind of stuff and so it's kind of fun