新编-第2章信息安全与信息论-精品课件.ppt

1、 一、保密系统一、保密系统(Secrecy System)(M M,C C,K K1,K K2,Ek k1,Dk k2)k1mcmC m图图2-1 保密系统模型保密系统模型密钥源密钥源 K K1 密钥源密钥源 K K2 k2密钥信道密钥信道信信 源源 M M加密器加密器c c=E Ek k1 1(m m)解密器解密器m m=D=D k2 k2(c c)接接 收者收者(主动攻击主动攻击)(被动攻击被动攻击)非非 法法接入者接入者密码分析员密码分析员 (窃听者窃听者)信道信道 搭线信道搭线信道 搭线信道搭线信道 l信源信源：是产生消息的源，在离散情况下可以产生字母：是产生消息的源，在离散情况下可以

2、产生字母或符号。可以用简单概率空间描述离散无记忆源。设信或符号。可以用简单概率空间描述离散无记忆源。设信源字母表为源字母表为M=ai,i=0,1,q1，字母，字母ai 出现的概率出现的概率为为pi 0，且，且 (21)信源产生的任一长为信源产生的任一长为L个符号的消息序列为个符号的消息序列为 m=(m1,m2,mL)mi M=Zq (22)l消息空间或明文空间消息空间或明文空间MM：长为：长为L的信源输出序列的集合的信源输出序列的集合 m MM=ML=ZqL (23)它含有它含有qL个元素。若信源为有记忆时，我们需要考虑个元素。若信源为有记忆时，我们需要考虑MM中各元素的概率分布。当信源为无记

3、忆时有中各元素的概率分布。当信源为无记忆时有 p(m)=p(m1,m2,mL)=(24)信源的统计特性对密码设计和分析起重要作用信源的统计特性对密码设计和分析起重要作用。101qiipiLip m1()l密钥源密钥源：是产生密钥序列的源。密钥通常是离散的，设：是产生密钥序列的源。密钥通常是离散的，设密钥字母表为：密钥字母表为：L L=kt,t=0,1,.,s-1。字母。字母kt的概率的概率p(kt)0，且，且密钥源为无记忆均匀分布密钥源为无记忆均匀分布，所以各密钥符号，所以各密钥符号为独立等概。为独立等概。l密钥空间密钥空间K K：对于长为对于长为r的密钥序列的密钥序列 k=k1,k2,.,k

