# One-Time Pads

*by Ben Goren*

## Introduction

People have long sought ways to protect their communications from eavesdroppers. Caesar shifted the letters of the alphabet; modern computers rely on high-powered math and very large numbers. With one exception, all have theoretical weaknesses—though, in fairness, the theoretical weaknesses in some of today’s systems require assuming that every atom in the universe is a supercomputer working to break the message for hundreds of billions of years.

The single exception, a one-time pad, is proveably, absolutely, unbreakable. It’s quite simple in principle, although it is a bit cumbersome to implement in most situations. If you’re willing to sacrifice convenience for confidentiality, though, it truly can’t be beat.

## Historical Implementation

One-time pads date back to the early twentieth century, and originally were used for teletype operators. If Alice and Bob wanted communicate securely, they would first get together for a Scrabble party. In addition to whatever fun they had with word games, they would put one (and only one) of every letter into a bag. Then—“shaken, not stirred”—they would mix up the letters in the bag. A single letter would be removed, written down on a pad of paper with a single carbon copy. They would put the letter back in, shake, and repeat until they had a booklet full of random letters. Each would take a copy of the pad, and they would burn the carbon paper.

Let’s assume that this is the result of their Scrabble party:

`OQONDALHJHNIJKTLXGHWQSMAKQNMJSCR`

EZAILEUMEKTJRAOHKHARFOUKASTUQOBR

SOLWAUKBIXEESKCVHXXFYSSNKLINXNIL

UNJYLWCKBBAHNRFRLHURSCHMDEDZWZMR

AKMDNKAHVWXOQIPDCSFUFZPKSYVFHFJK

RNEHATQGUMBPYTRHMXYBMYGAMMWBMNAE

NUSWXVOHLVVBOFQOWCDJPUUSKMXNLZ

The time has come for Alice to communicate secretly with Bob. Her first message is as follows:

Congress shall make no law respecting an establishment of religion, or prohibiting the free exercise thereof; or abridging the freedom of speech, or of the press; or the right of the people peaceably to assemble, and to petition the Government for a redress of grievances.

Before she can send it, she must first strip out spaces and punctuation and convert lower-case characters to upper-case characters. Note that the concept of a one-time pad works equally well with binary data, as you’ll see below—this particular restriction is solely because Alice and Bob’s Scrabble set only has upper-case letters.

CONGRESSSHALLMAKENOLAWRESPECTING

ANESTABLISHMENTOFRELIGIONORPROHI

BITINGTHEFREEEXERCISETHEREOFORAB

RIDGINGTHEFREEDOMOFSPEECHOROFTHE

PRESSORTHERIGHTOFTHEPEOPLEPEACEA

BLYTOASSEMBLEANDTOPETITIONTHEGOV

ERNMENTFORAREDRESSOFGRIEVANCES

Now, it’s time to encrypt the message. Alice takes the first letter of her message and the first letter of her pad, and “adds” them together, wrapping around when she gets to the end of the alphabet. For example, if the first letter of her message was “D” and the first letter of the pad was “C,” the first letter of the encrypted message would be “G.” If the next letter of the message was “Y” and the next letter of the pad was “F,” the next letter of the encrypted message would be “D.” Here’s all three versions laid out:

OQONDALHJHNIJKTLXGHWQSMAKQNMJSCR

CONGRESSSHALLMAKENOLAWRESPECTING

RFCUVFEACPOUVXUWCUWIRPEFDGSPDBQY

EZAILEUMEKTJRAOHKHARFOUKASTUQOBR

ANESTABLISHMENTOFRELIGIONORPROHI

FNFBFFWYNDBWWOIWQZFDOVDZOHLKIDJA

SOLWAUKBIXEESKCVHXXFYSSNKLINXNIL

BITINGTHEFREEEXERCISETHEREOFORAB

UXFFOBEJNDWJXPAAZAGYDMASCQXTMFJN

UNJYLWCKBBAHNRFRLHURSCHMDEDZWZMR

RIDGINGTHEFREEDOMOFSPEECHOROFTHE

MWNFUKJEJGGZSWJGYWAKIHMPLTVOCTUW

AKMDNKAHVWXOQIPDCSFUFZPKSYVFHFJK

PRESSORTHERIGHTOFTHEPEOPLEPEACEA

QCRWGZSBDBPXXQJSIMNZVEEAEDLKIIOL

RNEHATQGUMBPYTRHMXYBMYGAMMWBMNAE

