Communication Theory of Secrecy Systems ?
`
`By C. E. SHANNON
`
`1
`
`INTRODUCTION AND SUMMARY
`
`The problems of cryptography and secrecy systems furnish an interesting ap-
`plication of communication theory1. In this paper a theory of secrecy systems
`is developed. The approach is on a theoretical level and is intended to com-
`plement the treatment found in standard works on cryptography2. There, a
`detailed study is made of the many standard types of codes and ciphers, and
`of the ways of breaking them. We will be more concerned with the general
`mathematical structure and properties of secrecy systems.
`The treatment is limited in certain ways. First, there are three general
`types of secrecy system: (1) concealment systems, including such methods
`as invisible ink, concealing a message in an innocent text, or in a fake cov-
`ering cryptogram, or other methods in which the existence of the message
`is concealed from the enemy; (2) privacy systems, for example speech in-
`version, in which special equipment is required to recover the message; (3)
`“true” secrecy systems where the meaning of the message is concealed by
`cipher, code, etc., although its existence is not hidden, and the enemy is as-
`sumed to have any special equipment necessary to intercept and record the
`transmitted signal. We consider only the third type—concealment system are
`primarily a psychological problem, and privacy systems a technological one.
`Secondly, the treatment is limited to the case of discrete information
`where the message to be enciphered consists of a sequence of discrete sym-
`bols, each chosen from a finite set. These symbols may be letters in a lan-
`guage, words of a language, amplitude levels of a “quantized” speech or
`video signal, etc., but the main emphasis and thinking has been concerned
`with the case of letters.
`The paper is divided into three parts. The main results will now be briefly
`summarized. The first part deals with the basic mathematical structure of
`secrecy systems. As in communication theory a language is considered to be
`represented by a stochastic process which produces a discrete sequence of
`
`? The material in this paper appeared in a confidential report “A Mathematical Theory of Cryptogra-
`phy” dated Sept.1, 1946, which has now been declassified.
`1 Shannon, C. E., “A Mathematical Theory of Communication,” Bell System Technical Journal, July
`1948, p.623.
`2 See, for example, H. F. Gaines, “Elementary Cryptanalysis,” or M. Givierge, “Cours de Cryptogra-
`phie.”
`
`1
`
`DISH 1019
`
`

`

`symbols in accordance with some system of probabilities. Associated with
`a language there is a certain parameter D which we call the redundancy of
`the language. D measures, in a sense, how much a text in the language can
`be reduced in length without losing any information. As a simple example,
`since u always follows q in English words, the u may be omitted without
`loss. Considerable reductions are possible in English due to the statistical
`structure of the language, the high frequencies of certain letters or words, etc.
`Redundancy is of central importance in the study of secrecy systems.
`A secrecy system is defined abstractly as a set of transformations of one
`space (the set of possible messages) into a second space (the set of possible
`cryptograms). Each particular transformation of the set corresponds to enci-
`phering with a particular key. The transformations are supposed reversible
`(non-singular) so that unique deciphering is possible when the key is known.
`Each key and therefore each transformation is assumed to have an a priori
`probability associated with it—the probability of choosing that key. Similarly
`each possible message is assumed to have an associated a priori probability,
`determined by the underlying stochastic process. These probabilities for the
`various keys and messages are actually the enemy cryptanalyst’s a priori
`probabilities for the choices in question, and represent his a priori knowledge
`of the situation.
`To use the system a key is first selected and sent to the receiving point.
`The choice of a key determines a particular transformation in the set form-
`ing the system. Then a message is selected and the particular transformation
`corresponding to the selected key applied to this message to produce a cryp-
`togram. This cryptogram is transmitted to the receiving point by a channel
`and may be intercepted by the “enemy?.” At the receiving end the inverse
`of the particular transformation is applied to the cryptogram to recover the
`original message.
`If the enemy intercepts the cryptogram he can calculate from it the a pos-
`teriori probabilities of the various possible messages and keys which might
`have produced this cryptogram. This set of a posteriori probabilities consti-
`tutes his knowledge of the key and message after the interception. “Knowl-
`edge” is thus identified with a set of propositions having associated proba-
`bilities. The calculation of the a posteriori probabilities is the generalized
`problem of cryptanalysis.
`As an example of these notions, in a simple substitution cipher with ran-
`dom key there are 26! transformations, corresponding to the 26! ways we can
`substitute for 26 different letters. These are all equally likely and each there-
`fore has an a priori probability 1
`26!. If this is applied to “normal English”
`
`? The word “enemy,” stemming from military applications, is commonly used in cryptographic work
`to denote anyone who may intercept a cryptogram.
`
`657
`
`2
`
`

