The Mathematics of Cryptography

this video was sponsored by Coursera if you and I wanted to let's say pass notes in class such that if anyone opened the note up they would have no idea what it said but we can still figure it out there are several methods for doing this for example maybe beforehand we could agree on shifting all the letters by three in order to encrypt our message otherwise known as the Caesar cipher so if I wanted to say hello I'd write a word with those same letters shifted by three instead of H I'd write K since K is one two three letters past H instead of e I'd write H L goes to O and O goes to R so this is the encrypted message that I send you then when you receive the snow all you do is ship the letters three to the left and you get the original message back but this is too simple so if someone could just try a bunch of shifts and figure out what the original message was but hopefully you can see the foundations of cryptography are pretty simple you have some message you want to send or the plain text like hello and you encrypt this to create a bunch of gibberish otherwise known as the cipher text that we saw earlier this is then decrypted back to plain text and this is what we just did using our specific encryption and decryption algorithm of shifting by three but let's do something else instead let's come up with a secret word or key that will swap around the letters for us for this scenario let's just say our secret key is computer and now I want to encrypt the message you can trust me well since the message is longer than the key I'll just rewrite the key repeatedly until the end and now what you do is really just add the letters C is the third letter of the alphabet so we I go three past Y now since Y is at the end all we do is wrap around back to a so we go three letters past Y wrap around and land at B o is the 15th letter if we add o or another 15 we get 30 and to figure out the letter more quickly remember that Z is the 26th letter so you could say 27 corresponds to a 28 with B which would make 30 go with deep and we can do this for the rest of the message to get our cipher text to decrypt it you would just subtract by the secret key now that wrapping around we just saw is actually the start of the real math I'm gonna get into soon so we just saw the 25th letter y plus the third letter C gave us B which is the second letter but we really know that 25 plus 3 is in fact 28 in fact we could say that 28 corresponds with 2 and we'll use this symbol to show that but this works specifically for the 26 letter alphabet and this is the same math you do as with a 12-hour clock if it's a lemon o'clock disregarding a.m. or p.m. what time will it be in 3 hours well obviously it'll be 2 but 11 plus 3 is really 14 so 14 corresponds with 2 on a 12-hour clock because just like with the alphabet you wrap around to the beginning now the official way to write and say all of this is 14 is congruent to 2 modulo 12 the visual way to think about this is if the integers continue to wrap around a clock 14 + 2 would land at the same place in fact if we kept going 26 would also land there which means 26 is congruent to 14 as well as 2 modulo 12 then algebraically the reason 26 is congruent to 2 mod 12 is because if you subtract 26 + 2 the result is divisible by 12 or you can see that 20 is congruent to 8 mod 12 since 20 minus 8 is divisible by 12 same goes for all these pairs of numbers on the clock so this is where we're headed and I'm going to get back to this soon but this is the beginning of number theory the main branch of mathematics used for cryptography but first the encryption we are just using is known as the Visionaire cipher which is used during the sixteenth century however there's a problem with it though if we used our secret key many times like over hundreds of messages an adversary could intercept those and using frequency analysis they can eventually decipher what our original messages were in the English language the most popular letters e which comes up about twelve point seven percent on the time next up is T which comes up about nine one percent then a which comes up about eight point one percent followed by oh and so I was curious about this so I found an online frequency analysis tool and copied in the first chapter of Harry Potter and the most popular letters correspondent pretty accurately oh and a were just a little mixed up but yeah using this there are ways to crack the Visionaire cipher over many many messages you can see that having a key is important in cryptography so now let's talk about key exchange or how to establish a secret key when you have to exchange it with someone over a public champ so I'll start this with a question a friend and I want to share a secret key or in this case a secret number now the problem is there's an eavesdropper who can see or hear anything that we say or write or whatever okay literally anything we can't use another language we can't whisper to each other or nothing like that and let's say it's a new friend so you guys don't know much about each other now the question is is this task even possible to come up with a secret key that only you two can understand but the eavesdropper cannot well give that some thought because now we've reached a point where we need the real math I want to talk about or number theory aka the study of integers so pop quiz this 10 congruent to 6 modulo 4 well yes it is algebraically it's because 10 minus 6 is divisible by 4 visually if I had a clock with only 4 numbers I just kept wrapping integers around it 10 and 6 would land at the same location and since 10 is 5 times 2 we can say that 5 times 2 is congruent to 6 mod 4 which I know looks really weird but now we're starting to do arithmetic with a number theory but now let's see what other type of arithmetic we can apply to this like could I divide both sides by 2 and get 5 is congruent to 3 mod 4 well no this is incorrect because 5 minus 3 is not divisible by 4 but why didn't that work well the first equation says 10 minus 6 is divisible by 4 but what that actually means is 10 minus 6 equals 4 times some integer we'll call now we know this is true for some value n in this case one but if i factor out a 2 from both terms does this also mean that this part the 5 minus 3 is also divisible by 4 well clearly that's not true which means 5 is not congruent to 3 mod 4 and one way to think about this is that the prime factors of 4 are 2 and 2 and two of these twos do not appear in either of these terms it's the combination of these terms which lead to this so none of these individually is visible by 4 so that's why you can't just divide by 2 and have something that's correct but look at this 72 is congruent to 12 mod 15 which should be easy to see at this point if I divide both sides by 2 I get 36 is congruent to 6 mod 15 and this in fact is also true since 36 minus 6 is divisible by a 15 so before we go further let's just think about is there some rule for when we can divide both sides and of course the answer is yes if the number that you're dividing and the modulus are relatively prime then you're able to do the division and relatively prime just means 1 is the only number that can go evenly into both like 9 and 10 are relatively prime since nothing goes into both of them besides 1 same with 70 and 33 another way to see it is the prime factorizations of let's say 70 and 33 have nothing in common so we can say that from this equation 72 minus 12 equals 15 times some integer n if we factor out a 2 we get 2 times 36 minus 6 equals 15 times some integer n now you'll notice that the prime factors of 15 are 5 and 3 which means this side of the equation is going to be 5 times 3 times some other stuff whatever n is this side of the equation therefore also must contain 5 times 3 times some other stuff and because five and three don't appear in this first term since two and 15 are again relatively prime then the five and the three must appear in this term and in fact five times three times two would get us what this is thirty and that means that this term is divisible by 15 because it contains the factors five and three and that means that this equation does hold because 36 minus six is divisible by 15 but hopefully you see we cannot divide both sides of this equation by six now and get six this congruent to 1 mod 15 because well this is obviously wrong and six is not relatively prime to 15 since three goes into both of them now those are some of the basics but there's so many theorems in this field that no one video could cover but a lot of them show some really interesting relationships between numbers when it comes like primes divisibility and so for example if I pick a prime P and raise any integer to the P minus 1 it will be congruent to 1 mod P if we let P equal 5 and X equal 2 we can see that 2 to the 4th or P minus 1 is congruent to 1 mod 5 since to the 4th is 16 16 minus 1 is 15 which is divisible by 5 but instead if P is let's say a hundred and thirteen and X is 18 I know that 18 to the 112 or P minus 1 is congruent to 1 mod 113 I have no idea what this number is but I know that if I subtract 1 from it that will be divisible by a hundred and thirteen there's another similar theorem but to understand it let me first ask this how many integers less than or equal to 10 are relatively prime to 10 well there's 1 3 7 & 9 so there are four numbers in number theory this comes from euler's totient function which is written using 5 event so 510 is four because there are four integers less than ten that are relatively prime to ten another example could be Phi of 15 is 8 because there are 8 integers that are relatively prime to 15 notice for a prime number that Phi of P is always P minus 1 and this is because nothing goes into a prime but one in itself like 5 7 would be 6 since 1 2 3 4 5 & 6 are all relatively prime to 7 a total of 6 numbers so oiler came up with a more general theorem that said an integer X raised to the Phi of some integer n is always congruent to 1 mod n assuming that X and n are relatively prime so if n is 15 we saw that Phi of 15 is 8 meaning some integer let's say 14 raised to the 8th power is congruent to 1 mod 15 which I find really interesting because I don't know what this is but I do know that if I subtract 1 the result is divisible by 15 I'd remember that Phi of some prime number P always equals P minus 1 so if I use P for n here and then plug in P minus 1 up here I get X to the P minus 1 is congruent to 1 mod P which is the same as that theorem we saw earlier ok so now we're ready to see this actually applied to cryptography and we're gonna look at the diffie-hellman protocol so this is how we go to exchange a secret key with each other so that an eavesdropper couldn't figure it out or at least they'd have a very difficult time trying to figure it out even if they had a computer you

Channel: Zach Star

Views: 254,672

Keywords: majorprep, major prep, cryptography, mathematics of cryptography, math used in cryptography, math needed for cryptography, number theory, encryption, bitcoin, cryptocurrency, math used in bitcoin, math needed for encryption, vigener cipher, caesar cipher, number theory applications, cryptography course, coursera, computer science, computer science math

Id: uNzaMrcuTM0

Length: 13min 3sec (783 seconds)

Published: Mon Jan 21 2019