shannon1949 (776132), страница 3
Текст из файла (страница 3)
The assumption is actually the one ordinary used in cryptographic studies.It is pessimistic and hence safe, but in the long run realistic, since onemust expect his system to be found out eventually. Thus, even when anentirely new system is devised, so that the enemy cannot assign any a662priori probability to it without discovering it himself, one must still livewith the expectation of his eventual knowledge.The situation is similar to that occurring in the theory of games3 where it isassumed that the opponent “finds out” the strategy of play being used. In bothcases the assumption serves to delineate sharply the opponent’s knowledge.A second possible objection to our definition of secrecy systems is thatno account is taken of the common practice of inserting nulls in a messageand the use of multiple substitutes.
In such cases there is not a unique cryptogram for a given message and key, but the encipherer can choose at willfrom among a number of different cryptograms. This situation could be handled, but would only add complexity at the present stage, without substantially altering any of the basic results.If the messages are produced by a Markoff process of the type describedin (1) to represent an information source, the probabilities of various messages are determined by the structure of the Markoff process. For the present,however, we wish to take a more general view of the situation and regardthe messages as merely an abstract set of entities with associated probabilities, not necessarily composed of a sequence of letters and not necessarilyproduced by a Markoff process.It should be emphasized that throughout the paper a secrecy system meansnot one, but a set of many transformations.
After the key is chosen only oneof these transformations is used and one might be led from this to define asecrecy system as a single transformation on a language. The enemy, however, does not know what key was chosen and the “might have been” keysare as important for him as the actual one. Indeed it is only the existence ofthese other possibilities that gives the system any secrecy. Since the secrecyis our primary interest, we are forced to the rather elaborate concept of a secrecy system defined above.
This type of situation, where possibilities are asimportant as actualities, occurs frequently in games of strategy. The courseof a chess game is largely controlled by threats which are not carried out.Somewhat similar is the “virtual existence” of unrealized imputations in thetheory of games.It may be noted that a single operation on a language forms a degenerate type of secrecy system under our definition—a system with only one keyof unit probability. Such a system has no secrecy—the cryptanalyst finds themessage by applying the inverse of this transformation, the only one in thesystem, to the intercepted cryptogram. The decipherer and cryptanalyst inthis case possess the same information.
In general, the only difference between the decipherer’s knowledge and the enemy cryptanalyst’s knowledge3See von Neumann and Morgenstern “The Theory of Games”, Princeton 1947.663is that the decipherer knows the particular key being used, while the cryptanalyst knows only the a priori probabilities of the various keys in the set.The process of deciphering is that of applying the inverse of the particulartransformation used in enciphering to the cryptogram. The process of cryptanalysis is that of attempting to determine the message (or the particular key)given only the cryptogram and the a priori probabilities of various keys andmessages.There are a number of difficult epistemological questions connected withthe theory of secrecy, or in fact with any theory which involves questionsof probability (particularly a priori probabilities, Bayes’ theorem, etc.) whenapplied to a physical situation.
Treated abstractly, probability theory can beput on a rigorous logical basis with the modern measure theory approach 45 .As applied to a physical situation, however, especially when “subjective”probabilities and unrepeatable experiments are concerned, there are manyquestions of logical validity. For example, in the approach to secrecy madehere, a priori probabilities of various keys and messages are assumed knownby the enemy cryptographer—how can one determine operationally if his estimates are correct, on the basis of his knowledge of the situation?One can construct artificial cryptographic situations of the “urn and die”type in which the a priori probabilities have a definite unambiguous meaningand the idealization used here is certainly appropriate. In other situations thatone can imagine, for example an intercepted communication between Martian invaders, the a priori probabilities would probably be so uncertain as tobe devoid of significance.
Most practical cryptographic situations lie somewhere between these limits. A cryptanalyst might be willing to classify thepossible messages into the categories “reasonable”, “possible but unlikely”and “unreasonable”, but feel that finer subdivision was meaningless.Fortunately, in practical situations, only extreme errors in a priori probabilities of keys and messages cause significant errors in the important parameters. This is because of the exponential behavior of the number of messagesand cryptograms, and the logarithmic measures employed.3R EPRESENTATION OF S YSTEMSA secrecy system as defined above can be represented in various ways.
Onewhich is convenient for illustrative purposes is a line diagram, as in Figs. 2and 4. The possible messages are represented by points at the left and thepossible cryptograms by points at the right. If a certain key, say key 1, transforms message M2 into cryptogram E4 then M2 and E4 are connected by a45See J. L. Doob, “Probability as Measure”, Annals of Math. Stat., v.
12, 1941, pp. 206–214.A. Kolmogoroff, “Grundbegriffe der Wahrscheinlichkeitsrechnung”, Ergebnisse der Mathematic, v.2, No. 3 (Berlin 1933).664line labeled 1, etc. From each possible message there must be exactly oneline emerging for each different key. If the same is true for each cryptogram,we will say that the system is closed.A more common way of describing a system is by stating the operationone performs on the message for an arbitrary key to obtain the cryptogram.Similarly, one defines implicitly the probabilities for various keys by describing how a key is chosen or what we know of the enemy’s habits of key choice.The probabilities for messages are implicitly determined by stating our a priori knowledge of the enemy’s language habits, the tactical situation (whichwill influence the probable content of the message) and any special information we may have regarding the cryptogram.M1M21322M113132E23M322M211 2M4E113E33CLOSED SYSTEMNOT CLOSEDFig.
2. Line drawings for simple systems4S OME E XAMPLES OF S ECRECY S YSTEMSIn this section a number of examples of ciphers will be given. These willoften be referred to in the remainder of the paper for illustrative purposes.4.1 Simple Substitution CipherIn this cipher each letter of the message is replaced by a fixed substitute,usually also a letter.
Thus the message,M = m 1 m2 m3 m4 · · ·where m1 , m2 , · · · are the successive letters becomes:E = e1 e2 e3 e4 · · · = f (m1 )f (m2 )f (m3 )f (m4 )· · ·where the function f (m) is a function with an inverse. The key is a permutation of the alphabet (when the substitutes are letters) e.g. X G U A C D TB F H R S L M Q V Y Z W I E J O K N P . The first letter X is thesubstitute for A, G is the substitute for B, etc.6654.2 Transposition (Fixed Period d)The message is divided into groups of length d and a permutation applied tothe first group, the same permutation to the second group, etc.
The permutation is the key and can be represented by a permutation of the first d integers.Thus for d = 5, we might have 2 3 1 5 4 as the permutation. This means that:m1 m2 m3 m4 m5 m6 m7 m8 m9 m10 · · ·becomesm2 m3 m1 m5 m4 m7 m8 m6 m10 m9 · · ·.Sequential application of two or more transpositions will be called compound transposition. If the periods are d1 , d2 , · · ·, dn it is clear that the result is a transposition of period d, where d is the least common multiple ofd1 , d2 , · · ·, dn .4.3 Vigenère, and VariationsIn the Vigenère cipher the key consists of a series of d letters.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
