[Next] [Up] [Previous] [Index]

Conclusions for Chapter 1

This first chapter has touched on the major basic elements that apply to any form of encryption.

Its treatment of them has been brief, almost to the point of being perfunctory. Encyclopedia articles and inexpensive books cover this territory fairly well. The more recent methods of encryption are covered in more specialized publications; that, and a fascination with their intricacies, has led me to cover them in more detail.

Because most methods of substitution require some sort of chart or table (the Gronsfeld was specifically designed to avoid this problem), or a slide or disk for polyalphabetics, transposition ciphers were quite popular with armies as field ciphers.

Although it is easy to create a cipher that is very difficult to solve by a sufficiently complicated combination of transposition and substitution, some simple ciphers combining both are breakable.

During World War I, for a short time Germany used Vigenere encipherment with key ABC (and, later, with key ABCD - but only for deceptive transmissions and not important messages) followed by a simple columnar transposition.

For puzzle-solving purposes, the "Nicodemus" cipher breaks a message into complete rectangular blocks, which are transposed by exactly the same keyword as was previously used to encipher them in Vigenere. Thus, the enciphered message consists of groups of plaintext letters encrypted in Vigenere with the same key, which can, of course, be exploited by the cryptanalyst.

Claude Shannon, the father of information theory, who also contributed to the theory of chess-playing computers, wrote a paper in The Bell System Technical Journal the title of which was The Communications Theory of Secrecy Systems in which he noted that the two basic elements of a cipher system are confusion and diffusion.

This has influenced the design of some cipher systems. A preliminary sketch of the design of IBM's LUCIFER block cipher, appearing in Scientific American embodied these elements in almost a pure form. (The actual LUCIFER cipher as implemented was quite different, although it also embodied those elements, but in a less straightforward way.)

Generally, confusion is understood as substitution, and diffusion is understood as transposition.

These terms are, however, general and inclusive. Based on the specific methods of attaining security found in the actual pencil-and-paper systems we've met so far, I feel it is warranted to take the dangerous step of moving to a more specific and concrete division of the operations within a cipher system.

The danger is that it could limit the imagination of cipher designers by being more concrete. But since the terms 'confusion' and 'diffusion' are tending to be identified with the simplest forms of substitution and transposition, it seems to me that more detail might instead stimulate cipher designers to consider more options.

Thus, I propose the following set of basic elements in a cryptographic system:

Confusion
replacing symbols by other symbols.

Diffusion
moving of plaintext symbols to other positions within the ciphertext.

Convolution
the achievement of diffusion by means of confusion; the effect of performing diffusion on a finer scale than confusion. This refers to what happens in polygraphic and fractionation systems.

Alternation
changing, from one portion of the ciphertext to the next, of the rules for confusion and/or diffusion.

Indirection
placing elements in a cipher 'behind' other elements so that their effects are harder to analyze.

With this division, more of the methods actually used suggest themselves. Also, a measure of quality can perhaps be noted. For confusion and diffusion, bigger seems to be better. For alternation, the complexity of the scheme of alternation, its unpredictability, is the measure of quality.

Associated with these goals are specific means, such as substitution for confusion.

If we view a message as an array of symbols, where P(n) is the n-th element of the plaintext message P, and C is the ciphertext message, one can illustrate the various techniques by formulas.

Substitution (Confusion)
Transforming a message by replacing the values of its elements according to some rule; for example, C(i)=S(P(i)) over all i in the message, where S is a substitution table indexed over the elements of the alphabet used.

Transposition (Diffusion)
Transforming a message by placing its elements in different locations within the message; for example, C(T(i))=P(i) over all i in the message, where T is a transposition table indexed over all the character positions in the message.

Fractionation (Convolution)
Transforming a message from being expressed in a number of symbols of one alphabet to a different number of symbols in an alphabet of a different size, combined with transpositions and substitutions on those alphabets. Such a transformation might have a form such as C(i/2) = S(P(i)*N+P(i-1)) where i starts as 2 and goes over all the even-numbered characters of the original message, and N is the number of characters in the original alphabet. Its inverse would be P(2i) = SL(C(i)) and P(2i-1) = SR(C(i)), where SL and SR are substitutions such that mapping the characters c of the original alphabet to pairs ( SL(c), SR(c) ) is bijective; that is, different inputs become different outputs in both directions. This is most useful when substitutions are applied to the message with the larger alphabet size and fewer characters, and transpositions are applied to the message with the smaller alphabet size and more characters.

Polyalphabeticity (Variation)
Applying a different substitution rule to different characters of the message. Thus, C(i)=S(P(i),i) where the output of the substitution is a function of the character's position in the message as well as the particular character.

Autokey (also Variation)
Causing the rule of encipherment for a part of a message to depend on another part of the same message. C(i)=S(P(i)+P(i-1)) is a classic form of autokey, which requires adding a dummy P(0) character to the start of the message. This results in encipherment differing from one message to another.

Indirection involves preparing things like substitution tables in ways that are ciphers in their own right; hence, it isn't found very much in simple paper-and-pencil ciphers, where the amount of work to be done must be kept limited. The methods used for forming substitution alphabets from a keyword by means of a transposition block, such as the Ohaver method, noted previously, involve indirection in a sense, but only once during a message. So there is no basic pencil-and-paper technique which is an effective example of indirection. However, later on we will see the rotor machine SIGABA, which may be considered the classic illustration of indirection.


[Next] [Up] [Previous] [Index]

Next
Table of Contents
Main page