RSA Encryption Algorithm: How Prime Numbers Secure the Internet

[00:00:00]tim welcome back to computer files slightly  different circumstances we were doing mega fave numbers in the last one right  that's right yes i was talking about my favorite number um which many people  were disappointed i didn't know by heart um but it is still my favorite topic to talk  about big numbers um in the video i mentioned uh prime numbers in particular and the big  number i selected for that video was a prime number and i said i'll come back and talk  about how they relate to computer science prime numbers in computer science  are interesting for various reasons one of them is it's not always easy to find  whether something is a prime number or not and if i give you a number not like 91 can you  instantly tell whether it's a prime number or not um then again if i tell you that 7 times 13 is 91  you can quite quickly verify that that's right and therefore 91 is not a prime number um so there's  various shortcuts that people found to quickly be able to determine whether something is a prime  number but no one has found a shortcut to be able to find the actual prime factors so telling  that 91 is not a prime number is fairly easy for a computer to do finding the number 7 and 13 is  relatively difficult of course i say relatively here because for a computer it's peanuts to  find seven and thirteen um so that makes it interesting for computer science um but what  makes it even more interesting is its application its application is mostly in cryptography  if i want to communicate in secret with you then i want to be able to do that so one example  of where prime numbers are used in cryptography is the diffie-hellman key  exchange which is something that mike pound was spoke about about three years  ago on this channel a very interesting video watch it but another important application that  uses prime numbers is rsa which stands for revest shamir edelman the three developers of the  algorithm and it's heavily based on prime numbers we see rsa everywhere don't we it's  connecting to the internet we are almost always using rsa at some point is that would i be right  in saying that exactly right yes thank you um so public key cryptography is the general class  that rsa is in there was a video about this a long time ago by robert miles and he explains  what public key crypto is but one of the most important modern applications i would say crucial  to the internet is the fact that https is built on top of this kind of technology now there are  two main flavors to implement it there's rsa which is the older more established algorithm  and there's elliptic curve cryptography again a topic of a different video and those are basically  the two competing algorithms and of the two rsas based on prime numbers which is why i'm talking  about those today in fact i would like to give a quick demonstration of how rsa is used by going  to our university's website so the browser i'm using is firefox but all browsers will have  this functionality what you can see is this little padlock in the top left next to the  address which means that your connection is secure now you can actually investigate how the  connection is set up by clicking on the padlock clicking on the right buttons and then here's a  button that says more information and then there's the option to view the certificate which is what  we're going to do now and here we see information about these certificates and the relevant  information that i want to talk about is right here public key info and so it says the algorithm  is rsa which is the algorithm i want to talk about it says something about the key size being 2048  bits then it says exponent which is roughly 65 000 and then there is this number which is the modulus  which is a massive number it's cut off here in hexadecimal and if we translate this to  a decimal number the number we end up with is this number so what you end up with is this  600 digit decimal number it's a massive number and it's not a prime number actually but it is  the product of two very very large prime numbers and two 300 digit prime numbers now the idea is  that nobody knows what these two prime numbers are if you can figure out what these two big  300 digit prime numbers are that make up this larger number i will offer you a fully funded  phd and a guaranteed spot in the newspapers and perhaps even a big prize here and there and on  top of that you get to hack the nottingham website but how come then this idea that it's difficult  to find prime factors actually lays the foundation for a cryptographic protocol in order to explain  how it works we need to talk about a slightly different topic first it's called modular  arithmetic now it sounds complicated but it's actually very easy in fact we do it every day if  we're using an analog clock because a clock every 12 hours it goes back to its original position  so if i ask you what is 15 hours on the clock you will know it's three hours because it's the  remainder after division by 12. we do it often for 24 hour to 12 hour clock conversions but you can  even do things like minus one hour which would be 11 on the clock or 25 hours which would be one  on the clock now the clock we are going to be talking about is not a 12 hour clock but a 91  hour clock because 91 is the product of the two prime numbers we're interested in the magic  that actually happens is that if you think of a magic number between 0 and 90 then i can  instruct you to take that number and raise it to the fifth power so can you think of any number  should we go for let's go for number 18. okay 18.

