โ† Wiki Index / Computation & Algorithms / One-Time Pad
๐Ÿ’ป Computation & Algorithms

One-Time Pad

The one-time pad is an encryption technique that achieves mathematical perfect secrecy by combining a plaintext message with a truly random, single-use key of equal length via modular addition.

One-Time Pad (OTP) is a symmetric encryption algorithm in computation and algorithms that achieves mathematical perfect secrecy by combining a plaintext message with a truly random secret key of equal length via bitwise exclusive-OR (XOR) or modular addition. Originally conceived by American engineer Gilbert Vernam in 1917 as an automated telegraph cipher and augmented by US Army officer Joseph Mauborgne with the requirement of infinite non-repeating key entropy, the one-time pad represents the sole cryptosystem mathematically proven to be unbreakable against an adversary with unlimited computational resources.

Within computational complexity theory, conventional cryptographic algorithmsโ€”such as the RSA cryptosystem or the Advanced Encryption Standardโ€”rely on computational hardness assumptions (the unproven intractability of integer factorization or discrete logarithms). In contrast, the security of the one-time pad is information-theoretic, derived from the mathematical laws of probability rather than limits on processing power or algorithmic runtime.

Mathematical Formulation and Claude Shannon's Perfect Secrecy

Let the plaintext message M and the secret key K be binary strings of length n, where M, K โˆˆ {0, 1}n. The ciphertext C is produced by evaluating the bitwise XOR operation (addition modulo 2) across each bit position:

C = M โŠ• K

Decryption evaluates the identical bitwise XOR operation on the ciphertext using the identical secret key:

M = C โŠ• K = (M โŠ• K) โŠ• K = M โŠ• (K โŠ• K) = M โŠ• 0n = M

In his seminal 1949 treatise "Communication Theory of Secrecy Systems", Claude Shannon formalized the concept of Perfect Secrecy. A cryptosystem achieves perfect secrecy if and only if the conditional probability of observing any plaintext message M, given that a particular ciphertext C has been intercepted, equals the a priori probability of that plaintext:

P(M = m | C = c) = P(M = m) for all messages m and ciphertexts c

Equivalently, expressed in the language of Shannon entropy, the mutual information I(M; C) between the plaintext and the ciphertext is zero:

I(M; C) = H(M) โˆ’ H(M | C) = 0

Shannon proved mathematically that for any cipher to achieve perfect secrecy, two immutable conditions must hold:

  1. The secret key K must be drawn from a uniform probability distribution over {0, 1}n, with each bit possessing independent entropy H(ki) = 1.
  2. The key entropy must be at least as large as the message entropy: H(K) โ‰ฅ H(M), which implies that the key length must be greater than or equal to the message length.

Because every candidate plaintext string of length n can be generated by exactly one corresponding key K = C โŠ• m, an intercepted ciphertext C provides an adversary with zero statistical leverage to favor one meaningful plaintext interpretation over any other conceivable plaintext of identical length.

Two-Time Pad Vulnerability and Key Reuse

The security of the one-time pad degrades rapidly if a key is reused to encrypt more than one message. Suppose two distinct plaintexts M1 and M2 are encrypted under an identical key K, yielding ciphertexts C1 = M1 โŠ• K and C2 = M2 โŠ• K. An eavesdropper intercepting both ciphertexts computes their XOR difference:

C1 โŠ• C2 = (M1 โŠ• K) โŠ• (M2 โŠ• K) = M1 โŠ• M2

The shared secret key K cancels out in the XOR sum, leaving the raw difference of the two plaintexts. Because natural human language, file formats, and network payloads possess high redundancy and low entropy per character (typically 1.0 to 1.5 bits per character for English prose), cryptanalysts exploit frequency distributions and crib draggingโ€”sliding probable words across C1 โŠ• C2 to observe whether the resulting complementary text yields plausible language fragmentsโ€”to reconstruct both plaintexts simultaneously.

This mathematical vulnerability formed the operational foundation of the mid-twentieth-century Venona Project, wherein American and British cryptanalysts successfully decrypted thousands of Soviet diplomatic and intelligence cables because Soviet cryptographic bureaus had mistakenly manufactured and distributed duplicate one-time pad codebook pages during the logistics pressures of World War II.

The Key Distribution Dilemma and Practical Applications

Despite its unconditional mathematical perfection, the one-time pad is rarely deployed in modern general-purpose computing networks due to four fundamental practical constraints:

  • Key Distribution and Storage: Securely communicating an n-bit key requires an authenticated, confidential channel whose bandwidth equals the total volume of data to be transmitted, creating a circular key-distribution dilemma.
  • True Randomness Generation: The key material must be generated by physical non-deterministic entropy sources (such as radioactive decay, thermal semiconductor noise, or quantum vacuum fluctuations) rather than pseudorandom number generators, which reduce the system to a stream cipher vulnerable to algorithmic analysis.
  • Lack of Integrity Protection: The one-time pad is malleable. An active man-in-the-middle attacker who alters bit i in the ciphertext C flips bit i in the decrypted plaintext M without detection, requiring supplemental message authentication codes (such as Carterโ€“Wegman MACs) to ensure data authenticity.

Consequently, historical and modern deployments of the one-time pad are reserved for ultra-high-security diplomatic channels (such as the Moscowโ€“Washington hotline established after the Cuban Missile Crisis) and high-value sovereign military communication systems where pre-shared physical key material can be distributed in advance via diplomatic couriers.

Comparison of Secrecy Models

Security ParadigmDefining Theoretical CriterionAdversarial Power AssumedRepresentative PrimitivesPractical Vulnerability Vector
Information-Theoretic SecurityI(M; C) = 0; unconditional perfect secrecyInfinite computational powerOne-Time Pad, Shamir's Secret SharingKey reuse, physical codebook theft
Computational SecurityPolynomial-time distinguishing advantage is negligibleBounded polynomial-time algorithmsAES, ChaCha20, RSAAlgorithmic breakthroughs, quantum computing
Quantum Key Distribution (QKD)Physical no-cloning theorem; eavesdropping perturbs statesQuantum mechanics lawsBB84 Protocol, E91Side-channel detector blinding attacks

References

  1. Shannon, C. E. (1949). Communication theory of secrecy systems. Bell System Technical Journal, 28(4), 656-715.
  2. Vernam, G. S. (1926). Cipher printing telegraph systems for secret wire and radio telegraphic communications. Transactions of the American Institute of Electrical Engineers, 45, 109-115.
  3. Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6), 644-654.
  4. Bellovin, S. M. (2011). Frank Miller: Inventor of the One-Time Pad. Cryptologia, 35(3), 203โ€“222.
๐Ÿงฌ Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
๐Ÿ’ก Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision