C.E.Shannon-CommunicationTheoryofSecrecySystems

5星 · 超过95%的资源需积分: 16 89 浏览量更新于2023-05-19 评论 1 收藏 680KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

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

. 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

. 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.

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

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

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





is to be used with probabilities



and



, respectively. When this is done





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

 









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















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页未读，继续阅读

wys7011205

2014-10-27

文章很难找，谢谢楼主分享，就是分有点贵，嘿嘿

xwautumn

粉丝: 0
资源: 1

会员权益专享

C.E.Shannon-Communication Theory of Secrecy Systems

评论2

会员权益专享

最新资源

C.E.Shannon-Communication Theory of Secrecy Systems

评论2

qiime2 16s双端数据分析代码

Huffman与Shannon-Fano编码实验报告

shannon-wiener多样性指数

jensen-shannon divergence

鸟类多样性如何构建变系数模型

shannon小波连续变换 matlab代码

香农，费诺和赫夫曼编码代码

有哪些提供图像数据集的网站

gis计算土地利用多样性

给出代码，利用python绘制l香农熵

pywt库wavedec 的wavelet参数有哪些取值

请用python写一个计算图像熵的程序

已知一个三角波，其周期为T，当t=0时峰值为A，画出该波的频谱图

wgan-gp详细介绍

matlab离散对称信道的信道容量仿真

python中时间序列求熵

为什么adc采样频率要限定在400到1000000之间呢？

会员权益专享

最新资源