Chapter 1, Part 2
In a substitution cipher, the order of the plaintext isn’t changed, but new letters (or symbols) are substituted for the ones in the plaintext. A Caesar Cipher, is a very simple cipher in which each letter in the plaintext is replaced by a letter a fixed number of positions later in the alphabet, say three:
Substitution systems are generally much more diverse and important than transposition systems. They typically rely on the concept of a cipher alphabet, a list of equivalents which are used to transform the plaintext into the secret form.
An example of one-to-one mapping is shown below:
Thus, enemy would become SWSHP, and RIS would reduce to foe. (Notice that the repetition of the S’s hint of the repeated e’s, incidentally. This preservation of frequency effects is a key weakness.)
Sometimes a cipher alphabet will provide for multiple alternative substitutes for a letter. These alternates are sometimes called homophones. (Strangely, these even show up in genetic codes, such as our DNA, which will be explored in Chapter 22.)
Sometimes a cipher alphabet will also include symbols that mean nothing, called nulls, which are simply included to confuse any interceptors.
Substitution ciphers come in four basic varieties:
- Monoalphabetic, where letters are the basic unit of encipherment and each symbol in the ciphertext stands for a unique plaintext letter. (There can be more than one ciphertext equivalent for any given plaintext letter.)
- Polyalphabetic, where single letters are the basic unit, but a number of alternative substitution alphabets are utilized in rotation (or some other scheme) to encipher successive letters of the plaintext. Thus, in one part of the ciphertext, the letter “X” might stand for the plaintext “m” while in another place the cipher letter “X” might stand for the plaintext “g,” etc.
- Polygraphic, where two or more plaintext letters form the unit of encipherment.
- Block Substitution, which includes Fractionating schemes. The government’s Data Encryption Standard is of this type.
As long as only one cipher alphabet is in use, as above, the system is called monoalphabetic. The intrinsic weakness of monoalphabetic systems is that the frequency patterns of the letters in the plaintext are carried over into the ciphertext. (This is even evident in the trivial examples above.) The use of multiple and dynamically changing alphabets was a major advance in cryptology. One type of polyalphabetic substitution ciphers was considered to be unbreakable for well over four centuries. It is called the Vigènere Polyalphabetic Cipher, based on a scheme originally invented by Leon Battista Alberti around 1466, which has been modified and improved since then.9 It was not until the 19th century that Kasiski developed a method of cracking the system regularly.
The polyalphabetic cipher involves the use of a key word in which each of the letter’s cardinal positions repetitively shift a Caesar cipher for each letter of the plaintext. This is usually accomplished through a table such as shown in Fig. 1-2.10
The keyword is repetitively written above the plaintext, and then the letters of both the keyword and the plaintext are used as entries into the table to obtain the ciphertext letters. Using “Darkly” as a keyword:
Thus, a given ciphertext letter may stand for different plaintext letters. (In the example, W stands for T in one case, M in another. H stands for H in one case, E in another. J for L in one case, G in another. With a five-letter keyword, five different cipher alphabets are used. The longer the keyword or keyphrase, the better. The ultimate keyword, or keyphrase, is one which is as long as the message itself.)
Figure 1-2: Vigenére Table
This denies the cryptanalyst two of his most powerful tools: letter frequencies and digram (letter pairing) frequencies. All letter frequencies (and digrams) are thus blurred by being enciphered by many different alphabets.
Blaise de Vigènere didn’t invent the polyalphabetic cipher that bears his name – Alberti did – but somehow his name has become attached to it. However, in 1585 he did come very close to inventing the most modern form of polyalphabetic cipher, which is called the one-time-pad. The only truly unbreakable cipher is one whose key is as long as the message, is totally random, and is never reused.
In most ciphers the basic unit is a single letter, but sometimes they exploit a letter-pair (digraph or digram) or larger groups of letters (polygrams). Perhaps the most well-known example of digraphic encipherment is the Playfair Cipher. (It was actually invented by Charles Wheatstone, but its enthusiastic promotion by Lyon Playfair, first Baron Playfair of St. Andrews, a scientist and public figure in Victorian England, caused it to be known in the War Office as “Playfair’s Cipher,” and the name has stuck to this day.)11
The Playfair Cipher is a simple, practical system which requires no special equipment, and properly used, provides a high level of protection for modest messages. It is based on a 5 x 5 matrix of the alphabet (our alphabet of 26 having been reduced to 25 by combining I and J as a single letter). The plaintext is then divided into pairs of letters (with an X inserted between any double letters).12 The plaintext letters are replaced as follows: if they occur in the same row or same column, they are replaced with the letters below, or to the right, respectively. If they are in different rows or columns, they define the corners of a rectangle and are replaced with the letters on the opposing diagonal. Decipherment is accomplished by simply reversing the process. An example is shown in Fig. 1-3.
Figure 1-3: The Playfair Code
To simplify the example, the alphabet was inserted in the matrix without a keyword. Normally the letters are inserted following a prearranged keyword, each letter in alphabetic order with no repetitions, and the unused letters following.13
The power of the method is that it obliterates the single-letter characteristics and undercuts monographic methods of frequency analysis. Encipherment by digraphs also halves the number of elements available for frequency analysis. Furthermore, the number of potential digraphs is far greater than the number of single letters, and consequently the linguistic characteristics are more widespread and have substantially less opportunity to individualize themselves.14
This method was very attractive as a field cipher: it required no special tables or apparatus. It required only a keyword that could be easily remembered and readily changed, and it was so simple that it could be easily executed in any hotel room. It was first used by the British War Office in the Boer War. It was also used when corresponding with T. E. Lawrence (of Arabia).15 It was also used by German spies during World War II who used Gideon Bibles, which could be found in any hotel room, for the keyphrases, drawing typically on the Book of Proverbs, using the chapter and verse corresponding to the day and the month, respectively. (The Book of Proverbs has 31 chapters, and no chapter has fewer than 12 verses.)
Block Substitution Systems
The difference between a stream cipher and a block cipher is that in the former you can obtain each ciphertext letter as each plaintext letter is read in, whereas in the latter you have to accumulate a block of letters before you encipher anything. Transposition ciphers are all of the block kind, as exemplified by the turning grilles, etc. In modern computer and communication use, dealing with entire blocks of letters is not a problem and can give rise to more highly advanced methods.
The National Bureau of Standards’ Data Encryption Standard (DES) involves a 64-bit key that controls 17 stages of polyalphabetic substitution, each alternated with 16 stages of transposition. Cryptanalysis involves an exhaustive search of all 264 keys.
(It was the author’s pursuit and personal support in developing this standard into a microchip that was singularly responsible for bringing Western Digital Corporation out of bankruptcy, and from which it has since grown into a Fortune 500 company.)
Fractionating schemes are also a form of block substitution cipher in which fractions – or sub-parts – of letters are treated as units of encipherment. They are best understood as combinations of substitution and transposition such as Bifid ciphers or Trifid, its close cousin, in which letters are referenced by the row and column numbers of a matrix of a scrambled alphabet, and these coordinates are then scrambled by various mathematical schemes.
Attacking such codes requires Chi-square analysis, indices of coincidence, and other advanced statistical techniques, but these are far beyond the scope of this brief survey.
- The Gronsfeld, Porta, and Beaufort systems are simply variations on the Vigènere and not as secure.
- This is also commonly accomplished through a slide rule type of device, known as the St. Cyr Slide, named after the French military academy where the device was first used. These are also available in a more convenient circular form similar to the cipher disks described later in this chapter. The Wheatstone Disk and Thomas Jefferson’s Cipher Wheels were essentially mechanical variations of these approaches.
- Kahn, p. 202.
- Another significant enhancement can be gained by writing the plaintext in two rows and using the vertically aligned letters as the digraphs. This introduces a transposition before the substitutions and leaves the cryptanalyst very little to work with unless there is considerable text to work with or strongly probable words in the context.
- A better scrambling technique is to write out the unused alphabet under the keyword, creating columns that are then taken vertically to fill out the matrix. The tendency for less popular letters to remain in a predictable order is easily exploited by a competent cryptanalyst.
- With 26 letters there are 676 digraphs. The most frequent English letters, e and t, have mean frequencies of 12 and 9%. The two most frequent English digraphs, th and he, reach only 3¼ and 2½%.
- Kahn, pp. 202, 312.