CSE 365 F23 11-1-23 "Cryptography Pt. 3"

all right how now can you hear me in the back hear me in the back all right what my thing is oh I see this this not supposed to be what you want to see yeah but if that's where all the good content is exactly who needs those things okay that seems fine right see remember what I said about OBS somebody should fix it this is garbage don't apologize for OBS okay we good we good we can see in here all good all right cool okay we are on the other side of uh Halloween so happy November uh it's definitely way too early for Christmas stuff I can't believe that's already starting uh but I do have I guess to celebrate the demise of Halloween I do have candy so if you answer question no no no you don't get it for free what's wrong with you you only get it for free when your children trick-or-treating you're adults you answer questions and I'll try to throw candy at you and uh then you can get some candy yeah I heard a trick where some professors said that they would uh oh didn't now you evaluate professors and do course reviews like when you're um home but back in my day you had to do it like on paper in class like a professor would pass it out and some people I knew would bring candy whenever those were passed out and just happen to give candy to the whole class on those days I don't know if it works yeah you can throw candy uh depends if you catch it or not yeah you know life's risky yeah can you fabricate questions no no no I ask questions and you answer it's not the other way around maybe we'll see I'm the Arbiter of the candy so whenever I feel like giving out candy answer uh if you have candy I do I don't want you don't want to do that then don't do that also don't randomly throw candy at me if I'm not ready okay supposed to be fun cool all right so we've been talking about cryptography and so somebody refresh us what is the key difference between asymmetric cryptography and symmetric cryptography yeah okay asymmetric does what what's the key difference no no follow that's a followup question to you so yeah I think the key is it's it's different to just say it's not that there is no shared key right there are keys that have to be shared but everyone has essentially two keys a public key and a private key that's pretty good this is going to be a great class uh great okay yeah so you know the idea being thinking of so symmetric for sure there's one key uh that's shared but um why is it showing this part of my screen that's what oh yeah everything is messed up okay you talk to me there you go okay okay all right I guess these slides are fine if you're on Twitch and you're if this looks weird this present presenter view say something and I will fix it yeah yeah I'm looking at it here okay we'll see how that works okay so uh and we looked at asymmetrical asymmetric crypto systems um we saw that we can get all kinds of cool stuff we can get encryption so if we have Alice and Bob they both have public keys they both have secret Keys how can Bob send a message to Alice so that only Alice can read it yeah no we haven't got there yet that's next content in the back yeah so Bob can use Alice's public key encrypt the message to get Cipher text that Cipher text can only be decrypted with Alice's secret key exactly okay you think I can throw this far are you willing to try okay that's good feel like not even halfway okay try I can't do that again I will I can already feel that it's not good for my arm uh you may have to come closer to collect said candy uh somebody make sure you get that one on like row four or five yeah we have not we're GNA get there right next yeah so now we're talking about this as a high level because this is really the key thing of understanding how do I use these systems how do I use the different keys so we just talked talk about encrypting what about non-repudiation so if uh Bob wants to transmit a message and that everyone cryptographically knows that that message comes from Bob what can Bob do yeah you already have a candy okay answer that he would just encryp it with his own secret key okay he encrypts it with his own secret key and why does that help how does then everyone else so if I get that message from Bob how do I then verify that it comes from Bob exactly I use Bob's public key to decrypt that message which I know everyone can do which why it doesn't guarantee um encryption and it doesn't guarantee confidentiality but I'm able to say that this actually comes from Bob okay great you I was just kidding of course you do that um cool yes nonre excellent and we just also talked about this is the more complicated one I want to send a message so let we'll stick with Alice and Bob Bob wants to send a message to Alice such that only Alice can read the message and then Alice can verify comes from Bob so let's pointer pen so I have my message m so Bob wants to send a message to Alice that message M that is both confidential confidential and that Alice will know comes from Bob so the public key of Alice encrypt the message so which part does this guarantee so that Alice is the only one that decrypts it but anyone can do this right so like mallerie or Eve the evil person can make another message message Prime and encrypt that with Alice's public key so the secret key of Bob like this okay so we get that and then so one thing make sure it's correct so Bob can the outer layer of apply uh so that would give you C and so if you then take that apply first the public key of Bob to then get the middle and then the but the message is from Bob to Alice Bob doesn't have access to Alice's secret key on top of it it also encs it with yeah okay wait wait let's Okay so this is from Bob Dallas wait maybe I got confused okay so Alice uses Bob's public key to encrypt the outer layer then Alice uses her secret key to encrypt the message so great okay so we get the message back now if e if Eve our malicious Eve gets this message right gets C what can Eve do Bob's can use Bob's public key and to get so she can apply Bob's public key to get the inside of the public key of A of M yeah and then she could substitute in her own M Prime and then so the problem with this scheme is it's not like the outer layer is not being protected right we can actually go in there and and um um we can't decrypt this so we can't know exactly what's being sent but we can modify it and mess with it right uh and that's the key problem with this approach what we really want to be doing is so on the outermost layer so the very first thing we want to do is encrypt it with the secret key of Bob so Bob uses uh his secret key for the message so this gets non-repudiation so that Alice will know that came from Bob and then on that we want to use the public key of Alice and at this point there's no possible way that anybody can look inside this message at all so there's no way of peeling off that outer layer so that's the way to get there yeah it's uh complicated but important okay so now we can understand oh here uh you actually gave like a couple options can you rapid fire catch all right um so now that we've talked about these schemes what they are now we'll get into how they're implemented and there's several different styles of uh these public private key crypto systems again I'm not a um I'm not like a hardcore math person so I will give you the shape and flavor of why this stuff works but again you can dig into the math to figure this stuff out more what's crazy interesting to me is that this stuff um the concepts of so we we already kind of know what has to exist right we talked about it so we have these public key and a secret key and it should be very very there there has to be some relation otherwise this stuff is probably not going to work but it should be the case that it's difficult if you have the public key to derive the secret key right if it was trivial then you don't have anything and you need to keep that public key secret too and now you're at a symmetric crypto system so the seeds of this idea go all the way back to 1874 um so this says the same difficulty arises in many scientific processes given any two numbers we may by a simple and infallible process obtain their product do you know how to do this simple and infallible process to obtain a product what's that multiplication multiplication oh sorry I was trying to get around the the camera uh multiplication to obtain their product but it is quite another matter when a large number is given to determine its factors can the reader say what two numbers multiplied together will produce the number uh is this billion 8 b616 m460 799 do you know this off the top of your head uh sorry I'm trying to think of more of who asked the question but um it's good uh yeah so one way we could do this so here take a thing oh that was so close all right um guess I'll never be an NFL quarterback okay so one way we could figure this out is try dividing this number by well we don't need to do one will two work no we can already see because it's an odd number yeah yeah we can you can start doing things like that we can maybe do it cleverly but the stupid way would just be trying all those numbers here you think you can catch do you want to try to catch no okay do you want to come up here this will be the candy candy table um okay but one simple way we could do this we know two numbers multiplied together resulted in this number but we don't know what those are so we could just try all numbers smaller than that until we get two numbers that multiply together yeah think about exactly so maybe there are clever algorithms this is the one where head oh so close um but maybe this will boost the twitch stream numbers if I just throw C candy at people apparently not no that would be I don't want you in the video just me but uh that would be a good uh if I was producing this anyways so there are maybe clever ways we can try to do this but fundamentally we we have to try a bunch and we can all agree and we'll see it's actually difficult right the multiplication step is Trivial it took this person in 1874 I wouldn't say two seconds but you know doing lonand doing this out you could do this right you learned how to do this as children in school um and this is what the author continues to go on I think it unlikely that anyone but myself will ever know for they are two large prime numbers and can only be rediscovered by trying in succession a long series of prime divisors until the right one is Fallen upon I like that one Fallen upon the work would probably occupy a good computer for many weeks wait a minute what are they did I just lie to you that this was 1874 and he's talking about computers what does it mean there used be people whose entire job was just to compete the numbers yeah Computing numbers by hands using books and tables and all kinds of crazy stuff um yeah so that's what he's talking about here but just a quick fact check he's not a uh time traveler for many weeks but it did not occupy me many minutes to multiply the two factors together similarly there is no direct process for discovering whether number is a prime or not it is only by exhaustively trying all inferior numbers which could be divisors we could show there is none blah blah blah blah and the labor of the process would be intolerable were it not performed systematically once for all in the process known as this the C SE of aristes thank you uh the result being registered in tables of prime numbers um so this is crazy this is a hint even back in 1874 that there is a mathematical process that is very easy to do oneway multiplication but very difficult to undo when those numbers are prime so [Music] uh this notion and this seed of people that started exploring this kind of finally realized like they could connect these ideas together that's been in math and in number theory for a long time um in 1976 uh Diffy and Helman which we'll talk about published a way of exchanging keys in the secret this is actually like mindblowing that this works it's so cool um in 1977 uh Ron rivest rivest rivest Addie Shamir and Leonard Adelman created RSA made from their initials which is the general public key crypto system uh which is super cool and some interesting things when you get into like who developed what remember we talked about the NSA had Crypt linear Crypt analyst of Dees before that was ever known by the public similarly um the concept of public ke e crypto was invented by a British cryptographer in 1970 uh so I think that's pretty interesting and then in 1973 one of that person's colleagues actually also invented RSA so there's kind of an interesting sub question here of like who gets credit for this invention if we only know about the NSA or the not the NSA but the classified advances decades after they actually happened so the folks on the top the public people are the ones who actually get the credit for inventing these but it's interesting to see that these ideas sprung up and what I also find interesting is that time Gap right between the discovering these things in the classified Space versus the public space it's an open problem especially for somebody like me who doesn't have classified clearance or anything you could think about what's the Gap nowadays is it a six-year Gap like here or is it a shorter Gap longer gap I don't know yeah do you have a guess probably guess still around to I don't know but I bet there are people that know right because it's kind of interesting you can have the people in the classified space they have all the knowledge that's in the public space plus their own classified knowledge right so they can probably estimate how far in advanced they are anyways so let's get into uh Diffy helman's idea of public key cryptography by talking about paint um so is this like a true analogy I don't know I don't know if paint actually paint mixing actually works exactly like this is that true sure I don't know do colors work when you mix them like this like is this a paint this a valid color theory uh demonstration I don't know if this is true but I think it might be two just because it's on Wikipedia but I feel like that's a bad argument in my head exactly okay cool okay so Alice and Bob randomly decided to color but they share in the clear with each other so on the left sorry it'll be more clear as we go on on the left is everything Alice knows on the far left on the middle is going to be every the information that Alice and Bob exchange on the far left is going to be all of Alice's secret knowledge that only Alice knows on the far right will be Bob's secret knowledge that only Bob knows and on the bottom is is everything that mallerie knows because mallerie can watch everything that happens in the open but you can't know about anything that happens secretly that only Alice or Bob does make sense and don't worry you can still follow this even if you're like color blind and stuff I think these colors are color blind safe so randomly decide on an initial color let's say it's yellow they exchange that with each other they then both randomly decide on a different secret color in Alice's case it's like a orange if some like had one of those giant box of Crayola crayons as a child and remembers what exactly those colors are I if this like a burnt orange or something or this is a cyan for Bob I'm sorry I'll probably just use orange and blue but you feel free to suggest better ones but Alice generates an orange like Color Bob generates a yellow like color teal teal sorry did I say yellow yes oh sorry sorry sorry I was looking at the yellow one when I was talking okay yes the blue teal like color and then they combine those so by using the public information the yellow Alice combines the yellow with the see the problem is it's a different color on the there than I'm seeing on my thing so uh whatever the yellow with the orange to get slightly lighter orange Bob adds the yellow plus the teal to get I say perrywinkle is that a good guess like a light light almost like a lilac blue it looks perwinkle on my screen thank you very much dark sky boo okay anyways looks like see they say baby blue on Twitch so I think I'm correct okay a bluish a lighter is bluish color that is definitely different from that teal and then they share those colors with each other so what does mallerie know at this point that Alice this color Bob has this bluish color Yes Alice has the bluish color Bob has Al sorry Alice has the orangish Color Bob has the bluish color and they each know each other's one that they just share so then now the state of the information is that Alice has knows about this bluish color of Bob and and Bob now knows of this orange color of Alice and mallerie knows all three colors what's the piece of information that mallerie does not know louder yeah doesn't know these colors right the dark orange for Alice and the cyan teal for Bob yeah oh these aren't keys we're talking about paint yeah which [Music] color so right so this um you could maybe yeah the problem is how do you subtract paint colors I think it's like fundamentally a difficult thing to do we'll assume for these things I don't know anything about paints or colors no no no it's physical paint it's not anything with colors exactly it's very easy to mix paint together it's hard to separate them into what what exactly I missed because it mixed because it should be I think there should be multiple pairs of paints that could get you to similar things and uh so just buy that argument and then everything else follows um yeah we'll show how you do this with actual map that's that's the cool thing but for now we're just talking paints um so now by combining Alice and Bob can both this is the magic part Alice and Bob can both combine their randomly generated one with so the orange the dark orange plus the light orange plus the I'll say baby blue and get this super muddy brown color Bob can also combine the cyan the light blue and the light orange to get this dark brown color and it's exactly the same color that they're both able to derive so we've reached a state now where mallerie can't combine any of these colors together in order to infer and get what that what each of them has separately derived so you reach this crazy state where Alice and Bob now know something that only they know that mallerie cannot know when they've only exchanged information in the clear it's kind of crazy huh and this is the whole thing that this entire scheme relies on and now for instance if this brown color was a AES key now they've collaboratively derived exactly the same AES key that they can now use to encrypt some communication and start a secure uh message but mallerie can't derive that same key with the information that she has or rather than say can't I think the proper thing is it's comput we create the system such that it's computationally infeasible for mallerie to do that questions it's kind of like insane that this works and this is why so the other important thing this is why this is like one of the first public key crypto systems because it's not a true public key crypto where you have a public and a private key but you can see that they're able to derive a shared secret that only two parties know by only transmitting public messages so this you can see can be used to generate that key that can be used for symmetric crypto we'll see that RSA is a general purpose public private key crypto system okay now to talk about to get some intuition about why this works we now need to uh think about uh we're going to look at some math of what's actually happening behind the scenes Okay so uh little bit of math refresher communative property on some type of operation any type of operation it seems like I don't know when was the last time you saw this on like in a class 230 wait math 230 yeah yeah like a math class is it like a discret math or whatever is like math for computer scientists or something yeah right or you probably actually learned this all the way maybe I think I remember learning this like back in algebra right where you learn about the property and you're probably at the time you're like why the heck am I learning this stuff I'll never it'll never come up again uh spoiler alert so okay so we have several operations that are communative and some that are non-c communative right so subtraction you can't just swap the like the order that you apply them in matters um division matrix multiplication but integer addition integer multiplication and paint mixing oh good are all commun operations that we have stated in our paint mixing World okay now we need to talk about another operator that I'm sure you love and now I'm going to fix this slide because we just talked about it on the way here the other ones it's correct because they're 13 okay so the mod operator somebody remind me what that does who hasn't had candy yeah you divides a number by another number and gives you the remainder yeah you think you can catch a star first that was perfect uh okay yes and in principle what does this do so the result will be like how does this affect the range of the result yes yeah so the results only be Z through 11 right okay cool when have you used the mod operator when programming is it useful wait somebody raise the hand and tell me when you oh you you were noding yeah I Okay cool so factors uh what about any other cases yeah use it to find out if a number is even or odd you mod two and that giv you a one or a zero yeah awesome you can also use it to restrict ranges of things right right so if you have a um do a circular buffer like that's a size of 200 or something you can do mod 200 that way you know you'll always stay within those that size cool and we can think about it like a clock you ever thought about a clock as like a mod 12 it's kind of what it is right when somebody tells you like mimia 1300 hours what time do they mean on a clock like this yeah one right um so we have 0 1 2 3 4 5 6 7 8 9 10 11 all of these now we'll look at a different kind of clock so this is the clock that we're normally used to thinking about in terms of mod now it turns out and the why does this happen Adam I don't know this is all mass stuff um so if you have two numbers that are Co I believe they is the requirement that they're co-prime or they're both Prime Seven and 13 doesn't have to be co-prime they just need to be two random and the smaller one is the this one right to a generator which has see exactly crazy Mass stuff so um so we can Define I can probably pop forward and check here but that's okay anyways that will tell us we'll get there eventually Okay so sorry I'm jumping around okay what this does so now we have n so 7 to the N Mod 13 everyone know what exponentiation is Right seven to zero is all together now one seven to the one is seven 7 the 2 is9 49 after that I don't care I don't know it's too much too big uh but but you could take each of those results and Mod 13 so we can do that right so we can do 7 to the 0 is 1 Mod 13 is GNA be what one and two so or to the so that was zero so 7 to the one is seven Mod 13 is what seven uh 49 Mod 13 is turns out to be 10 if you do the math you don't have to do the math that's fine and so you can actually continually do this from 0 1 2 3 4 5 six seven all of the numbers up there and what you'll get is now you get the same mod type operation where the results will always be from 0 to 13 where's zero on here Z can't zero you can't have zero interesting fascinating oh this does that make sense oh because it'll never be uh interesting okay got it wait why was there sorry you guys can't see the stream but balloons just shot up on the stream it was very weird on my camera okay I think it's the yeahi going crazy okay so the results in this case will then be one through one minus the thing so we have one two three but and this is the very very very important thing unlike this modulo operator where everything the result was exactly one more right 0o one two three now you can think of this as this essentially randomizes what the next number is we have we have to like do these calculations so 1 7 10 5 9 11 and I believe we can then use this uh to do math here on this beautiful uh our beautiful friend Mr clock uh 7 to the end Mod 13 um yeah so oh good we have it all here so so zero would be here one is seven five is 11 -2 is four and if we do one + one oh great is that uh okay I don't recall why this is important why is this important do addition and multiplication yeah okay great so yeah we can do just like before we can do addition multiplication all on this table moving around at different points and so we can actually it turns out use this property in order to actually implement this divy Helman key exchange cool so steps of the operation are Alice and Bob agree on some p and g where p is prime so p is going to be the mod so the requirement is this this uh mod has to be Prime and G is a primitive root module op what the I don't remember that just means it literally has that property you get all thees oh perfect okay so it looks something like this that you get all 12 in that Circle see cool then so this is that information they Exchange in our example the yellow paint are these two numbers then Alish chooses a secret integer a to send Bob G to the a mod P so Alice computes that operation so looks at her clock and says okay where is this number great send that to Bob Bob chooses a random secret integer B sends G to the B mod P to Bob so similar thing calculates where on Bob's clock and and sends that result so these are all sent in the clear so mallerie would know PG capital A and capital B Alice then computes B to the a mod P so takes B raises it to the a mod P that gets s and Bob is able to compute the same secret taking Alice's secret raise to the B mod P and why this works so this is actually like I guess incredibly simple math uh of why this works so what we're doing here right is taking B uh let me draw pointer so wait this is g b yeah so this is a so a capital A to the B God mod P right so just taking this which is this is s so expanding out a gives you g to the a mod P to the B mod P uh B can go into and pass in here so this is the same thing as G to the ab mod P and because we can uh multiplication is communative we can swap those so we can do G to the a * B mod P and with that we can then take a out and this is g to the B mod P raised to the a mod P and what is this inside here what B yeah Big B right Big B to the a mod P which is what what's Big B to the a mod P yeah yeah it is but what in our in here what is it s somebody said it it's s yeah so on both sides here you get S right you get here you get S is B to the a mod P and then we do these Transformations and at the very end we get B to the a mod P which is the same as s and so this shows that they each derive this secret s and I believe this all deres on the fact that it's very very difficult if I said uh if I said okay I have 7 to the [Music] 012 Mod 13 if I am multiplying this number times this number that would give me one two three four five six 2 * six would be 12 so that would go here I think two this one the very top one we want me to count all of this oh yeah this is six to 12 yeah that makes sense so it goes up here the result would be one but if you knew just the result was one it's difficult to know which of those I multiplied together to get back because it's a giant Circle uh you could try each of them but if this circle was incredibly large with a lot of numbers in here it would take you a very very very long time to try all of them which is why this is an example where we show you because we can do the math very easily um but real systems have to use large very large numbers so we can now apply this to our paint mixing analogy and so in this case Alice and Bob both agree in the clear to use 23 and five uh this would be so 23 would be p and five would be Q so P this is the mod operator and so it's five to the N mod 23 is going to be the scheme that we're using so they will randomly choose an integer so seven and 10 they will perform the addition so here we have 5 to the 7 mod 25 23 is equal to 17 Bob calculates 5 to the 10 mod 23 is equal to nine so we can see the linkage between the colors here right so this is how they're able to derive and mix the paint if you will then they exchange those numbers with each other so they send each other uh 17 and N so they both know that now they combine these so they do 9 to the 7 mod 23 is equal to 4 and Bob does 17 to the 10 mod 23 is equal to four and that's how they're both able to get the brown numbers but mallerie with using the information that she has cannot calculate what that secret value is without trying all the values questions this is nuts right and this is like one of the basis of what all of our secure Communications is based off of which is also nuts like in its simple quote I guess simple is a relative term but it's simple-ish mathematical properties like these that we able to identify and prove and then actually use it's you don't think it's proven interesting yeah ah yes uh no the answer is there not uh this I think Diffy helmet is still used if I remember correctly it's still used for forward secrecy um the idea being so we'll actually look at SSH Keys SSH Keys currently you can use RSA which what we'll talk about which uses primes and prime factorizations um the problem with those is actually I guess the uh is quantum Computing so they have theorized Quantum algorithms for factoring Prime numbers and that severely you have to significantly increase the size of your RSA Keys uh to make those theoretically safe and so we've actually started moving to elliptic curves which have similar properties to this and with prime factorization but as far as we know elliptic curve uh the elliptic curve constructions can't be uh defeated easily by a quantum computer as far as we know yes and that's why exactly because the as we'll see right or as even our D of like how we talked about public private key right so um our adversary Eve can store all the messages that she sees and then try and knows public keys so she can try Breaking All the public keys to get the secret keys and if she has a very clever way of doing that that we don't have access to then she can now go back historically and read all those messages um so Dy Helman I believe is you used to do some forward secrecy to say that like even if the SSH keys are broken or the RSA keys are broken we still have some guarantees there sorry people had hands raised while I was talking about Quantum stuff yeah so about the Sayes ellip uh yeah elliptic curves I don't know anything about them except for the things I've literally just told you so but you feel free to ask I was G to ask yeah great question I don't know smart people think about these things yeah cool so now we can look at RSA so this is the Diffy helmet construction part of what you're doing in your assignment is actually building this and doing this and you can see it's actually not crazy math I mean this is just you're using very simple Primitives um so with RSA now we have we'll see we have a more General crypto system a public key crypto system with a public key and a private key and you can generate RSA Keys yourself uh any anybody does anybody know off the top of their head whether their RSA key or their SSH key is RSA so it'll have a I think if it ends in like idore Ed whatever is a or EC is a litic curve and if it's idore RSA something then it's an RSA key yeah so you're using this stuff all the time to access the servers cool so RSA key generation so first and this is generating the keys so this is now answering the question so Diffy Helman right the whole point of that like you have to have an exchange right you have to have another party that you're working with to derive some secret right but that's not a general purpose crypto system so for RSA what our goal is is to actually be able to generate a public key and a secret key that are linked but it's difficult to generate the private key from the public key so to do that first you have have to choose two distinct prime numbers p and Q uh the other cool thing as you get into crypto everything that I'm saying like is a thing that must be true right these are two distinct prime numbers um you'll look at ways that you can break them if these things like don't hold so you can show that like if they're the same prime number I'm sure there's like massive problems to that there's also massive problems if if any of these stages so very first thing we do just like our friend back in 18 70 something I really wish I had memorize that off the top of my head that would have been so cool 1874 I was super close though that was it was like two two years off we can compute this right so we can multiply numbers can computers multiply numbers yeah computer's real good at multiplying numbers even large numbers even numbers with a thousand digits it can still do it right it may be slower than just multiplying two 32-bit numbers which you did in the assembly uh levels but you can still do it so the whole idea of this scheme is that if you give n to somebody it is very difficult to figure out the factor into p and Q right just like our friend back in 1974 said aha it took me five minutes or whatever actually did he say exactly how long it took uh yeah it did not occupy me many minutes to multiply the two factors together but he thinks in his time it would have taken people weeks to try to figure out those numbers so what we can do and our computers can do very quickly it should be the case that is very difficult for people to do that so okay cool okay okay there also some other ones but it's pretty easy uh yeah this is just saying that we can easily calculate a to the E mod n and we know that P and Q are prime um so we can easily satisfy this it's just saying that calculate that is easy but if we have C and N calculating a going backwards from this is hard that is the other requirement okay so we calculate another number M so we have P minus1 * Q -1 we choose an e between one and M compute e to the ne 1 mod M and that gives us D we can do this easily because e * D is equal to 1 M we finally get our public key which is n so n we can't derve p and Q from and d and our secret key is going to be n comma e so we keep e to ourselves D is derived from E here so the idea being given n because everyone knows n it's hard to get back to p and Q and given D it is difficult to go back and derive e cool properties now how do we encrypt things so Alice wants to send a message M to Bob Alice now we can actually dig in rather than using our public Keys just as these kind of blobs uh and say like oh we just performed some stuff we can actually look at what that stuff is so Bob takes the private key sorry the public key of Bob which is n of Bob and D of Bob and we need to somehow then turn the message into an integer this is like a key problem we're gonna be using exponentiation and operating on that so uh and this number M must be uh between zero and NB so there is a limit of I think exactly what you can do here but again a lot often times we're not going to try to encrypt the whole message M we would encrypt some AES key or something with with public key crypto and then also send the message encrypted with a symmetric encryption all right Alice does m to the D mod n and gets C so Alice has the message M Alice uses n in there calculates m to the D so D of V mod n and gets C so now we have our Cipher text C Bob gets C to the E mod n using his e that he has secret and the N that everyone knows and he's able to drive the message so Eve has C the public key of B the public key of A but because of this properties that this crypto system uh and because it's difficult to factor these Primes Eve it should be computationally infeasible for Eve to derive the message from the Cyber text cool okay okay well anyways this is what I just said so I've been hinting at this all along uh so we need to be able to send numbers but like we don't want to send numbers we want to send messages we want to send arbitrary size things we want want to send a one gigabyte file right that one gigabyte file is for sure going to be less than your public private key does anybody remember know the size of their public or private Keys yeah it's like actually we can look at mine not my private key of course that would be very very very very very bad um but we can look so we can do lsla SSH ID RSA Pub so my public key is 394 bytes my I do have [Music] a an elect a curve key and that's 97 bytes cool can I show you this key yeah because it's a public key it's actually on my GitHub you can actually see these keys will I cat it for you right here no because it's very trivial to make a mistake because uh this is your private key and this is your public key so it's super easy if you're demoing something to type in cat Tilda sl. SS AG _ RSA uh tab enter and then boom now your private key is everywhere so something to be mindful of and is a terrible design decision of the SSH clients that they do this yeah then I have to change it like everywhere yeah there's a I guess technically my private keys do have passwords so there's another layer on top of that but uh so you'd have to break my password first but like I just rather you not have it in the first place Okay cool so all that mass leads us to a place where we now have a crypto system that we can use to send messages to each other but we actually hit a little bit of a problem right so I had said well we want to show and demonstrate um non-repudiation but to do so we had to use our secret key on the entire message right but do I want to do that with a key that is then used to decrypt something like then the message itself is actually encrypted and it's not in plain text and anyways that turns into a lot of problems so we have another giant problem that we've talked about of message Integrity so how can I guarantee and demonstrate to you that the that a message has not been tampered with why might this be useful in what cases yeah verify that the message is coming from the correct Source how would you do that so you maybe verify get a message from the source that says hey this is what I expect the data to be and then get the data that says this is the data for instance yeah what what situations may that be useful yeah there's inters yeah so for instance uh anybody install any software on their computer anybody run Linux or anything like that use a package manager yeah guess what you're actually downloading packages from not always from if you're using Ubuntu you're not downloading them from Ubuntu there's a whole network of people who uh will run servers and donate bandwidth and dis space to host these packages but then if you think about it that's insane you have your computer you type app getet install emac you connect to some random server download that package and just run it on your computer so now you've installed some random thing so that seems like a terrible idea right because how do you know you want your computer to know and verify that the stuff that you're installing is exactly what the people intended uh so this is another case where Integrity may be important maybe it's not necessarily A man in the middle maybe you're Del like if you think about this this uh like content distribution Network and they call it mirrors right you have servers that are mirroring content how can you trust those other content and those other mirrors so we really want uh and the other question is um for The cryptographic Primitives we've looked at one of their main properties is if I'm mallerie and I get a message and a bit is flipped in the message in The Cypher text you cryt it it's going to be completely gibberish now how do I know the case between the senders actually trying to send me random looking gibberish message versus it's actually gibberish right like so I get some Cipher text so if you think uh we have Eve in the middle Alice is sending an encrypted message to Bob it doesn't really matter which system mallerie flips a bit and sends it on Eve Alice decrypts it and says huh Bob must be trying to send me something weird or maybe it was a key that they're trying to exchange and now that key is corrupted and completely different um and the question is how do we know so this is where we get into the concept of the notion of cryptographic hash functions so these are super important to understand how they use uh we'll be seeing I think hopefully that how this can be used in authentication and and identifying users um um in password checking checking and verifying and authenticating a user um but fundamentally what a hash function is is it a it uh takes arbitrary input so any size input and produces a fixed size output so let's say uh GNA try to remember one off the top of my head the shot I guess an easy one would be shot 256 that's 256 bytes on the output um so any data you give me shot 256 produces 256 bites so how could this be useful so let's say I have this magic box that does this yeah so hope hopefully if I send less data right so if I if my input data is a thousand bytes and I get a specific bit string 256 bytes output if I send and remove the last bite hopefully I get something completely arbitrary like completely random to detect that something changed right also if I flip one single bit I would want different hash output would it be useful if I just take the first 256 bytes of the file the data that you give me so you give me arbitrary data my hash function is I take the two first 256 bytes and give that to you as the hatch is that good or bad yeah I can't throw that thing to you again but you can answer yeah it's very bad because it it allows people to add stuff to the end all the attacker would know as long as I don't change the first 256 bytes then I'm good and I can just modify things later um so some of the properties we want um so I guess think about it conceptually right and arbitrary size input Magic Black Box fix size output will there be the case that two inputs have the same hash output yes no somebody want to make an argument for either possibly the output is smaller than the input so what is our input size does it on the thing arbitrary arbitrary input and fixed size output so will there be collisions yeah yeah it must be I don't this I think it's pigeon hole principle or something but uh uh yeah fundamentally if you have arbitrarily sized input so if you have 256 bytes that is what two to the to the eight to the 256 or something I don't know that's a lot um or it should be is that right 8 to the 256 how many bits is that6 eight to the 256 two 26 two to the 256 no no no that's bits is it 256 bit yeah I kept saying bite okay anyways uh 1.15 time 10 77 so there's a lot of possible inputs but I know if I keep applying that many right at a certain point there will be some kind of collision um uh other important property is we want it to be a one-way function in the sense that it is very easy to compute the hash and and fast but it's very difficult to go back so if I give you a hash it should be very difficult for you to tell me what input generated that or to another way because there are collisions to easily find another input that hashes there this is actually can be used to um people to timestamp making statements uh Twitter was good for this you could post on Twitter a hash and then a month later like if you have a prediction for who's going to win the World Series you could tweet that now take your message hash it post the hash and then after the World Series be like I predicted this look because I said this and it hash to this and I said that four days ago um and assuming that it's very difficult to go back or to calculate a collision um yeah one key thing I hope this is clear it needs to be deterministic when I say function here at the top it's not just like a function you write but a mathematical function so the output only depends on the inputs um and the other property we really want is that a small change in the input just fundamentally changes the output so you change the input a little and the output changes dramatically if we have something like this we get really great properties so um as we talked about and saw public key and asymmetric crypto systems are expensive we didn't really talk about that but the exponentiation on large numbers is actually pretty computationally intensive um and so Alice wants to make some statement M that everyone knows is from Alice and let's say m is very large now that hash reduces that output and so now Alice takes a hash of that message the output being 256 bits and she encrypts that with her secret key and this is what we call like the signature of M so Alice now has a signature of M and the message M right which kind of makes sense because what was the purpose like why do we want to encrypt M with Alice's secret key what's the point of that louder verice yeah just to verify that it's from Alice right so every single person should be able to get Alice's public key decrypt the message to read it well that seems like a waste right we we want everyone to see the message so we send the message in clear text but we also append uh add the signature of the message so that way anybody wants to say hey did this come from Alice they can take the message hash it and then take the signature apply Alice's public key check the computed hash and make sure they match and if our hash function is good then we can be C reasonably certain that it was difficult like nobody else was able to create a message that hash the same way yeah so Bob can then check hash M and hashing m is way way way faster than doing public private key crypto stuff on him and this is exactly what so we go back to the problem of your um umuntu distributions installing packages this is exactly what happens your umuntu system has keys of the maintainers and it will and also they publish a signed hash of all the packages so that way when your machine can downloads a package from a random mirror it can do this exact not can it does do this exact process in order to stop somebody from manipulating with the packages it's pretty crazy the stuff like in action all the time bless you cool so now Bob yeah at this point we're not the same situation as we had for non-repudiation so now a Bob knows that the message M that Alice tried to send is this what she intended and she knows it Bob knows it hasn't been tampered with there's no M Prime so what would happen if Eve sat in the middle between Alice and Bob and altered M to be M Prime what would happen yeah louder no exactly so the hash of M so now the hash of M Prime will be different than the hash of M so the signatures won't match right too people the way all right thank you okay cool so exactly so the altering the hash altering the message either way right so there's two things that that Eve can do Eve can either change the message or Eve can change the signature right can Eve change the message and put her own signature there so Eve generat some new message M Prime calculates the hash of it encrypts that hash with her secret key and then gives that to Bob I mean signat would mat up signature right Bob only can validate the signature based on what he gets so it would be he Tri comparing the signature yeah so what let's take it step by step so we have uh so Eve gives the secret key of E on the hash ah I should have just used h of M Prime and M Prime so Bob gets this or Eve changes it Eve thinks this comes from Alice he gets it what does he do yeah tries to decrypt the signature but what does he use to encrypt the signature Alice exactly Alice's public key so he'll apply Alice's public key to this and what will that decrypt to gibberish garbage and the hash will definitely not match right he'll has message M Prime try to check it it will definitely not match um or it would fail the signature usually they have some sort of validation so you can tell like oh if you try to decrypt something that was encrypted with a different public key anyways yeah the point is by doing this if now Bob can also verify that this was definitely message sent by Eve if he has Eve's public key right but he cannot be tricked into thinking that this message came from Alice because he cannot pass the signature validation process for Alice cool questions on this yeah so signature here we're just defining as uh hashing a message and then apply your secret key to it yeah which is exactly what if you see something's been signed like digitally signed I guess depending if that's sometimes a marketing term but like with public private key crypto actually involved that's what a signature means yeah cool oh cool and we can use uh we use a hash function all the time literally any website you log into is using hash functions uh we use it for file or message Integrity so just like we said in terms of communication password verification so this actually is a different property this is using the property that the website wants to store your password but doesn't want to store your password right what the website actually wants is to check if you know the password that you gave earlier but the website doesn't want to know your password because if they get compromised then everybody knows their password so what they do instead is is you send them your password they hash it and they do some other things to it that we'll talk about later and then store that in the database and then later on they can verify that it's you because you give the same input that hashes to the same thing but when an attacker compromises the database if it's done correctly it should be very difficult they can't go easily from the hash to the password unfortunately as we'll see uh what they can do is just guess passwords so they hash password and look for all the passwords in the database or hashes in the database that map to password and they will find people as people do this anyway uh proof of work so all of the crypto stuff most of it runs on hashes this is how Bitcoin actually operates under the hood um it's actually trying to find hashes that have a certain number of leading zeros and the number of zeros corresponds with the difficulty of uh the finding the block so each block that they find this is what mining is literally all about is just finding based on the current pool of transactions you find some random value that you X you hash all together that gets a certain number of leading zeros and the first person to do that within roughly well the first person to do that which usually uh the network is made to do happen roughly in 10 minutes uh they then tell everyone else and they give themselves 50 Bitcoins as part of that transaction and that's how or I think now it's 25 is there still mining fees or mining bonuses I think so right it's built in the protocol I don't remember yeah there's a limit on how much yeah thank you okay cool also anybody use git yeah have seen random character is heximal strings those are hashes so git is all done based on identifying data so it is a h a commit is a hash and it does that to represent a set of changes so what gets doing under the hood is you say I want to change these files and commit it it takes those changes hashes that so that that way people can't rewrite history and stuff and you can easily verify this stuff anyways we will continue on to Hash functions on Monday today was Wednesday right okay and uh if you didn't get any come take some wait a second than you anyway yeah