World Library  
Flag as Inappropriate
Email this Article
 

Gilbert Vernam

Gilbert Sandford Vernam (3 April 1890 – 7 February 1960) was a Worcester Polytechnic Institute 1914 graduate and AT&T Bell Labs engineer who, in 1917, invented an additive polyalphabetic stream cipher and later co-invented an automated one-time pad cipher. Vernam proposed a teleprinter cipher in which a previously prepared key, kept on paper tape, is combined character by character with the plaintext message to produce the ciphertext. To decipher the ciphertext, the same key would be again combined character by character, producing the plaintext. Vernam later worked for the Postal Telegraph Company, and became an employee of Western Union when that company acquired Postal in 1943. His later work was largely with automatic switching systems for telegraph networks.

Contents

  • Vernam's patent 1
  • One-time pad 2
  • The Vernam cipher 3
  • Notes 4
  • References 5

Vernam's patent

Figure 1 from Vernam's patent.

The combining function Vernam specified in U.S. Patent 1,310,719, issued July 22, 1919, is the XOR operation, applied to the individual impulses or bits used to encode the characters in the Baudot code. Vernam did not use the term "XOR" in the patent, but he implemented that operation in relay logic. In the example Vernam gave, the plaintext is A, encoded as "++---" in Baudot, and the key character is B, encoded as "+--++". The resulting ciphertext will be "-+-++", which encodes a G. Combining the G with the key character B at the receiving end produces "++---", which is the original plaintext A. The NSA has called this patent "perhaps one of the most important in the history of cryptography.".[1]

One-time pad

Shortly thereafter, US Army Signal Corps, proposed, in addition, that the paper tape key contain random information. The two ideas, when themselves combined, implement an automatic form of the one-time pad, though neither inventor used the name then. It was patented in the mid-1920s.

Claude Shannon, also at Bell Labs, proved that the one-time pad is unbreakable in his World War II research that was later published in October 1949. He also proved that any unbreakable system must have essentially the same characteristics as the one-time pad: the key must be truly random, as large as the plaintext, never reused in whole or part, and kept secret.[2]

The Vernam cipher

In modern terminology, a Vernam cipher is a symmetrical stream cipher in which the plaintext is combined with a random or pseudorandom stream of data (the "keystream") of the same length, to generate the ciphertext, using the Boolean "exclusive or" (XOR) function. This is symbolised by ⊕ [3] and is represented by the following "truth table", where + represents "true" and − represents "false".

INPUT OUTPUT
A B AB
+ +
+ +
+ +

Other names for this function are: Not equal (NEQ), modulo 2 addition (without 'carry') and modulo 2 subtraction (without 'borrow').

The cipher is reciprocal in that the identical keystream is used both to encipher plaintext to ciphertext and to decipher ciphertext to yield the original plaintext:

Plaintext ⊕ Key = Ciphertext

and:

Ciphertext ⊕ Key = Plaintext

If the keystream is truly random and used only once, this is effectively a one-time pad. Substituting pseudorandom data generated by a cryptographically secure pseudo-random number generator is a common and effective construction for a stream cipher. RC4 is an example of a Vernam cipher that is widely used on the Internet.

If, however, the same keystream is used for two messages, known to cryptanalysts as a depth, the effect of the keystream can be eliminated, leaving the two plaintexts XORed together. The result is equivalent to a Running key cipher and the two plaintexts may be separated by linguistic cryptanalytical techniques.

Ciphertext1 ⊕ Ciphertext2 = Plaintext1 ⊕ Plaintext2

An operator's mistake of this sort famously allowed the Cryptanalysis of the Lorenz cipher by the British at Bletchley Park during World War II. They diagnosed how the keystream was generated, worked out how to break the cipher, and read vast quantities of high-level messages to and from German high command without ever seeing an actual Lorenz machine.[4]

Notes

  1. ^ Klein, p. 3 “Vernam had invented the unbreakable cipher: “one-time tape” (OTT) for on-line TTY encryption. In 1919 he was granted a patent, perhaps one of the most important in the history of cryptography.”
  2. ^ Shannon 1949
  3. ^ Klein, p. 2
  4. ^ Tutte 2006, pp. 4–6

References

  • Klein, Melville, Securing Record Communications: The TSEC/KW-26 (PDF), retrieved 2012-04-12 
  •  
  • University of Waterloo Transcript of a lecture given by Prof. Tutte at the  
  • Vernam, Gilbert S. (1926), "Cipher Printing Telegraph Systems For Secret Wire and Radio Telegraphic Communications", Journal of the IEEE 55: 109–115 
  • Vernam, Gilbert S. (April 1932), "An Automatic Concentration Unit for Printing Telegraph Circuits", Electrical Communication: 200 
  • Vernam, Gilbert S. (July 1938), "Printing Telegraph Operation of Way Wires", AIEE Transactions 57: 365,  
  • Vernam, Gilbert S. (April 1958), "Printing Telegraph Systems For Secret Wire and Radio Telegraphic Communications", Western Union Technical Review 12 (2): 37  Also in Vernam, Gilbert S. (May 1958), "Automatic Telegraph Switching System Plan 55-A", AIEE Transactions on Communication and Electronics: 239 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.