Encryption and HUGE numbers - Numberphile

Key Takeaways

so I've got a very big number to show you today used by NatWest Bank so that you can send them your secret Bank details it starts 2 3 4 5 3 6 7 6 287 did you get that or do you want me to repeat it so this number that we are reading out is 617 digits long all banks have similar numbers when you want to send them your credit card details this is not a secret number in fact your computer will download this number when it wants to send your credit card details it's there to find this is public so this code that they use on the Internet is called RSA it's named after the three people who came up with it which who were revest Shamir Adelman can I show you how it works please all right imagine if you had a secret that you wanted to send to the bank so the bank provides you with a box and it provides you with a key to lock the box so you can put your secret inside and you can lock it and then you can send the secret to the bank that's good isn't it uh but the problem is if the bank is giving everyone one of these boxes and a key that goes with it it then that means that well one person could steal someone else's box and use the key to unlock it and read their secrets that would be terrible we can't do that so what the banks do same sort of idea but instead of giving out keys they give out padlocks so they give everyone a box if you've got a secret put it inside the box lock it not with a key but with a padlock it goes click it snaps shot once it's locked and snapped shut you don't have the padlock key so you can't reverse it you can't open it up so if someone steals your box they don't have the key Either they've got a padlock but they don't have the key to open the padlock the only person that does is the bank themselves and it's a way to send secret messages without having to send out the keys it's easy to lock the code but it's hard to unlock the code first of all I have to explain this with the smallest example I can and then I'll show you why we use that massive number let's say you're the bank and you give out two numbers they're public so everyone can know them they're not secret numbers I'm going to choose the number three and the number 10 the bank also has a secret number if this Bank secret number for now you don't know what it is no one knows what that is only the bank knows what that secret number is I had a very bad breakfast this morning so I'm going to send a message bad Chef the first thing you do if you have a message like that is to turn the letters into numbers that's quite simple a is 1 B is 2 and Z is 26 simple stuff C is 3 D is 4 now I'm going to turn it into a code and I'm going to use the number three now there are some codes that would just add three or there are some codes that would multiply by three what we're going to do is raise to the power three so we're going to cube these numbers here let's do that so I get 2 cubed which is eight 1 cubed which is 1 5 cubed is 125 and 6 cubed 216 the final step is to use the second number the number 10 I'm going to divide by 10 and I'm going to look at the remainder so if I take something like 512 when I divide by 10 there would be 51 T and then two left over that's just two five here one and four and that's your code and that's what you would send the bank or the person who's going to decode this message has a secret number now the secret number is in this example it's going to be three there's a formula to work out the secret number I'm going to gloss over that for a second but I'm going to show you what to do next to decode the message this is my code I'll write it out again I'm going to do the same thing I did before this time I'm going to use my secret number it doesn't have to be the same as three but it just happens to be the same as the three we used before but never mind it doesn't have to be but I'm going to cube again so I Cube these numbers we do like we did before we divide by 10 and find the remainder and then the decoder will turn that into letters which is B and he gets the message back again bad Chef now that's just a taste of how it works that's the process that your computer does every time you buy something on Amazon or Ebay one of the important numbers in this code was this 10 now this 10 was made by multiplying two prime numbers together 2 * 5 are prime numbers multiply them together and you get 10 now that massive number that I showed you that NatWest uses it's the same idea it's two massive prime numbers multiplied together that's what it is if you want to work out the decode key the secret key you need to know the original prime numbers now the only way a spy someone who wants to break the code could work out the original prime numbers is to take that massive number number and factorize it turn it back break it up into the original two prime numbers this is really hard so hard that it's impractical to break with modern technology the massive number I showed you was a 20148 bit number that means it's about it's about 2 to the power 2048 now about a decade ago we did manage to break 512 bit numbers we were able to take that number and factorize it into its original primes a few years ago a team of academics managed to break a 768 bit number it took this team of academics with all their resources two years to break a 768 bit key uh and they said that to break what we use now which is about 1,24 would take thousands of times longer but given that given the speed of Technology they reckon that this sort of code 1,24 bit could be broken within a few years they said they said that a few years ago so this should now start to be replaced Gmail still uses this but this should be this should be replaced and as you can see Nat West have done that other banks have done that they are now using 2004 48 bit number which again would take computers and I mean even you proper with a proper attack big computers it would still take them thousands of years to factorize that number into its original prime numbers now hidden in the details for this code is a mathematical fact that was worked out in the 17th century by Pierre def fermar uh he's famous for firma's Last Theorem well this was firma's little theorem if I take a number a whole number an integer any number call it X I'm going to raise it to a power and it's going to be a prime number so P for Prime I'm going to raise it to a power and I'm going to take away X this is a multiple of P the prime number let me let me do an example what I mean is if you took a number like like four and then I took a prime number like five and then I take away four I would get four 4^ 5 which is24 take away 4 which is 1,20 and that is a multiple of five but that would be guaranteed you're guaranteed to have a multiple of five now you can imagine that in the 17th century when firmar came up with this fact that people said well very nice mathematical fact but that's pretty useless well what use are you going to have for that and then suddenly the internet comes along and it's massively useful in fact our whole whole modern world depends on this fact so to use this code the public key has two numbers I've shown you the massively long one that NatWest uses the other number that they need which is the power that they that you have to raise uh that is not as big that is 65,536 quite a big number but when you compare it to the second number it's it's small if you're in the mood for even more about Banks and really big numbers then check out my latest video from the chemistry Channel periodic videos where we've been inside the bank of England gold bullion Vault where they have a couple of hundred billion pounds worth of gold lying around that's not something you see every day the link is here on the screen and below the video