Cryptography/One time pads

A One Time Pad (OTP) is the only potentially unbreakable encryption method. Plain text encrypted using an OTP cannot be retrieved without the encrypting key. However, there are several key conditions that must be met by the user of a one time pad cipher, or the cipher can be compromised.

The key must be random and generated by a non-deterministic, non-repeatable process. Any key generated by an algorithm will not work. The security of the OTP relies on the randomness of the key. Unfortunately, the randomness of a key cannot be proved.
The key must never be reused. Use of the same key to encrypt different messages, no matter how trivially small, compromises the cipher.
The key must not fall in the hands of the enemy. This may seem obvious, but it points to the weakness of system in that you must be able to transmit large amounts of data to the reader of the pad. Typically, one time pad cipher keys are sent via diplomatic pouch.

A typical one time pad system works like this: Generate a long fresh new random key. XOR the plaintext with the key to create the ciphertext. To decrypt the ciphertext, XOR it with the original key. The system as presented is thus a symmetric and reciprocal cipher. Other functions (e.g., addition modulo n) could be used to combine the key and the plaintext to yield the ciphertext, although the resulting system may not be a reciprocal cipher.

If the key is random and never re-used, an OTP is provably unbreakable. Any ciphertext can be decrypted to any message of the same length by using the appropriate key. Thus, the actual original message cannot be determined from ciphertext alone, as all possible plaintexts are equally likely. This is the only cryptosystem for which such a proof is known.

The OTP is extremely simple to implement.^[1]

However, there are limitations. Re-use the key and the system becomes extremely weak; it can be broken with pencil and paper. Try to build a "one-time-pad" using some algorithm to generate the keys and you don't have a one-time-pad, you have a stream cipher. There are some very secure stream ciphers, but people who do not know one from a one-time pad are probably not able to design one. It is unfortunately fairly common to see weak stream ciphers advertised as unbreakable one-time pads.

Also, even if you have a well-implemented OTP system and your key is kept secure, consider an attacker who knows the plaintext of part of a message. He can then recover that part of the key and use it to encrypt a message of his own. If he can deliver that instead of yours, you are in deep trouble.

Example

First, an OTP is selected for the plaintext:

Preshared Random Bits = 1010010010101010111010010000101011110101001110100011
           Plain text = 110101010101010010100
   Length(Plain Text) = 21
              Key(21) = 101001001010101011101

Wikipedia has related information at Padding (cryptography)

The example indicates that the plaintext is not always the same length as the key material. This can be handled by methods such as:

appending a terminator to the plaintext before encryption, and terminating the cyphertext with random bits.
prepending the length and a preamble terminator to the plaintext, and terminating with random bits.

Such signaling systems (and possibly the plaintext encoding method) must be designed so that these terminators are not mistaken for plaintext. For this example, therefore, it is assumed the plaintext already contains endpoint/length signaling.

For increasingly long plaintext/key pair lengths, the cross-correlation gets closer to zero.

Encryption

Key(21)    = 101001001010101011101
Plaintext  = 110101010101010010100
 $\oplus$ bitwise    |||||||||||||||||||||
cyphertext = 011100011111111001001

For increasingly long plaintext/cyphertext pair lengths, the cross-correlation also gets closer to zero.

Decryption

Preshared Random Bits = 1010010010101010111010010000101011110101001110100011
           cyphertext = 011100011111111001001
            $\oplus$ bitwise    |||||||||||||||||||||
           Plain text = 110101010101010010100

An astute reader might observe that the decryptor needs to know the length of the plaintext in actual practice. This is done by decrypting the cyphertext as a bitstream (i.e. xor each bit as it is read), and observing the stream until the end-of-plaintext ruleset is satisfied by the signals prepended/appended to the plaintext.

Making one-time pads by hand

One-time pads were originally made without the use of a computer and this is still possible today. The process can be tedious, but if done correctly and the pad used only once, the result is unbreakable.

There are two components needed to make a one-time pad: a way to generate letters at random and a way to record two copies of the result. The traditional way to do the latter was to use a w:typewriter and w:carbon paper. The carbon paper and w:typewriter ribbon would then be destroyed since it is often possible to recover the pad data from them. As typewriters have become scarce, it is also acceptable to hand write the letters neatly in groups of five on two part w:carbonless copy paper sheets, which can be purchased at office supply stores. Each sheet can given a serial number or some other unique marking.

Historically, the key material for manual one-time pads was distributed as a pad of many small pages of paper. Each small page typically had a series of 5-digit groups, each digit randomly selected from 0 to 9.^[2]^[3]^[4]^[5]^[6]^[7]^[8]^[9]

A one-time pad set consists of two identical pads. Some writers refer to the two as "two identical originals", to emphasize that no copies should ever be made of the key material.^[10]

Traditionally two-way communication requires two pad sets (a total of 4 pads): One person gets the "IN" pad of one set, and the "OUT" pad of the other set.^[11]

Each small page typically contains 50 groups of 5 random decimal digits 0...9, enough for one normal message, and a unique "page number" of five digits.^[11]^[12]

A conversion table is used to convert the letters of the plaintext message to numbers, and the numbers of the decoded message back to letters.^[5] Perhaps the simplest conversion table is A=01, B=02, ... Z=26, but historically some sort of straddling checkerboard was usually used, such as CT-37c,^[13] CT-37w, CT-46,^[14] etc.^[15]

The key material for a one-time pad was sometimes written as 50 groups of 5 random letters A...Z.^[12]^[16] One-time pads where the keys are written as letters are sometimes called letter one-time pad (LOP)^[17]^[18] or one-time letter pad (OTLP).^[11]

The key material for cryptographic machines, including one-time pad systems, was often punched in a binary code on long, narrow paper tape—a "one time tape" OTT.^[10]^[12]^[19]

letter tiles

The simplest way to generate random letters in the Roman alphabet is to obtain 26 identical objects with a different letter of the alphabet marked on each object. Tiles from the game w:Scrabble can be used, as long as only one of each letter is selected. Kits for making name charm bracelets are another possibility. One can also write the letters on 26 otherwise identical coins with a marking pen. The objects are placed in a box or cup and shaken vigorously, then one object is withdrawn and its letter is recorded. The object is returned to the box and the process is repeated.

10-sided dice

Another way to make one time pads is to use w:ten-sided dice. One can generate random number groups by rolling several ten-sided dice at a time and recording a group of decimal digits—one decimal digit from each die—for each roll.^[11] This method will generate random code groups much faster than using Scrabble tiles. The plaintext message is converted into numeric values with A =01, B =02 and so on. The resulting numeric values are encrypted by adding digits from the one time pads using non-carrying addition. One can then either transmit the numeric groups as is, or use the straddling checkerboard to convert the numbers back into letters and transmit that result.

6-sided dice

Another way to make one time pads is to use 6-sided dice.^[20]

It is possible to generate random decimal digits (to make a traditional decimal one-time pad) using 6-sided dice.^[11]

If the message is converted into two digit base-6 numbers, then ordinary six-sided dice can be used to generate the random digits in a one time pad. Digits in the pad would be added modulo-6 to the digits in the plaintext message (again without carry), and subtracted modulo 6 from the ciphertext to decrypt. For example:

Table for converting messages to base-6
PT	0	1	2	3	4	5	6	7	8	9
CT	00	01	02	03	04	05	10	11	12	13
PT	A	B	C	D	E	F	G	H	I	J	K	L	M
CT	14	15	20	21	22	23	24	25	30	31	32	33	34
PT	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
CT	35	40	41	42	43	44	45	50	51	52	53	54	55

Table for converting messages to base-6
		right	digit
left digit
	x0	x1	x2	x3	x4	x5
0x	0	1	2	3	4	5
1x	6	7	8	9	A	B
2x	C	D	E	F	G	H
3x	I	J	K	L	M	N
4x	O	P	Q	R	S	T
5x	U	V	W	X	Y	Z

Using this table, "Wikipedia" would convert to 52 30 32 30 41 22 21 30 14. If the pad digits were 42 26 21 35 32 34 22 62 43, the ciphertext would be 34 50 53 05 13 50 43 32 51. (Note that 6 = 0 modulo 6).

Key Exchange

In order to use this algorithm, each party must possess the same random key. This typically involves meeting the other party in person or using a trusted courier. Other methods are sometime proposed, such as or both users to have identical devices that generate the same semi-random numbers, however these methods are essentially w:stream ciphers and are not covered by the security proof of one time pads.