信息论 第五讲 完善保密.ppt

1张焕国张焕国武汉大学计算机学院武汉大学计算机学院信息论博士课程: 博士课程: 2 目录第一部分密码 1、通信系统的数学模型 2、自信息和熵 3、互信息 4、信源编码 5、完善保密 3 目录第二部分纠错码 1、纠错编码的基本概念 2、线性分组码的基本理论 3、线性分组码在计算机系统中的应用 4、循环码的基本理论 5、典型循环码及应用 4五、完善保密 1、密码分析?密码分析的概念: ?密码分析俗称密码破译或密码攻击。?如果能够系统地获得明文或密钥,则称破译了该密码。?密码分析的方法: 穷举攻击,统计分析,数学分析?密码分析假设: ①攻击者可获得任何密文和部分明文②攻击者知道密码算法③攻击者拥有足够的计算资源?根据分析者可用的数据资源分类: ①仅知密文攻击; 对攻击者最不利②已知明文攻击;攻击者知道了部分密文和相应的明文(不是全部) ③选择明文攻击; 对攻击者最有利④选择密文攻击。对签名攻击 5 1、密码分析?密码分析的概念: ?一个密码系统,说它是完善保密的(或称是无条件安全的) : ?既使密码分析者拥有无限的密文资源和计算资源(诸如时间、空间、设备等)也无法破译该密码。?保密系统的安全性通常是针对某种类型的攻击的?本节研究仅知密文攻击下保密系统的完善保密性, ?所得结果不一定能适合已知明文攻击或选择明文攻击。五、完善保密 6 1、密码分析?保密系统框图信源加密器信道信宿解密器 mm 加密钥解密钥安全信道 k ek d对称密码 k e=k e五、完善保密 7 1、密码分析?密码系统的数学描述:{ M,C,K,E,D } M:明文空间,一切明文的集合; C :密文空间,一切密文的集合; K :密钥空间,一切密钥的集合; E:加密算法,加密变换的集合; D :解密算法,它是加密算法的逆。五、完善保密 8 1、密码分析?密码分析的数学描述: ?信息论指出:对一个给定的保密系统,由系统一部分的熵和互信息,可计算出系统中各部分的熵。?记明文空间的熵为 H(M),密钥空间的熵为 H(K ),密文空间的熵为 H(C)。?记已知密文条件下明文的含糊度为 H( M/C ),已知密文条件下密钥的含糊度为 H( K/C )。?密码分析问题: ①从仅知密文攻击来看,密码分析者的任务是从截获的密文中提取有关明文的信息: I( M,C ) =H (M) -H ( M/C ) ②或从密文中提取有关密钥的信息: I( K,C ) =H (K) -H ( K/C ) (5-1) (5-2) 根据式(3-15) I(X,Y )=H(X)- H(X/Y) 五、完善保密 9 1、密码分析?密码分析的数学描述: ?上两式表明, H( M/C ) 和H( K/C ) 越大,窃听者从密文能获得的有关明文和密钥的信息就越少。?对于合法的接收者,由于已知密文和密钥,根据加密变换的可逆性可知H(M/ CK )=0 这是因为已知密文和密钥的条件下,解密出明文是确定的,概率为 1, 所以熵为 0。?于是,根据式( 5-1 )有 I( M,CK ) =H (M) -H ( M/CK ) = H(M)这表明, 在已知密文和密钥条件下,合法接收者可完全提取明文信息。(5-3) (5-4) 五、完善保密 10 1、密码分析?定理 对任意保密系统都有: I( M,C )≥ H(M) -H (K) ?证明由式( 5-3 )知道 H(M/ CK )=0 ,于是 H(K/C)=H(K/C)+H(M/KC) =H ( KC )-H(C )+H( MKC )-H( KC ) =H(KMC )-H(C) =H ( MC ) -H (C) +H ( KMC ) -H ( MC ) = H( M/C )+H( K/MC ) 又根据熵的非负性, H( K/MC ) ≥ 0, 所以有: H(K/C) ≥ H(M/C) . 又根据定理 有: H(K) ≥ H(K/C) ,条件熵不大于无条件熵所以 H(K) ≥ H(M/C) 。根据式( 5-1 ), I( M,C ) =H (M) -H ( M/C )。综合可得 I( M,C )≥ H(M) -H (K) 证毕。(5-5) 有 H(K/C)=H(KC)-H(C) 有(M/KC)=H(MKC)-H(KC) 据(3-12) H(XY)=H(Y/X)+H(X) 五、完善保密