Ch2 Shannon 理论.ppt

大纲 完善必威体育官网网址性 熵及其性质 伪密钥和唯一解距离 乘积密码体制 香农简介 香农(1916-2001),生于美国密执安州的加洛德。1940年获得麻省理工学院数学博士学位和电子工程硕士学位。1941年他加入了贝尔实验室数学部，在此工作了15年。 Shannon的必威体育官网网址系统信息理论 1949年， Shannon发表了一篇题为《必威体育官网网址系统的信息理论》的论文。 用信息论的观点对信息必威体育官网网址问题进行了全面的阐述。 宣告了科学的密码学时代的到来。 密码体制的安全性（1） 无条件安全或完善必威体育官网网址性（unconditionally secure）： 不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文； 具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统。 密码体制的安全性（2） 实际上安全 计算上是安全：算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。 可证明安全：从理论上证明破译它的计算量不低于解已知难题的计算量。 实例 移位密码、代换密码和维吉尼亚密码对惟密文攻击都不是计算上安全的。 后面将给出一个对惟密文攻击是无条件安全的密码体制。 完善必威体育官网网址性 通俗地讲，完善必威体育官网网址性就是第三方不能通过观察密文得到明文的任何信息。 定义：一个密码体制具有完善必威体育官网网址性，即如果对于任意的x∈P, y ∈C, 都有 Pr(x|y)=Pr(x) 明文元素定义了一个随机变量，用x表示； 密钥也定义了一个随机变量，用k表示； P和K的概率分布导出了C的概率分布，故可将密文元素看成随机变量。 概率公式 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定理 定理 2.3 假设移位密码的26个密钥都是以相同的概率1/26使用的，则对于任意的明文概率分布，移位密码具有完善必威体育官网网址性。 Shannon完善必威体育官网网址定理 假设密码体制 (P, C, K, E, D)满足|K|=|C|=|P|.这个密码体制是完善必威体育官网网址的，当且仅当每个密钥被使用的概率都是1/|K|, 并且对于任意的x ∈P, y ∈C, 存在唯一的密钥k, 使得e k( x)=y 完善必威体育官网网址的例子——一次一密 Gilbert Vernam 1917 一次一密： P=C=K=(Z2)n, x=(x1, …, x n) ∈P, Y=(y1, …, y n) ∈C e k( x)=(x1+ k1, …, x n+ k n) mod 2 d k( y)=(y1+ k1, …, y n+ k n) mod 2 密码体制的无条件安全是基于每个密钥仅用一次的事实。 一次一密对已知明文攻击 是脆弱的。 一个密钥加密多个明文信息会发生什么？在足够的时间下，进行一次惟密文攻击有多大的可能性？ 大纲 完善必威体育官网网址性 熵及其性质 伪密钥和唯一解距离 乘积密码体制 熵及其性质 如何定量刻划一个随机事件包含的信息量？ 用熵的概念! 随机事件和随机变量 定义1：设一个实验有 共n个可能的结果，则每个可能结果都称为一个事件。这个实验也称为一个随机事件。 性质1：设X是一个离散随机变量，它有n个可能的取值　　　　　，设每种取值出现的概率为p( xi),则 熵的数学定义 完善必威体育官网网址性的熵的定义 一个密码体制称为完善必威体育官网网址的，如果对于任意的x∈P和y∈C,有Pr(x|y)= Pr(x)。 一个必威体育官网网址系统（P，C，K，E，D）称为完善的无条件的必威体育官网网址系统，如果H(P)=H(P|C),其中，P为明文集合，C为密文集合，K为密钥集合，E为加密算法,D为解密算法. 例子 书中例2.3 （P42 ,P47, P52） 大纲 完善必威体育官网网址性 熵及其性质 伪密钥和唯一解距离 乘积密码体制 密码体制组成部分的熵之间的关系 设 （P, C, K, E, D）是一个密码体制 ，则 H(K|C)=H(K)+H(P)-H(C) 定理 2.11 假设(P, C, K, E, D)是一个密码体制，|C|=|P|并且密钥是等概率选取的，设RL表示 明文的自然语言的冗余度， 则给定一个充分长（长n）的密文串，伪密钥的期望满足 （4） 当截获的密文长度大于唯一解距离时，理论上就可以破译，但一般破译所需的 密文量都远大于理论值；并且，这里没有涉及到为了得到唯一解所需要作出的努力，或需完成多少计算量，从实际来看，有时虽然截获的密文长度虽然远大于唯一解距离，但由于所需的工作量太大而难以实现破译。 （5） 没能将计算量考虑进去，是以信息理