[00:06:24]so what i instruct you to do is to take the  number 18 raise it to the fifth power but do that on a 91 hour clock so this is like 18 times  80 five times and then so it will always be a number between 0 and 90. for a human this is a bit  complicated i don't expect you to know the answer but the answer will be 44 which is you know it's  a normal number between 0 and 19. and then what i do is i take that number 44 and i raise it to the  29th power so i multiply it with itself 29 times on the clock and the number i end up with is  18. so i know in normal arithmetic you have this idea of inverse operations is that a bit like  that have we got back to the start doing that yes that's exactly right so 29 is a magical number  that we found that will reverse you're doing the power to the s taking the number to the power five  so whenever you take a number to the power of five if i take that result to the power 29 the result i  end up with is the original and it will always be the case on a 91 hour clock so that's something  special about 91 hour clocks and i know they're different numbers for different clocks that's  right so it's a special property of 5 and 29 and if you can figure out that the number in question  is number 29 you can read the secret messages so it is important that no one knows the number  29. um so let's there's three questions we can ask ourselves when when we see this equation the  first one is where did the magic number 29 come from how do we get that the second one is how  does the computation work why does it reverse the operation and number three is is this secure  why is this secure let's answer question one so question one is where does the magic number 29  come from now to see where it comes from we need to construct a different clock so we had a 91 hour  clock which was constructed by multiplying the two prime numbers 7 and 13. we're going to construct  the different clock by taking the number before the prime number so 6 because it's 7 minus  1 and 12 because it's 13 minus 1. multiply them to get 72. so we're going to work now in  a 72 hour clock and then we're going to pick a prime number which does not divide 72 so we're  not allowed to pick two of three because they divide 72 but 5 is allowed so let's say we pick  the number 5 that is our encryption value e and that is the 5 that we saw before we took 18  to the power 5. so that's an arbitrarily chosen number to some extent but the number 29 is not  arbitrarily chosen because what we want to do is we want to valid find a value d such that e in our  case 5 times d is equal to 1 on our 72-hour clock now finding that by computer is very easy it  uses an algorithm called the extended euclidean algorithm i'm going to give you the answer because  we know what the answer is going to be it's 29 a computer can find it quickly and indeed if we  multiply 5 times 29 what we get is 145 which is one more than 144 and 144 is a multiple of 72 in  other words 5 times 29 is indeed equal to 1 on a 72 hour clock and this is where that magic value  29 that we used before comes from so that brings us then to the second question how does it work  we came up with this magic value 29 and and it it has a property that five times 29 is equal to  1 on our 72 hour clock right um so what this means is that if we subtract 1 from 5 times 29  what we end up with is a multiple of 72.

[00:10:50]now let me just tell you what e times d is without  any clocks it's 145. so on a 72 hour clock okay we go once around we go second time around and  then we have one hour more okay works perfectly so if we subtract one we end up with the  number 144 so 5 times 29 minus 1 is a multiple of 72 but that also means it's a multiple  of this number six which is seven minus one and it's a multiple of uh 12 which is 13  minus one so eb minus 1 is a multiple of both our left prime number minus 1 and our right prime  number minus 1 7 and 13 respectively now because it is a multiple uh of both of those numbers for  each of them individually we can apply a theorem known as fermat's little theorem fermat was a  famous mathematician living hundreds of years ago never having heard of cryptography of course yet  his results are very useful today so using that we can actually deduce that this value m to the  power e d minus one simplifies to one on our clock now because we have this minus one we have  one little m left over so what we end up with is one times m which is m uh which is how  it cancels out in the end okay so that's quite difficult to to follow i would say but it's  quite elegant like things that are not clear somehow fit together as puzzle pieces and they all  cancel out and what we end up with is exactly our original value now there's one remaining question  is it secure so we know that it works we know why our magic numbers are chosen the way they are but  the question is is is it secure so how come that i as in this case the university of nottingham am  able to deduce this value d but strangers cannot now if we look at the way in which the magic  numbers were chosen remember that we found the number 72 by taking one prime number seven  subtracting one and the other part number thirteen subtracting one and multiplying them how will you  do that if you don't know the prime factors of 91 so you cannot find number 72 simply because  you don't know the prime factors of 91 and we established the very beginning that finding prime  factors was a difficult problem but computing a number which consists of two prime factors is an  easy problem so the university of nottingham came up with two 300 digit prime numbers multiplied  them which was relatively easy found the numbers e and d the magic numbers and then forgot about the  prime numbers because they are no longer relevant and then it's secure because only people that  have the numbers p and q will be able to deduce the secret magic numbers and nobody else can know  the magic numbers if i go to the site will i see those same magic numbers do you see what i mean  so you will see two of the three magic numbers which is the product p times q but you won't  know what the original values p and q were you will see the number e which in our little  problem was in number five but you will not see the other magic value which in  our example was the number 29 so the number e is usually a small number and  the number d is usually quite a large number so that's why we found for nottingham that the  number e was 65 500 something but the number d which is a secret number could really be  any number that is roughly 300 digits long we have no idea which number it is you're  not going to be able to search them all quite quickly 2 to the 16 operations 65 000  operations even on a laptop not going to take very long so i go through and i find all the  possible x's that means that any device which is keeping track of time in that way will get really  confused and we basically get the millennium [MANUAL PUBLISH]