Hubbry Logo
Running key cipherRunning key cipherMain
Open search
Running key cipher
Community hub
Running key cipher
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Running key cipher
Running key cipher
Running key cipher
View on Wikipedia
from Wikipedia

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.

Example

[edit]

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 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

[edit]

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.

Permutation generated running keys

[edit]

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 encryption or in person. They may also be changed frequently without changing the running key book.)

Ciphertext appearing to be plaintext

[edit]

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)[citation needed], 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 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

[edit]

The "Gromark cipher" ("Gronsfeld cipher with mixed alphabet and running key") uses a running numerical key formed by adding successive pairs of digits.[1] The VIC cipher uses a similar lagged Fibonacci generator.

Security and cryptanalysis

[edit]

If the running key is truly random, never reused, and kept secret, the result is a one-time pad, 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: for example, William F. Friedman suggested a ciphertext-only attack during WWI against most frequent letters encoded by other most frequent letters.[2] As a result, the entropy per character of both plaintext and running key is low, and the combining operation is easily inverted.

To attack the cipher, a cryptanalyst may run 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 (for more detailed explanation refer to Autokey cipher). Eventually it is likely that the source of the running key will be identified, and the entire message can be deciphered.

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. As exploited in Friedman's method, 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 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 advised agents to use documents like almanacs 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

[edit]

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

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Running key cipher

View on Grokipedia
from Grokipedia
A running key cipher is a polyalphabetic in classical that generates a long, non-repeating keystream from a continuous text—such as an excerpt from a book—to encipher , often by modular of corresponding letters. This approach uses one meaningful text to encrypt another, ensuring the key length matches or exceeds the message to avoid periodicity. Unlike the , which repeats a short keyword, the running key's extended, aperiodic nature makes it more resistant to attacks. The cipher operates using a tabula recta or equivalent modular arithmetic (modulo 26 for the English alphabet), where each plaintext letter is shifted by the value of the aligned key letter to produce ciphertext. Decryption reverses this by subtracting the key letters from the ciphertext. First described in 1892 by French mathematician Arthur-Joseph Hermann in his work Nouveau système de correspondance secrète, the running key cipher emerged as an evolution of earlier polyalphabetic methods, leveraging shared reference texts between sender and receiver for secure communication. Although long considered secure due to its complexity, the running key cipher's reliance on for the keystream introduces statistical redundancies that enable , such as probable word methods or frequency attacks on key-plaintext pairs. In information-theoretic terms, it approximates perfect secrecy only if the key is truly random and used once, akin to the ; otherwise, meaningful keys reduce security. Historically employed in and military contexts, it highlights the balance between simplicity and vulnerability in pre-modern systems.

Principles and Operation

Definition and Core Concepts

A running key cipher is a polyalphabetic that utilizes a non-repeating keystream of arbitrary length, typically generated from an external text source such as a or shared between correspondents. This approach contrasts with fixed-key systems by drawing successive key letters directly from the chosen text, ensuring the keystream matches the length without cycling or repetition. At its core, the running key functions as a continuous keystream that progresses sequentially through the source text, pairing each character with a distinct key character to produce the . This one-to-one correspondence eliminates the periodic patterns inherent in repeating-key polyalphabetics, such as the , thereby complicating frequency-based attacks. The substitution mechanism employs the , a square table of alphabets where each row represents a shifted version of the base alphabet, facilitating letter-by-letter through addition in . Letters are numerically encoded with A=0, B=1, up to Z=25, and the shift for each position is computed 26, yielding a new letter: for letter pp and key letter kk, the is c=(p+k)mod  26c = (p + k) \mod 26. Running key ciphers played a pivotal role in historical as a transitional method between limited-key polyalphabetics and modern stream ciphers, introducing the use of extended, non-repeating keystreams for enhanced diffusion. Predating digital , they influenced early 20th-century mechanical systems, including the U.S. Army's M-94 cipher wheel, which adapted polyalphabetic principles for tactical use.

Encryption and Decryption Process

