第六讲认证与杂凑函数课件.ppt_163文库

资源描述

1、2022-12-2812022-12-282 保密的目的是防止对手破译系统中的机密信息保密的目的是防止对手破译系统中的机密信息。认证认证(Authentication)是防止主动攻击，是防止主动攻击，如伪装、窜扰等，的重的重要技术要技术，包括对消息的内容、顺序、和时间的窜改以及重发等。认证目的认证目的：（1）验证信息的发送者是真的、而不是冒充的，此为实体实体认证认证，包括信源、信宿等的认证和识别；（2）验证信息的完整性验证信息的完整性，此为消息认证，验证数据在传送或存储过程中未被窜改、重放或延迟等。认证的理论与技术认证的理论与技术：认证和认证系统认证和认证系统、杂凑杂凑(Hash)函数、数数字

2、签名字签名、身份证明身份证明、认证协议认证协议。2022-12-283一、认证与认证系统认证与认证系统类似于保密系统的信息理论，可将信息论用于研究认证系统的理论安全性和实际安全性问题，指出认证系统的性能极限以及设计认证码必须遵循的原则。保密和认证同是信息系统安全的两个重要方面，但它们是两个不同属性的问题。认证不能自动地提供保密性，而保密也不能自然地提供认证功能。一个纯认证系统的模型如图6-1-1所示。在这个系统中的发送者通过一个公开信道将消息送给接收者，接收者不仅想收到消息本身，而且还要验证消息是否来自合法的发送者及消息是否经过窜改。系统中的密码分析者不仅要截收和分析信道中传送的密报，而且可

3、伪造密文送给接收者进行欺诈，称其为系统的窜扰者窜扰者(Tamper)更加贴切。实际认证系统可能还要防止收、发之间的相互欺诈。2022-12-284一、认证与认证系统认证与认证系统图图6-1-1 纯认证系统模型纯认证系统模型安全信道信道窜扰者认证编码器认证译码器信信源源信宿密钥源认证信道2022-12-285一、认证与认证系统认证与认证系统认证编码：认证编码：在要发送的消息中引入多余度，使通过信道传送的可能序列集Y大于消息集X。对于任何选定的编码规则(相应于某一特定密钥)：发方可从Y中选出用来代表消息的许用许用序列序列，即码字码字；收方可根据编码规则唯一地确定出发方按此规则向他传来的消

4、息。窜扰者由于不知道密钥，因而所伪造的假码字多是Y中的禁用序列禁用序列，收方将以很高的概率将其检测出来而被拒绝。认证系统设计者的任务是构造好好的认证码认证码(Authentication Code)，使接收者受骗概率受骗概率极小小化。令x X为要发送的消息，k K是发方选定的密钥，y=A(x,k)Y是表示消息x的认证码字认证码字，Ak=y=A(x,k),x X为认证码。Ak是Y中的许用许用(合法合法)序列集序列集，而其补集Ak则为禁用序禁用序列集列集，且AkAk=Y。2022-12-286一、认证与认证系统认证与认证系统接收者知道认证编码A(，)和密钥k，故从收到的y可可惟一地确定出消息x。

5、窜扰者虽然知道X、Y、y、A(，)，但不知道具体密钥k，他的目标是想伪造出一个假码字y*，使y*Ak，使接收者收到y*后可以密钥k解密得到一个合法的、可能由发端送出的消息x*，使接收者上当受骗。如果发生这一事件，则认为窜扰者欺诈成功。窜扰者攻击的基本方式窜扰者攻击的基本方式：模仿伪造模仿伪造(Impersonative Fraudulent)，窜扰者在未观测到认证信道中传送的合法消息(或认证码字)条件下伪造假码字y*，称其为无密文伪造无密文伪造更合适些。若接收者接受y*作为认证码字，则说窜扰者攻击成功。2022-12-287一、认证与认证系统认证与认证系统代换伪造代换伪造(Substitut

6、ion Fraudulent)，窜扰者截收到认证系统中的认证码字y后，进行分析并伪造假认证码字y*，故可称为已知密文伪造已知密文伪造。若接收者接受y*为认证码字，则称窜扰者攻击成功。窜扰者可以自由地选择最有利的攻击方式。窜扰者成功概率窜扰者成功概率(接收者受骗概率)：pd=maxpI，pS (611)pI：窜扰者采用模仿攻击时最大可能的成功概率 ps：在代换攻击时最大可能的成功概率。完善认证性完善认证性(Perfect Authentication)：令#Y、#X、#K分别表示密文空间、消息空间、密钥空间中概率为非零的元素的个数。一般认证编码中#Y#X，且认证码中元素个数#Ak#X2022-1

