Placeholder Image

字幕列表 影片播放

  • 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.

  • TADGE DRYJA: Today, I'm going to talk

  • about signatures and all sorts of different signature

  • kind of things.

  • In the problem set, 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.

  • OK.

  • 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.

  • 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-- yeah?

  • AUDIENCE: You can only use it once.

  • TADGE DRYJA: Yeah.

  • OK.

  • So plus.

  • This is hashes.

  • That's cool.

  • One-time use.

  • Other possible disadvantages of them relative to other systems,

  • if you're aware.

  • Another is they're kind of huge, kind of big, right?

  • You can deal with it.

  • But if you were looking in the forge,

  • or that file with the signatures,

  • it's like, what, 8K for a signature--

  • 8 kilobytes-- kind of big.

  • Keys are 16 kilobytes--

  • kind of annoying.

  • Private keys are also 16 kilobytes.

  • So yes, sig 8K, 16K priv/pub key.

  • So that's some disadvantages.

  • So since I don't have slides, I'm

  • gonna make this more fun and interactive.

  • What are some solutions for these problems?

  • So we can actually mitigate/solve

  • both of these things to a 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 don't think the answer is too stupid.

  • It may be a fairly stupid answer, and it might work.

  • So yeah?

  • AUDIENCE: Not actually revealing pieces of your private key?

  • Instead, reveal something else.

  • TADGE DRYJA: There's probably some clever way.

  • But that might be too clever.

  • Something really simple for, OK, I can only use a key once.

  • How can I use a "key," quote unquote, more than once?

  • Yeah?

  • AUDIENCE: Make another one.

  • TADGE DRYJA: Yeah.

  • You can make another key.

  • So you could say, well, I've got this 16 kilobyte public key.

  • Well, I'm going to make a 32 kilobyte public key.

  • And it's just two public keys stuck together.

  • 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 key,

  • and you say, OK, well, it starts with a zero,

  • so that means it's using the first key, the first subkey

  • in this 32 byte public key block.

  • And in this case, it's using one,

  • so that means it's using the latter subkey.

  • So that would work.

  • That would let you use your public key twice,

  • at the cost of doubling your public key size, which

  • is not really great, right?

  • And it's not very efficient.

  • But it does sort of work.

  • OK.

  • Any clever ways to do it more efficiently?

  • Or wait.

  • So OK, also, I'll give you sort of a hint.

  • In this case, let's say this is pub sub 0 and pub sub 1, right?

  • And then, your 32 byte pubkey is just them

  • concatenated together, right--

  • pub0, pub1.

  • What would happen to the private keys in this case, right?

  • How would private keys work here?

  • Same expansion of size, I guess.

  • Can anyone think of a way to mitigate the expansion of size

  • of private keys in this case?

  • So the private keys are the preimages here, right?

  • They lead into these public key blocks.

  • So you could just say, OK, well, I

  • have twice the size private key leading into twice the size

  • public key.

  • Could you do that more efficiently?

  • Yeah?

  • AUDIENCE: Could you just hash the private key

  • so that you have two hashes instead of one?

  • TADGE DRYJA: Yes.

  • So let's say you have this 16k block,

  • and you want this to turn into two public key.

  • So that's the basic good way to do it.

  • And it sort of turns in like that.

  • How exactly-- what's the way you do that?

  • AUDIENCE: You can keep the same private key as before

  • and just add something like zero or one to indicate--

  • TADGE DRYJA: Yeah.

  • So this is a hash function, right?

  • And so before, we just said, OK, hash of this is block 0,

  • this is block 1, this is block 2.

  • So the idea of pub--

  • let's see.

  • Is this visible?

  • This might be too small, right?

  • AUDIENCE: Yes.

  • TADGE DRYJA: Yes, OK.

  • Let me make this bigger.

  • Sorry.

  • OK.

  • So in these diagrams, you've got 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.

  • So we say, OK, pub2--

  • and this is public, this is private, and, let's say,

  • secret--

  • pub2 is just the hash of secret2, right?

  • But yeah.

  • What we could do is we could sort of have two different hash

  • functions.

  • And then a real simple way to make

  • a whole bunch of different hash functions

  • is we define, OK, well hash0 is defined

  • as the hash function of whatever your input x is concatenated

  • with the number 0.

  • And then hash1, we define as just x comma 1 and so on.

  • And this is actually secure.

  • You could do this.

  • Any questions or possible objections?

  • AUDIENCE: I was thinking that if someone knew the hash function

  • you're using, wouldn't they only define

  • x because they know that it won't help with [INAUDIBLE] x.

  • [INAUDIBLE]

  • TADGE DRYJA: Yes.

  • Yes.

  • So there's no real entropy or secrets in this 0 and 1.

  • But it's purely riding on x, right?

  • But the idea is, well, if I do this,

  • and I say, OK, well pub2 is the hash

  • of secret2 concatenated with 0, yeah, if you know secret2,

  • you can go back.

  • Because 0 is obvious.

  • But the idea is if you don't know secret2, the fact that you

  • know the last byte of the hash input doesn't really help you.

  • Because there's all this data that you don't know.

  • And so you're not going to be able to find a preimage.

  • You're like, OK, I know the preimage

  • to public2 ends with a 0 byte.

  • What are the other 32 bytes that come before that?

  • You still can't go back to make a preimage.

  • AUDIENCE: But it feels like there's some sort of--

  • what's the word-- you'd make a similar statement saying, oh,

  • if the last byte is not important,

  • then the second-to-last byte is not important, either, right?

  • TADGE DRYJA: So the attack is I've got pub2,

  • 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 going to be, let's say, 33 bytes,

  • and the last byte is a 0.

  • And this is going to be some random numbers

  • all the way back.

  • So I have some insight into what the preimage is.

  • I know the last byte is a 0.

  • But that doesn't help because I don't

  • know all the bytes before that.

  • So I can't really do--

  • I can't sign because I need to be able to reveal

  • all these things.

  • And the way the hash functions, 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 looks really random.

  • And adding stuff to the end here shouldn't reveal anything.

  • There are hash functions where this can be dangerous,

  • and you can consider those like broken hash functions, where

  • if I concatenate a lot of known data at the end,

  • it might give me properties of the public key that I can find.

  • [INAUDIBLE],, as far as we know, it works fine.

  • Most of the hash functions work fine this way.

  • So yeah, you can do this.

  • And then you can say, OK, well, I'm

  • going to use hash function 0 to make pubkey 0, right?

  • This is pubkey 0.

  • And if I use hash function 1, I make pubkey 1.

  • Now I have a 16 kilobyte-- let me erase this--

  • so now what I can do is I can say, OK, well,

  • I have a 16 kilobyte secret key, private key,

  • but I have a 32 kilobyte public key

  • that I can use twice that has two subkeys

  • 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.

  • Any ideas?

  • Yeah.

  • Well, 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

  • going to be able to find the preimage, right?

  • So maybe add some more stuff here.

  • Any idea?

  • Oh, yeah?

  • AUDIENCE: Could you hash the index?

  • TADGE DRYJA: Right.

  • Right.

  • So instead of just saying 0 and 1,

  • we can say here, well, why not just have one chunk?

  • And there's one chunk, and it's got random number x.

  • Well, this is hash x comma 0.

  • This is hash x comma 1.

  • This is hash x comma 2.

  • OK.

  • So yeah.

  • So what you can do is you can--

  • this was before, right, where I said, OK, 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, OK, 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 0, x comma 1, x comma a million.

  • I can give you millions of them.

  • And 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, OK, the private key problem is solved.

  • I have 0 of 1 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 keys, though.

  • Let's say I want to sign four times.

  • OK.

  • Well, I make a 64 kilobyte pubkey.

  • Now I can sign four times.

  • Great.

  • But my public key size expands with the number of signatures

  • I ever want to do.

  • Any ideas on how you could mitigate that

  • or how you could still make a usable system,

  • despite this fact?

  • There's a couple different techniques.

  • Any ideas?

  • OK.

  • So one would be every time I sign,

  • I also sign my next pubkey.

  • You can do that.

  • It's got some downsides, right?

  • So the idea is I first publish one 16 kilobyte pubkey.

  • And then I say, OK, when I sign, I'm going to sign my message.

  • And concatenated to that message will be my next pubkey.

  • And so I'm signing something and also indicating

  • what my next public key will be that I sign 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 going to need to look at all of my previous signatures,

  • right?

  • So if I'm saying, hey, here's my 500th public key

  • that I'm signing with, here's the message,

  • you're going to have to go back and look at my entire history

  • of signing, which is not great.

  • OK.

  • So other ideas of how to deal with large pubkeys?

  • What's a 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?

  • [LAUGHING]

  • In fact, it's the only thing we've

  • been talking about so far.

  • So what would you do to make your public keys smaller?

  • AUDIENCE: Hash.

  • TADGE DRYJA: Hash them.

  • Right.

  • OK.

  • So you say, well, yeah, 32 byte pubkey.

  • Well, you just commit to the pubkey

  • with the hash of the whole thing, right?

  • And I say, well, I've got my 16 kilobyte by pubkey.

  • I just hash it, right?

  • And now I have a 32 byte public key.

  • And I've committed.

  • 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.

  • I need to provide this whole 16 original pubkey,

  • original version pubkey, after when I sign.

  • So now my signature goes from 8K to, what, 24K.

  • So I haven't really made it more efficient, right,

  • in that the total thing with public keys and signatures

  • stays the same size--

  • actually, slightly larger.

  • But this is kind of a game.

  • Because the public key, it might be

  • like I'm showing it to you beforehand,

  • and we're space-constrained there.

  • And then, when I'm doing the signature,

  • I have more space or time or something like that.

  • So this is actually useful.

  • And actually, this technique is used

  • in Bitcoin and all different cryptocurrencies,

  • where you can call this a pubkey hash--

  • pubkey hash, or they say PKH.

  • And the main benefit is size, right?

  • You could say, well, if I've got a really big pubkey,

  • I can commit to it by sending to the hash of the pubkey.

  • And then, when I later want to sign,

  • I reveal the actual pubkey.

  • You can do it that way.

  • OK.

  • So then this is pretty cool, right?

  • We've now taken our system, which had fairly large--

  • 16 kilobyte-- private keys, turned them

  • into 32 byte private keys.

  • Great.

  • And also, this is 0 of 1-- never expands.

  • Awesome.

  • We've taken a system with large, potentially 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 one of these things,

  • where we make a bunch of public keys

  • and commit to them at the outset.

  • So you say, OK, I've got a 64 kilobyte pubkey.

  • 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--

  • 72, right?

  • The signature would be 72 kilobytes--

  • kind of huge.

  • So I can add a bunch of keys, but I'm just

  • sort of pushing the problem somewhere else--

  • into the signature, right?

  • There's a better way to commit to 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 it on the spot,

  • and it'd be like, wow, you should have gotten

  • this stuff named after you.

  • Any idea?

  • OK.

  • So what you can do--

  • 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 pubkeys,

  • stick them all in a row, take the hash of that whole thing

  • and publish that as my public hash,

  • I'm going to have a little bit more complex design.

  • And that design is a binary tree.

  • OK.

  • So the idea is here are my four public keys that take up 64K

  • each.

  • I can make these intermediate hashes.

  • So I make a binary tree where I say, OK, 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 my root, which is

  • equivalent to my pubkey hash.

  • And so I can publish this, and it commits me to all four

  • of my public keys.

  • So it might not be obvious.

  • Do you see any advantages that this

  • could have over just concatenating all four

  • of the keys and hashing it?

  • Yes?

  • AUDIENCE: I'm confused.

  • Where is your private key in this?

  • TADGE DRYJA: The private key is down here, right?

  • The private key is not shown.

  • But I have a private key.

  • It turns into these pubkeys.

  • 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

  • by concatenating different indices.

  • Yes?

  • AUDIENCE: You can do [INAUDIBLE] systems and log-in time instead

  • of linear time.

  • TADGE DRYJA: Yeah, exactly.

  • I can prove that, hey, this is public key 0, which

  • is in here, this root hash, and I don't have to reveal all four

  • in order to do it.

  • So yeah.

  • Did someone else have, probably, the same idea?

  • Yeah, OK.

  • OK.

  • So how are we going to do that?

  • You obviously know.

  • Anyone else?

  • Yeah.

  • AUDIENCE: So assuming you wanted the public key 0,

  • you would publish that and 1, and also hash of 2, 3.

  • TADGE DRYJA: Right, yeah.

  • And then you can prove up to the top.

  • So I have little colors.

  • So the idea is the verifier who's verifying the signature,

  • he already knows the root, right?

  • Because you've pre-published that as your public key,

  • as your public key root and your public key hash.

  • And then that verifier is provided

  • with public key 0 saying, hey, here's a signature.

  • Here's the message.

  • Here is public key 0.

  • So you've got both of these things.

  • Now, the prover needs to prove that public key 0 is

  • contained within the root.

  • And to do that, the only two things the prover needs to add

  • is pub1--

  • OK, so the prover says, here's public key 1.

  • That allows the verifier to compute this.

  • And then the prover says, hey, here's

  • hash 2, 3, which allows the verifier to compute the root

  • and then check that it's equal.

  • So yeah, you only need two extra hashes instead of all four.

  • So saves some space.

  • It doesn't save that much space when you only have four.

  • It saves a lot of space when you have 1,000, right?

  • So you can add 0 of n elements.

  • And the root stays the same size.

  • The root stays 32 bytes, regardless

  • of how many leaf nodes you have.

  • And you can prove an element with log n--

  • oh, those parentheses are wrong--

  • 0 log n intermediate hashes.

  • So if you have 1,000 keys, your root stays 32 bytes,

  • and your proofs are going to be not too, too big, right--

  • 320 bytes of overhead, which is a bunch smaller

  • than a signature, right?

  • So this is really cool.

  • And you can use this much more practically

  • than the raw lamport signatures that

  • were in the first problem set.

  • Because those, if you're just doing

  • one key and 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 kind of huge, right?

  • Your signatures are going to be a little over 8

  • kilobytes, which is OK, right?

  • Computers can deal with 8 kilobytes.

  • That's called a Merkle tree made by Ralph Merkle

  • in '76 or something.

  • And it was originally made for exactly that purpose.

  • Anyway, so these are called Merkle trees.

  • Ralph Merkle.

  • He doesn't really work on crypto now.

  • He works on biotech stuff now, I think.

  • Anyway.

  • But he's cool.

  • And he gets, like, everything named after him.

  • So you will see the word Merkle everywhere.

  • And it's, 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.

  • It's nothing that crazy.

  • But so there's all sorts of Merkle trees.

  • You can make a different thing.

  • It's used in Bitcoin.

  • It's used in a bunch of different cryptocurrencies.

  • Oh, cool.

  • It's a very powerful way to take a whole bunch

  • of different things and commit to them in one small thing.

  • OK.

  • 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 elliptic curve [INAUDIBLE] signatures, which

  • do different things and are not based on just hash functions.

  • So I'll talk about RSA for a few minutes,

  • and then we'll have a little break, like intermission.

  • And then we'll go into elliptic curve stuff.

  • OK.

  • So RSA was invented by locals.

  • The R is Ron--

  • no, I think the R stands for Rivest,

  • but Ron Rivest is at CSAIL, and he's still

  • working on cool crypto stuff.

  • It's not used in Bitcoin or any currency, actually--

  • well, any currently operating cryptocurrency.

  • Because the signatures and keys are

  • a bit larger than the later systems we'll see--

  • smaller than the hash-based things, but still a bit larger.

  • Was used in chaumian blinded cash.

  • Because you can do blinded signatures, where you say,

  • OK, I'm going to have you sign something for me,

  • and then after you give me the signature,

  • I can pull apart the signature.

  • Because I'll have you sign something

  • that you don't know what you're signing, right?

  • I'm going to 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 message prime equals message plus randomness.

  • And I say, hey, can you sign m prime?

  • And you say, OK.

  • I produce a signature on m prime with my private key.

  • And we'll call that s prime.

  • And then what I can do is I can 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 m.

  • So that's kind of cool.

  • It's like, hey, can you sign this message for me?

  • And we're not going to tell you what you're signing.

  • It seems sort of useless, like why would I

  • sign something I have no idea what I'm signing?

  • But it can be used in that chaumian blinded cash.

  • Because I then have a proof that, well, this bank didn't

  • know what they were signing, but they signed this,

  • and this is their signature, and they gave it to me.

  • And I can use that as a thing to represent money.

  • There's all sorts of cool things you can do with this.

  • 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 what prime numbers are.

  • Now you have this composite number, p times q.

  • How do I make a leading question for the next slide?

  • Does this have any relation to things that we've looked at?

  • This doesn't look at all like a hash function, right?

  • But are there any properties similar to a hash function

  • here?

  • Yeah?

  • AUDIENCE: It's hard to route the image.

  • It's hard to [INAUDIBLE].

  • TADGE DRYJA: Yeah.

  • It's a one-way function in that if I know p 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 check.

  • And there's all sorts of algorithms to find factors.

  • But if p and q are pretty big, like hundreds of bits long

  • or thousands of bits long, finding n

  • may be impractical, whereas if p and q are really long,

  • finding the product of both of them will be very practical.

  • Even if huge, multiplying two integers is 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 cool things that you can do.

  • So I'm not going to go into RSA in super detail.

  • I'm going to 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 you go to CSAIL and ask Ron

  • how it works, although maybe try to look it up first.

  • He's probably explained it a lot of times.

  • But it has different properties.

  • So you could say, I'm going to use this p times

  • q equals n as 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 n's, 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 going to go through it really fast.

  • But if you know anything, this is kind of cool.

  • The idea is you can do a bunch of multiplication

  • and exponential modulo n.

  • And so because n is almost prime,

  • there's some interesting properties,

  • where if you know the factors of n,

  • you have these shortcuts you can do.

  • And 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.

  • So RSA is used today all over the place.

  • 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, it's 65537.

  • They just make this up.

  • You could 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 d number

  • and then discard p and q.

  • And so this is how you compute d or whatever.

  • But the idea is n is your 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 not going to get into it-- but you can say, OK,

  • my signature s is message, right--

  • I can take the hash and make a message m--

  • 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 crazy and kind of awesome.

  • Because the idea is to sign, OK, I

  • just raised to the d power mod n.

  • It's going to be some number on the same size as n, right?

  • And then I give that to someone.

  • They take that signature to the 65537 power modulo

  • m again and see if m--

  • the message-- comes back out.

  • And if it does, they know I signed,

  • and I have the private key that corresponds to n.

  • Now, the cool thing is I can use this any number of times.

  • I can use the same thing a bazillion times

  • with different m's, and that doesn't give any help

  • on how to factor n or how to compute d.

  • So this was late 70s, also, RSA, and one of the first,

  • hey, we can do better than hash functions.

  • It was developed at around the same time

  • as hash-based signatures.

  • All of these things were sort of coming out at the same time.

  • You can do lots of cool stuff because there's

  • these properties where we can make m prime plus m

  • and take the exponentiation of all that, and it still 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 is the size.

  • So key sizes are smaller than with lamport signatures.

  • And they're often about 2 kilobits, or 256 bytes,

  • which is fine.

  • And that's the same size as signatures.

  • So if you use your web browser--

  • secure-- well, how secure?

  • Certificate, valid.

  • Oh, this browser might not show me.

  • OK, never mind.

  • AUDIENCE: In Firefox, it'll do it.

  • TADGE DRYJA: In Firefox, it tells you more.

  • OK.

  • Well, anyway, anyway, anyway.

  • But yeah, there's RSA keys in, basically, every certificate

  • for web browsers and websites.

  • And they're generally 2,048 bits long.

  • That's seen as pretty secure.

  • Even 1,024 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, OK, I have a hash function, use it, right?

  • It's kind of hard to shoot yourself

  • in the foot with the lamport signature scheme.

  • You can, right, but it's sort of obvious

  • if you do, so if you're doing the homework

  • and it just doesn't work at all, and you're like,

  • oh, I was hashing twice, or, oh, I was reversing the order,

  • or it just didn't work.

  • But there's no subtle ways where, oh, I was off by one,

  • and now it reveals all my private keys.

  • That's hard to do, whereas in RSA, it's actually quite easy.

  • If your p and q values, for example--

  • what's a really crazy gotcha--

  • if p or q minus 1-- so if 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 too unprime.

  • It can't be a power of two or something.

  • Otherwise, you can lose your privacy.

  • So there's all sorts of crazy things that happen with RSA.

  • Bitcoin and other coins use elliptic curve signatures,

  • which I'll talk about next, that are sort of displacing RSA,

  • in many cases.

  • So it hasn't really taken off for web certificates

  • but a lot of other types of encryption, signing, things

  • like that.

  • Cryptocurrencies 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.

  • OK.

  • So they're using these elliptic curves,

  • which are curves of the form y squared

  • plus x cubed plus 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 7.

  • And that's the curve Bitcoin uses.

  • And this is what it looks like if you plot it.

  • And that seems really simple.

  • 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, it 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 try to be like, oh, I'm

  • going only intersect in two, well, I

  • can take a tangent here, and it'll

  • intersect in one more place.

  • What we can do, though, is we can say, well,

  • if you intersect at a tangent, that's kind

  • of like intersecting twice.

  • We can deal with that.

  • AUDIENCE: What if you draw a vertical line?

  • TADGE DRYJA: If you draw a vertical-- oh, yeah, vertical

  • line, then there's a point at infinity,

  • which shouldn't happen.

  • AUDIENCE: But infinity is included--

  • TADGE DRYJA: Yeah.

  • AUDIENCE: --in the set of points on the curve?

  • So it's like there's three points, anyway.

  • TADGE DRYJA: Yeah.

  • There's a point up there--

  • sort of.

  • In the practice of signing and stuff,

  • you probably shouldn't hit it.

  • Yeah.

  • But so what we do is we say, OK, 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 y-coordinate flipped.

  • So if this is negative R, we just

  • go down to the bottom side of this,

  • and this is positive R. Similarly, minus P

  • would be here.

  • Minus Q would be here.

  • And if you had a point Z here, negative Z would be up here.

  • This is how it's constructed.

  • However, we don't actually use these nice curves.

  • We chop them up in modulo something.

  • Yeah?

  • AUDIENCE: You have P plus Q equals negative R. Should it

  • be positive R?

  • TADGE DRYJA: No.

  • In this case, R is up here.

  • Right.

  • In this case--

  • P. Wait, hold on.

  • [INTERPOSING VOICES]

  • TADGE DRYJA: Oh, shoot.

  • Sorry.

  • P plus Q equals R. Right.

  • Sorry.

  • OK.

  • Never mind.

  • Yeah.

  • The picture is correct.

  • But so basically, P plus Q equals R

  • because R is down here.

  • Sorry.

  • Yeah, that's why.

  • OK.

  • This is R. This is negative R. So yeah,

  • P plus Q equals R, 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, OK, I want the sum of P and Q,

  • which will be down here--

  • R. I want 2P, for example.

  • Well, with 2P, I can take a tangent

  • and then find where it intersects

  • and then go down below the curve.

  • So for example, if this is G, I say OK, well, G

  • starts here, take the tangent, find where it intersects

  • and then drop down.

  • And this is 2G.

  • So it's a simple way to say, well,

  • 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 4G.

  • I take the tangent at 2G, find the intersection here,

  • drop down.

  • OK.

  • Here's 4G.

  • Take the tangent here, it'll go--

  • I can keep doing that and get 2G, 4G, 8G.

  • And if I want intermediate things, like, well, I want 3G,

  • well, I draw a line between G and 2G, find the intersection,

  • and find the sum.

  • So yeah?

  • Yes?

  • AUDIENCE: When you find the intersection of that

  • [INAUDIBLE] the intersection of the modulo of something,

  • does it just--

  • TADGE DRYJA: Yeah, yeah.

  • So the pictures look nice, in this case, right?

  • It's like, hey, there's this curve.

  • And it looks so simple.

  • And we can 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.

  • 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 a number.

  • So it doesn't actually map to a nice curve.

  • So the fun thing about when you're doing modulo

  • is all the properties stay the same, right?

  • With regular numbers, you can still

  • do addition, multiplication, division

  • all modulo some number, and it still all works, right?

  • So same with this.

  • You still have the same 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 take a tangent--

  • although a tangent is harder to visually see because there's

  • no obvious curve here--

  • but the equations work the same.

  • OK.

  • So you don't need to know exactly why these things work

  • or curves.

  • But we're going to go through what you can do with these

  • and what properties you have.

  • OK.

  • So we've defined these points on a curve

  • and how this curve works.

  • And then we also have regular old numbers, right?

  • So what we'll do from now on is say, like a and b,

  • our lowercase numbers, these are scalars.

  • Scalars just means regular old numbers.

  • The uppercase A and B will refer to points on the curve, OK?

  • So from now on, lowercase is regular number,

  • uppercase is point on this curve,

  • or point on this mashed-up thing that we still call a curve.

  • OK.

  • So I'll go through what operations we can do,

  • and then we can see what use those have.

  • So first, scalars.

  • You can add, subtract, multiply, divide.

  • You can do whatever you want, right?

  • These are just regular numbers, like five or 17 or 22.

  • Everything's OK, right?

  • Easy.

  • Everything here is integers.

  • We're doing modulo some big prime number,

  • so there's no decimal points.

  • 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 also uint.

  • These are like unsigned integers.

  • You can do it with signed.

  • 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 pretty close, but you've

  • got some fixed amount of decimal places you can store.

  • Your floating point goes out to some precision.

  • And then error can accumulate.

  • And in a lot of cryptography, you want zero error, right?

  • Like in a hash function, it's pretty exact.

  • So a lot of times, the cryptography,

  • you use integers instead of floating point or rational

  • numbers.

  • OK.

  • 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 do that visually.

  • And then the equations for it, the computer

  • can do that pretty quick.

  • However, this is not defined.

  • Multiplication and division with two points is undefined.

  • It's just not clear how you do it.

  • 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 and subtract points,

  • but you can't multiply them.

  • Any questions about this?

  • This is pretty important.

  • Make sense?

  • Yes?

  • AUDIENCE: In the previous case, when you were adding points,

  • what is defined as addition?

  • Are you adding only the y components?

  • TADGE DRYJA: You use both the x and y-coordinates

  • to add, right?

  • So when you're doing it in the computer,

  • you're saying, OK, well, what are

  • the x- and y-coordinates of P?

  • What are the x- and y-coordinates of Q?

  • Find the slope here and where it intersects the axis.

  • And then see where it'll intersect the curve

  • at another point.

  • AUDIENCE: Addition Is literally defined as compute that point.

  • It is not a function of adding the x- and y-coordinates.

  • AUDIENCE: Gotcha.

  • TADGE DRYJA: Yeah.

  • Well, I mean-- yeah.

  • But the equation would be--

  • since the computer doesn't actually look at the curve,

  • you just say, OK.

  • Find the Px- and y-coordinate.

  • Find the Qx- and y-coordinate.

  • Find the slope, and then find where it intersects,

  • and then compute for that for R.

  • OK.

  • So yeah.

  • You can add and subtract.

  • You cannot multiply and divide these points.

  • Sounds good?

  • Any other questions?

  • Yes?

  • AUDIENCE: How would you subtract?

  • TADGE DRYJA: Ah.

  • You just go down, right?

  • So if I want P minus Q, I should say P plus negative Q.

  • And negative Q is just right here, right down on the axis.

  • So I say, OK, I want P minus Q. I go here.

  • Find it.

  • It's going to be up there somewhere.

  • So yeah.

  • You just add the negative of the number.

  • I guess that's another thing.

  • Minus B-- negative B-- is also an operation I can do.

  • I can negate something, which lets me do subtraction.

  • AUDIENCE: For those of you with math backgrounds,

  • this is defining a group operation

  • on the field of natural numbers, modulo--

  • TADGE DRYJA: Which is a big one.

  • AUDIENCE: --and using this elliptic curve.

  • So this is A. And the only thing that's defined

  • is addition and subtraction and not multiplication.

  • TADGE DRYJA: Right.

  • You can do the same group operations

  • without using elliptic curves.

  • And so you can just do exponential modulo

  • big prime number.

  • I'm going to use curves because it's

  • what is used in all the actual systems.

  • But you can sort of forget about the curve after this, right?

  • You can say, well, look, we just have 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're in the computer, you're just like,

  • yeah, that's a point.

  • That's a scalar.

  • Here are the operations I can do,

  • and I just run the functions.

  • OK.

  • 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

  • and an integer.

  • That's not defined, right?

  • You say, OK, here's this point p minus 7.

  • Well, does that mean move the x-axis?

  • Does that mean move the y?

  • It's not defined.

  • However, you can do this, right?

  • You can multiply and divide.

  • So you can say, well, A times 2, well,

  • you take the tangent, right?

  • It's just A plus A. Or A times 7, is we just break it down 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 inverse of B

  • and then multiply by that--

  • the multiplicative inverse of B modulo the order.

  • But anyway, you can do these.

  • This is a little trickier because you

  • have to compute what, like, B to the negative 1 is

  • and multiply by that.

  • You can do it.

  • So you can do these things where you have points times scalars.

  • But you cannot add.

  • Yeah?

  • AUDIENCE: So 2A is basically joining

  • the tangent to A, [INAUDIBLE] beginning.

  • TADGE DRYJA: Yep.

  • So that was here.

  • If this is G, this is 2G.

  • Find the tangent, find the intersection, and then negate.

  • OK.

  • So you can do that.

  • That's cool.

  • You cannot do that.

  • OK.

  • 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 and subtract them.

  • And when you mix, you can multiply and divide.

  • And that's it.

  • OK.

  • Any questions so far?

  • You don't have to worry too much about the curves and all

  • of the math and stuff.

  • But you just sort of say, OK, here's my toolbox.

  • Here's what I can do.

  • OK.

  • 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 pick 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, since it's all modulo, this number,

  • if B is too big, you'll wrap around, right,

  • because it's all modulo, this n.

  • So it's called a generator point because--

  • and every point on the curve can be one--

  • if you keep, say, 2G, 3G, 4G, 5G,

  • eventually, you'll get back to G, right?

  • It's all finite.

  • OK so does anyone have an idea, OK,

  • 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, you're like, oh.

  • Any ideas?

  • Yeah.

  • AUDIENCE: So you take your point G,

  • and you multiply it by some scalar,

  • and you publish where the point is [INAUDIBLE] scalars.

  • TADGE DRYJA: Yep, yep.

  • OK.

  • So your private key--

  • let's say private key, lowercase a,

  • it's just some 256 bit random number, scalar,

  • exactly the same as 32 bytes like in a lamport signature.

  • And your public key is just a times G.

  • And your public key is now a point on a curve.

  • We're going to call it uppercase A.

  • And you have a 32 byte x-coordinate, right--

  • because the x dimension is 256 bits--

  • 32 byte y-coordinate.

  • So it's 64 bytes--

  • pretty small.

  • Anyone have another quick optimization

  • on how you could reduce this?

  • So there's a lot of optimization going on

  • in all these different cryptocurrency systems.

  • Because they don't scale too well.

  • But any idea of how to get that down?

  • AUDIENCE: Can you hash it?

  • TADGE DRYJA: You could.

  • So you could hash it.

  • You'd make it into 32 bytes.

  • There's a more useful way.

  • But if you hash it, you still have to reveal it later, right?

  • So it helps, making a pubkey hash.

  • And that's what Bitcoin did initially

  • is you'd have the 64 byte public keys.

  • And then you'd send to the hash of them.

  • There's a nicer way.

  • Any ideas?

  • OK.

  • So the thing is it's symmetric, right?

  • So the curve is symmetric about the x-axis.

  • Any ideas?

  • yes.

  • AUDIENCE: Could you just code one of the x- or y-coordinates

  • and say which side?

  • TADGE DRYJA: Right.

  • So you take the x-coordinate and encode that.

  • And then just that one bit--

  • 4-- it's on the top.

  • It's on the bottom.

  • And then let them figure out exactly where it is, right?

  • So you can encode the x-coordinate only and 1 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 going to be empty.

  • It's just going to have one bit in it for up or down.

  • But whatever.

  • So you can do that, and that's also really cool.

  • OK.

  • Any questions so far?

  • AUDIENCE: Could you encode a [INAUDIBLE] and same

  • up and down?

  • Could you just encode an [INAUDIBLE]??

  • TADGE DRYJA: Huh.

  • Probably.

  • But I don't think it would be smaller.

  • I think you'd have to probably have the same size

  • if you use some other coordinate system.

  • Hm.

  • Yeah, you could encode a slope--

  • AUDIENCE: Yeah, the [INAUDIBLE].

  • TADGE DRYJA: And you say it intersects,

  • and it's at the slope, and which side of the axis?

  • AUDIENCE: Yeah, and if it crosses multiple times,

  • which one of the--

  • TADGE DRYJA: You probably could.

  • I think you would end up the same size.

  • But yeah.

  • But it might be faster for some things.

  • There's all sorts of different encodings.

  • AUDIENCE: I guarantee that you have an integer in the end.

  • TADGE DRYJA: 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 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?

  • AUDIENCE: Can you define the scalar multiplication again?

  • how does it go?

  • TADGE DRYJA: OK.

  • 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 2G, right-- tangent, intersect,

  • and then the negation.

  • And so you just do that a bazillion times.

  • However, since you can find 2G and then you

  • can double 2G to get 4G and double 4G to get 8G,

  • you can come up with powers of 2 of G

  • and then add those powers of 2 to do

  • a much more efficient addition so that you can practically

  • make--

  • because little a is going to be some huge decimal 50-digit

  • number or whatever.

  • So you're going to have to do this two, four, six,

  • eight binary expansion and then add them all up.

  • OK.

  • Yeah?

  • AUDIENCE: You're chucking everything into some grain size

  • to get these.

  • You're [INAUDIBLE] a continuous curve.

  • TADGE DRYJA: Yes.

  • AUDIENCE: It feels like if you have 306 bits in the original,

  • you shouldn't be able to get all the way down to 32 bits, right?

  • Because you just want to make sure that you--

  • TADGE DRYJA: This?

  • AUDIENCE: Yeah.

  • If you removed a byte of precision,

  • would you actually be losing any power?

  • TADGE DRYJA: What you can do 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, positive y

  • component.

  • And everything else is disallowed.

  • You could have that as a rule of your system,

  • and then you can get rid of the y bit.

  • But the thing is the y-coordinate

  • does affect some of the things like signatures, things

  • that you'll later use.

  • So you can just say, OK, look, implicitly y bit is positive.

  • And you lose 1 bit of security.

  • Because there is a difference between

  • the positive and negative thing if you're doing signing.

  • But yeah.

  • And so some systems do do that.

  • And it makes things easier.

  • There's some signing systems that do that.

  • OK.

  • I'm going to go to the next part.

  • 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, more obvious, cleaner, more powerful

  • signature system that was patented by this German guy,

  • Claus Schnorr.

  • And so no one used it, or maybe a few people used it.

  • But in general, with open source things and web standards,

  • patents are 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 Schnorr 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 cryptocurrencies use Schnorr signatures.

  • I think Monero uses a Schnorr-like signature.

  • But Bitcoin will probably be putting it

  • into Bitcoin in the next year or so.

  • So all these things will be much more applicable,

  • and you can use them.

  • And there's code out.

  • You can use them now.

  • OK.

  • Yeah.

  • Sorry.

  • Patent has expired-- free to use the better

  • algo that must not be named.

  • So yeah.

  • People don't call it Schnorr signature as much.

  • Because it's like, well, this is the guy who prevented us

  • from using this for 20 years.

  • And there's modifications to it.

  • OK.

  • So the elliptic curve signature, for lack of a better name.

  • This is something of a simplification.

  • And there's 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 secure, and it works.

  • But later things, you might want to actually add 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 and 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 going to multiply it by G.

  • And they call this R. I don't know why they

  • use these letters, but anyway.

  • K times G is R. R is 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--

  • minus the hash of your message concatenated with R,

  • this public key-- so you encode the public key in 33 bytes,

  • stick it in there--

  • multiplied by a, your normal private key.

  • And then your signature is the pair--

  • the R point and the s scalar.

  • This is a little bit of a bunch to process.

  • But it's actually not too bad, right?

  • This is a scalar--

  • 32 bytes-- that you made up.

  • The hash, this is a message, also going to 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, the only elliptic curve operation

  • here is calculating what R is.

  • 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 a decent code, a decent CPU, can

  • do on the order of thousands of these types of operations

  • per second, which is decent.

  • You can do a decent amount, but it is kind of slow.

  • And it's considerably slower than hash functions.

  • You can do a million iterations of a hash function per second

  • on a core, or you can do, maybe, 1,000 or 2,000

  • 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 32 byte scalar

  • integers, which is much faster.

  • OK.

  • So does this make sense?

  • We'll go a little bit of how you can't forge this.

  • OK.

  • Sorry.

  • So first verification.

  • Sorry.

  • So how would you, if anyone knows or can think,

  • how would you verify this, right?

  • I know their public key--

  • capital A, which is 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 big A. So how would I verify this?

  • AUDIENCE: Can I, for example, take the hash of the message,

  • use R, and then try random a's and that--

  • on, sorry.

  • TADGE DRYJA: Yeah.

  • Do you have one?

  • AUDIENCE: So trying random is probably [INAUDIBLE] because--

  • TADGE DRYJA: There's a lot, yeah.

  • AUDIENCE: --there's too many.

  • The old one that you don't know it.

  • But I think one more thing you could do is take little s

  • and multiply it by big G.

  • TADGE DRYJA: Yes.

  • AUDIENCE: And then do some--

  • TADGE DRYJA: Yeah.

  • 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, OK, well, as the verifier--

  • I've got R, I've got s--

  • I multiply s by G, and now I have

  • to multiply this side by G. And what'll that look like?

  • Well, what's k times G?

  • AUDIENCE: R.

  • TADGE DRYJA: R. What's little a times G?

  • Big A. So yeah.

  • I want to verify.

  • I want to verify 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 k times G minus the hash thing times little a times

  • G. This is big A. This is R.

  • Hey, now I know everything here as the verifier, right?

  • I know what s time G 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, OK.

  • Well, I rearrange it a little, and I 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?

  • Does this makes sense, mostly?

  • So for the verification, it's a bit more CPU-intense, right?

  • You're given a scalar.

  • You multiply by G. 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 precompute all sorts of coefficients times G,

  • and you store them in RAM or in your CPU somewhere.

  • So multiplying by G is a little bit faster

  • because you do it a lot, you can precompute 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 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.

  • OK.

  • Any questions so far?

  • I'll go a little bit into why this is not forgible, right?

  • So I want to forge a signature.

  • Well, I don't know little a.

  • But why don't I make up a k and compute s and R?

  • But I need a, right?

  • So I'm going to say, OK, this is the equation I want.

  • I'll just make up my own k and make up my own k, s,

  • that'll 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 because I don't know here, right?

  • 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 R is in the hash function, as well.

  • It's the one-wayness of the hash function that

  • actually breaks this, right?

  • So I could say, well, let me solve for R. Well,

  • R is the hash of m and R times a plus s times G.

  • If I can come up with a valid R 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 you can see just like, OK, I need to solve for R. Well,

  • but it's already in here.

  • I'm stuck.

  • If I don't know k, I can't come up with a signature, either.

  • OK.

  • There is one footgun with EC signatures.

  • If you use the same R value for different signatures

  • with the same pubkey, you reveal your private key.

  • So k has to be random and new every time.

  • If you look through the equation,

  • you'll see how you can solve--

  • if you have two of the same k's with different s's--

  • you can solve for k.

  • And then, once you solve for k given

  • this, if you know what k is, you can

  • find what little a is, right, as a verifier.

  • You can say, well, you gave me s.

  • That's part of the signature.

  • I know this whole coefficient.

  • If I know k, I can solve for 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 about elliptic curve signatures,

  • in 2010 or something.

  • So actually, there's interesting tutorials

  • written by the hackers who broke Playstation 3 about how

  • this works.

  • And that's when I first read about it.

  • OK.

  • We're almost out of time.

  • Any questions about this stuff so far?

  • OK.

  • So this is a signature algorithm.

  • It's like, OK, 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 I've found fun things that you

  • can do that I guess are novel.

  • And I'm not an expert on this at all.

  • It's just that it's a fairly new area of research

  • in how to do cool bitcoiny cryptocurrency

  • things with these curves and points and stuff.

  • So I'll go through a couple fun things you can do.

  • Fun with points.

  • OK.

  • So I'm not using an asterisk.

  • Just 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 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. C-- this

  • is called a Diffie-Hellman key exchange point.

  • Diffie and Hellman are two also late-'70s PhD students who came

  • up with all this cool stuff.

  • No, wait.

  • Diffie was a PhD student.

  • Hellman was his advisor?

  • I don't remember.

  • Anyway, they came up with this idea.

  • And this is a shared point.

  • What would this be useful for?

  • It's actually super useful.

  • Can you think of like, oh, OK.

  • We can do this.

  • We can compute C. Why would we want to do that?

  • Any applications you can think of?

  • Yeah?

  • AUDIENCE: Trying to share keys with people without both

  • of them knowing who they are and evaluating

  • the other set of keys.

  • TADGE DRYJA: Yeah.

  • It's really cool to share keys.

  • So this is also done if you have a web browser.

  • I think it's all elliptic curve Diffie-Hellman now, mostly.

  • But if you have a web browser and you go to a website,

  • this is happening, basically, for every HTTPS request.

  • Because you can use C as a sort of

  • shared key and encrypt things with it.

  • The idea is big A can be public.

  • Big B can be public.

  • Point C will not be public.

  • The only way to compute it is to know

  • either Alice's private key-- little a--

  • or Bob's private key, little b.

  • Even though you can see the public keys,

  • you can't compute C from just the public keys, right?

  • Because big A times big B, that's not defined.

  • 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 an interactive verification

  • where you say, OK, I'm Bob.

  • I'm going to make random point.

  • I'm going to give that to you.

  • Prove you know your private key-- little a--

  • by telling me what C is, right?

  • So I can make a random key here, give it to you.

  • You return C. I verify that that's the right C. And I say,

  • OK, well you must know little a.

  • You haven't shown me a little a, but you've

  • proven that you know it, so proof of knowledge

  • of the private key.

  • So you can use that for logins instead of passwords.

  • And it's 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 we'll

  • define D as the sum of these two public keys.

  • The thing is if you're summing these two public keys,

  • it's commutative, and it is 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 public key D,

  • and I say I want a signature from public key D?

  • You can.

  • And you so the private key, little d,

  • which can sign for this, is just little a plus little b.

  • So you can make a combined key.

  • And then either party--

  • Alice has little a, Bob has a little b--

  • and they could reveal it to each other

  • and allow the other person to make a signature with D later.

  • I use this in the lightning network software I've had,

  • where, basically, you say, look, we'll compute D,

  • and I can give you the private key, right?

  • I'm Bob.

  • And I say, OK, here's point b.

  • Here's point a.

  • We add them together.

  • And then, Alice, if I give you my private key, now

  • you can sign, but I can't, right?

  • So I'll give you the private key to D

  • from some information I have.

  • Or you could give me the private key to D

  • by sharing 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 bitcoin addresses, things like that.

  • Before you even get to signatures,

  • you can share keys and stuff.

  • There's all sorts of super fun things

  • you can do with these points and curves and systems.

  • Multisignatures-- I put a link to a PDF file

  • that's very recent and kind of overkill and over my head,

  • as well.

  • But you can do signatures where you aggregate the signatures.

  • But

  • There's ways to say, OK, well, I'm

  • going to add all these R points, and I'm

  • going to 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 10 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 10 signatures, instead of being 64 bytes

  • each are more like 32 bites each.

  • And there's one extra 32 byte value for all of them.

  • So there's a lot of really cool ways

  • you can 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 figure out what people's private keys are,

  • whereas hash stuff, hash things like lamport signatures,

  • still work.

  • So there's some talk of hey, we should

  • prepare for if that ever happens and make efficient, effective

  • hash-based signatures and use them

  • in something like Bitcoin or Ethereum.

  • People haven't yet because the overhead is really high.

  • It's really big.

  • 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're not going to do anything yet

  • 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 multiply by G is a function,

  • and multiply by this point is a function.

  • So this is groundwork for cool stuff you can do.

  • And it's really nice because it's a new area.

  • And I'm not an expert on this, but I've come up with stuff

  • that people have cited 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 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 no one think of that?

  • It's one line.

  • Wow.

  • So there's just not a ton of people

  • working on this kind of stuff.

  • And so it's kind of fun.

The following content is provided under a Creative

字幕與單字

單字即點即查 點擊單字可以查詢單字解釋

B1 中級

3.3. 簽署 (3. Signatures)

  • 4 0
    林宜悉 發佈於 2021 年 01 月 14 日
影片單字