《信息安全与信息论》PPT课件

1,信息安全的数学基础-信息论及与信息安全的关系,北京师范大学应用数学学院杨进,2,信息论与密码学,Shannon在1949年发表了一重要论文，“保密通信的通信理论”，用信息论观点系统地阐述了保密通信的问题。他提出了保密系统的模型、完善保密(Perfectsecrecy)理论、理论保密性、实际保密性的理论、设计和破译密码的基本原则，将密码学从艺术(art)变为科学。DiffieandHellman在1976年提出了公钥密码体制，(1981得DonaldG.FinkPrize论文奖，1998年获IEEEInformationTheorySocietyGoldenJubileeAwardsforTechnologicalInnovation)。Hellman引用Shannon原话，“好的密码设计本质上是寻求一个困难问题的解，相对于某种其它条件，我们可以构造密码，使其破译它(或在过程中的某点上)等价于解某个已知数学难题。”这是指引Hellman走向发现公钥密码的思想。因此，人们尊称Shannon为公钥密码学之父(Godfather)。,3,一、保密系统(SecrecySystem)(M,C,K1,K2,Ek1,Dk2),信息论与密码学,4,l信源：是产生消息的源，在离散情况下可以产生字母或符号。可以用简单概率空间描述离散无记忆源。设信源字母表为M=ai,i=0,1,q1，字母ai出现的概率为pi0，且(21)信源产生的任一长为L个符号的消息序列为m=(m1,m2,mL)miM=Zq(22)l消息空间或明文空间M：长为L的信源输出序列的集合mM=ML=ZqL(23)它含有qL个元素。若信源为有记忆时，我们需要考虑M中各元素的概率分布。当信源为无记忆时有p(m)=p(m1,m2,mL)=(24)信源的统计特性对密码设计和分析起重要作用。,信息论与密码学,5,l密钥源：是产生密钥序列的源。密钥通常是离散的，设密钥字母表为：L=kt,t=0,1,.,s-1。字母kt的概率p(kt)0，且密钥源为无记忆均匀分布，所以各密钥符号为独立等概。l密钥空间K：对于长为r的密钥序列k=k1,k2,.,krk1,krK=ZS(25)的全体，且有KKr=Zsr(26)一般消息空间K与密钥空间M彼此独立。合法的接收者知道k和密钥空间K。窃听者不知道k。双钥体制下，有两个密钥空间K1和K2、在单钥体制下K1=K2=K，此时密钥k需经安全的密钥信道由发方传给收方。,信息论与密码学,6,l密文空间C：密文c的全体构成的集合。c=(c1,c2,.,cV)=EK(m1,m2,.,mL)(27)l加密变换：Ek1E，MC，由加密器完成，即c=f(m,k1)=Ek1(m)mM，k1K1(28)l解密变换：Dk2D，CM，由加密器完成，即m=Dk2(c)mM，k2K2(29)l合法接收者：知道密文c、解密变换和密钥，信道是无扰条件下，易于从密文得到原来的消息m，即m=Dk(c)=Dk(Ek(m)(210)l密码分析者：可以得到密文c，他知道明文的统计特性、加密体制、密钥空间及其统计特性，但不知道截获的密文c所用的特定密钥。,信息论与密码学,7,密码分析者实施被动攻击(Passiveattack)：对一个保密系统采取截获密文进行分析的攻击。用其选定的变换函数h，对截获的密文c进行变换，得到m=h(c)(211)一般mm。l主动攻击(Activeattack)：非法入侵者(Tamper)、攻击者(Attcker)或黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。lA.Kerckhoff(18351903荷兰)原则：密码的安全必须完全寓于秘密钥之中。,信息论与密码学,8,通信系统与保密系统对消息m的加密变换的作用类似于向消息注入噪声。密文c就相当于经过有扰信道得到的接收消息。密码分析员就相当于有扰信道下原接收者。所不同的是，这种干扰不是信道中的自然干扰，而是发送者有意加进的，目的是使窃听者不能从c恢复出原来的消息。由此可见，通信问题和保密问题密切相关，有一定的对偶性，用信息论的观点来阐述保密问题是十分自然的事。信息论自然成为研究密码学和密码分析学的一个重要理论基础，Shannon的工作开创了用信息理论研究密码学的先河。,信息论与密码学,9,二、完善保密性令明文熵为H(M)H(ML)，密钥熵为H(K)，密文熵为H(C)=H(C)，在已知密文条件下明文的含糊度为H(ML/C)，在已知密文条件下密钥的含糊度为H(K/C)惟密文破译下，密码分析者的任务是从截获的密文中提取有关明文的信息I(ML;C)=H(ML)H(ML/C)(212)或从密文中提取有关密钥的信息I(K;C)=H(K)H(K/C)(213)由此可知，H(K/C)和H(ML/C)越大，窃听者从密文能够提取出的有关明文和密钥的信息就越小。,信息论与密码学,10,合法的接收者已知密钥和密文知H(ML/CK)=0(2514)因而有I(ML;CK)=H(ML)(215)定理2-1对任意保密系统I(ML;C)H(ML)H(K)(216)证明：由式(2-5-34)及式(2-5-22)有H(K/C)=H(K/C)H(ML/KC)=H(MLK/C)=H(ML/C)H(/MLC)H(ML/C)又H(K)H(K/C)故由式(2-14)可得I(ML;C)H(ML)H(K),信息论与密码学,11,定理说明，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。完善的(Perfect)或无条件的(Unconditionally)保密系统：I(ML;C)=0(217)密文与明文之间的互信息为零，窃听者从密文就得不到任何有关明文的信息,不管窃听者截获的密文有多少，他用于破译的计算资源有多丰富,都是无济于事的。显然，这种系统是安全的。定理2-2：完善保密系统存在的必要条件是H(K)H(ML)(218)证明：(2-16)和平均互信息的非负性知，当式(2-18)成立时必有式(2-17)。,信息论与密码学,12,完善保密系统的密钥量的对数(密钥空间为均匀分布条件下)要大于明文集的熵。当密钥为二元序列时要满足H(ML)H(M)=H(k1,k2,kr)rbits(219)定理2-3：存在有完善保密系统。证明今以构造法证明。不失一般性可假定明文是二元数字序列m=(m1,m2,mL),miGF(2)令密钥序列k=(k1,k2,kr)密文序列c=(c1,c2,cv)也都是二元序列。m和k彼此独立。今选L=r=v，并令k是一理想二元对称源(BSS)的输出，即k为随机数字序列，因而有H()=Lbits。若采用Vernam体制，则有c=Ek(m)=mk。式中，加法是逐位按模2进行，即,信息论与密码学,13,ci=miki。这等价于将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最先证明这种体制是完善保密的，并能抗击已知明文-密文下的攻击。在不知密钥条件下，任何人采用任何破译法都不会比随机猜测更好些!在实际应用中，为了安全起见，必须保证密钥以完全随机方式产生(如掷硬币)并派可靠信使通过安全途径送给对方，每次用过后的密钥都立即销毁。,信息论与密码学,14,三、冗余度P31-P32r:语言的信息率R:语言的绝对信息率冗余度=R-r题：2.3密码分析者借助自然语言的冗余度进行密码分析，冗余度越大，越容易进行破译，所以加密明文前，用一个压缩程序来降低明文的冗余度是一个非常好的选择,信息论与密码学,15,四、压缩编码在二元情况下，为实现完善保密所需的密钥量仅为Nbit。理想压缩编码可使密钥长度减至r=NH(M1,M2,ML)（224)收端先由收到的密文c利用已知密钥k恢复出压缩后的明文m=ck，再由明文m恢复原来的明文消息m。可能实现完善保密。而所需的密钥量由原来的Lbits降为H(M1,M2,ML)bit。当然，这并不能从根本上解决一次一密体制中密钥量过大的问题。但是在下面我们将会看到，加密前的数据压缩是强化保密系统的重要措施，这也是Shannon最先指出的一个重要结果。降低明文中的多余度常常会使密码分析者处于困境。,信息论与密码学,16,五、理论保密性长密文序列集C=C1,C2,.,CC，密钥的不确定性，即从密钥含糊度，由条件熵性质知H(K/C)=(K/C1,C+1)H(K/C1,C)(225)显然，当=0时的密钥的含糊度就是密钥的熵H(K)。即随着的加大，密钥含糊度是非增的。即随着截获密文的增加，得到的有关明文或密钥的信息量就增加，而保留的不确定性就会越来越小。若H=(K/C)0，就可惟一地确定密钥K，而实现破译。0=minN|H(K/C)0(226),信息论与密码学,17,惟一解距离(Unicitydistance)对于给定的密码系统，在惟密文攻击下的0=minN|H(K/C)0(227)N是正整数集。当截获的密报量大于0时，原则上就可惟一地确定系统所用的密钥，即原则上可以破译该密码。0与明文多余度的关系0H(K)/L(228)图2-2给出H(K)l的典型变化特性。,信息论与密码学,18,信息论与密码学,19,证明：令Ml，Cl和K都是二元序列集。K和Cl之间平均互信息为I(K;Cl)=H(Cl)K(Cl/K)(229)对于典型的密码系统，当l足够小时，二元密文序列的前lbit实际上是完全随机的二元数字，因而有H(Cl)lbits(230)由熵的性质有H(MlCl/K)=H(Ml/K)H(Cl/MlK)=H(Cl/K)H(Ml/ClK)(231)式中：H(Cl/MlK)=0(232)H(Ml/ClK)=0(233)又由所有密码系统的明文和密钥统计独立，即,信息论与密码学,20,H(Ml/K)=H(Ml)(234)将上述三式代入式(2-5-49)得H(Cl/K)=H(Ml)(235)对于多数密码系统和相应的明文源，在l不太大时，例如lL，不确定性H(Cl/K)随l近似于线性关系增加，因而可将上式写成H(Cl|K)H(ML)1lL(236)将式(2-5-48)和式(2-5-54)代入式(2-5-47)得(237)由式(2-5-41)知，上式括号中的量是L长二元信源序列的多余度，故有I(K;CL)=lL0L1(238)又由于,信息论与密码学,21,I(K;CL)=H(K)H(K/Cl)因而有H(K/Cl)H(K)lL(239)由此可见，当l足够小时，密钥含糊度将随截获的密文长度l线性地降低，直到当H(KCl)变得相当小为止。由式(2-5-57)及唯一解距离0的定义可得0H(K)/L(240)讨论：若L=0，即当明文经过最佳数据压缩编码后，其惟一解距离0。虽然这时系统不一定满足H(K)H(ML)的完善保密条件，但不管截获的密报量有多大，密钥的含糊度仍为H(K/Cl)H(K)，即可能的密钥解有2H(K)个之多!,信息论与密码学,22,实际中不可能实现L=0，但是在消息进行加密之前，先进行压缩编码来减小多余度，对于提高系统安全性是绝对必要的!多余度的存在，使得任何密码体制在有限密钥下(H(K)为有限)，其惟一解距离都将是有限的，因而在理论上都将是可破的。一些使数据扩展的方式对于密码的安全是不利的。增大H(K)是提高保密系统安全性的途径，即采用复杂的密码体制，直至一次一密钥体制。,信息论与密码学,23,例2-2英语单表代换密码的密钥量|K=26!，其密钥空间的熵为H(K)=lb(26!)=88.4bits。由例2-1知，=3.2bits/字母，所以这一密码体制的唯一解距离=88.4/3.2=27.6字母。此例说明，只要截获到28个字母长的密文，原则上就可能破译英语单表代换密码。这和著名密码分析家W.F.Friedman的经验值25个字母相符。例如，当密文量=40字母，若每个字母的多余度以=1.5计算，一个有意义的脱密消息的期望数仅为1.210-10。因此，当得到一个有意义的解时显然是可信赖的。但若以=20个密文字母破译，有意义的脱密解高达2.2107个之多，如果得到了一个有意义的解，其可信度是很低的。,信息论与密码学,24,例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的代换密码(如Beaufort或Vigenre密码)。H(K)=lb(qd)=dlbq，0=(dlbq)/，对英语，01.5d。这些结果都是在统计意义下得到的，因此，只有当处理的报文数据足够大时才适用。,信息论与密码学,25,六、实际保密性理论保密性：码分析者有无限的时间、设备和资金条件下，惟密文攻击时密码系统的安全性。一个密码系统，如果对手有无限的资源可利用，而在截获任意多密报下仍不能被破译，则它在理论上是保密的。实际保密性：一个密码系统的破译所需要的努力，如果超过了对手的能力(时间、资源等)时，则该系统为实际上安全保密的。保密的相对性:最小保障时间(Minimumcovertime)：,信息论与密码学,26,计算能力(时间、费用等)与破译算法的有效性破译平均工作量W(l)：破译l长截获密文所需的计算。破译工作特性(Workcharacteristic)：W(l)随l的变化曲线，其中W(l)可用人-时度量。平均是在所有可能密钥上进行的。W(l)可用来衡量密码系统的实际保密性。,信息论与密码学,27,W(l),H(K/C),信息论与密码学,28,图中，点线表示可能的解多于一个的区域，对各可能的解出现的概率需分别确定；实线表示有惟一解的区域。由图可知，随密文量l增加，W(l)会降至一个渐近值。任何一个非理想系统，其工作特性的趋势大致和图2-5-6一致，但W(l)的绝对取值随密码体制不同相差极大。即使当它们的密钥含糊度H(KCl)随l变化的曲线大致相同时，它们的W(l)也会有很大差别。例如，密钥量和简单代换一样的维吉尼亚或组合维吉尼亚密码的工作特性要比简单代换密码的好得多。如何实现使破译一个密码系统所需的工作量极大化，这是博奕论中“极大化极小”问题。仅仅从对付现有的标准的密码分析法是不够的，还必须确保没有轻而易举的破译方法。要判定密码体制的安全性绝非易事！,信息论与密码学,29,如何保证破译它所需的工作量足够大？研究分析者可能采用的有哪些分析法，尔后估计各法破译该体制时所需的平均工作量W(l)。这需要有丰富的密码分析经验，这种方法在实际中常会使用。设计者要尽可能在一般条件下描述这些分析方法，设法构造一种可以抗击这类一般分析法的密码系统。估计破译一个保密系统所需的平均工作量W(l)的另一种途径是，将破译此密码的难度等价于解数学上的某个已知难题。Shannon在1949年时虽然没有计算复杂性这样的理论工具可用，但他已明确地意识到这一问题，他曾指出“好密码的设计问题，本质上是寻找针对某些其它条件的一种求解难题的问题”。,信息论与密码学,30,七、乘积密码系统(Productcryptosystems)利用“乘积”对简单密码进行组合，可构造复杂而安全的密码系统。设计当代密码有重要指导意义，许多近代分组密码体制，几乎无一例外都采用了这一思想。为讨论简单，设C=M，这类密码称为自同态(Endomorphic)密码。令S1=(M,M,K1,E1,D1)和S2=(M,M,K2,E2,D2)是两个自同态密码系统，它们有相同的明文空间和密文空间。S1和S1的乘积S1S2表示为(M,M,K1K2,E,D)。乘积密码系统的密钥为k=(k1,k2)，k1K1，k2K2加密：(241),信息论与密码学,31,解密：,由于k1和k2独立选取，故有,信息论与密码学,(242),(243),32,特例：幂等(Idempotent)密码系统：SS=S2=S。可以推广到n阶乘积密码以Sn表示。移位、代换、仿射、Hill、Vigenre和置换等密码都是幂等体制。若密码是幂等的，则不会采用乘积S2，即使用另一个密钥，也不会增大安全性。对于非幂等密码体制，增加迭代次数，会增大潜在的安全性。两个不同的密码进行乘积常会得到一个非幂等密码。易于证明，若S1和S2是幂等，则S1S2也是幂等的。因为(S1S2)(S1S2)=S1(S2S1)S2=(S1S1)(S2S2)=S1S2(244),信息论与密码学,33,八、认证系统(Authenticationsystem)认证是为了防止主动攻击，如对消息的内容、顺序、和时间的窜改以及重发等伪装、窜扰等的重要技术，使发送的消息具有被验证的能力，使接收者或第三者能够识别和确认消息的真伪。实现这类功能的密码系统称作认证系统。认证目的：（1）验证信息的发送者是真的、而不是冒充的，此为实体认证，包括信源、信宿等的认证和识别；（2）验证信息的完整性，此为消息认证，验证数据在传送或存储过程中未被窜改、重放或延迟等。,信息论与密码学,34,认证的理论与技术：是保密学研究的一个重要领域，包括认证系统、杂凑(Hash)函数、数字签名、身份证明、认证协议等。保密性：保密性是使截获者在不知密钥条件下不能解读密文的内容。认证性：使任何不知密钥的人不能构造一个密报，使意定的接收者脱密成一个可理解的消息(合法的消息)。完整性(integrity)：在有自然和人为干扰条件下，系统保持检测错误和恢复消息和原来发送消息一致性的能力。实际中常常借助于纠、检错技术和杂凑技术来保证消息的完整性。,信息论与密码学,35,要求：意定的接收者能够检验和证实消息的合法性和真实性。消息的发送者对所发送的消息不能抵赖。除了合法消息发送者外，其它人不能伪造合法的消息。而且在已知合法密文c和相应消息m下，要确定加密密钥或系统地伪造合法密文在计算上是不可行的。必要时可由第三者作出仲裁。,信息论与密码学,36,认证的信息理论：类似于保密系统的信息理论，可将信息论用于研究认证系统的理论安全性和实际安全性，指出认证系统的性能极限以及设计认证码必须遵循的原则。保密和认证同是信息系统安全的两个重要方面，但它们是两个不同属性的问题。认证不能自动地提供保密性，而保密也不能自然地提供认证功能。一个纯认证系统的模型如图2-4所示。在这个系统中的发送者通过一个公开信道将消息送给接收者，接收者不仅想收到消息本身，而且还要验证消息是否来自合法的发送者及消息是否经过窜改。系统中的密码分析者不仅要截收和分析信道中传送的密报，而且可伪造密文送给接收者进行欺诈，称其为系统的窜扰者(Tamper)更加贴切。实际认证系统可能还要防止收、发之间的相互欺诈。,信息论与密码学,37,信息论与密码学,图2-4纯认证系统模型,38,信息论与密码学,认证编码在要发送的消息中引入多余度，使通过信道传送的可能序列集Y大于消息集X。对于任何选定的编码规则(相应于某一特定密钥)：发方可从Y中选出用来代表消息的许用序列，即码字；收方可根据编码规则唯一地确定出发方按此规则向他传来的消息。窜扰者由于不知道密钥，因而所伪造的假码字多是Y中的禁用序列，收方将以很高的概率将其检测出来而被拒绝。认证系统设计者的任务是构造好的认证码(AuthenticationCode)，使接收者受骗概率极小化。令xX为要发送的消息，kK是发方选定的密钥，y=A(x,k)Y是表示消息x的认证码字，Ak=y=A(x,k),xX为认证码。Ak是Y中的许用(合法)序列集，而其补集Ak则为禁用序列集，且AkAk=Y。,39,信息论与密码学,接收者知道认证编码A(，)和密钥k，故从收到的y可惟一地确定出消息x。窜扰者虽然知道X、Y、y、A(，)，但不知道具体密钥k，他的目标是想伪造出一个假码字y*，使y*Ak，使接收者收到y*后可以密钥k解密得到一个合法的、可能由发端送出的消息x*，使接收者上当受骗。如果发生这一事件，则认为窜扰者欺诈成功。窜扰者攻击的基本方式：模仿伪造(ImpersonativeFraudulent)，窜扰者在未观测到认证信道中传送的合法消息(或认证码字)条件下伪造假码字y*，称其为无密文伪造更合适些。若接收者接受y*作为认证码字，则说窜扰者攻击成功。,40,信息论与密码学,代换伪造(SubstitutionFraudulent)，窜扰者截收到认证系统中的认证码字y后，进行分析并伪造假认证码字y*，故可称为已知密文伪造。若接收者接受y*为认证码字，则称窜扰者攻击成功。窜扰者可以自由地选择最有利的攻击方式。窜扰者成功概率(接收者受骗概率)：pd=maxpI，pS(245)pI：窜扰者采用模仿攻击时最大可能的成功概率ps：在代换攻击时最大可能的成功概率。,41,信息论与密码学,完善认证性(PerfectAuthentication)：令#Y、#X、#K分别表示密文空间、消息空间、密钥空间中概率为非零的元素的个数。一般认证编码中#Y#X，且认证码中元素个数#Ak#X。对每个kK，至少有#X个不同的密文使p(Y=y|K=k)0。若对手采用模仿伪造策略，完全随机地以非零概率从Y中选出一个作为伪造密文(认证码字)送给接收者，则其成功的概率有(246),42,信息论与密码学,要安全性高，即要pI小，需有#Y#X。由于#X0，要求完全保护，即要pI=0是不可能实现的。而且可以证明，要求式(6-1-2)等号成立的充要条件是：对任一kK，都恰有#Ak#X。这表明采用随机密码不能使上式等号成立。由于认证系统不能实现完全保护，故将完善认证定义为对给定认证码空间，能使受骗率pd最小的认证系统(在此意义下，即使对#Y=#X时的平凡情况，此时pd=1，也有完善认证可言)。,43,信息论与密码学,若在最佳模仿策略下窜扰者只能随机地选取一个yY，则有H(Y)=log#Y(247)而若在任一给定密钥下，任一认证码字在认证码A中等概出现，则有H(Y|K)=log#X(248)对式(6-1-2)两边取对数可得logpIlog#Xlog#Y=H(Y)H(Y|K)=I(Y；K)上述结果可归结为定理6-1-1。定理6-1-1认证信道有logpII(Y；K)(249),44,信息论与密码学,等号成立的充要条件为式(6-1-3)和(6-1-4)成立，且logpdI(Y；K)(250)等号成立的必要条件为式(247)和(248)成立。Simmons称式(250)为认证信道的容量。定义完善认证是使式(2-50)等号成立的认证系统。由式(2-50)可知，即使系统是完善的，要使pd小就必须使I(Y；K)大，也就是说使窜扰者从密文Y中可提取更多的密钥信息！而由式I(Y；K)=H(K|Y)H(K)知，在极端情况下，当H(K|Y)=0即窜扰者可从Y获取有关密钥的全部信息时有logpdH(K)(251),45,信息论与密码学,即有pd#K(250)这是一个平凡的下限。Gilbert等曾给出一个更强的下限。定理6-1-3对具有保密的认证(窜扰者不知信源状态)有logpd1/2H(K)(250)而对无保密的认证(窜扰者知道信源状态)有logpd1/2H(K)H(XY)H(Y)=1/2H(K)H(X|Y)(251)系(252),46,信息论与密码学,类似于保密系统的安全性，认证系统的安全性也划分为两大类，即理论安全性和实际安全性。理论安全性又称作无条件安全性，就是我们上面所讨论的。它与窜扰者的计算能力或时间无关，也就是说窜扰者破译体制所做的任何努力都不会优于随机试凑方式。实际安全性是根据破译认证体制所需的计算量来评价其安全性的。如果破译一个系统在原理上是可能的，但以所有已知的算法和现有的计算工具不可能完成所要求的计算量，就称其为计算上安全的。如果能够证明破译某体制的困难性等价于解决某个数学难题，就称其为可证明安全的，如RSA体制。,47,信息论与密码学,这两种安全性虽都是从计算量来考虑，但不尽相同，计算安全要算出或估计出破译它的计算量下限，而可证明安全则要从理论上证明破译它的计算量不低于解已知难题的计算量。,48,信息论与密码学,认证码上面给出了认证系统安全性指标pd的下限，本节将研究如何构造认证码使其接近或达到其性能下限。无条件安全认证码和纠错码理论互为对偶。这两者都需要引入多余数字，在信道中可传送的序列集中只有一小部分用于传信。这是认证和纠错赖以实现的基本条件。纠错码的目的是抗噪声等干扰，要求将码中各码字配置得尽可能地散开(如最小汉明距离极大化)，以保证在干扰作用下所得到的接收序列与原来的码字最接近。在最大似然译码时可以使平均译码错误概率极小化。认证码的目的是防止伪造和受骗。对于发送的任何消息序列(或码字)，窜扰者采用最佳策略所引入的代换或模拟伪造序列应尽可能地散布于信道可传送的序列集中。,49,信息论与密码学,在认证系统中，密钥的作用类似于信道的干扰，在它们的控制下变换编码规则，使造出的代表消息的码字尽可能交义地配置，即将消息空间X最佳地散布于输出空间(信道传送序列集)Y之中，以使窜扰者在不知道密钥情况下，伪造成功的概率极小化。,50,信息论与密码学,九、杂凑函数(HashFunction)将任意长数字串M映射成一个较短的定长输出数字串H的函数，以h表示，h(M)易于计算，称H=h(M)为M的杂凑值，也称杂凑码、杂凑结果等或简称杂凑。特点：H打上了输入数字串的烙印，为数字指纹(DigitalFingerPrint)。h是多对一映射，因此我们不能从H求出原来的M，但可以验证任一给定序列M是否与M有相同的杂凑值。分类：密码杂凑函数，有密钥控制，以h(k,M)表示。其杂凑值不仅与输入有关，而且与密钥有关，只有持此密钥的人才能计算出相应的杂凑值，因而具有身份验证功能，如消息认证码MACANSIX9.9。杂凑值也是一种认证符或认证码。它要满足各种安全性要求，密码杂凑函数在现在密码学中有重要作用。,51,信息论与密码学,一般杂凑函数，无密钥控制。无密钥控制的单向杂凑函数，其杂凑值只是输入字串的函数，任何人都可以计算，因而不具有身份认证功能，只用于检测接收数据的完整性，如窜改检测码MDC，用于非密码计算机应用中。应用：在密码学和数据安全技术中，它是实现有效、安全可靠数字签字和认证的重要工具，是安全认证协议中的重要模块。别名：压缩(Compression)函数、紧缩(Contraction)函数、数据认证码(DataAuthenticationCode)、消息摘要(MessageDigest)、数字指纹、数据完整性校验(DataIntegityCheck)、密码检验和(CryptographicCheckSum)、消息认证码MAC(MessageAuthenticationCode)、窜改检测码MDC(ManipulationDetectionCode)等。,52,信息论与密码学,密码学中所用的杂凑函数必须满足安全性的要求，要能防伪造，抗击各种类型的攻击，如生日攻击、中途相遇攻击等等。为此，必须深入研究杂凑函数的性质，从中找出能满足密码学需要的杂凑函数。,53,信息论与密码学,杂凑函数、认证码与检错码的关系杂凑函数、认证码与检错码都是利用冗余度。线性分组检错码是在长为L的消息数字上增加n比特校验位，构成一个长为Ln(bit)线性码。GF(2)上Ln维线性空间中的L维子空间就是这类线性分组检错码的码空间。当码字在传输过程中被窜扰，若结果不属于码空间，收端通过对n个一致检验关系的检验可以实现检错。一个好的检错线性码在于使不可检错概率极小化，其最佳码的不可检错上限为pd2-n1(1p)n(253)式中p是信道误码率。在抗主动攻击下，可认为p=1/2。而有pd2-n(254),54,信息论与密码学,线性分组检错码是一种MDC杂凑，可作为数据完整性检验，但不能作为身份认证。二元认证码是将长为L的消息bit序列映射为Lnbit序列的编码。在不同密钥下，同一消息序列被映射为不同的码序列。为了实现无条件安全认证，希望在密钥控制下能将消息所对应的码字在尽可能交叉地配置，使不知密钥的窜扰者成功的概率极小化。模仿伪造成功概率(255)此与最佳线性检错码的不可检错概率的上限一致。窜扰成功的概率限由(6-1-3)有(256),55,信息论与密码学,杂凑函数可以看作是一种非线性认证码，将Lbit输入消息M变成码字M|H，其中H是M的杂凑值，一般为nbit。故码长为Ln(bit)。这种非线性码可能数极大，即相应的密钥空间K可以很大，但从式(2-55)和式(2-56)式可以看出#K22n是无作用的。由此可以得出一个重要结论，即对于nbit杂凑值下，选择密钥比特数大于2nbit是无意义的。这对于设计杂凑算法有重要意义。这是将杂凑函数看作是一种认证编码给我们的启示。对于线性分组检测码来说，其编码规则是固定的。因而#K=1。虽然其不可检错误的概率上界为2-n，但Pd的下界为1。可见它不能抗击窜扰者的攻击。,56,信息论与密码学,杂凑函数压缩输入数字串与认证编码之间的差别在于，后者是对固定长Lbits进行编码成Lnbits码字，而前者对输入字串长度未加限制。一般Lnbit，且当L不是n的整数倍时，采用填充办法凑成L/n倍(表示取不小于括号内数的最小整数)。虽然式(2-55)给出的对任意L取值模仿攻击成功概率下限都是2-n。但对杂凑函数来说，输入空间的选择远大于认证码的情况。为了减小碰撞，通常都将输入消息数字串长度作为参数纳入最后一个分段中，这样攻击者在试图找到伪消息M与发送消息M的杂凑值一样时，必须使M的长度和M的长度一致才合法，从而大大增加了攻击的难度。这种技术由Merkle和Damgrd等提出，称作MD强化技术。Damgrd等证明经过MD强化后，杂凑算法抗自由起始攻击的强度等价于迭代函数的强度。,57,十、密码学与计算复杂性计算复杂性理论始于60年代，研究为什么某些计算不能有效地完成，其内在原因是什么，它与信息论有广泛而深刻的联系。两者在研究史、理论、技术和方法论上都存在着密切关系。Shannon在1949年曾指出几乎所有有n个输入的布尔函数，其计算所要求的门的个数都随n指数增长。Kolmogorov复杂性：为计算一个问题所需的“典型”输入长度。,信息论与密码学,58,通信复杂性：两个代理人各有一半输入bit，通过通信交换尽可能少的信息完成一个布尔函数的计算。可解决并行复杂性的下限以及在芯片上计算函数所需的面积和时间等问题。公钥密码学中的加密、签字、智力朴克、零知识证明、概率性检验证明(ProbabilisticallyCheckableProofs)、证实和近似问题的难度等问题都和计算复杂性理论有密切关系。概率性检验证明是当今复杂性理论中最为深刻的结果。,信息论与密码学,59,现代密码学的一些新理论，特别是安全性的形式证明理论，也是建立在计算复杂性理论之上的。这一极为重要而又很前沿的问题。当今，任何密码算法、协议的设计和相应标准的制定，都不能回避可证明安全性，都必须通过这一理论的严格检验。,信息论与密码学,60,密码与计算复杂性关系Shannon1949指出“设计好的密码问题本质上是寻求在某些其它条件下的一