1、信息论与密码学信息论与密码学 一、保密系统一、保密系统(Secrecy System)(M M,C C,K K1,K K2,Ek k1,Dk k2)k1mcmC m图图2-1 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 M=a ai i,i,i=0,1,=0,1,q q11，字母，字母a ai i 出现的出现的概率为概率为p pi i 0 0，且，且 (21)(21)信源产生的任一长为信源产生的任一长为L L个符号的消息序列为个符号的消息序列为 m m=(=(m m1 1,m m2 2,m mL L)m mi i M M=Z Zq q (22)(22)l消息空间或明文空间消息空间或明文空间MM ：长为：长为L L的信源输
3、出序列的集的信源输出序列的集合合 m m MM=M ML L=Z Zq qL L (23)(23)它含有它含有q qL L个元素。若信源为有记忆时，我们需要考虑个元素。若信源为有记忆时，我们需要考虑MM中各元素的概率分布。当信源为无记忆时有中各元素的概率分布。当信源为无记忆时有 p p(m m)=)=p p(m m1 1,m m2 2,m mL L)=)=(24)(24)信源的统计特性对密码设计和分析起重要作用信源的统计特性对密码设计和分析起重要作用。101qiip信息论与密码学信息论与密码学iLip m1()l密钥源密钥源：是产生密钥序列的源。密钥通常是离散的，设：是产生密钥序列的源。密钥通
4、常是离散的，设密钥字母表为：密钥字母表为：L L=k kt t ,t t=0,1,.,=0,1,.,s s-1-1。字母。字母k kt t的的概率概率p p(k kt t)0 0，且，且密钥源为无记忆均匀分布密钥源为无记忆均匀分布，所以各密钥，所以各密钥符号为独立等概。符号为独立等概。l密钥空间密钥空间K K：对于长为对于长为r r的密钥序列的密钥序列 k k=k k1 1,k k2 2,.,.,k kr r k k1 1,k kr r K K=Z ZS S (25)(25)的全体，且有的全体，且有 K K K Kr r=Z Zs sr r (26)(26)一般消息空间一般消息空间K K与密钥
5、空间与密钥空间MM彼此独立。合法的彼此独立。合法的接收者知道接收者知道k k和密钥空间和密钥空间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的全体构成的集合。的全体构成的集合。c c=(=(c c1 1,c c2 2,.,.,c cV V)=)=E EK K(m m1 1,m m2 2,.,.,m
6、mL L)(27)(27)l加密变换加密变换：Ek k1E E，M MC C，由加密器完成，即 c=f(m,k1)=Ek1(m)m M M，k1K K1 (2828)l解密变换解密变换：Dk k2 D D，C C M M，由加密器完成，即m=Dk2(c)mM M，k2K K2 (2929)l合法接收者合法接收者：知道密文：知道密文c c、解密变换和密钥，信道是解密变换和密钥，信道是无扰条件下，易于从密文得到原来的消息无扰条件下，易于从密文得到原来的消息m m，即，即 m m=D Dk k(c c)=)=D Dk k(E Ek k(m m)(210(210)l密码分析者密码分析者：可以得到密文：
7、可以得到密文c c，他知道明文的统计特，他知道明文的统计特性、加密体制、密钥空间及其统计特性，但不知道截获性、加密体制、密钥空间及其统计特性，但不知道截获的密文的密文c c所用的特定密钥。所用的特定密钥。信息论与密码学信息论与密码学 密码分析者实施密码分析者实施被动攻击被动攻击 (Passive attack)(Passive attack)：对：对一个保密系统采取截获密文进行分析的攻击。一个保密系统采取截获密文进行分析的攻击。用其选定用其选定的变换函数的变换函数h，对截获的密文，对截获的密文c进行变换，得到进行变换，得到 m=h(c)(211211)一般一般 m m。l 主动攻击主动攻击 (
8、Active attack)(Active attack)：非法入侵者非法入侵者(Tamper)(Tamper)、攻击者攻击者(Attcker)(Attcker)或或黑客黑客(Hacker)(Hacker)主动向系统窜扰，主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。消息，达到利已害人的目的。l A.KerckhoffA.Kerckhoff(18351903(18351903荷兰荷兰)原则原则：密码的安全：密码的安全必须完全寓于秘密钥之中。必须完全寓于秘密钥之中。信息论与密码学信息论与密码学 通信系统与
9、保密系统通信系统与保密系统 对消息对消息m m的加密变换的作用类似于向消息注入的加密变换的作用类似于向消息注入噪声。密文噪声。密文c c就相当于经过有扰信道得到的接收消息。就相当于经过有扰信道得到的接收消息。密码分析员就相当于有扰信道下原接收者。所不同的是密码分析员就相当于有扰信道下原接收者。所不同的是，这种干扰不是信道中的自然干扰，而是发送者有意加，这种干扰不是信道中的自然干扰，而是发送者有意加进的，目的是使窃听者不能从进的，目的是使窃听者不能从c c恢复出原来的消息。恢复出原来的消息。由此可见，通信问题和保密问题密切相关，有由此可见，通信问题和保密问题密切相关，有一定的一定的对偶性对偶性，
10、用信息论的观点来阐述保密问题是十分，用信息论的观点来阐述保密问题是十分自然的事。信息论自然成为研究密码学和密码分析学的自然的事。信息论自然成为研究密码学和密码分析学的一个重要理论基础，一个重要理论基础，ShannonShannon的工作开创了用信息理论的工作开创了用信息理论研究密码学的先河。研究密码学的先河。信息论与密码学信息论与密码学二、完善保密性二、完善保密性 令明文熵为令明文熵为H H(MM)H H(M ML L)，密钥熵为，密钥熵为H H(K K)，密，密文熵为文熵为H H(C C)=)=H H(C C)，在已知密文条件下明文的含糊度为，在已知密文条件下明文的含糊度为H H(M ML
11、L/C C )，在已知密文条件下密钥的含糊度为，在已知密文条件下密钥的含糊度为H H(K K/C C)惟密文破译下，密码分析者的任务是从截获的惟密文破译下，密码分析者的任务是从截获的密文中提取有关明文的信息密文中提取有关明文的信息 I I(M ML L;C C)=)=H H(M ML L)H H(M ML L/C/C)(212)(212)或从密文中提取有关密钥的信息或从密文中提取有关密钥的信息 I I(K K;C C)=H=H(K K)H H(K K /C/C)(213)(213)由此可知，由此可知，H H(K K /C/C)和和H H(M ML L/C/C)越大，窃听者越大，窃听者从密文能够
12、提取出的有关明文和密钥的信息就越小。从密文能够提取出的有关明文和密钥的信息就越小。信息论与密码学信息论与密码学 合法的接收者已知密钥和密文知合法的接收者已知密钥和密文知 H H(M ML L/C/C K K)=0 0 (2514)(2514)因而有因而有 I I(M ML L;C C K K )=H=H(M ML L)(215)(215)定理定理2-12-1 对任意保密系统对任意保密系统 I I(M ML L;C C)H H(M ML L)H H(K K)(216)(216)证明：由式证明：由式(2-5-34)(2-5-34)及式及式(2-5-22)(2-5-22)有有 H H(K K /C/
13、C)=)=H(H(K K/C/C)H H(M ML L/K KC C)=)=H H(M ML LK K/C/C)=H=H(M ML L/C/C)H H(/M/ML LC C)H(MH(ML L/C/C)又又 H H(K K)H H(K K /C/C)故由式故由式(2-14)(2-14)可得可得 I I(M ML L;C C)H(MH(ML L)H H(K K)信息论与密码学信息论与密码学 定理说明，保密系统的密钥量越小，其密文中定理说明，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。含有的关于明文的信息量就越大。完善的完善的(Perfect)(Perfect)或无条件的或无条件的
14、(Unconditionally)(Unconditionally)保密系保密系统统：I I(M ML L;C C)=0 )=0 (217)(217)密文与明文之间的互信息为零，窃听者从密文就得不到密文与明文之间的互信息为零，窃听者从密文就得不到任何有关明文的信息任何有关明文的信息,不管窃听者截获的密文有多少，不管窃听者截获的密文有多少，他用于破译的计算资源有多丰富他用于破译的计算资源有多丰富,都是无济于事的。显都是无济于事的。显然，这种系统是安全的。然，这种系统是安全的。定理定理2-22-2：完善保密系统存在的必要条件是：完善保密系统存在的必要条件是 H H(K K)H H(M ML L)(
15、218)(218)证明证明 ：(2-16)(2-16)和平均互信息的非负性知，当式和平均互信息的非负性知，当式(2-(2-18)18)成立时必有式成立时必有式(2-17)(2-17)。信息论与密码学信息论与密码学 完善保密系统的密钥量的对数完善保密系统的密钥量的对数(密钥空间为均密钥空间为均匀分布条件下匀分布条件下)要大于明文集的熵。当密钥为二元序列要大于明文集的熵。当密钥为二元序列时要满足时要满足 H H(M ML L)H H(MM)=)=H H(k k1 1,k k2 2,k kr r)r r bits bits (219)(219)定理定理2-32-3：存在有完善保密系统。：存在有完善保
16、密系统。证明证明 今以构造法证明。不失一般性可假定今以构造法证明。不失一般性可假定明文是二元数字序列明文是二元数字序列 m m=(=(m m1 1,m m2 2,m mL L),),m mi iGFGF(2)(2)令密钥序列令密钥序列 k k=(=(k k1 1,k k2 2,k kr r)密文序列密文序列 c c=(=(c c1 1,c c2 2,c cv v)也都是二元序列。也都是二元序列。m m和和k k彼此独立。今选彼此独立。今选L L=r r=v v，并令并令k k是一理想二元对称源是一理想二元对称源(BSS)(BSS)的输出，即的输出，即k k为随机数为随机数字序列，因而有字序列，
17、因而有 H(H()=L L bits bits。若采用。若采用VernamVernam体制，体制，则有则有 c c=E Ek k(m m)=)=m m k k。式中，加法是逐位按模式中，加法是逐位按模2 2进行，即进行，即信息论与密码学信息论与密码学 c ci i=m mi i k ki i。这等价于将这等价于将m m通过一个转移概率通过一个转移概率p p=1/2=1/2的的BSCBSC传送，传送，BSCBSC的的容量为零容量为零(参看例参看例2-5-3)2-5-3)。因而有。因而有 I(MI(ML L；C CL L)LCLC=0=0。但由平均互信息的非负性有但由平均互信息的非负性有I(MI(
18、ML L；C CL L)0)0，从而证明上，从而证明上述系统有述系统有 I I(M ML L；C CL L)=0)=0，即系统是完善的。，即系统是完善的。定理定理2-5-42-5-4构造的系统在惟密文破译下是安全构造的系统在惟密文破译下是安全的，但在已知明文攻击下是不安全的。的，但在已知明文攻击下是不安全的。ShannonShannon最先证最先证明这种体制是完善保密的，并能抗击已知明文明这种体制是完善保密的，并能抗击已知明文-密文下密文下的攻击。在不知密钥条件下，任何人采用任何破译法都的攻击。在不知密钥条件下，任何人采用任何破译法都不会比随机猜测更好些不会比随机猜测更好些!在实际应用中，为了
19、安全起见，必须保证密钥在实际应用中，为了安全起见，必须保证密钥以完全随机方式产生以完全随机方式产生(如掷硬币如掷硬币)并派可靠信使通过安全并派可靠信使通过安全途径送给对方，每次用过后的密钥都立即销毁。途径送给对方，每次用过后的密钥都立即销毁。信息论与密码学信息论与密码学三、冗余度三、冗余度 P31-P32P31-P32r:r:语言的信息率语言的信息率R:R:语言的绝对信息率语言的绝对信息率冗余度冗余度=R-r题：题：2.3密码分析者借助自然语言的冗余度进行密码分析，冗余度密码分析者借助自然语言的冗余度进行密码分析，冗余度越大，越容易进行破译，越大，越容易进行破译，所以加密明文前，用一个压缩所以
20、加密明文前，用一个压缩程序来降低明文的冗余度是一个非常好的选择程序来降低明文的冗余度是一个非常好的选择信息论与密码学信息论与密码学四、压缩编码四、压缩编码 在二元情况下，为实现完善保密所需的密钥量在二元情况下，为实现完善保密所需的密钥量仅为仅为N bitN bit。理想压缩编码可使密钥长度减至。理想压缩编码可使密钥长度减至 r r=N N H H(M M1 1,M M2 2,M ML L)（224)224)收端先由收到的密文收端先由收到的密文c c利用已知密钥利用已知密钥k k恢复出压缩后的明恢复出压缩后的明文文 m m=c c k k，再由明文再由明文m m恢复原来的明文消息恢复原来的明文消
21、息m m。可能。可能实现完善保密。而所需的密钥量由原来的实现完善保密。而所需的密钥量由原来的L L bits bits降为降为H(MH(M1 1,M M2 2,M ML L)bit)bit。当然，这并不能从根本上解决一。当然，这并不能从根本上解决一次一密体制中密钥量过大的问题。但是在下面我们将会次一密体制中密钥量过大的问题。但是在下面我们将会看到，加密前的数据压缩是强化保密系统的重要措施，看到，加密前的数据压缩是强化保密系统的重要措施，这也是这也是ShannonShannon最先指出的一个重要结果。降低明文中的最先指出的一个重要结果。降低明文中的多余度常常会使密码分析者处于困境。多余度常常会使
22、密码分析者处于困境。信息论与密码学信息论与密码学 五、理论保密性五、理论保密性 长密文序列集长密文序列集C C=C C1 1,C C2 2,.,.,C C C C，密钥的不确定性，即从密钥含糊度，由条件熵密钥的不确定性，即从密钥含糊度，由条件熵性质知性质知 H H(K/CK/C)=(K/C=(K/C1 1,C C+1+1)H H(K/CK/C1 1,C C)(225)(225)显然，当显然，当=0=0时的密钥的含糊度就是密钥的熵时的密钥的含糊度就是密钥的熵H(K)H(K)。即随。即随着着 的加大，密钥含糊度是非增的。即随着截获密文的增的加大，密钥含糊度是非增的。即随着截获密文的增加，得到的有关
23、明文或密钥的信息量就增加，而保留的加，得到的有关明文或密钥的信息量就增加，而保留的不确定性就会越来越小。不确定性就会越来越小。若若H H=(=(K K/C C)0 0，就可惟一地确定密钥，就可惟一地确定密钥K K，而实，而实现破译。现破译。0 0=min=min N N|H(K/CH(K/C)0 (226)0 (226)信息论与密码学信息论与密码学惟一解距离惟一解距离(Unicity distance)(Unicity distance)对于给定的密码系统，在惟密文攻击下的对于给定的密码系统，在惟密文攻击下的 0 0=min=min N N|H(K/CH(K/C)0 0 (227)(227)N
24、 N是正整数集。当截获的密报量大于是正整数集。当截获的密报量大于 0 0时，原则上就可惟时，原则上就可惟一地确定系统所用的密钥，即原则上可以破译该密码。一地确定系统所用的密钥，即原则上可以破译该密码。0 0与明文多余度的关系与明文多余度的关系 0 0 H H(K K)/)/L L (228)(228)图图 2-22-2给出给出H(K)H(K)l l的典型变化特性。的典型变化特性。信息论与密码学信息论与密码学H(H(K K)0 1 2 3 0 1 2 3 H(H(K K)/)/L L l l（密文量）（密文量）图图2-2 2-2 H(K)H(K)l l的典型变化特性的典型变化特性信息论与密码学信
25、息论与密码学证明证明：令令M Ml l，C Cl l和和K K都是二元序列集。都是二元序列集。K K和和C Cl l之间平均互之间平均互信息为信息为I I(K K;C Cl l)=)=H(CH(Cl l)K(CK(Cl l/K K)(229)(229)对于典型的密码系统，当对于典型的密码系统，当l l足够小时，二元密文序列的足够小时，二元密文序列的前前l l bit bit实际上是完全随机的二元数字，因而有实际上是完全随机的二元数字，因而有 H H(C Cl l)l l bits bits (230)(230)由熵的性质有由熵的性质有 H H(M Ml lC Cl l/K K)=)=H(MH(
26、Ml l/K)K)H(CH(Cl l/M Ml lK K)=H H(C Cl l/K K)H H(M Ml l/C Cl lK K)(231)(231)式中：式中：H H(C Cl l/M Ml l K K)=0 (232)=0 (232)H H(M Ml l/C Cl l K K)=0 )=0 (233)(233)又由所有密码系统的明文和密钥统计独立，即又由所有密码系统的明文和密钥统计独立，即 信息论与密码学信息论与密码学 H H(M Ml l/K K)=)=H H(M Ml l)(234)(234)将上述三式代入式将上述三式代入式(2-5-49)(2-5-49)得得 H H(C Cl l/
27、K K)=)=H H(M Ml l)(235)(235)对于多数密码系统和相应的明文源，在对于多数密码系统和相应的明文源，在l l不太大时，例不太大时，例如如l l L L，不确定性，不确定性H H(C Cl l/K)K)随随l l近似于线性关系增加，因近似于线性关系增加，因而可将上式写成而可将上式写成 H H(C Cl l|K|K)H H(M ML L)1)1 l l L (236)L (236)将式将式(2-5-48)(2-5-48)和式和式(2-5-54)(2-5-54)代入式代入式(2-5-47)(2-5-47)得得 (237)(237)由式由式(2-5-41)(2-5-41)知，上式
28、括号中的量是知，上式括号中的量是L L长二元信源序列长二元信源序列的多余度，故有的多余度，故有 I(KI(K;C CL L)=)=l l L L 0 0 L L 1 1 (238)(238)又由于又由于信息论与密码学信息论与密码学I I(K K;C CL L)=)=H(KH(K)H H(K K/C Cl l)因而有因而有 H H(K K/C Cl l)H H(K K)l l L L (239)(239)由此可见，当由此可见，当l l足够小时，密钥含糊度将随截获的密文足够小时，密钥含糊度将随截获的密文长度长度l l线性地降低，直到当线性地降低，直到当H(KH(K C Cl l)变得相当小为止。变
29、得相当小为止。由式由式(2-5-57)(2-5-57)及唯一解距离及唯一解距离 0 0的定义可得的定义可得 0 0 H H(K K)/)/L L (240)(240)讨论讨论：若若 L L=0=0，即当明文经过最佳数据压缩编码后，其，即当明文经过最佳数据压缩编码后，其惟一解距离惟一解距离 0 0。虽然这时系统不一定满足。虽然这时系统不一定满足H H(K K)H H(M ML L)的完善保密条件，但不管截获的密报量有的完善保密条件，但不管截获的密报量有多大，密钥的含糊度仍为多大，密钥的含糊度仍为H H(K K/C Cl l)H H(K K)，即可能的密，即可能的密钥解有钥解有2 2H(K)H(K
30、)个之多个之多!信息论与密码学信息论与密码学 实际中不可能实现实际中不可能实现 L L=0=0，但是在消息进行加密之，但是在消息进行加密之 前，先进行压缩编码来减小多余度，对于提高系统安前，先进行压缩编码来减小多余度，对于提高系统安全性是绝对必要的全性是绝对必要的!多余度的存在，使得任何密码体多余度的存在，使得任何密码体制在有限密钥下制在有限密钥下(H H(K K)为有限为有限)，其惟一解距离都将是，其惟一解距离都将是有限的，因而在理论上都将是可破的。有限的，因而在理论上都将是可破的。一些使数据扩展的方式对于密码的安全是不利的一些使数据扩展的方式对于密码的安全是不利的。增大增大H H(K K)
31、是提高保密系统安全性的途径，即采用是提高保密系统安全性的途径，即采用复杂的密码体制，直至一次一密钥体制。复杂的密码体制，直至一次一密钥体制。信息论与密码学信息论与密码学 例例2-2 2-2 英语单表代换密码的密钥量英语单表代换密码的密钥量|K K=26!=26!，其密钥空间的熵为其密钥空间的熵为H H(K K)=lb(26!)=88.4 bits)=lb(26!)=88.4 bits。由例。由例2-12-1知知，=3.2bits/=3.2bits/字母，所以这一密码体制的唯一解距离字母，所以这一密码体制的唯一解距离=88.4/3.2=27.6=88.4/3.2=27.6字母。字母。此例说明，只
32、要截获到此例说明，只要截获到2828个字母长的密文，原则个字母长的密文，原则上就可能破译英语单表代换密码。这和著名密码分析家上就可能破译英语单表代换密码。这和著名密码分析家W.W.F.FriedmanF.Friedman的经验值的经验值2525个字母相符。例如，当密文量个字母相符。例如，当密文量=40=40字母，若每个字母的多余度以字母，若每个字母的多余度以=1.5=1.5计算，一个有意计算，一个有意义的脱密消息的期望数仅为义的脱密消息的期望数仅为1.21.21010-10-10。因此，当得到一。因此，当得到一个有意义的解时显然是可信赖的。但若以个有意义的解时显然是可信赖的。但若以=20=20
33、个密文字个密文字母破译，有意义的脱密解高达母破译，有意义的脱密解高达2.22.210107 7个之多，如果得到个之多，如果得到了一个有意义的解，其可信度是很低的。了一个有意义的解，其可信度是很低的。信息论与密码学信息论与密码学 例例2-3 2-3 下面给出几种密码体制对英语报文加密下面给出几种密码体制对英语报文加密时的唯一解距离。时的唯一解距离。(1)(1)周 期 为周 期 为d d的 移 位 密 码，的 移 位 密 码，H H(K K)=l b()=l b(d d!)!)，0 0=lb(=lb(d d!)/3.2=0.3dlb(!)/3.2=0.3dlb(d d/e e)字母。若选字母。若选
34、d d=27=27，则，则d d/e e1010，lb(lb(d d/e e)3.2)3.2，故，故0 0=2.7=2.7字母。字母。(2)(2)含含q q个字母表的单表代换，个字母表的单表代换，H H(K K)=lb()=lb(q q!)!)，0 0=lb(=lb(q q!)/!)/。例如。例如q q=26=26，=3.2=3.2就为例就为例2-5-62-5-6的情况的情况。(3)(3)周期为周期为d d的代换密码的代换密码(如如BeaufortBeaufort或或VigenVigenrere密密码码)。H H(K K)=lb()=lb(q qd d)=dlb)=dlbq q，0 0=(dl
35、b=(dlbq q)/)/，对英语，对英语，0 01.51.5d d。这些结果都是在统计意义下得到的，因此，只有这些结果都是在统计意义下得到的，因此，只有当处理的报文数据足够大时才适用。当处理的报文数据足够大时才适用。信息论与密码学信息论与密码学 六、实际保密性六、实际保密性 理论保密性理论保密性：码分析者有无限的时间、设备和资：码分析者有无限的时间、设备和资金条件下，惟密文攻击时密码系统的安全性。一个密码系金条件下，惟密文攻击时密码系统的安全性。一个密码系统，如果对手有无限的资源可利用，而在截获任意多密报统，如果对手有无限的资源可利用，而在截获任意多密报下仍不能被破译，则它在理论上是保密的。
36、下仍不能被破译，则它在理论上是保密的。实际保密性实际保密性：一个密码系统的破译所需要的努力，：一个密码系统的破译所需要的努力，如果超过了对手的能力如果超过了对手的能力(时间、资源等时间、资源等)时，则该系统为实时，则该系统为实际上安全保密的际上安全保密的 。保密的相对性保密的相对性:最小保障时间最小保障时间(Minimum cover time)(Minimum cover time)：信息论与密码学信息论与密码学 计算能力计算能力 (时间、费用等时间、费用等)与破译算法的有效性与破译算法的有效性 破译平均工作量破译平均工作量W(W(l l)：破译：破译l l长截获密文所需的长截获密文所需的计
37、算。计算。破译工作特性破译工作特性(Work characteristic)(Work characteristic)：W(W(l l)随随l l的变化曲线的变化曲线 ，其中，其中W(W(l l)可用人可用人-时度量。平均是在所时度量。平均是在所有可能密钥上进行的。有可能密钥上进行的。W(W(l l)可用来衡量密码系统的实际保可用来衡量密码系统的实际保密性密性。信息论与密码学信息论与密码学W(l)H(K/C)W(l)0 H(K)/l(密文量)图图2-3 2-3 破译工作特破译工作特性性信息论与密码学信息论与密码学 图中，点线表示可能的解多于一个的区域，对各可能图中，点线表示可能的解多于一个的区
38、域，对各可能的解出现的概率需分别确定；实线表示有惟一解的区域。的解出现的概率需分别确定；实线表示有惟一解的区域。由图可知，随密文量由图可知，随密文量l l增加，增加，W(W(l l)会降至一个渐近值。会降至一个渐近值。任何一个非理想系统，其工作特性的趋势大致和图任何一个非理想系统，其工作特性的趋势大致和图2-2-5-65-6一致，但一致，但W(W(l l)的绝对取值随密码体制不同相差极大。的绝对取值随密码体制不同相差极大。即使当它们的密钥含糊度即使当它们的密钥含糊度H(KH(K C Cl l)随随l l变化的曲线大致相变化的曲线大致相同时，它们的同时，它们的W(W(l l)也会有很大差别。例如
39、，密钥量和简单也会有很大差别。例如，密钥量和简单代换一样的维吉尼亚或组合维吉尼亚密码的工作特性要比代换一样的维吉尼亚或组合维吉尼亚密码的工作特性要比简单代换密码的好得多。简单代换密码的好得多。如何实现使破译一个密码系统所需的工作量极大化，如何实现使破译一个密码系统所需的工作量极大化，这是博奕论中这是博奕论中“极大化极小极大化极小”问题。仅仅从对付现有的标问题。仅仅从对付现有的标准的密码分析法是不够的，还必须确保没有轻而易举的破准的密码分析法是不够的，还必须确保没有轻而易举的破译方法。译方法。要判定密码体制的安全性绝非易事！要判定密码体制的安全性绝非易事！信息论与密码学信息论与密码学 如何保证破
40、译它所需的工作量足够大？如何保证破译它所需的工作量足够大？研究分析者可能采用的有哪些分析法，尔后估计各研究分析者可能采用的有哪些分析法，尔后估计各法破译该体制时所需的平均工作量法破译该体制时所需的平均工作量W(W(l l)。这需要有丰富的。这需要有丰富的密码分析经验，这种方法在实际中常会使用。设计者要尽密码分析经验，这种方法在实际中常会使用。设计者要尽可能在一般条件下描述这些分析方法，设法构造一种可以可能在一般条件下描述这些分析方法，设法构造一种可以抗击这类一般分析法的密码系统。抗击这类一般分析法的密码系统。估计破译一个保密系统所需的平均工作量估计破译一个保密系统所需的平均工作量W(W(l l
41、)的另的另一种途径是，将破译此密码的难度等价于解数学上的某个一种途径是，将破译此密码的难度等价于解数学上的某个已知难题。已知难题。ShannonShannon在在19491949年时虽然没有计算复杂性这样年时虽然没有计算复杂性这样的理论工具可用，但他已明确地意识到这一问题，他曾指的理论工具可用，但他已明确地意识到这一问题，他曾指出出“好密码的设计问题，本质上是寻找针对某些其它条件好密码的设计问题，本质上是寻找针对某些其它条件的一种求解难题的问题的一种求解难题的问题”。信息论与密码学信息论与密码学七、乘积密码系统七、乘积密码系统(Product cryptosystems)(Product cr
42、yptosystems)利用利用“乘积乘积”对简单密码进行组合，可构造复杂对简单密码进行组合，可构造复杂而安全的密码系统。设计当代密码有重要指导意义，许多而安全的密码系统。设计当代密码有重要指导意义，许多近代分组密码体制，几乎无一例外都采用了这一思想。近代分组密码体制，几乎无一例外都采用了这一思想。为讨论简单，设为讨论简单，设C C=MM，这类密码称为自同态，这类密码称为自同态(Endomorphic)(Endomorphic)密码。令密码。令S S1 1=(=(MM,MM,K K1 1,E E1 1,D D1 1)和和S S2 2=(=(MM,MM,K K2 2,E E2 2,D D2 2)
43、是两个自同态密码系统，它们是两个自同态密码系统，它们有相同的明文空间和密文空间。有相同的明文空间和密文空间。S S1 1和和S S1 1的乘积的乘积S S1 1S S2 2表示表示为为(MM,MM,K K1 1 K K2 2,E E,D D)。乘积密码系统的密钥为。乘积密码系统的密钥为 k k=(=(k k1 1,k k2 2)，k k1 1 K K1 1 ，k k2 2 K K2 2 加密：加密：(241)(241)b 信息论与密码学信息论与密码学EmEEmk kkk()()()1221解解 密：密：mmEDmEEDDmEEDmEDcDkkkkkkkkkkkkkkkk)()()()()(11
44、12211221212121)(,),()(由于由于k k1 1和和k k2 2独立选取，故有独立选取，故有)()(),(212121kpkpkkpkkk信息论与密码学信息论与密码学(242)(242)(243)(243)特例：幂等特例：幂等(Idempotent)(Idempotent)密码系统：密码系统：S SS S=S S2 2=S S。可以推广到可以推广到n n阶乘积密码以阶乘积密码以S Sn n表示。表示。移位、代换、仿射、移位、代换、仿射、HillHill、VigenVigen rere和置换等和置换等密码都是幂等体制。若密码是幂等的，则不会采用乘积密码都是幂等体制。若密码是幂等的
45、，则不会采用乘积S S2 2，即使用另一个密钥，也不会增大安全性。，即使用另一个密钥，也不会增大安全性。对于非幂等密码体制，增加迭代次数，会增大对于非幂等密码体制，增加迭代次数，会增大潜在的安全性。两个不同的密码进行乘积常会得到一个潜在的安全性。两个不同的密码进行乘积常会得到一个非幂等密码。非幂等密码。易于证明，若易于证明，若S S1 1和和S S2 2是幂等，则是幂等，则S S1 1S S2 2也是幂等也是幂等的。因为的。因为 (S S1 1S S2 2)(S S1 1S S2 2)=)=S S1 1(S S2 2S S1 1)S S2 2 =(=(S S1 1S S1 1)(S S2 2S
46、 S2 2)=)=S S1 1S S2 2 (244)(244)信息论与密码学信息论与密码学八、认证系统八、认证系统(Authentication systemAuthentication system)认证是认证是为了为了防止主动攻击，如对消息的内容、顺序、防止主动攻击，如对消息的内容、顺序、和时间的窜改以及重发等伪装、窜扰等的重要技术，和时间的窜改以及重发等伪装、窜扰等的重要技术，使使发送的消息具有被验证的能力，使接收者或第三者能够发送的消息具有被验证的能力，使接收者或第三者能够识别和确认消息的真伪。实现这类功能的密码系统称作识别和确认消息的真伪。实现这类功能的密码系统称作认证系统。认证系
47、统。认证目的认证目的：（1）验证信息的发送者是真的、而不是冒充的，）验证信息的发送者是真的、而不是冒充的，此为实体认证，包括信源、信宿等的认证和识别；此为实体认证，包括信源、信宿等的认证和识别；（2）验证信息的完整性，此为消息认证，验证）验证信息的完整性，此为消息认证，验证数据在传送或存储过程中未被窜改、重放或延迟数据在传送或存储过程中未被窜改、重放或延迟等。等。信息论与密码学信息论与密码学 认证的理论与技术认证的理论与技术：是保密学研究的一个重要领域，是保密学研究的一个重要领域，包括认证系统、杂凑包括认证系统、杂凑(Hash)函数、数字签名、身份证明、函数、数字签名、身份证明、认证协议等。认
48、证协议等。l l 保密性：保密性是使截获者在不知密钥条件下保密性：保密性是使截获者在不知密钥条件下不能解读密文的内容。不能解读密文的内容。l l 认证性：使任何不知密钥的人不能构造一个密认证性：使任何不知密钥的人不能构造一个密报，使意定的接收者脱密成一个可理解的消息报，使意定的接收者脱密成一个可理解的消息(合合法的消息法的消息)。l l 完整性完整性(integrity)(integrity)：在有自然和人为干扰条件：在有自然和人为干扰条件下，系统保持检测错误和恢复消息和原来发送消息下，系统保持检测错误和恢复消息和原来发送消息一致性的能力。实际中常常借助于纠、检错技术和一致性的能力。实际中常常
49、借助于纠、检错技术和杂凑技术来保证消息的完整性。杂凑技术来保证消息的完整性。信息论与密码学信息论与密码学要求：要求：l l 意定的接收者能够检验和证实消息的合法性和真实意定的接收者能够检验和证实消息的合法性和真实性。性。l l 消息的发送者对所发送的消息不能抵赖。消息的发送者对所发送的消息不能抵赖。l l 除了合法消息发送者外，其它人不能伪造合法的除了合法消息发送者外，其它人不能伪造合法的消息。而且在已知合法密文消息。而且在已知合法密文c c和相应消息和相应消息m m下，要确定下，要确定加密密钥或系统地伪造合法密文在计算上是不可行的。加密密钥或系统地伪造合法密文在计算上是不可行的。l l 必要
50、时可由第三者作出仲裁。必要时可由第三者作出仲裁。信息论与密码学信息论与密码学 认证的信息理论认证的信息理论：类似于保密系统的信息理论，可将信：类似于保密系统的信息理论，可将信息论用于研究认证系统的理论安全性和实际安全性，指息论用于研究认证系统的理论安全性和实际安全性，指出认证系统的性能极限以及设计认证码必须遵循的原则。出认证系统的性能极限以及设计认证码必须遵循的原则。保密和认证同是信息系统安全的两个重要方面，但它们保密和认证同是信息系统安全的两个重要方面，但它们是两个不同属性的问题。认证不能自动地提供保密性，是两个不同属性的问题。认证不能自动地提供保密性，而保密也不能自然地提供认证功能。一个纯
