Encryption and the One-Time Pad

Encryption and the One-time Pad

There are many ways to scramble, or encrypt, data. How do we determine what constitutes good encryption? Let's try out an example. Enter a word or two you'd like encrypted below.

We converted your phrase to ALL CAPS and removed all but the Latin characters, in order to simplify our explanations below. Here it is after conversion:

Here are three different encryptions of your text:

Which one of these was obtained using secure encryption? Here are some facts about the methods used. The first one was used very recently to protect electronic documents against unauthorized copying; at least one programmer was jailed in the US for writing code to break it. The second one has been used for millennia. The third one was patented in 1919, but has seen only limited use.

ROT13: to encrypt a letter, find it on the wheel and write down the corresponding right next to it (either on its inside or its outside). For example, "A" becomes "N" and "V" becomes "I."

The first method, known as ROT13, simply substitutes for each letter the letter that is 13 steps away from it in the alphabet (looping back from Z to A if necessary). Thus, A becomes N, B becomes O, C becomes P, and so on. As you can see, the protection it offers can be broken by first-graders. As for the copy protection and the jailed programmer? Here's more on the story.

The third method, known as the one-time pad, has a separate random value for each letter of the message. All these values together make up the key. The key that was used to produce the encryption above is shown below. You can try different values to see how the encryption changes.

picture of paper punch tape with up to five holes per column

Tape used to store messages sent and received by telegraph, known as Baudot Tape. Source: Ricardo Ferreira de Oliveira

This method was patented by Gilbert Vernam in 1919 for use with the telegraph. At the time, the telegraph used a punch tape, much like the one in the picture. Each column in the tape represented a character, which was determined by which holes were punched through. Vernam's idea was to build a machine that would read two tapes: one that contained the message and another one that contained the key. The machine would then produce a new tape with the encryption. Its requirement for a long key has prevented it from being widely adopted; yet, it has had a tremendous influence on modern crytography and the ideas behind it are present in many of today's systems.

Here are some good questions about the one-time-pad. How many keys are there? How many possible different outputs for a given message? If you don’t know the key and see only the encrypted message, how much information can you obtain about the original message? Can we prove that this is a secure encryption method (before we can do that, we would, of course, have to define what the term “secure” means)?