Gilbert Vernam
Encyclopedia
Gilbert Sandford Vernam was an AT&T
Bell Labs
engineer who, in 1917, invented the stream cipher
and later co-invented the 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 Postal Telegraph Co., and became an employee of Western Union when W.U. acquired
Postal in 1943. His later work was largely with automatic switching systems for teletypewriter networks.
The combining function Vernam specified in , issued July 22, 1919, is the XOR operation, applied to the individual impulses or bit
s used to encode the characters in the Baudot
Teletype
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.".
, at that time a captain in the 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.
in which the plaintext is XORed with a random or pseudorandom stream of data (the "keystream") of the same length to generate the ciphertext. 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.
AT&T
AT&T Inc. is an American multinational telecommunications corporation headquartered in Whitacre Tower, Dallas, Texas, United States. It is the largest provider of mobile telephony and fixed telephony in the United States, and is also a provider of broadband and subscription television services...
Bell Labs
Bell Labs
Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...
engineer who, in 1917, invented the stream cipher
Stream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
and later co-invented the one-time pad
One-time pad
In cryptography, the one-time pad is a type of encryption, which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key of the same length as the plaintext, resulting...
cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
. Vernam proposed a teleprinter cipher in which a previously-prepared key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
, kept on paper tape, is combined character by character with the plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
message to produce the ciphertext
Ciphertext
In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...
. To decipher the ciphertext, the same key would be again combined character by character, producing the plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
.
Vernam later worked for Postal Telegraph Co., and became an employee of Western Union when W.U. acquired
Postal in 1943. His later work was largely with automatic switching systems for teletypewriter networks.
Vernam's patent
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s used to encode the characters in the Baudot
Baudot code
The Baudot code, invented by Émile Baudot, is a character set predating EBCDIC and ASCII. It was the predecessor to the International Telegraph Alphabet No 2 , the teleprinter code in use until the advent of ASCII. Each character in the alphabet is represented by a series of bits, sent over a...
Teletype
Teletype Corporation
The Teletype Corporation, a part of American Telephone and Telegraph Company's Western Electric manufacturing arm since 1930, came into being in 1928 when the Morkrum-Kleinschmidt Company changed its name to the name of its trademark equipment...
code. Vernam did not use the term "XOR" in the patent, but he implemented that operation in relay
Relay
A relay is an electrically operated switch. Many relays use an electromagnet to operate a switching mechanism mechanically, but other operating principles are also used. Relays are used where it is necessary to control a circuit by a low-power signal , or where several circuits must be controlled...
logic. In the example Vernam gave, the plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
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.".
One-time pad
Shortly thereafter, Joseph MauborgneJoseph Mauborgne
In the history of cryptography, Joseph Oswald Mauborgne co-invented the one-time pad with Gilbert Vernam of Bell Labs. In 1914 he published the first recorded solution of the Playfair cipher...
, at that time a captain in the 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
One-time pad
In cryptography, the one-time pad is a type of encryption, which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key of the same length as the plaintext, resulting...
, though neither inventor used the name then. It was patented in the mid-1920s.
Claude Shannon
Claude Elwood Shannon
Claude Elwood Shannon was an American mathematician, electronic engineer, and cryptographer known as "the father of information theory"....
, also at Bell Labs, proved that the one-time pad is unbreakable in his World War II
World War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
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.
The Vernam cipher
In modern terminology, a Vernam cipher is a symmetrical stream cipherStream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
in which the plaintext is XORed with a random or pseudorandom stream of data (the "keystream") of the same length to generate the ciphertext. If the keystream is truly random and used only once, this is effectively a one-time pad
One-time pad
In cryptography, the one-time pad is a type of encryption, which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key of the same length as the plaintext, resulting...
. Substituting pseudorandom data generated by a cryptographically secure pseudo-random number generator is a common and effective construction for a stream cipher. RC4
RC4
In cryptography, RC4 is the most widely used software stream cipher and is used in popular protocols such as Secure Sockets Layer and WEP...
is an example of a Vernam cipher that is widely used on the Internet.