Main : Index : Pencil and Paper Systems : 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]