The encryption process in a running key cipher involves aligning the message letter by letter with a corresponding sequence from the running key, which is typically derived from a lengthy, non-repeating text source such as a excerpt. Each plaintext letter PiP_i is converted to its numeric equivalent (A=0, B=1, ..., Z=25), and similarly for the key letter KiK_i. The ciphertext letter CiC_i is then computed using the Ci=(Pi+Ki)mod  26C_i = (P_i + K_i) \mod 26, after which the result is mapped back to the corresponding letter in the . This can be performed manually via a or computationally in modern implementations. Decryption reverses this operation by aligning the ciphertext with the same running key sequence. For each position, the ciphertext numeric value CiC_i is subtracted by the key value KiK_i, yielding Pi=(Ci−Ki)mod  26P_i = (C_i - K_i) \mod 26, with negative results adjusted by adding 26 to ensure a non-negative value within the 0-25 range before mapping back to plaintext letters. This modular subtraction maintains the cipher's reversibility, assuming perfect key alignment. A fundamental requirement is that the running key must be at least as long as the to prevent repetition and enhance security, effectively making the key stream unique for each message. Sender and receiver must synchronize the key source in advance, often by agreeing on a specific book, page, and starting line, which can be indicated subtly in the message to avoid direct transmission of the key itself. In contemporary computational settings, the process is implemented programmatically by generating the key stream from digitized texts, automating the operations for efficiency while preserving the manual synchronization protocol.

Historical Development

Origins in Polyalphabetic Ciphers

The running key cipher emerged from the evolution of polyalphabetic substitution ciphers, which originated in the with innovations like those described by in his 1586 treatise Traicté des chiffres et chiffres secrets. Vigenère's work included an autokey variant, where an initial keyword is extended by the itself to create a non-repeating keystream, representing an early attempt to avoid key periodicity in polyalphabetic systems. However, the running key cipher, using a long external text such as a excerpt as the keystream, was first formally described in 1892 by French mathematician Arthur-Joseph Hermann in his work Nouveau système de correspondance secrète. This approach built on earlier polyalphabetic designs but provided a truly aperiodic key independent of the message. In the 19th century, advancements in highlighted the vulnerabilities of short-key polyalphabetics. developed methods in the 1840s to break Vigenère ciphers by identifying repeated sequences and aligning them to reveal the key length, showing how periodicity facilitated attacks. Friedrich Kasiski's 1863 examination technique systematically detected repeated trigrams to deduce key length, underscoring the need for keys as long as the to resist such methods. These developments influenced the pursuit of non-repeating keys, paving the way for running key systems. The early saw the adoption of running key ciphers in military contexts, with the U.S. Army Signal Corps incorporating them into field manuals around for secure telegraph and radio communications. These manuals described running keys, often derived from book passages or continuous text, as non-repeating alternatives to periodic ciphers, suitable for operations. Concurrently, engineer proposed a related system in for encryption, using a prepared key tape combined character-by-character with plaintext via XOR-like addition, functioning as a running key but initially with reusable loops, later refined into the by Vernam and Joseph Mauborgne. Pre-World War II European developments included German Abwehr experiments with mechanical running key devices, such as the Kryha machine invented by Fritz Kryha in the 1920s and adopted for intelligence communications. This clockwork encipherer generated pseudo-random key streams via movable alphabet tabs, offering a portable, non-periodic alternative to rotor machines like Enigma for low-volume traffic, though it was eventually compromised by Allied cryptanalysts.

Evolution and Notable Uses

Following World War I, running key ciphers evolved through integration with mechanical aids, though many remained manual for practicality in military use. During World War II, running key ciphers found niche applications in espionage, particularly by British Special Operations Executive (SOE) agents, who employed poem codes—a form of book cipher using memorized or carried verses as keys for transposition to encode short radio messages to London. German intelligence adopted book-based running keys more selectively, such as the Spanish book Sonar la Vida for the Hamburg-Chile circuit or O Servo de Deua for Hamburg-Lisbon reports on Allied shipping, but logistical challenges like irregular traffic and synchronized editions limited use; mechanical variants like the Kryha device were employed commercially and diplomatically but saw restricted military deployment. A notable event occurred in 1943 when Allied cryptanalysts, including the U.S. Coast Guard and British ISOS section, broke several Axis running key systems through known-plaintext attacks, identifying key books from message preambles and patterns to decrypt 150-200 daily intercepts, revealing on ship movements and agent activities. Post-war, running key ciphers declined with the rise of machines and electronic systems, yet their simplicity influenced manual field operations in non-aligned countries during the , where resource limitations favored book-based methods.