4、r k1,kr K=ZS (25)的全体，且有的全体，且有 K K Kr=Zsr (26)一般消息空间一般消息空间K K与密钥空间与密钥空间MM彼此独立。合法的接收彼此独立。合法的接收者知道者知道k和密钥空间和密钥空间K K。窃听者不知道。窃听者不知道k。双钥体制下，有两个双钥体制下，有两个密钥空间密钥空间K K1 1和K K2 2、在单钥体制在单钥体制下下K K1 1=K K2 2=K K，此时密钥，此时密钥k k需经安全的密钥信道由发方传需经安全的密钥信道由发方传给收方。给收方。l密文空间密文空间C C：密文密文c的全体构成的集合。的全体构成的集合。c=(c1,c2,.,cV)=EK(m1

5、,m2,.,mL)(27)l加密变换加密变换：Ek k1E E，M MC C，由加密器完成，即 c=f(m,k1)=Ek1(m)m M M，k1K K1 (28)l解密变换解密变换：Dk k2 D D，C C M M，由加密器完成，即m=Dk2(c)mM M，k2K K2 (29)l合法接收者合法接收者：知道密文：知道密文c、解密变换和密钥，信道是解密变换和密钥，信道是无扰条件下，易于从密文得到原来的消息无扰条件下，易于从密文得到原来的消息m，即，即 m=Dk(c)=Dk(Ek(m)(210)l密码分析者密码分析者：可以得到密文：可以得到密文c，他知道明文的统计特，他知道明文的统计特性、加密体

6、制、密钥空间及其统计特性，但不知道截获性、加密体制、密钥空间及其统计特性，但不知道截获的密文的密文c所用的特定密钥。所用的特定密钥。密码分析者实施密码分析者实施被动攻击被动攻击 (Passive attack)：对一：对一个保密系统采取截获密文进行分析的攻击。个保密系统采取截获密文进行分析的攻击。用其选定的用其选定的变换函数变换函数h，对截获的密文，对截获的密文c进行变换，得到进行变换，得到 m=h(c)(211)一般一般 m m。l 主动攻击主动攻击(Active attack)：非法入侵者非法入侵者(Tamper)、攻击者攻击者(Attcker)或或黑客黑客(Hacker)主动向系统窜扰，

7、采用主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。，达到利已害人的目的。l A.Kerckhoff(18351903荷兰荷兰)原则原则：密码的安全：密码的安全必须完全寓于秘密钥之中。必须完全寓于秘密钥之中。通信系统与保密系统通信系统与保密系统 对消息对消息m的加密变换的作用类似于向消息注入噪声的加密变换的作用类似于向消息注入噪声。密文。密文c就相当于经过有扰信道得到的接收消息。密码就相当于经过有扰信道得到的接收消息。密码分析员就相当于有扰信道下原接收者。所不同的是，这分析员就相当于有扰信道下原接收者。所

8、不同的是，这种干扰不是信道中的自然干扰，而是发送者有意加进的种干扰不是信道中的自然干扰，而是发送者有意加进的，目的是使窃听者不能从，目的是使窃听者不能从c恢复出原来的消息。恢复出原来的消息。由此可见，通信问题和保密问题密切相关，有一由此可见，通信问题和保密问题密切相关，有一定的定的对偶性对偶性，用信息论的观点来阐述保密问题是十分自，用信息论的观点来阐述保密问题是十分自然的事。信息论自然成为研究密码学和密码分析学的一然的事。信息论自然成为研究密码学和密码分析学的一个重要理论基础，个重要理论基础，Shannon的工作开创了用信息理论的工作开创了用信息理论研究密码学的先河。研究密码学的先河。二、完善

9、保密性二、完善保密性 令明文熵为令明文熵为H(MM)H(ML)，密钥熵为，密钥熵为H(K K)，密文熵，密文熵为为H(C C)=H(C)，在已知密文条件下明文的含糊度为，在已知密文条件下明文的含糊度为H(ML/C )，在已知密文条件下密钥的含糊度为，在已知密文条件下密钥的含糊度为H(K/C)惟密文破译下，密码分析者的任务是从截获的密文惟密文破译下，密码分析者的任务是从截获的密文中提取有关明文的信息中提取有关明文的信息 I(ML;C)=H(ML)H(ML/C)(212)或从密文中提取有关密钥的信息或从密文中提取有关密钥的信息 I(K K;C)=H(K K)H(K K/C)(213)由此可知，由此

10、可知，H(K K/C)和和H(ML/C)越大，窃听者从密越大，窃听者从密文能够提取出的有关明文和密钥的信息就越小。文能够提取出的有关明文和密钥的信息就越小。合法的接收者已知密钥和密文知合法的接收者已知密钥和密文知 H(ML/C K K)=0 (2514)因而有因而有 I(ML;C K K)=H(ML)(215)定理定理2-1 对任意保密系统对任意保密系统 I(ML;C)H(ML)H(K K)(216)证明：由式证明：由式(2-5-34)及式及式(2-5-22)有有 H(K K/C)=H(K K/C)H(ML/K KC)=H(MLK K/C)=H(ML/C)H(/MLC)H(ML/C)又又 H(

11、K K)H(K K/C)故由式故由式(2-14)可得可得 I(ML;C)H(ML)H(K K)定理说明，保密系统的密钥量越小，其密文中含有定理说明，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。的关于明文的信息量就越大。完善的完善的(Perfect)或无条件的或无条件的(Unconditionally)保密系统保密系统：I(ML;C)=0 (217)密文与明文之间的互信息为零，窃听者从密文就得不到密文与明文之间的互信息为零，窃听者从密文就得不到任何有关明文的信息任何有关明文的信息,不管窃听者截获的密文有多少，他不管窃听者截获的密文有多少，他用于破译的计算资源有多丰富用于破译的计算

12、资源有多丰富,都是无济于事的。显然，都是无济于事的。显然，这种系统是安全的。这种系统是安全的。定理定理2-2：完善保密系统存在的必要条件是：完善保密系统存在的必要条件是 H(K K)H(ML)(218)证明证明：(2-16)和平均互信息的非负性知，当式和平均互信息的非负性知，当式(2-18)成立时必有式成立时必有式(2-17)。完善保密系统的密钥量的对数完善保密系统的密钥量的对数(密钥空间为均匀分密钥空间为均匀分布条件下布条件下)要大于明文集的熵。当密钥为二元序列时要满要大于明文集的熵。当密钥为二元序列时要满足足 H(ML)H(MM)=H(k1,k2,kr)r bits (219)定理定理2-

13、3：存在有完善保密系统。：存在有完善保密系统。证明证明 今以构造法证明。不失一般性可假定明文是今以构造法证明。不失一般性可假定明文是二元数字序列二元数字序列 m=(m1,m2,mL),miGF(2)令密钥序列令密钥序列 k=(k1,k2,kr)密文序列密文序列 c=(c1,c2,cv)也都是二元序列。也都是二元序列。m和和k彼此独立。今选彼此独立。今选L=r=v，并令，并令k是一理想二元对称源是一理想二元对称源(BSS)的输出，即的输出，即k为随机数字序列为随机数字序列，因而有，因而有 H()=L bits。若采用。若采用Vernam体制，则有体制，则有 c=Ek(m)=m k。式中，加法是逐

14、位按模式中，加法是逐位按模2进行，即进行，即 ci=mi ki。这等价于将这等价于将m通过一个转移概率通过一个转移概率p=1/2的的BSC传送，传送，BSC的容量为零的容量为零(参看例参看例2-5-3)。因而有。因而有 I(ML；CL)LC=0。但由平均互信息的非负性有但由平均互信息的非负性有I(ML；CL)0，从而证明上述系统有从而证明上述系统有 I(ML；CL)=0，即系统是完善的。，即系统是完善的。定理定理2-5-4构造的系统在惟密文破译下是安全的，构造的系统在惟密文破译下是安全的，但在已知明文攻击下是不安全的。但在已知明文攻击下是不安全的。Shannon最先证明这最先证明这种体制是完善

15、保密的，并能抗击已知明文种体制是完善保密的，并能抗击已知明文-密文下的攻击密文下的攻击。在不知密钥条件下，任何人采用任何破译法都不会比。在不知密钥条件下，任何人采用任何破译法都不会比随机猜测更好些随机猜测更好些!在实际应用中，为了安全起见，必须保证密钥以完在实际应用中，为了安全起见，必须保证密钥以完全随机方式产生全随机方式产生(如掷硬币如掷硬币)并派可靠信使通过安全途径并派可靠信使通过安全途径送给对方，每次用过后的密钥都立即销毁。送给对方，每次用过后的密钥都立即销毁。三、冗余度三、冗余度 P31-P32r:语言的信息率语言的信息率R:语言的绝对信息率语言的绝对信息率冗余度冗余度=R-r题：题：

16、2.3密码分析者借助自然语言的冗余度进行密码分析，冗余度密码分析者借助自然语言的冗余度进行密码分析，冗余度越大，越容易进行破译，越大，越容易进行破译，所以加密明文前，用一个压缩所以加密明文前，用一个压缩程序来降低明文的冗余度是一个非常好的选择程序来降低明文的冗余度是一个非常好的选择四、压缩编码四、压缩编码 在二元情况下，为实现完善保密所需的密钥量仅为在二元情况下，为实现完善保密所需的密钥量仅为N bit。理想压缩编码可使密钥长度减至。理想压缩编码可使密钥长度减至 r=N H(M1,M2,ML)（224)收端先由收到的密文收端先由收到的密文c利用已知密钥利用已知密钥k恢复出压缩后的明恢复出压缩后

