Ch2Shannon理论.ppt

Ch 2 Shannon 理论理论1大纲大纲n完善保密性n熵及其性质n伪密钥和唯一解距离n乘积密码体制2香农简介香农简介 香香 农农(1916-2001),生生 于于美美 国国密密执执安安州州的的加加洛洛德德1940年年获获得得麻麻省省理理工工学学院院数数学学博博士士学学位位和和电电子子工工程程硕硕士士学学位位1941年年他他加加入入了了贝贝尔尔实实验验室室数数学学部部，，在在此此工工作作了了15年年 3Shannon的保密系统信息理论的保密系统信息理论n1949年， Shannon发表了一篇题为《保密系统的信息理论》的论文 n用信息论的观点对信息保密问题进行了全面的阐述 n宣告了科学的密码学时代的到来 4密码体制的安全性（1）n无条件安全或完善保密性（unconditionally secure）：n n不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文；n n具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统5密码体制的安全性（2）n n实际上安全n n计算上是安全：算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。

n n可证明安全：从理论上证明破译它的计算量不低于解已知难题的计算量6实例实例n移位密码、代换密码和维吉尼亚密码对惟密文攻击都不是计算上安全的n后面将给出一个对惟密文攻击是无条件安全的密码体制7完善保密性完善保密性n通俗地讲，完善保密性就是第三方不能通过观察密文得到明文的任何信息n定义：一个密码体制具有完善保密性，即如果对于任意的x∈P, y ∈C, 都有 Pr(x|y)=Pr(x)8n n明文元素定义了一个随机变量，用x表示；n n密钥也定义了一个随机变量，用k表示；n nP和K的概率分布导出了C的概率分布，故可将密文元素看成随机变量即， 对每个密钥k， C(k)代表密钥是k时所有可能的密文9概率公式概率公式nPr( x, y)=Pr( x | y) Pr( y) =Pr( y| x )Pr( x)n统计独立：Pr( x| y)=Pr( x)Pr( x, y)=Pr( x) Pr( y)nBayes定理10定理定理 2.3n假设移位密码的26个密钥都是以相同的概率1/26使用的，则对于任意的明文概率分布，移位密码具有完善保密性11Shannon完善保密定理完善保密定理n假设密码体制 (P, C, K, E, D)满足|K|=|C|=|P|.这个密码体制是完善保密的，当且仅当每个密钥被使用的概率都是1/|K|, 并且对于任意的x ∈P, y ∈C, 存在唯一的密钥k, 使得e k( x)=y12完善保密的例子完善保密的例子——一次一密一次一密nGilbert Vernam 1917n一次一密：P=C=K=(Z2)n, x=(x1, …, x n) ∈P,Y=(y1, …, y n) ∈Ce k( x)=(x1+ k1, …, x n+ k n) mod 2d k( y)=(y1+ k1, …, y n+ k n) mod 213n密码体制的无条件安全是基于每个密钥仅用一次的事实。

n一次一密对已知明文攻击 是脆弱的n一个密钥加密多个明文信息会发生什么？在足够的时间下，进行一次惟密文攻击有多大的可能性？14大纲大纲n完善保密性n熵及其性质n伪密钥和唯一解距离n乘积密码体制15熵及其性质熵及其性质n如何定量刻划一个随机事件包含的信息量？n用熵熵的概念!16谁谁能提供信息能提供信息?• 我将你原来不知道的结果告诉你,就是提供了信息! 例例1 当我给你一封信时，你就从我这里获得了信息，因为你事先并不知道其中的内容 例例2 设电脑彩票由8个10进制数组成在开奖之前，我们不知道特等奖号码的信息，因为特等奖的号码是不确定特等奖号码的信息只有在开奖时才获得一旦开奖，就获得了8个十进制数的信息 这就是说，这就是说，未知未知(不确定不确定)的的变成变成已知已知(确定确定)的的，，在该过程中获得在该过程中获得了信息！了信息！ 信息寓于不确定之中！信息寓于不确定之中！17简单地说简单地说,信息就是信息就是: (1) 当未知的变成已知的当未知的变成已知的之后之后获取的信息获取的信息; (2) 当未知的还没变成已知当未知的还没变成已知之前之前包含的未知信息包含的未知信息.信息寓于不确定之中！信息寓于不确定之中！18通常的信息是指通常的信息是指: (1) 一个实验提供的信息一个实验提供的信息; (2) 一个随机事件包含的信息一个随机事件包含的信息; (3) 一个随机变量包含的信息一个随机变量包含的信息.　　　其中　　　其中(1)和和(2)的含义相同的含义相同,它们比它们比(3)的意义的意义更　　更　　 加广泛加广泛. 19信息量信息量•我向你提供的信息量就是你事先不知道结果的程度!也即是信息的不确定度信息的不确定度。

