What are Digital Signatures? - Computerphile

i do want to talk about certificates at some point but kind of the way that the certificates work is that they have these really important digital signatures at the bottom and they kind of underpin the whole thing so rob did a video already on public key cryptography which is a really good watch and you should definitely you know check that out so if you recall in public key you have a public key and you have a private key and they're kind of the inverse of one another so you can encrypt with one and decrypt the other one so i can for example if you have a public key i can encrypt something with it and send it to you right but actually we don't tend to do that very often we could do that but encryption with something like rsa is not that quick and for very long messages becomes a little bit impractical there are other reasons as well in terms of the fact that we use these keys for very long time and people prefer to rotate keys more often so these days for actual encryption what we would tend to do is just encrypt things using something like aes and symmetric keys so you use this kind of thing to verify who you are and then move on and establish something else yeah that's exactly right the way that we use something like rsa or the other signature schemes is going to be that we verify the identity of one of the people in the conversation and then we revert to regular symmetric photography right and we'll have done a key exchange or something like this i mean we talked about this in the tls video right so part of tls is a certificate and a digital signature and it only forms a part of the handshake after which we just consider that done and then we move on right um so what is a digital signature right that's i suppose that's the first question in my head i've got this idea of kind of like a bitmap 8-bit version of signing your name right i mean there are obviously lots of cryptographic things that we have to tick off right to make sure it's not forgivable but the idea is that i have a document or a message or something that i want to send you and i want to prove that it was me that sent it and so to do that i'm going to use my private key to sign a digital signature and basically what you're going to do on your end is verify that signature and verify that it was actually me that encrypted it that that's the idea so when we perform this process what we tend to think of is the person that's doing the signing and the person that's doing the verification right now i you know i might nod to rsa or something like this but really this applies to any signature scheme so we have the signer over here and we have the verifier over here right is that a haste verifier i think so yeah okay we've got some document or something like this or message for now let's not worry about how long it is or what it is right it could be a letter it could be you know a mortgage application it could just be part of a tls handshake message it's not it's not really important now this document is not currently encrypted and we're going to send it over to the verifier like this right as part of our conversation right now the problem with that is there could be someone in the middle changing this document forging it this could be a fake document you know we don't know that it's come from me this is over the internet and so when you send something over the internet you can't guarantee that someone um hasn't changed something or done something they shouldn't be doing now if we had an encrypted connection where we knew we had we each had a key that would help but we've still got the issue of how do you do this when you establish the key and during the initial handshake and things like this so digital signatures form a big part of these kind of systems because at the beginning at least you're going to have to prove one of the identities at least otherwise you're going to be finding no one knows who anyone else is and that's going to be a huge problem okay so what the signer is going to do is create a digital signature so they're going to take the document and we'll just simplify for a minute and then we'll build up a little bit of sort of information in a while right and they're going to encrypt it with their private key right and this is basically exactly like bob described right so this will form a signature now they're the only ones that could have done that right because they only they're the only ones that have the private key right otherwise none of this works right if they've got to do it that way they then send the signature over to the verifier right over the internet and the ver and the verifier can perform this verification process so they can basically say well okay what if we take this signature and we decrypt it with the public key all right so this is the signature here what if we do take this and we decrypt it with the public key because remember they reverse one another and then we can sort of work out whether the document and the signature match right because if it was the original document that was encrypted using a private key that original document is going to pop back out again and then we can verify that that's actually taken place if that's a big document isn't this a bit wasteful because you know if it's gigabytes like the video files that i might send is that not a bit wasteful too a huge problem right which is what i've oversimplified it right and everyone watching the video who knows about this is going to be like when is he going to talk about hashing right well now now we're going to talk about hashing um this is this is an oversimplification because the problem is that this document could be any length right and it's a problem if it's very very long but it's also a problem if it's very very short right if your document is literally the number one the encryption using rsa of that with any key is also one right as a sort of contrived example right so signature schemes like rsa don't work well when you have very very short messages and we start to run into problems of computational efficiency and the fact that you're going to have to split the message up and sign multiple bits and then they can be reordered and there's all kinds of attacks that you can run on this so this isn't going to quite work right we want a scheme that will work however long the document is or however short the document is so we're going to mix this up a bit right what we're going to do is i'm going to change my pen color it's all very exciting we're going to insert a hash function here so this is going to be a hash function h right and you know we might use something like sha256 for this now that will take as you know any message length and turn it into a length of exactly 256 bits which for this purpose is going to help us a lot we're also probably going to want to add some padding because typically 256 bits is quite short for this kind of signature scheme so you'd usually sign a longer message than this again you don't know what the output of the hash is going to be if the hash ends up very very small right like in blockchain that could be a security risk we don't take that risk so we take the document and we summarize it using a hash function maybe we add some padding or some other mechanism like this and then we encrypt it using the private key so this this arrow here goes away and we're going to take our private key and encrypt it there instead so now the verifiers process has to change slightly to basically to match so we're going to take the document and we're going to hash it and then we're going to possibly add some padding and perform the exact same process and we can work out whether that unsigned signature which is what we've got is going to match the one that's been decrypted using the public key what we will normally do is ship these both off together in a conversation so as an example in tls you will send a bunch of messages to each other and then at some point you will send a certificate with a that has a public key on it and you will send a certificate verify message in tls 1.3 for example which has a summary of some of the previous messages hashed padded and encrypted using a private key right to verify so you don't actually send the document because the document is the previous tls messages right so you know what that document is we know what it is that we can we have to be checking against basically you're doing a um a comparison right between what you've already received that you've then hashed an ad padding to and then what you receive as the kind of authorization or confirmation that that should be the right thing how do we we know what panning and stuff is that like a system is it like a set that's a great question yes so we would usually use something like the probabilistic signature scheme for rsa right and and these introduce essentially a a formal structure for doing this they also tend to add something like a salt or a random number which means that um messages encrypt differently each time there's never a secret it's just that it it it helps with the implementation and the security we're talking about any document here this isn't the certificate that we sort of started talking about at the beginning is it it could be it could be and often it is one of the primary roles for digital signatures is on the ends of certificates right as part of public key infrastructure now we could spend a long time talking about public key infrastructure perhaps another time the idea is we have a certificate for a server for example backed by a private key you know kept on the server um and that signa that so and that certificate holds their public key and it has a digital signature on it but signed by some certification authority right and tom has covered this in his video on superfish right and this is a huge part of the modern internet it's a huge part of tls mainly because if you remember when you're doing this handshake the server sends a certificate and you verify that certificate by basically looking at it and making sure it's been signed properly by a certification authority that you trust right and the process you use to verify is this right you take the bytes from the content of a certificate you hash them you pad them right or you use a probabilistic signature scheme or something like this and then you decrypt the signature using their public key and you compare them right and if they match you've got a long way to proving that that's a real signature on the end of that certificate and that it's a legitimate server you're talking to the problem with this is we've got to share all these public keys we've got to share these public key certificates we have to have some mechanism where certification authorities sign them and then we can check them and things like this right and this whole sort of structure is called public key infrastructure and we'll talk about that in the next video i actually managed to install it on a windows 98 virtual machine the other day took me back a bit a few people you know the nsa had been looking at this netscape had been looking at this other groups have been looking at this idea of web encryption themselves to click through but you know you try okay the attacker can't intercept the keys anymore not without sending up

Channel: Computerphile

Views: 234,220

Keywords: computers, computerphile, computer, science, Signatures, Certificates, Digital Certificate, University of Nottingham, Dr Mike Pound, Mike Pound, Crypto, Info Sec, InfoSec, Cryptography

Id: s22eJ1eVLTU

Length: 10min 17sec (617 seconds)

Published: Fri Dec 11 2020