shannon1949 (776132), страница 10
Текст из файла (страница 10)
With a finite key size, the equivocationof key and message generally approaches zero, but not necessarily so. In factit is possible for HE (K) to remain constant at its initial value H(K). Then,no matter how much materials is intercepted, there is not a unique solutionbut many of comparable probability. We will define an “ideal” system as onein which HE (K) and HE (M ) do not approach zero as N →∞. A “stronglyideal” system is one in which HE (K) remains constant at H(K).An example is a simple substitution on an artificial language in whichall letters are equiprobable and successive letters independently chosen. It iseasily seen that HE (K) = H(K) and HE (M ) rises linearly along a line ofslope log G (where G is the number of letters in the alphabet) until it strikesthe line H(K), after which it remains constant at this value.With natural languages it is in general possible to approximate the idealcharacteristic—the unicity point can be made to occur for as large N as isdesired.
The complexity of the system needed usually goes up rapidly whenwe attempt to do this, however. It is not always possible to attain actually theideal characteristic with any system of finite complexity.To approximate the ideal equivocation, one may first operate on the message with a transducer which removes all redundancies. After this almost anysimple ciphering system—substitution, transposition, Vigenère, etc., is satisfactory. The more elaborate the transducer and the nearer the output is to thedesired form, the more closely will the secrecy system approximate the idealcharacteristic.699Theorem 12.
A necessary and sufficient condition that T be strongly ideal isthat, for any two keys, Ti−1 Tj is a measure preserving transformation of themessage space into itself.This is true since the a posteriori probability of each key is equal to its apriori probability if and only if this condition is satisfied.18E XAMPLES OF I DEAL S ECRECY S YSTEMSSuppose our language consists of a sequence of letters all chosen independently and with equal probabilities.
Then the redundancy is zero, and from aresult of section 12, HE (K) = H(K). We obtain the resultTheorem 13. If all letters are equally likely and independent any closed cipher is strongly ideal.The equivocation of message will rise along the key appearance characteristic which will usually approach H(K), although in some cases it doesnot. In the cases of n-gram substitution, transposition, Vigenère, and variations, fractional, etc., we have strongly ideal systems for this simple languagewith HE (M )→H(K) as N →∞.Ideal secrecy systems suffer from a number of disadvantages.1. The system must be closely matched to the language. This requires anextensive study of the structure of the language by the designer.
Also achange in statistical structure or a selection from the set of possible messages, as in the case of probable words (words expected in this particularcryptogram), renders the system vulnerable to analysis.2. The structure of natural languages is extremely complicated, and this implies a complexity of the transformations required to eliminate redundancy. Thus any machine to perform this operation must necessarily bequite involved, at least in the direction of information storage, since a“dictionary” of magnitude greater than that of an ordinary dictionary is tobe expected.3.
In general, the transformations required introduce a bad propagation oferror characteristic. Error in transmission of a single letter produces aregion of changes near it of size comparable to the length of statisticaleffects in the original language.19F URTHER R EMARKS ON E QUIVOCATION ANDR EDUNDANCYWe have taken the redundancy of “normal English” to be about .7 decimaldigits per letter or a redundancy of 50%. This is on the assumption that worddivisions were omitted.
It is an approximate figure based on statistical structure extending over about 8 letters, and assumes the text to be of an ordinary type, such as newspaper writing, literary work, etc. We may note herea method of roughly estimating this number that is of some cryptographicinterest.700A running key cipher is a Vernam type system where, in place of a randomsequence of letters, the key is a meaningful text. Now it is known that runningkey ciphers can usually be solved uniquely. This shows that English can bereduced by a factor of two to one and implies a redundancy of at least 50%.This figure cannot be increase very much, however, for a number of reasons,unless long range “meaning” structure of English is considered.The running key cipher can be easily improved to lead to ciphering systems which could not be solved without the key.
If one uses in place of oneEnglish text, about d different texts as key, adding them all to the message,a sufficient amount of key has been introduced to produce a high positiveequivocation. Another method would be to use, say, every 10th letter of thetext as key. The intermediate letters are omitted and cannot be used at anyother point of the message. This has much the same effect, since these spacedletters are nearly independent.The fact that the vowels in a passage can be omitted without essentialloss suggests a simple way of greatly improving almost any ciphering system.
First delete all vowels, or as much of the messages as possible withoutrunning the risk of multiple reconstructions, and then encipher the residue.Since reduces the redundancy by a factor of perhaps 3 or 4 to 1, the unicity point will be moved out by this factor.
This is one way of approachingideal systems—using the decipherer’s knowledge of English as part of thedeciphering system.20D ISTRIBUTION OF E QUIVOCATIONA more complete description of a secrecy system applied to a language thanis afforded by the equivocation characteristics can be founded by giving thedistribution of equivocation. For N intercepted letters we consider the fraction of cryptograms for which the equivocation (for these particular E’s, notthe mean HE (M ) lies between certain limits. This gives a density distributionfunctionP (HE (M ), N ) dHE (M )for the probability that for N letters H lies between the limits H and H +dH.
The mean equivocation we have previously studied is the mean of thisdistribution. The function P (HE (M ), N ) can be thought of as plotted along athird dimension, normal to the paper, on the HE (M ), N plane. If the languageis pure, with a small influence range, and the cipher is pure, the function willusually be a ridge in this plane whose highest point follows approximately themean HE (M ), at least until near the unicity point.
In this case, or when theconditions are nearly verified, the mean curve gives a reasonably completepicture of the system.701On the other hand, if the language is not pure, but made up of a set ofpure componentsXL = pi Lihaving different equivocation curves with the system, then the total distribution will usually be made up of a series of ridges. There will be one for eachLi weighted in accordance with its pi . The mean equivocation characteristicwill be a line somewhere in the midst of these ridges and may not give a verycomplete picture of the situation.
This is shown in Fig. 11. A similar effectoccurs if the system is not pure but made up of several systems with differentH curves.The effect of mixing pure languages which are near to one another instatistical structure is to increase the width of the ridge. Near the unicityFig. 11. Estimation of equivocation with a mixed language L = 12 L1 + 12 L2point this tends to raise the mean equivocation, since equivocation cannotbecome negative and the spreading is chiefly in the positive direction. Weexpect, therefore, that in this region the calculations based on the randomcipher should be somewhat low.PART IIIPRACTICAL SECRECY21T HE W ORK C HARACTERISTICAfter the unicity point has been passed in intercepted material there will usually be a unique solution to the cryptogram.
The problem of isolating thissingle solution of high probability is the problem of cryptanalysis. In the region before the unicity point we may say that the problem of cryptanalysisis that of isolating all the possible solutions of high probability (compared tothe remainder) and determining their various probabilities.702Although it is always possible in principle to determine these solutions(by trial of each possible key for example), different enciphering systemsshow a wide variation in the amount of work required. The average amountof work to determine the key for a cryptogram of N letters, W (N ), measured say in man hours, may be called the work characteristic of the system.This average is taken over all messages and all keys with their appropriateprobabilities.
The function W (N ) is a measure of the amount of “practicalsecrecy” afforded by the system.For a simple substitution on English the work and equivocation characteristics would be somewhat as shown in Fig. 12. The dotted portion ofFig. 12. Typical work and equivocation characteristicsthe curve is in the range where there are numerous possible solutions andthese must all be determined. In the solid portion after the unicity point onlyone solution exists in general, but if only the minimum necessary data aregiven a great deal of work must be done to isolate it. As more material isavailable the work rapidly decreases toward some asymptotic value—wherethe additional data no longer reduces the labor.Essentially the behavior shown in Fig.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