•如果你事先全知道了,说明我提供的信息量等于0 0;•如果你事先一无所知,说明我提供的信息量最多最多.•不知道意味着在我告诉你之前你只能猜测猜测!•猜测就是按照每个可能结果的出现概率出现概率进行猜测!•你只知道这个事情的每个结果的发生概率!•所以,我提供的信息量由由你事先知道的每个可能结果的发生概率(即随机事件的概率分布概率分布)决定决定.20随机事件和随机变量随机事件和随机变量定义定义1：设一个实验有：设一个实验有 共共n个可能个可能的结果，则每个可能结果都称为一个的结果，则每个可能结果都称为一个事件这个实验也称为一个随机事件这个实验也称为一个随机事件性质性质1：设：设X是一个离散随机变量，它有是一个离散随机变量，它有n个可个可能的取值　　　　　，设每种取值出现的能的取值　　　　　，设每种取值出现的概率为概率为p( xi),则则21 随机事件的熵随机事件的熵 一个事件可能发生，也可能不发生！但我们总在一个事件可能发生，也可能不发生！但我们总在每个事件每个事件 发生的概率发生的概率 都已知的条件下都已知的条件下分析！分析！ 这个实验提供的信息就是：这个实验提供的信息就是： (1) 实验前实验前该实验所包含的未知信息；该实验所包含的未知信息； (2) 实验后实验后这个实验所提供的信息这个实验所提供的信息. 如何对信息量的大小进行定量刻划如何对信息量的大小进行定量刻划? 再看一下彩票的例子再看一下彩票的例子.22例例3 设电脑彩票由设电脑彩票由8个个10进制数组成，在开奖之前，进制数组成，在开奖之前，108个可能号码成为特等奖的概率相同个可能号码成为特等奖的概率相同,都是都是10-8.一一旦开奖旦开奖,我们就知道了特等奖的我们就知道了特等奖的8个具体号码个具体号码,因而就因而就获得了获得了8个十进制数的信息。

个十进制数的信息 我们获得的信息量与开奖前每个可能号码成为我们获得的信息量与开奖前每个可能号码成为特等奖的概率特等奖的概率10-8有何关系有何关系? 显然显然,有有 8 = - log10 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 设设b>1,则有则有 且,都有(2) 当且仅当且仅当当,都有(1)(3) 当且仅当当且仅当存在使得证明证明 (1) 由由 可知可知故(1)成立.　　　　 (2) 由由Jensen不等式的推论不等式的推论1可知可知(2)成立成立., ,再由再由Jensen　　不等式的推论131(3)(3)充分性充分性: :此时必要性必要性: :由于诸设H(X)=0.若存在t,使,则,从而两个值,该矛盾说明诸 只能取0和1这因而必要性成立..矛盾!32 定理定理3.1说明说明: (1) 结果确定的随机事件不提供信息结果确定的随机事件不提供信息, 因而提供的信息量最少因而提供的信息量最少! (2) 各可能的结果各可能的结果等可能发生等可能发生的随机事件的随机事件 提供的信息包含的信息量最大提供的信息包含的信息量最大! 这与我们的直觉是一致的这与我们的直觉是一致的!33 现实中的事件都不是孤立的现实中的事件都不是孤立的! 很多随机很多随机事件之间都有相互的联系和影响事件之间都有相互的联系和影响!那么那么,如何如何刻划和研究多个随机事件相互提供的信息呢刻划和研究多个随机事件相互提供的信息呢? 这就要引入两个实验的这就要引入两个实验的联合熵联合熵条件熵条件熵 互信息互信息等概念！等概念！34 因此因此,实验实验X与实验与实验Y的联合熵的联合熵(Joint Entropy)就是事件就是事件(xi ,yj )的自信息量的数学的自信息量的数学期望期望. 它反映了联合分布它反映了联合分布p(x, y )包含的信息量包含的信息量. 定义定义4(联合熵联合熵): 实验实验X与实验与实验Y的可能结果分别的可能结果分别为为 和和 ,定义定义X与与Y的联合熵的联合熵 为为35 定义定义5(条件熵条件熵): 实验实验X与实验与实验Y的可能结果分别的可能结果分别为为 和和 .定义定义X与与Y的条件熵为的条件熵为 (1) 称称 为在实验为在实验Y的结果为的结果为 yj的条件下的条件下,事件事件xi的的条件自信息量条件自信息量.　　　为在实验　为在实验Y的结果为的结果为yj的条件下的条件下,实验实验X的的条件熵条件熵. (2)称称 定义定义5(条件熵条件熵): 实验实验X与实验与实验Y的可能结果分别的可能结果分别为为 和和 .定义定义X与与Y的条件熵为的条件熵为 定义定义5(条件熵条件熵): 实验实验X与实验与实验Y的可能结果分别的可能结果分别为为 和和 .36(3) 称称为在实验为在实验X关于实验关于实验Y的的条件熵条件熵.反映了反映了Y的结果是的结果是yj条件下条件下,实验实验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完善保密性的熵的定义完善保密性的熵的定义n n一个密码体制称为完善保密的，如果一个密码体制称为完善保密的，如果对于任意的对于任意的x∈∈P和和y∈∈C,有有Pr(x|y)= Pr(x)。

