shannon1949 (776132), страница 12
Текст из файла (страница 12)
In determining a single letter the key space is reduced by 1.4decimal digits from the original 26. The same effect is seen in all the elementary types of ciphers. In the Vigenère, the assumption of two or three lettersof the key is easily checked by deciphering at other points with this fragmentand nothing whether clear emerges. The compound Vigenère is much betterfrom this point of view, if we assume a fairly large number of component periods, producing a repetition rate larger than will be intercepted. In this caseas many key letters are used in enciphering each letter as there are periods.Although this is only a fraction of the entire key, at least a fair number ofletters must be assumed before a consistency check can be applied.Our first conclusion then, regarding practical small key cipher design, isthat a considerable amount of key should be used in enciphering each smallelement of the message.23S TATISTICAL M ETHODSIt is possible to solve many kinds of ciphers by statistical analysis.
Consideragain simple substitution. The first thing a cryptanalyst does with an intercepted cryptogram is to make a frequency count. If the cryptogram contains,say, 200 letters it is safe to assume that few, if any, of the letters are out oftheir frequency groups, this being a division into 4 sets of well defined frequency limits. The logarithm of the number of keys within this limitationmay be calculated aslog 2!9!9!6! = 14.28and the simple frequency count thus reduces the key uncertainty by 12 decimal digits, a tremendous gain.In general, a statistical attack proceeds as follows: A certain statistic ismeasured on the intercepted cryptogram E. This statistic is such that for allreasonable message M it assumes about the same value, SK , the value depending only on the particular key K that was used.
The value thus obtained707serves to limit the possible keys to those which would give values of S in theneighborhood of that observed. A statistic which does not depend on K orwhich varies as much with M as with K is not of value in limiting K. Thus,in transposition ciphers, the frequency count of letters gives no informationabout K—every K leaves this statistic the same. Hence one can make no useof a frequency count in breaking transposition ciphers.More precisely one can ascribe a “solving power” to a given statistic S.For each value if S there will be a conditional equivocation of the key H S (K),the equivocation when S has its particular value, and that is all that is knownconcerning the key.
The weighted mean of these valuesXP (S) HS (K)gives the mean equivocation of the key when S is known, P (S) being thea priori probability of the particular value S. The key size H(K), less thismean equivocation, measures the “solving power” of the statistic S.In a strongly ideal cipher all statistics of the cryptogram are independentof the particular key used. This is the measure preserving property of T j Tk−1on the E space or Tj−1 Tk on the M space mentioned above.There are good and poor statistics, just as there are good and poor methods of trial and error. Indeed the trial and error testing of an hypothesis isa type of statistic, and what was said above regarding the best types of trialsholds generally. A good statistic for solving a system must have the followingproperties:1.
It must be simple to measure.2. It must depend more on the key than on the message if it is meant to solvefor the key. The variation with M should not mask its variation with K.3. The values of the statistic that can be “resolved” in spite of the “fuzziness”produced by variation in M should divide the key space into a number ofsubsets of comparable probability, with the statistic specifying the one inwhich the correct key lies. The statistic should give us sizeable information about the key, not a tiny fraction of a bit.4. The information it gives must be simple and usable. Thus the subsets inwhich the statistic locates the key must be of a simple nature in the keyspace.Frequency count for simple substitution is an example of a very goodstatistic.Two methods (other than recourse to ideal systems) suggest themselvesfor frustrating a statistical analysis.
These we may call the methods of diffusion and confusion. In the method of diffusion the statistical structure of Mwhich leads to its redundancy is “dissipated” into long range statistics—i.e.,708into statistical structure involving long combinations of letters in the cryptogram. The effect here is that the enemy must intercept a tremendous amountof material to tie down this structure, since the structure is evident onlyin blocks of very small individual probability. Furthermore, even when hehas sufficient material, the analytical work required is much greater sincethe redundancy has been diffused over a large number of individual statistics.
An example of diffusion of statistics is operating on a message M =m1 , m2 , m3 , · · · with an “averaging” operation, e.g.,yn =sXmn+i (mod 26),i=1adding s successive letters of the message to get a letter yn . One can showthat the redundancy of the y sequence is the same as that of the m sequence,but the structure has been dissipated. Thus the letter frequencies in y willbe more nearly equal than in m, the digram frequencies also more nearlyequal, etc.
Indeed any reversible operation which produces one letter out foreach letter in and does not have an infinite “memory” has an output with thesame redundancy as the input. The statistics can never be eliminated withoutcompression, but they can be spread out.The method of confusion is to make the relation between the simple statistics of E and the simple description of K a very complex and involved one.In the case of simple substitution, it is easy to describe the limitation of Kimposed by the letter frequencies of E. If the connection is very involved andconfused the enemy may still be able to evaluate a statistic S1 , say, whichlimits the key to a region of the key space. This limitation, however, is tosome complex region R in the space, perhaps “folded ever” many times, andhe has a difficult time making use of it.
A second statistic S2 limits K stillfurther to R2 , hence it lies in the intersection region; but this does not helpmuch because it is so difficult to determine just what the intersection is.To be more precise let us suppose the key space has certain “natural coordinates” k1 , k2 , · · · , kp which he wishes to determine. He measures, let ussay, a set of statistics s1 , s2 , · · · , sn and these are sufficient to determine theki .
However, in the method of confusion, the equations connecting these setsof variable are involved and complex. We have, say,f1 (k1 , k2 , · · · , kp ) = s1f2 (k1 , k2 , · · · , kp ) = s2...fn (k1 , k2 , · · · , kp ) = sn ,709and all the fi involve all the ki . The cryptographer must solve this systemsimultaneously—a difficult job. In the simple (not confused) cases the functions involve only a small number of the ki —or at least some of these do. Onefirst solves the simpler equations, evaluating some of the ki and substitutesthese in the more complicated equations.The confusion here is that for a good ciphering system steps should betaken either to diffuse or confuse the redundancy (or both).24T HE P ROBABLE W ORLD M ETHODOne of the most powerful tools for breaking ciphers is the use of probablewords.
The probable words may be words or phrases expected in the particular message due to its source, or they may merely be common words orsyllables which occur in any text in the language, such as the, and, tion, that,and the like in English.In general, the probable word method is used as follows: Assuming aprobable word to be at some point in the clear, the key or a part of the key isdetermined. This is used to decipher other parts of the cryptogram and provide a consistency test. If the other parts come out in the clear, the assumptionis justified.There are few of the classical type ciphers that use a small key and can resist long under a probable word analysis.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
