One-time pad

A format of one-time pad used by the U.S. National Security Agency, code named DIANA. The table on the right is an aid for converting between plaintext and ciphertext using the characters at left as the key.

In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked, but requires the use of a single-use pre-shared key that is larger than or equal to the size of the message being sent. In this technique, a plaintext is paired with a random secret key (also referred to as a one-time pad). Then, each bit or character of the plaintext is encrypted by combining it with the corresponding bit or character from the pad using modular addition.[1]

The resulting ciphertext will be impossible to decrypt or break if the following four conditions are met:[2][3]

  1. The key must be at least as long as the plaintext.
  2. The key must be truly random.
  3. The key must never be reused in whole or in part.
  4. The key must be kept completely secret by the communicating parties.

It has also been mathematically proven that any cipher with the property of perfect secrecy must use keys with effectively the same requirements as OTP keys.[4] Digital versions of one-time pad ciphers have been used by nations for critical diplomatic and military communication, but the problems of secure key distribution make them impractical for most applications.

First described by Frank Miller in 1882,[5][6] the one-time pad was re-invented in 1917. On July 22, 1919, U.S. Patent 1,310,719 was issued to Gilbert Vernam for the XOR operation used for the encryption of a one-time pad.[7] Derived from his Vernam cipher, the system was a cipher that combined a message with a key read from a punched tape. In its original form, Vernam's system was vulnerable because the key tape was a loop, which was reused whenever the loop made a full cycle. One-time use came later, when Joseph Mauborgne recognized that if the key tape were totally random, then cryptanalysis would be impossible.[8]

The "pad" part of the name comes from early implementations where the key material was distributed as a pad of paper, allowing the current top sheet to be torn off and destroyed after use. For concealment the pad was sometimes so small that a powerful magnifying glass was required to use it. The KGB used pads of such size that they could fit in the palm of a hand,[9] or in a walnut shell.[10] To increase security, one-time pads were sometimes printed onto sheets of highly flammable nitrocellulose, so that they could easily be burned after use.

There is some ambiguity to the term "Vernam cipher" because some sources use "Vernam cipher" and "one-time pad" synonymously, while others refer to any additive stream cipher as a "Vernam cipher", including those based on a cryptographically secure pseudorandom number generator (CSPRNG).[11]

  1. ^ Lugrin, Thomas (2023), Mulder, Valentin; Mermoud, Alain; Lenders, Vincent; Tellenbach, Bernhard (eds.), "One-Time Pad", Trends in Data Protection and Encryption Technologies, Cham: Springer Nature Switzerland, pp. 3–6, doi:10.1007/978-3-031-33386-6_1, ISBN 978-3-031-33386-6
  2. ^ "Intro to Numbers Stations". Archived from the original on 18 October 2014. Retrieved 13 September 2014.
  3. ^ "One-Time Pad (OTP)". Cryptomuseum.com. Archived from the original on 2014-03-14. Retrieved 2014-03-17.
  4. ^ Shannon, Claude (1949). "Communication Theory of Secrecy Systems" (PDF). Bell System Technical Journal. 28 (4): 656–715. doi:10.1002/j.1538-7305.1949.tb00928.x.
  5. ^ Frank Miller (1882). Telegraphic Code to Insure Privacy and Secrecy in the Transmission of Telegrams  – via Wikisource.
  6. ^ Bellovin, Steven M. (2011). "Frank Miller: Inventor of the One-Time Pad". Cryptologia. 35 (3): 203–222. doi:10.1080/01611194.2011.583711. ISSN 0161-1194. S2CID 35541360.
  7. ^ "'Secret signaling system patent' on Google.Com". google.com. Archived from the original on 11 March 2016. Retrieved 3 February 2016.
  8. ^ Kahn, David (1996). The Codebreakers. Macmillan. pp. 397–8. ISBN 978-0-684-83130-5.
  9. ^ "One-Time-Pad (Vernam's Cipher) Frequently Asked Questions, with photo". Archived from the original on 2006-05-07. Retrieved 2006-05-12.
  10. ^ Savory, Stuart (2001). "Chiffriergerätebau : One-Time-Pad, with photo" (in German). Archived from the original on 2011-05-30. Retrieved 2006-07-24.
  11. ^ Kahn, David (1967). The Codebreakers. Macmillan. pp. 398 ff. ISBN 978-0-684-83130-5.