One Time Pad (OTP)

Introduction

First described by Frank Miller in 1882, the one-time pad was re-invented in 1917 by Gilbert Vernam. It is an encryption technique which involves using a key that is as long as the message itself and consists of truly random values. To encrypt a message, each character (or bit) of the plaintext is combined with the corresponding character (or bit) of the key. This combination is typically done using a simple operation such as the XOR (exclusive or) function. For instance, in binary, each bit of the plaintext is XORed with the corresponding bit of the key. In the case of text, a modular addition might be used, where each letter's numerical value (e.g., A=0, B=1, ..., Z=25) is added to the value of the corresponding letter in the key, and the sum is taken modulo the size of the alphabet (typically 26 for English). The result is a ciphertext that is completely random and bears no statistical relationship to the plaintext. For decryption, the process is reversed: the ciphertext is combined with the same key using the same operation, which retrieves the original plaintext. The security of the OTP is contingent on the key being truly random, kept secret, used only once, and destroyed after use.

Two requirements

1. Key must be atleast as long as a message.
2. All the keys are uniformly distributed in key space.
3. Key must be randomly selected from the key space.

Why the name "one time pad"?
The term "One-Time Pad" (OTP) is derived from its historical usage, where the key material was distributed as a pad of paper containing pre-generated, random key values. Each page of the pad was used to encrypt and then decrypt a single message, after which it was discarded. The key on each page was used only once, hence the name "one-time." The concept was that once a page (or "pad") was used for encryption, it was torn off and destroyed, ensuring that the key was never reused.

Example 1: A Simple Illustration

Imagine we have a message JULIUS and a randomly chosen secret key DKMWVI, both of the same length. To encrypt the message using this key, we first convert each letter to its corresponding numeric position in the alphabet: A is 1, B is 2, and so on. Thus, JULIUS becomes the sequence 10, 21, 12, 9, 21, 19, and DKMWVI translates to 4, 11, 13, 23, 22, 9. The next step in the encryption process involves using modular arithmetic. We add each number from the message to the corresponding number from the key, and if the sum exceeds 26 (the number of letters in the alphabet), we wrap around by applying the modulus 26 operation. This method ensures each letter in the original message is shifted by a position determined by the corresponding letter in the key, resulting in a securely encrypted message.

Plaintext	JULIUS	10, 21, 12, 9, 21, 19
Key	DKMWVI	4, 11, 13, 23, 22, 9
Ciphertext	NFYFQB	14, 6, 25, 6, 17, 2

Example 2: Vernam cipher

In Vernam cipher the encryption is performed by combining the plaintext message with the key using bitwise XOR (exclusive or, $\oplus$) operation. In a more traditional approach where letters are used instead of binary, each letter of the plaintext is shifted along the alphabet by a number of places defined by the corresponding letter in the key. We saw this above.

Formally:
$C:=\textit{E}(K,M)=K \oplus M$ and $\textit{D}(K,C)=K \oplus C$.

Properties of message space, ciphertext space and key space:
$\mathcal{M}=\mathcal{C}=\{0,1\}^n$, and $\mathcal{K}=\{0,1\}^n$.

XOR ($\oplus$) truth table:

A (Input 1)	B (Input 2)	A $\oplus$ B (Output)
0	0	0
0	1	1
1	0	1
1	1	0

Check the consistency equation:

Problem with OTP?

Definition of perfect secrecy by Shannon.

Plaintext	S								h								a								n								n								o								n
Plaintext in Binary	0	1	0	1	0	0	1	1	0	1	1	0	1	0	0	0	0	1	1	0	0	0	0	1	0	1	1	0	1	1	1	0	0	1	1	0	1	1	1	0	0	1	1	0	1	1	1	1	0	1	1	0	1	1	1	0
Key	0	1	1	1	0	0	0	0	0	1	1	1	1	0	0	1	0	1	1	0	0	1	0	1	0	1	1	1	1	0	1	0	0	1	1	0	1	0	0	0	0	1	1	1	0	0	1	0	0	1	1	1	0	0	1	1
Ciphertext (XOR)	0	0	1	0	0	0	1	1	0	0	0	1	0	0	0	1	0	0	0	0	0	1	0	0	0	0	0	1	0	1	0	0	0	0	0	0	0	1	1	0	0	0	0	1	1	1	0	1	0	0	0	1	1	1	0	1

Key is "pyezhrs" in binary

Important property of XOR

Theorem: Let $Y$ be a random variable over $\{0,1\}^n$ with some distribution. Let $X$ be an independent random variable over $\{0,1\}^n$ with uniform distribution, then

$$Z:=Y \oplus X$$

is a random variable over $\{0,1\}^n$ with uniform distribution.

Proof:

Ques: What would be the distribution of $Z$ if $X$ is not uniform?