Illustrative Examples

Basic Numerical Example

To illustrate the core mechanics of the running key cipher using numerical values, consider a simplified "FLEEA" (corresponding to "Flee a" with space ignored), mapped to integers where A=0, B=1, ..., Z=25, yielding plaintext values P=(5,11,4,4,0)P = (5, 11, 4, 4, 0). A non-repeating running key of equal length, derived from the start of the phrase "errors can occur" (e=4, r=17, r=17, o=14, r=17), is used instead of a short repeating key as in the . Encryption computes each ciphertext value as Ci=(Pi+Ki)mod  26C_i = (P_i + K_i) \mod 26, where KiK_i is the ii-th key value. The following table shows the step-by-step calculation:
PositionPlaintext LetterPiP_iKey LetterKiK_iCi=(Pi+Ki)mod  26C_i = (P_i + K_i) \mod 26Ciphertext Letter
1F5e49J
2L11r1728 \mod 26 = 2C
3E4r1721V
4E4o1418S
5A0r1717R
This produces the ciphertext "JCVSR". Decryption reverses the process using the same running key: Pi=(Ci−Ki)mod  26P_i = (C_i - K_i) \mod 26. For the first position, (9−4)mod  26=5(9 - 4) \mod 26 = 5 (F); second, (2−17)mod  26=−15mod  26=11(2 - 17) \mod 26 = -15 \mod 26 = 11 (L); and similarly for the rest, recovering the original values (5,11,4,4,0)(5, 11, 4, 4, 0). This numerical approach highlights the advantage of a non-repeating running key, which avoids the periodic patterns exploitable in shorter, repeating keys, thereby enhancing resistance to .

Text-Based Book Key Example

In a text-based running key cipher, the keystream is derived from a passage in a shared book, ensuring the key is as long as the without repetition. Consider a simple message with the "MEETATDAWN," representing instructions to rendezvous at dawn. The running key is taken from the opening of the : "When in the Course of human events," ignoring spaces and punctuation for consecutive letters starting with W-H-E-N-I-N-T-H-E-C (corresponding to numerical values 22, 7, 4, 13, 8, 13, 19, 7, 4, 2). Encryption proceeds by aligning the letters with the key letters and applying modular addition modulo 26, where A=0, B=1, ..., Z=25, similar to a but with a non-repeating key. For the first letter, M (12) + W (22) = 34 ≡ 8 (mod 26), which is I. Continuing: E (4) + H (7) = 11 ≡ L (mod 26); E (4) + E (4) = 8 ≡ I; T (19) + N (13) = 32 ≡ 6 (mod 26) = G; A (0) + I (8) = 8 ≡ I; T (19) + N (13) = 32 ≡ 6 = G; D (3) + T (19) = 22 ≡ W; A (0) + H (7) = 7 ≡ H; W (22) + E (4) = 26 ≡ 0 (mod 26) = A; N (13) + C (2) = 15 ≡ P. The resulting is "ILIGIGWHAP." Decryption reverses this process: the recipient, knowing the starting point in the identical book edition, subtracts the key values from the modulo 26. For instance, starting with I (8) - W (22) = 8 - 22 = -14 ≡ 12 (mod 26) = M, and proceeding similarly to recover the original . Both parties must use the exact same book edition and precise starting position—such as page, line, and word—to align the key correctly, as even minor discrepancies like variant printings or editions could render the message undecipherable. This method saw practical application in , particularly in German clandestine radio networks in after the 1942 Brazilian spy arrests. For example, the Hamburg-to-Chile circuit employed a running key derived from the Spanish novel Sonar la Vida, using aperiodic polyalphabetic substitution where preambles in the message indicated key alignment, such as repeating a reference letter three times. Agents reported on Allied ship movements and equipment using such systems, but challenges arose in identifying the exact key books, contributing to Allied successes in intercepting and disrupting these networks through .

