Strong prime

Transcription

DR. JAMES GRIME: 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 2 8-- [MULTIPLE CLIPS OF NUMBERS BEING COUNTED AT THE SAME TIME] --7. 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, who were Rivest, Shamir, Adleman. Should I show you how it works? BRADY HARAN: Please. DR. JAMES GRIME: 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? But the problem is that the bank is giving everyone one of these boxes and a key that goes with it, and 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. You've got a secret. Put it inside the box. Lock it not with a key but with a padlock. It goes click. It's snapped shut. 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 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 3 and the number 10. The bank also has a secret number. The bank secret number, for now, you don't know what it is. No one knows what it is. Only the bank knows what that secret number is. I had a very bad breakfast this morning, so I'm going to send the 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 3. Now there are some codes that would just add 3, or there are some codes that would multiply by 3. What we're going to do is raise to the power 3, so we're going to cube these numbers here. Let's do that. So I get 2 cubed, which is 8. 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, it would be 51 10's and 2 leftover. So that's just 2. 5 here, 1 and 4. And that's your code. And that's what you would send. The bank, or the person who is going to decode this message, has a secret number. Now the secret number in this example is going to be 3. 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 3, but it just happens to be the same as the 3 we used before. But nevermind, 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 times 5 are prime numbers. Multiply them together and you get 10. Now that massive number that I showed you that NatWest uses is the same idea. It's two massive prime numbers multiplied together. That's what it is. If you want 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 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 2,048-bit number. That means it's about 2 to the power 2,048. 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 the 768-bit number. It took this team of academics with all their resources two years to break at 768-bit key. And they said that to break what we use now, which is about 1,024, would take thousands of times longer. But given the speed of technology, they reckon that this sort of code, 1,024-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 replaced. And as you can see, NatWest have done that. All the banks have done that. They are now using 2,048-bit number, which again would take computers-- and I mean even with a proper attack-- big computers, it would still take them thousands of years to factorize that number into its original prime number. Now hidden in the details for this code is a mathematical fact that was worked out in the 17th century by Pierre de Fermat. He's famous for Fermat's Last Theorem. Well, this was Fermat'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 takeaway x. This is a multiple of p, the prime number. Let me do an example. What I mean is if you took a number like 4, and then I took a prime number like 5, and then I takeaway 4, I would get 4 to the power 5, which is 1,024, takeaway 4, which is 1,020. And that is a multiple of 5, but that would be guaranteed. You're guaranteed to have a multiple of 5. Now you can imagine that in the 17th century when Fermat came up with this factor, people said, well, very nice mathematical fact, but that's pretty useless. 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 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 we need, which is the power that you have to raise, that is not as big. That is 65,537. Quite a big number. When you compare it to the second number, it's small. BRADY HARAN: 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 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.