11/5/2020
`
`Communication theory of secrecy systems - Nokia Bell Labs Journals & Magazine
`
`Communication theory of secrecy systems
`
`II
`
`ieeexplore.ieee.org/document/6769090
`
`Abstract:
`THE problems of cryptography and secrecy systems furnish an interesting application of communication theory.
`1
` In this paper a theory of secrecy systems is developed. The approach is on a theoretical level and is intended to
`2
`complement the treatment found in standard works on cryptography. 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.
`
`Published in: The Bell System Technical Journal ( Volume: 28, Issue: 4, Oct. 1949)
`Page(s): 656 - 715
`
`Date of Publication: Oct. 1949
`Print ISSN: 0005-8580
`
`DOI: 10.1002/j.1538-7305.1949.tb00928.x
`Publisher: Nokia Bell Labs
`
`Authors
`
`Citations
`
`Metrics
`
`References
`
`References is not available for this document.
`
`https://ieeexplore.ieee.org/document/6769090
`
`1/1
`
`Oracle-1026 p. 1
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`Communication Theory of Secrecy Systems*
`
`By C. E. SHANNON
`
`1. INTRODUCTION AND SUMMARY
`
`T HE problems of cryptography and secrecy systems furnish an interest(cid:173)
`
`ing application of communication theory. 1 In this paper a theory of
`secrecy systems is developed. The approach is on a theoretical level and is
`intended to complement the treatment found in standard works on cryp(cid:173)
`tography.2 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 con(cid:173)
`cerned 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 cover(cid:173)
`ing cryptogram, or other methods in which the existence of the message is
`concealed from the enemy; (2) privacy systems, for example speech inver(cid:173)
`sion, 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
`assumed to have any special equipment necessary to intercept and record
`the transmitted signal. \Ve consider only the third type-concealment
`systems 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(cid:173)
`bols, each chosen from a finite set. These symbols may be letters in a lan(cid:173)
`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
`* The material in this paper appeared originally in a confidential report "A Mathe(cid:173)
`matical Theory of Cryptography" dated Sept. 1, 1945, which has now been declassified.
`1 Shannon, C. E., "A Mathematical Theory of Communication," Bell System Technical
`Joumal, July 1948, p. 379; Oct. 1948, p. 623.
`2 See, for example, H. F. Gaines, "Elementary Cryptanalysis," or M. Giviergc, "Cours
`de Cryptographic."
`
`656
`
`Oracle-1026 p. 2
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`CO.llMl'NlCATION THEORY OF SECRECI' SYSTEMS
`
`657
`
`be represented by a stochastic process which produces a discrete sequence of
`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 struc(cid:173)
`ture 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
`enciphering with a particular key. The transformations are supposed rever(cid:173)
`sible (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 prob(cid:173)
`abilities for the various keys and messages are actually the enemy crypt(cid:173)
`analyst'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
`forming the system. Then a message is selected and the particular trans(cid:173)
`formation corresponding to the selected key applied to this message to
`produce a cryptogram. 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 posteriori probabilities of the various possible messages and keys which
`might have produced this cryptogram. This set of a posteriori probabilities
`constitutes his knowledge of the key and message after the interception.
`"Knowledge" is thus identified with a set of propositions having associated
`probabilities. The calculation of the a posteriori probabilities is the gen(cid:173)
`eralized problem of cryptanalysis.
`As an example of these notions, in a simple substitution cipher with ran(cid:173)
`dom key there are 26! transformations, corresponding to the 26! ways we
`*The word "enemy," stemming from military applications, is commonly used in cryp(cid:173)
`tographic work to denote anyone who may intercept a cryptogram.
`
`Oracle-1026 p. 3
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`658
`
`BELL SYSTEM TECHNICAL JOURNAL
`
`can substitute for 26 different letters. These are all equally likely and each
`therefore has an a priori probability i/26!. If this is applied to "normal
`English" 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 various messages of N letters are merely their relative
`frequencies in normal English text.
`If the enemy intercepts N letters of cryptogram in this system his prob(cid:173)
`abilities change. If N is large enough (say SO 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
`messages and keys of comp:i.rable 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 cor(cid:173)
`responds 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=l
`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
`algebraic 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 T.-, Th T 1,
`in the set the product
`
`T;Tj-1Tk
`
`is also a transformation in the set. That is enciphering, deciphering, and
`enciphering with any three keys must be equivalent to enciphering with
`some key.
`
`Oracle-1026 p. 4
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`COMMUNICATION THEORY OF SECRECY SYSTEMS
`
`659
`
`With a pure cipher it is shown that all keys are essentially equivalent(cid:173)
`they all lead to the same set of a posteriori probabilities. Furthermore, when
`a given cryptogram is intercepted there is a set of messages that might have
`produced this cryptogram (a "residue class") and the a posteriori prob(cid:173)
`abilities of messages 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
`systems, including simple substitution with random key. In this case the
`residue class consists of all messages with the same pattern of letter repeti(cid:173)
`tions 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-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 crypt analytically the same.
`The second part of the paper deals with the problem of ''theoretical
`secrecy." How secure is a system against cryptanalysis when the enemy has
`unlimited time and manpower available for the analysis of intercepted
`cryptograms? The problem is closely related to questions of communication
`in the presence of noise, and the concepts of entropy and equivocation
`developed 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 crypto(cid:173)
`gram is intercepted by the enemy the a posteriori probabilities of this crypto(cid:173)
`gram representing various messages be identically the same as the a priori
`probabilities of the same messages before the interception. It is shown that
`perfect secrecy is possible but requires, if the number of messages is finite,
`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
`certain 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
`others are practically zero. A quantity IJ(N) is defined, called the equivoca(cid:173)
`tion, 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
`original message after intercepting a cryptogram of N letters. Various
`properties of the equivocation are deduced-for example, the equivocation
`
`Oracle-1026 p. 5
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`660
`
`BELL SYSTEJf TECHNICAL JOURNAL
`
`of the key never increases with increasing N. This equivocation is a theo(cid:173)
`retical secrecy 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 random
`cipher is determined. \Yith certain modifications this function can be applied
`to many cases of practical interest. This gives a way of calculating approxi(cid:173)
`mately 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(cid:173)
`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 log10 26! or about 20 andD (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
`oo.
`"languages" in which the equivocation does not approach zero as N -
`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 alter(cid:173)
`natives, all of reasonable probability. Such systems we call ideal systems.
`It is possible in any language to approximate such behavior-Le., 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 sensi(cid:173)
`tivity 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 sec(cid:173)
`recy systems is made. This leads to methods for constructing systems which
`will require a large amount of work to solve. Finally, a certain incompat(cid:173)
`ibility 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 neces(cid:173)
`sary 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
`
`Oracle-1026 p. 6
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`COMMUNICATION THEORY OF SECRECJ' Sl"STEMS
`
`661
`
`end there are 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 example 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 inter(cid:173)
`ccptible 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
`
`ME$AGE
`M
`
`l:NC1Pt£RER
`
`TK
`
`CRYPTOGRAM
`E
`
`DECIPHERER
`T-1
`K
`
`MESSAGE
`M
`
`E
`
`Kl:Y
`K
`
`'
`
`KEY
`SOURCE
`
`KEY
`
`I\
`
`Fig. 1 ~Schematic of a geueral secrecy system.
`
`Evidently the encipherer performs a functional operation. If M is the
`message, K the key, and Ethe enciphered message, or cryptogram, we have
`
`E = J(M, K)
`
`that is Eis a function of.Mand K. It is preferable to think of this, however,
`not as a function of two variables but as a (one parameter) family of opera(cid:173)
`tions or transformations, and to write it
`
`E = T;M.
`
`The transformation T; applied to message M produces cryptogram E. The
`index i corresponds to the particular key being used.
`\Ve 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
`• • • , T,,, with the respective probabilities p1 ,
`of transformations T1 , T2 ,
`P2 , · · ·, Pm . Similarly we will generally assume a finite number of possible
`messages lrf1 , M2 , · · ·, M,. with associated a priori probabilities q1 , q2 ,
`· · ·, q,. . The possible messages, for example, might be the possible sequences
`of English letters all of length N, and the associated probabilities are then
`
`Oracle-1026 p. 7
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`662
`
`BELL SYSTEM TECHNICAL JOURNAL
`
`the relative frequencies of occurrence of these sequences in normal English
`text.
`At the receiving end it must be possible to recover M, knowing E and K.
`Thus the transformations T; in the family must have unique mverses
`171 such that T;T; 1 = I, the identity transformation. Thus:
`M = T; 1E.
`At any rate this inverse must exist uniquely for every E which can be
`obtained from an M with key i. Hence we arrive at the definition: A secrecy
`system is a family of uniquely reversible transformations T; of a set of
`possible mssages into a set of cryptograms, the transformation T, having
`an associated prob1bility p,. 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 T,, with the same message 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 mess1ge, is fed into the
`input of the m1chine and a second series emerges at the output. The par(cid:173)
`ticular setting of the controls corresponds to the p1rticular key being used.
`Some statistical 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(cid:173)
`formations Ti, and the probibilities of choosing various keys. It might be
`objected that this assumption is unrealistic, in that the cryptanalyst often
`does not know what system was used or the probJ.bilities 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 cryptog(cid:173)
`rapher intercepts a message and does not know whether a substitution,
`transposition, or Vigenere 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 according 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 ordinarily 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,
`
`Oracle-1026 p. 8
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`COMMUNICATION THEOR!' OF SECRECY SYSTEMS
`
`663
`
`even when an entirely new system is devised, so that the enemy cannot
`assign any a 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 crypto(cid:173)
`gram for a given message and key, but the encipherer can choose at will
`from among a number of different cryptograms. This situation could be
`handled, but would only add complexity at the present stage, without sub(cid:173)
`stantially 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(cid:173)
`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 prob(cid:173)
`abilities, not necessarily composed of a sequence of letters and not neces(cid:173)
`sarily 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, however, 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 elabor(cid:173)
`ate concept of a secrecy 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 110/ 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 degenerate
`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(cid:173)
`tween the decipherer's knowledge and the enemy cryptanalyst's knowledge
`3 See von Neumann and Morgenstern "The Theory of Games," Princeton 1947,
`
`Oracle-1026 p. 9
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`664
`
`BELL SYSTEM TECHNICAL JOURNAL
`
`is that the decipherer knows the particular key being used, while the crypt(cid:173)
`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(cid:173)
`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 ap(cid:173)
`proach.4·5 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 estimates 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
`Martian invaders, the a priori probabilities would probably be so uncertain
`as to be devoid of significance. Most practical cryptographic situations lie
`somewhere between these limits. A cryptanalyst might be willing to classify
`the possible messages into the categories "reasonable," "possible but un(cid:173)
`likely" and "unreasonable," but feel that finer subdivision was meaningless.
`Fortunately, in practical situations, only extreme errors in a priori prob(cid:173)
`abilities of keys and messages cause significant errors in the important
`parameters. 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, transforms message M, into cryptogram E4 then M 2 and E4 are connected
`4 See J. L. Doob, "Probability as Measure," Annals of Mat/1. Stat., v. 12, 1941, pp.
`206-214.
`6 A. Kolmogoroff, "Grundbegriffe der Wahrscheinlichkeits rechnung," Ergebnisse der
`Mathematic, v. 2, No. 3 (Berlin 1933).
`
`Oracle-1026 p. 10
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`COMMUNICATION THEORY OF SECRECY SYSTEMS
`
`665
`
`by a 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 dosed.
`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 de(cid:173)
`scribing 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 priori knowledge of the enemy's language habits, the tactical situation
`(which will influence the probable content of the message) and any special
`information we may have regarding the cryptogram.
`
`Mz
`
`M3
`
`M1
`
`Mz
`
`E,
`
`Ez
`
`E3
`
`NOT CLOSED
`CLOSED SYSTEM
`Fig. 2-Line drawings for simple systems.
`
`4. Sm.m 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.
`
`1. Si111plc Substitution Cipher.
`In this cipher each letter of the message is replaced by a fixed substitute,
`usually also a letter. Thus the message,
`
`where 11ii, m2 ,
`
`· • · are the successive letters becomes:
`
`E = e1e2eae4 · • ·
`= f(1111)f(1112)J(ma)f(m4) · · ·
`
`where the functionf(m) is a function with an inverse. The key is a permuta(cid:173)
`tion of the alphabet (when the substitutes are letters) e.g. X G U A CD
`T B F II R S L M Q V Y Z H' I E J O K N P. The first letter X is the
`substitute for A, G is the substitute for B, etc.
`
`Oracle-1026 p. 11
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`666
`
`BELL SYSTEM TECHNICAL JOURNAL
`
`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 per(cid:173)
`mutation is the key and can be represented by a permutation of the first d
`integers. Thus, for d = S, we might have 2 3 1 S 4 as the permutation.
`This means that:
`
`m1 m2 ma m4 m6 m6 m1 ms m9 mm · · · becomes
`mi m3 m1 m6 m4 m1 ms m6 m10 mo · · · .
`Sequential application of two or more transpositions will be called compound
`transposition. If the periods are d1 , d2 , · · ·, d, it is dear that the result is
`a transposition of period d, where d is the least common multiple of d1 ,
`<h ' ... ' d, .
`
`3. V igenere, and Variations.
`In the Vigenere cipher the key consists of a series of d letters. These are
`written repeatedly below the message and the two added modulo 26 (con(cid:173)
`sidering the alphabet numbered from A = 0 to Z = 25. Thus
`e, = m; + k; (mod 26)
`where k; is of period d in the index i. For example, with the key G A H,
`we obtain
`
`message
`repeated key
`cryptogram
`
`NOWISTHE···
`GAHGAHGA···
`TODOSANE···
`
`The Vigenere of period 1 is called the Caesar cipher. It is a simple substi(cid:173)
`tution in which each letter of Mis advanced a fixed amount in the alphabet.
`This amount is the key, which may be any number from O to 25. The so(cid:173)
`called Beaufort and Variant Beaufort are similar to the Vigenere, and en(cid:173)
`cipher by the equations
`
`e, = k,- m; (mod 26)
`
`and
`
`k; (mod 26)
`
`e; = m, -
`respectively. The Beaufort of period one is called the reversed Caesar
`cipher.
`The application of two or more Vigeneres in sequence will be called the
`compound Vigenere. It has the equation
`ei = mi + k; + l; + • • · + Si (mod 26)
`
`Oracle-1026 p. 12
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`COMMUNICATION THEORY OF SECRECY SYSTEMS
`
`667
`
`where k; , I; , · · ·, s; in general have different periods. The period of their
`sum,
`
`k, + l; + · · · + s,
`as in compound transposition, is the least common multiple of the individual
`periods.
`When the Vigenere is used with an unlimited key, never repeating, we
`have the Vernam system,6 with
`e; = m; + k; (mod 26)
`the k, being chosen at random and independently among 0, 1, · · ·, 25. If
`the key is a meaningful text we have the "running key" cipher.
`
`4. Digram, Trigram, and N-gram substihition.
`Rather than substitute for letters one can substitute for digrams, tri(cid:173)
`grams, etc. General digram substitution requires a key consisting of a per(cid:173)
`mutation 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 substitutes (usually also digrams).
`
`5. Single Mixed Alphabet Vigenere.
`This is a simple substitution followed by a Vigenere.
`e; = f(m,) + k,
`m, = J-1(e; - k,)
`
`The "inverse" of this system is a Vigenere followed by simple substitution
`e; = g(m; + k,)
`m; = g-1(e;) -
`k;
`
`6. Matrix Syslem. 1
`One method of n-gram substitution is to operate on successive n-grams
`with a matrix having an inverse. The letters are assumed numbered from
`Oto 25, making them elements of an algebraic ring. From then-gram m 1 m~
`• • • mn of message, the matrix a,; gives an n-gram of cryptogram
`
`"
`e; = La;; m;
`i-1
`
`i = 1, • • • , n
`
`a G. S. Vernam, "Cipher Printing Telegraph Systems for Secret Wire and Radio Tele(cid:173)
`graphic Communications," Journal American Institute of Electrical Engineers, v. XLV,
`pp. 109-115, 1926.
`7 See L. S. Hill, "Cryptography in an Algebraic Alphabet," American Math. Monlldy,
`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.
`
`Oracle-1026 p. 13
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`668
`
`BELL SYSTEM TECHNICAL JOURNAL
`
`The matrix ai; is the key, and deciphering is performed with the inverse
`matrix. The inverse matrix will exist if and only if the determinant I a;; I
`has an inverse element in the ring.
`
`7. The Play/air Cipher.
`This is a particular type of digram substitution governed by a mixed 25
`letter alphabet written in a S x S square. (The letter J is often dropped in
`cryptographic work-it is very infrequent, and when it occurs can be re(cid:173)
`placed by I.) Suppose the key square is as shown below:
`
`LZQCP
`A·:G NO U
`RD MI F
`KYHVS
`XBTETV
`
`The substitute for a digram AC, for example, is the pair of letters at the
`other corners