Running key cipher

In classical cryptography, the running key cipher is a type of polyalphabetic substitution cipher in which a text, typically from a book, is used to provide a very long keystream.

The earliest description of such a cipher was given in 1892 by French mathematician Arthur Joseph Hermann (better known for founding Éditions Hermann). Usually, the book to be used would be agreed ahead of time, while the passage to be used would be chosen randomly for each message and secretly indicated somewhere in the message.

The term running key was introduced by William F. Friedman; it is distinct from progressive key (David Kahn's term for systems such as that of Trithemius, which cycle through every alphabet in a fixed order before repeating) or progressing key (Gaines' term for the same concept).

An early cryptanalysis of a running-text key was carried out by Étienne Bazeries in 1899, when he read the enciphered dispatches of the conspirators around the Duke of Orléans. The dispatches were written in four-figure groups, each pair of digits standing for a letter through a Beaufort table, and the key was a continuous text: successive lines of Alfred de Musset's poem La Nuit de décembre, or a written-out date, selected according to the calendar date. Because the key did not repeat over the short telegrams, their apparent periodicity was a chance effect, and Bazeries recovered the messages by guessing probable words.

Example

The key text used is a portion of The C Programming Language (1978 edition), and the tabula recta is the tableau. The plaintext here 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:

Plaintext	f	l	e	e	a	t	o	n	c	e
Running key	E	R	R	O	R	S	C	A	N	O
Ciphertext	J	C	V	S	R	L	Q	N	P	S

The message is then sent as "JCVSR LQNPS". However, unlike a Vigenère cipher, if the message is extended, the key is not repeated; the key text itself (the text from The C Programming Language) is used as the key and can be extended for any arbitrary length. If the message is extended, such as, "Flee at once. We are discovered", then the running key continues as before:

Plaintext	f	l	e	e	a	t	o	n	c	e	w	e	a	r	e	d	i	s	c	o	v	e	r	e	d
Running key	E	R	R	O	R	S	C	A	N	O	C	C	U	R	I	N	S	E	V	E	R	A	L	P	L
Ciphertext	J	C	V	S	R	L	Q	N	P	S	Y	G	U	I	M	Q	A	W	X	S	M	E	C	T	O

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, operate on whole bytes 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.

The American Cryptogram Association uses "Running Key" for a constrained puzzle form, in which a 40–50-letter plaintext is split in half and its first half is used as the key for its second half. Methods for solving this form are set out in the association's lessons.

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. The VIC cipher uses a similar lagged Fibonacci generator.

Security and cryptanalysis

A single message can be attacked with a probable word: a likely plaintext fragment is placed against each position of the ciphertext and the resulting key fragment tested for intelligibility, building up message and key alternately.

Because both the message and the key are natural-language text, a running-key ciphertext can also be attacked statistically. That it can be solved at all shows English to be at least 50 percent redundant, since two texts are recovered from a ciphertext of half their combined length.

Deavours estimated the unicity distance of a running-key Vigenère cipher in English to be eight letters, so that in principle a ciphertext longer than this has a unique solution.

Bauer and Tate scored candidate (plaintext, key) pairs at each position using unsmoothed letter n-grams up to order 6; on 1,000-letter ciphertexts this recovered between 28.9% and 33.5% of characters, too few to read.

Bauer and Gottloeb used a dictionary attack that lists every combination of valid words consistent with a ciphertext; ignoring grammar, the average number of such combinations rose from about 34 for a three-letter block to about 9,000 for a six-letter block, but grammatical constraints eliminate almost all of them.

Griffing applied the Viterbi algorithm with a 6-gram letter model, recovering a median of about 87% of characters on 1,000-letter ciphertexts (and nearly all when the model was trained on the source texts) and found that a solution is generally possible when the combined redundancy of message and key exceeds about 50%.

Reddy and Knight used blocked Gibbs sampling over a word-based language model, recovering about 88–93% of characters on 1,000-character ciphertexts, 42–58% on 100-character ciphertexts, and 17–26% on 10-character ciphertexts, and running much faster than Viterbi decoding. Short messages remain ambiguous, because several natural-language (plaintext, key) pairs can produce the same ciphertext. Recovering a running key enciphered with a secret keyword-mixed table instead of the tabula recta is an open problem.

The cipher can be strengthened by enciphering with several independent texts in succession, an idea due to Shannon. Diffie and Hellman noted that, because English is about 75 percent redundant, four successive running keys would be secure against all attacks; Ryabko later proved that adding four or more independent English texts as the key gives a positive equivocation, so the cipher cannot be read without the key. As the number of running keys grows, the modulo-26 sum tends to a random sequence, giving a one-time tape.

When the same running key is used for several messages, the set can be solved "in depth": Friedman showed in 1918 that such messages can be recovered column by column, more quickly than they were enciphered.

In February 2026, a 1,128-letter running-key challenge posted by Satoshi Tomokiyo was solved by Matthew Brown using a dictionary attack on long words followed by manual extension.

Confusion

Because both ciphers classically employed novels as part of their key material, many sources confuse the book cipher 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
• Substitution cipher
• Book cipher
• Topics in cryptography

Further reading

• Gaines, Helen Fouché (1939). Elementary Cryptanalysis: A Study of Ciphers and Their Solution. American Photographic Publishing. p. 143.
• Friedman, William F. (1918). Methods for the Solution of Running-Key Ciphers (PDF). Riverbank Publication No. 16. Geneva, Illinois: Riverbank Laboratories.
• Tomokiyo, Satoshi (2026). "Solving Running Key Ciphers (Manually/Digitally)". Cryptiana.