17、的明文文 m=c k，再由明文再由明文m恢复原来的明文消息恢复原来的明文消息m。可能。可能实现完善保密。而所需的密钥量由原来的实现完善保密。而所需的密钥量由原来的L bits降为降为H(M1,M2,ML)bit。当然，这并不能从根本上解决一次。当然，这并不能从根本上解决一次一密体制中密钥量过大的问题。但是在下面我们将会看一密体制中密钥量过大的问题。但是在下面我们将会看到，加密前的数据压缩是强化保密系统的重要措施，这到，加密前的数据压缩是强化保密系统的重要措施，这也是也是Shannon最先指出的一个重要结果。降低明文中的最先指出的一个重要结果。降低明文中的多余度常常会使密码分析者处于困境。多余度

18、常常会使密码分析者处于困境。五、理论保密性五、理论保密性 长密文序列集长密文序列集C=C1,C2,.,C C，密钥的不确定性，即从密钥含糊度，由条件熵性质密钥的不确定性，即从密钥含糊度，由条件熵性质知知 H(K/C)=(K/C1,C+1)H(K/C1,C)(225)显然，当显然，当=0时的密钥的含糊度就是密钥的熵时的密钥的含糊度就是密钥的熵H(K)。即。即随着随着 的加大，密钥含糊度是非增的。即随着截获密文的的加大，密钥含糊度是非增的。即随着截获密文的增加，得到的有关明文或密钥的信息量就增加，而保留增加，得到的有关明文或密钥的信息量就增加，而保留的不确定性就会越来越小。的不确定性就会越来越小。

19、若若H=(K/C)0，就可惟一地确定密钥，就可惟一地确定密钥K，而实现破，而实现破译。译。0=min N|H(K/C)0 (226)惟一解距离惟一解距离(Unicity distance)对于给定的密码系统，在惟密文攻击下的对于给定的密码系统，在惟密文攻击下的 0=min N|H(K/C)0 (227)N是正整数集。当截获的密报量大于是正整数集。当截获的密报量大于 0时，原则上就可惟时，原则上就可惟一地确定系统所用的密钥，即原则上可以破译该密码。一地确定系统所用的密钥，即原则上可以破译该密码。0与明文多余度的关系与明文多余度的关系 0 H(K)/L (228)图图 2-2给出给出H(K)l的典

