第5讲--Shannon理论2.ppt

解放军信息工程大学电子技术学院 * * 定理3.1 设b1,则有 且 ,都有 (2) 当且仅当 ,都有 (1) (3) 当且仅当存在 使得 上节内容回顾 熵: * * 上节内容回顾 定理3.3 推论3.1 且等号成立 X与Y独立. 定理3.2: 且等号成立 X与Y独立. 联合熵: 条件熵: 结论: 且等号成立 X与Y独立. 平均互信息: §3.3 伪密钥和唯一解距离 主要内容: 利用Shannon信息论,研究密文、明文和密钥的信息量。 分析唯密文攻击条件下要唯一确定密钥时至少需要的密文长度。 定理3.4 设M,K,C分别是明文空间、密钥空间和密文空间上的随机变量，则有 截获密文后密钥的未知信息量等于明文与密钥总的未知信息量减去从已知的密文中获得的信息量。 直观含义: 定理3.4 设M,K,C分别是明文空间、密钥空间和密文空间上的随机变量，则有 根据条件熵与联合熵之间的关系,有 证明: 由于知道密文和密钥,自然也知道明文,因而密钥和密文都知道时提供的信息量H(K,C)等于密钥、密文和明文都知道时提供的信息量H(K,M,C),即 下证之. 由 和条件熵与联合熵的关系知 同理,有 ,故由密钥与明文独立知 截获密文C后,就可将密钥唯一确定等价于 下面根据这个条件,计算至少需要多少密文才能将密钥唯一确定. 将密钥唯一确定所需要的最少的密文的数量,就称为该密码体制的唯一解距离（唯一解码量）. 要求唯一解距离,需要首先计算出n长明文M的熵H(M)和n长密文的熵H(C). 定理3.4说明: 截获密文C后,就可将密钥唯一确定等价于 (A) n长密文熵的计算 我们需要做一个合理的假设: 假设: 密文是随机的! 设密文字母表为Y,则n长密文就是由字母表Y中n 个字母 组成的密文字母串 . 结论: 设n长密文服从均匀分布,则n长密文的熵为 证明: 因n长密文共有 个,从而由n长密文服从均匀分布和熵的性质知 如何刻划明文本身包含的未知信息量呢?我们 给出如下的定义： 设明文字母表为X,则n长明文就是由字母表X中n 个字母 组成的明文字母串 . (B) n长明文熵的计算 定义3.5 （2）设L是一种语言,则称 为该语言L的冗余度(Redundancy) . 其中，X表示语言L的字母表，X(n)是Xn上的随 机变量. 定义3.5 (1) 设L是一种语言,则称 为该语言L的(单字母)熵. * * 例1 如果由64个二进制数构成的某类密钥 的熵平均是56比特,则该类密钥的熵为0.875比特. 例2 如果由64个二进制数构成的某类密钥的熵平均是56比特,则该类密钥的冗余度是 1 - 0.875 = 0.125 比特 即:平均每个密钥比特有0.125个比特是多余的. HL表示自然语言L中每个字母的熵，它是“有意义的”明文字母串中每个字母的平均信息量的度量.对于字母表X上的一个随机语言，因为X(n)是Xn上的均匀随机变量，所以， 随机语言L的熵为 且当n很大时,近似有 截获密文C后,就可将密钥唯一确定等价于 定理3.4说明: 截获密文C后,就可将密钥唯一确定等价于 下面转到分析需要截获多少密文才能将密钥唯一确定的问题. 当截获n长明文X(n)对应的 n长密文Y(n)后,就可将密钥的信息全部确定等价于 现设 , 则有 从而 即 也就是说,当截获 个密文字母后,就可将密钥的信息全部确定. 设已知密文C(n)及对应的明文M(n).由于明文M(n)是已知的,因而此时该明文的熵H(M(n))=0,因而