shannon1949 (776132), страница 13
Текст из файла (страница 13)
From a consideration of this methodwe can frame a test of ciphers which might be called the acid test. It appliesonly to ciphers with a small key (less than, say, 50 decimal digits), appliedto natural languages, and not using the ideal method of gaining secrecy. Theacid test is this: How difficult is it to determine the key or a part of the keyknowing a small sample of message and corresponding cryptogram? Anysystem in which this is easy cannot be very resistant, for the cryptanalyst canalways make use of probable words, combined with trial and error, until aconsistent solution is obtained.The conditions on the size of the key make the amount of trial and errorsmall, and the condition about ideal systems is necessary, since these automatically give consistency checks.
The existence of probable words andphrases is implied by the assumption of natural languages.Note that the requirement of difficult solution under these conditions isnot, by itself, contradictory to the requirements that enciphering and deciphering be simple processes. Using functional notation we have for encipheringE = f (K, M )and for decipheringM = g(K, E)710Both of these may be simple operations on their arguments without the thirdequationK = h(M, E)being simple.We may also point out that in investigating a new type of ciphering system one of the best methods of attack is to consider how the key could bedetermined if a sufficient amount of M and E were given.The principle of confusion can be (and must be) used to create difficultiesfor the cryptanalyst using probable word techniques.
Given (or assuming)M = m1 , m2 , · · · , ms and E = e1 , e2 , · · · , es , the cryptanalyst can set upequations for the different key elements k1 , k2 , · · · , kr (namely the enciphering equations).e1 = f1 (m1 , m2 , · · · , ms ; k1 , · · · , kr )e1 = f2 (m1 , m2 , · · · , ms ; k1 , · · · , kr )....e1 = fs (m1 , m2 , · · · , ms ; k1 , · · · , kr )All is known, we assume, except the ki .
Each of these equations should therefore be complex in the ki , and involve many of them. Otherwise the enemycan solve the simple ones and then the more complex ones by substitution.From the point of view of increasing confusion, it is desirable to havethe fi involve several mi , especially if these are not adjacent and hence lesscorrelated. This introduces the undesirable feature of error propagation, however, for then each ei will generally affect several mi in deciphering, and anerror will spread to all these.We conclude that much of the key should be used in an involved mannerin obtaining any cryptogram letter from the message to keep the work characteristic high.
Further a dependence on several uncorrelated m i is desirable,if some propagation of error can be tolerated. We are led by all three of thearguments of these sections to consider “mixing transformations”.25M IXING T RANSFORMATIONSA notion that has proved valuable in certain branches of probability theoryis the concept of a mixing transformation. Suppose we have a probability ormeasure space Ω and a measure preserving transformation F of the spaceinto itself, that is, a transformation such that the measure of a transformed711region F R is equal to the measure of the initial region R. The transformationis called mixing if for any function defined over the space and any regionR the integral of the function over the region R n R approaches, as n→∞,the integral of the function over the entire space Ω multiplied by the volumeof R.
This means that any initial region R is mixed with uniform densitythroughout the entire space if F is applied a large number of times. In general,F n R becomes a region consisting of a large number of thin filaments spreadthroughout Ω. As n increases the filaments become finer and their densitymore constant.A mixing transformation in this precise sense can occur only in a spacewith an infinite number of points, for in a finite point space the transformation must be periodic. Speaking loosely, however, we can think of a mixingtransformation as one which distributes any reasonably cohesive region inthe space fairly uniformly over the entire space.
If the first region could bedescribed in simple terms, the second would require very complex ones.In cryptography we can think of all the possible messages of length N asthe space Ω and the high probability messages as the region R. This lattergroup has a certain fairly simple statistical structure. If a mixing transformation were applied, the high probability messages would be scattered evenlythroughout the space.Good mixing transformations are often formed by repeated products oftwo simple non-commuting operations.
Hopf13 has shown, for example, thatpastry dough can be mixed by such a sequence of operations. The dough isfirst rolled out into a thin slab, then folded over, then rolled, and the foldedagain, etc.In a good mixing transformation of a space with natural coordinatesX1 , X2 , · · · , XS the point Xi is carried by the transformation into a point Xi0 ,withXi0 = f1 (X1 , X2 , · · · , XS ) i = 1, 2, · · · , Sand the functions fi are complicated, involving all the variables in a “sensitive” way.
A small variation of any one, X3 , say, changes all the Xi0 considerably. If Xi passes through its range of possible variation the point Xi0 tracesa long winding path around the space.Various methods of mixing applicable to statistical sequences of the typefound in natural languages can be devised. One which looks fairly good is tofollow a preliminary transposition by a sequence of alternating substitutionsand simple linear operations, adding adjacent letters mod 26 for example.Thus we might take13E.
Hopf, “On Causality, Statistics and Probability,” Journal of Math. and Physics, v. 13, pp. 51-102,1934.712F = LSLSLTwhere T is a transposition, L is a linear operation, and S is a substitution.26C IPHERS OF THE T YPE Tk F SjSuppose that F is a good mixing transformation that can be applied to sequences of letters, and that Tk and Sj are any two simple families of transformations, i.e., two simple ciphers, which may be the same.
For concretenesswe may think of them as both simple substitutions.It appears that the cipher T F S will be a very good secrecy system fromthe standpoint of its work characteristic. In the first place it is clear on reviewing our arguments about statistical methods that no simple statistics will giveinformation about the key—any significant statistic derived from E must beof a highly involved and very sensitive type—the redundancy has been bothdiffused and confused by the mixing transformation F .
Also probable wordslead to a complex system of equations involving all parts of the key (whenthe mix is good), which must be solved simultaneously.It is interesting to note that if the cipher T is omitted the remaining system is similar to S and thus no stronger. The enemy merely “unmixes” thecryptogram by application of F −1 and then solves.
If S is omitted the remaining system is much stronger than T alone when the mix is good, but still notcomparable to T F S.The basic principle here of simple ciphers separated by a mixing transformation can of course be extended. For example one could useTk F 1 S j F 2 R iwith two mixes and three simple ciphers.
One can also simplify by using thesame ciphers, and even the same keys as well as the same mixing transformations. This might well simplify the mechanization of such systems.The mixing transformation which separates the two (or more) appearances of the key acts as a kind of barrier for the enemy—it is easy to carry aknown element over this barrier but an unknown (the key) does not go easily.By supplying two sets of unknowns, the key for S and the key for T , andseparating them by the mixing transformation F we have “entangled” theunknowns together in a way that makes solution very difficult.Although systems constructed on this principle would be extremely safethey possess one grave disadvantage.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
