shannon1949 (776132), страница 11
Текст из файла (страница 11)
12 can be expected with any typeof secrecy system where the equivocation approaches zero. The scale of manhours required, however, will differ greatly with different types of ciphers,even when the HE (M ) curves are about the same. A Vigenère or compoundVigenère, for example, with the same key size would have a much better (i.e.,703much higher) work characteristic. A good practical secrecy system is one inwhich the W (N ) curve remains sufficiently high, out to the number of lettersone expects to transmit with the key, to prevent the enemy from actuallycarrying out the solution, or to delay it to such an extent that the informationis then obsolete.We will consider in the following sections ways of keeping the functionW (N ) large, even though HE (K) may be practically zero.
This is essentiallya “max min” type of problem as is always the case when we have a battle ofwits.12 In designing a good cipher we must maximize the minimum amount ofwork the enemy must do to break it. It is not enough merely to be sure none ofthe standard methods of cryptanalysis work—we must be sure that no methodwhatever will break the system easily. This, in fact, has been the weakness ofmany systems; designed to resist all the known methods of solution they latergive rise to new cryptanalytic techniques which rendered them vulnerable toanalysis.The problem of good cipher design is essentially one of finding difficultproblems, subject to certain other conditions. This is a rather unusual situation, since one is ordinarily seeking the simple and easily soluble problemsin a field.How can we ever be sure that a system which is not ideal and thereforehas a unique solution for sufficiently large N will require a large amount ofwork to break with every method of analysis? There are two approaches tothis problem; (1) We can study the possible methods of solution available tothe cryptanalyst and attempt to describe them in sufficiently general terms tocover any methods he might use.
We then construct our system to resist this“general” method of solution. (2) We may construct our cipher in such a waythat breaking it is equivalent to (or requires at some point in the process) thesolution of some problem known to be laborious. Thus, if we could show thatsolving a certain system requires at least as much work as solving a system ofsimultaneous equations in a large number of unknowns, of a complex type,then we would have a lower bound of sorts for the work characteristic.The next three sections are aimed at these general problems.
It is difficult to define the pertinent ideas involved with sufficient precision to obtainresults in the form of mathematical theorems, but it is believed that the conclusions, in the form of general principles, are correct.12See von Neumann and Morgenstern, loc. cit. The situation between the cipher designer and cryptanalyst can be thought as a “game” of a very simple structure; a zero-sum two person game withcomplete information, and just two “moves”. The cipher designer chooses a system for his “move”.Then the cryptanalyst is informed of this choice and chooses a method of analysis.
The “value” ofthe play is the average work required to break a cryptogram in the system by the method chosen.70422G ENERALITIES ON THE S OLUTION OFC RYPTOGRAMSAfter the unicity distance has been exceeded in intercepted material, any system can be solved in principle by merely trying each possible key until theunique solution is obtained—i.e., a deciphered message which “make sense”in the original language. A simple calculation shows that this method of solution (which we may call complete trial and error) is totally impracticalexcept when the key is absurdly small.Suppose, for example, we have a key of 26! possibilities or about 26.3decimal digits, the same size as in simple substitution on English.
This is,by any significant measure, a small key. It can be written on a small slip ofpaper, or memorized in a few minutes. It could be registered on 27 switches,each having ten positions, or on 88 two-position switches.Suppose further, to give the cryptanalyst every possible advantage, that heconstructs an electronic device to try keys at the rate of one each microsecond(perhaps automatically selecting from the results of a χ2 test for statisticalsignificance). He may expect to reach the right key about half way through,and after an elapsed time of about 2×1026 /2×602 ×24×365×106 or 3×1012years.In other words, even with a small key complete trial and error will neverused in solving cryptograms, except in the trivial case where the key is extremely small, e.g., the Caesar with only 26 possibilities, or 1.4 digits.
Thetrial and error which is used so commonly in cryptography is of a differentsort, or is augmented by other means. If one had a secrecy system which required complete trial and error it would be extremely safe. Such a systemwould result, it appears, if the meaningful original messages, all say of 1000letters, were a random selection from the set of all sequences of 1000 letters.If any of the simple ciphers were applied to this type of language it seemsthat little improvement over complete trial and error would be possible.The methods of cryptanalysis actually used often involved a great dealof trial and error, but in a different way. First, the trials progress from moreprobable to less probable hypotheses, and, second, each trial disposes of alarge group of keys, not a single one.
Thus the key space may be dividedinto say 10 subsets, each containing about the same number of keys. By atmost 10 trials one determines which subset is the correct one. This subset isthen divided into several secondary subsets and the process repeated. With.the same key size (26! = 2 × 1026 we would expect about 26 × 5 or 130 trialsas compared to 1026 by complete trial and error. The possibility of choosingthe most likely of the subsets first for test would improve this result evenmore.
If the divisions were into two compartments (the best way to minimize705the number of trials) only 88 trials would be required. Whereas complete trialand error requires trials to the order of the number of keys, this subdividingtrial and error requires only trials to the order of the key size in bits.This remains true even when the different keys have different probabilities. The proper procedure, then, to minimize the expected number of trials isto divide the key space into subsets of equiprobability. When the proper subset is determined, this is again subdivided into equiprobability subsets. If thisprocess can be continued the number of trials expected when each division isinto two subsets will beH(K)h=log 2If each test has S possible results and each of these corresponds to thekey being in one of S equiprobability subsets, thenh=H(K)log Strials will be expected.
The intuitive significance of these results should benoted. In the two-compartment test with equiprobability, each test yields onebit of information as to the key. If the subsets have very different probabilities,is in testing a single key in complete trial and error, only a small amount ofinformation is obtained from the test. Thus with 26 equiprobable keys, a testof one yields only"26! − 126! − 111log+log−26!26!26!26!#or about 10−25 bits of information. Dividing into S equiprobability subsetsmaximizes the information obtained from each trial at log S, and the expected number of trials is the total information to be obtained, that is H(K)divided by this amount.The question here is similar to various coin weighing problems that havebeen circulated recently.
A typical example is the following: It is known thatone coin in 27 is counterfeit, and slightly lighter than the rest. A chemist’sbalance is available and the counterfeit coin is to be isolated by a series ofweighings. What the least number of weighings required to do this? The correct answer is 3, obtained by first dividing the coins into three groups of 9each.
Two of these are compared on the balance. The three possible resultsdetermine the set of 9 containing the counterfeit. This set is then divided into3 subsets of 3 each and the process continued. The set of coins correspondsto the set of keys, the counterfeit coin to the correct key, and the weighingprocedure to a trial or test. The original uncertainty is log 2 27 bits, and each706trial yields log 2 3 bits of information; thus, when there is no “diophantine2 27trouble”, logor 3 trials are sufficient.log 2 3This method of solution is feasible only if the key space can be dividedinto a small number of subsets, with a simple method of determining thesubset to which the correct key belongs.
One does not need to assume a complete key in order to apply a consistency test and determine if the assumptionis justified—an assumption on a part of the key (or as to whether the key isin some large section of the key space) can be tested. In other words it ispossible to solve for the key bit by bit.The possibility of this method of analysis is the crucial weakness of mostciphering systems. For example, in simple substitution, an assumption on asingle letter can be checked against its frequency, variety of contact, doublesor reversals, etc.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
