第4章 信息理论《密码学：加密演算法》(邓安文)(免费)

返回总目录第4章信息理论1.2©2006第4章信息理论教学目的•回忆概率的基本概念和定理•了解什么是完美秘密？•了解熵•了解自然之熵1.3©2006第4章信息理论概率本章内容完美秘密熵自然之熵1.4©2006第4章信息理论概率4.1概率定义令S为一非空的有限集合，称为样本空间（SampleSpace），其部分集合称为事件（Events）。在样本空间上的概率分布（ProbabilityDistribution）即用一个函数p将事件映至某实数，Sp:2（其中表S的幂集合，即）满足下列各条件：S2{M|MS}（1）对所有的事件（2）（3）当两事件与互斥（即）若A为事件，则p(A)为此事件的概率。p(A)0ASp(S)1p(AB)p(A)p(B)AB1.5©2006第4章信息理论概率的性质♫性质（1）（2）若则（3）当（4）（5）若均两两相斥，则（6）p()0ABp(A)p(B)0p(A)1ASp(S\A)1p(A)12nAAA、、、nniii1i1p(A)p(A)aAp(A)p(a)＝其中p(a)p({a})1.6©2006第4章信息理论条件概率和独立事件定义条件概率，ConditionalProbability令A与B为事件，且，A在条件B成立下的条件概率定义为p(B)0p(AB)p(A|B)p(B)定义两事件A与B称为独立事件（IndependentEvents）p(AB)p(A)p(B)此等式也等价于p(A|B)p(A)若等式不成立，则称A与B为相依事件（DependentEvents）1.7©2006第4章信息理论Bayes定理Bayes定理若A与B为事件，且，，则p(A)0p(B)0p(B)p(A|B)p(A)p(B|A)证明：由条件概率的定义，得：p(A|B)p(B)p(AB)p(B|A)p(A)p(AB)p(B)p(A|B)p(A)p(B|A)和因此：1.8©2006第4章信息理论完美秘密4.2完美秘密定义：一个密码系统定义为完美秘密（PerfectSecrecy）所有给定密文出现的事件与所有特定明文出现的事件，皆是独立事件。对所有明文m以及所有密文c皆成立。p(m|c)p(m)Shannon定理令（所有密文的可能数目等于所有密钥的可能数目）且任一明文m出现的概率均为正数，即。此密码系统为完美秘密下列条件皆成立：##CKp(m)0（1）在密钥空间上的概率分布函数为pK均匀分布。（2）对任一明文m以及任一密文c，均恰好仅存在一把密钥k使得kE(m)c1.9©2006第4章信息理论熵4.3熵定义熵，Entropy令A为样本空间，X为定义在样本空间上的随机变量，则随机变量X的熵定义为2xAH(X)p(Xx)log(p(Xx))定义连接熵，JointEntropy令X与Y为样本空间A与B上的随机数，则连接熵H（X，Y）定义为XY2XY(x,y)ABH(X,Y)p(x,y)log(p(x,y))1.10©2006第4章信息理论条件熵定义条件熵，ConditionalEntropy令X与Y为样本空间A与B上的随机数，则在条件X下的Y条件熵定义为XxAXY2YxAyBXY2Y(x,y)ABH(Y|X)p(x)H(Y|Xx)p(x)p(y|x)logp(y|x)p(x,y)logp(y|x)。1.11©2006第4章信息理论链式规则定理链式规则，ChainRuleH(X,Y)H(X)H(Y|X)证明：XY2XY(x,y)ABH(X,Y)p(x,y)logp(x,y)XY2XY(x,y)ABp(x,y)logp(x)p(y|x)XY2X(x,y)ABp(x,y)logp(x)XY2Y(x,y)ABp(x,y)logp(y|x)2XXYxAyBlogp(x)p(x,y)H(Y|X)X2XxAp(x)logp(x)H(Y|X)XYXyBp(x,y)p(x)H(X)H(Y|X)条件概率定义指数律1.12©2006第4章信息理论熵♫性质（1），“=”成立当样本空间A的各元素出现的概率相同。（2）。（3），“=”成立当X与Y为独立事件。H(X)log2|A|H(X,Y)H(X)H(Y)H(Y|X)H(Y)定理令M为明文空间M的随机变量，C为密文空间C的随机变量。密码系统为完美秘密。H(M|C)H(M)1.13©2006第4章信息理论熵定理H(K|C)H(K)H(M)H(C)证明：H(K,M,C)=H(M,K)+H(C|M,K)H(M,K)(H(C|M,K)=0)H(K)H(M)链式规则K与M为独立事件H(K,M,C)=H(K,C)+H(M|K,C)H(K,C)(H(M|K,C)=0)H(C)H(K|C)链式规则故由链式规则H(K|C)H(K,C)H(C)H(K)H(M)H(C)1.14©2006第4章信息理论自然语言之熵4.4自然语言之熵定义假密钥，SpuriousKey令为含n个字元的某密文。令c，其中m为符合语法，有意义的明文}为产生密文c的假密钥的集合。ncCk(c):{k|E(m)K定义自然语言熵，EntropyoftheNaturalLanguage令M为某自然语言的字母集合，Mn表长度为n的各种不同字母排列。该自然语言L之熵值定义为：nLnH()HlimnM此处熵值HL就是该自然语言的熵值；而由此M中字母所产生的随机信息熵是log2|M|，该自然语言的“重复率”（Redundancy）可定义为：L2HR1log||M1.15©2006第4章信息理论Unicity距离定义Unicity距离n0，就是该密码系统所产生密文而惟一决定惟一密钥值的密文长度。定理Unicity距离n0估计为：202log||nRlog||KM其中|K|表示所有可能的密钥数，而|M|表示所有的字母总数，R即重复率。1.16©2006第4章信息理论Unicity距离示例例：（恺撒挪移）此时可能的密钥总数|K|=26，（含未加密）故Unicity距离为：202log26n1.330.75log26（仿射密码）此时可能密钥总数|K|=12×26=312，（含未加密）故：例：202log312n2.350.75log26若Alice以单次密码本加密法将长度为二元字串信息加密，传讯给Bob。其中可能密钥总数（含未加密）为|K|=2n，Eve计算n202log2n1.33nn0.75log2例：