shannon1949 (776132), страница 5
Текст из файла (страница 5)
On the other hand, if theindividual Ti and Rj of two systems T and R commute, then the systemscommute.A system whose M and E spaces can identified, a very common case aswhen letter sequences are transformed into letter sequences, may be termedendomorphic. An endomorphic system T may be raised to a power T n .A secrecy system T whose product with itself is equal to T , i.e., for whichTT = Twill be called idempotent. For example, simple substitution, transposition ofperiod p, Vigenère of period p (all with each key equally likely) are idempotent.672The set of all endomorphic secrecy systems defined in a fixed messagespace constitutes an “algebraic variety”, that is, a kind of algebra, using theoperations of addition and multiplication. In fact, the properties of additionand multiplication which we have discussed may be summarized as follows:The set of endomorphic ciphers with the same message space and the twocombining operations of weighted addition and multiplication form a linearassociative algebra with a unit element, apart from the fact that the coefficients in a weighted addition must be non-negative and sum to unity.The combining operations give us ways of constructing many new typesof secrecy systems from certain ones, such as the examples given.
We mayalso use them to describe the situation facing a cryptanalyst when attemptingto solve a cryptogram of unknown type. He is, in fact, solving a secrecysystem of the typeT = p1 A + p 2 B + · · · + p r S + p0 XXp=1where the A, B, · · · , S are known types of ciphers, with the pi their a prioriprobabilities in this situation, and p0 X corresponds to the possibility of acompletely new unknown type of cipher.7P URE AND M IXED C IPHERSCertain types of ciphers such as the simple substitution, the transposition ofa given period, the Vigenère of a given period, the mixed alphabet Vigenère,etc. (all with each key equally likely) have a certain homogeneity with respect to key. Whatever the key, the enciphering, deciphering and decryptingprocesses are essentially the same.
This may be contrasted with the cipherpS + qTwhere S is a simple substitution and T a transposition of a given period. Inthis case the entire system changes for enciphering, deciphering and decryptment, depending on whether the substitution or transposition is used.The cause of the homogeneity in these systems stems from the groupproperty–we notice that, in the above examples of homogeneous ciphers, theproduct Ti Tj of any two transformations in the set is equal to a third transformation Tk in the set. On the other hand Ti Sj just does not equal any transformation in the cipherpS + qTwhich contains only substitutions and transpositions, no products.We might define a “pure” cipher, then, as one whose Ti form a group.This, however, would be too restrictive since it requires that the E space be673the same as the M space, i.e., that the system be endomorphic.
The fractionaltransposition is homogeneous as the ordinary transposition without being endomorphic. The proper definition is the following: A cipher T is pure if forevery Ti , Tj , Tk there is a Ts such thatTi Tj−1 Tk = Tsand every key is equally likely. Otherwise the cipher is mixed.
The systemsof Fig. 2 are mixed. Fig. 4 is pure if all keys are equally likely.Theorem 1. In a pure cipher the operations Ti−1 Tj which transform the message space into itself form a group whose order is m, the number of differentkeys.ForTj−1 Tk Tk−1 Tj = Iso that each element has an inverse. The associative law is true since theseare operations, and the group property follows fromTi−1 Tj Tk−1 Tl = Ts−1 Tk Tk−1 Tl = Ts−1 Tlusing our assumption that Ti−1 Tj = Ts−1 Tk for some s.The operation Ti−1 Tj means, of course, enciphering the message with keyj and then deciphering with key i which brings us back to the message space.If T is endomorphic, i.e., the Ti themselves transform the space ΩM intoitself (as is the case with most ciphers, where both the message space and thecryptogram space consist of sequences of letters), and the Ti are a group andequally likely, then T is pure, sinceTi Tj−1 Tk = Ti Tr = Ts .Theorem 2.
The product of two pure ciphers which commute is pure.For if T and R commute Ti Rj = Rl Tm for every i, j with suitable l, m, andTi Rj (Tk Rl )−1 Tm Rn = Ti Rj Rl−1 Tk−1 Tm Rn= Ru Rv−1 Rw Tr Ts−1 Tl= R h Tg .The commutation condition is not necessary, however, for the product to bea pure cipher.A system with only one key, i.e., a single definite operation T1 , is puresince the only choice of indices isT1 T1−1 T1 = T1 .Thus the expansion of a general cipher into a sum of such simple transformations also exhibits it as a sum of pure ciphers.An examination of the example of a pure cipher shown in Fig.
4 discloses674certain properties. The messages fall into certain subsets which we will callresidue classes, and the possible cryptograms are divided into correspondingresidue classes. There is at least one line from each message in a class to eachcryptogram in the corresponding class, and no line between classes whichdo not correspond. The number of messages in a class is a divisor of thetotal number of keys. The number of lines “in parallel” from a message Mto a cryptogram in the corresponding class is equal to the number of keysdivided by the number of messages in the class containing the message (orcryptogram). It is shown in the appendix that these hold in general for pureciphers. Summarized formally, we have:CRYPTOGRAMRESIDUECLASSESMESSAGERESIDUECLASSESC14M23M3M4M5C2M6C31M1M7E1234E212413C’1E32342E4114423E532E6C’21124E73PUREC’3SYSTEMFig.
4. Pure systemTheorem 3. In a pure system the messages can be divided into a set of“residue classes” C1 , C2 , · · ·, Cs and the cryptograms into a correspondingset of residue classes C10 , C20 , · · ·, Cs0 with the following properties:(1) The message residue classes are m dually exclusive and collectively contain all possible messages. Similarly for the cryptogram residue classes.(2) Enciphering any message in Ci with any key produces a cryptogram inCi0 .
Deciphering any cryptogram in Ci0 with any key leads to a message inCi .(3) The number of messages in Ci , say ϕi , is equal to the number of cryptograms in Ci0 and is a divisor of k the number of keys.675(4) Each message in Ci can be enciphered into each cryptogram in Ci0 byexactly ϕki different keys. Similarly for decipherment.The importance of the concept of a pure cipher (and the reason for thename) lies in the fact that in a pure cipher all keys are essentially the same.Whatever key is used for a particular message, the a posteriori probabilitiesof all messages are identical.
To see this, note that two different keys applied to the same message lead to two cryptograms in the same residue class,say Ci0 . The two cryptograms therefore could each be deciphered by ϕki keysinto each message in Ci and into no other possible messages. All keys beingequally likely the a posteriori probabilities of various messages are thusPE (M ) =P (M )P (M )PM (E)P (M )PM (E)==PP (E)P (Ci )M P (M )PM (E)where M is in Ci , E is in Ci0 and the sum is over all messages in Ci . If Eand M are not in corresponding residue classes, PE (M ) = 0. Similarly it canbe shown that the a posteriori probabilities of the different keys are the samein value but these values are associated with different keys when a differentkey is used. The same set of values of PE (K) have undergone a permutationamong the keys.
Thus we have the resultTheorem 4. In a pure system the a posteriori probabilities of various messages PE (M ) are independent of the key that is chosen. The a posteriori probabilities of the keys PE (K) are the same in value but undergo a permutationwith a different key choice.Roughly we may say that any key choice leads to the same cryptanalyticproblem in a pure cipher.
Since the different keys all result in cryptogramsin the same residue class this means that all cryptograms in the same residueclass are cryptanalytically equivalent–they lead to the same a posteriori probabilities of messages and, apart from a permutation, the same probabilities ofkeys.As an example of this, simple substitution with all keys equally likely is apure cipher. The residue class corresponding to a given cryptogram E is theset of all cryptograms that may be obtained from E by operations T i Tk−1 E.
Inthis case Ti Tk−1 is itself a substitution and hence any substitution on E givesanother member of the same residue class. Thus, if the cryptogram isE = X C P P G C F Q,thenE1 = R D H H G D S NE2 = A B C C D B E F676etc. are in the same residue class. It is obvious in this case that these cryptograms are essentially equivalent. All that is of importance in a simple substitution with random key is the pattern of letter repetitions the actual lettersbeing dummy variables.
Indeed we might dispense with them entirely, indicating the pattern of repetitions in E as follows:z}|z }| {{This notation describes the residue class but eliminates all information as tothe specific member of the class. Thus it leaves precisely that informationwhich is cryptanalytically pertinent. This is related to one method of attacking simple substitution ciphers—the method of pattern words.In the Caesar type cipher only the first differences mod 26 of the cryptogram are significant. Two cryptograms with the same δei are in the sameresidue class.
One breaks this cipher by the simple process of writing downthe 26 members of the message residue class and picking out the one whichmakes sense.The Vigenère of period d with random key is another example of a purecipher. Here the message residue class consists of all sequences with the samefirst differences as the cryptogram, for letters separated by distance d. Ford = 3 the residue class is defined bym1 — m 4m2 — m 5m3 — m 6m4 — m 7====...c1 — c4c2 — c5c3 — c6c4 — c7where E = e1 , e2 , · · · is the cryptogram and m1 , m2 , · · · is any M in thecorresponding residue class.In the transposition cipher of period d with random key, the residue classconsists of all arrangements of the ei in which no ei is moved out of its blockof length d, and any two ei at a distance d remain at this distance. This is usedin breaking these ciphers as follows: The cryptogram is written in successiveblocks of length d, one under another as below (d = 5):e1 e2 e3 e4 e5e6 e7 e8 e9 e10e11 e12 .
. .. . . . .677The columns are then cut apart and rearranged to make meaningful text.When the columns are cut apart, the only information remaining is the residueclass of the cryptogram.Theorem 5. If T is pure then Ti Tj−1 T = T where Ti Tj are any two transformations of T . Conversely if this is true for any Ti Tj in a system T then T ispure.The first part of this theorem is obvious from the definition of a pure system.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