BLYTOASSEMBLEANDTOPETITIONTHEGOV

TZDBPUJZZZDBDUFLGMOGGHAJBAQJRUPA

NUSWXVOHLVVBOFQOWCDJPUUSKMXNLZRK

ERNMENTFORAREDRESSOFGRIEVANCES

SMGJCJINANWTTJITPVSPWMDXGNLQQS

Alice then sends the following to Bob:

RFCUVFEACPOUVXUWCUWIRPEFDGSPDBQY

FNFBFFWYNDBWWOIWQZFDOVDZOHLKIDJA

UXFFOBEJNDWJXPAAZAGYDMASCQXTMFJN

MWNFUKJEJGGZSWJGYWAKIHMPLTVOCTUW

QCRWGZSBDBPXXQJSIMNZVEEAEDLKIIOL

TZDBPUJZZZDBDUFLGMOGGHAJBAQJRUPA

SMGJCJINANWTTJITPVSPWMDXGNLQQS

Next comes an extremely important step: Alice destroys her pad (or, at least, the parts of it she used for this message).

Alice can now use means she likes to send the message—she could even place it as an advertisement in the paper preceeded by “ULTRA-SECRET MESSAGE TO BOB.” Nobody except for Bob can decrypt the message—or even, for that matter, know that it isn’t truly random gibberish.

When Bob recieves the message, he takes out his copy of the pad and applies the reverse process to read the message. When he’s finished decoding it, he, too, destroys his copy of the pad. Now, there is nobody who has any chance of decrypting the message. If both Alice and Bob destroyed the decrypted versions of the note, nobody will ever know what it said, even if they have the encrypted form and all the resources in the universe.

The reason this works is that every encrypted letter depends on the random process used to generate a matching letter in the pad. In fact, if “they” threaten Bob with thumbscrews, he could supply a fake pad that made the encrypted text decrypt to whatever he wanted:

QMMPSLMVTWGTAJANONRNZAOAJYNWNWNE

ASPECTREISHAUNTINGEUROPETHESPECT

RFCUVFEACPOUVXUWCUWIRPEFDGSPDBQY

NIQVCQJLSPSDJNWKWRANZYYHVSFVWZEF

REOFCOMMUNISMALLTHEPOWERSOFOLDEU

FNFBFFWYNDBWWOIWQZFDOVDZOHLKIDJA

CIPAGAIEIPCEFKWRLGRXVXOTBELKLRGI

ROPEHAVEENTEREDINTOAHOLYALLIANCE

UXFFOBEJNDWJXPAAZAGYDMASCQXTMFJN

SHIHFSGVQBMRJDQQTTGSDRXZGSHKIATE

TOEXORCISETHISSPECTREPOPEANDTSAR

MWNFUKJEJGGZSWJGYWAKIHMPLTVOCTUW

DXXCBHESATOJTJOJIXTTDZQXWLKGZFNZ

METTERNICHANDGUIZOTFRENCHRADICAL

QCRWGZSBDBPXXQJSIMNZVEEAEDLKIIOL

AYPXIPRMYLNMRLCGNWFBNKSEJVHQXMKK

SANDGERMANPOLICESPIESWHEREISTHEP

TZDBPUJZZZDBDUFLGMOGGHAJBAQJRUPA

RUMKTVTXKYDKZATFVNRVOLKJRTJLLE

ARTYINOPPOSITIONTHATHASNOTBEEN

SMGJCJINANWTTJITPVSPWMDXGNLQQS

See? The ciphertext is exactly the same, but the pad is completely different, and the revealed message is also completely different. Because there’s an equal chance of any given letter being plucked from the bag, there’s also an equal chance of any given letter being the resulting encrypted character. In fact, Albert and Barbara could have sent the exact same encrypted message in the same paper on the same day, but, because their pad is different, the unencrypted message is also different.

## Modern Implementation

Modern computers store everyting in binary form—that is, as a whole heck of a lot of ones and zeroes. Any kind of data that can be stored on a computer can be represented as a string of ones and zeroes. Demonstrating how is beyond the scope of this document, but assume that a simplistic computer uses the following table to translate the alphabet into ones and zeroes:

Character | Binary Equivalent |
---|---|

`A` | `00000` |

`B` | `00001` |

`C` | `00010` |

`D` | `00011` |

`E` | `00100` |

`F` | `00101` |

`G` | `00110` |

`H` | `00111` |

`I` | `01000` |

`J` | `01001` |

`K` | `01010` |

`L` | `01011` |

