Károly Zsolnai-Fehér explains why simple ciphers like Caesar's fail against frequency analysis, then shows how one-time pads achieve perfect secrecy. The catch: you need a random key as long as your message, and you can never reuse it.
Dear fellow scholars, this is two minute Papers with cryptography helps us communicate securely with someone in the presence of third parties. We use this when we do, for instance, online banking, or even as mundane tasks as reading our Gmail. One of the simplest ways of doing cryptography is using the Caesar cipher. We have a message and each letter we shift with the same amount. Okay, wait, what does shifting mean? Shifting the letter A by 1 becomes B and shifting E by 1 becomes F, and so on. The amount of shifting doesn't have to be exactly one. It can be anything as long as we shift all letters in the message with the same amount. If we would run out of the Alphabet, for instance, by shifting the last letter Z by one, we get A, the first letter back. There's a special case of Caesar ciphers that we call ROT 13 that has an interesting property. It means that we shift the entirety of the message by 13 letters. Let's encrypt a message with rod13. We obtain some gibberish. OK, now let's pretend that this gibberish is again a message that we would like to encrypt. We get the original message back. Why is that? Since there is 26 letters in the basic Latin Alphabet, we first shift by 13. Then doing it again, we shift by 13 letters, which is a total of 26. Therefore, we went around the clock and ended up where we started. Mathematicians like to describe this concisely by saying that the inverse of the rod 13 function is itself. If you call it again, you end up with the same message. We know the statistical probabilities of different letters in the English language. For instance, we know that the letter E is relatively common and Z is pretty rare. If we shift our Alphabet by a fixed amount, the probabilities will remain the same only for different letters. Therefore, this cipher is quite easy to break even automatically with a computer. This is anything but secure communication. The one time pad encryption is one step beyond this, where we don't shift each letter with the same amount, but with different amounts. This list of numbers to use for shifting is called a pad because it can be written on a pad of paper and it has to be as long as the message itself. Why one time? Why paper? No worries, we're gonna find out soon enough. If we use this technique, we'll enjoy a number of beneficial properties. For instance, take a look at this example. With a one time pad, We have two Vs in the encrypted output, but the first V corresponds to an H and the second V corresponds to a P. Therefore, if I See a V in the encrypted output. I have no idea which letter it was in the input. Computing statistical probabilities doesn't make any sense here and we're powerless in breaking this. So even if you can intercept this message as a third party, you have no idea what it is about. It's very easy to prove mathematically that the probability of the message being happy is the very same probability as hello or ABCDE or actually any gibberish. The one time pad is the only known technique that has optimal perfect secrecy, meaning that it is impossible to crack as long as it it is used correctly. This is mathematically proven. It is not a surprise that it had seen plenty of use during the Second World War. So what does it mean to use it correctly? Several things. Pads need to be delivered separately from the message itself. For instance, you walk up to the recipient and give them the pad in person. The exchange of the pads is a huge problem if you are on the Internet or at war. Now, you must also be wary that the pad must not be damaged. If you lose just one number, the remainder of your message is going to be completely garbled up. You're done. The key in the pad needs perfectly random numbers. No shortcuts. Generating perfectly random numbers is anything but a trivial task and is subject to lots of discussion. One time pads have actually been broken. Because of this. There's an excellent episode on a well known channel called Vsauce on what random really means. Make sure to check it out. The pad has to be destroyed upon use and should never be reused. So if you do all this, you're using it correctly. In the age of the Internet, it is not really practical because you cannot send a delivery guy with the secret pad next to every message you send on the Internet. So in a nutshell, one time pad is great, but it is not practical for large scale real time communication from afar. And as crazy as it sounds, if a civilization can find a method to do practical communication with perfect cryptography, their communication will look indistinguishable from noise. This is amazing. There's tons of ongoing debates on the fact that we're being exposed to tons of radio signals around the earth. Why can we still not find any signs of extraterrestrial communication? Well, there you have the answer, and this is going to blow your mind. If practical perfect cryptography is mathematically possible. The communication of any sufficiently advanced civilization is indistinguishable from noise. They may be transmitting their diabolic follicle plants through us this very moment. And all we would hear is white noise. Crazy, isn't it? Thanks for watching and for your generous support. And I'll see you next time.