n n一个保密系统（一个保密系统（P，，C，，K，，E，，D）称）称为完善的无条件的保密系统，如果为完善的无条件的保密系统，如果H(P)=H(P|C),其中，其中，P为明文集合，为明文集合，C为密文集合，为密文集合，K为密钥集合，为密钥集合，E为加密为加密算法算法,D为解密算法为解密算法.46n n完善保密系统存在的必要条件是完善保密系统存在的必要条件是H(P)≤H(K)n n可见，要构造一个完善保密系统，其可见，要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵的条件下）必须不小于明文集的熵 n n从熵的基本性质可推知，保密系统从熵的基本性质可推知，保密系统的密钥量越小，其密文中含有的关的密钥量越小，其密文中含有的关于明文的信息量就越大于明文的信息量就越大 47例子例子n书中例2.3 （P42 ,P47, P52）48大纲大纲n完善保密性n熵及其性质n伪密钥和唯一解距离n乘积密码体制49密码体制组成部分的熵之间的关系密码体制组成部分的熵之间的关系n设 （P, C, K, E, D）是一个密码体制 ，则H(K|C)=H(K)+H(P)-H(C)50n n设设(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)n n因为密钥和明文唯一决定密文，而且密钥因为密钥和明文唯一决定密文，而且密钥和密文唯一决定明文，所以和密文唯一决定明文，所以H(P|C，，K) = H(C|P，，K) = 0再假设密钥再假设密钥K的选择与明的选择与明文文P无关，即无关，即H(P|K) = H(P)n n所以，结合上面的几个等式，有所以，结合上面的几个等式，有H(K|C) = H(K)+ H(P) -H(C)其中条件熵其中条件熵H(K|C)称为称为密钥含糊度密钥含糊度，它给出，它给出了在给定密文下密钥的不确定性的一种度量了在给定密文下密钥的不确定性的一种度量51伪密钥n n若H(K |C)=0，则意味着密钥已找到密码体，则意味着密钥已找到密码体制被攻破若制被攻破若H(K |C)> 0，则意味着，给，则意味着，给一段密文一段密文y，则存在两个或以上的密钥可被，则存在两个或以上的密钥可被用来产生同一个密文用来产生同一个密文y 一般来说，。

一般来说，Eve能能排除某些密钥，但仍存在许多可能的密钥，排除某些密钥，但仍存在许多可能的密钥，这其中只有一个密钥是正确的我们称那这其中只有一个密钥是正确的我们称那些可能的但不正确的密钥称为些可能的但不正确的密钥称为伪密钥伪密钥52n n例 设设Eve知道知道Alice与与Bob用英文通信，用英文通信，而且使用移位密码来加密通信的消息而且使用移位密码来加密通信的消息如果如果Eve窃获了密文为窃获了密文为y=WNAJW则用则用唯密文攻击，寻找伪密钥集合唯密文攻击，寻找伪密钥集合K(y)，应，应用用26个字母与模个字母与模Z26的对应，即的对应，即n nA↔0，，B↔1,…..,Z↔25n n则密文y=WNAJW对应于数字序列对应于数字序列22，，13，，0，，9，，22使用非零的移位，则有使用非零的移位，则有下表下表:53易知，“river”和和“arena”是可能的明文，因而可能的是可能的明文，因而可能的密钥是密钥是k=5和和k=225455定理定理 2.11 n n假设(P, C, K, E, D)是一个密码体制，|C|=|P|并且密钥是等概率选取的，设RL表示 明文的自然语言的冗余度， 则给定一个充分长（长n）的密文串，伪密钥的期望满足5657代换密码的唯一解距离代换密码的唯一解距离5859 几点说明几点说明: n （（1）如何确定唯一密钥？确定过程实际上能否）如何确定唯一密钥？确定过程实际上能否实现，这里并不关心。

