Public Key Cryptography and Digital Signatures Explained | IT Security Lecture

[00:00:06]and today we must finish this topic getting it's longer than I hoped and I've given you if you haven't grabbed a copy there's this a sheet floating around just a one page two side sheet which summarizes a lot of the things that you need to know from this large topic this large topic covers many different subtopics we got on to public key encryption where we have a public and a private key so we generate a key pair each user has their own public private key and we use algorithms such that if we encrypt with one key we can only successfully decrypt with the other key in the key pair that's how the algorithms are designed so if I take some message I encrypt it with my public key then the only way to decrypt the cipher text is using the corresponding private key and usually they work in the opposite order as well that is if I encrypt something with a private key then the only way to decrypt is using the corresponding public key if we use some wrong key some other key then when we try to decrypt we'll get an error and we'll be able to detect that similar with symmetric key encryption when we encrypt some message with a secret key we can only successfully decrypt with the same secret key if we try some other key then we'll get an error and those assumptions or those basic uh assumptions are listed and I'll return to that handout in a moment are listed in that handout so with public key cryptography every user has we assume generates their key pair and that's one the first task of your homework generate your own key PA we'll use it and we can provide two main services with public key encryption confidentiality and authentication remember confidentiality is making sure that no one can read the contents of the message I send a message from A to B I don't want anyone else to be able to receive or read that message that's keep it confidential authentication is send a message from A to B I want to make sure from B's perspective that this message came from a it didn't come from someone else pretending to be a and no one modified it along the way so two different aims one keep the message secret or confidential the other make sure the message we receive is is uh authentic and we generally can do both with public key cryptography and we see by using the keys in the opposite order with confidentiality the idea is that user a to send a message to b we encrypt with a we encrypt with B's public key why well our the nature of our public key algorithms is that if something's encrypted with B's public key the only way to decrypt is using B's private key and the only person who has B's private key is B so the only person who can decrypt this Cipher text and get the original message is B no one else can find the message so that provides confidentiality if use a c intercepts a cipher text to decrypt they need the private key of B but by definition that must be kept private so that provides confidentiality encrypt with the destination public key so if you want to send me a secret you need to know my public key and you encrypt using my public key of course that needs to be made available some somewhere I I publish it on a website or I give it to you in class or we distribute it across a network in some way the other service authentication we don't care if someone sees the message in this example what we care about that b can confirm who who sent the message so in this case The Source encrypts the message with their private key to decrypt to successfully decrypt we need the public key of the source public key a to decrypt that's here and that means if it successfully decrypt with the public key of A that implies the message must have been encrypted with the private key of A which implies it must have come from a because the only person who has the private key of A is a and that provides our authentication if I decrypt with a public key of A and it doesn't decrypt successfully then that implies that it was not encrypted with the private key of A or it was modified along the way and that shows from the receiver that something's gone wrong it's not authentic if an attack pretends to be a but encrypts a message with private key of C sends it to b b thinks it's from a will try to decrypt with a public key of A it will not decrypt successfully the receiver will detect that and assume something's gone wrong so since a is the only one with a private key of A then this provides authentication and in fact this is the most practical way where public key cryptography is used it's not not used so much for confidentiality but it's used mainly for authentication and we'll see that leads to signing something there are different algorithms for public key cryptography the main one is RSA but there are others RSA maybe has been around the longest and the most widely used and you'll see in the handout that one of the principles that uh is often applied in security is that uh you you gain more trust in algorithms that have been used more so a new Advanced algorithm that's released last year may be faster we may think it's better but an algorithm that's been around for 10 20 years and been used and analyzed we may consider more secure so something that we have experienced with we generally trust more because security is complex and people need to do some analysis before we can build up the trust so RSA has been around for many years even though there are potentially faster algorithms RSA is still used a lot Diffy Helman digital signature standard and elliptic curve cryptography other common techniques and that uh puts the operations that are in those diagrams in in uh in a set of requirements so we need some algorithm encryption algorithm and decryption algorithm such that these requirements are met the first three are just means it's practical to encrypt and decrypt if we have the right information from a security perspective four and five are important from the attackers perspective if they know the public key they know the algorithm and they know the cipher text it must be impossible to find the private key and note that the public and private key the key pair are related there's a relationship between the two values they're not random they there's some algorithm that determines the value so even though we know the algorithm that relates these two values we need it to be such that if I know the public key of someone else I know the cipher and I know the algorithm it still should be practically impossible to find the other person's private key if I do it's not private and our system fails and similar if I know a public key a cipher text it should be hard to find the plain text the message this last op uh this last requirement six just says often we want algorithms to be able to allow to use the keys in in either direction if we encrypt with a private key we can decrypt with a public key or if we encrypt with a public key we can decrypt with a private key some algorithms have that property summed on there are some more details about the requirements which I think are not necessary for us to cover uh that slide is one of them uh attacks it turns out attacks uh often for the algorithms that we're discussing come down to Brute Force attacks trying large trying to guess the key okay and if we make the key large enough then it becomes too hard to guess the key but an an interesting thing about the public key algorithm is a lot of them are based upon some mathematical operations and the security really relies in that those some of those mathematical operations are hard to compute solving the mathematical equations are computationally hard uh and you need to study the algorithms and some of the the mathematics behind it to start to understand the difficulties there RSA is the main algorithm you'll use it to generate your key pair what you do you generate Keys a public and a private key and then you can encrypt and decrypt with those values without going through the steps for generating the key so there's some mathematics behind it it involves using some large prime numbers you select some large prime numbers perform some operation s and from that generate your keys which really are made up of some value n some value e which are public they form your public key and some other values p q and d private values p and Q are your initial prime numbers D is generated from them so the idea what you'll do with OP SSL in your first step is the software chooses two large prime numbers p and Q random almost randomly chooses two large prime numbers does some calculations and from that generates your public and private key where we can think of the public key I have it maybe we'll draw it on the board the public key pu is not denoted as the value e and n and the private key is D and often we include n as well that is we choose two large prime numbers generate NE e and P and Ne and D okay how we generate them then you need to study the to see how that works we're not going to go into that detail but we generate these values and n and E we can tell everyone they public and they form our public key so anyone else in the world can know those two values D is really the secret value that's generated as well and what's commonly done is that we say that D with n is considered the private key but no n is public so D is the secret value so when I generate these values e d and n I can tell you the values of e and n and in fact that's what you do with OP SSL in your homework op SSL chooses two large prime numbers p p and Q generates e DNN and saves them in a file as well as a few other parameters but saves them in a file and when you extract your public key you'll see it contains the value of e and n and you send them to me you submit the file which contains these values and now I know these values I can use to encrypt and decrypt and then with RSA the algorithms designed and the way that these values are generated is designed such that if you have some plain text you treat it as a number an integer and to encrypt you take the value you raise it to the power of E mod by n and you get your Cipher Tex value so encryption mathematically is very uh simple or beautiful in that here's an equation to encrypt some plain text as Des many of the symmetric ciphers are very complex in the design of the algorithms RSA is just a simple equation with four parameters it says take your plain text or your message we often use M to mean the plain text because P often is confused with a public and private key so M the message treat it as an integer raise it to the power of E the value that we generated mod by n the value that we generated and the value the answer is our Cipher text and we can send that Cipher text across the network when someone receives that Cipher text note that we use en andn to encrypt so we use the public key to encrypt that message so to decrypt we need to use the private key so to decrypt we take the cipher text raise it to the power of D the secret or private value and mod by n the same n as we used to encrypt and we will get the original message back that will work because of the way that the key generation was designed and you need to study that algorithm to see why that's true it's it's an interesting uh design to see why if you apply these algorithms you'll get the original message back but we will not go into that detail so RSA one of the most commonly used public key algorithms is simply for encryption this mathematical operation for it to work you need to generate keys According to some steps and the keys we denote as the public and private key en andn and DNN whereas n is in fact public rather than doing that on by hand on on paper we use some software to to do that for us and that's what you're using op SSL for in the first homework task you go back to the instructions you generate your own RSA key pair 248 bits determines the length of n it's 248 bits long a long number okay a very large number and E is in fact fixed to 65537 there's some reasons for doing that so you your key pair will contain e and n n would be 248 bits some large number e would be 65,000 537 and also it will generate your private value D some other number of course you cannot tell anyone what the value of your D is because then it won't be private it actually generates some other values that help to speed up the the encryption and decryption but they the main values so that's step one at generates these values for you it actually combines them into one file for you step two is to extract these two values from it and put it into a second file so you can submit to me that's step two we'll see the other steps later so RSA designed by by ravest Shamir and Adelman RSA uh it's considered secure today there may be a few uh special instances where you if you use particular values it's insecure but in practice it's considered secure and it turns out that the the way to break it the best known way to break RSA is to if you know as the attacker the value of n which is in fact generated from two prime numbers p and q n is in fact just multiplying p and Q together if you know n if you can Factor it into the two prime values as the attacker you can find D and once you can find D you've broken RSA so the strength of RSA depends upon the ability to or the fact that it's hard to factor large numbers into its primes okay large numbers and for example 248 bits so 2 the^ of 248 is the maximum s value of n so take that number if you can then Factor it into primes then you can break RSA and there's no known way at the moment to do that fast some some of the past uh attempts for example in 2009 when n was 768 bits so they had there was some competition and with n 768 bits so if you write that down it was about 232 decimal digits so that's how long the the number is someone did an attack using some some computers and effectively took uh if you had a single computer they distributed across many computers if you had a single one it would take 2,000 years to factor this number into its primes uh or 10 to the 20 operations of course they they actually factored it but they use many many computers at the same time in parallel so that was the best known in 2009 nowadays it's assumed that still 10,24 bits is secure 248 is better and commonly used or recommended 4,096 even better okay so whereas symmetric key ciphers are measured in the length of their secret key often especially for RSA we can talk about the length of the value of n because the difficulty is given n find its prime factors you will use 248 bit n with RSA but we're going into too much detail again if you want to know this you need to take security and cryptography to know how RSA works that's not important for your objectives a problem most public key crypto systems especially RSA are much much slower than symmetric key encryption and you can try in op SSL I won't do it on my computer but you can do a speed test take a file encrypt it with AES take the same file encrypt it with RSA RSA will be much much slower it's too slow to encrypt large files so in practice because it's not very good for encrypting large files public key cryptography is only used to encrypt small amounts of information like we'll see to sign information so we've talked about symmetric key encryption one of the main algorithms being AES we spoke about authentication making sure that we can confirm what we receive is authentic and different methods for doing that and we introduce public key encryption RSA being an example there when we have two keys Key Management let's skip over okay I want to finish this topic today the issue is well the issues are how do we share a secret if I'm going to encrypt with symmetric key encryption I use a secret key and you need to have that same secret to decrypt how do I get that secret to you right I can write it down on a piece of paper and give it to you but what if you're on the other side of the world and we're using the internet to communicate what can I do send it in an email to you the secret key what if someone intercepts the email they'll find the secret so Distributing Secrets is not easy similar with public key encryption the idea with public key encryption is that for example I encrypt some value with with uh someone else's public key and they decrypt with their private key but what how do I get their public key okay I give you on a piece of paper here's my public key or you submit in the homework your public key but what if you want to send it across the internet okay in your email you send your public key to your friend and they will use that value but what if someone fakes that public key and say Here's the public key of Steve and in fact it's the public key of some malicious user but you think it's my public key then that can cause problems so there become issues of how do you get someone else's public key in a trusted manner such that you know it's theirs it's not somethingone pretending to be say this is their public key and issues of okay when do you change keys do you keep the same key for the rest of your life or do you change it on a regular basis to be more secure there are ways to practically overcome some of these problems sharing secret Keys we can use public key encryption to do so and that's what you'll do in your homework and there are ways to verify public keys and we'll see that in later topics after the midterm about digital certificates and the issues with uh verifying public keys so that's it Key Management interesting topic but we're not going to go into the details this one I want to cover to finish this topic digital signatures and it's related to public keys in authentication so we've basically done it already the aim is authentication but a special case when you sign something a piece of paper so there's a document and you sign your name on it that is some confirmation that you approve of that document okay so if you sign some contract then that acts as some proof that that you that person approve of that contract agree to that contract and then later when we see and you say no I don't agree to the contract we can come back and say well here's your signature you signed it we can prove that it was from you that's the idea of a normal signature we want to have the same service in in Computing and Communications and that's where digital signatures come in to be able to prove that prove to anyone in the world that a message came from or is approved by a particular user that is I send a a message to the class saying uh there'll be the extens the the homework deadline is extended by another week okay you receive an email then one thing you'd like to do is to be able to prove did it really come from me or did it come from someone pretending to be me and just tricking you to submit late and then you get zero for the assignment okay so can we sign a message well that's where we use digital signatures what about using symmetric key cryptography the idea we saw that we can use symmetric key cryptography for authentication what happens is that we have two users am they share some secret key K that symmetric key crypto cryptography so we take our message that we want to send and one of those users encrypts with the secret key and let's say user a receives the message user a receives a message if it decrypts successfully it means it must have been encrypted with that secret key and the secret key is known by A and B so if a receives the message they can verify that this message must have come from B because only B has that secret key it's shared between A and B so that's okay that's authentication a can prove from its perspective the message came from B but another user some user C they receive a message can they prove that it came from b or with symmetric cryp phography they cannot some message encrypted with a key shared by A and B could have been encrypted by either A or B we don't know which one how can we prove the a encrypted it or B encrypted it both A and B have that same secret so there's no way for someone else to prove exactly which user created this message and with a signature we want to be able to prove that one particular user created a message not one of two with symmetric ke key crypto we can't do that because a key is shared between two users so if we have a message encrypted with that key we don't know which of the two users created that message could be either of one of them the message it says it's from a signed by a but maybe it was B pretending to be a and Performing some attack on a so symmetric key crypto cannot be used for a digital signature because we cannot prove who uh this me message originated from we use public key crypto because with public key crypto with a key pair every user has their own public and private key only one user in the world has this private key so by the definition of being private only the user for the knows that value so let's see how it's used the concept is and we've actually seen it before we have a message I want to sign that message I'm user a I have a a contract in a in a Word document and I want to digitally sign it so what I do is I take that message that document and I encrypt it using public key cryptography and using my private key so I signed with my private key and I get some value as an output and we call that the signature s and usually what I do is I attach the signature with the original message the document so I send you here's the word document and here's the attached signature and then you need to verify that it was signed by me and the way to verify is you take the signature and you decrypt it using the public key of me of a in this case if it successfully decrypts using the public key of A then it means it must have been encrypted with the private key of A which means it must have come from user a because only user a has the private key of A so this is proof that this message came from user Aid so what we do is to verify is we decrypt the signature using the public key of the sender we get some value as an output if that value matches the message received then we assume that the signature is valid it's verified so this is the concept of signing something anyone in the world can can now prove when they receive the message that it came from a so a sends this signature and the message to everyone they know A's public key so to verify the message they decrypt with A's public key get some message and compare against the original message if they match then it means that it must have come from a and that's a digital signature or the concept of dig digital signature in practice so the E and D are public key algorithms like RSA for example but we've said before that public key cryptography is very slow so if my message I want to sign a a large file like a a DVD 5 gab RSA is too slow that it takes a long time to to apply the encryption operation on a large file so what we do in practice is we take a hash of the message and sign the hash value so this is the practical way that digital signatures are used there's no need to encrypt the entire message we encrypt just a hash of a message and remember we defined hash values hash functions before we said some of the properties is that the hash of two different messages will give us two different hash values it should be impossible to find two messages which are different which produce the same hash value so what I do to assign something now it's I have my DVD the message I want to sign it so that when someone receives it they know it's it's original it came from me I take the content the message I calculate a hash of that message remember hash functions produce a a relatively short hash value md5 produces 128 bits sh 512 51 512 produces a 512 bit hash value so my 5 gigabyte DVD the hash value is just hundreds of bits so very small I take the hash value encrypt it with my private key encrypt the hash value with my private key and the result is called the signature the signature of this message then what I do is I send the message and the signature to whoever wants to receive it B for example and it's then their task to verify and same to verify we take the signature decrypt with the public key of the signer a signed decrypt with A's public key we get some hash value as the output if this value H matches the hash of the received message then we assume that this has been verified that's the practical way that signatures are applied let's try and draw that as an exchange and see what can go wrong and see how our hash functions work so we have our user a and say sending a message to b the aim is for B to verify the message came from a so the basic approach is that a calculates the signature of a message S as by encrypting using A's private key only a has his private key of the hash of the message and send that along with a message to b so we say we send the message concatenated with the signature so that's sent across the network a has a message to send to B they sign the message and send both the original message and the signature to B so this the two vertical bars again a con concatenation we combine them together so we send both of them in in the in the me in the packet for example or the email or the file this doesn't provide confidentiality anyone can see the message that's not our aim I don't care if someone sees the message what we want to make sure is that confirm that it came from a not someone pretending to be a to verify B they receive the message they you they must know the hash and encryption algorithm use they take the receive message and calculate the hash so M that's received they calculate the hash of that and then they decrypt the signature so they decrypt using the public key of A the signature and what do they get well with public key cryptography if something is encrypted with a private key of A this was encrypted with a private Kea if we decrypted the cipher text with a public Kea we get the original plane text so we'll get the hash of M as the output so if nothing has been changed and we're using the right key then we'll get the original input from the encryption which is the hash of M and they should be the same so that's the normal operation a signs the message sends the message and the signature to b b verifies by taking a hash of the received message and checking the signature by decrypting it with the public CA and if those hash values match then it means the messages match because our uh assumption about hash fun function is the hash of two messages will produce the two messages which are the same will produce the H same hash value or the hash of two different messages will produce different hash values so if the hash values are the same the messages must have been the same let's see what an attacker can try to do and see where it goes wrong so let's say an attacker pretends to be a so B is going to receive a message an attacker our malicious user is going to send a message to b pretending to be a so they're going to send a message concatenated with some signature what is the signature well we need to encrypt the hash of that message what can the malicious user encrypt with they want to pretend to be a normally we being encrypt with the sender's private key so the malicious user doesn't have A's private key so let's say they use their own private key private key of the malicious user so the malicious user has some message they want to pretend to be a they send the message to b m and they send a signature of that message which was obtained by taking a hash of M encrypting with the private key of the malicious user that's sent B when they receive a message when they think it's from a they verify the verification steps are take the receive message calculate it's hash and then decrypt the signature and how do they decrypt the signature how does B decrypt the signature what key do they use public key of A if you think the message comes from a then to verify you decrypt with A's public key and then we compare the result of the encryption with the the hash value We compare these values they will not match because note that we encrypted with the private key of the malicious user we did not decrypt with the corresponding key in the key pair and when we decrypt with the wrong key we will not get the original PL Tex out that's our assumption and it's generally true that is here's our plain text we encrypt with a private key if we decrypt with the corresponding private key we'll get the plain text back but if we decrypt s using the wrong public key we will not get the plain text back that is we will not get the hash of M as the output we'll get some other value and when we compare it to here they'll be different okay so the output of the decryption will not equal the hash of M and that's how B knows something's gone wrong this message didn't come from a someone's either pretending to be a or someone's modified something along the way so someone assumption that we're relying on here and I've tried to capture these assumptions in the handout that I passed around this morning is that both with symmetric and public key encryption if we decrypt with the wrong key we will not get the original plain text we'll get something else so here we've decrypted with the wrong key so we would do not get the original M text which means it doesn't match the hash of the message B detects something's gone wrong what else can you do as an attacker what can you try that was trying to pretend to be a any other attempts social engineering to that uh be that uh to to try to change the public key of A to be the okay and and know that are correct if so in this case b thought that the message was from a okay malicious user was pretending to be a so B decrypts with the public key of A if somehow the malicious user could make B think that the public key of A is not in fact public key of A but is the public key of the milous user this would be a successful attack that is if let's say B has the public key of A it has a list of public Keys maybe it was published on a website A's public key listed on a website but in fact it wasn't A's public key it was the public key of the malicious user B thought this was the public key of A then what B does when they receive a a message from a they decrypt with the public key of A but in fact the public key is of a is the public key of the malicious user if we use that in the decryption the result of the decryption will be the original hash value and B would be fooled into thinking that this message came from a so a successful attack is possible if we can somehow make B think that the public herey of a or that this public key of the malicious user is in fact the public key of A that's like the issue of well that's the issue of Key Management I say here's Steve's public key how do you know it's really mine or you see on a website this is Steve's public key how do you know it's my public Key Well we need some way to verify to to manage keys that way so yes that's an issue we'll come back to that issue and we look at digital certificates but and see still it's a challenging problem but assuming we can distribute Keys correctly assuming that we can't do this attack what else could the attacker try to do let's try and see if we can modify a message first a simple attack uh let's say a a sends a message to B and malicious user tries to modify the message so a takes some message and the signature and we send the message but it's intercepted by the malicious user and the message is again as original before the message and the signature where s was calculated by a as encrypt with the private key of A the hash of the of m so this is the same as our original scenario a generates the signature attaches that to the message sends it to B but malicious user intercepts before it gets to B they get a copy and can they modify the message and send it to B send up to B and make B think that the message came from a well let's try let's say we change the message to M Prime okay a different value than M the original message M Prime we don't know of course the malicious user doesn't know the private key of A so we will not try to recreate a new signature because it won't work we saw from the previous case if we try to encrypt something something with the private key of the malicious user it won't work so let's just attach the original signature that is all I do let's say the signature is uh 512 bits the message is a megabyte what I do is I as a malicious user I change the first one megabyte to my new message M Prime and I just copy the last 512 bits and attach it to the end and send that to b b receives thinks it's from a they verify and the verification same as before we take a hash of the received message M Prime and we decrypt the signature what key do we decrypt with again we think it's from a we decrypt with a public key of A the signature when we decrypt the signature what's the output so this is B verifying receive a message take the hash receive a signature decrypt the signature with A's public key and we will get H of M the signature was created by encrypting h of M with the private key of A when we decrypt it with the public key of A we'll get the original PL text back we'll get H of M the hash of the original message do match are they are they the same that's the verification step hash of the received message decrypt the signature compare are they the same hands up for Yes okay yes they are the same hands up for no okay they're not the same the hash and this comes back to our hash functions the hash of two different messages M and M Prime are different will produce two different values so when we compare them we'll see not the same therefore we've detected something's gone wrong so this relies on our hash function property the hash of two different messages uh gives us two different hash values if the malicious user could find a message M Prime which was different from M but had the same hash value if they could do that this attack would be successful but with strong hash functions it's practically impossible to find two messages which have the same hash value so that attacks unsuccessful so signatures generally work by using public key encryption and hash function the hash functions are used to to reduce what we encrypt going back to our slides in the concept we only really need to encrypt the message but with public key crypto encrypting large messages is too slow so in fact we encrypt the hash of the message and the hash of the message is quite short it it makes it convenient in terms of performance verification decrypt the signature compare to the hash of the received message if they match verified if they don't match not authentic problem there are different algorithms for digital signatures RSA is common but there are other algorithms which are also used DSS or the digital signature signature algorithm which is part of the digital signature standard DSS uh elliptic curve DSA El gaml and there are others okay but RSA is still quite common and you can do use different hash algorithms but the common ones are in the past md5 and now sha sh 2 so the different hash functions and that's why we need these properties of the hash functions that we introduced on Tuesday so because we use them for digital signatures these properties of one way and it's hard to find collisions almost gets us to the end of this topic questions about digital signatures before we move on everyone's got a copy of that one page handout that uh uh sheet if not there's a few more hanging around make sure you have one anyone a few more spare it's I've put it on the website this morning uh I try to summarize many of the key assumptions that we're going to use in later topics from this topic on cryptography I not go through them all but let's just look at a few that will be useful so cryptography is a very wide topic uh we would we don't need to know all the details to look how it's used what we often do is make some assumptions about okay that some algorithms are strong some aren't and I've tried to list some of the key assumptions they normally hold they are assumptions they're not always true there may be special cases when these assumptions I State here are not true and if they're not true then we make have security flaws but usually we we'll know when they're not true but so we normally make assumptions uh for example A7 assumption 7 here if we decrypt some Cipher text using the incorrect key so some Cipher text was created by encrypting plain text with one key if we try to decrypt that Cipher text using the wrong key then we assume that the output will not be the original plain text and the decryptor the person doing the decryption will know they'll recognize that the key that they just used is wrong what is the wrong key if we're using symmetric key encryption the wrong key is the shared secret that wasn't used for encryption if we're using public key encryption it's it's not the key in the corresponding key pair so that's actually covered in the previous assumption the wrong and right keys so this is an assumption that we make if we decrypt something and we're using the wrong key then we'll get some we will not get the plain Tex's output uh some other assumptions from now on we're going to assume that Brute Force attacks are not possible when we're using strong ciphers that is the easy way to stop a Brute Force attack is make your key longer or or make the parameter longer uh so right it varies as to how long a key should be to stop a Brute Force attack but uh well anything 128bit Key impossible 100 bit key is considered impossible so I said anything above 2 to the 80 operations or attempts then let's assume that it's not possible to do that in in a reasonable time that is under 100 years and some other assumptions we assume the attacker knows is knows everything that's public their algorithms the language that the pl T was in let's assume that they know that that they can use some way to find out that so we can't make it more secure by saying oh let's make the plane text In tha instead of English that doesn't help because in practice the the attacker can find that out yeah yeah okay okay that you if if the attacker you said if the attacker can know the private key from the public key before I you continue let's go to one of the assumptions uh an attacker does not know secret values so if we say we have a secret key we assume the attacker cannot find that secret value if they can it's no longer secret and their whole system fails so in public key cryptography the public key is public the attacker does know it the private key and especially D is private or secret and we assume the attacker doesn't know it and we assume we from now on we're going to assume that the algorithms that we use are strong enough such that there's no way for the attacker even if they know the public key to find the private key uh so if the attacker somehow manages to find the private key then we assume the system fails from a security standpoint so the attacker can't find the private key from the public key you say if they can well if we analyze the algorithms if we use strong algorithms they can't there's no known way okay it's secure if we use an insecure algorithm maybe they can but if we use secure algorithms like RSA a for symmetric key encryption there's no way for the attacker to find the secret no practical way okay how about to protect the force can we limit the time to brute force uh again we don't put exact values and this 2 to the 80 is not an exact value is my point is that in practice to avoid a Brute Force attack we can make the key large enough such it will take billions of years how can you reduce that to be manageable well even if you uh even if you double the speed of your computers then billions of years down to well still billions of years I mean that uh if if the key are not correct we lock the bu because because I I saw in the many webite many website that I if I have the key okay that that's a different thing and that comes in the next topic passwords and locking accounts but that's not Brute Force attack although we can use that technique to slow down Brute Force attacks uh but we'll see when we come to passwords Brute Force attacks are possible but when we're talking about our encryption algorithms it's all we're talking about at the moment then they're not possible okay but yes will come to your your question and comment in the next topic uh some the assumptions about hash functions digital signatures Key Management we didn't really cover well quite simply let's assume that we have a way to exchange a secret between two entities if we need need to both have a secret let's assume we have some way to get that secret to the other person and there are there are practical ways to do that all right physically deliver the secret not very convenient but there are protocols that allow us to do across the internet and similar we assume from now on that we can correct obtain the correct public key from The Entity so if you have Steve's public key it really is Steve's public key it's not someone pretending to be Steve that's what we'll assume in our subsequent discussions and some other assumptions the principles are just a few other issues definitely not all principles used in security but some that may have come up from our discussion uh I mentioned this one before let's assume that generally the better known an algorithm is the longer it's been used in practice the more secure we may consider it the less chance it will have flaws you come and design a new algorithm you say it's 10 times faster than RSA and you write some software and distribute to the world then people will not trust it until they've used it a lot and done a lot of analysis of it not just used it for one day but used it and and analyzed it over a period of years usually so the longer it's been used and there are no known flaws the the more secure we consider it to be so we don't just upgrade to the newest version as soon as it's released performance symmetric key algorithms are much faster than public key algorithms so generally we don't use public key crypto to encrypt large amounts of data it's too slow increase the plain text and you increase the time to encrypt that's the number three we should dist distribute Keys using automatic means for example I ask you to give me your public keys one approach you write them on a piece of paper you come to my office and I give get the the your public key and all 40 students come to my office over a period of a week and I got your public keys well that's a manual means an automatic way would be to let's say publish the public key on some website or use some software or some protocol to exchange public Keys automatically manually doing things is inconvenient especially when we have many users distributed across a large area across the world coming to my office is okay for you but what if we want to distribute to uh users in other countries we need automatic means we haven't really covered this but a a principle that we'll see come up is that the more times you use a key a secret key generally the greater the chance of a disc that key being discovered by an attacker which suggests change your keys on a regular basis and we'll come up to that with passwords the same things apply you should change your password on a regular basis change your secrets it decreases the chance that it is discovered use multiple security mechanisms that overlap in what they try to do so that if one fails you have some backup don't put all your Trust In One Security mechanism because because if that one fails your whole system will fail we'll see that principle come up and we'll see some other principles over the topics have a read through those assumptions the rest of them we haven't covered and really if you can we'll use them uh as the basis for the next topic so even if you don't understand all the details of the cryptographic techniques we've used we can still understand the subsequent Topics by using those assumptions random numbers it's hard to create random numbers with computers but let's assume that we've got some ways to do so so we're not going to cover random numbers they're important very important insecurity turns out it's not easy to create random numbers computers are deterministic they follow some steps some algorithm so how do you get Randomness in a computer most random numbers created in software are what we call pseudo random numbers they're not truly random they follow some sequence so we have pseudo random number generators true random number generators use some non-deterministic Source like some radiation events or measure some physical uh event in the environment but it becomes very inconvenient to get your computer to measure radiation to to Generate random numbers so we usually use what's called pseudo random numbers we will see random numbers are used in many different parts in in it security that is we rely on them to be secure y sorry time [Music] random write get your computer to generate a random number how does how do you do it with a Time time's not random time's predictable but how you need some algorithm okay and an algorithm in a that a computer uses is deterministic we know the algorithm in advance so again how do you produce a random number write a write a piece of software that creates a random number just choose a random number but how do you choose that random number how do you get a computer to choose the random number so when we use software we we call some function Rand or something and it returns a random number but how is that function implemented that's what we care about how does that function choose a random number well in many cases there's just an algorithm and it uses some equations to generate one but it's not truly random in many cases you there's a sequence of values it selects from and it predictable as to what the values are so uh that is a challenging problem yeah okay so better random numbers start to use some other source of events okay for example uh a computer operating system if you measure keyboard presses you measure activity on the hard disk uh you measure noise leak from electrical circuits then some of those activities exhibit randomness and if you can measure those values then you can generate close to True random numbers but that requires measuring the hardware and it and what I can do on my computer to measure Hardware may be different from what you can do on your mobile phone so making a a random number generator that measures for example noise from your CPU or from your uh circuits on your motherboard is not easy okay and not all devices support that so so yes using some Hardware inputs can lead to True random number generators but we don't have them available on onot all devices so often we use some algorithm to generate and they are not true random numbers but pseudo random numbers and you'll find that many attacks on security systems have in the past taken advantage of the fact that poor implementations of Random number generators we may point to some as we come through different topics some example random number generators but we're not going to cover that but for now random numbers are important in Security in they in theory they're hard to generate it's hard to create random numbers in computers that work across many different systems but from now on we're going to assume that we've got some algorithms that will produce random numbers this is a long topic covering many different things uh a bit of a summary but maybe the best summary is the handout of the assumptions that you've got that summarizes the main points that we we're going to need for the rest of the topics many things we haven't covered Key Management is hard we've sort of skipped over it making sure that keys are are from the right person we use all these super secure algorithms and then someone implements it in software and they make a mistake and Implement bugs they have bugs in their software and it leads to flaws in the algorithm that's common and that leads to Avenues for attacks so we may have a perfect algorithm but then someone goes and implements it in software and they implement it wrongly and that may lead to attacks that are possible okay so that's a practical Avenue of attack it's often difficult to prove the security of alchs to say 100% this is secure so making a judgment of this is secure or this is more secure than something else is challenging and there are many other topics that we haven't touched upon which interesting but we will not explore okay next topic next week we'll move on to passwords and we'll start to move into practical things of it security Now the cryptography will be used throughout the rest of the topics but maybe the mainly the assumptions that we have here will be used for