shannon1949 (776132), страница 14
Текст из файла (страница 14)
If the mix is good then the propagationof errors is bad. A transmission error of one letter will affect several letterson deciphering.71327I NCOMPATIBILITY OF THE C RITERIA FOR G OODS YSTEMSThe five criteria for good secrecy systems given in section 5 appear to havea certain incompatibility when applied to a natural language with its complicated statistical structure. With artificial languages having a simple statisticalstructure it is possible to satisfy all requirements simultaneously, by means ofthe ideal type ciphers. In natural languages a compromise must be made andthe valuations balanced against one another with a view toward the particularapplication.If any one of the five criteria is dropped, the other four can be satisfiedfairly well, as the following example show:1. If we omit the first requirement (amount of secrecy) any simple ciphersuch as simple substitution will do.
In the extreme case of omitting thiscondition completely, no cipher at all is required and one sends the clear!2. If the size of the key is not limited the Vernam system can be used.3. If complexity of operation is not limited, various extremely complicatedtypes of enciphering process can be used.4. If we omit the propagation of error condition, systems of the type T F Swould be very good, although somewhat complicated.5. If we allow large expansion of message, various systems are easily devised where the “correct” message is mixed with many “incorrect” ones(misinformation). The key determines which of these is correct.A very rough argument for the incompatibility of the five conditions maybe given as follows: From condition 5, secrecy system essentially as studiedin this paper must be used; i.e., no great use of nulls, etc.
Perfect and idealsystems are excluded by condition 2 and by 3 and 4, respectively. The highsecrecy required by 1 must then come from a high work characteristic, notfrom a high equivocation characteristic. If key is small, the system simple,and the errors do not propagate, probable word methods will generally solvethe system fairly easily since we then have a fairly simple system of equationsfor the key.This reasoning is too vague to be conclusive, but the general idea seemsquite reasonable. Perhaps if the various criteria could be given quantitativesignificance, some sort of an exchange equation could be found involvingthem and giving the best physically compatible sets of values. The two mostdifficult to measure numerically are the complexity of operations, and thecomplexity of statistical structure of the language.APPENDIXProof of Theorem 3Select any message M1 and group together all cryptograms that can beobtained from M1 by any enciphering operation Ti .
Let this class of crypto714grams be C10 . Group with M1 all messages that can be obtained from M1by Ti−1 Tj M1 , and call this class C1 . The same C10 would be obtained if westarted with any other M in C1 sinceTs Tj−1 Ti M1 = Tl M1 .Similarly the same C1 would be obtained.Choosing an M not in C1 (if any such exist) we construct C2 and C20 inthe same way.
Continuing in this manner we obtain the residue classes withproperties (1) and (2). Let M1 and M2 be in C1 and supposeM2 = T1 T2−1 M1 .If E1 is in C10 and can be obtained from M1 byE 1 = T α M1 = T β M1 = · · · = T η M1 ,thenE1 = Tα T2−1 T1 M2 = Tβ T2−1 T1 M2 = · · ·= T λ M2 = T µ M2 · · ·Thus each Mi in C1 transforms into E1 by the same number of keys. Similarlyeach Ei in C10 is obtained from any M in C1 by the same number of keys. Itfollows that this number of keys is a divisor of the total number of keys andhence we have properties (3) and (4).PostScript by Jiejun Kong:Many papers die before their authors die. Nevertheless, some papers will be read and referreduntil they become part of our life.
In that context they live forever.Claude Elwood Shannon died Saturday, February 24, 2001 at the Courtyard Nursing Care Centerin Medford, Massachusetts. He was 84 years old. Though he has left the world, I believe this classicalpaper “Communication Theory of Secrecy Systems” will not.I am working at network security area and Shannon’s work always amazes me. Recently I amshocked to find that this paper does not have a typesetted version on the colossal Internet, the onlything people can get is a set of barely-legible scanned JPEG images from photocopies (see http://www3.edgenet.net/dcowley/docs.html). So here is my memorial service to the greatman. I spent a lot of time to input and inspect the entire contents of this 60-page paper. During mytypesetting I am convinced that his genius is worth the time and effort I spent!Although not every word looks exactly like the original copy, I can assure the correctness ofcontents, page numbers, places of theorems, figures, and footnotes, etc., as you have read from yourprintout.Salute to Dr.
Shannon and thank you for reading this postscript.715.