7、2-288一、认证与认证系统认证与认证系统对每个k K，至少有#X个不同的密文使p(Y=y|K=k)0。若对手采用模仿伪造策略，完全随机地以非零概率从Y中选出一个作为伪造密文(认证码字)送给接收者，则其成功的概率有 (612)要安全性高，即要pI小，需有#Y#X。由于#X0，要求完全保护，即要pI=0是不可能实现的。而且可以证明，要求式(6-1-2)等号成立的充要条件是：对任一kK，都恰有#Ak#X。这表明采用随机密码不能使上式等号成立。由于认证系统不能实现完全保护，故将完善认证定义为对给定认证码空间，能使受骗率pd最小的认证系统(在此意义下，即使对#Y=#X时的平凡情况，此时pd=1，也有

8、完善认证可言)。YXYApI#k#min2022-12-289一、认证与认证系统认证与认证系统若在最佳模仿策略下窜扰者只能随机地选取一个yY，则有H(Y)=log#Y (613)而若在任一给定密钥下，任一认证码字在认证码A中等概出现，则有 H(Y|K)=log#X (614)对式(6-1-2)两边取对数可得 log pIlog#Xlog#Y=H(Y)H(Y|K)=I(Y；K)定理定理6-1-1 认证信道有 log pII(Y；K)(615)等号成立的充要条件为式(6-1-3)和(6-1-4)成立，且 log pd I(Y；K)(616)等号成立的必要条件为式(6-1-3)和(6-1-4)成立

10、11一、认证与认证系统认证与认证系统定义定义6-1-2 完善认证是使式(6-1-6)等号成立的认证系统。由式(6-1-6)可知，即使系统是完善的，要使pd小就必须使I(Y；K)大，也就是说使窜扰者从密文Y中可提取更多的密钥信息！而由式(6-1-7)知，在极端情况下，当 H(K|Y)=0 即窜扰者可从Y获取有关密钥的全部信息时有 log pd H(K)(6116)即有 pd#K (6117)这是一个平凡的下限。Gilbert等曾给出一个更强的下限。定理定理6-1-3 对具有保密的认证(窜扰者不知信源状态)有 log pd 1/2H(K)(6118)而对无保密的认证(窜扰者知道信源状态)有202

13、证系统认证与认证系统类似于保密系统的安全性，认证系统的安全性也划分为两大类，即理论安全性理论安全性和实际安全性实际安全性。理论安全性又称作无条件安全性无条件安全性，就是我们上面所讨论的。它与窜扰者的计算能力或时间无关，也就是说窜扰者破译体制所做的任何努力都不会优于随机试凑方式。际安全性是根据破译认证体制所需的计算量来评价其安全性的。如果破译一个系统在原理上是可能的，但以所有已知的算法和现有的计算工具不可能完成所要求的计算量，就称其为计算上安全计算上安全的。如果能够证明破译某体制的困难性等价于解决某个数学难题，就称其为可证明安全的可证明安全的，如RSA体制。这两种安全性虽都是从计算量来考虑，但

14、不尽相同，计算安全要算出或估计出破译它的计算量下限，而可证明安全则要从理论上证明破译它的计算量不低于解已知难题的计算量。2022-12-2815 构造认证码使其接近或达到其性能下限。对偶性对偶性：无条件安全认证码和纠错码理论互为对偶。这两者都需要引入多余数字，在信道中可传送的序列集中只有一小部分用于传信。这是认证和纠错赖以实现的基本条件。纠错码的目的是抗噪声等干扰，要求将码中各码字配置得尽可能地散开(如最小汉明距离极大化)，以保证在干扰作用下所得到的接收序列与原来的码字最接近。在最大似然译码时可以使平均译码错误概率极小化。认证码的目的是防止伪造和受骗。对于发送的任何消息序列(或码字)，窜扰者采

15、用最佳策略所引入的代换或模拟伪造序列应尽可能地散布于信道可传送的序列集中。在认证系统中，密钥的作用类似于信道的干扰，在它们的控制下变换编码规则，使造出的代表消息的码字尽可能交义地配置，即将消息空间X最佳地散布于输出空间(信道传送序列集)Y之中，以使窜扰者在不知道密钥情况下，伪造成功的概率极小化。2022-12-2816 例例6-2-1 令X=0,1，Y=00,01,10,11，K=0,1。认证码如下表：这种认证编码就是在消息xi后链接上密钥ki，yj=(xi|ki)(621)可将ki看作是对消息xi的签字，或称其为xi的认证符认证符(authenticator)。类似于系统纠错码，这种认证码字

