没有合适的资源？快使用搜索试试~ 我知道了~

首页C.E.Shannon-Communication Theory of Secrecy Systems

资源详情

资源评论

资源推荐

Communication Theory of Secrecy Systems

By C. E. SHANNON

1 INTRODUCTION AND SUMMARY

The problems of cryptography and secrecy systems furnish an interesting ap-

plication of communication theory

1

. In this paper a theory of secrecy systems

is developed. The approach is on a theoretical level and is intended to com-

plement the treatment found in standard works on cryptography

2

. There, a

detailed study is made of the many standard types of codes and ciphers, and

of the ways of breaking them. We will be more concerned with the general

mathematical structure and properties of secrecy systems.

The treatment is limited in certain ways. First, there are three general

types of secrecy system: (1) concealment systems, including such methods

as invisible ink, concealing a message in an innocent text, or in a fake cov-

ering cryptogram, or other methods in which the existence of the message

is concealed from the enemy; (2) privacy systems, for example speech in-

version, in which special equipment is required to recover the message; (3)

“true” secrecy systems where the meaning of the message is concealed by

cipher, code, etc., although its existence is not hidden, and the enemy is as-

sumed to have any special equipment necessary to intercept and record the

transmitted signal. We consider only the third type—concealment system are

primarily a psychological problem, and privacy systems a technological one.

Secondly, the treatment is limited to the case of discrete information

where the message to be enciphered consists of a sequence of discrete sym-

bols, each chosen from a ﬁnite set. These symbols may be letters in a lan-

guage, words of a language, amplitude levels of a “quantized” speech or

video signal, etc., but the main emphasis and thinking has been concerned

with the case of letters.

The paper is divided into three parts. The main results will now be brieﬂy

summarized. The ﬁrst part deals with the basic mathematical structure of

secrecy systems. As in communication theory a language is considered to be

represented by a stochastic process which produces a discrete sequence of

The material in this paper appeared in a conﬁdential report “A Mathematical Theory of Cryptogra-

phy” dated Sept.1, 1946, which has now been declassiﬁed.

1

Shannon, C. E., “A Mathematical Theory of Communication,” Bell System Technical Journal, July

1948, p.379; Oct. 1948, p.623.

2

See, for example, H. F. Gaines, “Elementary Cryptanalysis,” or M. Givierge, “Cours de Cryptogra-

phie.”

Claude E. Shannon, "Communication Theory of Secrecy Systems", Bell System Technical

Journal, vol.28-4, page 656--715, Oct. 1949.

symbols in accordance with some system of probabilities. Associated with

a language there is a certain parameter

which we call the redundancy of

the language.

measures, in a sense, how much a text in the language can

be reduced in length without losing any information. As a simple example,

since

always follows

in English words, the

may be omitted without

loss. Considerable reductions are possible in English due to the statistical

structure of the language, the high frequencies of certain letters or words, etc.

Redundancy is of central importance in the study of secrecy systems.

A secrecy system is deﬁned abstractly as a set of transformations of one

space (the set of possible messages) into a second space (the set of possible

cryptograms). Each particular transformation of the set corresponds to enci-

phering with a particular key. The transformations are supposed reversible

(non-singular) so that unique deciphering is possible when the key is known.

Each key and therefore each transformation is assumed to have an a priori

probability associated with it—the probability of choosing that key. Similarly

each possible message is assumed to have an associated a priori probability,

determined by the underlying stochastic process. These probabilities for the

various keys and messages are actually the enemy cryptanalyst’s a priori

probabilities for the choices in question, and represent his a priori knowledge

of the situation.

To use the system a key is ﬁrst selected and sent to the receiving point.

The choice of a key determines a particular transformation in the set form-

ing the system. Then a message is selected and the particular transformation

corresponding to the selected key applied to this message to produce a cryp-

togram. This cryptogram is transmitted to the receiving point by a channel

and may be intercepted by the “enemy

.” At the receiving end the inverse

of the particular transformation is applied to the cryptogram to recover the

original message.

If the enemy intercepts the cryptogram he can calculate from it the a pos-

teriori probabilities of the various possible messages and keys which might

have produced this cryptogram. This set of a posteriori probabilities consti-

tutes his knowledge of the key and message after the interception. “Knowl-

edge” is thus identiﬁed with a set of propositions having associated proba-

bilities. The calculation of the a posteriori probabilities is the generalized

problem of cryptanalysis.

As an example of these notions, in a simple substitution cipher with ran-

dom key there are

transformations, corresponding to the

ways we can

substitute for

different letters. These are all equally likely and each there-

fore has an a priori probability

. If this is applied to “normal English”

The word “enemy,” stemming from military applications, is commonly used in cryptographic work

to denote anyone who may intercept a cryptogram.

657

the cryptanalyst being assumed to have no knowledge of the message source

other than that it is producing English text, the a priori probabilities of var-

ious messages of

letters are merely their relative frequencies in normal

English text.

If the enemy intercepts

letters of cryptograms in this system his prob-

abilities change. If

is large enough (say

letters) there is usually a single

message of a posteriori probability nearly unity, while all others have a total

probability nearly zero. Thus there is an essentially unique “solution” to the

cryptogram. For

smaller (say

) there will usually be many mes-

sages and keys of comparable probability, with no single one nearly unity. In

this case there are multiple “solutions” to the cryptogram.

Considering a secrecy system to be represented in this way, as a set of

transformations of one set of elements into another, there are two natural

combining operations which produce a third system from two given systems.

The ﬁrst combining operation is called the product operation and corresponds

to enciphering the message with the ﬁrst secrecy system

