In classical
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 running key cipher is a type of
polyalphabetic substitution
A polyalphabetic cipher substitution, using multiple substitution alphabets. The Vigenère cipher is probably the best-known example of a polyalphabetic cipher, though it is a simplified special case. The Enigma machine is more complex but is sti ...
cipher in which a text, typically from a book, is used to provide a very long
keystream In cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message (the ciphertext).
The "characters" in the keystream can be bits, bytes, numbers or actual cha ...
. Usually, the book to be used would be agreed ahead of time, while the passage to be used would be chosen
random
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual ra ...
ly for each message and secretly indicated somewhere in the message.
Example
The text used is ''
The C Programming Language
''The C Programming Language'' (sometimes termed ''K&R'', after its authors' initials) is a computer programming book written by Brian Kernighan and Dennis Ritchie, the latter of whom originally designed and implemented the language, as well as ...
'' (1978 edition), and the ''
tabula recta
In cryptography, the ''tabula recta'' (from Latin ''tabula rēcta'') is a square table of alphabets, each row of which is made by shifting the previous one to the left. The term was invented by the German author and monk Johannes TrithemiusSal ...
'' is the tableau. The plaintext is "Flee at once".
Page 63, line 1 is selected as the running key:
errors can occur in several places. A label has...
The running key is then written under the plaintext:
The message is then sent as "JCVSR LQNPS". However, unlike a
Vigenère cipher
The Vigenère cipher () is a method of encrypting alphabetic text by using a series of interwoven Caesar ciphers, based on the letters of a keyword. It employs a form of polyalphabetic substitution.
First described by Giovan Battista Bella ...
, if the message is extended, the key is not repeated; the key text itself is used as the key. If the message is extended, such as, "Flee at once. We are discovered", then the running key continues as before:
To determine where to find the running key, a fake block of five ciphertext characters is subsequently added, with three denoting the page number, and two the line number, using A=0, B=1 etc. to encode digits. Such a block is called an indicator block. The indicator block will be inserted as the second last of each message. (Many other schemes are possible for hiding indicator blocks.) Thus page 63, line 1 encodes as "AGDAB" (06301).
This yields a final message of "JCVSR LQNPS YGUIM QAWXS AGDAB MECTO".
Variants
Modern variants of the running key cipher often replace the traditional ''tabula recta'' with bitwise
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, , ...
, operate on whole
byte
The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable uni ...
s rather than alphabetic letters, and derive their running keys from large files. Apart from possibly greater entropy density of the files, and the ease of automation, there is little practical difference between such variants and traditional methods.
Permutation generated running keys
A more compact running key can be used if one combinatorially generates text using several
start pointers (or combination rules). For example, rather than start at one place
(a single pointer), one could use several start pointers and xor together the streams
to form a new running key, similarly skip rules can be used. What is exchanged then
is a series of pointers to the running key book and/or a series of rules for generating
the new permuted running key from the initial key text. (These may be exchanged
via
public key
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic al ...
encryption or in person. They may also be changed frequently
without changing the running key book.)
Ciphertext appearing to be plaintext
Traditional ciphertext appears to be quite different from plaintext.
To address this problem, one variant outputs "plaintext" words instead
of "plaintext" letters as the ciphertext output. This is done by creating
an "alphabet" of words (in practice multiple words can correspond to each ciphertext
output character). The result is a ciphertext output which looks like a long
sequence of plaintext words (the process can be nested). Theoretically, this is
no different from using standard ciphertext characters as output. However,
plaintext-looking ciphertext may result in a "human in the loop" to try to mistakenly
interpret it as decoded plaintext.
An example would be BDA (Berkhoff deflater algorithm), each ciphertext output
character has at least one noun, verb, adjective and adverb associated with it.
(E.g. (at least) one of each for every
ASCII
ASCII ( ), abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication. ASCII codes represent text in computers, telecommunications equipment, and other devices. Because ...
character). Grammatically plausible
sentences are generated as ciphertext output. Decryption requires mapping the words back to
ASCII, and then decrypting the characters to the real plaintext using the running key.
Nested-BDA will run the output through the reencryption process several times, producing
several layers of "plaintext-looking" ciphertext - each one potentially requiring
"human-in-the-loop" to try to interpret its non-existent
semantic meaning.
Gromark cipher
The "Gromark cipher" ("
Gronsfeld cipher with mixed alphabet and running key") uses a running numerical key formed by adding successive pairs of digits.
[
American Cryptogram Association]
"The ACA and You"
2016.
The
VIC cipher
Vic (; es, Vic or Pancracio Celdrán (2004). Diccionario de topónimos españoles y sus gentilicios (5ª edición). Madrid: Espasa Calpe. p. 843. ISBN 978-84-670-3054-9. «Vic o Vich (viquense, vigitano, vigatán, ausense, ausetano, ausonense): ...
uses a similar
lagged Fibonacci generator A Lagged Fibonacci generator (LFG or sometimes LFib) is an example of a pseudorandom number generator. This class of random number generator is aimed at being an improvement on the 'standard' linear congruential generator. These are based on a gene ...
.
Security
If the running key is truly random, never reused, and kept secret, the result is a
one-time pad
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 not smaller than the message being sent. In this technique, a plaintext is paired with a ran ...
, a method that provides
perfect secrecy (reveals no information about the plaintext). However, if (as usual) the running key is a block of text in a
natural language, security actually becomes fairly poor, since that text will have non-random characteristics which can be used to aid cryptanalysis. As a result, the
entropy
Entropy is a scientific concept, as well as a measurable physical property, that is most commonly associated with a state of disorder, randomness, or uncertainty. The term and the concept are used in diverse fields, from classical thermodynam ...
per character of both plaintext and running key is low, and the combining operation is easily inverted.
To attack the cipher, 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 ...
runs guessed probable plaintexts along the ciphertext, subtracting them out from each possible position. When the result is a chunk of something intelligible, there is a high probability that the guessed plain text is correct for that position (as either actual plaintext, or part of the running key). The 'chunk of something intelligible' can then often be extended at either end, thus providing even more probable plaintext - which can in turn be extended, and so on. Eventually it is likely that the source of the running key will be identified, and the jig is up.
There are several ways to improve the security. The first and most obvious is to use a secret mixed alphabet tableau instead of a ''tabula recta''. This does indeed greatly complicate matters but it is not a complete solution. Pairs of plaintext and running key characters are far more likely to be high frequency pairs such as 'EE' rather than, say, 'QQ'. The skew this causes to the output
frequency distribution
In statistics, the frequency (or absolute frequency) of an event i is the number n_i of times the observation has occurred/recorded in an experiment or study. These frequencies are often depicted graphically or in tabular form.
Types
The cumula ...
is smeared by the fact that it is quite possible that 'EE' and 'QQ' map to the same ciphertext character, but nevertheless the distribution is not flat. This may enable the cryptanalyst to deduce part of the tableau, then proceed as before (but with gaps where there are sections missing from the reconstructed tableau).
Another possibility is to use a key text that has more entropy per character than typical English. For this purpose, 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 ...
advised agents to use documents like
almanac
An almanac (also spelled ''almanack'' and ''almanach'') is an annual publication listing a set of current information about one or multiple subjects. It includes information like weather forecasts, farmers' planting dates, tide tables, and othe ...
s and trade reports, which often contain long lists of random-looking numbers.
Another problem is that the keyspace is surprisingly small. Suppose that there are 100 million key texts that might plausibly be used, and that on average each has 11 thousand possible starting positions. To an opponent with a massive collection of possible key texts, this leaves possible a brute force search of the order of
, which by computer cryptography standards is a relatively easy target. (See permutation generated running keys above for an approach to
this problem).
Confusion
Because both ciphers classically employed
novels as part of their key material, many sources confuse the
book cipher
A book cipher, or Ottendorf cipher, is a cipher in which the key is some aspect of a book or other piece of text. Books, being common and widely available in modern times, are more convenient for this use than objects made specifically for crypto ...
and the running key cipher. They are really only very distantly related. The running key cipher is a polyalphabetic substitution, the book cipher is a homophonic substitution. Perhaps the distinction is most clearly made by the fact that a running cipher would work best of all with a book of random numbers, whereas such a book (containing no text) would be useless for a book cipher.
See also
*
Polyalphabetic substitution
A polyalphabetic cipher substitution, using multiple substitution alphabets. The Vigenère cipher is probably the best-known example of a polyalphabetic cipher, though it is a simplified special case. The Enigma machine is more complex but is sti ...
*
Substitution cipher
In cryptography, a substitution cipher is a method of encrypting in which units of plaintext are replaced with the ciphertext, in a defined manner, with the help of a key; the "units" may be single letters (the most common), pairs of letters, tri ...
*
Book cipher
A book cipher, or Ottendorf cipher, is a cipher in which the key is some aspect of a book or other piece of text. Books, being common and widely available in modern times, are more convenient for this use than objects made specifically for crypto ...
*
Topics in cryptography
The following outline is provided as an overview of and topical guide to cryptography:
Cryptography (or cryptology) – practice and study of hiding information. Modern cryptography intersects the disciplines of mathematics, computer scien ...
References
{{Reflist
Stream ciphers
Classical ciphers