16、的前面部分就是消息数字本身，因此它对消息本身是不保密的。yjxi0 1kt0 0 1 00 1 1 1012022-12-2817 但其H(KY)=0，因而有I(Y;K)=1 bit，由此可知有pI1/2。但对j，p(yj为认证码字)=1/2，故有pI=1/2，此为最小可能的取值。但当窜扰者截获到yj后，就会知道当前所用密钥下认证码的另一个码字，因而总可用代换攻击取得成功。所以，有。这一认证方案无安全性可言。本例说明，代换攻击较模仿攻击更难于防范。例例6-2-2 条件同例6-2-1，但K=00,01,11。认证码如下表：ppSdI YZ 121 2(;)/xi yj 0 10 0 1 00

17、1 1 10 0 1 10 1 1 00 00 11 01 1kt2022-12-2818 这种认证码仍是链接形式，即 yj=(xi|f(xi,kt)(622)式中，f(xi,kt)为给定kt下对于消息xi的认证符。例6-2-1中的认证符是其特例，即f(xi,kt)=kt。由于消息数字xi直接在信道中传送，此编码对消息本身不保密。对任一给定的yj，可能的密钥有两个，因而H(KY)=1 bit，I(Y;K)=H(K)H(KY)=21=1 bit。由此可知有。一旦观察到yj，例如yj=(0,0)，窜扰者将有两种可能的码字(1 0)或(1 1)可作为代换伪造的备选者。而对于合法的接收者，由于他知道密

18、钥而可惟一地确定其中之一。因此pS=1/2，故此例下有pd=max(pI,pd)=pI=pS=1/2。不管X的统计特性如何，此码都是完善的。2022-12-2819 例例6-2-3 条件同例6-2-2。认证码如下表：此码不再是系统形式码字,yj=f(xi,kt)（623）的前一部分，不再是消息数字，而是经密钥作用后的密文。对所有i,j,p(yj|xj)=1/4，因此，系统提供了完善保密性。又H(KY)=1 bit，H(K)=2 bit，I(Y;K)=1 bit，故有pI=1/2。但是H(KY)=0，窜扰者一旦观察到yj就可成功地选择其补作为代换伪造码字，因此，ps=1=pd 。这种认证码在代换

19、攻击下无安全性可言。yjxi0 1kt0 0 1 10 1 1 01 0 0 11 1 0 00 00 11 01 12022-12-2820 例例6-2-4 条件同例6-2-2，认证码如下表：此认证码为非系统形式，且对消息数字可提供完善保密性。又H(K)=2 bit，H(K|Y)=1 bit，故I(Y;Z)=1 bit。而且对所有j，p(yj为认证码字)=1/2，故pI=1/2。若已知yj，例如yj=(0 0)，窜扰者有两种可能的选择：(1 0)或(0 1)，分别与kt=(0 0)和(0 1)对应，即其成功概率或为p(x=1)(kt=(0 0)时)，或为p(x=0)(kt=(01)时。因此，

20、pS1/2，当且仅当p(x=1)=p(x=0)=1/2时，有pS=1/2，此时pd=pI=pS=1/2，达到完善认证。可见，消息等概是实现完善认证的条件之一。yjxi0 1kt0 0 1 00 1 0 01 1 0 11 0 1 10 00 11 01 12022-12-2821 由上述几个简单的例子可以看出，在同样的编码参数下，不同的编码方案的保密和认证性能相差很大，研究认证编码理论可为认证系统设计提供有效工具。上一节给出了构造完善认证体制的理论。从式(6-1-2)知，要pI小，需选#Ak小，#Y要大。而#Ak的最小可能值为#X。而且我们已知，实现完善认证的必要条件是对所有k，#Ak相等。G

21、ilbert等利用区组设计构造了一批较有效的可使pd达到或接近式(6-1-3)下限的无条件认证码。Simmons对各种认证码进行了分类，并将例6-2-2的完善认证码进行了推广，利用正交阵列构造认证码。Stinson、万哲先等利用此法得到了一些新的认证码，认证码的研究还刚刚开始，远没有纠错码那么成熟，本节也只介绍了一些基本概念。2022-12-2822杂凑函数杂凑函数杂凑杂凑(Hash)函数函数：将任意长的数字串M映射成一个较短的定长输出数字串H的函数，以h表示，h(M)易于计算，称H=h(M)为M的杂凑值，杂凑值，也称杂凑码、杂凑结果等或简称杂凑。特点特点：H打上了输入数字串的烙印，为数字指

22、纹数字指纹(Digital Finger Print)。h是多对一映射多对一映射，因此我们不能从H求出原来的M，但可以验证任一给定序列M是否与M有相同的杂凑值。分类分类：密码杂凑函数密码杂凑函数，有密钥控制，以h(k,M)表示。其杂凑值不仅与输入有关，而且与密钥有关，只有持此密钥的人才能计算出相应的杂凑值，因而具有身份验证功能具有身份验证功能，如消息认证码MACANSI X 9.9。杂凑值也称作认证符认证符(Authenticator)或认认证码证码。它要满足各种安全性要求，密码杂凑函数在现在密码学中有重要作用。2022-12-2823杂凑函数杂凑函数一般杂凑函数一般杂凑函数，无密钥控制。无

23、密钥控制的单向杂凑函数，其杂凑值只是输入字串的函数，任何人都可以计算，因而不具有身份认证功能不具有身份认证功能，只用于检测接收数据的完整性，如窜改检测码MDC，用于非密码计算机应用中。应用：应用：在密码学和数据安全技术中，它是实现有效、安全可靠数字签字和认证的重要工具，是安全认证协议中的重要模块。别名别名：压缩压缩(Compression)函数、紧缩紧缩(Contraction)函数、数据数据认证码认证码(Data Authentication Code)、消息摘要消息摘要(Message Digest)、数字指纹、数据完整性校验数据完整性校验(Data Integity Check)、密码检

24、验密码检验和和(Cryptographic Check Sum)、消息认证码消息认证码MAC(Message Authentication Code)、窜改检测码窜改检测码MDC(Manipulation Detection Code)等。2022-12-2824杂凑函数杂凑函数 1.单向杂凑函数单向杂凑函数密码学中所用的杂凑函数必须满足安全性的要求，要能防伪造，抗击各种类型的攻击，如生日攻击生日攻击、中途相遇攻击中途相遇攻击等等。为此，必须深入研究杂凑函数的性质，从中找出能满足密码学需要的杂凑函数。首先我们引入一些基本概念。1.单向杂凑函数单向杂凑函数定义定义6-2-1 若杂凑函数h为单

25、向函数，则称其为单向杂凑函数单向杂凑函数。显然，对一个单向杂凑函数h，由M计算H=h(M)是容易的，但要产生一个M使h(M)等于给定的杂凑值H是件难事。定义定义6-2-2弱单向杂凑函数：弱单向杂凑函数：若单向杂凑函数h，对任意给定M的杂凑值H=h(M)下，找一M使h(M)=H在计算上不可行。2022-12-2825杂凑函数杂凑函数 2.杂凑函数的安全性杂凑函数的安全性定义定义6-2-3 强单向杂凑函数：强单向杂凑函数：对单向杂凑函数h，若要找任意一对输入M1,M2，M1 M2，使h(M1)=h(M2)在计算上不可行。无碰撞无碰撞(Collision-free)性：弱单向杂凑，是在给定M下，考

26、察与特定M的无碰撞性；而强单向杂凑函数是考察输入集中任意两个元素的无碰撞性。显然，对于给定的输入数字串的集合，后一种碰撞要容易实现。因为从下面要介绍的生日悖论生日悖论知，在N个元素的集中，给定M找与M相匹配的M的概率要比从N中任取一对元素M，相匹配的概率小得多。2.杂凑函数的安全性：杂凑函数的安全性：杂凑函数的安全性取决于其抗击各种攻击的能力，对手的目标是找到两个不同消息映射为同一杂凑值。一般假定对手知道杂凑算法，采用选择明文攻击法。2022-12-2826杂凑函数杂凑函数 2.杂凑函数的安全性杂凑函数的安全性对杂凑函数的基本攻击方法：穷举攻击法穷举攻击法：给定h=h(H0,M)，其中H0为

27、初值，攻击者在所有可能的M中寻求有利于攻击者的M，使h(H0,M)=h(H0,M)，由于限定了目标h(H0,M)来寻找h(H0,M)，这种攻击法称为目标攻击目标攻击。若对算法的初值H0不限定，使其h(H0,M)等于h(H0,M)，则称这种攻击法为自由起始目标攻击自由起始目标攻击。生日攻击生日攻击：这种攻击法不涉及杂凑算法的结构，可用于攻击任何杂凑算法。强杂凑函数正是基于生日悖论一类的攻击法定义的。穷举和生日攻击都属选择明文攻击。生日攻击给定初值H0，寻找MM，使h(H0,M)=h(H0,M)，也可对初始值H0不加限制，即寻找H0,M使h(H0,M)=h(H0,M)。2022-12-2827杂凑

28、函数杂凑函数 2.杂凑函数的安全性杂凑函数的安全性生日悖论生日悖论：在一个会场参加会议的人中，找一个与某人生日相同的概率超过0.5时，所需参会人员为183人。但要问使参会人员中至少有两个同日生的概率超过0.5的参会人数仅为23人。这是因为，对于与某个已知生日的人同日生的概率为1/365，若房中有t人，则至少找到一人与此人同日生的概率为。易于解出，当t183时可使p0.5。第一个人在特定日生的概率为1/365，而第二人不在该日生的概率为，类似地第三人与前两位不同日生的概率为，以此类推，t个人都不同时生日概率为，因此，至少有两人于同日生的概率为解之，当t23时，p0.5。对于n比特杂凑值

29、的生日攻击，由上式可计算出，当进行2n/2次的选择明文攻击下成功的概率将超过0.63。365113652136511.3652136511t36511.36521365111tp2022-12-2828杂凑函数杂凑函数 2.杂凑函数的安全性杂凑函数的安全性例例6-2-1 令h是一个杂凑值为80 bit的单向杂凑函数。给定消息M和H(M)下，假定280 个杂凑值等概，则对M有Prh(M)=2-80。今进行k次试验，找到一个M能使h(M)=h(M)的概率为1-(1-2-80)k。因此，当进行k=274试验时，找到满足要求的M的概率近于1。若在不限定杂凑值的情况下，在消息集中找出一对消息M和M使h

30、(M)=h(M)，根据生日悖论所需的试验次数，至少为1.1724022n是无作用的。由此可以得出一个重要结论重要结论，即对于即对于n bit杂凑值下，杂凑值下，选择密钥比特数大于选择密钥比特数大于2 n bit是无意义的是无意义的。这对于设计杂凑算法有重要意义。这是将杂凑函数看作是一种认证编码给我们的启示。对于线性分组检测码来说，其编码规则是固定的。因而#K=1。虽然其不可检错误的概率上界为2-n，但Pd的下界为1。可见它不能抗击窜扰者的攻击。2022-12-2832杂凑函数杂凑函数 3.杂凑函数、认证码与检错码的关系杂凑函数、认证码与检错码的关系杂凑函数压缩输入数字串与认证编码之间的差别在

31、于，后者是对固定长L bits进行编码成Ln bits码字，而前者对输入字串长度未加限制。一般Ln bit，且当L不是n的整数倍时，采用填充办法凑成L/n倍(表示取不小于括号内数的最小整数)。虽然式(6-3-3)给出的对任意L取值模仿攻击成功概率下限都是2-n。但对杂凑函数来说，输入空间的选择远大于认证码的情况。为了减小碰撞，通常都将输入消息数字串长度作为参数纳入最后一个分段中，这样攻击者在试图找到伪消息M与发送消息M的杂凑值一样时，必须使M的长度和M的长度一致才合法，从而大大增加了攻击的难度。这种技术由Merkle和Damgrd等提出，称作MD强化技术强化技术。Damgrd等证明经过MD强化

32、后，杂凑算法抗自由起始攻击的强度等价于迭代函数的强度。2022-12-2833杂凑函数杂凑函数 4.分组迭代单向杂凑算法的层次结构分组迭代单向杂凑算法的层次结构 4.分组迭代单向杂凑算法的层次结构分组迭代单向杂凑算法的层次结构要想将不限定长度的输入数据压缩成定长输出的杂凑值，不可能设计一种逻辑电路使其一次到位。实际中，总是先将输入数字串划分成固定长的段，如m比特段，而后将此m bit映射成n bit，称完成此映射的函数为迭代函数迭代函数。采用类似于分组密文反馈的模式进行对一段m bit输入做类似映射，以此类推，直到全部输入数字串完全做完，以最后的输出值作为整个输入的杂凑值。类似于分组密码，当

33、输入数字串不是m的整数倍时，可采用填充等方法处理。2022-12-2834杂凑函数杂凑函数 4.分组迭代单向杂凑算法的层次结构分组迭代单向杂凑算法的层次结构 m bit到n bit的分组映射或迭代函数的三种选择：mn。有数据压缩，例如，MD4，MD5，SHA等算法。是不可逆不可逆映射。m=n。无数据压缩，亦无数据扩展，通常分组密码采用这类。此时输入到输出是一种随机映射，在已知密钥下是可逆可逆的的。利用分组密码构造的杂凑算法多属此类。在不知道密钥下，分组密码实质上是一个单向函数(或更确切地说是陷门单向函数)。mn。有数据扩展的映射。认证码属于此类。当然迭代函数设计中，也可采用上述组合来实现，如采

34、用将m bit先进行扩展，而后再逐步经过几次压缩实现理想的密码特性，如Universal2函数的构造法。2022-12-2835杂凑函数杂凑函数 5.迭代杂凑函数的构造方法迭代杂凑函数的构造方法一个m bit到n bit的迭代函数以E表示，一般E又都是通过基本轮函数轮函数的多轮迭代实现的，如分组密码。因此，像分组密码一样轮函数的设计是杂凑算法设计的核心。在迭代计算杂凑值时，为了随机化输入消息，多采用一个随机化初始向量初始向量IV(initial Vector)。它可以是已知的、或随密钥改变、或作为前缀(prefix)加在消息数字之前，以H0表示。5.迭代杂凑函数的构造方法迭代杂凑函数的构造方

35、法安全迭代函数E 消息M划分成组M1,M2,Mi,Mt。选定密钥为K，H0为初始向量IV，2022-12-2836杂凑函数杂凑函数 5.迭代杂凑函数的构造方法迭代杂凑函数的构造方法 Rabin法法：H0=IV；Hi=E(Mi,Hi-1)i=1,t；H(M)=Ht。密码分组链接密码分组链接(CBC)法：法：H0=IV；Hi=E(K,Mi Hi-1)i=1,2,t；H(M)=Ht。ANSI X9.91986、ANSI X9.19、ISO 8731-1、ISO 9797以及澳大利亚标准都采用了这类CBC-MAC方案。Ohta等对此法进行了差分分析。密码反馈密码反馈(CFB)法：法：Hi=E(K,H

36、i-1Mi)，i=1,2,t；H(M)=Ht 4.组合明组合明/密文链接法密文链接法：Mt+1=IV；Hi=E(K,MiMi-1Hi-1)i=1,2,t；H(M)=Ht+1。5修正修正Daveis-Meyer法法：H0=IV；Hi=E(Hi-1,Mi,Hi-1)(Hi和Mi共同作为密钥)2022-12-2837杂凑函数杂凑函数 5.迭代杂凑函数的构造方法迭代杂凑函数的构造方法若数据分组长和密钥长度相等则可用B.Preneel总结的下述12种基本方式构造的分组迭代杂凑函数。令E是迭代函数，它可以是一种分组加密算法，E(K,X)，K是密钥，X是输入数据组或某种压缩算法。令消息分组为M1,M i,

37、H0=I为初始值。(1)Hi=E(Mi,Hi-1)Hi-1 (2)Hi=E(Hi-1,Mi)MiHi-1 (3)Hi=E(Hi-1,MiHi-1)Mi (4)Hi=E(Hi-1,MiHi-1)MiHi-1 (5)Hi=E(Hi-1,Mi)Mi (6)Hi=E(Mi,MiHi-1)MiHi-1 2022-12-2838杂凑函数杂凑函数 5.迭代杂凑函数的构造方法迭代杂凑函数的构造方法 (7)Hi=E(Mi,Hi-1)MiHi-1(N-hash算法，采用128 bit FEAL用此式实现，但安全性可疑 (8)Hi=E(Mi,MiHi-1)Hi-1 (9)Hi=E(MiHi-1,Mi)Mi (10)

38、Hi=E(MiHi-1,Hi-1,)Hi-1 Brown等1990 (11)Hi=E(MiHi-1,Mi)Hi-1 (12)Hi=E(MiHi-1,Hi-1)Mi 如果原来的加密算法是安全的，则上述12种方案给出的杂凑函数，对于目标攻击的计算复杂度为O(2n)，对于中途相遇攻击的计算复杂度为O(2n/2)，因而当大于128 bit时也是安全的。2022-12-2839杂凑函数杂凑函数 6.由由n长长bit杂凑算法扩展为杂凑算法扩展为2n bit杂凑的算法杂凑的算法 6.由由n长长bit杂凑算法扩展为杂凑算法扩展为2n bit杂凑的算法杂凑的算法现有大多数分组密码算法，输入、输出数据多为64

39、bit。作为杂凑算法，都经受不了生日攻击。为此要求杂凑值至少为128 bit才能保证安全性。如何从64 bit杂凑算法，扩展为128 bit或更大的杂凑算法，已有不少方案提出。Knudsen1984曾对其中一些重要方案，如MDC-2、平行DM、PBGV/LOKI扩散等进行了分析，表明以分组密码为基础构造快速而安全的杂凑函数是很困难的。讲义中列举了8种方案。2022-12-2840杂凑函数杂凑函数 7.基本迭代函数的选择基本迭代函数的选择 7.基本迭代函数的选择：基本迭代函数的选择：迭代函数是杂凑函数的核心，有了安全而有效的迭代函数，就可用前述的迭代结构构造安全杂凑函数。讲义中列出10种构造的迭

40、代函数数方法(1)将分组密码算法作为迭代函数将分组密码算法作为迭代函数(2)用用RSA来构造迭代函数来构造迭代函数(3)背包法背包法(4)基于胞元自动机基于胞元自动机(Cellular automata)的算法的算法(5)专门设计的具有数据压缩的单向迭代函数专门设计的具有数据压缩的单向迭代函数(6)矩阵单向迭代函数矩阵单向迭代函数 2022-12-2841杂凑函数杂凑函数 7.基本迭代函数的选择基本迭代函数的选择(7)以以FFT构造单向迭代函数构造单向迭代函数(8)以有限域中元素的指数运算构造迭代函数以有限域中元素的指数运算构造迭代函数(9)IBC-HASH算法算法(10)用流密码构造杂凑函数

41、用流密码构造杂凑函数 2022-12-2842杂凑函数杂凑函数 8.应用杂凑函数的基本方式应用杂凑函数的基本方式杂凑算法可与加密及数字签字结合使用，实现系统的有效、安全、保密与认证。其基本方式如图6-3-1中所示。(a)发端A 收端B M EkM|h(M)M h(M)MUX E D h h k k 比较 h(M)判决 h(M)输出图中的(a)部分，发端A将消息M与其杂凑值h(M)链接，以单钥体制加密，后送至收端B。收端用与发端共享密钥解密后得M和h(M)，而后将M送入杂凑变换器计算出h(M)，并通过比较完成对消息M的认证，从而提供了保密和认证。2022-12-2843杂凑函数杂凑函数 8.

42、应用杂凑函数的基本方式应用杂凑函数的基本方式图中(b)部分，消息M不保密，只对消息的杂凑值进行加解密变换，它只提供认证。M M|Ekh(M)M h(M)(b)k MUX DMX h 判决 h E k 比较输出 h(M)Ekh(M)Ekh(M)D h(M)图中(c)部分，发端A采用双钥体制，用A的秘密钥ksa对杂凑值进行签字得Eksah(M)，而后与M链接发出。收端则用A的公钥对Eksah(M)解密得到h(M)。再与收端自己由接收消息M计算得到的h(M)进行比较实现认证。本方案提供了认证和数字签字。称作签字一杂凑方案签字一杂凑方案(Signature-hashing Scheme)。这一方案

43、用对消息M的杂凑值签字来代替对任意长消息M本身的签字。大大提高了签字的速度和有效性。2022-12-2844杂凑函数杂凑函数 8.应用杂凑函数的基本方式应用杂凑函数的基本方式图中(d)部分是在(c)的基础上加了单钥加密保护，可提供认证、数字签字和保密。M M|Eksak(M)M h(M)(c)ksa MUX DMX h 判决输出 h E kpa 比较 h(M)Eksah(M)Eksah(M)D h(M)M EkM|Eksah(M)M h(M)(d)ks MUX E D DMX h 判决 h E k k kpa 比较输出 h(M)Eksah(M)Eksah(M)D h(M)2022-12-2

45、代杂凑函数的基本方式应用迭代杂凑函数的基本方式2022-12-2846单向迭代杂凑函数的设计理论单向迭代杂凑函数的设计理论安全的单向迭代函数是构造安全消息杂凑值的核心和基础安全的单向迭代函数是构造安全消息杂凑值的核心和基础。有了好的单向迭代函数，就可以利用6-3节中给出的迭代方式形成杂凑值了。为了抗击生日和中途相遇攻击，杂凑值至少应为128 bit。从实际应用出发，要求杂凑算法快速、易于实现。满足安全性要求，从理论上看最重要的有两点：一是函数的单向性单向性，二是函数映射的随机性随机性。1.单向性。单向性。单向性保证了求逆的困难性，这不仅对密码体制有决定意义，而且对杂凑函数设计也是一个基本条件

46、。不具有单向性的函数是不能作认证用的。一个函数的单向性，如果求逆的困难性超过O(264)，则可认为此函数为计算复杂度意义下的单向函数算复杂度意义下的单向函数。2022-12-2847单向迭代杂凑函数的设计理论单向迭代杂凑函数的设计理论杂凑函数如果生日攻击下的难度为O(264)，则可认为是无无碰撞的碰撞的。函数的单向性和无碰撞性的关系如何？Rompel1990证明了一个重要结果，即无碰撞函数存在的充要条件是单向无碰撞函数存在的充要条件是单向函数的存在函数的存在。但这是否就等价于函数的单向性函数的碰撞性，还不清楚。2.伪随机性。伪随机性。迭代函数是一种映射，如果能通过某种可判定的检验逻辑验证随机

47、性，则称其为伪随机映射伪随机映射。已经证明若要迭代函数能抗击生日攻击，则它必须是伪随机映射函数。如果伪随机性迭代函数的逆也是伪随机的，就称其为超伪超伪随机函数随机函数。2022-12-2848单向迭代杂凑函数的设计理论单向迭代杂凑函数的设计理论已经证明要迭代函数能抗击中途相遇攻击，它必须是超伪随机的。这个结果告诉我们超伪随机性函数作为迭代函数才能抗击中途相遇攻击。已经证明了一些特定结构的迭代函数的伪随机性和超伪随机性。从而可用来构造安全迭代函数。3.抗差分攻击能力。抗差分攻击能力。可以用差分分析来攻击迭代函数。因此，要求在构造杂凑算法的迭代函数时，必须使其能经受此类攻击。4.非线性性。非线性

48、性。类似于分组密码，还有许多性质影响安全性。如雪崩特性、高阶相关免疫性等等。2022-12-2849单向迭代杂凑函数的设计理论单向迭代杂凑函数的设计理论对杂凑函数来说。主要要求是能够提供认证和抗击生日及中途相遇碰撞能力。因此，函数的单向性和伪随机及超伪随机性是最根本的要求。如何构造具有伪随机性和超伪随机性的函数，它们的结构特点等是杂凑函数理论的核心。虽然单向杂凑函数和分组密码设计上有很多相似的要求，但一个好的单向杂凑函数未必就是一个安全的分组加密算法，反之亦然，因为两者要求不一样。例如，线性攻击对单向杂凑函数没有太大意义，有些单向杂凑函数如SHA可有线性特性，但并不影响其安全性，但用于消息加

49、密则不能保证安全性。如前所述，对杂凑迭代函数而言，能抵抗生日和中途相遇碰撞攻击是本质的要求，但一个安全的分组密码算法未必能承受这类攻击。2022-12-2850MD-5MD-5杂凑算法杂凑算法 Ron Rivest于1990年提出MD-4杂凑算法,特别适于软、硬件快速实现。输入消息可任意长，压缩后输出为128bits。MD-5是MD-4的改进形式。下面介绍MD-5算法。1.算法算法步骤步骤（参看图6-5-1）(1)对明文输入按512bit分组，最后要填充使其成为512 bit的整数倍，且最后一组的后64 bit用来表示消息长在mod 264下的值K，故填充位数为1512 bit，填充数字图样为

50、(1000)，得Y0,Y1,，YL-1。其中，Yl为512 bit，即16个长为32 bit的字，按字计消息长为N=L16。(2)每轮输出为128 bit，可用下述4个32 bits字表示：A，B，C，D。其初始存数以十六进制表示为：A=01234567，B=89ABCDEF，C=FEDCBA98，D=76543210。2022-12-2851MD-5MD-5杂凑算法杂凑算法 (3)HMD5的运算，对512 bit(16-字)组进行运算，Yq表示输入的第q组512 bit数据，在各轮中参加运算。T1,64为64个元素表，分四组参与不同轮的计算。Ti为232abs(Sine(i)的整数部分，i是

展开阅读全文