第六章 香农理论

第六章香农理论香农(Shannon) 1949年在贝尔系统技术期刊上发表了一篇标题为“保密 系统的通信理论”的论文，该论文对密码学的科学研究有重大影响。待加密后发送的所有可能消息的集合称为明文空间，常用M表示；所有密丈的集合称为密丈空间，常用c表示；所有密钥的集合称为密钥空间，常用K表示；在实际情况中，M, C和K都是有限集。算法确定后，对于给定 m e M,k e K ,则密文c唯一确定，即c - E(m,k)或c = E (m), E是加密变换。k定义6.1假设X与Y是随机变量，一般地用P(x)表示X取值为x的概率，即P(x) - P(X - %,用P(y)表示Y取值为y的概率，即P(y) - PY - y,用P (x, y)表示X取值为x且Y取值为y的联合概率，即P(x, y) - P(X - x, Y - y,用P(x/ y)表示当Y取值为y时X取值为x的条件概率。若P(x,y) - P(x)P(y)对所有可能的X取值为x和Y取值为y成立，则称随 机变量X和Y是相互独立的。联合概率与条件概率的关系P(x, y) - P(x)P(y / x) - P(y)P(x / y)定理6.1 (贝叶斯定理丿如果P(y) 0,那么P (x / y)-皆。推论设x与y是相互独立随机变量，当且仅当对所有x和y有P (X / y) = P (x)。如果给定一个密码体制，则关于它的明丈、密文与密钥的联合概率分布为 P(m, c, k)。由给定密码体制的联合概率分布可以确定该体制的各种边际分布 与条件分布，并由此确定一系列信息的度量。常用边际分布与条件分布如下:明文与密钥的联合概率分布为P(m,k)=工P(m,c,k),m g M,k g KceC明文与密文的联合概率分布为P(m,c)=工P(m,c,k), m g M,c g Ck g K明丈的概率分布为P(m)=工P(m,k), m g Mk gK i密钥的概率分布为P(k)二 EP(m,k), k g KmeM密丈的概率分布为P(c) = E P(m, c), c g CmeM由联合概率分布与边际分布产生的条件概率分布为密文关于明文和密钥的条件概率分布为P (m, k, c)P (c / m, k)=P (m, k)密文关于明文的条件概率分布为P (c / m)=P (m, c)P (m)明丈关于密丈的条件概率分布为P (m, c)P (c)密钥关于密文的条件概率分布为P (k, c)P (c)上述分布反映了密码体制中的数据结构关系6.2熵从密码分析的角度看，明文毫无不确定性，密文则不然。密文的不确定性 程度随着密码分析的进行而逐渐减小，直至完全确定。研究密文不确定性问题的基本工具是熵的思想，“熵”是香农1948年在密 码学中引进信息论时用到的概念。熵被认为是信息的数学测度或不确定性，可以作为概率分布的函数进行计 算。假定一个随机变量X，根据概率分布在一个有限集合上取值，即P(X = x= P, i = 1,2,n ,i则根据分布发生的事件所获得的信息是什么？或者，如果事件还没有发生，有关这个结果的不确定性是什么？这个量称为X的熵并表示为H(X)。定义6.2设X是一个随机变量，它根据概率分布在一个有限集合上取值，即px = x= P, i = 1,2,ni那么这个概率分布的熵定义为nH (X) = Y P lbPi ii=1式中 lbx = log x。2说明:1尽管limxlbx = 0，即允许x = 0，但因为在熵的定义中，当P = 0时，x T 0ilbP无定义，所以假设定义6.2中的和是在所有P丰0的下标i上进行 ii的。2熵定义中对数的底通常用2,因为lbP = log P lba (其中a为常数)，ia i所以计算熵时，若改变对数的底，熵的值只相差一个常数因子如果对1 i 0和H(X) = 0当且仅当对某一个i有P.= 1，并且对所有i主j 有 P = 0。j定理6.2对随机变量X , X的概率分布为P(X = x= P,i = 1,2,n , X的i熵的基本性质为0 H (X) lbn由定理6.2可知，当沪笃=二曽n时，随机变量的熵取最大值当各结果等概率时不确定性达到最大，最难做出预测。一个密码体制各个组成部分的熵 密钥概率分布相关的熵为H (K) = -E P (k )lbP (k)k eK明丈概率分布相关的熵为H (M)二E P(m)lbP(m)meM密丈概率分布相关的熵为H(C)二-EP(c)lbP(c)ceC明文与密文联合概率分布相关的熵为H (M, C)=-工 E P(m, c)lbP(m, c)meM ceC例 令M = L, b有 P(a) = 1, P(b) = 3 ；4“1，k2, k3有 P(k1) = 2, P(k 2) = 4, P (k3)= 4；C = h,2,3,4并假设加密函数定义如下E (a) = 1, E (b) = 2； E (a) = 2, E (b) = 3； E (a) = 3, E (b) = 4 片片k2k2kgkg这个密码体制可通过下列加密矩阵表示：Ekiabkk21223k343计算该密码体制各组成部分的熵解明丈概率分布相关的熵为H (M)二-P(a)lbP(a) - P(b)lbP(b)1133二一11=- (-1) - - (-2) - - (-2) = 1.5 4420061116 （星期四）第十九次课截止于此密文概率分布相关的熵为 H (C) = - P(1)lbP(1) - P lbP (2) - P(3)lbP(3) - P(4)lbP(4) lb1 - 3 lb 34444133二一- (-2) - _(lb3 - 2)二 2 - -lb3 沁 0.81444密钥概率分布相关的熵为H (K) = - P (k1)lbP (k1) - P (k 2)lbP(k 2) - P (k3)lbP (k3) 111111=-lb - - - lb - - - lb -2 24444欲求H(C)，必须先求出P(l),P,P(3),P(4)。又A, B双方在进行加密通信之前，A用预先确定的密钥加密明丈, 同时在信道上发送产生的密文给B, 即 A知道明文之前就选择了密钥。以下假设是合理的：密钥k和明文m是相互独立的因为P(C)二 工 工 P(m, k, c)keK meM所以P(1)二 P(a,仆1)二 P(a) P(ki)1114 28P二 P(a,k2,2) + P(b,仆2)二 P(a) P(k2) + P(b) P(k1)11317=_X+_X= 一4 44 216P二 P(a, k3,3) + P(b, k2,3)二 P(a) P(k3) + P(b) P(k2)11311= _X + _x_ = _4 44 44P =P (b, k3,4)=P (b) P(k3)3 13=_ x _ = 一4 416最后得H (C) = - P (l)lbP 一P lbP 一P (3)lbP 一P(4)lbP(4)-1 lb1 - L lb .1 -1 lb1 -1 lb J_88 1616 44 161617138 -(-3)- 16(lb7-4)- 4 -(-2)- 16(lb3-4)沁 1.856.3条件熵密码学研究更感兴趣的是在巳获某些密丈的条件，对发送某些消息或使用 某一密钥的不确定性测度。为此定义暧昧度(即条件熵丿如下： 定义6.3设X与Y是两个随机变量，则对Y的任何一个固定值y，都可达 到一个(条件)概率分布P( x / y)。显然H (X / y) = -Y P(x / y) lbP(x / y)x若定义条件熵H(X / Y)是所有可能值y的熵H(X / y)的加权平均(关于概 率P(y)，即H (X / Y)=-工 P (y) H (X / y)= -E P (y) P (x / y) lbP (x / y)y x条件熵测度通过Y来泄露有关X的信息的平均数。定理6.3H (X ,Y) = H (Y) + H (X/Y)H (X ,Y) = H (X) + H (Y/X)推论若X与Y是相互独立的，则(1) H(X ,Y) = H(X) + H(Y) H (X Y) = H (X) H (Y X) = H (Y)推论若X, Y和Z是相互独立的，则H (X, Y, Z) = H (X, Y) + H (Z X , Y)=H (X) + H (Y X) + H (Z X , Y)6.4多余度和唯一解码量把熵的结果应用到密码体制，可以证明在密码体制的组成部分之间存在一 个基本关系，称为密钥暧昧度。它是密文能泄露多少有关密钥的信息的一 种测度。定理6.4设(M, C, K, E, D)是一个密码体制，那么H (K/C) = H (K) + H (M) - H (C)例31(续)前面巳经计算了 H(M)沁0.81,H(K) = 1.5,H(C)沁1.85，于是有H(K/C)二 H(M) + H(K) - H(C)沁 0.81 +1.5 -1.85 二 0.46假设(M, C, K, E, D)是一个正在使用的密码体制，明文串mmm用一个12n密钥加密，产生一个密文串 CC。同时假设攻击者有无限的计算资源，1 2 n并知道明文为一个“自然”语言，如英语。对于任意密文，用不同的密钥脱密可能得到一种以上有意义的译丈，有意 义译丈的数量越多，判断哪一个是原文的难度就越大。若只有一个有意义的译文，则它一定就是。那么截获多少字符密文时能获 得唯一有意义的译丈？假定K中的密钥都是等概率的，设K = k , ,k , n是密钥数量。所以1Np =丄,H (K) = 一 Nplbp = 一 N x L lb 丄=lbNNNN长度为n的字符串共有t = 2rn，其中有意义的明文数S = 2对。所以nnH (M) = r nnH (C) = r nH(KC) = H(K) + H(M)-H(C) = 0表达了给定密文，密钥不存在不确定性，即给定了密文后，密钥便确定了。字符数n使H (K) + H (M) - H (C) = 0(2)将(1) 式代入上式得H(K) = (r - r )n(3)n(3) 式的解便是唯一解码量，用表示况。令r* = r - r为语言的多余度，则dnH (K) = r * udH (K)udr *u给出了破译一密码的最少字符数，也就是确定密钥的最少密文字符数目 d例6.2对于单表置换密码，密钥的数目为26!H(K) = lb26!沁 8838(bit)设长度为n的明文、密文串都取自英文字母表 A = (a,b,z,于是t = A n，而 A = 26，令 r = lb26 = 4.7004 , A = 2r 有nt = 2 r n = 24.7004nn对于长度为n的有意义明文的数目，有不同的估计值。当明丈的长度充分大时，设字母a, b,z出现的频数分别用n , n ,n表示。若明丈的概 a bz率为p，则P - PnaP% Pnza bz其中P ,P,p分别是字母a,b,z出现的概率。a bz令长度为n的有意义的明文数目为S，假设它们是等概率的，即nP =丄或S =Sn pn同时假定n充分大时有n = n paan = n p Q bbn = n pzz则lbS =lbpn=n( p lbp + p lbp HF p lbp )a a b bz z=n f p lbpja a丿a=a令r = X p lbpna aaa根据英文字母的频率计算得r 4.19bitnlbS r n 4.19 x 26 108.16n nS 2 rn n 2108.16nr *= r r 4.7004 4.19 0.5104n所以H (K) 88.38u u 173d r *0.5104即对单表置换密码，唯一解码量为173字符。唯一解码量依赖于对语言多余度的估计，归根到底是基于对有意义报丈 概率的计算。6.5完全保密体制对于某一密码体制保密性的评估，需要一种测度方法。用于讨论密码体制 保密性的基本方法有两类：计算保密性研究和无条件保密性研究。计算保密性研究计算保密性是涉及破译一个密码体制所需计算能力的一种指标。如果定义一个密码体制是计算上保密的，则指破译这个体制的最好算法需要至少N次运算，而N是一个非常大的数。 目前,还没有一种密码体制被证明是“计算上保密的”。实际中所称的 “计算上保密的”仅指攻破该体制的已知最好方法需要的计算机时间过 大。另一种提供“计算保密性”的方法是把一个密码体制的保密性转换为一 些巳经研究过的非常困难问题。无条件保密性研究无条件保密性涉及当破译者允许做无限的计算时密码体制的保密性。 如果一个密码体制甚至在无限计算资源条件下都不能破译，则被定义为无 条件保密。密码体制的无条件保密性不能根据计算复杂性来研究。研究无条件保密性的最合适方法是概率论。设明文空间M =仏,m，,m ，密丈空间C =甘,c，,c ，密钥空间12r12sK =族,k，,k ，令p(m )是m被发送的概率。12tii若截获一密丈c ;可以求得在已知c的条件下m被发送的后验概率如果，对于任何密文c，用P (c )表示得到c的概率，P (c m )表示发送 jjjj i明丈m.得到密丈c.的概率，根据概率乘法定理有定理6.5密码系统是完全保密的充要条件是对所有m和c ,当ijP (m.)0, P (c.)0 时有P(=卩(cj)现有明文m和m，即密丈c，由于完全保密，有其中P (.m)=工 P (1),xeKE (m , 1)二cikE (m , x) - cjkP(1),P(x)分别是1,x密钥的先验概率，即将 m变为c的所有密钥的概率之和 =将m 变为c的所有密钥的概率之ikjk和。当密钥空间K中所有密钥都是等概率的时候，可得结论：将 m变为c的密钥数目=将m 变为c的密钥数目。ikjk即表明：在密钥为等概率的密码体制中将任一明文变为任一密文的密钥数目 相同。定理6.6在一完全保密体制中，不同的密钥数目不少于可能的明文数目。定理6.7某一密码体制的密文数、密钥数和明文数若都相等，则该密码体制 完全保密的充要条件是：1 将每一明文加密成每一密文的密钥只有一个；2 所有密钥都是等概率的。完全保密是十分安全的。然而为了确保完全保密，必须分配大量的密钥， 这可能引起较大的麻烦。当信息量不大时，这种加密方法是实用、可行的。一次一密加密体制如下：假定明文长度为n，密钥长度至少等于n，设密丈为c ,c ,c。其中12nc 三(m + k )(mod26)ii i一次一密密码体制理论上是不可破的，实际应用中密钥管理确实颇为脆弱 的环节。2006.11.21 (星期二)第二十次课截止于此