《第2章.信息安全与信息论ppt(精品).ppt》由会员分享，可在线阅读，更多相关《第2章.信息安全与信息论ppt(精品).ppt（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息安全的数学基础信息安全的数学基础-信息论及与信息安全的信息论及与信息安全的关系关系北京师范大学应用数学学院北京师范大学应用数学学院杨进杨进1 1信息论与密码学信息论与密码学 ShannonShannon在在在在19491949年发表了一重要论文，年发表了一重要论文，年发表了一重要论文，年发表了一重要论文，“保密通信保密通信保密通信保密通信的通信理论的通信理论的通信理论的通信理论”，用信息论观点系统地阐述了保密通信的，用信息论观点系统地阐述了保密通信的，用信息论观点系统地阐述了保密通信的，用信息论观点系统地阐述了保密通信的问题。他提出了保密系统的模型、完善保密问题。他提出了保密系统的模型、完
2、善保密问题。他提出了保密系统的模型、完善保密问题。他提出了保密系统的模型、完善保密(Perfect(Perfect secrecy)secrecy)理论、理论保密性、实际保密性的理论、设计理论、理论保密性、实际保密性的理论、设计理论、理论保密性、实际保密性的理论、设计理论、理论保密性、实际保密性的理论、设计和破译密码的基本原则，将密码学从艺术和破译密码的基本原则，将密码学从艺术和破译密码的基本原则，将密码学从艺术和破译密码的基本原则，将密码学从艺术(art)(art)变为科变为科变为科变为科学。学。学。学。DiffieDiffie and and HellmanHellman在在在在19761
3、976年提出了公钥密码体制，年提出了公钥密码体制，年提出了公钥密码体制，年提出了公钥密码体制，(1981(1981得得得得Donald G.Fink Prize Donald G.Fink Prize 论文奖，论文奖，论文奖，论文奖，19981998年获年获年获年获IEEE IEEE Information Theory Society Golden Jubilee Awards for Information Theory Society Golden Jubilee Awards for Technological InnovationTechnological Innovation)。H
4、ellmanHellman引用引用引用引用ShannonShannon原话，原话，原话，原话，“好的密码设计本质上是寻求一个困难问题的解，相对好的密码设计本质上是寻求一个困难问题的解，相对好的密码设计本质上是寻求一个困难问题的解，相对好的密码设计本质上是寻求一个困难问题的解，相对于某种其它条件，我们可以构造密码，使其破译它于某种其它条件，我们可以构造密码，使其破译它于某种其它条件，我们可以构造密码，使其破译它于某种其它条件，我们可以构造密码，使其破译它(或或或或在过程中的某点上在过程中的某点上在过程中的某点上在过程中的某点上)等价于解某个已知数学难题。等价于解某个已知数学难题。等价于解某个已知
5、数学难题。等价于解某个已知数学难题。”这这这这是指引是指引是指引是指引HellmanHellman走向发现公钥密码的思想。因此，人们走向发现公钥密码的思想。因此，人们走向发现公钥密码的思想。因此，人们走向发现公钥密码的思想。因此，人们尊称尊称尊称尊称ShannonShannon为公钥密码学之父为公钥密码学之父为公钥密码学之父为公钥密码学之父(Godfather)(Godfather)。2 2 一、保密系统一、保密系统(SecrecySystem)(M M,C C,K K1,K K2,Ek k1,Dk k2)k1mcmC m图图2-1 保密系统模型保密系统模型密钥源密钥源 K K1 密钥源密钥源
6、 K K2 k2密钥信道密钥信道信信 源源 M M加密器加密器c c=E Ek k1 1(m m)解密器解密器m m=D=D k2k2(c c)接接 收者收者(主动攻击主动攻击)(被动攻击被动攻击)非非 法法接入者接入者密码分析员密码分析员 (窃听者窃听者)信道信道 搭线信道搭线信道 搭线信道搭线信道 信息论与密码学信息论与密码学3 3l信信源源：是是产产生生消消息息的的源源，在在离离散散情情况况下下可可以以产产生生字字母母或或符符号号。可可以以用用简简单单概概率率空空间间描描述述离离散散无无记记忆忆源源。设设信信源源字字母母表表为为M=ai,i=0,1,q1，字字母母ai 出出现现的的概概率
7、率为为pi 0，且且 (21)信源产生的任一长为信源产生的任一长为L个符号的消息序列为个符号的消息序列为 m=(m1,m2,mL)mi M=Zq (22)l消息空间或明文空间消息空间或明文空间MM：长为长为L的信源输出序列的集合的信源输出序列的集合 m MM=ML=ZqL (23)它它含含有有qL个个元元素素。若若信信源源为为有有记记忆忆时时，我我们们需需要要考考虑虑MM中各元素的概率分布。当信源为无记忆时有中各元素的概率分布。当信源为无记忆时有 p(m)=p(m1,m2,mL)=(24)信源的统计特性对密码设计和分析起重要作用信源的统计特性对密码设计和分析起重要作用。信息论与密码学信息论与密
8、码学4 4l密密钥钥源源：是是产产生生密密钥钥序序列列的的源源。密密钥钥通通常常是是离离散散的的，设设密密钥钥字字母母表表为为：L L=kt,t=0,1,.,s-1。字字母母kt的的概概率率p(kt)0，且且密密钥钥源源为为无无记记忆忆均均匀匀分分布布，所所以以各各密密钥钥符符号号为为独立等概。独立等概。l密钥空间密钥空间K K：对于长为对于长为r的密钥序列的密钥序列 k=k1,k2,.,kr k1,kr K=ZS (25)的全体，且有的全体，且有 K K Kr=Zsr (26)一一般般消消息息空空间间K K与与密密钥钥空空间间MM彼彼此此独独立立。合合法法的的接接收收者知道者知道k和密钥空间
9、和密钥空间K K。窃听者不知道窃听者不知道k。双双钥钥体体制制下下，有有两两个个密密钥钥空空间间K K1 1和K K2 2、在在单单钥钥体体制制下下K K1 1=K K2 2=K K，此此时时密密钥钥k k需需经经安安全全的的密密钥钥信信道道由由发发方方传传给收方。给收方。信息论与密码学信息论与密码学5 5l密文空间密文空间C C：密文密文c的全体构成的集合。的全体构成的集合。c=(c1,c2,.,cV)=EK(m1,m2,.,mL)(27)l加密变换加密变换：Ek k1E E，M MC C，由加密器完成，即 c=f(m,k1)=Ek1(m)mM M，k1K K1(28)l解密变换解密变换：D
10、k 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，他他知知道道明明文文的的统统计计特特性性、加加密密体体制制、密密钥钥空空间间及及其其统统计计特特性性，但但不不知知道道截截获获的的密密文文c所用的特定密钥。所用的特定密钥。信息论与密码学信息论与密码学6 6密密码码分分析析者者实实施施被
11、被动动攻攻击击 (Passive attack)：对对一一个个保保密密系系统统采采取取截截获获密密文文进进行行分分析析的的攻攻击击。用用其其选选定定的的变换函数变换函数h，对截获的密文对截获的密文c进行变换，得到进行变换，得到 m=h(c)(211)一般一般 m m。l 主主动动攻攻击击(Active attack)：非非法法入入侵侵者者(Tamper)、攻攻击击者者(Attcker)或或黑黑客客(Hacker)主主动动向向系系统统窜窜扰扰，采采用用删删除除、增增添添、重重放放、伪伪造造等等窜窜改改手手段段向向系系统统注注入入假假消消息，达到利已害人的目的。息，达到利已害人的目的。l A.Ke
12、rckhoff(18351903荷荷兰兰)原原则则：密密码码的的安安全全必须完全寓于秘密钥之中。必须完全寓于秘密钥之中。信息论与密码学信息论与密码学7 7 通信系统与保密系统通信系统与保密系统 对消息对消息m的加密变换的作用类似于向消息注入噪声。的加密变换的作用类似于向消息注入噪声。密文密文c就相当于经过有扰信道得到的接收消息。密码分就相当于经过有扰信道得到的接收消息。密码分析员就相当于有扰信道下原接收者。所不同的是，这种析员就相当于有扰信道下原接收者。所不同的是，这种干扰不是信道中的自然干扰，而是发送者有意加进的，干扰不是信道中的自然干扰，而是发送者有意加进的，目的是使窃听者不能从目的是使窃
13、听者不能从c恢复出原来的消息。恢复出原来的消息。由此可见，通信问题和保密问题密切相关，有一定由此可见，通信问题和保密问题密切相关，有一定的的对偶性对偶性，用信息论的观点来阐述保密问题是十分自然，用信息论的观点来阐述保密问题是十分自然的事。信息论自然成为研究密码学和密码分析学的一个的事。信息论自然成为研究密码学和密码分析学的一个重要理论基础，重要理论基础，Shannon的工作开创了用信息理论研究的工作开创了用信息理论研究密码学的先河。密码学的先河。信息论与密码学信息论与密码学8 8二、完善保密性二、完善保密性 令明文熵为令明文熵为H(MM)H(ML)，密钥熵为密钥熵为H(K K)，密文熵密文熵为
14、为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)由此可知，由此可知，H(K K/C)和和H(ML/C)越大，窃听者从密越大，窃听者从密文能够提取出的有关明文和密钥的信息就越小。文
15、能够提取出的有关明文和密钥的信息就越小。信息论与密码学信息论与密码学9 9 合法的接收者已知密钥和密文知合法的接收者已知密钥和密文知 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(K K)H(K K/C)故由式故由式(2-14)可得可得 I(ML;C)H(ML
16、)H(K K)信息论与密码学信息论与密码学1010 定理说明，保密系统的密钥量越小，其密文中含有定理说明，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。的关于明文的信息量就越大。完善的完善的(Perfect)或无条件的或无条件的(Unconditionally)保密系保密系统统：I(ML;C)=0 (217)密文与明文之间的互信息为零，窃听者从密文就得不到密文与明文之间的互信息为零，窃听者从密文就得不到任何有关明文的信息任何有关明文的信息,不管窃听者截获的密文有多少，他不管窃听者截获的密文有多少，他用于破译的计算资源有多丰富用于破译的计算资源有多丰富,都是无济于事的。显然，都是无
17、济于事的。显然，这种系统是安全的。这种系统是安全的。定理定理2-2：完善保密系统存在的必要条件是：完善保密系统存在的必要条件是 H(K K)H(ML)(218)证明证明：(2-16)和平均互信息的非负性知，当式和平均互信息的非负性知，当式(2-18)成立时必有式成立时必有式(2-17)。信息论与密码学信息论与密码学1111 完善保密系统的密钥量的对数完善保密系统的密钥量的对数(密钥空间为均匀分密钥空间为均匀分布条件下布条件下)要大于明文集的熵。当密钥为二元序列时要满要大于明文集的熵。当密钥为二元序列时要满足足 H(ML)H(MM)=H(k1,k2,kr)r bits (219)定理定理2-3：
18、存在有完善保密系统。：存在有完善保密系统。证明证明 今以构造法证明。不失一般性可假定明文是今以构造法证明。不失一般性可假定明文是二元数字序列二元数字序列 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。式中，加法是逐位按模式
19、中，加法是逐位按模2进行，即进行，即信息论与密码学信息论与密码学1212 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最先证
20、明这种最先证明这种体制是完善保密的，并能抗击已知明文体制是完善保密的，并能抗击已知明文-密文下的攻击。密文下的攻击。在不知密钥条件下，任何人采用任何破译法都不会比随在不知密钥条件下，任何人采用任何破译法都不会比随机猜测更好些机猜测更好些!在实际应用中，为了安全起见，必须保证密钥以完在实际应用中，为了安全起见，必须保证密钥以完全随机方式产生全随机方式产生(如掷硬币如掷硬币)并派可靠信使通过安全途径并派可靠信使通过安全途径送给对方，每次用过后的密钥都立即销毁。送给对方，每次用过后的密钥都立即销毁。信息论与密码学信息论与密码学1313三、冗余度三、冗余度 P31-P32r:语言的信息率语言的信息率R
21、:语言的绝对信息率语言的绝对信息率冗余度冗余度=R-r题：题：2.3密密码码分分析析者者借借助助自自然然语语言言的的冗冗余余度度进进行行密密码码分分析析，冗冗余余度度越越大大，越越容容易易进进行行破破译译，所所以以加加密密明明文文前前，用用一一个个压压缩缩程序来降低明文的冗余度是一个非常好的选择程序来降低明文的冗余度是一个非常好的选择信息论与密码学信息论与密码学1414四、压缩编码四、压缩编码 在在二二元元情情况况下下，为为实实现现完完善善保保密密所所需需的的密密钥钥量量仅仅为为N bit。理想压缩编码可使密钥长度减至理想压缩编码可使密钥长度减至 r=N H(M1,M2,ML)（224)收收端
22、端先先由由收收到到的的密密文文c利利用用已已知知密密钥钥k恢恢复复出出压压缩缩后后的的明明文文 m=c k，再再由由明明文文m恢恢复复原原来来的的明明文文消消息息m。可可能能实实现现完完善善保保密密。而而所所需需的的密密钥钥量量由由原原来来的的L bits降降为为H(M1,M2,ML)bit。当当然然，这这并并不不能能从从根根本本上上解解决决一一次次一一密密体体制制中中密密钥钥量量过过大大的的问问题题。但但是是在在下下面面我我们们将将会会看看到到，加加密密前前的的数数据据压压缩缩是是强强化化保保密密系系统统的的重重要要措措施施，这这也也是是Shannon最最先先指指出出的的一一个个重重要要结结
23、果果。降降低低明明文文中中的多余度常常会使密码分析者处于困境。的多余度常常会使密码分析者处于困境。信息论与密码学信息论与密码学1515 五、理论保密性五、理论保密性 长密文序列集长密文序列集C=C1,C2,.,C C，密密钥钥的的不不确确定定性性，即即从从密密钥钥含含糊糊度度，由由条条件件熵熵性性质质知知 H(K/C)=(K/C1,C+1)H(K/C1,C)(225)显显然然，当当=0时时的的密密钥钥的的含含糊糊度度就就是是密密钥钥的的熵熵H(K)。即即随随着着 的的加加大大，密密钥钥含含糊糊度度是是非非增增的的。即即随随着着截截获获密密文文的的增增加加，得得到到的的有有关关明明文文或或密密钥
24、钥的的信信息息量量就就增增加加，而而保保留留的的不确定性就会越来越小。不确定性就会越来越小。若若H=(K/C)0，就就可可惟惟一一地地确确定定密密钥钥K，而而实实现现破破译。译。0=min N|H(K/C)0 (226)信息论与密码学信息论与密码学1616惟一解距离惟一解距离(Unicity distance)对于给定的密码系统，在惟密文攻击下的对于给定的密码系统，在惟密文攻击下的 0=min N|H(K/C)0 (227)N是是正正整整数数集集。当当截截获获的的密密报报量量大大于于 0时时，原原则则上上就就可可惟惟一地确定系统所用的密钥，即原则上可以破译该密码。一地确定系统所用的密钥，即原则
25、上可以破译该密码。0与明文多余度的关系与明文多余度的关系 0 H(K)/L (228)图图 2-2给出给出H(K)l的典型变化特性。的典型变化特性。信息论与密码学信息论与密码学1717H(K K)0 1 2 3 H(K K)/L l（密（密文量）文量）图图2-2 H(K)l的典型变化特性的典型变化特性信息论与密码学信息论与密码学1818证明证明：令令Ml，Cl和和K都是二元序列集。都是二元序列集。K和和Cl之间平均互之间平均互信息为信息为I(K;Cl)=H(Cl)K(Cl/K)(229)对于典型的密码系统，当对于典型的密码系统，当l足够小时，二元密文序列的前足够小时，二元密文序列的前l bit
26、实际上是完全随机的二元数字，因而有实际上是完全随机的二元数字，因而有 H(Cl)l bits (230)由熵的性质有由熵的性质有 H(MlCl/K)=H(Ml/K)H(Cl/MlK)=H(Cl/K)H(Ml/ClK)(231)式中：式中：H(Cl/Ml K)=0 (232)H(Ml/Cl K)=0 (233)又由所有密码系统的明文和密钥统计独立，即又由所有密码系统的明文和密钥统计独立，即 信息论与密码学信息论与密码学1919 H(Ml/K)=H(Ml)(234)将上述三式代入式将上述三式代入式(2-5-49)得得 H(Cl/K)=H(Ml)(235)对于多数密码系统和相应的明文源，在对于多数密
27、码系统和相应的明文源，在l不太大时，例如不太大时，例如l L，不确定性不确定性H(Cl/K)随随l近似于线性关系增加，因而近似于线性关系增加，因而可将上式写成可将上式写成 H(Cl|K)H(ML)1 l L (236)将式将式(2-5-48)和式和式(2-5-54)代入式代入式(2-5-47)得得 (237)由由式式(2-5-41)知知，上上式式括括号号中中的的量量是是L长长二二元元信信源源序序列列的多余度，故有的多余度，故有 I(K;CL)=l L 0 L 1 (238)又由于又由于信息论与密码学信息论与密码学2020I(K;CL)=H(K)H(K/Cl)因而有因而有 H(K/Cl)H(K)
28、l L (239)由由此此可可见见，当当l足足够够小小时时，密密钥钥含含糊糊度度将将随随截截获获的的密密文文长长度度l线性地降低，直到当线性地降低，直到当H(K Cl)变得相当小为止。变得相当小为止。由式由式(2-5-57)及唯一解距离及唯一解距离 0的定义可得的定义可得 0 H(K)/L (240)讨论讨论：若若 L=0，即即当当明明文文经经过过最最佳佳数数据据压压缩缩编编码码后后，其其惟惟一一解解距距离离 0。虽虽然然这这时时系系统统不不一一定定满满足足H(K)H(ML)的的完完善善保保密密条条件件，但但不不管管截截获获的的密密报报量量有有多多大大，密密钥钥的的含含糊糊度度仍仍为为H(K/
29、Cl)H(K)，即即可可能能的的密密钥钥解解有有2H(K)个之多个之多!信息论与密码学信息论与密码学2121 实际中不可能实现实际中不可能实现 L=0，但是在消息进行加密之但是在消息进行加密之 前，先进行压缩编码来减小多余度，对于提高系统安前，先进行压缩编码来减小多余度，对于提高系统安全性是绝对必要的全性是绝对必要的!多余度的存在，使得任何密码体制多余度的存在，使得任何密码体制在有限密钥下在有限密钥下(H(K)为有限为有限)，其惟一解距离都将是有，其惟一解距离都将是有限的，因而在理论上都将是可破的。限的，因而在理论上都将是可破的。一些使数据扩展的方式对于密码的安全是不利的。一些使数据扩展的方式
30、对于密码的安全是不利的。增增大大H(K)是是提提高高保保密密系系统统安安全全性性的的途途径径，即即采采用用复杂的密码体制，直至一次一密钥体制。复杂的密码体制，直至一次一密钥体制。信息论与密码学信息论与密码学2222 例例2-2 英英语语单单表表代代换换密密码码的的密密钥钥量量|K=26!，其其密密钥钥空空间间的的熵熵为为H(K)=lb(26!)=88.4 bits。由由例例2-1知知，=3.2bits/字字母母，所所以以这这一一密密码码体体制制的的唯唯一一解解距距离离=88.4/3.2=27.6字母。字母。此此例例说说明明，只只要要截截获获到到28个个字字母母长长的的密密文文，原原则则上上就就
31、可可能能破破译译英英语语单单表表代代换换密密码码。这这和和著著名名密密码码分分析析家家W.F.Friedman的的经经验验值值25个个字字母母相相符符。例例如如，当当密密文文量量=40字字母母，若若每每个个字字母母的的多多余余度度以以=1.5计计算算，一一个个有有意意义义的的脱脱密密消消息息的的期期望望数数仅仅为为1.210-10。因因此此，当当得得到到一一个个有有意意义义的的解解时时显显然然是是可可信信赖赖的的。但但若若以以=20个个密密文文字字母母破破译译，有有意意义义的的脱脱密密解解高高达达2.2107个个之之多多，如如果果得得到到了了一个有意义的解，其可信度是很低的。一个有意义的解，其
32、可信度是很低的。信息论与密码学信息论与密码学2323 例例2-3 下下面面给给出出几几种种密密码码体体制制对对英英语语报报文文加加密密时时的的唯一解距离。唯一解距离。(1)周周 期期 为为 d的的 移移 位位 密密 码码，H(K)=lb(d!)，0=lb(d!)/3.2=0.3dlb(d/e)字字母母。若若选选d=27，则则d/e10，lb(d/e)3.2，故，故0=2.7字母。字母。(2)含含 q个个 字字 母母 表表 的的 单单 表表 代代 换换，H(K)=lb(q!)，0=lb(q!)/。例如例如q=26，=3.2就为例就为例2-5-6的情况。的情况。(3)周周期期为为d的的代代换换密密
33、码码(如如Beaufort或或Vigen re密密码码)。H(K)=lb(qd)=dlbq，0=(dlbq)/，对对英英语语，01.5d。这这些些结结果果都都是是在在统统计计意意义义下下得得到到的的，因因此此，只只有有当当处理的报文数据足够大时才适用。处理的报文数据足够大时才适用。信息论与密码学信息论与密码学2424 六、实际保密性六、实际保密性 理理论论保保密密性性：码码分分析析者者有有无无限限的的时时间间、设设备备和和资资金金条条件件下下，惟惟密密文文攻攻击击时时密密码码系系统统的的安安全全性性。一一个个密密码码系系统统，如如果果对对手手有有无无限限的的资资源源可可利利用用，而而在在截截获
34、获任任意意多多密密报报下下仍仍不能被破译，则它在理论上是保密的。不能被破译，则它在理论上是保密的。实实际际保保密密性性：一一个个密密码码系系统统的的破破译译所所需需要要的的努努力力，如如果果超超过过了了对对手手的的能能力力(时时间间、资资源源等等)时时，则则该该系系统统为为实实际上安全保密的际上安全保密的。保密的相对性保密的相对性:最小保障时间最小保障时间(Minimum cover time)：信息论与密码学信息论与密码学2525 计算能力计算能力(时间、费用等时间、费用等)与破译算法的有效性与破译算法的有效性 破译平均工作量破译平均工作量W(l)：破译破译l长截获密文所需的计算长截获密文所
35、需的计算。破破译译工工作作特特性性(Work characteristic)：W(l)随随l的的变变化化曲曲线线，其其中中W(l)可可用用人人-时时度度量量。平平均均是是在在所所有有可可能能密密钥上进行的。钥上进行的。W(l)可用来衡量密码系统的实际保密性可用来衡量密码系统的实际保密性。信息论与密码学信息论与密码学2626W(l)H(K/C)W(l)0 H(K)/L L l(密文量)图图2-3 破译工作特性破译工作特性信息论与密码学信息论与密码学2727 图中，点线表示可能的解多于一个的区域，对各可能图中，点线表示可能的解多于一个的区域，对各可能的解出现的概率需分别确定；实线表示有惟一解的区域
36、。的解出现的概率需分别确定；实线表示有惟一解的区域。由图可知，随密文量由图可知，随密文量l增加，增加，W(l)会降至一个渐近值。会降至一个渐近值。任何一个非理想系统，其工作特性的趋势大致和图任何一个非理想系统，其工作特性的趋势大致和图2-5-6一致，但一致，但W(l)的绝对取值随密码体制不同相差极大。的绝对取值随密码体制不同相差极大。即使当它们的密钥含糊度即使当它们的密钥含糊度H(K Cl)随随l变化的曲线大致相变化的曲线大致相同时，它们的同时，它们的W(l)也会有很大差别。例如，密钥量和简单也会有很大差别。例如，密钥量和简单代换一样的维吉尼亚或组合维吉尼亚密码的工作特性要比代换一样的维吉尼亚
37、或组合维吉尼亚密码的工作特性要比简单代换密码的好得多。简单代换密码的好得多。如何实现使破译一个密码系统所需的工作量极大化，如何实现使破译一个密码系统所需的工作量极大化，这是博奕论中这是博奕论中“极大化极小极大化极小”问题。仅仅从对付现有的标问题。仅仅从对付现有的标准的密码分析法是不够的，还必须确保没有轻而易举的破准的密码分析法是不够的，还必须确保没有轻而易举的破译方法。译方法。要判定密码体制的安全性绝非易事！要判定密码体制的安全性绝非易事！信息论与密码学信息论与密码学2828 如何保证破译它所需的工作量足够大？如何保证破译它所需的工作量足够大？研研究究分分析析者者可可能能采采用用的的有有哪哪些
38、些分分析析法法，尔尔后后估估计计各各法法破破译译该该体体制制时时所所需需的的平平均均工工作作量量W(l)。这这需需要要有有丰丰富富的的密密码码分分析析经经验验，这这种种方方法法在在实实际际中中常常会会使使用用。设设计计者者要要尽尽可可能能在在一一般般条条件件下下描描述述这这些些分分析析方方法法，设设法法构构造造一一种种可可以以抗击这类一般分析法的密码系统。抗击这类一般分析法的密码系统。估估计计破破译译一一个个保保密密系系统统所所需需的的平平均均工工作作量量W(l)的的另另一一种种途途径径是是，将将破破译译此此密密码码的的难难度度等等价价于于解解数数学学上上的的某某个个已已知知难难题题。Shan
39、non在在1949年年时时虽虽然然没没有有计计算算复复杂杂性性这这样样的的理理论论工工具具可可用用，但但他他已已明明确确地地意意识识到到这这一一问问题题，他他曾曾指指出出“好好密密码码的的设设计计问问题题，本本质质上上是是寻寻找找针针对对某某些些其其它它条条件件的一种求解难题的问题的一种求解难题的问题”。信息论与密码学信息论与密码学2929七、乘积密码系统七、乘积密码系统(Product cryptosystems)利利用用“乘乘积积”对对简简单单密密码码进进行行组组合合，可可构构造造复复杂杂而而安安全全的的密密码码系系统统。设设计计当当代代密密码码有有重重要要指指导导意意义义，许许多多近近代
40、代分组密码体制，几乎无一例外都采用了这一思想。分组密码体制，几乎无一例外都采用了这一思想。为为 讨讨 论论 简简 单单，设设 C C=MM，这这 类类 密密 码码 称称 为为 自自 同同 态态(Endomorphic)密密 码码。令令 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
41、K K2 加加密密：(241)b 信息论与密码学信息论与密码学3030解解 密：密：由于由于k1和和k2独立选取，故有独立选取，故有信息论与密码学信息论与密码学(242)(243)3131 特例：幂等特例：幂等(Idempotent)密码系统：密码系统：SS=S2=S。可以推广到可以推广到n阶乘积密码以阶乘积密码以Sn表示。表示。移移位位、代代换换、仿仿射射、Hill、Vigenre和和置置换换等等密密码码都都是是幂幂等等体体制制。若若密密码码是是幂幂等等的的，则则不不会会采采用用乘乘积积S2，即使用另一个密钥，也不会增大安全性。即使用另一个密钥，也不会增大安全性。对对于于非非幂幂等等密密码码
42、体体制制，增增加加迭迭代代次次数数，会会增增大大潜潜在在的的安安全全性性。两两个个不不同同的的密密码码进进行行乘乘积积常常会会得得到到一一个个非非幂幂等密码。等密码。易易于于证证明明，若若S1和和S2是是幂幂等等，则则S1S2也也是是幂幂等等的的。因为因为 (S1S2)(S1S2)=S1(S2S1)S2 =(S1S1)(S2S2)=S1S2 (244)信息论与密码学信息论与密码学3232八、认证系统八、认证系统(Authentication system)认证是认证是为了为了防止主动攻击，如对消息的内容、顺序、防止主动攻击，如对消息的内容、顺序、和时间的窜改以及重发等伪装、窜扰等的重要技术，和
43、时间的窜改以及重发等伪装、窜扰等的重要技术，使使发送的消息具有被验证的能力，使接收者或第三者能够发送的消息具有被验证的能力，使接收者或第三者能够识别和确认消息的真伪。实现这类功能的密码系统称作识别和确认消息的真伪。实现这类功能的密码系统称作认证系统。认证系统。认证目的认证目的：（1）验证信息的发送者是真的、而不是冒充的，）验证信息的发送者是真的、而不是冒充的，此为实体认证，包括信源、信宿等的认证和识别；此为实体认证，包括信源、信宿等的认证和识别；（2）验证信息的完整性，此为消息认证，验证）验证信息的完整性，此为消息认证，验证数据在传送或存储过程中未被窜改、重放或延迟数据在传送或存储过程中未被窜
44、改、重放或延迟等。等。信息论与密码学信息论与密码学3333 认证的理论与技术认证的理论与技术：是保密学研究的一个重要领域，是保密学研究的一个重要领域，包包括括认认证证系系统统、杂杂凑凑(Hash)函函数数、数数字字签签名名、身身份份证证明明、认证协议等。认证协议等。保保密密性性：保保密密性性是是使使截截获获者者在在不不知知密密钥钥条条件件下下不能解读密文的内容。不能解读密文的内容。认认证证性性：使使任任何何不不知知密密钥钥的的人人不不能能构构造造一一个个密密报报，使使意意定定的的接接收收者者脱脱密密成成一一个个可可理理解解的的消消息息(合合法的消息法的消息)。完完整整性性(integrity)
45、：在在有有自自然然和和人人为为干干扰扰条条件件下下，系系统统保保持持检检测测错错误误和和恢恢复复消消息息和和原原来来发发送送消消息息一一致致性性的的能能力力。实实际际中中常常常常借借助助于于纠纠、检检错错技技术术和和杂凑技术来保证消息的完整性。杂凑技术来保证消息的完整性。信息论与密码学信息论与密码学3434要求：要求：意意定定的的接接收收者者能能够够检检验验和和证证实实消消息息的的合合法法性性和和真真实实性。性。消息的发送者对所发送的消息不能抵赖。消息的发送者对所发送的消息不能抵赖。除除了了合合法法消消息息发发送送者者外外，其其它它人人不不能能伪伪造造合合法法的的消消息息。而而且且在在已已知知
46、合合法法密密文文c和和相相应应消消息息m下下，要要确确定定加密密钥或系统地伪造合法密文在计算上是不可行的。加密密钥或系统地伪造合法密文在计算上是不可行的。必要时可由第三者作出仲裁。必要时可由第三者作出仲裁。信息论与密码学信息论与密码学3535 认认证证的的信信息息理理论论：类类似似于于保保密密系系统统的的信信息息理理论论，可可将将信信息息论论用用于于研研究究认认证证系系统统的的理理论论安安全全性性和和实实际际安安全全性性，指指出出认认证证系系统统的的性性能能极极限限以以及及设设计计认认证证码码必必须须遵遵循循的的原原则则。保保密密和和认认证证同同是是信信息息系系统统安安全全的的两两个个重重要要
47、方方面面，但但它它们们是是两两个个不不同同属属性性的的问问题题。认认证证不不能能自自动动地地提提供供保保密密性性，而而保保密密也也不不能能自自然然地地提提供供认认证证功功能能。一一个个纯纯认认证证系系统统的的模模型型如如图图2-4所所示示。在在这这个个系系统统中中的的发发送送者者通通过过一一个个公公开开信信道道将将消消息息送送给给接接收收者者，接接收收者者不不仅仅想想收收到到消消息息本本身身，而而且且还还要要验验证证消消息息是是否否来来自自合合法法的的发发送送者者及及消消息息是是否否经经过过窜窜改改。系系统统中中的的密密码码分分析析者者不不仅仅要要截截收收和和分分析析信信道道中中传传送送的的密
48、密报报，而而且且可可伪伪造造密密文文送送给给接接收收者者进进行行欺欺诈诈，称称其其为为系系统统的的窜窜扰扰者者(Tamper)更更加加贴贴切切。实实际际认认证证系系统统可可能还要防止收、发之间的相互欺诈。能还要防止收、发之间的相互欺诈。信息论与密码学信息论与密码学3636信息论与密码学信息论与密码学图图2-4 纯认证系统模型纯认证系统模型信道信道窜扰者窜扰者认证编码器认证编码器认证译码器认证译码器信信 源源信信 宿宿密钥源密钥源安全信道安全信道3737信息论与密码学信息论与密码学 认证编码认证编码 在要发送的消息中引入多余度，使通过信道传送的在要发送的消息中引入多余度，使通过信道传送的可能序列
49、集可能序列集Y大于消息集大于消息集X。对于任何选定的编码规则对于任何选定的编码规则(相相应于某一特定密钥应于某一特定密钥)：发方可从：发方可从Y中选出用来代表消息的中选出用来代表消息的许用序列，即码字；收方可根据编码规则唯一地确定出许用序列，即码字；收方可根据编码规则唯一地确定出发方按此规则向他传来的消息。窜扰者由于不知道密钥，发方按此规则向他传来的消息。窜扰者由于不知道密钥，因而所伪造的假码字多是因而所伪造的假码字多是Y中的禁用序列，收方将以很高中的禁用序列，收方将以很高的概率将其检测出来而被拒绝。认证系统设计者的任务的概率将其检测出来而被拒绝。认证系统设计者的任务是构造好的认证码是构造好的
50、认证码(Authentication Code)，使接收者受使接收者受骗概率极小化。骗概率极小化。令令x X为要发送的消息，为要发送的消息，k K是发方选定的密钥，是发方选定的密钥，y=A(x,k)Y是表示消息是表示消息x的认证码字，的认证码字，Ak=y=A(x,k),x X为认证码。为认证码。A Ak是是Y中的许用中的许用(合法合法)序列集，而其补序列集，而其补集集A A k则为禁用序列集，且则为禁用序列集，且A AkA A k=Y。3838信息论与密码学信息论与密码学 接接收收者者知知道道认认证证编编码码A(，)和和密密钥钥k，故故从从收收到到的的y可可惟惟一一地地确确定定出出消消息息x。