1.4-香农理论简介

《1.4-香农理论简介》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四节Shannon理论简介密码体制安全性标准®计算安全性(computationalsecurity)®可证明安全性(provablesecurity)®无条件安全性(unconditionalsecurity)计算安全性这种度量涉及到攻击密码体制所作的计算上的努力。如果使用最好的算法攻破一个密码体制需要至少N次操作，这里的N是一个特定的非常大的数字，我们可以定义这个密码体制是计算安全的。可证明安全性另外一种途径是将密码体制的安全性归结为某个经过深入研究的数学难题。例如，可以证明这样一类命题：如果给定

2、的整数是不可分解的，那么给定的密码体制是不可破解的。我们称这种类型的密码体制是可证明安全的。注:这种途径只是说明了安全性和另一个问题是相关的，并没有完全证明是安全的。无条件安全性这种度量考虑的是对攻击者的计算量没有限制的时候的安全性。即使提供了无穷的计算资源，也是无法被攻破的，我们定义这种密码体制是无条件安全的。问题:计算安全性、可证明安全性、无条件安全性中哪种安全标准更实用?在上面三种安全标准的判定中，只有无条件安全性和信息论有关，即通过信息论来证明传递过程中无信息泄露。下面来建立密码学中的信息论模型

3、。密码学中的信息论模型密码系统的保密性能及破译一个密码系统都和信息论密切相关。我们知道，信息的传输是由通信系统完成的，而信息的保密则是由密码系统来完成。在通信过程中发送方发出的信息在信道中进行传输时往往受到各种干扰，使m出错而变成m′，一般m′≠m。合法接收者要从m′恢复m，必须识别m′中哪些信息是出错的。为此他要求发送方对m进行适当编码，即按一定的规则增加部分码字，使合法接收者通过译码器把m′中的错误纠正过来。对消息m进行加密的作用类似于对m进行干扰，密文c相当于被干扰的信息m′，破译者相当于在有干扰

4、的信道下的接收者,他要设法去掉这种“干扰”恢复原明文。密码系统图示mccm信源M加密器信道解密器信宿Mc破译者密钥k这样便出现了如下问题:密码设计者在设计密码体制时,要尽可能地使破译者从密文c中少获得原明文信息,而破译者则要从密文c中尽可能多地获得原明文信息。于是,便产生了密码学的信息理论。Shannon用信息理论描述了被截获的密文量与成功破译的可能性之间的关系。利用信息理论，他确定了一种密码的唯一解码量n。他把这种唯一解0码量描述为:当密文字符大于n时,这种密码就存在0一个解,而当密文字符少于n时,就

5、会出现多个可能0的解。概念与符号信源是产生消息的源。在离散情况下,它可以产生字母或符号,我们可以用明文空间来描述离散的无记忆源。设信源字母表为M={a,a,…,a},字母a出现01q−1i的概率为p,且p+p+…+p=1。i01q−1信源产生的任一L长的消息序列设为m=(m,0m,…,m),其中m∈M.若我们研究所有长为L1L−1i的信源的输出，则称m∈ML的全体为明文空间，它包含qL个元素。当信源无记忆时Lpm()==pmm(,,......,m)∏pm()12Lii=1破译由此信源加密的密码时，我们

6、需研究此信源的统计特性。加密是在密钥k的控制下由加密器完成的。密钥源是产生密钥的源。一般说来,密钥是离散的。设密钥字母表为B={b,b,…,b},字母b(0≤t≤s−1)出现01s−1t的概率为p(b)≥0,且p(b)+p(b)+…+p(b)=1。t01s−1密码设计一般都使密钥源为无记忆的均匀分布源,所以各密钥符号为独立同分布的。称长为r的密钥序列kkk=(,,......,kkB)(∈)的全体为密钥空间K，且有12rirK=B。一般情况下，明文空间与密钥空间彼此独立。合法接收者知道密钥k和密钥空间K

7、,故能把由k控制的加密消息c还原成明文m，而破译者则不知道密钥k。一个密码体制也可以记为EEkK={

8、∈},加密变换是k将明文空间中元素m在密钥k的控制下变为密文c，即ccc==(,,......,cEmm)(,,......,m);EE∈。12vk12Lk称c的全体为密文空间C。通常情况下，密文字母集和明文字母集相同，因而明文与密文的长度一般也相同。密文的统计特性一般由明文的统计特性和密钥的统计特性决定。破译者可以得到密文c,一般也假定他知道明文的统计特性,密码机的结构，密钥空间及密文的统计特性但不知

9、道加密截获的密文c所用的密钥k,要破译出原明文m或密钥k。概率论基础密码体制的无条件安全性当然不能用计算复杂性的观点来研究，因为我们允许计算时间是无限的。研究无条件安全的合适框架是概率论。下面复习概率论的基本知识。定义1.1一个离散的随机变量X，由有限集合X和定义在它上的概率分布组成。我们用Pr[X=x]表示随机变量X取x时的概率。对任意的x∈X，有0≤Pr[x]≤1,并且∑Pr[]x=1xX∈假设我们有定义在集合X上的随机变量X，且E⊆X