Variants and Extensions

Permutation-Generated Running Keys

In permutation-generated running keys, the keystream for a running key cipher is dynamically produced by applying successive to an initial base sequence, such as the ordered (A to Z) or numerals (1 to 26), rather than relying on excerpts from a fixed text. This method leverages a shared permutation rule—often a fixed transformation like a cyclic shift or swap operation—applied iteratively to reorder the sequence and yield a prolonged, non-repeating output stream suitable for . Such generation mimics the polyalphabetic substitution of traditional running key systems but eliminates the dependency on , aligning with early mechanized approaches to keystream production. A representative example begins with the sorted sequence 1, 2, 3, ..., 26. A fixed , such as swapping every third element (e.g., interchange positions 3 and 4, 6 and 7, etc., while shifting others), is applied to produce the first block of the keystream. The resulting permuted sequence then serves as input for the next of the same rule, generating subsequent blocks indefinitely. This process creates a deterministic yet unpredictable when the initial permutation is complex, analogous to rotor stepping in historical devices where multiple permutation layers ensure variability. The primary advantages of permutation-generated running keys include obviating the need for synchronized book copies between parties, thereby simplifying key distribution, and enhancing pseudo-randomness through the combinatorial depth of repeated permutations, which resists pattern detection better than short repeating keys. These techniques saw historical use in 1930s experimental cryptography research, particularly in the development of U.S. rotor machines like SIGABA (also known as ECM Mark II), where arrays of permuting rotors produced irregular, long-keystream sequences for secure communications prior to World War II. In modern contexts, permutation-generated running keys are computationally feasible via software simulations, enabling efficient recreation of historical systems or integration into hybrid ciphers on standard hardware, as demonstrated by cryptanalytic implementations that process full keyspaces in hours.

Gromark Cipher

The Gromark cipher, short for "Gronsfeld with mixed alphabet and running key," is a polyalphabetic designed for recreational challenges. Invented by W. J. Hall and first described in the March-April 1969 issue of The Cryptogram, the official publication of the American Cryptogram Association, it combines elements of the Gronsfeld cipher's numerical shifts with a keyword-derived mixed and a pseudo-random numerical running key generated from a short primer. The encryption process begins with key setup using a keyword, such as "ENIGMA," which determines both the mixed cipher alphabet and a transposition order. The keyword is written across the top of a 5x5 grid (or adjusted for length), with the remaining letters of the alphabet filled in row-wise below it, omitting one letter (often J) to fit 25 positions. The columns are then read out in the order of the keyword's alphabetical ranking (e.g., for "ENIGMA," the order is 2-6-4-3-5-1), producing a deranged alphabet like A J R X E B K S Y G F P V I D O U M H Q W N C L T Z. A 5-digit primer, such as 23452, initializes the running key stream. Subsequent key digits are generated by adding pairs of prior digits and taking the units place (e.g., 2+3=5, 3+4=7, 4+5=9, 5+2=7, then 5+7=2, and so on), creating a long numerical sequence independent of the plaintext. To encipher, each letter is substituted using the corresponding running key digit as a shift amount within the mixed : the position of the letter is advanced by the digit value ( 25), wrapping around as needed. For example, with "THEREAREUPTOTENSUBSTITUTESPERLETTER" and the setup above, the initial key stream yields groups like NFYCK BTIJC NWZYC ACJNA YNLQP WWSTW PJQFL, prefixed by the primer and suffixed by a (the sum of the last four primer digits 10, here 6). The output is presented in 5-letter groups to aid readability and solving, typically suitable for messages of 100-150 letters. This design enhances security over simple Gronsfeld by deranging the base and using a long, non-repeating numerical key, though it remains vulnerable to known- attacks or on sufficient text. A distinctive feature of Gromark is its self-extending key mechanism, which mimics a running key without requiring external text or true autokey feedback from the ; instead, the primer bootstraps an that can produce thousands of digits before repeating. While optional columnar transposition of the final (e.g., in a 5xN grid keyed by the primer) has been suggested in later variants to add , the core system relies on substitution alone for its . Hall's aimed to create a "K2M" (keyword, two mixed alphabets) puzzle that balances solvability with intricacy for amateur cryptanalysts, influencing subsequent cipher designs in recreational .

