Vigenère cipher
The Vigenère cipher is a polyalphabetic substitution method of encrypting alphabetic text, in which each letter of the plaintext is shifted a different number of places down an alphabet based on a predetermined keyword, effectively using a series of interwoven Caesar ciphers to obscure letter frequencies.[1] It was first publicly described in 1586 by French diplomat Blaise de Vigenère in his book Traicté des chiffres ou secrètes manières d'escrire, though earlier similar polyalphabetic techniques had been proposed by Italian cryptographer Giovan Battista Bellaso in 1553.[1][2] The cipher operates using a Vigenère square (also known as a tabula recta), a 26-by-26 table of letters where each row represents a shifted version of the alphabet, starting from A in the first row to Z in the last.[3] To encrypt a message, the keyword is repeated to match the plaintext length, and for each position, the corresponding keyword letter determines the row of the square from which the plaintext letter (as a column) is shifted to produce the ciphertext.[1] Decryption reverses this process by using the keyword to identify the row and locating the ciphertext letter within it to find the original plaintext column.[3] This repeating key structure provides greater security than simple monoalphabetic ciphers like the Caesar shift, as it flattens the statistical distribution of letters in the ciphertext, making frequency analysis more challenging.[2] Historically, the Vigenère cipher gained its reputation for strength in the 19th century, often dubbed le chiffre indéchiffrable (the indecipherable cipher), and remained in practical use for diplomatic and military communications for nearly three centuries.[1] It was independently broken in the mid-19th century—first unpublished by English mathematician Charles Babbage in 1854, and then publicly by Prussian military officer Friedrich Kasiski in 1863 through methods that detect keyword length via repeated letter patterns (Kasiski examination).[2][4] Variants include the Beaufort cipher (a reciprocal form using subtraction instead of addition) and the Gronsfeld cipher (a weaker version using numeric digits 0–9 for shifts), which influenced later mechanical encryption devices like rotor machines.[3] Despite its vulnerabilities to modern cryptanalysis, the Vigenère cipher remains a foundational example in cryptography education, illustrating principles of key-based polyalphabetic substitution and the evolution from manual to computational security.[2]Background
History
The Vigenère cipher, a polyalphabetic substitution method, was first described by the Italian cryptographer Giovan Battista Bellaso in his 1553 treatise La cifra del. Sig. Giovan Battista Bellaso, where he outlined a system using a keyword to generate multiple Caesar shifts for encrypting messages.[5] Although the cipher bears the name of Blaise de Vigenère, a French diplomat and scholar, modern scholarship attributes its invention to Bellaso, with Vigenère's later description representing an independent or adapted formulation.[6] Vigenère detailed a variant in his 1586 book Traicté des chiffres ou secrètes manières d'escrire, incorporating polyalphabetic elements and referencing earlier works by Johannes Trithemius and Bellaso, though he did not claim originality.[1] During the Renaissance, the cipher gained traction for securing military and diplomatic communications across Europe, valued for its resistance to simple frequency analysis compared to monoalphabetic ciphers like the Caesar shift.[7] Its adoption extended into the early modern period, aiding confidential exchanges in an era of frequent warfare and intrigue, though specific instances of use remain sparsely documented due to the secrecy of cryptographic practices.[8] By the 19th century, the cipher had been popularized in France as le chiffre indéchiffrable ("the indecipherable cipher"), reflecting confidence in its security against contemporary attacks.[9] This reputation persisted until British mathematician and inventor Charles Babbage successfully cryptanalyzed it around 1846, employing methods to identify keyword lengths and dismantle the polyalphabetic structure, marking a pivotal advancement in cryptologic history.[1] Subsequent scholarship in the 20th century further clarified the misattribution to Vigenère, emphasizing Bellaso's foundational role through comparative analysis of historical texts.[5]Relation to Other Ciphers
The Vigenère cipher represents a significant evolution from the Caesar cipher, which employs a single fixed shift across the entire alphabet to substitute letters, making it vulnerable to frequency analysis. In contrast, the Vigenère cipher applies a series of Caesar shifts determined by the letters of a repeating keyword, effectively creating a polyalphabetic substitution that varies the encryption for each plaintext letter and disrupts simple statistical patterns.[10][11] This advancement built directly on the work of Johannes Trithemius, who in 1518 introduced the tabula recta, a tableau of 26 shifted alphabets that formed the basis for progressive polyalphabetic encryption in his Polygraphia. While Trithemius's method used a rigid, sequential progression of shifts without a keyword, Vigenère adapted this tableau in 1586 to incorporate a repeating keyword for more flexible and practical keying, enhancing usability while maintaining the polyalphabetic principle.[10][5] Unlike monoalphabetic ciphers, such as the Caesar or simple substitution ciphers, which map each plaintext letter to a consistent ciphertext equivalent using a single permutation of the alphabet, the Vigenère cipher employs multiple Caesar ciphers in sequence based on the keyword, resulting in a different substitution alphabet for positions corresponding to each key letter. This polyalphabetic structure flattens letter frequencies in the ciphertext, providing greater resistance to basic cryptanalytic attacks compared to monoalphabetic systems.[10][12] The Vigenère cipher served as a foundational precursor to more sophisticated polyalphabetic systems, influencing the development of rotor-based machines like the Enigma, which extended the concept of multiple dynamic substitutions through mechanical wheels to achieve even greater complexity and variability in encryption.[11][13] A common misconception attributes the original Vigenère cipher to an autokey mechanism, where the plaintext itself extends the key after an initial primer, but Vigenère's primary description in 1586 focused on the repeating keyword method, with autokey presented as a separate variant he adapted from earlier ideas like those of Girolamo Cardano; the repeating key version, actually originating with Giovan Battista Bellaso in 1553, became indelibly associated with Vigenère's name.[5][10]Operation
Description
The Vigenère cipher operates by employing a keyword to generate a series of Caesar shifts applied to the plaintext, creating a polyalphabetic substitution that varies the shift for each letter based on the keyword's letters.[14] The core mechanism involves repeating the keyword cyclically until it matches the length of the plaintext message, with each keyword letter determining the shift amount for the corresponding plaintext letter, where A corresponds to a shift of 0, B to 1, and so on up to Z for 25.[14] This process assumes the text consists solely of uppercase English letters, with spaces and punctuation typically ignored or removed prior to encryption.[14] Central to the cipher is the tabula recta, also known as the Vigenère square, which is a 26×26 grid of letters where the rows and columns are labeled A through Z.[15] The first row contains the standard alphabet (A B C ... Z), while each subsequent row is a leftward cyclic shift of the previous one by one position, such that the row labeled B starts with B C D ... A, the row C with C D E ... B, and so forth.[15] This table serves as a lookup tool for performing the shifts without explicit calculation. For encryption, the repeated keyword is aligned above the plaintext. For each position i, the letter from the keyword selects the row in the tabula recta, the plaintext letter selects the column, and the letter at their intersection becomes the ciphertext letter.[16] Decryption reverses this: the keyword letter again selects the row, but the ciphertext letter is located within that row to identify the column label, which yields the original plaintext letter.[14] A worked example illustrates the process: consider the plaintext "ATTACKATDAWN" and keyword "LEMON". The keyword repeats to "LEMONLEMONLE", aligned as follows:| Plaintext: | A | T | T | A | C | K | A | T | D | A | W | N |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Key: | L | E | M | O | N | L | E | M | O | N | L | E |
| Ciphertext: | L | X | F | O | P | V | E | F | R | N | H | R |
Algebraic Formulation
The Vigenère cipher operates on an alphabet of 26 letters, typically the English alphabet, where each letter is mapped to an integer from 0 to 25, with A corresponding to 0, B to 1, and so on up to Z at 25.[17][18] All arithmetic operations are performed modulo 26 to ensure the results cycle within this range.[17][19] Let the plaintext message be represented as a sequence of integers P_1, P_2, \dots, P_n, where each P_i is the numeric value of the i-th plaintext letter, and let the keyword be a string K of length m, with each letter K_j (for j = 1 to m) also mapped to an integer from 0 to 25.[17][19] The key stream is generated by repeating the keyword cyclically to match the length of the plaintext: for position i, the key value K_i = K_{(i \mod m)}, where the modulo operation ensures periodicity with period m.[17][18] This repetition aligns each key letter with the corresponding plaintext letter.[19] Encryption is defined by the formula C_i = (P_i + K_i) \mod 26 for each i = 1 to n, where C_i is the numeric value of the i-th ciphertext letter.[17][18][19] Decryption reverses this process using P_i = (C_i - K_i) \mod 26, recovering the original plaintext values.[17][18][19] The cipher's structure generalizes to any keyword length m, with the periodicity of the key stream directly tied to m, making the encryption a sequence of m independent Caesar shifts applied cyclically to the plaintext blocks.[17][19] The reversibility of the cipher follows from the properties of modular arithmetic: substituting the encryption formula into the decryption yields P_i = ((P_i + K_i) - K_i) \mod [26](/page/26) = P_i \mod [26](/page/26), confirming that decryption inverts encryption uniquely for any key.[17][18]Cryptanalysis
Kasiski Examination
The Kasiski examination, a key cryptanalytic technique for polyalphabetic substitution ciphers like the Vigenère, was first systematically described by Friedrich Kasiski in his 1863 book Die Geheimschriften und die Dechiffrirkunst, though Charles Babbage had developed a similar method around 1846 in unpublished work and applied it to break several ciphers by 1854.[20][21] This approach exploits the periodic nature of the repeating keyword, enabling attackers to estimate the key length without prior knowledge of the plaintext. The underlying principle relies on the fact that in a Vigenère cipher, identical plaintext segments encrypted under the same key letters will produce identical ciphertext segments; thus, if the same plaintext repeats at positions separated by a multiple of the key length, the corresponding ciphertext will exhibit matching sequences.[22] To apply the method, the analyst scans the ciphertext for repeated sequences of three or more letters, records the positional distances between each pair of occurrences, and computes the greatest common divisor (GCD) of these distances; the GCD is likely to be the key length or a factor thereof, as chance repetitions are less probable for longer strings.[20][22] For example, consider the ciphertext fragment "KIOV IEEIG KIOV NU...", where "KIOV" repeats with a distance of 9 positions between starts; the GCD of such distances (after checking multiple repeats and discarding spurious ones) might yield 3, indicating a key length of 3, as in the case where the key is "RUN" encrypting plaintext like "to be or not to be...".[20] Once the key length is estimated, the ciphertext can be divided into subsets for further analysis, such as frequency counts per position.[21] Despite its effectiveness, the Kasiski examination has limitations, including vulnerability to false positives from coincidental repeats in the ciphertext, which can suggest incorrect key lengths, and reduced reliability with short texts or when the plaintext lacks natural repetitions (e.g., in randomized or non-repetitive messages).[22][21] Its success improves with longer ciphertexts, where genuine repeats dominate over random ones.[20]Index of Coincidence Test
The Index of Coincidence (IC) is a statistical tool in cryptanalysis that measures the degree of unevenness in letter frequencies within a text, helping to distinguish between monoalphabetic and polyalphabetic ciphers such as the Vigenère.[23] Developed by William F. Friedman in 1920 while at Riverbank Laboratories, it was first published in his 1922 monograph The Index of Coincidence and Its Applications in Cryptography.[24] The IC provides a probabilistic indicator of redundancy in the text, with higher values suggesting language-like frequency distributions typical of monoalphabetic encryptions. The IC is calculated using the formula \text{IC} = \frac{\sum_{i=1}^{26} f_i (f_i - 1)}{N (N - 1)}, where f_i is the frequency of the i-th letter in the 26-letter alphabet, and N is the total number of letters in the text.[23] This expression estimates the probability that two randomly selected letters from the text are identical, accounting for the combinatorial nature of coincidences.[25] For plaintext in English, the expected IC is approximately 0.065 to 0.066, reflecting the natural unevenness of letter frequencies (e.g., 'E' at about 12.7%, 'Z' at 0.07%).[23] In contrast, for a random or uniformly distributed text (as in a long-key polyalphabetic cipher), the expected IC is about 0.038, equivalent to $1/26.[25] In the context of the Vigenère cipher, the overall IC of the ciphertext tends to be lower than that of English plaintext, approaching the random value of 0.038 as the key length l increases, due to the mixing of multiple substitution alphabets.[26] An approximation for this overall IC is given by \text{IC} \approx \frac{0.065}{l} + \left(1 - \frac{1}{l}\right) \times 0.038, which shows how the monoalphabetic contribution diminishes with longer keys.[25] Friedman's test applies the IC to estimate the Vigenère key length by testing possible values of k (typically from 1 to 20 or half the ciphertext length). For each assumed k, the ciphertext is partitioned into k separate sequences, each comprising every k-th letter (i.e., positions congruent modulo k). The IC is then computed for each sequence.[23] If k matches the true key length, each sequence encrypts a monoalphabetic substitution of the plaintext, yielding IC values around 0.065 for each; thus, the average IC across the k sequences will peak near 0.065. For incorrect k, the sequences remain polyalphabetic with effective periods that are multiples or factors, resulting in IC values closer to 0.038 and a lower average.[23] Peaks in the average IC plot identify the key length (and its multiples), enabling subsequent attacks like frequency analysis on the aligned cosets. Additionally, the variance of the individual sequence ICs can confirm the result: low variance (all near 0.065) supports the correct k, while high variance indicates misalignment.[25] This method excels with shorter ciphertexts (as few as 100-200 letters) where repeated sequences are scarce, relying instead on statistical properties of language rather than deterministic patterns.[26]Frequency Analysis
Frequency analysis applied to the Vigenère cipher involves treating each position in the key cycle as a separate monoalphabetic substitution cipher, specifically a Caesar shift, after the key length k has been estimated from prior tests. The ciphertext is divided into k cosets, where each coset comprises every k-th letter of the ciphertext, starting from the first, second, and so on up to the k-th position. For instance, with a key length of 5, the first coset includes positions 1, 6, 11, etc., the second coset positions 2, 7, 12, etc. Each coset is then analyzed independently by computing the frequency distribution of its letters, which should approximate the shifted frequencies of the plaintext language's letter distribution due to the fixed shift imposed by the corresponding key letter.[27][28] To deduce the key letter for a given coset, the observed frequency peaks are mapped to the expected plaintext frequencies, typically using standard tables for the language (e.g., English, where 'E' occurs about 12.7% of the time, followed by 'T' at 9.1%). The most frequent letter in the coset is assumed to correspond to the most common plaintext letter, such as 'E'; the key letter is then the one whose numerical position (A=0 to Z=25) equals the difference (ciphertext letter position minus plaintext letter position) modulo 26. For example, if the first coset shows a high frequency of 'K' (position 10), mapping it to 'E' (position 4) yields a shift of $10 - 4 = 6 modulo 26, corresponding to the key letter 'G' (position 6). This process is repeated for each coset, often with iterative refinement to resolve ambiguities by testing adjacent shifts and evaluating the resulting partial plaintext for readability or linguistic patterns. Tools like English frequency tables and computational aids for histogram comparison facilitate this mapping.[27][28] Challenges arise when the key length is long relative to the message length, resulting in few letters per coset and unreliable frequency estimates, or when the plaintext is in a non-English language without access to appropriate frequency tables, which can lead to incorrect mappings. Mutual indexing, involving cross-verification of frequency alignments between cosets or against known language patterns, can confirm candidate shifts but requires sufficient text volume. Overall, this method effectively reveals candidate key letters for each position, enabling partial decryption; a complete break necessitates successful analysis of all cosets to reconstruct the full key and recover the plaintext.[29][27]Key Elimination
Key elimination in the cryptanalysis of the Vigenère cipher involves generating candidate keys derived from preliminary frequency analysis of the ciphertext cosets and then systematically testing them against the full ciphertext to identify the correct one based on the resulting plaintext's linguistic properties.[30] This process typically begins by proposing multiple possible shifts for each position in the key, as each coset may yield several plausible mappings due to limited data or ambiguities in letter frequencies. Each candidate key is then applied to decrypt the entire message, and the outputs are scored for readability using measures such as digram and trigram frequencies that align with expected patterns in the target language, or more advanced n-gram models that evaluate overall text coherence.[31] Charles Babbage pioneered an iterative form of key elimination in the mid-19th century, assuming partial keys for initial cosets and propagating these assumptions to check for consistency across the remaining cosets by examining whether the decrypted fragments formed coherent plaintext segments.[30] This method involved testing letter chains at various intervals and eliminating incompatible partial keys through cross-validation of emerging plaintext patterns, such as recognizable word divisions or repeated phrases. Babbage applied this refinement technique to break military Vigenère ciphers during the Crimean War era, demonstrating its efficacy against practical encryptions of the time.[30] In modern computational approaches, key elimination for short keys employs brute-force enumeration of candidate keys combined with automated scoring via entropy measures or chi-squared statistics on the decrypted text to quantify deviation from random noise and favor English-like distributions.[31] For instance, starting from frequency-derived guesses, an algorithm might iteratively vary each key letter, selecting the variant that maximizes a fitness score based on n-gram probabilities, thereby narrowing to the optimal key through successive eliminations.[31] A representative example illustrates this process: given a ciphertext suspected to use a five-letter key, frequency analysis might suggest candidates like "LEMON" or "KEYED." Decrypting the full text with "LEMON" yields intelligible English prose with common digrams like "TH" and "HE," while "KEYED" produces gibberish with low trigram scores; thus, "LEMON" is selected as it aligns with expected language statistics.[32] Babbage's 1854 solution to Vigenère-encrypted military messages, refined through this elimination process, marked a pivotal historical break, enabling decryption of sensitive dispatches without prior knowledge of the full key.[30] However, the method's effectiveness diminishes for long keys, as the exponential growth in candidate combinations resists manual or even early computational efforts without substantial ciphertext length.[30]Variants
Autokey Cipher
The autokey cipher is a variant of the Vigenère cipher introduced by Blaise de Vigenère in 1586, in which the keystream is extended beyond an initial primer keyword by appending the plaintext, resulting in a non-repeating key as long as the message itself.[33] This approach modifies the standard repeating-key mechanism of the Vigenère cipher by making the keystream dependent on the message content, thereby increasing its effective length and complicating statistical attacks.[34] Vigenère described this system in his treatise Traicté des Chiffres, emphasizing its role in enhancing polyalphabetic security without requiring a pre-shared long key.[33] In the autokey mechanism, encryption begins with a short primer keyword of length m, followed by the plaintext to generate the full keystream. The sender concatenates the primer with the plaintext to form the keystream, ensuring each keystream position after the primer draws directly from the corresponding plaintext letter. This self-synchronizing process ties the key generation to the message, distinguishing it from the fixed repeating keyword of the classical Vigenère.[34] For decryption, the receiver starts with the shared primer to recover the initial plaintext segment from the ciphertext, then uses the successively recovered plaintext letters as the continuing keystream in a sequential manner.[33] Encryption follows the additive structure of the Vigenère cipher, where letters are numerically encoded (A=0, B=1, ..., Z=25). The ciphertext letter C_i at position i is computed as C_i = (P_i + K_i) \mod 26, with the keystream K defined such that K_1 to K_m are the primer letters, and K_{m+i} = P_i for i = 1, 2, \dots. This formulation ensures the keystream evolves with the plaintext, producing a unique shift for each message position after the primer.[34] Decryption reverses this process sequentially: for the first m positions, compute P_i = (C_i - K_i) \mod 26 using the primer for K; thereafter, use the recovered plaintext letters as the keystream, so P_i = (C_i - P_{i-m}) \mod 26. This step-by-step recovery allows full decryption with only the primer and ciphertext, as each new plaintext letter immediately becomes available for the next keystream position.[33] The main advantage of the autokey cipher lies in its extended, message-dependent keystream, which eliminates the periodic repetition of the standard Vigenère key and thereby reduces vulnerability to frequency analysis and methods like Kasiski examination that exploit key periodicity.[34] By matching the keystream length to the message, it achieves a theoretical perfect secrecy for random plaintext under certain conditions, though practical weaknesses arise from predictable plaintext structures that can aid partial key recovery.[33] Historically, while Vigenère proposed the autokey as a robust improvement, its security was scrutinized in the 19th century alongside the repeating-key Vigenère, with Charles Babbage contributing to early cryptanalytic techniques that highlighted differences in their breakability around 1854.[34] For example, consider the primer "KEY" (m=3) and plaintext "ATTACK". The initial keystream segment is "KEY", extended by the plaintext's first three letters to "KEYATT" for the full message. Encoding yields:- Position 1: A (0) + K (10) = 10 mod 26 → K
- Position 2: T (19) + E (4) = 23 mod 26 → X
- Position 3: T (19) + Y (24) = 43 mod 26 = 17 → R
- Position 4: A (0) + A (0) = 0 mod 26 → A
- Position 5: C (2) + T (19) = 21 mod 26 → V
- Position 6: K (10) + T (19) = 29 mod 26 = 3 → D
Beaufort Cipher
The Beaufort cipher is a polyalphabetic substitution cipher that modifies the Vigenère cipher by reversing the order of the letters in the tabula recta and employing subtraction instead of addition for enciphering. This reversal means the tableau's rows and columns are arranged such that the standard alphabetical progression is inverted, facilitating a distinct lookup process. The cipher was attributed to Sir Francis Beaufort, a British hydrographer and rear admiral, who developed it in the early 19th century for secure naval communications, leveraging its simplicity for manual use in maritime signaling.[35][36] In the Beaufort cipher, encryption is performed using the formula C_i = (K_i - P_i) \mod 26, where C_i is the ciphertext letter, K_i is the corresponding key letter, and P_i is the plaintext letter, with letters mapped to numbers from 0 (A) to 25 (Z); to ensure a non-negative result, 26 is added if the subtraction yields a negative value. Decryption employs the identical operation: P_i = (K_i - C_i) \mod 26, rendering the cipher reciprocal—meaning the same procedure serves both encryption and decryption without additional steps. This symmetry distinguishes it from the Vigenère cipher, where encryption adds the key to the plaintext modulo 26, while decryption subtracts, and it enables faster manual operations by eliminating the need to switch methods mid-process. The repeating keyword is applied over the plaintext in the same manner as Vigenère, maintaining polyalphabetic substitution but with equivalent cryptographic security, as the core weaknesses, such as vulnerability to key length detection via methods like the Kasiski examination, remain unchanged.[37][38] For example, using the key "LEMON" (repeated as needed) and plaintext "ATTACK", the numerical mappings are key values 11 (L), 4 (E), 12 (M), 14 (O), 13 (N), 11 (L) and plaintext values 0 (A), 19 (T), 19 (T), 0 (A), 2 (C), 10 (K). Applying the formula yields ciphertext values (11-0)=11 (L), (4-19+26)=11 (L), (12-19+26)=19 (T), (14-0)=14 (O), (13-2)=11 (L), (11-10)=1 (B), producing the ciphertext "LLTOLB"—distinct from the Vigenère output for the same inputs. This reciprocity ensures that applying the same key to "LLTOLB" recovers "ATTACK" directly, highlighting the cipher's operational efficiency for field use.[37]Gronsfeld Cipher
The Gronsfeld cipher is a polyalphabetic substitution cipher that functions as a variant of the Vigenère cipher, employing a repeating numeric key consisting of digits from 0 to 9 to determine the shift for each plaintext letter.[34] Unlike the Vigenère, which uses alphabetic characters for shifts ranging from 0 to 25, the Gronsfeld restricts shifts to 0 through 9, making it a numeric analog with a correspondingly reduced key space.[39] This limitation simplifies implementation but also diminishes security by limiting the variety of possible encryptions compared to the full 26-letter alphabet.[34] The Gronsfeld cipher is named after Count Jost Maximilian von Gronsfeld (1598–1662), a Bavarian field marshal to whom its invention is attributed in the mid-17th century; it was described by the Jesuit scholar Gaspar Schott in his 1659 work Magia universalis naturæ et artis for cryptographic purposes.[40] It gained some use during that period as a practical adaptation of polyalphabetic encryption principles, though it remained less complex than its alphabetic predecessor.[41] In operation, the numeric key repeats cyclically across the plaintext, with each digit specifying the Caesar shift to apply to the corresponding letter, treating the alphabet as numbered from A=0 to Z=25. The encryption formula is given by: C_i = (P_i + D_i) \mod 26 where P_i is the numeric value of the i-th plaintext letter, D_i is the corresponding key digit (0-9), and C_i is the numeric value of the i-th ciphertext letter.[34] Decryption reverses this by subtracting the key digits modulo 26. For example, using the key "432" to encrypt the plaintext "HELLO" (with the key repeating as 4,3,2,4,3): H (7) + 4 = 11 (L), E (4) + 3 = 7 (H), L (11) + 2 = 13 (N), L (11) + 4 = 15 (P), O (14) + 3 = 17 (R), yielding "LHNPR".[42] A primary weakness of the Gronsfeld cipher stems from its constrained key space: for a key of length m, there are only $10^m possible keys, far fewer than the $26^m for a Vigenère key of equivalent length, enabling feasible brute-force attacks even for modest m.[34] This numeric restriction also makes the cipher more susceptible to frequency-based cryptanalysis, as the limited shift variety produces less uniform letter distributions than broader polyalphabetic systems.[39]Running Key Variant
The running key variant of the Vigenère cipher modifies the standard polyalphabetic substitution by using a long, non-repeating keystream generated from an external text source, such as a specific passage from a book, document, or prayer, to provide successive key letters. This keystream is applied sequentially to the plaintext without repetition or cycling, ensuring the key length matches or exceeds the message length. The mechanism relies on the Vigenère tableau for encipherment: each plaintext letter is shifted by the numerical value (A=0 to Z=25) of the corresponding keystream letter, with the ciphertext letter determined modulo 26. Decipherment reverses this process by subtracting the keystream shift from the ciphertext.[43][44] Historically, the running key cipher emerged in the late 19th and early 20th centuries as a practical enhancement to earlier polyalphabetic systems, with documented use in military and espionage contexts. For instance, German intelligence services employed variants where offsets were determined by running keys during World War I. William F. Friedman, a pioneering U.S. cryptographer, analyzed and described methods for solving such ciphers in his 1918 publication, noting their prior reputation for security in field operations, including with the U.S. Army Disk device. This variant served as a precursor to more advanced systems like the one-time pad, bridging classical book-based encryption and modern stream ciphers.[45][43][46] In terms of security, the running key variant offers significantly greater resistance to traditional attacks like Kasiski examination compared to the repeating-key Vigenère, as the absence of periodicity disrupts key length detection. If the keystream is truly random and at least as long as the plaintext, it achieves information-theoretic security akin to a one-time pad, rendering it unbreakable without the key. However, practical implementations using natural language sources, such as book excerpts, introduce vulnerabilities: long ciphertexts enable frequency analysis of digrams or trigrams, while known plaintext attacks can reveal key portions if the source text is guessable. Friedman's work demonstrated that even short messages could be solved via probable word methods, and series of messages under the same key were decipherable faster than encipherment.[44][47][43] To illustrate, consider the plaintext "ATTACK" (shifted to numbers: A=0, T=19, etc.) and a running key excerpt "THEQUICK" (T=19, H=7, E=4, Q=16, U=20, I=8, C=2, K=10). The ciphertext is computed as follows:| Position | Plaintext | P Value | Key Letter | K Value | C Value (P + K mod 26) | Ciphertext |
|---|---|---|---|---|---|---|
| 1 | A | 0 | T | 19 | 19 | T |
| 2 | T | 19 | H | 7 | 0 (26 mod 26) | A |
| 3 | T | 19 | E | 4 | 23 | X |
| 4 | A | 0 | Q | 16 | 16 | Q |
| 5 | C | 2 | U | 20 | 22 | W |
| 6 | K | 10 | I | 8 | 18 | S |