All possible things out they probably want to like cut out the negative positive. He started every day listening so they can Kuti or something bad day. Sorry everyday England dance party a good day. It's not complex. Discriminating. Alright. So today's RSA day and Thanks to Sam and easy for hanging out with a Friday afternoon whiteboard session on the Diffie-Hellman because you're just like I showed you guys email. I put all that stuff over here. But since that's like the class chat a little bit this morning. Pudding is sort of a deeper dive into cricket I've gotten into slash man that's linked to other nodes. And and I did the same thing for the RSA net here. So so to some extent I think I've finally clips what you guys were missing as space namely learning French from a native French speaker. They're going to be like. Greg was just something. I wanted to say something in French there. But so this is this is I think was the big insight and polycomb them not to do this for a third time. It's been so successful the first keypad. But yeah I think that if I look at it in this context the big idea is that we spend all this time building out Fermat's little theorem and Euler's theorem or Euler's theorem. Client little allows actually just meeting condescending Official title. So in Fermat's little theorem the idea is that anything to the p minus one is 11. And we know that comes straight out of the group theory to look at the integers mod p under multiplication. There's one number that has no inverse and zeros. You throw it out which means the numbers monkey only a p minus one things. And so this is a group besides teammates wanted anything to decide which group is one blah blah blah but you can ignore all right like that. That's what goes through my mind like. Okay that's all just obvious but none of them is obvious and it's like early on aerodynamics or golf or stuff before or whatever. So you just treat this as a fact for any prime anything the p minus one is one. From that fact we can get everything else that we need to duty it's happened stuff and safely with RSA. So in RSA will start at the same exact facts but the general line width and this is not a prime you change it from primed five and instead of P minus one the exact same backed right away but less specific Since the more generalized effect. Because of the exact same logic which is how big is the group of integers. Under multiplication violent guys inverses and blah blah blah blah but you can ignore all that. And just say trust this trust that we can derive everything else. And so with that in mind if you just trust this one back Then the big idea is that well knew that this Chinese remaindering thing or whatever. I think the idea is and maybe sort of here roughly which is that if you can think mod three mod five mod seven or whatever in the world of mod greenness every single integer you'd never come up with has one of three values. 012 or two. Alright my three. Everything is either 01 or two. Because what else there's nothing else That can be written down in this way that every single integer can be written down as either 3K 3K plus one where 3K plus two. Alright so what I did here and kind of make the math a little bit more sexy all is since we don't know which of those three worlds were living in 01 or two world that we're going to write it down in the most generic way. We can say all right I'm going to look like mod three for a second. What I wanna do monetary worlds say let x equal three k plus Y and Y is 0 or one or two. It's just saying let's look at x mod three NFL and saying. But once you kind of have that And this was the discrete log problem you're trying to solve is that given G and H P find x which by the way I wanted to solve so bad last night at 01:00 AM. And and and I couldn't wait for right tell me how I'm supposed to solve the discrete log problem. Because p minus one and so on. So I'm too dumb to see it. Sorry that was negative self-talk. That's an experience that particular variety. Discrete log All right so this is the idea. If I have a discrete log and I need to figure out x mod three. All I'm trying to do is replace the search for length 0 e minus two with this search is 0 or one or two. So here's the idea plug it in. If it just so happens modulo some plane three divides p minus one easily. Then we can use that beautiful little Fermat's little theorem trick to reduce my search space from infinite. So I agree. Alright we're not infinite but joins to small. And here's that idea. We know I'm going to use P equals 31. We know that g to the 30th is one So and that every single integer x can be written as 3K plus y for some small y 01 or two in any k some k out there exists but it's true. So what I do is raise both sides to the ten. Why because I want to make 30 happen. So here's me. Imagine that if I raise both sides of the center just this just XEN but I'll look at it a little differently. What I see is three k plus one g k g that vary. Hey that's just one. Right now that what is gone and I've reduced the problem to ten y. Well does that help me at all **** yeah it helps me It helps me because now all I need to do is plug-in Y is 0. Y is one for wise too and one of those three values as an answer that guarantee. Because x has to have a modulus a remainder mod three. So x is either 0 or one or two. So all I have to do is solve the problem now is calculate this one and check it against this value that value and that that and that will tell me was y 0 was y one or was Y2. Right so that was the whole big idea. And I think without pricing that line of algebra maybe it doesn't make sense just to go further. Why not try like other modulus if I were to do like seven Do nothing is stopping me from writing down the exact same thing. I could write x equals seven k plus y for y equals x months 70 through six. But I don't that doesn't help me. Because when I look at this I don't have any clever tricks I can do to get rid of that seven K. So like my search space is still fighting to and then find the y. Whereas in the other triggers it'll get rid of. And that's all the ideas that I can write anything down and life is modular representation but I can search that change the search space and time. And that is all the neck. And that's the idea in public health is to change your search space an infinite to tiny. And you can only do that when for any modulus that divides p minus one. Alright so the biggest thing the biggest prime divides p minus one is the actual size of the attack on giving up. Which is why I was stumped saliency of everything. That I hope that helps you to dive through that at your own pace and a journal and detailed level or whatever else. So that you not only get the offer letter O. So today we're doing RSA. Rsa is definitely the best branded encryption scheme in the world. In my opinion besides maybe the Caesar cipher but I think RSA is more popular to decipher. At least more well-respected. I don't think it should be per se. Secure like literally literally 15 attacks on the RSA play. So so it is a curious. But for really tiny bands of securities like crazy to make you feel uneasy about eight. Yes. If I do the same thing with RSA or something I'm not going to think about just making another set of play seven RSA CTF problems that had all the crazy ways you can attack RSA because like every single CTF has a velocity and RSA Brown here of aliens. You'll love. Yes exactly. Exactly. Did you say yes to a jack And I believe really non-linear problem. Pause the oceanographer or whatever. I don't have all you engineers. Who have another CCS style problem like that I like the idea that like now anybody wants to get better at crypto CTSA. Oh gotta crypto crop that ended you probably to do Project three. You can do those. You'll always get points always. Yeah there you go. Alright so salty that with RSA will go through like 15 different styles and tags and things like that. Somebody said something clever recently ended on remember what it was Anything yeah yeah I remember I think all ambitious mathematicians should think that they can crack RSA at some point in their life. And and my advice to you is to give it one weekend. So I crack RSA totally general way not bored. Don't build your career cracking where I say unless you are like like I'm one of those french jobs it never needs any outputs to keep you have hired. There are positions like that where you're just or or I'm very tempted. So like I'm I'm I'm practically retired. And he's like public service to come in for supplies and things like that. I'm I'm thinking about building like an honor society of sorts where folks in their late teens or early twenties get heavily mentored to get financially independent by their thirties somewhere then varies and once you're financially to make my let's not go nuts like enough ism Whatever. But what's your once you set up we're like okay I know how business works and things like that whatever else then you pay it forward by improving the Middle C. So for a happy like making money saying happy life giving all the thing and you pay it forward by mentoring other way late teens early twenties people and show them how do you financially through what's called the mid-twenties count mission or something so if they say like that if you get to financial independence one of the things you can do it that's correct bars. So I'll say exactly right. Don't make your day job crack RSA. Unless you get into the project that system which we can debate the merits of that. Otherwise whatever he says as sows had the defendant you crack it. And you can't because like Watson boom cracking but there's like 1000 different way you're linking paperclips on it like that so that I think is really fascinating. And maybe we'll do a little bit as we lastly script go. It's really fascinating to see just the ballet dance between like totally cracked and secure. And that is this tiny little region that it's secure. And it's really secure in that tiny little region. And so are all the implementers using it wrong. Probably. That's why this course exists right is that you are going to be implementing stuff and you're gonna have more faith in it edition. And that's my job to make sure that your faith is correct as well as me now and you're thinking probably some bright mathematician will shrink even on the base limits. Thanks to the news and stuff to say oh crap I was wrong. And don't know what your assumptions are about harnessing the robot bow. Let's get. Let's get. 128 bits of security in EPS is equivalence like multi-thousand bits and security Norris it that's already should freak you out a little bit which is to say that. If you make like I've seen CTF problems which is perfect RSA everything is fine textbook. Just the size is 512 bits Five hundred twelve bits is like qnorm is good for decades of Kuang security ES world. And it's like crack it in our CTL. That's the only clause if there's 512. Okay alright. That sucks I I'll show why as we go through the math here but just be aware that you need massive key size to get the same level of security. But it's not like in. 2020 yeah yeah yeah it'd be like 20 bit AES which doesn't exist per se. But for lunch like there's like MD5 based ADS with something. So I'm going to show you the mechanics of RSA and then we're going to do it. And then we'll dive into math. I think unless you want to dive into the math or you didn't tell me you were a bit but but I want to actually just do it is they want to be handling keyboard. Here's the math the virus gets done is another classic. I maybe done ours in other class too. Okay that's one. So here is the idea you generate two primes You calculate enables P times Q. Alright that is the modulus. You calculate phi of n which is the number of numbers that gcd one with n smaller than n. And we've proved this ages ago mac week but I'll just tell you it's p minus one q minus one. P minus one times q minus one is five. You select and E with gcd one with five. And typically this is actually the precise value six cells. 65,537 that's the most common. You could say that y two by 6553 subnets those funding is not such a big deal It doesn't have to be Raymond's lecture and then calculate d. The modular inverse of e mod phi. D is go to your private key and you probably he is going to be n and e. Okay so far you're just trusted me and remembering like you're ugly kind of drone human mode. You don't you don't get it but you're doing. So to get n and e and get the d such that e times d is one modify. I'll say this the things that you don't tell anybody like the private information here is P Q by D Those are the things that you notice when I set this problem up and nobody else in the world knows. Alright and the theory is that if B to C N and E And they have no idea what p q phi where D R right and if you can figure out any of those and figure all the rest of those. And and they figure that out I can factor the number N. So if you can go from n to p and q then you break RSA. So RSA is based on the part from Diffie-Hellman itself as discrete long. Rsa's hard problem is factoring integers. And I'll say the tray. Factoring integers is not a hard problem. Right If I think about it this way for a number of size n. How many tech trial edition so I had to do to be guaranteed to find a factor or forget prime squared over n. So let's say we're in but it's actually are square root n. That's awesome like square root n time algorithm. I'm thinking alright I published and I said that's good. That's good complexity. The problem is that N is just massive and is to the bike out. So the square root of n is two the 2500. So like looking at a brute force of size two to the 2500 as far you know and the algorithms get better and better at factoring integers and things like that We have no earthly idea the actual complexity class factoring integers. Now I'm saying square root n is like this elementary subversion. What they really want is what's the complexity in the number of digits not the actual end itself but in how long it takes to write down. And I'm saying this it's a simple problem to do trial divisions up to two square root n. So it's more than just the size of the problem is big. And we as students just want magic. So it might actually just be intractably simple problem at massive scale. But if there were like a log n algorithm for n Then we win. And that's basically to fight There's something better than square root and that's good enough animals. And we probably never do. Here's his men. Forget all real and here's the mechanics of the dam or a sentence. I get a public key then I get public exponent e which is normally fixed six by three. So what I'm going to do is take my message right down isn't integer which we've done many times ratings the integer to the e mod n And that's my ciphertext. Alright so in this case the exponents is known. The base is not known so it's sort of the kind of discrete lobby but not quite the opposite. It is people. Oddly I know the power of another base And then down here is that decryption is back to the d which will equal m to the ED which is just m n. And stepped comes out this fact. But we can look at that and I'll get that go back to you in more detail here. If you'd like to kinda like walk through why does that work in the mass of that which more or less this comes from this anything five n is one mod N. So anything to the phi N plus one is itself. Right but that means also anything to the two phi n plus one itself. And anything to the k phi n plus one is itself. Which means that if what I have in this RSA things ended at E if I find some D some modular inverse and e such that d times e is a multiple of i n plus one is one mod five. Then m to the ED is K times five plus one which is one times m which is m. So anything that is one mod phi is going to be itself when I do that exponent. And so the idea is kind of factors something which is one by five. That's the OR is a mapping that you dive that neuron paste or whatever The implementation of this it is said that if you have the n and e is due like how message trauma e comma edge. They DID it's Pao ciphertexts comma D comma n. Anyway whatever might advice of all. That's not delay crack RSA or whatever. So all the real hard part is figuring out phi. Okay so let's go. Let's do. Ten very price out getting to some place. We have a terminal and you assess he SSH key gen RSA. So right now this is our first time looking at something that 30-minute him format format. And that's cool season tools than read that thing. We could do it. More hardcore. Assembly is dizzy ways. Yes well hearing. Oh no actually that in my CRC maybe ESA. But here I hold it explicitly. The RSA key size is 23 Which by the way since the secures AES-128 like the standard who's going up. So even that deal RSA he no longer wants work. Alright so then this next little sort of copy paste or you make this thing on your file or we call it and you put it in the IHI RSA or or wherever omega pack. While all this is saying hey show me this text. So I like really human or whatever. So here's the modulus is the hex digest. The public exponent like pretty good six by five through seven As is always. Now you can maybe start to see why when you see it in binary Which is that often the biggest issue with RSA or all public-key crypto is that it sucks. Sorry is that it's as low as slow as eight and its nonbasic here. And here we are. So the fact that it's really really slow because you're doing like hard core abstract algebra as opposed to like XORs and pitch CPUs and ships and stuff they're made for XORs and missions and and hash algorithms. They are failing or the AES block size is also like that barely made the hybrid that somebody insecure. This is doing like weird abstract algebra simply grouped things and repeated squaring stuff that comes out of my PhD this kind of stuff which is you know we try and make it as fast as we can complexities around like a huge kind of reach or whatever not like the 01 region. So making an In fact there's a whole career for you in doing crypto that is right size. That is built for embedded systems with shooting processors. How did you do this up as fast as you can and she processors. That's a whole career. Said you know you can you have FPGAs sort of low-level things you do to make all the crypto really facts. But the speed and security are always it off. The reason that he is always this one. 1-0-0 One is I may see exponentiation symbol by repeated squaring so I wouldn't be very good square square square square square W1 times do done. So if this were like more complex and if you do more computation things like that. And since so much of the world has signed RSA signatures whatever we need is to be fastness is not. Okay. Here's what I want to do with that Maybe graphs and those parameters now is validate yourself real quick that you have this d p or q. Let's just has that e times d is one by p minus one humanism and it ends. So figure out the DVD that humanity from that feeling there and just validate relationships are when I say Ooh race theory the hex crazy crazy. This is probably the way somebody was working passionately. Yes. But everything in All right yeah all right. So that was generating some real RSA parameters that are reason enough Republicans. And honestly in your like your network security class Every time you go in some server or whatever else you're gonna do that more or less going to generate some public private key pair you're going to put a public key on the remote server. They're going to do a little signature tests with you see lot of passwords like that happens all the time in this world. Oh so here's what I want to do with respirator which we've got 20 minutes to pull this off. I want to form four person teens. For why we're here let's say there's 15 persons in which case that person will be whoever they want to be or whatever I don't know let me personally because least competent to sleep. But those 3D you'd have three so you can join these guys wanted you guys to join over here and then the others will be a five-person team over there. So here's what I want to go for Emerson team on four person team and we'll say this is o each table has a number. So this can be 5317. Once you're never more than one of you guys to take five Situation three sorry. Okay so each of these teens I want the four roles to be the fall and you pick your rules to message send nurse to message crackers. Okay and we're going to do this in three phase or in phase one each sender is going to generate an RSA key pair with modulus length to 40. Here's here's how you can generate one of those nice weak keys. So there's a weak key generator for you. It's a slightly different thing but that that let me get out 200 character. Then the crackers are going to make some little utility functions to help them decrypted the right time. So your job is to thank factoring and getting in five and going from no exponents finding its inverse mod phi. And then calculating like majorly utilities to do thing. Once the senders are ready each sender is going to put out their public key. So what I want you to do in the chat saying you can say something along the lines. Ooh. So we could say banqueting table Sender one and n you can say n equals whatever. Okay here's your tangle with the comment. I will once you guys you're cracking this is that all the time you will. So so once you've got your public key you send it out. Cracker one is going to start factoring sender one's public modulus. So so hope that's a problem We have five teams a nice even number of teens. Now I think I think land and probably be a whole team what she's done this a lot this ECS every weekend. So maybe Mark zeta you want to take land is bought land and you go. Yeah. I think you'll do fine on his own. So now your table six subband and is going to be both sender one center to practice one factor two tables Because that's actually what it's like. Once you've done this enough times it's just like ******* bats. And when it happens it's not. So this is a really hard exercise to tweak just right because if I make the integer two larger network of accurate if it's not large enough backwards really fast I need to factor in just the right amount of time that it takes the cracker is enough time. So here's that here's the race finished. Okay so sales crack one starts taking down sender one's public-key. So you guys are going to be competing against each other. So this is Table five yes table or table three against Table. Seven Table one and against table six. So there's going to be. There's going to be four messages sent it seems and ascendancy message. Sender one's Center wanted to send a message to center to the center tooth public-key sender to send a message sender one with their public key Cracker one cracker two are going to start cracking the opponents message one message two. And and that way there's four messages for each pair. Two et cetera these attitudes lessons here instead of 100 excuse message there. The first team to read all four messages the senders have become history. They know their private-key isn't a crack at the old fashioned way whatever else the crackers or trying to it from the outside to make your crackers and he loved most sprinting script k skills make your centers the ones who are at least competent. Because they should just have the data there. First seeing to read all four messages when Spain. Okay because it makes sense. Any questions All right so each Saturday generated publicly January West. I said yeah we got a he or she is a CEO. So where approximately eight grades yeah there's a hard problems. Are good Yeah thanks by the way. What do you say you're going to probably able center yes we can make it difficult to get planted. And what it. Generally. Yeah. Yeah yeah. Yeah. Yeah. Yes. That's really answer here. Yes I had ciphertext. He says Nevertheless. Contest. One has to know where the format is uniform. So but you don't have the OpenSSL library. You have arts. I've read. The documentation is given to us. We'll get it. Yeah yeah. Yeah. Dewey places. Tabs. You can make any utility function because you have to do it a bunch of times. Let's look at how we get to see that they say are you sending you both connecting some years and years and so it really depends on your setting. And then I'll look at other teeth or trying to crack. That's right. That's right. So you're trying to read your heartbeat. Your graduates are table or I guess you could say well 31 ciphertext came over the center to the ciphertext how kids now table settings graduates to mobile search right right while your partner and so reboot center to center one's message sender wants to send messages. Or uses you can add a crackers you'd like lights and utility. Fashion. Again whatever I guess not. You don't have to worry about shapes like you want your own cells. There we go. Five Sender one. Alright I'll be off or size encoded. It goes through backed her up and say this is a simple. Oh yeah that's right. That's right. Yeah yeah published public-key is important to create the PDF right Yeah that's what makes face to face to the centers now writing messages to each other while the crackers are busy trying to get them to basically know that the private key. So the races can you read it for the practice yeah. That's the only way that it will be ready. Baby injury about you said it was. Never lie are actually done especially you can. Yeah or you just need enough. And yeah I mean I don't know. 06 by 53.. 70. Private exponent is your problem is you can read the message he sends recurrently kills that answer just publish those parts. Yeah. Yeah. What are you doing that you have 1 second to get busy get your probability on their license HLA mismatch. Oh yeah. Let me try this again. Okay table. What is the center of galaxies out go grab that. Grab this major message trace that you do to make your message. If you're not that probably she's like I'm not I'm not. Yeah. Yeah he's got. Jerry tells the story relatively simple. I have Yangtze. Yes you take his turning 20 integer take your message turned that into an integer take message to e by modulus and says okay while i's are you triggered an accurate number notebooks I was already. Paper. Will take what you see here is again. Slash eyes. Yeah yeah. Yeah. Yeah yeah. So how do we now have 34 are more easily seen that shipping in the outbreak
cpeg472-010-20190422-101000.mp4
From Andrew Novocin April 22, 2019
49 plays
49
0 comments
0
You unliked the media.