shannon1949 (776132), страница 6
Текст из файла (страница 6)
To prove the second part we note first that, if Ti Tj−1 T = T , then Ti Tj−1 Tsis a transformation of T . It remains to show that all keys are equiprobable.PWe have T = s ps Ts andXps Ti Tj−1 Ts =sXp s TssThe term in the left hand sum with s = j yields pj Ti . The only term in Ti onthe right is pi Ti . Since all coefficients are nonnegative it follows thatpj ≤pi .The same argument holds with i and j interchanged and consequentlypj = p iand T is pure. Thus the condition that Ti Tj−1 T = T might be used as analternative definition of a pure system.8S IMILAR S YSTEMSTwo secrecy systems R and S will be said to be similar if there exists atransformation A having an inverse A−1 such thatR = ASThis means that enciphering with R is the same as enciphering with S andthen operating on the result with the transformation A.
If we write R≈S tomean R is similar to S then it is clear that R≈S implies S≈R. Also R≈Sand S≈T imply R≈T and finally R≈R. These are summarized by sayingthat similarity is an equivalence relation.The cryptographic significance of similarity is that if R≈S then R and Sare equivalent from the cryptanalytic point of view. Indeed if a cryptanalystintercepts a cryptogram in system S he can transform it to one in system Rby merely applying the transformation A to it. A cryptogram in system R istransformed to one in S by applying A−1 . If R and S are applied to the samelanguage or message space, there is a one-to-one correspondence between theresulting cryptograms. Corresponding cryptograms give the same distributionof a posteriori probabilities for all messages.If one has a method of breaking the system R then any system S similar678to R can be broken by reducing to R through application of the operation A.This is a device that is frequently used in practical cryptanalysis.As a trivial example, simple substitution where the substitutes are not letters but arbitrary symbols is similar to simple substitution using letter substitutes.
A second example is the Caesar and the reverse Caesar type ciphers. The latter is sometimes broken by first transforming into a Caesartype. This can be done by reversing the alphabet in the cryptogram. TheVigenère, Beaufort and Variant Beaufort are all similar, when the key is random.
The “autokey” cipher (with the message used as “key”) primed withthe key K1 K2 · · · Kd is similar to a Vigenère type with the key alternatelyadded and subtracted Mod 26. The transformation A in this case is that of“deciphering” the autokey with a series of d A’s for the priming key.PART IITHEORETICAL SECRECY9I NTRODUCTIONWe now consider problems connected with the “theoretical secrecy” of a system.
How immune is a system to cryptanalysis when the cryptanalyst has unlimited time and manpower available for the analysis of cryptograms? Doesa cryptogram have a unique solution (even though it may require an impractical amount of work to find it) and if not how many reasonable solutionsdoes it have? How much text in a given system must be intercepted beforethe solution becomes unique? Are there systems which never become uniquein solution no matter how much enciphered text is intercepted? Are theresystems for which no information whatever is given to the enemy no matterhow much text is intercepted? In the analysis of these problems the conceptsof entropy, redundancy and the like developed in “A Mathematical Theory ofCommunication” (hereafter referred to as MTC) will find a wide application.10P ERFECT S ECRECYLet us suppose the possible messages are finite in number M1 , · · · , Mn andhave a priori probabilities P (M1 ), · · · , P (Mn ), and that these are encipheredinto the possible cryptograms E1 , · · · , Em byE = Ti M.The cryptanalyst intercepts a particular E and can then calculate, in principle at least, the a posteriori probabilities for the various messages, P E (M ).It is natural to define perfect secrecy by the condition that, for all E the aposteriori probabilities are equal to the a priori probabilities independently679of the values of these.
In this case, intercepting the message has given thecryptanalyst no information.9 Any action of his which depends on the information contained in the cryptogram cannot be altered, for all of his probabilities as to what the cryptogram contains remain unchanged. On the otherhand, if the condition is not satisfied there will exist situations in which theenemy has certain a priori probabilities, and certain key and message choicesmay occur for which the enemy’s probabilities do change.
This in turn mayaffect his actions and thus perfect secrecy has not been obtained. Hence thedefinition given is necessarily required by our intuitive ideas of what perfectsecrecy should mean.A necessary and sufficient condition for perfect secrecy can be found asfollows: We have by Bayes’ theoremPE (M ) =P (M )PM (E)P (E)in which:P (M ) = a priori probability of message M .PM (E) = conditional probability of cryptogram E if message M ischosen i.e.
the sum of the probabilities of all keys whichproduce cryptogram E from message M .P (E) = probability of obtaining cryptogram E from any cause.PE (M ) = a posteriori probability of message M if cryptogram E isintercepted.For perfect secrecy PE (M ) must equal P (M ) for all E and all M .
Henceeither P (M ) = 0, a solution that must be excluded since we demand theequality independent of the values of P (M ), orPM (E) = P (E)for every M and E. Conversely if PM (E) = P (E) thenPE (M ) = P (M )and we have perfect secrecy. Thus we have the result:Theorem 6. A necessary and sufficient condition for perfect secrecy is thatPM (E) = P (E)for all M and E. That is, PM (E) must be independent of M .Stated another way, the total probability of all keys that transform Mi9A purist might object that the enemy has obtained some information in that he knows a messagewas sent.
This may be answered by having among the messages a “blank” corresponding to “nomessage.” If no message is originated the blank is enciphered and sent as a cryptogram. Then eventhis modicum of remaining information is eliminated.680into a given cryptogram E is equal to that of all keys transforming M j intothe same E, for all Mi , Mj and E.Now there must be as many E’s as there are M ’s since, for a fixed i, T igives a one-to-one correspondence between all the M ’s and some of the E’s.For perfect secrecy PM (E) = P (E) 6= 0 for any of these E’s and any M .Hence there is at least one key transforming any M into any of these E’s.But all the keys from a fixed M to different E’s must be different, andtherefore the number of different keys is at least as great as the number ofM ’s.
It is possible to obtain perfect secrecy with only this number of keys, asM1E112345M251243E2M345132E3M434521E4M523451E5Fig. 5. Perfect systemone shows by the following example: Let the Mi be numbered 1 to n and theEi the same, and using n keys letTi M j = E swhere s = i + j (Mod n). In this case we see that PE (M ) = n1 = P (E)and we have perfect secrecy. An example is shown in Fig. 5 with s = i + j −1 (Mod 5).Perfect systems in which the number of cryptograms, the number of messages, and the number of keys are all equal are characterized by the properties that (1) each M is connected to each E by exactly one line, (2) all keysare equally likely. Thus the matrix representation of the system is a “Latinsquare”.In MTC it was shown that information may be conveniently measured bymeans of entropy.
If we have a set of possibilities with probabilities p 1 , p2 , · · · , pn ,the entropy H is given by:H=−Xpi log pi .681In a secrecy system there are two statistical choices involved, that of the message and of the key. We may measure the amount of information producedwhen a message is chosen by H(M ):H(M ) = −XP (M ) log P (M ),XP (K) log P (K).the summation being over all possible messages. Similarly, there is an uncertainty associated with the choice of key given by:H(K) = −In perfect systems of the type described above, the amount of informationin the message is at most log n (occurring when all messages are equiprobable).
This information can be concealed completely only if the key uncertainty is at least log n. This is the first example of a general principle whichwill appear frequently: that there is a limit to what we can obtain with a givenuncertainty in key—the amount of uncertainty we can introduce into the solution cannot be greater than the key uncertainty.The situation is somewhat more complicated if the number of messagesis infinite.
Suppose, for example, that they are generated as infinite sequencesof letters by a suitable Markoff process. It is clear that no finite key will giveperfect secrecy. We suppose, then, that the key source generates key in thesame manner, that is, as an infinite sequence of symbols.
Suppose further thatonly a certain length of key LK is needed to encipher and decipher a lengthLM of message. Let the logarithm of the number of letters in the messagealphabet be RM and that for the key alphabet be RK . Then, from the finitecase, it is evident that perfect secrecy requiresRM LM ≤RK LK .This type of perfect secrecy is realized by the Vernam system.These results have been deduced on the basis of unknown or arbitrarya priori probabilities of the messages.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