`M` | `01100` |

`N` | `01101` |

`O` | `01110` |

`P` | `01111` |

`Q` | `10000` |

`R` | `10001` |

`S` | `10010` |

`T` | `10011` |

`U` | `10100` |

`V` | `10101` |

`W` | `10110` |

`X` | `10111` |

`Y` | `11000` |

`Z` | `11001` |

`[space]` | `11010` |

`.` | `11011` |

`?` | `11100` |

`’` | `11101` |

`(` | `11110` |

`)` | `11111` |

Obviously, this leaves out all lower-case letters, all numbers, and a lot of punctuation…but it’s enough for an example to make sense. If you want to encode more information, start adding more ones and zeroes.

Here’s how we might encode the message. If you see spaces in your browser, they’re just there for readability; the computer only stores ones and zeroes.

`A`

`T`

`T`

`A`

`C`

`K`

`A`

`T`

`00000`

`10011`

`10011`

`00000`

`00010`

`01010`

`11010`

`00000`

`10011`

`11010`

`D`

`A`

`W`

`N`

`?`

`N`

`O`

`.`

`00011`

`00000`

`10110`

`01101`

`11100`

`11010`

`01101`

`01110`

`11011`

`11010`

`W`

`A`

`I`

`T`

`.`

`10110`

`00000`

`01000`

`10011`

`11011`

Next, we get out a coin. Any coin will do, so long as it’s not weighted to favor one side over another. If the coin comes up heads, mark a one; otherwise, a zero. There are 125 bits (a bit is a single instance of a one or a zero) in this message, so we need to flip the coin 125 times:

`01001001100001001011110010101110101011111111101011`

01110111000100000000101001000010110110111111111111

0001010000111000101100100

In order to combine the two, you need to use a logical function known as XOR. It’s quite simple: if two bits are the same, the resulting bit is 0. If they’re different, the resuting bit is 1. Here’s a table to help:

Original Bit | Pad Bit | Encrypted Bit |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

Let’s now write out the original message, the pad, and the encrypted message:

`00000100111001100000000100101011010000001001111010`

01001001100001001011110010101110101011111111101011

01001101011000101011110110000101111011110110010001

00011000001011001101111001101001101011101101111010

01110111000100000000101001000010110110111111111111

01101111001111001101010000101011011101010010000101

1011000000010001001111011

0001010000111000101100100

1010010000101001100011111

To recover the original message when given the encrypted version and the pad, again XOR the two streams of bits. Try it above: pick any two of a trio of ones and zeros above, XOR the two, and you’ll get the third.

Again, since your coin has an equal chance of coming up either heads or tails, the resulting encrypted bit has an equal chance of being a one or a zero…and there’s no way to know which was intended without the pad.

Since this would all be done on a computer, the encrypted message would most likely be sent in binary format and the two computers would worry about everything. You could, however, translate either the pad or the encrypted version into letters using the appropriate table above…but that just adds an extra step to the process.

## Unless….

From the standpoint of information theory, a one-time pad is perfectly secure (assuming the process used to create the pad is truly random). In reality, there are a few weaknesses worth noting.

First, it’s quite cumbersome. Before two parties can exchange messages securely, both need a copy of the same pad. Anybody who can intercept the pad can read all subsequent messages. If you’ve got a secure way of transmitting the pad…why not use it to transmit the message, as well? When one-time pads are used, the two parties typically meet in person, create the pad, and then use it for subsequent communications.

You need as much data in the pad as in the message. If you’re going to send a novel and encrypt it with a one-time pad, you first need to create a novel-sized pad. One-time pads are usually used for relatively short messages—though, with a CD-ROM filled with random bits, the term “relative” should be used advisedly.

If the pad and message aren’t perfectly synchronized—if they’re shifted by even one position—the result is gibberish; the technique is fragile. (Try it yourself on the above data.) One-time pads should only be used when it’s better to lose the message entirely than have it fall into the worng hands.

If the pad itself is ever reused, and an adversary has a copy of two messages encoded with the same pad, it’s trivial to recover the pad and therefore the contents of the message. Only people with good discipline and understanding of one-time pads should use them.

As with all forms of encryption, a one-time pad can only protect the encrypted form of the message. It doesn’t, for example, protect against somebody installing a camera to look over Alice’s shoulder as she composes her message to Bob. If Bob spills his guts…ah…just before he spills his guts, the encryption is likewise meaningless.

And, finally, should anybody figure out a practical method of time travel, all bets are off.