In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, the one-time pad (OTP) is an
encryption
In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can de ...
technique that cannot be
cracked
Cracked may refer to: Television
* ''Cracked'' (British TV series), a 2008 British comedy-drama television series that aired on STV
* ''Cracked'' (Canadian TV series), a 2013 Canadian crime drama series that aired on CBC
* "Cracked", a Season 8 ( ...
, but requires the use of a single-use
pre-shared key that is not smaller than the message being sent. In this technique, a
plaintext
In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted.
Overview
With the advent of com ...
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.
The resulting
ciphertext
In cryptography, ciphertext or cyphertext 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 ...
will be impossible to decrypt or break if the following four conditions are met:
#The key must be at least as long as the plaintext.
#The key must be random (
uniformly distributed in the set of all possible keys and
independent
Independent or Independents may refer to:
Arts, entertainment, and media Artist groups
* Independents (artist group), a group of modernist painters based in the New Hope, Pennsylvania, area of the United States during the early 1930s
* Independ ...
of the plaintext), entirely sampled from a non-algorithmic, chaotic source such as a
hardware random number generator
In computing, a hardware random number generator (HRNG) or true random number generator (TRNG) is a device that generates random numbers from a physical process, rather than by means of an algorithm. Such devices are often based on microscopic ...
. It is not sufficient for OTP keys to pass
statistical randomness tests as such tests cannot measure entropy, and the number of bits of entropy must be at least equal to the number of bits in the plaintext. For example, using cryptographic hashes or mathematical functions (such as logarithm or square root) to generate keys from fewer bits of entropy would break the uniform distribution requirement, and therefore would not provide perfect secrecy.
#The key must never be reused in whole or in part.
#The key must be kept completely
secret
Secrecy is the practice of hiding information from certain individuals or groups who do not have the "need to know", perhaps while sharing it with other individuals. That which is kept hidden is known as the secret.
Secrecy is often controvers ...
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.
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
Frank Miller (born January 27, 1957) is an American comic book writer, penciller and inker, novelist, screenwriter, film director, and producer known for his comic book stories and graphic novels such as his run on ''Daredevil'' and subsequen ...
in 1882,
the one-time pad was re-invented in 1917. On July 22, 1919, U.S. Patent 1,310,719 was issued to
Gilbert Vernam
Gilbert Sandford Vernam (April 3, 1890 – February 7, 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 on ...
for the
XOR operation used for the encryption of a one-time pad.
Derived from his ''Vernam cipher'', the system was a cipher that combined a message with a key read from a
punched tape
Five- and eight-hole punched paper tape
Paper tape reader on the Harwell computer with a small piece of five-hole tape connected in a circle – creating a physical program loop
Punched tape or perforated paper tape is a form of data storage ...
. 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
Joseph Oswald Mauborgne (February 26, 1881 – June 7, 1971) co-invented the one-time pad with Gilbert Vernam of Bell Labs. In 1914 he published the first recorded solution of the Playfair cipher. Mauborgne became a Major General in the U ...
recognized that if the key tape were totally random, then
cryptanalysis would be impossible.
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
The KGB (russian: links=no, lit=Committee for State Security, Комитет государственной безопасности (КГБ), a=ru-KGB.ogg, p=kəmʲɪˈtʲet ɡəsʊˈdarstvʲɪn(ː)əj bʲɪzɐˈpasnəsʲtʲɪ, Komitet gosud ...
used pads of such size that they could fit in the palm of a hand, or in a
walnut
A walnut is the edible seed of a drupe of any tree of the genus ''Juglans'' (family Juglandaceae), particularly the Persian or English walnut, '' Juglans regia''.
Although culinarily considered a "nut" and used as such, it is not a true ...
shell. To increase security, one-time pads were sometimes printed onto sheets of highly flammable
nitrocellulose
Nitrocellulose (also known as cellulose nitrate, flash paper, flash cotton, guncotton, pyroxylin and flash string, depending on form) is a highly flammable compound formed by nitrating cellulose through exposure to a mixture of nitric acid and ...
, 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
A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely kno ...
(CSPRNG).
History
Frank Miller
Frank Miller (born January 27, 1957) is an American comic book writer, penciller and inker, novelist, screenwriter, film director, and producer known for his comic book stories and graphic novels such as his run on ''Daredevil'' and subsequen ...
in 1882 was the first to describe the one-time pad system for securing telegraphy.
The next one-time pad system was electrical. In 1917,
Gilbert Vernam
Gilbert Sandford Vernam (April 3, 1890 – February 7, 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 on ...
(of
AT&T Corporation
AT&T Corporation, originally the American Telephone and Telegraph Company, is the subsidiary of AT&T Inc. that provides voice, video, data, and Internet telecommunications and professional services to businesses, consumers, and government agen ...
) invented and later patented in 1919 () a cipher based on
teleprinter
A teleprinter (teletypewriter, teletype or TTY) is an electromechanical device that can be used to send and receive typed messages through various communications channels, in both point-to-point and point-to-multipoint configurations. Init ...
technology. Each character in a message was electrically combined with a character on a
punched paper tape
Five- and eight-hole punched paper tape
Paper tape reader on the Harwell computer with a small piece of five-hole tape connected in a circle – creating a physical program loop
Punched tape or perforated paper tape is a form of data storage ...
key.
Joseph Mauborgne
Joseph Oswald Mauborgne (February 26, 1881 – June 7, 1971) co-invented the one-time pad with Gilbert Vernam of Bell Labs. In 1914 he published the first recorded solution of the Playfair cipher. Mauborgne became a Major General in the U ...
(then a
captain
Captain is a title, an appellative for the commanding officer of a military unit; the supreme leader of a navy ship, merchant ship, aeroplane, spacecraft, or other vessel; or the commander of a port, fire or police department, election precinct, e ...
in the
U.S. Army
The United States Army (USA) is the land service branch of the United States Armed Forces. It is one of the eight U.S. uniformed services, and is designated as the Army of the United States in the U.S. Constitution.Article II, section 2, cl ...
and later chief of the
Signal Corps) recognized that the character sequence on the key tape could be completely random and that, if so, cryptanalysis would be more difficult. Together they invented the first one-time tape system.
The next development was the paper pad system. Diplomats had long used codes and ciphers for confidentiality and to minimize
telegraph
Telegraphy is the long-distance transmission of messages where the sender uses symbolic codes, known to the recipient, rather than a physical exchange of an object bearing the message. Thus flag semaphore is a method of telegraphy, whereas p ...
costs. For the codes, words and phrases were converted to groups of numbers (typically 4 or 5 digits) using a dictionary-like
codebook
A codebook is a type of document used for gathering and storing cryptography codes. Originally codebooks were often literally , but today codebook is a byword for the complete record of a series of codes, regardless of physical format.
Crypto ...
. For added security, secret numbers could be combined with (usually modular addition) each code group before transmission, with the secret numbers being changed periodically (this was called
superencryption
Multiple encryption is the process of encryption, encrypting an already encrypted message one or more times, either using the same or a different algorithm. It is also known as cascade encryption, cascade ciphering, multiple encryption, and superen ...
). In the early 1920s, three German cryptographers (Werner Kunze, Rudolf Schauffler, and Erich Langlotz), who were involved in breaking such systems, realized that they could never be broken if a separate randomly chosen additive number was used for every code group. They had duplicate paper pads printed with lines of random number groups. Each page had a serial number and eight lines. Each line had six 5-digit numbers. A page would be used as a work sheet to encode a message and then destroyed. The
serial number
A serial number is a unique identifier assigned incrementally or sequentially to an item, to ''uniquely'' identify it.
Serial numbers need not be strictly numerical. They may contain letters and other typographical symbols, or may consist enti ...
of the page would be sent with the encoded message. The recipient would reverse the procedure and then destroy his copy of the page. The German foreign office put this system into operation by 1923.
A separate notion was the use of a one-time pad of letters to encode plaintext directly as in the example below.
Leo Marks
Leopold Samuel Marks, (24 September 1920 – 15 January 2001) was an English writer, screenwriter, and cryptographer. During the Second World War he headed the codes office supporting resistance agents in occupied Europe for the secret Special ...
describes inventing such a system for the British
Special Operations Executive
The Special Operations Executive (SOE) was a secret British World War II organisation. It was officially formed on 22 July 1940 under Minister of Economic Warfare Hugh Dalton, from the amalgamation of three existing secret organisations. Its pu ...
during
World War II
World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposin ...
, though he suspected at the time that it was already known in the highly compartmentalized world of cryptography, as for instance at
Bletchley Park
Bletchley Park is an English country house and estate in Bletchley, Milton Keynes ( Buckinghamshire) that became the principal centre of Allied code-breaking during the Second World War. The mansion was constructed during the years following ...
.
The final discovery was made by information theorist
Claude Shannon
Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American people, American mathematician, electrical engineering, electrical engineer, and cryptography, cryptographer known as a "father of information theory".
As a 21-year-o ...
in the 1940s who recognized and proved the theoretical significance of the one-time pad system. Shannon delivered his results in a classified report in 1945 and published them openly in 1949.
At the same time, Soviet information theorist
Vladimir Kotelnikov had independently proved the absolute security of the one-time pad; his results were delivered in 1941 in a report that apparently remains classified.
[ PACS numbers: 01.10.Fv, 03.67.Dd, 89.70.+c and openly in Russia]
Квантовая криптография и теоремы В.А. Котельникова об одноразовых ключах и об отсчетах. УФН
/ref>
Example
Suppose Alice and Bob, Alice wishes to send the message hello
to Bob
Bob, BOB, or B.O.B. may refer to:
Places
* Mount Bob, New York, United States
*Bob Island, Palmer Archipelago, Antarctica
People, fictional characters, and named animals
*Bob (given name), a list of people and fictional characters
*Bob (surname ...
. Assume two pads of paper containing identical random sequences of letters were somehow previously produced and securely issued to both. Alice chooses the appropriate unused page from the pad. The way to do this is normally arranged for in advance, as for instance "use the 12th sheet on 1 May", or "use the next available sheet for the next message".
The material on the selected sheet is the ''key'' for this message. Each letter from the pad will be combined in a predetermined way with one letter of the message. (It is common, but not required, to assign each letter a numerical value, e.g., a
is 0, b
is 1, and so on.)
In this example, the technique is to combine the key and the message using modular addition, not unlike the Vigenère cipher
The Vigenère cipher () is a method of encryption, encrypting alphabetic text by using a series of interwoven Caesar ciphers, based on the letters of a keyword. It employs a form of polyalphabetic cipher, polyalphabetic substitution.
First desc ...
. The numerical values of corresponding message and key letters are added together, modulo 26. So, if key material begins with XMCKL
and the message is hello
, then the coding would be done as follows:
h e l l o message
7 (h) 4 (e) 11 (l) 11 (l) 14 (o) message
+ 23 (X) 12 (M) 2 (C) 10 (K) 11 (L) key
= 30 16 13 21 25 message + key
= 4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) (message + key) mod 26
E Q N V Z → ciphertext
If a number is larger than 25, then the remainder after subtraction of 26 is taken in modular arithmetic fashion. This simply means that if the computations "go past" Z, the sequence starts again at A.
The ciphertext to be sent to Bob is thus EQNVZ
. Bob uses the matching key page and the same process, but in reverse, to obtain the plaintext
In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted.
Overview
With the advent of com ...
. Here the key is ''subtracted'' from the ciphertext, again using modular arithmetic:
E Q N V Z ciphertext
4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) ciphertext
− 23 (X) 12 (M) 2 (C) 10 (K) 11 (L) key
= −19 4 11 11 14 ciphertext – key
= 7 (h) 4 (e) 11 (l) 11 (l) 14 (o) ciphertext – key (mod 26)
h e l l o → message
Similar to the above, if a number is negative, then 26 is added to make the number zero or higher.
Thus Bob recovers Alice's plaintext, the message hello
. Both Alice and Bob destroy the key sheet immediately after use, thus preventing reuse and an attack against the cipher. The KGB
The KGB (russian: links=no, lit=Committee for State Security, Комитет государственной безопасности (КГБ), a=ru-KGB.ogg, p=kəmʲɪˈtʲet ɡəsʊˈdarstvʲɪn(ː)əj bʲɪzɐˈpasnəsʲtʲɪ, Komitet gosud ...
often issued its agents one-time pads printed on tiny sheets of flash paper, paper chemically converted to nitrocellulose
Nitrocellulose (also known as cellulose nitrate, flash paper, flash cotton, guncotton, pyroxylin and flash string, depending on form) is a highly flammable compound formed by nitrating cellulose through exposure to a mixture of nitric acid and ...
, which burns almost instantly and leaves no ash.
The classical one-time pad of espionage used actual pads of minuscule, easily concealed paper, a sharp pencil, and some mental arithmetic
Mental calculation consists of arithmetical calculations using only the human brain, with no help from any supplies (such as pencil and paper) or devices such as a calculator. People may use mental calculation when computing tools are not availab ...
. The method can be implemented now as a software program, using data files as input (plaintext), output (ciphertext) and key material (the required random sequence). The exclusive or
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
(XOR) operation is often used to combine the plaintext and the key elements, and is especially attractive on computers since it is usually a native machine instruction and is therefore very fast. It is, however, difficult to ensure that the key material is actually random, is used only once, never becomes known to the opposition, and is completely destroyed after use. The auxiliary parts of a software one-time pad implementation present real challenges: secure handling/transmission of plaintext, truly random keys, and one-time-only use of the key.
Attempt at cryptanalysis
To continue the example from above, suppose Eve intercepts Alice's ciphertext: EQNVZ
. If Eve tried every possible key, she would find that the key XMCKL
would produce the plaintext hello
, but she would also find that the key TQURI
would produce the plaintext later
, an equally plausible message:
4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) ciphertext
− 19 (T) 16 (Q) 20 (U) 17 (R) 8 (I) possible key
= −15 0 −7 4 17 ciphertext-key
= 11 (l) 0 (a) 19 (t) 4 (e) 17 (r) ciphertext-key (mod 26)
In fact, it is possible to "decrypt" out of the ciphertext any message whatsoever with the same number of characters, simply by using a different key, and there is no information in the ciphertext that will allow Eve to choose among the various possible readings of the ciphertext.
If the key is not truly random, it is possible to use statistical analysis to determine which of the plausible keys is the "least" random and therefore more likely to be the correct one. If a key is reused, it will noticeably be the only key that produces sensible plaintexts from both ciphertexts (the chances of some random ''incorrect'' key also producing two sensible plaintexts are very slim).
Perfect secrecy
One-time pads are " information-theoretically secure" in that the encrypted message (i.e., the ciphertext
In cryptography, ciphertext or cyphertext 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 ...
) provides no information about the original message to a cryptanalyst
Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic sec ...
(except the maximum possible length[The actual length of a plaintext message can hidden by the addition of extraneous parts, called ]padding
Padding is thin cushioned material sometimes added to clothes. Padding may also be referred to as batting when used as a layer in lining quilts or as a packaging or stuffing material. When padding is used in clothes, it is often done in an attempt ...
. For instance, a 21-character ciphertext could conceal a 5-character message with some padding convention (e.g. "-PADDING- HELLO -XYZ-") as much as an actual 21-character message: an observer can thus only deduce the maximum possible length of the significant text, not its exact length. of the message). This is a very strong notion of security first developed during WWII by Claude Shannon
Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American people, American mathematician, electrical engineering, electrical engineer, and cryptography, cryptographer known as a "father of information theory".
As a 21-year-o ...
and proved, mathematically, to be true for the one-time pad by Shannon at about the same time. His result was published in the ''Bell System Technical Journal'' in 1949. Properly used, one-time pads are secure in this sense even against adversaries with infinite computational power.
Shannon proved, using information theoretic considerations, that the one-time pad has a property he termed ''perfect secrecy''; that is, the ciphertext ''C'' gives absolutely no additional information
Information is an abstract concept that refers to that which has the power to inform. At the most fundamental level information pertains to the interpretation of that which may be sensed. Any natural process that is not completely random ...
about the plaintext
In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted.
Overview
With the advent of com ...
.[That is to say, the "information gain" or ]Kullback–Leibler divergence
In mathematical statistics, the Kullback–Leibler divergence (also called relative entropy and I-divergence), denoted D_\text(P \parallel Q), is a type of statistical distance: a measure of how one probability distribution ''P'' is different fro ...
of the plaintext message from the ciphertext message is zero. This is because (intuitively), given a truly uniformly random key that is used only once, a ciphertext can be translated into ''any'' plaintext of the same length, and all are equally likely. Thus, the ''a priori
("from the earlier") and ("from the later") are Latin phrases used in philosophy to distinguish types of knowledge, justification, or argument by their reliance on empirical evidence or experience. knowledge is independent from current ...
'' probability of a plaintext message ''M'' is the same as the '' a posteriori'' probability of a plaintext message ''M'' given the corresponding ciphertext.
Mathematically, this is expressed as , where is the information entropy
In information theory, the entropy of a random variable is the average level of "information", "surprise", or "uncertainty" inherent to the variable's possible outcomes. Given a discrete random variable X, which takes values in the alphabet \ ...
of the plaintext and is the conditional entropy
In information theory, the conditional entropy quantifies the amount of information needed to describe the outcome of a random variable Y given that the value of another random variable X is known. Here, information is measured in shannons, na ...
of the plaintext given the ciphertext ''C''. (Here, Η is the capital Greek letter eta
Eta (uppercase , lowercase ; grc, ἦτα ''ē̂ta'' or ell, ήτα ''ita'' ) is the seventh letter of the Greek alphabet, representing the close front unrounded vowel . Originally denoting the voiceless glottal fricative in most dialects, ...
.) This implies that for every message ''M'' and corresponding ciphertext ''C'', there must be at least one key ''K'' that binds them as a one-time pad. Mathematically speaking, this means must hold, where denote the quantities of possible keys, ciphers and messages, respectively. In other words, to be able to go from any plaintext in the message space ''M'' to any cipher in the cipher space ''C'' (via encryption) and from any cipher in cipher-space ''C'' to a plain text in message space ''M'' (decryption), it would require at least keys (with all keys used with equal probability of to ensure perfect secrecy).
Another way of stating perfect secrecy is that for all messages in message space ''M'', and for all ciphers ''c'' in cipher space ''C'', we have