20、型变化特性。的典型变化特性。H(K K)0 1 2 3 H(K K)/L l（密文（密文量）量）图图2-2 H(K)l的典型变化特性的典型变化特性又由于又由于信息论与密码学信息论与密码学W(l)H(K/C)W(l)0 H(K)/l(密文量)图图2-3 破译工作特性破译工作特性 图中，点线表示可能的解多于一个的区域，对各可能图中，点线表示可能的解多于一个的区域，对各可能的解出现的概率需分别确定；实线表示有惟一解的区域。的解出现的概率需分别确定；实线表示有惟一解的区域。由图可知，随密文量由图可知，随密文量l增加，增加，W(l)会降至一个渐近值。会降至一个渐近值。任何一个非理想系统，其工作特性的趋势

21、大致和图任何一个非理想系统，其工作特性的趋势大致和图2-5-6一致，但一致，但W(l)的绝对取值随密码体制不同相差极大。的绝对取值随密码体制不同相差极大。即使当它们的密钥含糊度即使当它们的密钥含糊度H(K Cl)随随l变化的曲线大致相同变化的曲线大致相同时，它们的时，它们的W(l)也会有很大差别。例如，密钥量和简单代也会有很大差别。例如，密钥量和简单代换一样的维吉尼亚或组合维吉尼亚密码的工作特性要比简换一样的维吉尼亚或组合维吉尼亚密码的工作特性要比简单代换密码的好得多。单代换密码的好得多。如何实现使破译一个密码系统所需的工作量极大化，如何实现使破译一个密码系统所需的工作量极大化，这是博奕论中这

22、是博奕论中“极大化极小极大化极小”问题。仅仅从对付现有的标问题。仅仅从对付现有的标准的密码分析法是不够的，还必须确保没有轻而易举的破准的密码分析法是不够的，还必须确保没有轻而易举的破译方法。译方法。要判定密码体制的安全性绝非易事！要判定密码体制的安全性绝非易事！如何保证破译它所需的工作量足够大？如何保证破译它所需的工作量足够大？研究分析者可能采用的有哪些分析法，尔后估计各研究分析者可能采用的有哪些分析法，尔后估计各法破译该体制时所需的平均工作量法破译该体制时所需的平均工作量W(l)。这需要有丰富的。这需要有丰富的密码分析经验，这种方法在实际中常会使用。设计者要尽密码分析经验，这种方法在实际中常

23、会使用。设计者要尽可能在一般条件下描述这些分析方法，设法构造一种可以可能在一般条件下描述这些分析方法，设法构造一种可以抗击这类一般分析法的密码系统。抗击这类一般分析法的密码系统。估计破译一个保密系统所需的平均工作量估计破译一个保密系统所需的平均工作量W(l)的另一的另一种途径是，将破译此密码的难度等价于解数学上的某个已种途径是，将破译此密码的难度等价于解数学上的某个已知难题。知难题。Shannon在在1949年时虽然没有计算复杂性这样年时虽然没有计算复杂性这样的理论工具可用，但他已明确地意识到这一问题，他曾指的理论工具可用，但他已明确地意识到这一问题，他曾指出出“好密码的设计问题，本质上是寻找

24、针对某些其它条件好密码的设计问题，本质上是寻找针对某些其它条件的一种求解难题的问题的一种求解难题的问题”。七、乘积密码系统七、乘积密码系统(Product cryptosystems)利用利用“乘积乘积”对简单密码进行组合，可构造复杂而对简单密码进行组合，可构造复杂而安全的密码系统。设计当代密码有重要指导意义，许多近安全的密码系统。设计当代密码有重要指导意义，许多近代分组密码体制，几乎无一例外都采用了这一思想。代分组密码体制，几乎无一例外都采用了这一思想。为讨论简单，设为讨论简单，设C C=MM，这 类 密 码 称 为 自 同 态，这 类 密 码 称 为 自 同 态(Endomorphic)密

