密码学Shannon理论

《密码学Shannon理论》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第三章Shannon理论3.1密码体制的数学模型3.2熵及其性质3.3伪密钥和惟一解距离3.4密码体制的完善保密性3.5乘积密码体制3.1密码体制的数学模型密码注定与通信密不可分,不需通信也就不需要密码了。通信系统：设计目的是在信道有干扰的情况下,使接收的信息无差错或差错尽可能地小。保密系统：设计目的是使窃听者即使完全准确地接收到了信道上的传输信号也无法恢复原始信息。信源编码器干扰源接收者解码器信道mm密钥源接收者解密器加密器信道秘密信道信源密钥源密码分析者mmckkc信源字母表：且的概率为1.如果信源是无记忆的，则2.如果信源是有记忆

2、的，则需要考虑明文空间中各元素的概率分布。明文空间：密钥源字母表：，其中bi的概率为长为s的密钥：加密变换：将明文在密钥的控制下变为密文，即t和r为何不等呢？密文空间的统计特性由明文空间和密钥空间的统计特性决定：由于明文空间与密钥空间是相互独立的，则又因为故由Bayes公式知从以上公式可知，知道明文空间和密钥空间的概率分布，就可确定密文空间的概率分布，密文空间关于明文空间的概率分布，以及明文空间关于密文空间的概率分布。加解密运算可记为3.2熵及其性质定义3.1称为随机变量X的熵。定义3.2称为随机变量X和Y的联合熵。定义3.3称为X在Y

3、取值时的条件熵。定义3.4称为X关于Y的条件熵。定义3.5一个实值函数f称为在区间I上是凸(严格凸)的，如果对任意,都有.引理3.1（Jensen不等式）设f是区间I上的一个连续的严格凸函数，则上式中的等号成立当且仅当定理3.1任意信息源X,其熵值满足：当且仅当存在一个而对其他当且仅当对任意，都有定理3.1证明过程如下：定理3.2等号成立当且仅当X与Y相互独立。定理3.3推论3.1等号成立当且仅当X与Y相互独立.H(X)H(Y)I(X,Y)H(X

4、Y)H(Y

5、X)定理3.2证明过程如下：例3.1设是一个密码体制，明文空间密文空间，密钥空

6、间加密变换为设明文的概率分布密钥的概率分布为设m是明文空间M上的随机变量，c是密文空间C上的随机变量，k是密钥空间K上的随机变量。下面来计算熵根据熵的定义，我们有为了计算，我们需要先计算密文的概率分布。假设明文和密钥相互独立是合理的。根据有于是为计算，需要先计算在已知密文的情况下明文的概率分布，则于是≈0.46再由Bayes公式可计算得由Bayes公式知：最后计算首先计算在已知密文的情况下密钥的概率分布。于是，可计算出=0.463.3伪密钥和惟一解距离定理3.4设是一个密码体制，则这里M,K,C分别是M，K，C上的随机变量。证明：上述定

7、理说明了知道密文确定密钥的不确定性相当大。密码分析者可能得到很多可能的密钥，但其中只有一个是正确的，其他的密钥我们都称为是伪密钥。对于任意密文用不同的密钥解密，如果得到有意义明文越多，则表明伪密钥越多，从而增加判断真正唯一密钥的难度。从密码分析师的角度来看当然希望伪密钥个数为0,即.定义3.5设L是一种自然语言，称为语言L的熵。称为语言L的冗余度。其中X表示语言L的字母表，X(n)表示Xn上的随机变量。HL表示自然语言L中每个字母所携带的平均信息量的度量。如果该自然语言的关联度不大的话，语言中前后字母的搭配没有相关性，相当于每个字母都是

8、独立无关的，这时而实际上，任何自然语言前后字母均有一定的关联度，前面字母可能反应下一个字母，这时冗余度导致HL实际值远小于log

9、X

10、。HL实际值越接近log

11、X

12、，表明该语言的冗余度越小，反之越大。定理3.5设是一个密码体制，设X是明文字母表，Y是密文字母表，并且，设是明文语言的冗余度。假设密钥的选取满足均匀分布。则对于任意一个长度为n的密文字母串，当n充分大时，伪密钥的期望数目满足该定理主要讨论了伪密钥的平均数目的下界，伪密钥的个数主要与密钥空间的大小基本成正比，而与冗余度成反比。冗余度越大，表明语言的关联度大，语言关联度能帮助我们

13、识别真正密钥。该定理有两个注意的地方，第一，

14、X

15、=

16、Y

17、,这个条件一般自然语言均满足，第二是当密文长度n本大的情况下，该定理对伪密钥平均数目的猜测是不准确的。定义3.6一个密码体制的唯一解距离unicitydistance定义为使得伪密钥的期望数目sn等于零的密文长度n0.一个密码体制的唯一解距离就是密码分析者在足够的计算时间的情况下，能够惟一的计算处正确密钥所需的密文的平均长度。分析上面n0的表达式，语言的冗余度越大，唯一解距离越小，密文分析者在进行唯密文攻击时越容易得到正确密钥。因此从编码者的角度来讲，要提高密码体制的安全性，应尽

18、量减少明文语言的冗余度，即在对明文加密之前，最后用huffman编码对明文进行一次压缩。也就是用最简短的语言表达精要的内容!!(发电报)3.4密码体制的完善保密性定义3.7设是一个密码体制。如果对任意和任意