Turing’s Machine 217 The Perfect Code The proof that a one-time pad is perfectly secret is straightforward. Imagine I take a coin and flip it 1000 times. PI write down some of the results as follows: HHTHHHTTHTTTHTTTTTHTH... I give you a copy of my results and keep one for myself. Now we each have the same random set of Heads and Tails recorded on a piece of paper. I can convert any message from letters to binary numbers: ‘a = 00000001, ‘b’ = 00000010, ‘’ = 00000011 and so on. If you are not familiar with binary just assume I have a code where we only ever use combinations of 0s or 1s. To encrypt the message we flip each bit — 0 goes to 1 or 1 goes to 0 — using my random list of heads and tails according to the following rule: If I have a head flip the bit, otherwise leave it the same. I now have a randomized message, and it really is truly random. To convince yourself, imagine answering the question, do you like coffee or tea? Think of your answer and flip a coin. If the coin lands heads change your answer otherwise leave it the same. Now write your answer down. Try it out a few times. Do you see you end up with a totally random set of decisions — tea, coffee, coffee, tea, tea, tea. If you don't record the coin toss there is no way to determine your true answer. Similarly, the message I encoded above now looks like a completely random stream of 1s and 0s and the only person who can decode it is the party with the other record of the coin tosses. Apply this to the message and, as if by magic, the message reappears. Any other random sequence will yield gibberish. It has to be the SAME random sequence I used in the first place. Mathematically, the proof involves working out that the probability of getting the right answer by applying a random sequence is 1 in 2" and the probability I could guess the answer is also 1 in 2"? The same! So the chance of decrypting the message knowing the encryption method is the same as simply guessing the message and getting lucky. Th