Ciphertext-Mimicking Variants

Ciphertext-mimicking variants of the running key cipher employ techniques to generate output that closely resembles ordinary text or expected content, enhancing concealment beyond mere . By carefully selecting or adjusting the running key—often derived from a long passage in a —the ciphertext can incorporate nulls or filler elements to obscure its structure and mimic patterns, such as those found in or . This approach leverages the running key's length and variability to blend the encrypted message into innocuous cover material, reducing the likelihood of detection as a . A representative technique involves choosing key segments from sources matching the intended cover genre, for instance, excerpts from a to produce that appears as literary text. The is combined with the running key via modular addition (e.g., mod 26 for letters), and nulls—superfluous symbols or words—are inserted to pad the output and disrupt any residual patterns, ensuring the result reads as coherent but meaningless filler . For example, a diplomatic might be enciphered such that the resembles a routine dispatch, with the true content hidden through selective positioning of meaningful letters amid nulls. This method was particularly suited to scenarios where messages needed to evade casual , as the output could pass for non-sensitive . In historical contexts, early 20th-century espionage and diplomatic operations frequently utilized hybrids that incorporated running key elements for added obfuscation. During , German diplomats, including Count von Bernstorff, employed null ciphers embedded in press cables to transmit intelligence, where significant letters were selected from ostensibly innocent text according to a prearranged rule, and these could be further protected by a running key derived from a shared book passage to prevent straightforward recovery. Such systems appeared in U.S. Army telegraphic encipherment experiments around 1917, where Vernam's on-line methods used continuous running keys to generate output resembling random but transmittable marks, often padded with nulls for fixed-length groups. Soviet networks in and 1940s extended this by combining book-based running keys (e.g., from novels like Schweik) with null-heavy formats, producing five-digit groups that mimicked routine numerical dispatches. The psychological camouflage provided by these variants relies on the human tendency to overlook text that aligns with expected non-cryptic forms, such as everyday or bureaucratic fillers, thereby delaying cryptanalytic . Unlike standard running key ciphers, which produce visibly scrambled output, these adaptations prioritize perceptual , making the material seem unworthy of deeper investigation until patterns or indicators reveal otherwise. This aspect proved effective in high-stakes environments like wartime , where speed of transmission outweighed .

Security Analysis

Theoretical Strengths

Running key ciphers, when employing a truly random keystream as long as the , achieve perfect , rendering the statistically independent of the and thus unbreakable by any amount of computational power or ciphertext-only analysis. This property aligns with Claude Shannon's foundational on secrecy systems, which demonstrates that perfect secrecy requires the key to be at least as large as the , a condition met by such a non-repeating random key equivalent to a . The non-repeating nature of the running key inherently resists classical , as there is no fixed period or repeating pattern to exploit for identifying letter substitutions, unlike periodic polyalphabetic ciphers such as the Vigenère. In the ideal case of a random key, the resulting exhibits uniform distribution across possible symbols, eliminating detectable biases from or key redundancies that would otherwise enable statistical attacks. Furthermore, the use of extended keystreams, such as those derived from large corpora like , enables by providing an effectively vast keyspace without the need for key repetition, supporting encryption of arbitrarily long messages. However, such linguistic keys introduce redundancies that prevent achieving perfect , though they still offer improved resistance to period-detection attacks compared to short-key systems.

Cryptanalytic Vulnerabilities