`

`the cryptanalyst being assumed to have no knowledge of the message source
`other than that it is producing English text, the a priori probabilities of var-
`ious messages of N letters are merely their relative frequencies in normal
`English text.
`If the enemy intercepts N letters of cryptograms in this system his prob-
`abilities change. If N is large enough (say 50 letters) there is usually a single
`message of a posteriori probability nearly unity, while all others have a total
`probability nearly zero. Thus there is an essentially unique “solution” to the
`cryptogram. For N smaller (say N = 15) there will usually be many mes-
`sages and keys of comparable probability, with no single one nearly unity. In
`this case there are multiple “solutions” to the cryptogram.
`Considering a secrecy system to be represented in this way, as a set of
`transformations of one set of elements into another, there are two natural
`combining operations which produce a third system from two given systems.
`The first combining operation is called the product operation and corresponds
`to enciphering the message with the first secrecy system R and enciphering
`the resulting cryptogram with the second system S, the keys for R and S
`being chosen independently. This total operation is a secrecy system whose
`transformations consist of all the products (in the usual sense of products
`of transformations) of transformations in S with transformations in R. The
`probabilities are the products of the probabilities for the two transformations.
`The second combining operation is “weighted addition.”
`
`T = pR + qS
`
`p + q = 1
`
`It corresponds to making a preliminary choice as to whether system R or S
`is to be used with probabilities p and q, respectively. When this is done R or
`S is used as originally defined.
`It is shown that secrecy systems with these two combining operations
`form essentially a “linear associative algebra” with a unit element, an alge-
`braic variety that has been extensively studied by mathematicians.
`Among the many possible secrecy systems there is one type with many
`special properties. This type we call a “pure” system. A system is pure if all
`keys are equally likely and if for any three transformations Ti; Tj; Tk in the
`set the product
`
`TiT (cid:0)1
`j Tk
`is also a transformation in the set. That is, enciphering, deciphering, and en-
`ciphering with any three keys must be equivalent to enciphering with some
`key.
`With a pure cipher it is shown that all keys are essentially equivalent—
`they all lead to the same set of a posteriori probabilities. Furthermore, when
`
`658
`
`3
`
`

`

`a given cryptogram is intercepted there is a set of messages that might have
`produced this cryptogram (a “residue class”) and the a posteriori probabili-
`ties of message in this class are proportional to the a priori probabilities. All
`the information the enemy has obtained by intercepting the cryptogram is a
`specification of the residue class. Many of the common ciphers are pure sys-
`tems, including simple substitution with random key. In this case the residue
`class consists of all messages with the same pattern of letter repetitions as the
`intercepted cryptogram.
`Two systems R and S are defined to be “similar” if there exists a fixed
`transformation A with an inverse, A(cid:0)1, such that
`
`R = AS:
`
`If R and S are similar, a one-to-one correspondence between the resulting
`cryptograms can be set up leading to the same a posteriori probabilities. The
`two systems are cryptanalytically the same.
`The second part of the paper deals with the problem of “theoretical se-
`crecy”. How secure is a system against cryptanalysis when the enemy has
`unlimited time and manpower available for the analysis of intercepted cryp-
`tograms? The problem is closely related to questions of communication in
`the presence of noise, and the concepts of entropy and equivocation devel-
`oped for the communication problem find a direct application in this part of
`cryptography.
`“Perfect Secrecy” is defined by requiring of a system that after a cryp-
`togram is intercepted by the enemy the a posteriori probabilities of this cryp-
`togram representing various messages be identically the same as the a pri-
`ori probabilities of the same messages before the interception. It is shown
`that perfect secrecy is possible but requires, if the number of messages is fi-
`nite, the same number of possible keys. If the message is thought of as being
`constantly generated at a given “rate” R (to be defined later), key must be
`generated at the same or a greater rate.
`If a secrecy system with a finite key is used, and N letters of cryptogram
`intercepted, there will be, for the enemy, a certain set of messages with cer-
`tain probabilities that this cryptogram could represent. As N increases the
`field usually narrows down until eventually there is a unique “solution” to
`the cryptogram; one message with probability essentially unity while all oth-
`ers are practically zero. A quantity H(N ) is defined, called the equivocation,
`which measures in a statistical way how near the average cryptogram of N
`letters is to a unique solution; that is, how uncertain the enemy is of the orig-
`inal message after intercepting a cryptogram of N letters. Various properties
`of the equivocation are deduced—for example, the equivocation of the key
`never increases with increasing N. This equivocation is a theoretical secrecy
`
`659
`
`4
`
`

`

`index—theoretical in that it allows the enemy unlimited time to analyse the
`cryptogram.
`The function H(N ) for a certain idealized type of cipher called the ran-
`dom cipher is determined. With certain modifications this function can be
`applied to many cases of practical interest. This gives a way of calculating
`approximately how much intercepted material is required to obtain a solution
`to a secrecy system. It appears from this analysis that with ordinary languages
`and the usual types of ciphers (not codes) this “unicity distance” is approxi-
`mately H(K)
`D . Here H(K) is a number measuring the “size” of the key space.
`If all keys are a priori equally likely H(K) is the logarithm of the number of
`possible keys. D is the redundancy of the language and measures the amount
`of “statistical constraint” imposed by the language. In simple substitution
`with random key H(K) is log 1026! or about 20 and D (in decimal digits per
`letter) is about :7 for English. Thus unicity occurs at about 30 letters.
`It is possible to construct secrecy systems with a finite key for certain
`“languages” in which the equivocation does not approach zero as N !1. In
`this case, no matter how much material is intercepted, the enemy still does
`not obtain a unique solution to the cipher but is left with many alternatives, all
`of reasonable probability. Such systems we call ideal systems. It is possible
`in any language to approximate such behavior—i.e., to make the approach
`to zero of H(N ) recede out to arbitrarily large N. However, such systems
`have a number of drawbacks, such as complexity and sensitivity to errors in
`transmission of the cryptogram.
`The third part of the paper is concerned with “practical secrecy”. Two
`systems with the same key size may both be uniquely solvable when N letters
`have been intercepted, but differ greatly in the amount of labor required to
`effect this solution. An analysis of the basic weaknesses of secrecy systems
`is made. This leads to methods for constructing systems which will require a
`large amount of work to solve. Finally, a certain incompatibility among the
`various desirable qualities of secrecy systems is discussed.
`
`PART I
`
`MATHEMATICAL STRUCTURE OF SECRECY SYSTEMS
`
`2 SECRECY SYSTEMS
`
`As a first step in the mathematical analysis of cryptography, it is necessary to
`idealize the situation suitably, and to define in a mathematically acceptable
`way what we shall mean by a secrecy system. A “schematic” diagram of a
`general secrecy system is shown in Fig. 1. At the transmitting end there are
`
`660
`
`5
`
`

`

`two information sources—a message source and a key source. The key source
`produces a particular key from among those which are possible in the system.
`This key is transmitted by some means, supposedly not interceptible, for ex-
`ample by messenger, to the receiving end. The message source produces a
`message (the “clear”) which is enciphered and the resulting cryptogram sent
`to the receiving end by a possibly interceptible means, for example radio. At
`the receiving end the cryptogram and key are combined in the decipherer to
`recover the message.
`
`ENEMY
`CRYPTANALYST
`
`E
`
`MESSAGE
`SOURCE
`
`MESSAGE
`M
`
`ENCIPHERER CRYPTOGRAM
`TK
`E
`
`DECIPHERER
`−1
`TK
`
`MESSAGE
`M
`
`E
`
`KEY
`K
`
`KEY
`SOURCE
`
`KEY K
`
`Fig. 1. Schematic of a general secrecy system
`
`Evidently the encipherer performs a functional operation. If M is the mes-
`sage, K the key, and E the enciphered message, or cryptogram, we have
`E = f (M; K)
`that is E is function of M and K. It is preferable to think of this, however, not
`as a function of two variables but as a (one parameter) family of operations
`or transformations, and to write it
`
`E = TiM:
`The transformation Ti applied to message M produces cryptogram E. The
`index i corresponds to the particular key being used.
`We will assume, in general, that there are only a finite number of possible
`keys, and that each has an associated probability pi. Thus the key source
`is represented by a statistical process or device which chooses one from
`the set of transformations T1; T2; (cid:1) (cid:1) (cid:1); Tm with the respective probabilities
`p1; p2; (cid:1) (cid:1) (cid:1); pm. Similarly we will generally assume a finite number of possible
`messages M1; M2; (cid:1) (cid:1) (cid:1); Mn with associate a priori probabilities q1; q2; (cid:1) (cid:1) (cid:1); qn.
`The possible messages, for example, might be the possible sequences of En-
`glish letters all of length N, and the associated probabilities are then the
`relative frequencies of occurrence of these sequences in normal English text.
`
`661
`
`6
`
`

`

`At the receiving end it must be possible to recover M, knowing E and
`K. Thus the transformations Ti in the family must have unique inverses T (cid:0)1
`i
`such that TiT (cid:0)1
`i = I, the identity transformation. Thus:
`M = T (cid:0)1
`i E:
`At any rate this inverse must exist uniquely for every E which can be ob-
`tained from an M with key i. Hence we arrive at the definition: A secrecy
`system is a family of uniquely reversible transformations Ti of a set of pos-
`sible messages into a set of cryptograms, the transformation Ti having an
`associated probability pi. Conversely any set of entities of this type will be
`called a “secrecy system”. The set of possible messages will be called, for
`convenience, the “message space” and the set of possible cryptograms the
`“cryptogram space”.
`Two secrecy systems will be the same if they consist of the same set of
`transformations Ti, with the same messages and cryptogram space (range and
`domain) and the same probabilities for the keys.
`A secrecy system can be visualized mechanically as a machine with one
`or more controls on it. A sequence of letters, the message, is fed into the in-
`put of the machine and a second series emerges at the output. The particular
`setting of the controls corresponds to the particular key being used. Some sta-
`tistical method must be prescribed for choosing the key from all the possible
`ones.
`To make the problem mathematically tractable we shall assume that the
`enemy knows the system being used. That is, he knows the family of trans-
`formations Ti, and the probabilities of choosing various keys. It might be ob-
`jected that this assumption is unrealistic, in that the cryptanalyst often does
`not know what system was used or the probabilities in question. There are
`two answers to this objection:
`
`1. The restriction is much weaker than appears at first, due to our broad
`definition of what constitutes a secrecy system. Suppose a cryptographer
`intercepts a message and does not know whether a substitution transposi-
`tion, or Vigen(cid:18)ere type cipher was used. He can consider the message as
`being enciphered by a system in which part of the key is the specification
`of which of these types was used, the next part being the particular key for
`that type. These three different possibilities are assigned probabilities ac-
`cording to his best estimates of the a priori probabilities of the encipherer
`using the respective types of cipher.
`2. The assumption is actually the one ordinary used in cryptographic studies.
`It is pessimistic and hence safe, but in the long run realistic, since one
`must expect his system to be found out eventually. Thus, even when an
`entirely new system is devised, so that the enemy cannot assign any a
`
`662
`
`7
`
`

`

`priori probability to it without discovering it himself, one must still live
`with the expectation of his eventual knowledge.
`
`The situation is similar to that occurring in the theory of games3 where it is
`assumed that the opponent “finds out” the strategy of play being used. In both
`cases the assumption serves to delineate sharply the opponent’s knowledge.
`A second possible objection to our definition of secrecy systems is that
`no account is taken of the common practice of inserting nulls in a message
`and the use of multiple substitutes. In such cases there is not a unique cryp-
`togram for a given message and key, but the encipherer can choose at will
`from among a number of different cryptograms. This situation could be han-
`dled, but would only add complexity at the present stage, without substan-
`tially altering any of the basic results.
`If the messages are produced by a Markoff process of the type described
`in (1) to represent an information source, the probabilities of various mes-
`sages are determined by the structure of the Markoff process. For the present,
`however, we wish to take a more general view of the situation and regard
`the messages as merely an abstract set of entities with associated probabil-
`ities, not necessarily composed of a sequence of letters and not necessarily
`produced by a Markoff process.
`It should be emphasized that throughout the paper a secrecy system means
`not one, but a set of many transformations. After the key is chosen only one
`of these transformations is used and one might be led from this to define a
`secrecy system as a single transformation on a language. The enemy, how-
`ever, does not know what key was chosen and the “might have been” keys
`are as important for him as the actual one. Indeed it is only the existence of
`these other possibilities that gives the system any secrecy. Since the secrecy
`is our primary interest, we are forced to the rather elaborate concept of a se-
`crecy system defined above. This type of situation, where possibilities are as
`important as actualities, occurs frequently in games of strategy. The course
`of a chess game is largely controlled by threats which are not carried out.
`Somewhat similar is the “virtual existence” of unrealized imputations in the
`theory of games.
`It may be noted that a single operation on a language forms a degener-
`ate type of secrecy system under our definition—a system with only one key
`of unit probability. Such a system has no secrecy—the cryptanalyst finds the
`message by applying the inverse of this transformation, the only one in the
`system, to the intercepted cryptogram. The decipherer and cryptanalyst in
`this case possess the same information. In general, the only difference be-
`tween the decipherer’s knowledge and the enemy cryptanalyst’s knowledge
`
`3 See von Neumann and Morgenstern “The Theory of Games”, Princeton 1947.
`
`663
`
`8
`
`

`

`is that the decipherer knows the particular key being used, while the crypt-
`analyst knows only the a priori probabilities of the various keys in the set.
`The process of deciphering is that of applying the inverse of the particular
`transformation used in enciphering to the cryptogram. The process of crypt-
`analysis is that of attempting to determine the message (or the particular key)
`given only the cryptogram and the a priori probabilities of various keys and
`messages.
`There are a number of difficult epistemological questions connected with
`the theory of secrecy, or in fact with any theory which involves questions
`of probability (particularly a priori probabilities, Bayes’ theorem, etc.) when
`applied to a physical situation. Treated abstractly, probability theory can be
`put on a rigorous logical basis with the modern measure theory approach45.
`As applied to a physical situation, however, especially when “subjective”
`probabilities and unrepeatable experiments are concerned, there are many
`questions of logical validity. For example, in the approach to secrecy made
`here, a priori probabilities of various keys and messages are assumed known
`by the enemy cryptographer—how can one determine operationally if his es-
`timates are correct, on the basis of his knowledge of the situation?
`One can construct artificial cryptographic situations of the “urn and die”
`type in which the a priori probabilities have a definite unambiguous meaning
`and the idealization used here is certainly appropriate. In other situations that
`one can imagine, for example an intercepted communication between Mar-
`tian invaders, the a priori probabilities would probably be so uncertain as to
`be devoid of significance. Most practical cryptographic situations lie some-
`where between these limits. A cryptanalyst might be willing to classify the
`possible messages into the categories “reasonable”, “possible but unlikely”
`and “unreasonable”, but feel that finer subdivision was meaningless.
`Fortunately, in practical situations, only extreme errors in a priori proba-
`bilities of keys and messages cause significant errors in the important param-
`eters. This is because of the exponential behavior of the number of messages
`and cryptograms, and the logarithmic measures employed.
`
`3 REPRESENTATION OF SYSTEMS
`A secrecy system as defined above can be represented in various ways. One
`which is convenient for illustrative purposes is a line diagram, as in Figs. 2
`and 4. The possible messages are represented by points at the left and the
`possible cryptograms by points at the right. If a certain key, say key 1, trans-
`forms message M2 into cryptogram E4 then M2 and E4 are connected by a
`
`4 See J. L. Doob, “Probability as Measure”,Annals of Math. Stat., v. 12, 1941, pp. 206–214.
`5 A. Kolmogoroff, “Grundbegriffe der Wahrscheinlichkeitsrechnung”, Ergebnisse der Mathematic, v.
`2, No. 3 (Berlin 1933).
`
`664
`
`9
`
`

`

`line labeled 1, etc. From each possible message there must be exactly one
`line emerging for each different key. If the same is true for each cryptogram,
`we will say that the system is closed.
`A more common way of describing a system is by stating the operation
`one performs on the message for an arbitrary key to obtain the cryptogram.
`Similarly, one defines implicitly the probabilities for various keys by describ-
`ing how a key is chosen or what we know of the enemy’s habits of key choice.
`The probabilities for messages are implicitly determined by stating our a pri-
`ori knowledge of the enemy’s language habits, the tactical situation (which
`will influence the probable content of the message) and any special informa-
`tion we may have regarding the cryptogram.
`1M
`
`1
`
`3
`
`2
`
`E1
`
`E2
`
`E3
`
`3
`
`1
`
`1 2
`
`2
`
`3
`
`1M
`
`2M
`
`1
`
`2
`
`2
`
`3
`
`3 1
`
`21
`
`3
`
`2M
`
`3M
`
`4M
`
`CLOSED SYSTEM
`
`NOT CLOSED
`
`Fig. 2. Line drawings for simple systems
`
`4 SOME EXAMPLES OF SECRECY SYSTEMS
`
`In this section a number of examples of ciphers will be given. These will
`often be referred to in the remainder of the paper for illustrative purposes.
`
`4.1 Simple Substitution Cipher
`In this cipher each letter of the message is replaced by a fixed substitute,
`usually also a letter. Thus the message,
`
`M = m1m2m3m4(cid:1) (cid:1) (cid:1)
`where m1; m2; (cid:1) (cid:1) (cid:1) are the successive letters becomes:
`
`E = e1e2e3e4(cid:1) (cid:1) (cid:1) = f (m1)f (m2)f (m3)f (m4)(cid:1) (cid:1) (cid:1)
`where the function f (m) is a function with an inverse. The key is a permuta-
`tion of the alphabet (when the substitutes are letters) e.g. X G U A C D T
`B F H R S L M Q V Y Z W I E J O K N P . The first letter X is the
`substitute for A, G is the substitute for B, etc.
`
`665
`
`10
`
`

`

`4.2 Transposition (Fixed Period d)
`
`The message is divided into groups of length d and a permutation applied to
`the first group, the same permutation to the second group, etc. The permuta-
`tion is the key and can be represented by a permutation of the first d integers.
`Thus for d = 5, we might have 2 3 1 5 4 as the permutation. This means that:
`
`m1 m2 m3 m4 m5 m6 m7 m8 m9 m10 (cid:1) (cid:1) (cid:1)
`
`becomes
`
`m2 m3 m1 m5 m4 m7 m8 m6 m10 m9 (cid:1) (cid:1) (cid:1):
`Sequential application of two or more transpositions will be called com-
`pound transposition. If the periods are d1; d2; (cid:1) (cid:1) (cid:1); dn it is clear that the re-
`sult is a transposition of period d, where d is the least common multiple of
`d1; d2; (cid:1) (cid:1) (cid:1); dn.
`
`4.3 Vigen(cid:18)ere, and Variations
`
`In the Vigen(cid:18)ere cipher the key consists of a series of d letters. These are writ-
`ten repeatedly below the message and the two added modulo 26 (considering
`the alphabet numbered from A = 0 to Z = 25. Thus
`
`ei = mi + ki (mod 26)
`
`where ki is of period d in the index i. For example, with the key G A H, we
`obtain
`
`message
`repeated key
`cryptogram
`
`N O W I S T H E
`G A H G A H G A
`T O D O S A N E
`
`The Vigen(cid:18)ere of period 1 is called the Caesar cipher. It is a simple substitution
`in which each letter of M is advanced a fixed amount in the alphabet. This
`amount is the key, which may be any number from 0 to 25. The so-called
`Beaufort and Variant Beaufort are similar to the Vigen(cid:18)ere, and encipher by
`the equations
`
`ei = ki (cid:0) mi (mod 26)
`ei = mi (cid:0) ki (mod 26)
`respectively. The Beaufort of period one is called the reversed Caesar cipher.
`The application of two or more Vigen(cid:18)ere in sequence will be called the
`compound Vigen(cid:18)ere. It has the equation
`
`ei = mi + ki + li + (cid:1) (cid:1) (cid:1) + si (mod 26)
`
`666
`
`11
`
`

`

`where ki; li; (cid:1) (cid:1) (cid:1); si in general have different periods. The period of their sum,
`
`ki + li + (cid:1) (cid:1) (cid:1) + si
`as in compound transposition, is the least common multiple of the individual
`periods.
`When the Vigen(cid:18)ere is used with an unlimited key, never repeating, we
`have the Vernam system6, with
`ei = mi + ki (mod 26)
`the ki being chosen at random and independently among 0; 1; (cid:1) (cid:1) (cid:1); 25. If the
`key is a meaningful text we have the “running key” cipher.
`
`4.4 Digram, Trigram, and N-gram substitution
`Rather than substitute for letters one can substitute for digrams, trigrams, etc.
`General digram substitution requires a key consisting of a permutation of the
`262 digrams. It can be represented by a table in which the row corresponds to
`the first letter of the digram and the column to the second letter, entries in the
`table being the substitutions (usually also digrams).
`
`4.5 Single Mixed Alphabet Vigen(cid:18)ere
`This is a simple substitution followed by a Vigen(cid:18)ere.
`ei = f (mi) + ki
`mi = f (cid:0)1(ei (cid:0) ki)
`The “inverse” of this system is a Vigen(cid:18)ere followed by simple substitution
`
`ei = g(mi + ki)
`mi = g(cid:0)1(ei) (cid:0) ki
`
`4.6 Matrix System
`One method of n-gram substitution is to operate on successive n-grams with
`a matrix having an inverse7. The letters are assumed numbered from 0 to 25,
`making them elements of an algebraic ring. From the n-gram m1 m2 (cid:1) (cid:1) (cid:1) mn
`of message, the matrix aij gives an n-gram of cryptogram
`
`aijmj
`
`i = 1; (cid:1) (cid:1) (cid:1); n
`
`nXj
`
`=1
`
`ei =
`
`6 G. S. Vernam, “Cipher Printing Telegraph Systems for Secret Wire and Radio Telegraphic Commu-
`nications”, Journal American Institute of Electrical Engineers, v. XLV, pp. 109–115, 1926.
`7 See L. S. Hill, “Cryptography in an Algebraic Alphabet”,American Math. Monthly, v. 36, No. 6, 1,
`1929, pp. 306–312; also “Concerning Certain Linear Transformation Apparatus of Cryptography”,
`v. 38, No. 3, 1931, pp. 135–154.
`
`667
`
`12
`
`

`

`The matrix aij is the key, and deciphering is performed with the inverse
`matrix. The inverse matrix will exist if and only if the determinant jaijj has
`an inverse element in the ring.
`
`4.7 The Playfair Cipher
`
`This is a particular type of digram substitution governed by a mixed 25 letter
`alphabet written in a 5(cid:2)5 square. (The letter J is often dropped in crypto-
`graphic work—it is very infrequent, and when it occurs can be replaced by
`I.) Suppose the key square is as shown below:
`
`L Z Q C P
`A G N O U
`R D M I F
`K Y H V S
`X B T E W
`The substitute for a digram AC, for example, is the pair of letters at the other
`corners of the rectangle defined by A and C, i.e., LO, the L taken first since
`it is above A. If the digram letters are on a horizontal line as RI, one uses
`the letters to their right DF ; RF becomes DR. If the letters are on a vertical
`line, the letters below them are used. Thus P S becomes U W . If the letters
`are the same nulls may be used to separate them or one may be omitted, etc.
`
`4.8 Multiple Mixed Alphabet Substitution
`
`In this cipher there are a set of l simple substitutions which are used in se-
`quence. If the period d is four
`m1 m2 m3 m4 m5 m6 (cid:1) (cid:1) (cid:1)
`
`becomes
`
`f1(m1) f2(m2) f3(m3) f4(m4) f1(m5) f2(m6) (cid:1) (cid:1) (cid:1)
`
`4.9 Autokey Cipher
`
`A Vigen(cid:18)ere type system in which either the message itself or the resulting
`cryptogram is used for the “key” is called an autokey cipher. The encipher-
`ment is started with a “priming key” (which is the entire key in our sense)
`and continued with the message or cryptogram displaced by the length of
`the priming key as indicated below, where the priming key is COMET. The
`message used as “key”:
`
`Message
`Key
`Cryptogram
`
`S E N D S U P P L I E S (cid:1) (cid:1) (cid:1)
`C O M E T S E N D S U P (cid:1) (cid:1) (cid:1)
`U S Z H L M T C O A Y H (cid:1) (cid:1) (cid:1)
`
`668
`
`13
`
`

`

`The cryptogram used as “key”8:
`
`Message
`Key
`Cryptogram
`
`S E N D S U P P L I E S (cid:1) (cid:1) (cid:1)
`C O M E T U S Z H L O H (cid:1) (cid:1) (cid:1)
`U S Z H L O H O S T S Z (cid:1) (cid:1) (cid:1)
`
`4.10 Fractional Ciphers
`
`In these, each letter is first enciphered into two or more letters or numbers
`and these symbols are somehow mixed (e.g., by transposition). The result
`may then be retranslated into the original alphabet. Thus, using a mixed 25-
`letter alphabet for the key, we may translate letters into two-digit quinary
`numbers by the table:
`
`4
`3
`2
`0 1
`0 L Z Q C P
`1 A G N O U
`2 R D M I F
`3 K Y H V S
`4 X B T E W
`Thus B becomes 41. After the resulting series of numbers is transposed in
`some way they are taken in pairs and translated back into letters.
`
`4.11 Codes
`
`In codes words (or sometimes syllables) are replaced by substitute letter
`groups. Sometimes a cipher of one kind or another is applied to the result.
`
`5 VALUATIONS OF SECRECY SYSTEM
`
`There are a number of different criteria that should be applied in estimating
`the value of a proposed secrecy system. The most important of these are:
`
`5.1 Amount of Secrecy
`
`There are some systems that are perfect—the enemy is no better off after
`intercepting any amount of material than before. Other systems, although
`giving him some information, do not yield a unique “solution” to intercepted
`cryptograms.