shannon1949 (776132), страница 4
Текст из файла (страница 4)
These are written repeatedly below the message and the two added modulo 26 (consideringthe alphabet numbered from A = 0 to Z = 25. Thusei = mi + ki (mod 26)where ki is of period d in the index i. For example, with the key G A H, weobtainmessagerepeated keycryptogramN OW IST HEGAH GAHGAT ODOSAN EThe Vigenère of period 1 is called the Caesar cipher. It is a simple substitutionin which each letter of M is advanced a fixed amount in the alphabet.
Thisamount is the key, which may be any number from 0 to 25. The so-calledBeaufort and Variant Beaufort are similar to the Vigenère, and encipher bythe equationsei = ki − mi (mod 26)ei = mi − ki (mod 26)respectively. The Beaufort of period one is called the reversed Caesar cipher.The application of two or more Vigenère in sequence will be called thecompound Vigenère.
It has the equationei = mi + ki + li + · · · + si (mod 26)666where ki , li , · · ·, si in general have different periods. The period of their sum,ki + li + · · · + s ias in compound transposition, is the least common multiple of the individualperiods.When the Vigenère is used with an unlimited key, never repeating, wehave the Vernam system6 , withei = mi + ki (mod 26)the ki being chosen at random and independently among 0, 1, · · ·, 25.
If thekey is a meaningful text we have the “running key” cipher.4.4 Digram, Trigram, and N -gram substitutionRather than substitute for letters one can substitute for digrams, trigrams, etc.General digram substitution requires a key consisting of a permutation of the262 digrams. It can be represented by a table in which the row corresponds tothe first letter of the digram and the column to the second letter, entries in thetable being the substitutions (usually also digrams).4.5 Single Mixed Alphabet VigenèreThis is a simple substitution followed by a Vigenère.ei = f (mi ) + kimi = f −1 (ei − ki )The “inverse” of this system is a Vigenère followed by simple substitutionei = g(mi + ki )mi = g −1 (ei ) − ki4.6 Matrix SystemOne method of n-gram substitution is to operate on successive n-grams witha matrix having an inverse7 .
The letters are assumed numbered from 0 to 25,making them elements of an algebraic ring. From the n-gram m1 m2 · · · mnof message, the matrix aij gives an n-gram of cryptogramei =nXaij mji = 1, · · ·, nj=167G. S. Vernam, “Cipher Printing Telegraph Systems for Secret Wire and Radio Telegraphic Communications”, Journal American Institute of Electrical Engineers, v. XLV, pp.
109–115, 1926.See L. S. Hill, “Cryptography in an Algebraic Alphabet”, American Math. Monthly, v. 36, No. 6, 1,1929, pp. 306–312; also “Concerning Certain Linear Transformation Apparatus of Cryptography”,v. 38, No. 3, 1931, pp. 135–154.667The matrix aij is the key, and deciphering is performed with the inversematrix. The inverse matrix will exist if and only if the determinant |aij | hasan inverse element in the ring.4.7 The Playfair CipherThis is a particular type of digram substitution governed by a mixed 25 letteralphabet written in a 5×5 square.
(The letter J is often dropped in cryptographic work—it is very infrequent, and when it occurs can be replaced byI.) Suppose the key square is as shown below:LARKXZGDYBQNMHTCOIVEPUFSWThe substitute for a digram AC, for example, is the pair of letters at the othercorners of the rectangle defined by A and C, i.e., LO, the L taken first sinceit is above A.
If the digram letters are on a horizontal line as RI, one usesthe letters to their right DF ; RF becomes DR. If the letters are on a verticalline, the letters below them are used. Thus P S becomes U W . If the lettersare the same nulls may be used to separate them or one may be omitted, etc.4.8 Multiple Mixed Alphabet SubstitutionIn this cipher there are a set of l simple substitutions which are used in sequence.
If the period d is fourm1 m2 m3 m4 m5 m6 · · ·becomesf1 (m1 ) f2 (m2 ) f3 (m3 ) f4 (m4 ) f1 (m5 ) f2 (m6 ) · · ·4.9 Autokey CipherA Vigenère type system in which either the message itself or the resultingcryptogram is used for the “key” is called an autokey cipher. The encipherment is started with a “priming key” (which is the entire key in our sense)and continued with the message or cryptogram displaced by the length ofthe priming key as indicated below, where the priming key is COMET.
Themessage used as “key”:MessageKeyCryptogramS E N D S U P P L I E S ···C O M E T S E N D S U P ···U S Z H L M T C O A Y H ···668The cryptogram used as “key”8 :S E N D S U P P L I E S ···C O M E T U S Z H L O H ···U S Z H L O H O S T S Z ···MessageKeyCryptogram4.10 Fractional CiphersIn these, each letter is first enciphered into two or more letters or numbersand these symbols are somehow mixed (e.g., by transposition).
The resultmay then be retranslated into the original alphabet. Thus, using a mixed 25letter alphabet for the key, we may translate letters into two-digit quinarynumbers by the table:012340LARKX1ZGDYB2QNMHT3COIVE4PUFSWThus B becomes 41. After the resulting series of numbers is transposed insome way they are taken in pairs and translated back into letters.4.11 CodesIn codes words (or sometimes syllables) are replaced by substitute lettergroups. Sometimes a cipher of one kind or another is applied to the result.5VALUATIONS OF S ECRECY S YSTEMThere are a number of different criteria that should be applied in estimatingthe value of a proposed secrecy system. The most important of these are:5.1 Amount of SecrecyThere are some systems that are perfect—the enemy is no better off afterintercepting any amount of material than before. Other systems, althoughgiving him some information, do not yield a unique “solution” to interceptedcryptograms. Among the uniquely solvable systems, there are wide variationsin the amount of labor required to effect this solution and in the amount ofmaterial that must be intercepted to make the solution unique.8This system is trivial from the secrecy standpoint since, with the exception of the first d letters, theenemy is in possession of the entire “key”.6695.2 Size of KeyThe key must be transmitted by non-interceptible means from transmitting toreceiving points.
Sometimes it must be memorized. It is therefore desirableto have the key as small as possible.5.3 Complexity of Enciphering and Deciphering OperationsEnciphering and deciphering should, of course, be as simple as possible. Ifthey are done manually, complexity leads to loss of time, errors, etc. If donemechanically, complexity leads to large expensive machines.5.4 Propagation of ErrorsIn certain types of ciphers an error of one letter in enciphering or transmissionleads to a large number of errors in the deciphered text.
The error are spreadout by the deciphering operation, causing the loss of much information andfrequent need for repetition of the cryptogram. It is naturally desirable tominimize this error expansion.5.5 Expansion of MessageIn some types of secrecy systems the size of the message is increased by theenciphering process. This undesirable effect may be seen in systems whereone attempts to swamp out message statistics by the addition of many nulls,or where multiple substitutes are used. It also occurs in many “concealment”types of systems (which are not usually secrecy systems in the sense of ourdefinition).6T HE A LGEBRA OF S ECRECY S YSTEMSIf we have two secrecy systems T and R we can often combine them invarious ways to form a new secrecy system S.
If T and R have the samedomain (message space) we may form a kind of “weighted sum”,S = pT + qRwhere p + q = 1. This operation consists of first making a preliminary choicewith probabilities p and q determining which of T and R is used. This choiceis part of the key of S. After this is determined T or R is used as originallydefined. The total key of S must specify which of T and R is used and whichkey of T (or R) is used.If T consists of the transformations T1 , · · ·, Tm with probabilities p1 , · · ·, pmand R consists of R1 , · · ·, Rk with probabilities q1 , · · ·, qk then S = pT +qR consists of the transformations T1 , · · ·, Tm , R1 , · · ·, Rk with probabilitiespp1 , pp2 , · · ·, ppm , qq1 , qq2 , · · ·, qqk respectively.670More generally we can form the sum of a number of systems.S = p1 T + p2 R + · · · + p m UXpi = 1We note that any system T can be written as a sum of fixed operationsT = p 1 T1 + p 2 T2 + · · · + p m TmTi being a definite enciphering operation of T corresponding to key choice i,which has probability pi .R−1TRK1K2T−1Fig.
3. Product of two systems S = RTA second way of combining two secrecy systems is by taking the “product”, shown schematically in Fig. 3. Suppose T and R are two systems andthe domain (language space) of R can be identified with the range (cryptogram space) of T . Then we can apply first T to our language and then Rto the result of this enciphering process. This gives a resultant operation Swhich we write as a productS = RTThe key for S consists of both keys of T and R which are assumed chosenaccording to their original probabilities and independently. Thus, if the mkeys of T are chosen with probabilitiesp1 p2 · · · pmand the n keys of R have probabilitiesp01 p02 · · · p0n ,then S has at most mn keys with probabilities pi p0j .
In many cases some of theproduct transformations Ri Tj will be the same and can be grouped together,adding their probabilities.Product encipherment is often used; for example, one follows a substitution by a transposition or a transposition by a Vigenère, or applies a code tothe text and enciphers the result by substitution, transposition, fractionation,etc.671It may be noted that multiplication is not in general commutative (we donot always have RS = SR), although in special cases, such as substitutionand transposition, it is. Since it represents an operation it is definitionallyassociative.
That is, R(ST ) = (RS)T = RST . Furthermore, we have thelawsp(p0 T + q 0 R) + qS = pp0 T + pq 0 R + qS(weighted associative law for addition)T (pR + qS) = pT R + qT S(pR + qS)T = pRT + qST(right and left hand distributive laws) andp1 T + p2 T + p3 R = (p1 + p2 )T + p3 RIt should be emphasized that these combining operations of addition andmultiplication apply to secrecy systems as a whole. The product of two systems T R should not be confused with the product of the transformations inthe systems Ti Rj , which also appears often in this work.
The former T R is asecrecy system, i.e., a set of transformations with associated probabilities; thelatter is a particular transformation. Further the sum of two systems pR + qTis a system—the sum of two transformations is not defined. The systems Tand R may commute without the individual Ti and Rj commuting, e.g., if Ris a Beaufort system of a given period, all keys equally likely.Ri Rj 6= Rj Riin general, but of course RR does not depend on its order; actuallyRR = Vthe Vigenère of the same period with random key.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