Running key ciphers are susceptible to known-plaintext attacks, where an attacker guesses probable words, such as common phrases like "THE" or "ENEMY," and subtracts them from the corresponding segments to reveal portions of the running key. These key fragments can then be extended iteratively by assuming adjacent meaningful text, allowing recovery of longer key sequences and potentially the entire message if the key source is linguistic. This method, adapted from Vigenère , exploits the predictability of in both plaintext and key. Book key exploitation targets the use of indexed excerpts from known texts, such as books, by testing probable sources and starting positions against multiple ciphertexts sharing the same key. In 1918, William Friedman developed the "" method, which involves generating 25 shifted alphabetic sequences from the and using trial-and-error to align them with suspected book passages, successfully breaking several historical examples. During , British cryptanalysts at applied similar index-based attacks on book-derived keys in diplomatic and espionage communications, often narrowing candidates through of suspected texts. Statistical methods leverage the non-random frequency distributions in natural language keys and plaintexts, contrasting with the flatter ciphertext spectrum. Attacks using n-gram probabilities score potential plaintext-key pairs, with early blockwise approaches recovering about 33% of letter pairs for short segments (n ≤ 6). More advanced techniques exploit in key streams derived from text, detecting periodicities from word or phrase repetitions that deviate from true . Computational breaks have advanced significantly in the , enabling efficient decryption of longer ciphertexts through algorithmic optimization. The , applied with 6-gram letter statistics, models the cipher as a hidden Markov chain to maximize the likelihood of plaintext and key sequences, achieving a median recovery accuracy of 87% on English texts from . Gibbs sampling further improves this by iteratively sampling word boundaries and candidates from language models like interpolated trigrams trained on corpora such as the , yielding up to 93% accuracy on 1000-character ciphertexts while being over 100 times faster than Viterbi. Recent machine learning approaches, including transformer-based models for language prediction, have pushed recovery rates above 95% for texts under 500 characters as of 2023. These digital tools, implementable on modern hardware including GPUs for parallel n-gram evaluation, address limitations of manual methods and demonstrate practical vulnerabilities even for keys from contemporary texts.

Comparison to Vigenère Cipher

The running key cipher and the share operational similarities as polyalphabetic substitution systems, both employing shifts based on a key stream to obscure letters, often visualized using a for encryption and decryption. In both cases, the ciphertext letter cic_i is generated by adding the plaintext letter mim_i and the corresponding key letter kik_i modulo 26, assuming A=0 to Z=25. A fundamental difference lies in key management: the relies on a short repeating keyword, typically 5 to 10 letters long, which cycles periodically throughout the message, introducing exploitable patterns. In contrast, the running key cipher uses a non-repeating key stream of at least the same length as the , often derived from a or other extended text, eliminating repetition and periodicity. This distinction profoundly impacts security. The Vigenère cipher's periodic key makes it vulnerable to cryptanalysis via the , which detects the key length by identifying repeated sequences spaced by multiples of the period, as detailed in Friedrich Kasiski's 1863 work. The running key cipher resists such period-detection attacks when the key is sufficiently long and lacks obvious structure, though its security depends on the of the key source; non-random book keys introduce redundancy that can aid recovery. Historically, running key ciphers emerged in the late as an improvement addressing the Vigenère's weaknesses exposed by Kasiski's method nearly three decades earlier, with the earliest formal description provided by Arthur-Joseph Hermann in 1892. This transition reflected a broader push toward longer, non-periodic keys to enhance resistance against frequency-based and period-analysis techniques prevalent in 19th-century cryptology. Quantitatively, the Vigenère cipher's keyspace is finite and scales as 26k26^k for a key of length kk, yielding, for example, 17,576 possibilities for k=3k=3, which brute-force attacks can exhaust given sufficient computational resources. For running key ciphers using book excerpts, the keyspace is effectively infinite due to the vast number of possible starting positions and text selections, rendering exhaustive search impractical despite lingering vulnerabilities from linguistic predictability.

Relation to One-Time Pad

The running key cipher and the (OTP) share a core operational similarity: both utilize a keystream of the same length as the , with achieved through modular addition, typically modulo 26 for alphabetic systems. This structure enables a running key cipher to achieve the perfect secrecy of the OTP when its keystream is generated from a truly random source and employed only once. A key distinction lies in key generation and usage: the OTP demands a truly random, never-reused keystream—often distributed via printed pads—to ensure , whereas running key ciphers commonly derive keystreams from predictable textual sources, such as , which compromise if the source material is known or guessable. Historically, the running key cipher acted as a precursor to the OTP, evolving from manual book-based systems to automated implementations. In 1917, patented an electrical system for teletype encryption that automated principles, initially using repeating keys but bridging toward full-length keystreams akin to running keys. Joseph Mauborgne advanced this in 1918 by emphasizing the need for random, non-repeating keys, thereby perfecting the OTP and resolving vulnerabilities in predictable keystreams through . From a security perspective, the running key cipher offers protection only insofar as its keystream remains unpredictable and single-use; in contrast, the OTP provides unconditional , as established by , where perfect secrecy holds when the key is independently random and at least as long as the , rendering ciphertext statistically independent of the message.

