Mark Yeah I like thinking about sort of tiered timings in human interactions that magnetic Presidency of the day you guys when designing your superior channels and you're chatting whatever else. And every time there's a through people chatting chatting there'll be this moment where everybody sciences at the same time then rinsed backed up read it. And it's just like Okay I'd like to go through the differential equations that model that'll allow or whatever. So somehow some of xs and play plastic teams always important in my lectures. Not like me I want every lecture would be important but like trustworthy to subpar compared Let me break. All right so this is this watershed moment or I don't know what Mars was me. Turning one glass. A lot of payoffs happened a day like yesterday is premier fema thrones. Season a little threads coming together looking at the Seinfeld episode or whatever like that with this lecture is to us where all these little threads may come together we finish awesome pictures. It might take a couple of days you get through it all. And it's all thanks to the guys in Bosnia yesterday slow down. So here's the idea. Everything we've done so far is this symmetric key the reason I have this five give here whatever else is that in the symmetric key Worlds actually do anything halfway decent. You've gotta get like actual files cross a border to the other the KGB headquarters whatever so that you can have the red phone encrypted. So symmetric key encryption required communicating every day with new key is whatever Enigma style or whatever right like they've got to change your key everyday owes the fact that they had a keen book. If the key both leaks everybody's done that kind of thing. Basic epic stories like folks going into is sinking U-boats to recover an enigma and a key thing and whatever else and getting it back out three out of five of dying stuff or whatever like you know. It's too big Makes sense of war. Our heads aren't made for it. But but that's at least a little deal name. Alright so now we want to change that to like like I'm calling this public key revolution because the internet and everything that we do and all of our economy and all of our e-commerce at every pass most of the careers that you all are thinking about would not exist without this wacky moment comes out to seven Right which is to say the move to public key changed everything. Now you think what in my mind isn't apply very modern crypto class and yeah I spent so long months talking about symmetric key encryption saying public-key changed everything. Why don't I just started public-key and do that the whole time I'm whatever. And that's why it's more Game of Life or more Seinfeld episode. And it seems like you might see from the outside like okay we'll just teach us public-key. Is it that matters the moderator not sure it. Yes is everything. Product two is everywhere This is 5% that enables the internet right so here's what we have to do. The eggs here. One just public-key encryption. All the changes is that the key for encrypting is different than the key for decryption. Alright so you have two keys now for every version scheme and there are two keys per user. So in a public-key scheme Alice will have a public and private key. Bob will have a public and private key of Alice wants to send a message to Bob. She uses his public key to encrypt. And he uses his private key to decrypt. Alright so this is published. It's like a big billboards anybody who knows but it's like an email address I sent you an email but only the person has passed from that email account can read. Back. The reality though is that picture of public-key encryption encryption like isn't the reality of our world. That's not actually what happens more or less ever except for in car Bob's identity cards on doors. And just one little moments in sort of a packet exchange very exchange an HTTPS site including this one this HTTPS site setup and cube encrypted communication with my server that all of this and came down eight yes encoded and then decrypted by eyebrows right so this Maybe yes but how did we get our share key that's the story when it's all day. That's how I get across a shared key in a noisy channel where everybody's list. Alright and so what we're going to try and do it. We're going to in the chat exchange public messages that allow you and one other person to completely swamp the private key that only you to know and everybody else is listening means higher exchange. Alright and then we'll break that. One thing that is also true is that from now on the math plays a different role in all of this eight yes. Yeah we can kind of say like alright stabilize this. So on and You know we have 28 to 56 on the Mac. It's way crap. You're in public-key encryption like I guess scarier bigger. Public-key crypto is way harder to analyze and all the map species are about Public-key stuff inside the NSA analyst thing that. And here's why every single public-key scheme has a hard prop. Is a hard problem with some pretty good information makes it easy and without it it's hard. Alright I'm called these back door problems. And if you want to make your own crypto scheme as a PhD student or whatever which I don't recommend anybody doing. You all did problem five maybe never if you only wrote once. Maybe didn't already. Remember people looked at knowingly. So if there's gotta be some length backdoor shrank and whatever else that FB is is this problem is NP complete. This problem is really learned through both off unless I know the answer and it's really that kind of thing that makes valid keyword. So the first heart based on discrete log problem. So here's discrete log I'm going to tell you that 22 is equal to three to the x my 31 find X icon. There you blah blah. Blah. All right Now let me ask you this a little bit leading leads on in cheeky whatever I know. Here's my solution to this thing. Brute force triangle whatever. And it's telling me that this is a hard problem. But now if I jump this up to 3100 or 331 million and it's got some prime up in that size. Can you do something better than try every power of x in your mind is like me asking you Packard integer how quickly can you do it Yeah so that's certainly something that you wanted to act on this thing that's known is avoidable or whatever else but way. I'll show it to you. This is the hard problem. So you just imagine just adding zeros everything that makes a rattling tricep. How does that change the essence of this problem and of course through to the elements 500 islands whatever then this is o So here's how we're going to use. The discrete log problem to do a public key exchange is called the Diffie-Hellman exchange. I think one of the dudes has long hair. It's kinda like the Ready Player One architect guy. So but all sorts of computer science Wurzburg be there bafflement. So here's what we're going to do. And we'll start with the smaller. Here's a small version here. Alright I'll walk you through that thing and then we're going to do the small ones and then we'll do a big one for me. I think that might be to the first person. We're going to have this sort of back-and-forth exchange Alice to Bob. Bob had. That should be enough. Alice is going to guarantee strong Prime which I'll explain live code base which we'll call g which might be number two or three something like that. A random number little a which she's going to call private. Alright and what's important is that little a has no common factors with the prime minus one. It's very important that the GCD of a minus one is one Then the discrete log Lockhart she'll take her private number raise g to the a mod P and that will be a public heath capital a as he will centric world to prime the base and our public-key capital a as you will remember her private key little bit. Okay so if if she she can validate the G to the a is capital a little private key is public key and nobody else should be able to figure out private key from just seeing capital a pH. That's the essence of the hard problems. What's going to happen Bob is going to receive capital a. And he's going to do is oh he's going to take her p her G And he said I thought that was all random private therapy with gcd one US one. And it'll calculate G to the B capital B mod p. Now what he'll publish is capital B. Alright so he took his own private key. Little b. Does the exponentiation sends it out and then secretly he takes Alice's key and raises it to his secret power. This is the big takeaway. She had G to the a and e raised to the b. Xi is going to get g to the b which she raises to the a. And in that way they both learn the G to the AB without knowing the other one's private key. I'll show you that here. Herky as GBA. His key is D sub B. If B she knows a. Then she takes his key and raises it to her little a like that. And he takes her he raises his will be like that. And I'm certainty that these are the same number. And I think numbers kept secret and that number is kept secret that's their shared secret. So they have a private key that they know individually and they have a shared secret and then two of them no. Nobody else knows and I didn't know need to know anything about his private key in order to accommodate. And nobody else is listening can figure out the shared secret. Unless the discrete log problem is broken is the view. So and this is you know it's just that g to the VA things you did leave GDB. And that's easy peasy stuff. Okay so that's the saints. Let's do it once. First assuming that this baby triple Alright so you're going to be Bob Alice has published a prime a 101 g is two and tackles. And six is her public key to your jobs now generate random prime that has no GCDs are random number but there's no GCD with 101100. So no common factors with 10101 minus one and publish to your private key and then invalidate that if you take her six your private key you get that thing. Nfc takes your public key to 7B. She gets your event. We're just gonna sort of do it here on Scratch. And then we'll do in the actual challenge. Big numbers are same Body language I feel like that's not clear as some words so don't be scared to say wait but he is one of the two capital A's. I think you probably wanted to scratch this out on my white board or papers on this once outbreak will continue to do so you get a number that has Fund is. Value is the number of 0s. Yes I think Gerry raised until I just check. Check check check into the violin And so here in this case I generated some random numbers until you got 50 sev and now I can look at something like yeah the DC retired. But just case or invalidate it. I can that crypto number utilities gcd function. And now my settings by little b was 57 and settings my public b will be 74 so I will be published in the Channel 74 now split alcohols and before I gotcha. So analysis side she knew that her little private number was seven Seventy four to 70 mod p And she got 65. This is me pretending to be atmospheric bottom. But meeting Bob I took per cat couplet number six racists in my 57. I got 65 and there's the same number. So that's sort of proved to me that now that was a little key exchange and displaced Abs. We're cool. Now we have a symmetric key and now we'll go into like really well studied symmetric key encryption. So that's all I need the public humor. But this is what makes the Internet work. This is what makes your banking transactions works. What makes HTTPS crypto that prompted into work is that So somebody I know anything about it never exchange information with perfume or whatever else to packets back and forth hierarchy. Once we setup another paranoid Wildcats going to come up with all sorts of problems with it but you all are doing this. I used my powers as protocol. Alice Bob's world to know Alice's right. Alright so now let's do it for real z. Sorry I don't mean to say that. Now let's do it in real life here in the chat So pick a partner and you two are going to do a public swap in the chat that these will be strong values. So we've got this little snippet will generate a random number a random strong primes using same utility and this will be 512 bits strong prices pretty big things. You don't know a strong prime means yet the stuff they're using a base of two and we get this thing. So we'll print out this triplet. It might be either base three is better than what I read. All right so if you run this you might have to loop until you CGC one. Maybe write a little loop or run it a couple times. But then save your little a. Because if you have to run the script again and I'm going to come back to a you have to save your AARP and publish these three in the chat. Alright for whoever wants to be Alice. So I guess the junior partner somebody pick the role Alice all the analysis differently she picks the prime alpha. Then the audit person Bob needs to do the same thing taken her crime In per capital a calculate is although B until there's gcd one b minus one. And then and then publish is capital B. Then do what we did which is take her public key and private key and validate that with your partner that you both have the same secret information. I think every table has an even number of people suffered this one. So Daniel even I couldn't be partners than Alice or shall I exhausted These are both two z2 is at the end of the first copy for 30 seconds. All right. So if you take in my p if you take an offer you generate your own B which has one peak and then calculate power to visit my family. Yeah. Yeah. Yeah Please pay attention here GCDs make sure you don't have a gcd. Is the chance that it won't be like demons will all have 3-2. Odds are more likely to use. And the answer is yes. The hard thing is a chat which is your JavaScript. What we're asked is how slash actual horse maybe. All right there's a bob. Diego's was a bad. Guy You pay that oh no. I thought I was too you know. The guy that makes FLS. These are the guys. They get. My handle is one time. So that I am writing here. Sorry this that I mean. Things can go wrong unless you write losing track of your t not agreed on which primes which right like you need to be on the same crime. And there's a small chance in the back of my mind they like different value of G and frankly I think mathematical properties. But there are definitely because you don't want to go crazy like there wasn't enough She vowels. So the first-person establishes with primary generator and one other key. Here they have a fried and little a little a is that the other person gets the DC generator today make them try that will be that one to p minus one. And then they'll publish it to their privacy laws. So there's Academy plus capital a capital B. If you think the other person's nor privately and then validate and that's the same Thank you very much He said I did. I used to go just yet this one's in the triple G whole housing freshmen right and there I made snippets and just do everything for you just copy paste whatever. Whereas here I'm trusting you. That even passing around a little bit you want to see like complete sets of just copy paste the prophet needed Socrates if these and helped us they challenge us. Big chunk is I don't know if that sounds sounds like you're saying that private refers to when you're a little a little a is supposed to have bigger balls represent private or that Hollywood that animals are. Just consider me like GitHub. They published. A long. Time to happen all beings alive. As long as most needs really are. Oh yeah. Yeah yeah I'm sorry. I missed incentive should be dependent. Child sexual and S3 yeah obliges the secret. Yeah I mean And validated the same. By the way I see yellow asserting that space was the use of words. Like everybody else. Just little things your capital V. I know it's just totally me fish oil twenties. Everybody this by the way is the pace version of what you just did or what are they doing in common base phase a secret color you pick yourself you mix it up and send that along they mix it up and then you add your secret name is why you get this wacky mix. All the colors the bottom they only need to know. And if it's hard to separate out his paintings vase painting the seat of a then this is secure. Oh my God. Oh hey that's a way. There's a way to as a when we go over it again and this is really good or a little. If you're sending it to me the slack time series may exist inside it. Okay superscalars you're talking. Alright so that's your capital B. Here rejects retitled by first-name. Yeah. Oh my gosh. So now my capital a homo. Yeah just tilt your lag effect on growth hundreds of hours. Rather than clashes. That are faster or more new sounds And let me tell you guys be happy. Just like tie fail. Fail yeah I was Carey who's now. So I already have accomplished author. Courage. I'm live right. Now right because we can validate. It said that I said that same universe that's expanding but it's one of the dangers. But every time you run it against the Washington. Why would he or she is to publish those whom we've had said yes he said. Yeah it's like everybody with no priorities at all. I wanted to be invisible. That means that you might say January he wrote this. And now you want me to pretend to be Bob. Just start generating that same value capital machines. My name is Tom we have a document That's the same kind of atoms. So now reusability units the units for random partners that we're working. Like a medical Yeah. I can see you've got this leaves. You no longer. See. Astronauts absolutely just know that. There's you're basically going to go through now and we're just printing. But he's really a share. And I started as he's rejecting utilized. Yes that's standard. Also there's this OK. Now workflow or capital T. Where did I didn't say by saying that you didn't know every stage instead if you said that currently right now with caution. Because like I said wow you already have a tighter bands and that's likely a unique powder. By Matthew cheered. Me on the elbow just hit Enter dialysis Trust power capital goods. Now that is what I love like I said Yes Chicago Atlas data going back and forth and you copy the data. Now will go south or do you guys think how happy you are You can rewrite the program. So let's talk about the implications of what happens to the other successes 5-6. So what we do there is make equivalently something like the ability to stand in this room feel like Hey everybody. My number is. 1235 everybody. Yeah. And you're like oh that's cool. That's cool and salaries. Like Hey everybody my number is worthy to areas like ours And he I like looking at each of them and they just exchange secret mission that nobody else not easy right that's really crazy to me. Pledge really simple to remember your private number. N discrete log is hard and that's it. Alright sounds like really simple math and weird. Like I mean it felt like complex here because probably little a capital that everybody. If you don't have to write primes and we'll decide their computers and their coordination thought setup right or whatever else It's a little scary but just beyond that. And now that we've done the rest is just switch to a private key. All right so now at that point you could do something like take the hex scientists have your number Shaw. 256 if that's your private or whatever any sort of convention we want now to go from that number. Ok. So now I want to talk about what is a c prime that was the same problem you guys use. And in fact they'll come back and say I actually I do this game for a second. I like the scene or minutes to play it. And let's go tools. Okay so here's a game I wanna play with you that seems unrelated but it's not it's related to the Chinese remainder theorem. Which made it switching. I it picks a random number in JavaScript between 2500 inclusive you as a class can it asked me for the remainder of my secret number modulo one of these modulized. Alright your job is to figure out my number with the fewest possible button presses. Okay so for instance if you were to ask for my number mod two I would say 0 or one. And now you'll know whether or not I'm going to need around you'll eliminate right off just like that. Okay so your job is now to figure out which buttons to press to figure out my number is single digit modulus. Fine. I think if you can get this in in the fewest number of steps I gave you an extension on project two. That was a big pie isn't it because we are throwing out. So he goes to fade away five. Anybody else have a preference sedentism eyes. The biggest seven okay maybe it's already consensus here. It sounds like everybody else 55 advise. Anybody I'm probably. I'm do it. Alright the number is for my pot. Okay you're different than our yes. Every time you run the secure wrote a lovely play here. Okay okay so for my five cool what have I learned Well the number could be the number four. What's the next number after four they could eat. They can also be not what's the next number after that okay you have now made an icicle kinda vector space of possible answers which is sort of bored 5K very value five cool. Next hm. What's up you guys know what I mean like he's talking like IOS device. But like saying it wrong they're going to say six mod said so is for Gators for out. Force out. All right how about nines 99 out of the eyes out yeah how about 1414 in or out now now now by the way as I say these
cpeg472-010-20190415-101001.mp4
From Andrew Novocin April 15, 2019
43 plays
43
0 comments
0
You unliked the media.