25、码。令密码。令S1=(MM,MM,K K1,E1,D1)和和S2=(MM,MM,K K2,E2,D2)是两个自同态密码系统，它们有相同的明是两个自同态密码系统，它们有相同的明文空间和密文空间。文空间和密文空间。S1和和S1的乘积的乘积S1S2表示为表示为(MM,MM,K K1 K K2,E,D)。乘积密码系统的密钥为。乘积密码系统的密钥为 k=(k1,k2)，k1 K K1，k2 K K2 加密：加密：(241)b EmEEmk kkk()()()1221解解 密：密：mmEDmEEDDmEEDmEDcDkkkkkkkkkkkkkkkk)()()()()(1112211221212121)(,

26、),()(由于由于k1和和k2独立选取，故有独立选取，故有)()(),(212121kpkpkkpkkk(242)(243)特例：幂等特例：幂等(Idempotent)密码系统：密码系统：SS=S2=S。可以推广到可以推广到n阶乘积密码以阶乘积密码以Sn表示。表示。移位、代换、仿射、移位、代换、仿射、Hill、Vigenre和置换等密码和置换等密码都是幂等体制。若密码是幂等的，则不会采用乘积都是幂等体制。若密码是幂等的，则不会采用乘积S2，即使用另一个密钥，也不会增大安全性。即使用另一个密钥，也不会增大安全性。对于非幂等密码体制，增加迭代次数，会增大潜在对于非幂等密码体制，增加迭代次数，会增大

27、潜在的安全性。两个不同的密码进行乘积常会得到一个非幂的安全性。两个不同的密码进行乘积常会得到一个非幂等密码。等密码。易于证明，若易于证明，若S1和和S2是幂等，则是幂等，则S1S2也是幂等的。也是幂等的。因为因为 (S1S2)(S1S2)=S1(S2S1)S2 =(S1S1)(S2S2)=S1S2 (244)八、认证系统八、认证系统(Authentication system)认证是认证是为了为了防止主动攻击，如对消息的内容、顺序、防止主动攻击，如对消息的内容、顺序、和时间的窜改以及重发等伪装、窜扰等的重要技术，和时间的窜改以及重发等伪装、窜扰等的重要技术，使使发送的消息具有被验证的能力，使接

28、收者或第三者能够发送的消息具有被验证的能力，使接收者或第三者能够识别和确认消息的真伪。实现这类功能的密码系统称作识别和确认消息的真伪。实现这类功能的密码系统称作认证系统。认证系统。认证目的认证目的：（1）验证信息的发送者是真的、而不是冒充的，）验证信息的发送者是真的、而不是冒充的，此为实体认证，包括信源、信宿等的认证和识别；此为实体认证，包括信源、信宿等的认证和识别；（2）验证信息的完整性，此为消息认证，验证）验证信息的完整性，此为消息认证，验证数据在传送或存储过程中未被窜改、重放或延迟数据在传送或存储过程中未被窜改、重放或延迟等。等。认证的理论与技术认证的理论与技术：是保密学研究的一个重要领

29、域，是保密学研究的一个重要领域，包括认证系统、杂凑包括认证系统、杂凑(Hash)函数、数字签名、身份证明、函数、数字签名、身份证明、认证协议等。认证协议等。l l 保密性：保密性是使截获者在不知密钥条件下不保密性：保密性是使截获者在不知密钥条件下不能解读密文的内容。能解读密文的内容。l l 认证性：使任何不知密钥的人不能构造一个密报，认证性：使任何不知密钥的人不能构造一个密报，使意定的接收者脱密成一个可理解的消息使意定的接收者脱密成一个可理解的消息(合法的合法的消息消息)。l l 完整性完整性(integrity)：在有自然和人为干扰条件下，：在有自然和人为干扰条件下，系统保持检测错误和恢复消

30、息和原来发送消息一致系统保持检测错误和恢复消息和原来发送消息一致性的能力。实际中常常借助于纠、检错技术和杂凑性的能力。实际中常常借助于纠、检错技术和杂凑技术来保证消息的完整性。技术来保证消息的完整性。要求：要求：l l 意定的接收者能够检验和证实消息的合法性和真实意定的接收者能够检验和证实消息的合法性和真实性。性。l l 消息的发送者对所发送的消息不能抵赖。消息的发送者对所发送的消息不能抵赖。l l 除了合法消息发送者外，其它人不能伪造合法的消除了合法消息发送者外，其它人不能伪造合法的消息。而且在已知合法密文息。而且在已知合法密文c和相应消息和相应消息m下，要确定下，要确定加密密钥或系统地伪造

31、合法密文在计算上是不可行的。加密密钥或系统地伪造合法密文在计算上是不可行的。l l 必要时可由第三者作出仲裁。必要时可由第三者作出仲裁。认证的信息理论认证的信息理论：类似于保密系统的信息理论，可将信：类似于保密系统的信息理论，可将信息论用于研究认证系统的理论安全性和实际安全性，指息论用于研究认证系统的理论安全性和实际安全性，指出认证系统的性能极限以及设计认证码必须遵循的原则。出认证系统的性能极限以及设计认证码必须遵循的原则。保密和认证同是信息系统安全的两个重要方面，但它们保密和认证同是信息系统安全的两个重要方面，但它们是两个不同属性的问题。认证不能自动地提供保密性，是两个不同属性的问题。认证不

32、能自动地提供保密性，而保密也不能自然地提供认证功能。一个纯认证系统的而保密也不能自然地提供认证功能。一个纯认证系统的模型如图模型如图2-4所示。在这个系统中的发送者通过一个公开所示。在这个系统中的发送者通过一个公开信道将消息送给接收者，接收者不仅想收到消息本身，信道将消息送给接收者，接收者不仅想收到消息本身，而且还要验证消息是否来自合法的发送者及消息是否经而且还要验证消息是否来自合法的发送者及消息是否经过窜改。系统中的密码分析者不仅要截收和分析信道中过窜改。系统中的密码分析者不仅要截收和分析信道中传送的密报，而且可伪造密文送给接收者进行欺诈，称传送的密报，而且可伪造密文送给接收者进行欺诈，称其

33、为系统的窜扰者其为系统的窜扰者(Tamper)更加贴切。实际认证系统可更加贴切。实际认证系统可能还要防止收、发之间的相互欺诈。能还要防止收、发之间的相互欺诈。图图2-4 纯认证系统模型纯认证系统模型信道信道窜扰者窜扰者认证编码器认证编码器认证译码器认证译码器信信 源源信信 宿宿密钥源密钥源安全信道安全信道 认证编码认证编码 在要发送的消息中引入多余度，使通过信道传送的在要发送的消息中引入多余度，使通过信道传送的可能序列集可能序列集Y大于消息集大于消息集X。对于任何选定的编码规则。对于任何选定的编码规则(相相应于某一特定密钥应于某一特定密钥)：发方可从：发方可从Y中选出用来代表消息的中选出用来代

34、表消息的许用序列，即码字；收方可根据编码规则唯一地确定出许用序列，即码字；收方可根据编码规则唯一地确定出发方按此规则向他传来的消息。窜扰者由于不知道密钥，发方按此规则向他传来的消息。窜扰者由于不知道密钥，因而所伪造的假码字多是因而所伪造的假码字多是Y中的禁用序列，收方将以很高中的禁用序列，收方将以很高的概率将其检测出来而被拒绝。认证系统设计者的任务的概率将其检测出来而被拒绝。认证系统设计者的任务是构造好的认证码是构造好的认证码(Authentication Code)，使接收者受骗，使接收者受骗概率极小化。概率极小化。令令x X为要发送的消息，为要发送的消息，k K是发方选定的密钥，是发方选定

35、的密钥，y=A(x,k)Y是表示消息是表示消息x的认证码字，的认证码字，Ak=y=A(x,k),x X为认证码。为认证码。A Ak是是Y中的许用中的许用(合法合法)序列集，而其补序列集，而其补集集A A k则为禁用序列集，且则为禁用序列集，且A AkA A k=Y。接收者知道认证编码接收者知道认证编码A(，)和密钥和密钥k，故从收到的，故从收到的y可惟一地确定出消息可惟一地确定出消息x。窜扰者虽然知道。窜扰者虽然知道X、Y、y、A(，)，但不知道具体密钥，但不知道具体密钥k，他的目标是想伪造出一个假码，他的目标是想伪造出一个假码字字y*，使，使y*A Ak，使接收者收到，使接收者收到y*后可以

36、密钥后可以密钥k解密得到解密得到一个合法的、可能由发端送出的消息一个合法的、可能由发端送出的消息x*，使接收者上当，使接收者上当受骗。如果发生这一事件，则认为窜扰者欺诈成功。受骗。如果发生这一事件，则认为窜扰者欺诈成功。窜扰者攻击的基本方式窜扰者攻击的基本方式：模仿伪造模仿伪造(Impersonative Fraudulent)，窜扰者在，窜扰者在未观测到认证信道中传送的合法消息未观测到认证信道中传送的合法消息(或认证码字或认证码字)条件条件下伪造假码字下伪造假码字y*，称其为无密文伪造更合适些。若接收，称其为无密文伪造更合适些。若接收者接受者接受y*作为认证码字，则说窜扰者攻击成功。作为认证

37、码字，则说窜扰者攻击成功。代换伪造代换伪造(Substitution Fraudulent)，窜扰者截收，窜扰者截收到认证系统中的认证码字到认证系统中的认证码字y后，进行分析并伪造假认证后，进行分析并伪造假认证码字码字y*，故可称为已知密文伪造。若接收者接受，故可称为已知密文伪造。若接收者接受y*为认为认证码字，则称窜扰者攻击成功。窜扰者可以自由地选择证码字，则称窜扰者攻击成功。窜扰者可以自由地选择最有利的攻击方式。最有利的攻击方式。窜扰者成功概率窜扰者成功概率(接收者受骗概率接收者受骗概率)：pd=maxpI，pS (245)pI：窜扰者采用模仿攻击时最大可能的成功概率窜扰者采用模仿攻击时最

38、大可能的成功概率 ps：在代换攻击时最大可能的成功概率。在代换攻击时最大可能的成功概率。完善认证性完善认证性(Perfect Authentication)：令：令#Y、#X、#K分别表示密文空间、消息空间、密钥空间中概率为分别表示密文空间、消息空间、密钥空间中概率为非零的元素的个数。一般认证编码中非零的元素的个数。一般认证编码中#Y#X，且认，且认证码中元素个数证码中元素个数#A Ak#X。对 每 个对 每 个 k K，至 少 有，至 少 有#X 个 不 同 的 密 文 使个 不 同 的 密 文 使p(Y=y|K=k)0。若对手采用模仿伪造策略，完全随机地。若对手采用模仿伪造策略，完全随机地

39、以非零概率从以非零概率从Y中选出一个作为伪造密文中选出一个作为伪造密文(认证码字认证码字)送送给接收者，则其成功的概率有给接收者，则其成功的概率有(246)YXYApI#k#min 要安全性高，即要要安全性高，即要pI小，需有小，需有#Y#X。由于。由于#X0，要求完全保护，即要，要求完全保护，即要pI=0是不可能实现的。而是不可能实现的。而且可以证明，要求式且可以证明，要求式(6-1-2)等号成立的充要条件是：对等号成立的充要条件是：对任一任一k K，都恰有，都恰有#A Ak#X。这表明采用随机密码不。这表明采用随机密码不能使上式等号成立。由于认证系统不能实现完全保护，能使上式等号成立。由于

40、认证系统不能实现完全保护，故将完善认证定义为对给定认证码空间，能使受骗率故将完善认证定义为对给定认证码空间，能使受骗率pd最小的认证系统最小的认证系统(在此意义下，即使对在此意义下，即使对#Y=#X时的平时的平凡情况，此时凡情况，此时pd=1，也有完善认证可言，也有完善认证可言)。若在最佳模仿策略下窜扰者只能随机地选取一个若在最佳模仿策略下窜扰者只能随机地选取一个y Y，则有，则有 H(Y)=log#Y (247)而若在任一给定密钥下，任一认证码字在认证码而若在任一给定密钥下，任一认证码字在认证码A中等概出现，则有中等概出现，则有 H(Y|K)=log#X (248)对式对式(6-1-2)两边

41、取对数可得两边取对数可得 log pI log#Xlog#Y=H(Y)H(Y|K)=I(Y；K)上述结果可归结为定理上述结果可归结为定理6-1-1。定理定理6-1-1 认证信道有认证信道有 log pI I(Y；K)(249)等号成立的充要条件为式等号成立的充要条件为式(6-1-3)和和(6-1-4)成立，且成立，且 log pd I(Y；K)(250)等号成立的必要条件为式等号成立的必要条件为式(247)和和(248)成立。成立。Simmons称式称式(250)为为认证信道的容量认证信道的容量。定义定义 完善认证完善认证是使式是使式(2-50)等号成立的认证系统。等号成立的认证系统。由式由式

42、(2-50)可知，即使系统是完善的，要使可知，即使系统是完善的，要使pd小就小就必须使必须使I(Y；K)大，也就是说使窜扰者从密文大，也就是说使窜扰者从密文Y中可提取中可提取更多的密钥信息！而由式更多的密钥信息！而由式I(Y；K)=H(K|Y)H(K)知，知，在极端情况下，当在极端情况下，当 H(K|Y)=0 即窜扰者可从即窜扰者可从Y获取有关密钥的全部信息时有获取有关密钥的全部信息时有 log pd H(K)(251)即有即有 pd#K (250)这是一个平凡的下限。这是一个平凡的下限。Gilbert等曾给出一个更强的下等曾给出一个更强的下限。限。定理定理6-1-3 对具有保密的认证对具有保

43、密的认证(窜扰者不知信源状态窜扰者不知信源状态)有有 log pd 1/2H(K)(250)而对无保密的认证而对无保密的认证(窜扰者知道信源状态窜扰者知道信源状态)有有log pd 1/2H(K)H(XY)H(Y)=1/2H(K)H(X|Y)(251)系系 (252)pKd1#类似于保密系统的安全性，认证系统的安全性也划类似于保密系统的安全性，认证系统的安全性也划分为两大类，即分为两大类，即理论安全性理论安全性和和实际安全性实际安全性。理论安全性理论安全性又称作无条件安全性，就是我们上面所又称作无条件安全性，就是我们上面所讨论的。它与窜扰者的计算能力或时间无关，也就是说讨论的。它与窜扰者的计算

44、能力或时间无关，也就是说窜扰者破译体制所做的任何努力都不会优于随机试凑方窜扰者破译体制所做的任何努力都不会优于随机试凑方式。式。实际安全性实际安全性是根据破译认证体制所需的计算量来评是根据破译认证体制所需的计算量来评价其安全性的。如果破译一个系统在原理上是可能的，价其安全性的。如果破译一个系统在原理上是可能的，但以所有已知的算法和现有的计算工具不可能完成所要但以所有已知的算法和现有的计算工具不可能完成所要求的计算量，就称其为计算上安全的。如果能够证明破求的计算量，就称其为计算上安全的。如果能够证明破译某体制的困难性等价于解决某个数学难题，就称其为译某体制的困难性等价于解决某个数学难题，就称其为

45、可证明安全的，如可证明安全的，如RSA体制。体制。这两种安全性虽都是从计算量来考虑，但不尽相同，这两种安全性虽都是从计算量来考虑，但不尽相同，计算安全要算出或估计出破译它的计算量下限，而可证计算安全要算出或估计出破译它的计算量下限，而可证明安全则要从理论上证明破译它的计算量不低于解已知明安全则要从理论上证明破译它的计算量不低于解已知难题的计算量。难题的计算量。认证码认证码 上面给出了认证系统安全性指标上面给出了认证系统安全性指标pd的下限，本节将的下限，本节将研究如何构造认证码使其接近或达到其性能下限。研究如何构造认证码使其接近或达到其性能下限。无条件安全认证码和纠错码理论互为无条件安全认证码

46、和纠错码理论互为对偶对偶。这两者。这两者都需要引入多余数字，在信道中可传送的序列集中只有都需要引入多余数字，在信道中可传送的序列集中只有一小部分用于传信。这是认证和纠错赖以实现的基本条一小部分用于传信。这是认证和纠错赖以实现的基本条件。纠错码的目的是抗噪声等干扰，要求将码中各码字件。纠错码的目的是抗噪声等干扰，要求将码中各码字配置得尽可能地散开配置得尽可能地散开(如最小汉明距离极大化如最小汉明距离极大化)，以保证，以保证在干扰作用下所得到的接收序列与原来的码字最接近。在干扰作用下所得到的接收序列与原来的码字最接近。在最大似然译码时可以使平均译码错误概率极小化。认在最大似然译码时可以使平均译码错

47、误概率极小化。认证码的目的是防止伪造和受骗。对于发送的任何消息序证码的目的是防止伪造和受骗。对于发送的任何消息序列列(或码字或码字)，窜扰者采用最佳策略所引入的代换或模拟，窜扰者采用最佳策略所引入的代换或模拟伪造序列应尽可能地散布于信道可传送的序列集中。伪造序列应尽可能地散布于信道可传送的序列集中。在认证系统中，密钥的作用类似于信道的干扰，在在认证系统中，密钥的作用类似于信道的干扰，在它们的控制下变换编码规则，使造出的代表消息的码字它们的控制下变换编码规则，使造出的代表消息的码字尽可能交义地配置，即将消息空间尽可能交义地配置，即将消息空间X最佳地散布于输出最佳地散布于输出空间空间(信道传送序列

48、集信道传送序列集)Y之中，以使窜扰者在不知道密之中，以使窜扰者在不知道密钥情况下，伪造成功的概率极小化。钥情况下，伪造成功的概率极小化。九、杂凑函数九、杂凑函数(Hash Function)将任意长数字串将任意长数字串M映射成一个较短的定长输出数字映射成一个较短的定长输出数字串串H的函数，以的函数，以h表示，表示，h(M)易于计算，称易于计算，称H=h(M)为为M的的杂凑值杂凑值，也称，也称杂凑码杂凑码、杂凑结果等或简称杂凑。、杂凑结果等或简称杂凑。特点特点：H打上了输入数字串的烙印，为数字指纹打上了输入数字串的烙印，为数字指纹(Digital Finger Print)。h是是多对一映射多对

49、一映射，因此我们不能，因此我们不能从从H求出原来的求出原来的M，但可以验证任一给定序列，但可以验证任一给定序列M是否与是否与M有相同的杂凑值。有相同的杂凑值。分类分类：密码杂凑函数密码杂凑函数，有密钥控制，以，有密钥控制，以h(k,M)表示。其表示。其杂凑值不仅与输入有关，而且与密钥有关，只有持此密杂凑值不仅与输入有关，而且与密钥有关，只有持此密钥的人才能计算出相应的杂凑值，因而具有钥的人才能计算出相应的杂凑值，因而具有身份验证功身份验证功能能，如消息认证码，如消息认证码MACANSI X 9.9。杂凑值。杂凑值也是一种也是一种认证符认证符或或认证码认证码。它要满足各种安全性要求，密码杂凑。它

50、要满足各种安全性要求，密码杂凑函数在现在密码学中有重要作用。函数在现在密码学中有重要作用。一般杂凑函数一般杂凑函数，无密钥控制。无密钥控制的单向，无密钥控制。无密钥控制的单向杂凑函数，其杂凑值只是输入字串的函数，任何人都可杂凑函数，其杂凑值只是输入字串的函数，任何人都可以计算，因而以计算，因而不具有身份认证功能不具有身份认证功能，只用于检测接收数，只用于检测接收数据的完整性，如窜改检测码据的完整性，如窜改检测码MDC，用于非密码计算机，用于非密码计算机应用中。应用中。应用应用：在密码学和数据安全技术中，它是实现有效、：在密码学和数据安全技术中，它是实现有效、安全可靠数字签字和认证的重要工具，是