Ch2 Shannon 理论

*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,Ch 2 Shannon 理论,1,大纲,完善保密性,熵及其性质,伪密钥和唯一解距离,乘积密码体制,2,香农简介,香农(,1916-2001,),生于,美国,密执安州的加洛德。1940年获得麻省理工学院数学博士学位和电子工程硕士学位。1941年他加入了贝尔实验室数学部，在此工作了15年。,3,Shannon的保密系统信息理论,1949年， Shannon发表了一篇题为保密系统的信息理论的论文。,用信息论的观点对信息保密问题进行了全面的阐述。,宣告了科学的密码学时代的到来。,4,密码体制的安全性（1）,无条件安全或完善保密性（unconditionally secure）：,不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文；,具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统。,5,密码体制的安全性（2）,实际上安全,计算上是安全：算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。,可证明安全：从理论上证明破译它的计算量不低于解已知难题的计算量。,6,实例,移位密码、代换密码和维吉尼亚密码对惟密文攻击都不是计算上安全的。,后面将给出一个对惟密文攻击是无条件安全的密码体制。,7,完善保密性,通俗地讲，完善保密性就是第三方不能通过观察密文得到明文的任何信息。,定义：一个密码体制具有完善保密性，即如果对于任意的xP, y C, 都有,Pr(x|y)=Pr(x),8,明文元素定义了一个随机变量，用x表示；,密钥也定义了一个随机变量，用k表示；,P和K的概率分布导出了C的概率分布，故可将密文元素看成随机变量,。,即， 对每个密钥k， C(k)代表密钥是k时所有可能的密文。,9,概率公式,Pr( x, y)=Pr( x | y) Pr( y),=Pr( y| x )Pr( x),统计独立：,Pr( x| y)=Pr( x),Pr( x, y)=Pr( x) Pr( y),Bayes定理,10,定理 2.3,假设移位密码的26个密钥都是以相同的概率1/26使用的，则对于任意的明文概率分布，移位密码具有完善保密性。,11,Shannon完善保密定理,假设密码体制 (P, C, K, E, D)满足|K|=|C|=|P|.这个密码体制是完善保密的，当且仅当每个密钥被使用的概率都是1/|K|, 并且对于任意的x P, y C, 存在唯一的密钥k, 使得e,k,( x)=y,12,完善保密的例子一次一密,Gilbert Vernam 1917,一次一密：,P=C=K=(Z,2,),n, x=(x,1, , x,n,) P,Y=(y,1, , y,n,) C,e,k,( x)=(x,1,+ k,1, , x,n,+ k,n,) mod 2,d,k,( y)=(y,1,+ k,1, , y,n,+ k,n,) mod 2,13,密码体制的无条件安全是基于每个密钥仅用一次的事实。,一次一密对已知明文攻击 是脆弱的。,一个密钥加密多个明文信息会发生什么？在足够的时间下，进行一次惟密文攻击有多大的可能性？,14,大纲,完善保密性,熵及其性质,伪密钥和唯一解距离,乘积密码体制,15,熵及其性质,如何定量刻划一个随机事件包含的信息量？,用,熵,的概念!,16,谁,能提供信息?,我将你原来不知道的结果告诉你,就是提供了信息!,例1,当我给你一封信时，你就从我这里获得了信息，因为你事先并不知道其中的内容。,例2,设电脑彩票由8个10进制数组成,。,在开奖之前，我们不知道特等奖号码的信息，因为特等奖的号码是不确定。特等奖号码的信息只有在开奖时才获得。一旦开奖，就获得了8个十进制数的信息。,这就是说，,未知,(,不确定,),的,变成,已知,(,确定,),的,，在该过程中获得,了信息！,信息寓于不确定之中！,17,简单地说,信息就是:,(1),当未知的变成已知的,之后,获取的信息;,(2),当未知的还没变成已知,之前,包含的未知信息.,信息寓于不确定之中！,18,通常的信息是指:,(1) 一个实验提供的信息;,(2) 一个随机事件包含的信息;,(3) 一个随机变量包含的信息.,其中(1)和(2)的含义相同,它们比(3)的意义更,加广泛.,19,信息量,我向你提供的信息量就是你事先不知道结果的程度!也即是,信息的不确定度,。,如果你事先全知道了,说明我提供的信息量等于,0,;,如果你事先一无所知,说明我提供的信息量,最多,.,不知道意味着在我告诉你之前你只能,猜测,!,猜测就是按照每个可能结果的,出现概率,进行猜测!,你只知道这个事情的每个结果的发生概率!,所以,我提供的信息量,由,你事先知道的每个可能结果的发生概率,(,即随机事件的,概率分布,),决定,.,20,随机事件和随机变量,定义1：设一个实验有 共,n,个可能的结果，则每个可能结果都称为一个,事件,。这个实验也称为一个随机事件。,性质1：设X是一个离散随机变量，它有,n,个可能的取值，设每种取值出现的概率为p( x,i,),则,21,随机事件的熵,一个事件可能发生，也可能不发生！但我们总在每个事件 发生的概率 都已知的条件下分析！,这个实验提供的信息就是：,(1),实验前,该实验所包含的未知信息；,(2),实验后,这个实验所提供的信息.,如何对信息量的大小进行定量刻划?,再看一下彩票的例子.,22,例3,设电脑彩票由8个10进制数组成，在开奖之前，10,8,个可能号码成为特等奖的概率相同,都是10,-8,.一旦开奖,我们就知道了特等奖的8个具体号码,因而就获得了8个十进制数的信息。,我们获得的信息量与开奖前每个可能号码成为特等奖的概率10,-8,有何关系?,显然,有 8 = - log,10,10,-8,信息量的定量刻划:,定义2,设 是一个实验中事件 发生的概率,则称 为事件 包含的,自信息量,.,23,熵的数学定义,24,因此,一个实验的,熵,就是该实验的每个可能结果包含的,自信息量,的,平均值,!,熵的单位与对数的底有关!,约定对数的底大于1!,当以2为底时,其单位称为比特(bit);,当以10为底时,其单位称为迪特(Det);,25,例5,设一个实验有a和b两个可能的结果,且实验结果是a和b的概率分别为1/4和3/4,试计算该实验的熵.,解:,根据熵的定义,有,26,下面介绍熵的性质.,定义3,一个实值函数,f,称为在区间,I,上是凸的,如果对任意的,都有,如果对任意的,都有,则称,f,称为在区间,I,上是严格凸的.,27,28,29,30,定理3.1,设b1,则有,且,都有,(2),当且仅当,都有,(1),(3),当且仅当,存在,使得,证明,(1),由 可知,故(1)成立.,(2),由Jensen不等式的推论1可知(2)成立.,再由,Jensen,不等式的推论1,31,(3)充分性:,此时,必要性:,由于诸,设H(X)=0.,若存在t,使,则,从而,两个值,该矛盾说明诸 只能取0和1这,因而必要性成立.,.矛盾!,32,定理3.1说明:,(1) 结果确定的随机事件不提供信息,因而提供的信息量最少!,(2) 各可能的结果,等可能发生,的随机事件,提供的信息包含的信息量最大!,这与我们的直觉是一致的!,33,现实中的事件都不是孤立的! 很多随机事件之间都有相互的联系和影响!那么,如何刻划和研究多个随机事件相互提供的信息呢? 这就要引入两个实验的,联合熵,条件熵,互信息,等概念！,34,因此,实验X与实验Y的联合熵(Joint Entropy)就是事件(,x,i,y,j,),的自信息量的数学期望.,它反映了联合分布,p,(,x,y,),包含的信息量.,定义4,(联合熵): 实验X与实验Y的可能结果分别为 和 ,定义X与Y的联合熵 为,35,定义5,(条件熵): 实验X与实验Y的可能结果分别为 和 .定义X与Y的条件熵为,(1),称 为在实验Y的结果为,y,j,的条件下,事件,x,i,的,条件自信息量,.,为在实验Y的结果为,y,j,的条件下,实验X的,条件熵,.,(2)称,定义5,(条件熵): 实验X与实验Y的可能结果分别为 和 .定义X与Y的条件熵为,定义5,(条件熵): 实验X与实验Y的可能结果分别为 和 .,36,(3),称,为在实验X关于实验Y的,条件熵,.,反映了,Y,的结果是,y,j,条件下,实验X包含的信息量,.,反映了,Y,的结果已知条件下,实验X,平均,包含的信息量.,37,联合熵与各自的熵的关系,定理3.2,且等号成立的,充要条件是X与Y独立.,两个实验提供的信息总量一定不超过这两个实验分别提供的信息量之和;当且仅当两个实验独立时,二者才相等.,直观含义:,38,39,40,41,42,联合熵与条件熵的关系,定理3.3,直观含义:,两个实验提供的信息总量等于第一个信息提供的信息量加上在第一个实验的结果已知条件下,第二个实验提供的信息量.,43,联合熵与熵的关系,故有,定理3.2指出:,定理3.3指出:,推论3.1,且等号成立,X,与Y独立.,44,定义3.3(平均互信息): 称,为实验X与实验Y的平均互信息.,结论:,直观的含义：,将X包含的未知信息量减去在实验Y的结果已知条件下,X仍具有的未知信息量.,就是实验Y提供的X的信息了.,45,完善保密性的熵的定义,一个密码体制称为完善保密的，如果对于任意的xP和yC,有Pr(x|y)= Pr(x)。,一个保密系统（P，C，K，E，D）称为完善的无条件的保密系统，如果,H(P)=H(P|C),其中，P为明文集合，C为密文集合，K为密钥集合，E为加密算法,D为解密算法.,46,完善保密系统存在的必要条件是,H(P)H(K)。,可见，要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵。,从熵的基本性质可推知，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。,47,例子,书中例2.3 （P42 ,P47, P52）,48,大纲,完善保密性,熵及其性质,伪密钥和唯一解距离,乘积密码体制,49,密码体制组成部分的熵之间的关系,设 （P, C, K, E, D）是一个密码体制 ，则,H(K|C)=H(K)+H(P)-H(C),50,设(P, C, K, E, D)是给定的密码体制。利用联合熵的链规则，则有,H(P，C，K)=H(C)+H(K|C)+H(P|C，K),H(P，C，K)=H(K)+H(P|K)+H(C|P，K),因为密钥和明文唯一决定密文，而且密钥和密文唯一决定明文，所以H(P|C，K) = H(C|P，K) = 0。再假设密钥K的选择与明文P无关，即H(P|K) = H(P),所以，结合上面的几个等式，有,H(K|C) = H(K)+ H(P) -H(C),其中条件熵H(K|C)称为,密钥含糊度,，它给出,了在给定密文下密钥的不确定性的一种度量。,51,伪密钥,若,H(K |C)=0，则意味着密钥已找到密码体制被攻破。若H(K |C) 0，则意味着，给一段密文y，则存在两个或以上的密钥可被用来产生同一个密文y 。一般来说，Eve能排除某些密钥，但仍存在许多可能的密钥，这其中只有一个密钥是正确的。我们称那些可能的但不正确的密钥称为,伪密钥,。,52,例,设Eve知道Alice与Bob用英文通信，而且使用移位密码来加密通信的消息。如果Eve窃获了密文为y=WNAJW则用唯密文攻击，寻找伪密钥集合K(y)，应用26个字母与模Z,26,的对应，即,A0，B1,.,Z25,则密文,y=WNAJW对应于数字序列22，13，0，9，22。使用非零的移位，则有下表:,53,易知，,“river”和“arena”是可能的明文，因而可能的密钥是,k=5和k=22。,54,55,定理 2.11,假设(P, C, K, E, D)是一个密码体制，|C|=|P|并且密钥是等概率选取的，设RL表示 明文的自然语言的冗余度， 则给定一个充分长（长n）的密文串，伪密钥的期望满足,56,57,代换密码的唯一解距离,58,59,几点说明,:,（,1,）如何确定唯一密钥？确定过程实际上能否实现，这里并不关心。,一般而言，唯一解距离给出了穷举攻击时，可能解密出唯一有意义明文所需要的最少密文量。,（,2,）唯一解距离越长，系统越好。,唯一解距离未无穷大的密码系统定义为,理想保密,的。,（,3,）唯一解距离可保证当其太小时，密码系统是不安全的。,60,（,4） 当截获的密文长度大于唯一解距离时，理论上就可以破译，但一般破译所需的 密文量都远大于理论值；并且，这里没有涉及到为了得到唯一解所需要作出的努力，或需完成多少计算量，从实际来看，有时虽然截获的密文长度虽然远大于唯一解距离，但由于所需的工作量太大而难以实现破译。,（5） 没能将计算量考虑进去，是以信息理论 方法研究密码学的一个重要缺陷，为此，Shannon1949年提出了实际保密性的概念。,61,如何估计一个系统的实际保密性,密码分析者的计算能力（基本运算次数，存储量）,密码分析者所采用的 破译算法的有效性（新的破译手段）,密码设计者的任务是尽力设计一个理想的或完善的保密系统，即使做不到这点，也要保证使分析者必须付出相当的代价（时间、费用），甚至在受到密文量超过唯一解距离时，也能满足实际保密的要求。,62,大纲,完善保密性,熵及其性质,伪密钥和唯一解距离,乘积密码体制,63,乘积密码体制（,Product Cipher）,一个乘积密码就是一个明文x使用密码体制,S,1,= (P,1,，C,1,，K,1,，E,1,，D,1,),后得到密文y，再对密文y使用密码体制,S,2,= (P,2,，C,2,，K,2,，E,2,，D,2,),后而得到一个最后的密文。,64,一般地，若,S,2,S,1,S,1,S,2,，则称为乘积密码S,2,S,1,是非交换的，否则称为交换的。,一个密码体制,S,1,= (P,1,，C,1,，K,1,，D,1,，E,1,)称为幂等的，如果它满足条件: S,1,S,1,= S,1,65,66,Shannon关于设计密码的一些基本观点,通过合并简单密码系统而形成它们的积，特殊情况是一个非幂等的密码系统自身的乘积，而构造一个非幂等密码系统的常用技巧是：代换密码和置换密码的乘积。,67,Shannon关于设计密码的一些基本观点,挫败统计分析的方法：,在加密之前将语言的一些多余度除去，例如，在加密之前， 采用Huffman编码除去多余度。,采用所谓“扩散（diffusion）”和“混淆(confusion)”两种加密技术扩散或混淆多余度。,68,混淆和扩散原则,混淆：用于掩盖明文和密文之间的关系，使得密文和明文的统计特性之间的关系复杂化。,代换（替代）,扩散：将每一位明文数字的影响尽可能迅速地散布到较多个输出的密文数字中，以隐藏明文数字的统计特性。,置换（换位）,69,本章作 业,2.2,2.11,2.13,2.16,2.20,70,