References

  1. https://courses.cs.duke.edu/fall02/cps182s/readings/APPLYC1.pdf
  2. https://www.cs.virginia.edu/~evans/greatworks/shannon1949.pdf
  3. https://websites.nku.edu/~christensen/1402extending%20keys.pdf
  4. http://www.diva-portal.org/smash/get/diva2:1877472/FULLTEXT01.pdf
  5. https://staff.science.uva.nl/h.vandermeer/pubs/riverbank16.pdf
  6. https://aclanthology.org/P12-2016.pdf
  7. https://sites.cs.ucsb.edu/~kemm/courses/cs177/crypto.pdf
  8. https://dummit.cos.northeastern.edu/docs/cryptography_1_classical_cryptosystems.pdf
  9. https://www.nsa.gov/portals/75/documents/news-features/declassified-documents/friedman-documents/publications/FOLDER_238/41748889078809.pdf
  10. http://practicalcryptography.com/ciphers/running-key-cipher/
  11. https://uomustansiriyah.edu.iq/media/lectures/5/5_2021_06_19!09_11_57_PM.pdf
  12. https://www.sciencedirect.com/topics/computer-science/polyalphabetic-cipher
  13. https://pages.mtu.edu/~shene/NSF-4/Tutorial/VIG/Vig-Kasiski.html
  14. https://academiccommons.columbia.edu/doi/10.7916/D8QV3W2Z/download
  15. https://www.nsa.gov/portals/75/documents/news-features/declassified-documents/cryptologic-histories/cryptology_of_gis.pdf
  16. http://www.crypto-it.net/eng/simple/running-key.html
  17. https://www.nsa.gov/portals/75/documents/about/cryptologic-heritage/historical-figures-publications/publications/wwii/cryptologic_aspects_of_gi.pdf
  18. http://www.cs.sjsu.edu/faculty/stamp/papers/Sigaba2.pdf
  19. https://www.nsa.gov/portals/75/documents/about/cryptologic-heritage/historical-figures-publications/publications/technology/The_SIGABA_ECM_Cipher_Machine_A_Beautiful_Idea3.pdf
  20. https://www.tandfonline.com/doi/full/10.1080/01611194.2021.1989522
  21. https://ecp.ep.liu.se/index.php/histocrypt/article/download/153/109/52
  22. https://www.cryptogram.org/downloads/aca.info/ciphers/Gromark.pdf
  23. https://theblackchamber552383191.wordpress.com/2020/11/18/gromark/
  24. https://sites.google.com/site/cryptocrackprogram/user-guide/cipher-types/other/periodic-gromark
  25. https://archive.org/stream/B-001-001-264/B-001-001-264_djvu.txt
  26. https://pages.cs.wisc.edu/~rist/642-spring-2014/shannon-secrecy.pdf
  27. https://cacr.uwaterloo.ca/hac/about/chap7.pdf
  28. https://cryptiana.web.fc2.com/code/runningkey.htm
  29. https://arxiv.org/abs/2305.12345
  30. https://people-ece.vse.gmu.edu/~jkaps/courses/ece646-f07/viewgraphs/lecture6_historical_h2.pdf
  31. https://books.google.com/books/about/Die_Geheimschriften_und_die_Dechiffrir_K.html?id=fB5dAAAAcAAJ
  32. https://books.google.com/books/about/Nouveau_syst%C3%A8me_correspondance_secr%C3%A8te.html?id=S5hi0QEACAAJ
  33. https://www.cachesleuth.com/runningkey.html
  34. https://patents.google.com/patent/US1310719A/en
  35. https://www.nsa.gov/press-room/digital-media-center/biographies/biography-view-page/article/3903416/mg-joseph-o-mauborgne-usa/
Add your contribution
Related Hubs
User Avatar
No comments yet.