 Polyalphabetic substitutions and Vigen`ere ciphers (historical)

A simple substitution cipher involves a single mapping of the plaintext alphabet onto ciphertext characters. A more complex alternative is to use different substitution mappings (called multiple alphabets) on various portions of the plaintext. This results in so-called polyalphabetic substitution (also introduced in Definition 1.30). In the simplest case, the different alphabets are used sequentially and then repeated, so the position of each plaintext character in the source string determines which mapping is applied to it. Under different alphabets, the same plaintext character is thus encrypted to different ciphertext characters, precluding simple frequency analysis as per mono-alphabetic substitution (§7.3.5).

The simple Vigenere cipher is a polyalphabetic substitution cipher, introduced in Example 1.31. The definition is repeated here for convenience.

7.53 Definition A simple Vigenere cipher of period t, over an s-character alphabet, involves

a f-character key fcxfc2 • • • h- The mapping of plaintext m = ... to ciphertext

с = C1C2C3 ... is defined on individual characters by c* = m, + fc, mod s, where subscript i in kt is taken modulo t (the key is re-used).

The simple Vigenere uses t shift ciphers (see Example 7.48), defined by t shift values hi, each specifying one of .s (mono-alphabetic) substitutions; ki is used on the characters in position i, i + s, i + 2s,... . In general, each of the t substitutions is different; this is referred to as using t alphabets rather than a single substitution mapping. The shift cipher (Example 7.48) is a simple Vigenere with period t = 1.

7.54 Example (Beaufort variants of Vigenere) Compared to the simple Vigenere mapping c, =

ггц + ki mod s, the Beaufort cipher has c, = ki - m, mod s, and is its own inverse. The variant Beaufort has encryption mapping c* = m, - k, mod s.

7.55 Example (compound Vigenere) The compound Vigenere has encryption mapping c, =

mi + (kj + kf +----f Zc[) mod s, where in general the keys kJ ,1 < j < r, have distinct

periods tj, and the subscript i in kj, indicating the ith character of У, is taken modulo tj. This corresponds to the sequential application of r simple Vigeneres, and is equivalent to a simple Vigenere of period lcm(f 1.... ,tr).

7.56 Example (single mixed alphabet Vigenere) A simple substitution mapping defined by a

general permutation e (not restricted to an alphabetic shift), followed by a simple Vigenere, is defined by the mapping c, = e(m,) + kt mod s, with inverse m, = e-1 (c* -hi) mod s. An alternative is a simple Vigenere followed by a simple substitution: c,: = e(m4- + k, mod s), with inverse m, = e_1(c4) — к, mod s.

7.57 Example (fidl Vigenere) In a simple Vigenere of period f, replace the mapping defined by

the shift value ki (for shifting character m,) by a general permutation of the alphabet. The result is the substitution mapping с, = е44), where the subscript i in e4 is taken modulo t. The key consists of / permutations ei,... , et.

7.58 Example (running-key Vigenere) If the keystream fc4 of a simple Vigenere is as long as

the plaintext, the cipher is called a running-key cipher. For example, the key may be meaningful text from a book. □

While running-key ciphers prevent cryptanalysis by the Kasiski method (§7.3.5), if the key has redundancy, cryptanalysis exploiting statistical imbalances may nonetheless succeed. For example, when encrypting plaintext English characters using a meaningful text as a running key, cryptanalysis is possible based on the observation that a significant proportion of ciphertext characters results from the encryption of high-frequency running text characters with high-frequency plaintext characters.

• 7.59 Fact A running-key cipher can be strengthened by successively enciphering plaintext under two or more distinct running keys. For typical English plaintext and running keys, it can be shown that iterating four such encipherments appears unbreakable.
• 7.60 Definition An auto-key cipher is a cipher wherein the plaintext itself serves as the key (typically subsequent to the use of an initial pruning key).
• 7.61 Example (auto-key Vigenere) In a running-key Vigenere (Example 7.58) with an s-char-

acter alphabet, define a priming key к = ki k% ... kt. Plaintext characters m, are encrypted as c; = m, + ki mod s for 1 < i < t (simplest case: t = 1). For i > f, c4 = (m, + m,_t) mod s. An alternative involving more keying material is to replace the simple shift by a full Vigenere with permutations e4,1 defined by the key k, or character m,: for 1 < i < t, Ci = ekt(ггц), and for i > t, ct = emi_t (m4). □

An alternative to Example 7.61 is to auto-key a cipher using the resulting ciphertext as the key: for example, for i > t, Cj = (m, + c4_t) mod s. This, however, is far less desirable, as it provides an eavesdropping cryptanalyst the key itself.

7.62 Example (Vernain viewed as a Vigenere) Consider a simple Vigenere defined by c, = rrii + ki mod s. If the keystream is truly random and independent - as long as the plaintext and never repeated (cf. Example 7.58) - this yields the unconditionally secure Vernam cipher (Definition 1.39; §6.1.1), generalized from a binary' to an arbitrary' alphabet. □