Digital Signatures & Security Services | Cryptography Lecture 18

[00:00:20]welcome everyone to another early Wednesday morning um let me turn that a little bit down um so um if you um if people fall asleep because they see this picture for the 500 time that's perfectly fine what I'm going to do now is you know usually I write down last week or last weeks and now we step back a little bit and consider what we've done the last one and a half semesters or so as you know this two semester sequence deals with these three big aspect of modern cryptography that means symmetric algorithms what we did here among other things we did death and three death and we did as lots of other stuff mods of operation stream cers BL Force tech blah blah blah blah blah so that was roughly the what first third of this two semester sequence um what you don't know what we finished last Wednesday is we finished asymmetric cryptography so we we're done you know within this intro introductory course um with the topic of astrometric algorithms per se what we did we introduced all three families of of um public key algorithms that are relevant in practice that means RSA discrete logarithm and last two weeks we did ECC okay so we're done with that here's the timeline right again this is you know October you don't have to copy that you can copy but it's won't be on the exam don't worry okay so um and yesterday I looked at the lectures and the syllabus and the layout of the course and it turned out it is in fact almost one thir almost exactly so this was roughly one3 here one third of two semesters is nine weeks here okay that was I think exactly nine weeks here exactly 9 weeks here and this is today okay so this is May 11 2011 okay so we're here we're done with this we're coming from here so what's left we have about nine weeks left or so and we start today with this new area of protocols it's not it's usually not strictly protocols it's a little bit like a protocol aspect in there what's the main difference is from these two areas compared to the third protocol area is we not introduce only rarely introducing new algorithms so what we mainly do is we take the stuff that we did here in the last 18 lecture weeks and try to build stuff with that so it goes a little bit more towards application we also look what are the other things we can do with these with these Primitives primitiv in do okay so these are often called this is kind of a new terminology people haven't been using it for 20 years but maybe for I don't know five or 10 years they called crypto primitive so these are the basic build building blocks right the Legos Lego B here so these are the Lego bricks and now we use Lego to build stuff okay so this is roughly what we're doing and there all kind of different things we do and and and and some things are cool and sometimes it's really surprising we even go back and it's in I think in two or three weeks we go heavily back to the metric algorithm and you know suddenly use triple D and as to build message authentication c a hash function kind of interesting things okay and people that are you know that hate mathematics and hate crypto per se it's hopefully getting more interesting I mean this is also a little bit more towards using cryptography in web browsers and cell phones this kind of stuff okay so and today we actually we start with I think one of the more exciting aspects of of kind of a little bit higher level cryptography today we try to cover four topics namely um want to give an introduction to digital signatures very important topic digital signatures another big big area in which we only treat very briefly here are Security Services whatever that is then we talk about RSA digital signatures that means how to build digital signatures using RSA and maybe and I want to put that in Brackets here um an attack against ours a digital signatures so this is in Brackets because I don't know whether we will have enough time today okay so um also um what typically happens from now on there will be less mathematics there will be less formulas there will be less funny elliptic curve graphs on the Blackboard again it's very often we use stuff that we did before and we put that in a larger context we use that to build new schemes new applications this kind of different different Notions and actually today particular the first the first two chapters a lot of talking okay so if you hate me talking this is the wrong course for you for the next few weeks okay so there's a lot more like understanding concepts as opposed to understanding mathematics or [Music] algorithms Okay jump let's jump to the first section of today introduction to digital signatures digital okay what is it what do we try to do and I always start from a pedagogical point of view the goal the objective the aim of of this whole undertaking today is we want to have something like a signature like signature like function for the electronic world what they mean when I talk about signature like like I mean actual you know signature on a piece of paper and I think it's this will be a pretty interesting discussion the next 20 minutes or so to look what happens when we sign in the real world and in the physical in the paper world and what happens if we try to do the same thing in the digital world so let's first look at a convent what I mean with conventional is paper Okay signature see now you have six semesters right for finishing your Bachelors your one and a half semester through so there are four and a half semesters left and after four and a half semesters you all get your Bachelor diploma right Bachelor of Science in its with your name and your grades okay you get that so it's pretty tempting to photoshop these things right and then you don't have to take the exams with me and you understand the point right so it's it's pretty easy to come up with a faked one and you still get good jobs so in order to prevent that what we are doing as a society and as a department we sign that okay so you get a signature from our department head from Dean right he signs every Bachelor diploma or Master diploma or whatever diploma engineer people in the old program what do we try to do well we say well you can maybe come up with this document in Photoshop but you can't really generate the signature here this is the underlying uh assumption and what why do we do that what is the in in more abstract terms is in more abstract terms the signature here is a proof of authenticity authenticate authentic Au authenticity of the sender sender being the issuer somebody who you know issu that who who creates that out which is our department right or the or university okay so this is what we're trying to do if there's an original signature underneath the assumption is it really comes from this person who you know claims to have created that [Music] okay so and that works pretty nicely in the real world you know you can buy a house for1 million EUR essentially based on your signature which is kind of interesting because they're not really that hard to fake right you know you you can recreate it if I give you my signature and I leave you one hour and I you know give you a fake diploma you could copy that you got the idea but it's kind of interesting but still we can you know buy cars and houses and sign all kind of contracts you know with a with a W with with faking a signature maybe right but of course there's social barriers right and and criminal barriers that make it pretty hard legal barriers but nevertheless so but again it works nicely you know it's very important in a modern world you can you can enroll in University with your signature you can buy Stu stuff and so forth so now it's of course in the old days we only had pieces of paper that was the only type of signature we could issue but now in for instance if you do e-commerce it might be very nice to let's say buy something on the Internet in order to make sure you really bought it you provide a signature so what I'm trying to say it is would be really nice to have a SIM similar functionality for internet type of things or in the digital world or in the electronic World okay so let's try to do the let's try the same let's try the same um digit dig digitally okay so now we don't have a paper document we have an electronic document we have a PDF file right a Word document or latex or whatever okay so now it doesn't say Bachelor of Science in it security Now it says 0 0 1 1 0 1 blah blah blah blah blah blah blah blah okay it's PDF if you open a PDF with editor this is what you see right you really see hex data typically but it's it's zeros and ones um so this is your document well that so what did we do here you know we could probably say okay this is some kind of separation and then we sign it at the bottom okay and what do we do we have some kind of unique biometric thing right we have a unique line with a with a pencil so let's do the same but instead of you know picking this this graph the shrift S I pick a 01 combination really long 1,000 bits so I you know Kristoff par I [Applause] pick you know I choose my own 1,000 bits kind of similar the way I choose my unique signal and put this under put that underneath a document and now from now on every time I want to send an email or PDF document that is digitally signed I put my unique 1,000 bits underneath okay and why is that a really stupid idea why is is that like the most stupid thing I've ever said in this lecture here why is this not working you can copy that mean did you notice like your grandparents when they watch TV they used videotapes and not DVDs you know that not your grandparents but you know me okay so um and videotapes were analog right this is analog and one reason we switch to DVDs and CDs and stuff is they're really easy to copy to make perfect copies so this is really stupid right I put my signature underneath I sent you an email with my signature the first time I'm doing that you get hold of my signature you can make perfect copies right so this does not work that way okay what do we do well and now and this this course this two semester course is not really about making funny you know contract things right but it's about cryptography so maybe we can use something with cryptography and we can you know this whole thing with Ellis and Bob and you know Ellis wants to send stuff and then she encrypts and Bob can decrypt and what makes this thing work is that they share the same key that means in particular on Bob side if Bob has has the correct key if Bob has a symmetric key he's suddenly suddenly capable able of doing certain things for instance to decrypt so if you have a if you have a cryptographic key under certain circumstances you're able to do things that other children cannot do right and and let's try to do the same that means we try to generate the signature here using a cryptographic algorithm in particular with the key and then the idea is if you have the key you can do the signature you know I can maybe digitally sign stuff if I have a cryptographic key if you guys don't have the key you cannot you cannot fake my signat more okay so how do we do that now and that's of course a huge fundamental difference from the paper signature we take our message which let's call that X the document you know like plain text X um we plug X into a signature algorithm algorithm cryptographic function and we use a key here at this point okay and then the output we call Y okay good so that's kind of we're not there yet but this is Hal meter okay halfway towards digital signature algorithm okay let's say we let's assume we do that we would get a protocol maybe this is not a protocol this is just generating a signature okay so let's assume this is the space the universe of all possible messages this is the which is actually called sometimes the message space and this is this one specific document you know this is this diploma I want to Bachelor work there this bachelor diploma I want to sign so what I do from here I have somewhere I have the signature [Applause] space just and what I do you know I use this this signature function whatever that is we don't know yet how that really works and I compute one y point one signature okay so what you see now is exactly the same as you see on the up upper Blackboard just with you know different different schematics or so but now this is only what happens on LS side on Bob side if you wish on Bob side maybe now we if you want to send that what you have to do you have to take both X and Y that means the document and the signature he send that over the channel okay and now it's getting interesting I mean this so far there is somewhat of an analogy to the um physical world you know we have a document we have a message and we have a signature what happens in the physical world at least in Germany mostly is if you're an employee and somebody applies and shows you you know his his or her diplom you look at it and you see the signature from the rural University on it you know from our department head or the director of the university and what essentially happens is they believe that this is correct okay they don't really check they don't really verify okay this doesn't work here right you can't take the document look at look at why and say oh that's probably correct you know nobody would fake that right it wouldn't work which is actually interesting I have um a friend of mine who who studied with me um is married to a um a woman from Spain and um that's different she they actually they had at some point they needed some anen of her diploma and they went and or some translation and they went to City Hall um um okay and so they they needed I think like a translation or something that this is original diploma so what they did they had all they had the signatures of the current University president of the Rector they had in City Hall but this was an older diploma so that wasn't current anymore that wasn't actual so they wouldn't give her the stamp they wouldn't say this is like an original diploma so what they actually did they had a list with the original signatures and then they actually compared you know how does the signature on the diploma look so you can do that but you know mostly in in you know at least in Germany people don't check that okay so but again we we have to do that different definitely in the digital world so what we need here we need and and a fancy word for saying we have to check we have to verify that's a fancy term of saying the same so what we need here is a verification function which is called ver V which again needs us input both the message and the signature that belongs to the message together with a cryptographic key and now there the first question which is I don't know maybe a simple question what is the possible outcome of of of of such a check of a verification what can happen what can the verification function tells us tell us how many bits of information do we get out one bit it's go or no go that's it means either this is a valid a true signature or this is an invalid signature that it's there only one bit of information why I'm stressing that later on you know we we end up using RSA for this stuff so you might again do arithmetic with 2,000 bits and stuff you know very big calculation and square and multiply blah blah blah but the end statement is only go or no go unlike encryption here typically we encrypted the whole message and the cipher text of course 248 bits for instance in the RSA case here we only want to have one bit of information okay so let's formally we can put it this this way so this is true comma if Y is valid [Applause] signature or it has a value false if Y is invalid invalid signature okay okay so let's stop with this okay and we later on this is not the whole truth okay as as as often I'm I'm cheating okay so that we have to add some very important little detail but we do that in 10 minutes okay so now but it's B you know we we're 90% correct or 70% or I don't know we we're almost there but there's some detail missing what I want to do now let's say we do it this way okay and then this is we're almost done with you know first chapter this introduction to to uh uh digital signatures we want to step back and discuss in more abstract terms let's say we build such a system what do we achieve you know what what what did we want to do what can we do now you know kind of what are the what are the more abstract functions that we achieve so this is I call number two that's chapter number two we almost done again we we we we going to come back to this chapter but first let's start with the second chapter because that makes sense at this moment in time um we talk about microphone cable um so what we did so far in this whole course you know you saw my diagram before we talked a lot about algorithms you know we had by now we have like 10 or so crypto algorithms introduced in the last whatever 18 weeks or so what we rarely did is we really we didn't really talk about what we can do with that oh good can microphone again is this okay okay so we switch microphones okay and um we should be online again very good so um what I was saying is I want to turn the uh volume down a little bit um so when we did the algorithms you kind of believed you were doing something meaningful something that makes sense but I was a little bit cheating here and didn't tell you very much what we can what we can use them for actually the main the my main motivation was only one very very simple thing probably the most simple thing you can do with cryptography namely doing actual encryption okay but in reality there many many other things you can do besides encryption and this is what we that's the discussion we we start to do now okay so and these are called security services so um the definition here is the [Applause] objectives the CA in German right the ca the objectives of a security system are called in quotation marks Security Services [Applause] okay and now I want to talk a little bit and and there many there's like I don't know you can come up with a dozen or so Security Services in practice they're not all equally important and what I want to introduce to you now is the four the four most important ones the most crucial ones the one that I'm most often used so the first one I already mentioned before is um um now comes a list of four important Security [Applause] Services where do I put that down okay guess start here okay the first one and this is the main security service we talked about I've never called that security service but now I start calling that security service which is keeping stuff secret you know preventing people from reading that okay and this is called confidentiality okay what is the definition of that [Applause] information if kept [Applause] secret from all but the [Applause] authorized parties this is very fancy terminology for you know this is this picture here we do encryption unsecure Channel we do decryption okay this is I think I did that in the first lecture back in October okay so and and this is the main motiv what's the main motivation I've been using for one and a half semester you know to keep keep you awake is saying this is what we're trying to do we send something over an unsecure Channel as Oscar tries to e drop so we try to keep things confident confidential so what do we do we use mainly symmetric encryption we could also use public key encryption asymmetric encryption right we know how to do that so now let's look to let's look at this protocol here does this protocol whatever we doing here this is the channel here right this is you know Ellis and Bob does this provide confidentiality yes or no no why not it's absolutely right this is X this a message in clear text so so no confidentiality is that a problem no because I never said I want to keep things confidential what I want to do is for this example it's the opposite you don't want to keep your grad secret here right you you know people should be able to read that what you want what we want try to do is we want it to have a proof of proof of sender right so it's not a problem we don't have confidentiality but we don't really want that here and again very often we need it that and so this is kind of almost trivial statement right the next where do we four you know it's one out of four so the remaining three are getting more interesting and actually they're getting more complex so please be awake this is kind of the most important the next 10 minutes are the most important part of of today um so no confidentiality what else can we do number two is message authentication what do you mean what do we mean by that we mean that the center of a message is authentic okay be awake be awake for the discussion that no follows do we have that here that means this is Bob Bob receives X and Y Bob verifies and he gets the statement yeah this is a valid signature so we in this case does do we have message authentication does Bob know this message is really coming from Alice no why not because anyone else could have sent it no no no we we do have this is incorrect this is wrong why do we have message authentication here who can generate X and Y what what does what what do we need to know to generate X and Y the key so that's the underlying assumption you Alice and Bob you know run a key establishment protocol ify Helman or whatever once we've done that and let's assume only Ellis has a key here only Ellis is able to do this digital signing so yes this is given which is by the way pretty much what my signal what my signature does under your diploma here right it's really coming from rural University right yeah it's really coming from Ellis because only Ellis has the key okay so this works so the main objective the main goal is Achieve we're done for today we're not okay but it's when we started out you know what was this goal you see that goal signature like function for the electronic world we have this is a signature like function for the electronic for but we have much more and this is now the discussion that follows now it's getting more and more interesting what we also get on in for again is um message integrity and I put message in parenthesis in clamon because it's often just called integrity [Applause] meaning message has not been modified during transmission [Music] now it's getting interesting here so what happens here this Alis signs the signature and now somebody starts to alter this let's say it's an electronic contract or a bank is you electronic fund transfer and you flip around the bits which can be pretty bad right you add a zero instead of transferring A1 e you're transferring €1,000 for instance that means X gets replaced by X till here okay this what Oscar does okay that means now the receiver Bob has this verification algorithm crypto algorithm and instead of x he uses X Tilla without knowing a verification how that works in detail what will happen here any idea yeah Will false will be false why because this y together with this key belongs to this X and not to the X tiller and you know that we what we end up doing we're doing essentially in RSA encryption later on even if you flip one bit in RSA and then you do an encryption exponentiation you know this spreads over the entire world immediately so this probably fails so yes we do have integrity and now maybe briefly let's compare that to the where we started from you know somewhere there's your overall grade your come then this is important and this is not difficult but it's important okay it's not not as difficult as elliptic curves but it's important somewhere there's probably your overall grade ex not right and let's say you have a 68% which is not good right we don't want to have a 68 this is not good here okay so and you really want to have the job right and you you know so and there's a signatures I already underneath and you know the six and the eight they don't look that different right so you know you could maybe sit down and turn that into an 88 right does this signature protect against this no okay so me what I'm trying to say here is tra the traditional analog piece of paper signature does not provide any type of data Integrity this does okay so even we tried to do something differently we only tried to generate sender authenticity message authentication here at this point we get for free so to speak we got message Integrity which is not bad okay so now comes the most important five minutes of this lecture Nam the four service which is also the least intuitive one so I really need we I need somewhat of a discussion just to explain what we're trying to do here okay um so this is not bad you know so means we have message authentication we have message Integrity now one big application for this stuff is electronic Commerce electronic Commerce meaning buying stuff on the internet okay so um do you know what happens if you buy something at something a book you buy my book you want to give it to your girlfriend for Christmas right so you buy this book Amazon 34 or something okay so you buy the book you order the book you know on on on um December 20th probably right or December 22nd this is when I buy my Christmas presents um your girlfriend splits up with you okay or your boyfriend splits up with you okay so now you have the book what what and you already have this one book right so what what do you want to do and and you hate crypto anyway so what do you do with two books you would like to have the money back so what you do you know what happens with Amazon if you want to if you don't want to have the book you mail it back and you get the money back okay so they're very very friendly okay so but now I want to talk about a different scenarios so we where people don't want to give you your money back for instance if you buy um Volkswagen okay so when you start by buying something really expensive such like as a car on the internet let's see what happens then okay so um this is Alice and this is Volkswagen so this is your car dealer okay what you can do with most cars nowadays with most car website you have BMW called that's a car configurator a while ago it means you can go there you can exactly look at your golf blah blah blah blah blah model and you know add the right engine and the right inside color and the right navigation system and you know everything you want to have I don't want to have you can configure your car okay let's say we do that here and let's say you have a really bad taste okay for instance in in the book I talk about I think you order a pink car which is already pretty um weird with an orange seats or something right like really ugly okay everybody with me really bad taste okay so you order that and it's €2,000 that thing okay you digitally sign that with this algorithm you know Volkswagen and you you have the same somehow you you you run a um run a Diffy Helman so you agree on the same key here you order that Volkswagen can check okay this is an original order it really comes from you know kristofh par or whatever because it's digitally signed and then they start manufacturing the car and whatever three Weeks Later the car gets delivered okay you're back with your girlfriend again right so she sees the car and she says are you crazy right I'm going to split up with you right I'm separating okay this car is too ugly you want to keep your girlfriend so what what do you do you want to do the same trick you did with Amazon okay that means you where am I here Al so you sent the car back he said I don't want to have it this is what what happens with the book before he said I don't want to have the book and Amazon as a policy no question ask they actually give you the money back I think you have to pay for the postage um Volkswagen won't they're not dumb right I mean they see the car say w this is ugly we never going to sell that car again right mean they just lost whatever 10 or 15,000 EUR manufacturing the car that they can never sell again um so what they're going to do they have to sue you for Claren okay to sue they they have to sue you in the court of law and they say here you know Professor p orders that car and he doesn't want to pay and now we getting really interesting discussion here okay so myself or my lawyer there two things we can say we can say oh yeah the first thing that we say well we we never ordered that and then Volkswagen says oh no they did order that because this is the order this is a web form right with the car configurator all the data and this is this why this this valid signature and you know only Christoph P has this key here okay so he must have shown that so and what is my argument at this moment here what am I doing to say so that I don't have to pay €2,000 for a really ugly car and I'm losing my girlfriend so what I I don't want to I don't want to have the car I don't want I want to keep my girlfriend so what do I do which is a legal argument here what is who can fake the Signature Volkswagen there's one other party on planet Earth there's one other per person one other entity who can come up with a valid signature which is Volkswagen and you know I'm I have a good lawyer said well first Volkswagen can do it and in fact they have a pretty big incentive right who unres it to do because they can sell more cars right so Happening Here is the Jud the he can't he can't decide right because the reality is of course I can generate I can I could have generated the signature but Volkswagen could have done too okay so we have this dispute here dispute and there's no way for when in cryptography that's called a neutral third party like a judge a judge cannot decide who has done that right okay and this is a very important security service this is called non non repudiation repi repudiation I write the German terms down this is um either I love those d words right only have a Blackboard long um um theice bite which is simpler provability okay so and what is that the cender of a message cannot deny can and cannot deny the [Applause] creation of the message okay towards a neutral third party this is strictly speaking this is sender non rediation you we also have um re receiver non rediation where where um let's say Alis wants to prove that somebody actually received the message which can be very important too let's say by by a um if you have whatever you have or you have a certain deadline where you have to hand in a document for instance here you know Marcus DM is really strict with you and he really wants to prove that you you know sent the email by 8:30 this morning with your homework assignment so that would be a situation where you want to have receiver underation but right now we we just call that underation for sender non rediation the question is do we have non rediation no we we if if Alis if Ellis claims I've never sent that we cannot prove that because the receiver could have done that the receiver has K that means the receiver FKS in the example before can generate a signature a valid signature here okay what do we do short answer is nothing as long as we stay with symmetric cryptography this is inherent this is an inherent property of symmetric cryptography of symmetric algorithm well why are they why are symmetric algorithms symmetric cryptography why is that called symmetric where's the Symmetry here in the setup what is symmetric herey same key when we talk about symmetric cryptography we mean symmetric keys that means Alis and Bob have the same key that means they can do the same stuff okay that means Ellis can sign Bob can sign Bob can verify Ellie can verifies okay this is inherent here that both parties have the same capabilities non-repudiation this is also this is an abstract look on on things confidentiality message authentication and message Integrity who was the attacker in the scenario when we talked about message integrity for instance we talked about somebody flipping bits here we talked about Oscar okay so one two and three are security services that are needed if the bad guy is Oscar if this a third person okay let's go back to this Volkswagen example who's the bad person in the Volkswagen example Alis right it's not Oscar this is one and this is one of the things that happens in The Brave New World of Internet we want to communicate securely with people you know Volkswagen wants to communicate with its customer base with his customers at the same time the customer may want to cheat FKS log right so now we have a situation with a legitimate communication partner Ellis is not faking something Ellis is not saying I'm Oscar it's not that Oscar saying I'm Ellis Ellis is Alice Ellis wants to communicate but maybe later on she wants to cheat okay so the dishonest party is now either Ellis or Bob and in these situations when Ellis and Bob cheat symmetric cryptography of no help why because they have the same key okay they can what Ellis can what Bob can do Ellis can do and vice versa okay so what do we need to do at this point we have to switch algorithm families right we have to go we have to switch to asymmetric cryptography and there's for the handbook of Applied cryptography which is was kind of my Bible for many years they say at some points they say this non rediation what we just discussed the last 10 minutes is the main reason why we need asymmetric cryptography there's a little bit simplification there other things where public key is good at you know key key EXT for instance but nevertheless this is one huge reason why we want to have public key cryptography so what do we do now we modify the protocol with colors so we go back here so what do we do what we have to do before the problem was that you know if you send if you send the car order to Volkswagen later on it turned out Volkswagen can also generate this car order right and the judge says you know I I can't decide so what we have to do now is we have to provide you know one of the keys becomes the private key so either here we use a public key or private key and here we use the other key okay that's the basic idea we use public key cryptography and now the big big question if you give the right answer it was perfectly fine that you spent 60 minutes here this morning where do we use the private key it's a verification or the signature part who is in favor of signature raise your hand who is signature okay you're right so meaning it's a private key which is private to Ellis that means only only Ellis knows the key that means only Ellis is capable of signing this is exactly what you want to have okay so which key does Bob get which key is used by Volkswagen is the surprise surprise the public key here okay which is also good because we want to make the public Keys easy to distribute right it's on my public key is literally on my website if you go to the website of my research group you click on you know people you click on Kristoff par you'll see my public pgp key okay so this is easy to distribute and this is great because we want to make it easy for people to verify right if you if you get a I can send you an email you know through Blackboard I can send you an email if I want to digitally signed you can verify that and you need my verification Key Well you get that from my website here okay so this is a good setup you know that this is the public key at this the the first great thing is I use a private key here only I only me we I can send uh assign um messages and then the publication is easy because everyone can verify but just don't loading my key from the website okay this is very simplistic and I you know didn't address a lot of nasty attack kind of things but this is a basic idea okay so maybe let's step back for one more minute let's go back to the Volkswagen example now it works nicely again you know you you still have a really bad taste you configure this car orange pink blah blah blah you sign it with your private key this g s over Volkswagen manufactures the golf golf gets sent you against say say I don't want to have that what you really say I never ordered that again Volkswagen drags you to the coure and they and now it's really easy you know now we now you Volkswagen says oh you know Professor P must have generated that because it's this is a car order this is a digital signature I can verify this this is Christof pass public key here at this point and now I'm stuck I cannot say oh no I didn't do it Volkswagen signed it say no because it's my private key only I have my private key you know which is maybe you know buried in my gu or WR new German ID card you can do this kind of things with with with with um no personal here you can provide this and nobody else can including including the receiver of the message this is kind of the cool thing the receiver can verify can say yes this is a valid message valid signature or an in valid one inval valid um but the receiver cannot generate signatures by himself so this is a cool setup can go back to sleep that's that's the important thing for today so now we can actually come up with a basic protocol call with digital signatures so Ellis generates a key pair okay private Ellis okay public Lis all with a a com for no okay um now El assigned something so she computes signature of the message X using of course her private key private key Ellis which yields y actually I call that in the book and let's call that s from now on okay not y she sends over X comma s and now Bob has to verify using the public key of Alis and the input is of course the message and the accompanying signature and he gets a true false statement out of it right either it's valid or invalid okay so and this is and by the way what you saw before with the symmetric setup okay where this was K and this was K so not private key and public key but just symmetric Keys what you saw here this also has a name and actually we doing that in three weeks or four weeks the same picture you know with without public and without these are called message authentication codes or Max okay again we we going to come back it's this is very very useful it's part of your web browsers web browsers heavily use use Macs if you do a secure connection um but this is a different story so we we we we going to talk about that later so now we're done with the second chapter and we're done done okay so now the very nice thing about this topic is in order to build you know what typically happens in the past I introduced maybe gave some motivation to do a cryp crypto system and then we did two weeks elliptic curves right it was really hard to do the crypto system this is not true anymore because we did all the crypto system you'll see now for instance doing oursa digital signature is super easy now which is kind of surprising so all this blah blah blah blah blah Volkswagen Car order this was kind of hard and longish but now actually doing the math doing the crypto is pretty easy from now on okay it will not always be the case but often okay so um now we want to look in a way of realizing that the big question obviously here the big question is you know what is this function and what is the verification function it turns out in the RSA case it's very easy they all kind of different different signatures out but RSA is is a good example so that will be chapter number three RSA digital signature so first we have the um um setup phase what is setup phase in public key cryptography this is mainly Computing the key pair you know public key and private key setups we compute K private Lis which is this parameter D you know this is this whole thing with oos Fe function and you know two two random primes blah blah blah blah blah we're not doing that again you did that in the you know for your first exam you then L is computes for public key which is the modulus n and the public um exponent e okay and now comes the um RS a digital signature protocol and I kind of do that in a similar way we've done that above with the same so what Bob does here is you know he [Applause] has what what Ellis does Ellis has these two parameters [Applause] here she sends a public key over that meaning the parameters n and E now Ellis now Ellis comput the um signature mean she computes s which is the signature using the private key of the message X and now it's interesting how how do we do that okay the interesting thing is you do almost almost The Identical thing or you do the same thing that you do with RSA in the RSA crypto system we we not doing encryption here but he's still doing the same thing you take X and you raise that to the E power modul n okay exactly the same thing we did before okay sorry to the DPA does anyone know why I wrote e there what why I made this mistake what do you do with RSA encryption what do you take x to the X to the E right for encryption you take the public exponent you remember this analogy the an analogy with with the mailbox right everybody can encrypt use the public key for encryption and that's the public key here that's what you do with RSA encryption in RSA digital signature you want to have this the secret here in the exponent right you want to have the secret exponent why is that that was a discussion before for generating signatures you need the private you need the secret okay this is what we're doing here now what you sent over is this is very important is X together with the signature don't send just a signature over with just a signature doesn't mean anything it's just a random to 248 bits now what Bob has to do Bob has to verify that the other big unknown how to we verify and this is kind of awkward to write because this is not equal to something this is just the the process what Bob computes he computes s to the E right you take s the signature raise it this to raises this to the E power e is a public exponent so Bob uses the public key at this point and let's call this result X Prime X Mod n here okay and this is just a computation so what you get out of here is 2,000 bits but this what you really want to have is this go noo statement true false right how do we do that does anyone know here what what what is the thing that pop has to do how does he right now he just computed 248 bits but how does he get the statement this is valid or invalid any ideas not XR he simply has to check this x Prime that's computed is this the same X as here okay so he has to check is X identical to actually we can do that this way okay this is equal to X are not equal if this is the case then we have a valid signature and if this is the case we have an invalid signature okay here comes the proof of correctness let's say whether this is C actually correct what happens here is [Applause] what does Bob compute Bob computes s to the e but where is s coming from s is coming from here s was computed as X raised to the secret exponent so this is X to the D to the E and of course all of that is is um modul n so this is X to the D and does any anyone remember from RSA this is equal to what what is the result of this here is X there was a proof you know oos Fe function in the exponent blah blah blah um that means first raising x to the D's power and then later on raising that to the E power we effectively compute x to the D to the E and if everything works out you get x out again okay this is the same what was inherent in RSA um encryption this can shown to be true um maybe let let's step back and let's see is what happens here when let's say with respect to the security services for instance what about integrity what happens if if you do have a bad guy on the channel if there is actually in fact Oscar and flips bits you know electronic bank transfer and he flips the MSB bit right the most significant bit really bad right with really bad consequences what would happen here what would happen here is um yeah Bob would do the comparison relatively to X Prime and that wouldn't work out any because what what Bob computes here is X x Prime is actually equal to the original X here and but now you don't have X anymore you have X Prime with a flip bit that means it would be in this case here right says these are not equal because so you have you have integrity um you have um of course you have um sender authenticity if this actually checks out if in this case here Bob knows this is coming from Ellis why is that because only Ellis has the private key the correct private key at this point and the third thing we discussed is non rediation yes we do have non rediation because um if there's a dispute you know fight in court if there's a dispute Ellis can prove Bob can show Ellis must have generated the signature here okay so the last thing for today actually we're not doing number four the last thing we're doing is um very briefly it's a very practical thing computational aspect um first signing so this is what Alis does what is the computation Alis has to do when she signs well this is a signature scheme she has to compute x to the E what kind of algorithm do we use at this point here very good square and multiply [Applause] algorithm which is no fun right I WR on costly meaning rule of some D regle Factor thousand slower than as okay doing one as encryption is this let's say takes millisecond this takes 1 second okay it's very rough rule of sum public key is a factor s and slow sometimes the factor 100 it's really slow it's no fun so now it's different for the verification maybe I should write that down so what we do here is X to the D mod n what we do here we do x to the E mod n and it looks completely identical that you do an exponentiation here at this point right and normally of course you use the square multiply but and I'm not sure whether I discussed that there's one trick that you can play did I talk about that when I did RSA s to the E Yeah d s to the e um what you can do you have to do an exponentiation there is no shortcut to an exponentiation but you can use special ease and that's what people do in practice often e if you have 248 bits you're not choosing e as a 248 bit number number but as a two bit number for instance with the value three you know three is really short right or which is another popular value is 2 to the 16 + 1 doesn't know how many bits you need for this number here any ideas no ideas zi in 17 bits okay it means rather than doing a square multiply with 2,000 bits you know scanning each bit starting you know on the MSB bit you only have to scan 17 bits what is the consequence and this is super practical it's implemented in many many web browsers and in all kind of of devices an application that means verification is super fast suddenly we get in the range of as of symmetric cryptography it means digital signature verif fake verification is very fast this is rather slow so it's kind of a kind of an odd thing which you don't have for instance with elliptic curves what you have with elliptic curves they both roughly equal speed here you're faster you may be a factor 10 faster uh uh with signature generation but then with verification you may be a factor 10 or so slower okay so this is specific to RSA whether that's helpful I don't know we're done with selction F Ana no is going to make a brief statement stay with me don't run out okay so I'm done with the lecture you can you can yeah very good