and enciphering

the resulting cryptogram with the second system

, the keys for

and

being chosen independently. This total operation is a secrecy system whose

transformations consist of all the products (in the usual sense of products

of transformations) of transformations in

with transformations in

. The

probabilities are the products of the probabilities for the two transformations.

The second combining operation is “weighted addition.”

It corresponds to making a preliminary choice as to whether system

or

is to be used with probabilities

and

, respectively. When this is done

or

is used as originally deﬁned.

It is shown that secrecy systems with these two combining operations

form essentially a “linear associative algebra” with a unit element, an alge-

braic variety that has been extensively studied by mathematicians.

Among the many possible secrecy systems there is one type with many

special properties. This type we call a “pure” system. A system is pure if all

keys are equally likely and if for any three transformations

in the

set the product

is also a transformation in the set. That is, enciphering, deciphering, and en-

ciphering with any three keys must be equivalent to enciphering with some

key.

With a pure cipher it is shown that all keys are essentially equivalent—

they all lead to the same set of a posteriori probabilities. Furthermore, when

658

a given cryptogram is intercepted there is a set of messages that might have

produced this cryptogram (a “residue class”) and the a posteriori probabili-

ties of message in this class are proportional to the a priori probabilities. All

the information the enemy has obtained by intercepting the cryptogram is a

speciﬁcation of the residue class. Many of the common ciphers are pure sys-

tems, including simple substitution with random key. In this case the residue

class consists of all messages with the same pattern of letter repetitions as the

intercepted cryptogram.

Two systems

and

are deﬁned to be “similar” if there exists a ﬁxed

transformation

with an inverse,

, such that

If

and

are similar, a one-to-one correspondence between the resulting

cryptograms can be set up leading to the same a posteriori probabilities. The

two systems are cryptanalytically the same.

The second part of the paper deals with the problem of “theoretical se-

crecy.” How secure is a system against cryptanalysis when the enemy has

unlimited time and manpower available for the analysis of intercepted cryp-

tograms? The problem is closely related to questions of communication in

the presence of noise, and the concepts of entropy and equivocation devel-

oped for the communication problem ﬁnd a direct application in this part of

cryptography.

“Perfect Secrecy” is deﬁned by requiring of a system that after a cryp-

togram is intercepted by the enemy the a posteriori probabilities of this cryp-

togram representing various messages be identically the same as the a pri-

ori probabilities of the same messages before the interception. It is shown

that perfect secrecy is possible but requires, if the number of messages is ﬁ-

nite, the same number of possible keys. If the message is thought of as being

constantly generated at a given “rate”

(to be deﬁned later), key must be

generated at the same or a greater rate.

If a secrecy system with a ﬁnite key is used, and

letters of cryptogram

intercepted, there will be, for the enemy, a certain set of messages with cer-

tain probabilities that this cryptogram could represent. As

increases the

ﬁeld usually narrows down until eventually there is a unique “solution” to

the cryptogram; one message with probability essentially unity while all oth-

ers are practically zero. A quantity

is deﬁned, called the equivocation,

which measures in a statistical way how near the average cryptogram of

letters is to a unique solution; that is, how uncertain the enemy is of the orig-

inal message after intercepting a cryptogram of

letters. Various properties

of the equivocation are deduced—for example, the equivocation of the key

never increases with increasing

. This equivocation is a theoretical secrecy

659

index—theoretical in that it allows the enemy unlimited time to analyse the

cryptogram.

The function

for a certain idealized type of cipher called the ran-

dom cipher is determined. With certain modiﬁcations this function can be

applied to many cases of practical interest. This gives a way of calculating

approximately how much intercepted material is required to obtain a solution

to a secrecy system. It appears from this analysis that with ordinary languages

and the usual types of ciphers (not codes) this “unicity distance” is approxi-

mately

. Here

is a number measuring the “size” of the key space.

If all keys are a priori equally likely

is the logarithm of the number of

possible keys.

is the redundancy of the language and measures the amount

of “statistical constraint” imposed by the language. In simple substitution

with random key

is

or about

and

(in decimal digits per

letter) is about

for English. Thus unicity occurs at about 30 letters.

It is possible to construct secrecy systems with a ﬁnite key for certain

“languages” in which the equivocation does not approach zero as

. In

this case, no matter how much material is intercepted, the enemy still does

not obtain a unique solution to the cipher but is left with many alternatives, all

of reasonable probability. Such systems we call ideal systems. It is possible

in any language to approximate such behavior—i.e., to make the approach

to zero of

recede out to arbitrarily large

. However, such systems

have a number of drawbacks, such as complexity and sensitivity to errors in

transmission of the cryptogram.

The third part of the paper is concerned with “practical secrecy.” Two

systems with the same key size may both be uniquely solvable when

letters

have been intercepted, but differ greatly in the amount of labor required to

effect this solution. An analysis of the basic weaknesses of secrecy systems

is made. This leads to methods for constructing systems which will require a

large amount of work to solve. Finally, a certain incompatibility among the

various desirable qualities of secrecy systems is discussed.

PART I

MATHEMATICAL STRUCTURE OF SECRECY SYSTEMS

2 SECRECY SYSTEMS

As a ﬁrst step in the mathematical analysis of cryptography, it is necessary to

idealize the situation suitably, and to deﬁne in a mathematically acceptable

way what we shall mean by a secrecy system. A “schematic” diagram of a

general secrecy system is shown in Fig. 1. At the transmitting end there are

660

剩余59页未读，继续阅读

安全验证

文档复制为VIP权益，开通VIP直接复制

信息提交成功

## 评论2