实现，这里并不关心 一般而言，唯一解距离给出了穷举攻击时，可能一般而言，唯一解距离给出了穷举攻击时，可能解密出唯一有意义明文所需要的最少密文量解密出唯一有意义明文所需要的最少密文量 n （（2）唯一解距离越长，系统越好唯一解距离越长，系统越好 唯一解距离未无穷大的密码系统定义为唯一解距离未无穷大的密码系统定义为理想保理想保密密的n （（3）唯一解距离可保证当其太小时，密码系统）唯一解距离可保证当其太小时，密码系统是不安全的是不安全的 60n n（4）） 当截获的密文长度大于唯一解距离时，当截获的密文长度大于唯一解距离时，理论上就可以破译，但一般破译所需的理论上就可以破译，但一般破译所需的 密密文量都远大于理论值；并且，这里没有涉文量都远大于理论值；并且，这里没有涉及到为了得到唯一解所需要作出的努力，及到为了得到唯一解所需要作出的努力，或需完成多少计算量，从实际来看，有时或需完成多少计算量，从实际来看，有时虽然截获的密文长度虽然远大于唯一解距虽然截获的密文长度虽然远大于唯一解距离，但由于所需的工作量太大而难以实现离，但由于所需的工作量太大而难以实现破译。

破译n n（（5）） 没能将计算量考虑进去，是以信息理没能将计算量考虑进去，是以信息理论论 方法研究密码学的一个重要缺陷，为此，方法研究密码学的一个重要缺陷，为此，Shannon1949年提出了实际保密性的概念年提出了实际保密性的概念61如何估计一个系统的实际保密性如何估计一个系统的实际保密性n n密码分析者的计算能力（基本运算次数，存储量）密码分析者的计算能力（基本运算次数，存储量）密码分析者的计算能力（基本运算次数，存储量）密码分析者的计算能力（基本运算次数，存储量）n n密码分析者所采用的密码分析者所采用的密码分析者所采用的密码分析者所采用的 破译算法的有效性（新的破破译算法的有效性（新的破破译算法的有效性（新的破破译算法的有效性（新的破译手段）译手段）译手段）译手段）n n密码设计者的任务是尽力设计一个理想的或完善密码设计者的任务是尽力设计一个理想的或完善密码设计者的任务是尽力设计一个理想的或完善密码设计者的任务是尽力设计一个理想的或完善的保密系统，即使做不到这点，也要保证使分析的保密系统，即使做不到这点，也要保证使分析的保密系统，即使做不到这点，也要保证使分析的保密系统，即使做不到这点，也要保证使分析者必须付出相当的代价（时间、费用），甚至在者必须付出相当的代价（时间、费用），甚至在者必须付出相当的代价（时间、费用），甚至在者必须付出相当的代价（时间、费用），甚至在受到密文量超过唯一解距离时，也能满足实际保受到密文量超过唯一解距离时，也能满足实际保受到密文量超过唯一解距离时，也能满足实际保受到密文量超过唯一解距离时，也能满足实际保密的要求。

密的要求密的要求密的要求62大纲大纲n完善保密性n熵及其性质n伪密钥和唯一解距离n乘积密码体制63乘积密码体制乘积密码体制（（Product Cipher）一个乘积密码就是一个明文一个乘积密码就是一个明文x使用密码体制使用密码体制S1 = (P1，，C1，，K1，，E1，，D1)后得到密文后得到密文y，再对密文，再对密文y使用密码体制使用密码体制S2 = (P2，，C2，，K2，，E2，，D2)后而得到一个最后的密文后而得到一个最后的密文64n n一般地，若S2S1 ≠S1S2，则称为乘积密，则称为乘积密码码S2S1是非交换的，否则称为交换的是非交换的，否则称为交换的n n一个密码体制S1= (P1，，C1，，K1，，D1，，E1)称为幂等的，如果它满足条件称为幂等的，如果它满足条件: S1S1 = S16566Shannon关于设计密码的一些关于设计密码的一些基本观点基本观点n通过合并简单密码系统而形成它们的积，特殊情况是一个非幂等的密码系统自身的乘积，而构造一个非幂等密码系统的常用技巧是：代换密码和置换密码的乘积67Shannon关于设计密码的一些关于设计密码的一些基本观点基本观点n挫败统计分析的方法：Ø在加密之前将语言的一些多余度除去，例如，在加密之前， 采用Huffman编码除去多余度。

Ø采用所谓“扩散（diffusion）”和“混淆(confusion)”两种加密技术扩散或混淆多余度68混淆和扩散原则混淆和扩散原则n n混淆：用于掩盖明文和密文之间的关系，混淆：用于掩盖明文和密文之间的关系，使得密文和明文的统计特性之间的关系复使得密文和明文的统计特性之间的关系复杂化n n代换（替代）代换（替代）n n扩散：将每一位明文数字的影响尽可能迅扩散：将每一位明文数字的影响尽可能迅速地散布到较多个输出的密文数字中，以速地散布到较多个输出的密文数字中，以隐藏明文数字的统计特性隐藏明文数字的统计特性n n置换（换位）置换（换位）69本章作本章作 业业n2.2n2.11n2.13n2.16n2.2070。