《信息安全引论》课件Chapter4

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,身份的认证与完整性认证是现代密码学的关键问题。认证性解决方案与单向散列函数、数字签名密切相关。前面已经学习过数字签名，在本章我们先学习单向散列函数并集中力量研究认证问题。,第,4,章 单向散列函数,本章内容,第,1,节 单向散列函数综述,第,2,节,MD4,算法,第,3,节,SHA-1,算法,第,4,节 单向散列函数特点,第,5,节 单向散列函数应用,小结,单向散列函数是密码学的一个重要概念，在密码学中有重要的应用。本章讲述了对于单向散列函数的要求，两个重要的单向散列函数算法,MD4,和,SHA-1,。介绍了单向散列函数的特点以及单向散列函数的主要应用。,作业题,1.,请你认真思考，还有什么密码学的问题，可以用单向散列函数解决？或者为单向散列函数找两个新的应用？,2.,为什么单向散列函数要设计的那么复杂,?,有简单的算法吗,?,如有,请提出改进意见。,The End,1.,单向散列函数综述,字符串的长度：一个字符串的长度是指字符串中所包含的字符的个数。字符串,1001010101,的长度是,9,，,123546,的长度是,6,单向散列函数应当满足以下要求,单向散列函数的形式定义,单向散列函数,设计一个以任意长度的消息为自变量的函数不是件容易的事；再要求单向就更难了。实际上设计单向散列函数时，往往采用与对称加密算法,DES,相同的方法，对任意长度的消息，先进行分组，然后对每个分组进行若干轮运算，而每一轮的输入是一个消息分组与前一轮计算的输出，最后一个分组的最后一轮输出作为最后的单向散列函数值。,单向散列函数,单向散列函数,单向散列函数的算法有很多，例如,Snefru,算法,(,函数值为,128,或,256,比特,),，,N-Hash,算法,(,日本电报电话公司设计的算法，函数值为,128,比特,),，,MD4,算法，,MD5,算法，,SHA,安全散列算法，,HAVAL,算法，,GOST,散列函数,(,俄罗斯的散列函数标准，产生,256,比特的函数值,),。应用最多的是,MD5,和,SHA,。,限门单向函数,限门单向函数是有一个秘密限门的特殊的单向函数。它在一个方向上计算很容易而反方向却很难计算，但是如果你知道那个秘密限门，反方向计算也就变得很容易。即很容易计算,F(x),但是给定,F(x),要求,x,却很难。然而有一个秘密消息,y,如果知道,F(x),和,y,，就很容易计算,x,.,BACK,2.,单向散列函数,MD4,MD4,进行计算的消息长度,L,必须是,512,比特的整数倍，如果消息长度不是,512,比特的整数倍，需要填充到长度,512,的整数倍，至少为,512,比特。如果,L,是,512,的整数倍，需要额外填充,512,比特。填充方法如图所示。,MD4,算法概述,MD4,概述,(1),MD4,产生的消息摘要是,128,比特的数据。,每次处理的是,512,比特的分组。将这个,512,比特的分组分成,16,个,32,比特的字，,分别记作,m,0, m,1, m,2, ., m,15,。,首先给消息摘要一个固定的值。用这,16,个,32,比特的字依次去修改消息摘要的值。然后每次运算都取出当前的消息摘要与消息的下一个分组进行运算，以得到,MD4,概述,(2),新的消息摘要。每次计算都对消息分组进行三轮运算，每轮运算就重复运用这,16,个,32,比特的字。每次计算都将计算的结果与上一次计算的结果中对应的字相加，然后与一个,32,比特的消息相加，并进行一定数量的循环移位。最后的结果就是消息摘要。,MD4,算法概述,(3),MD4,算法概述,(5),MD4,中所用的操作,MD4,算法概述,(4),首先我们看消息摘要的初值：消息摘要用,4,个字来表示，每个字为,8,个,16,进制数或者说一个,32,比特的数,。,MD4,的第一轮函数,MD4,的每一轮运算就是要根据消息对,d,3, d,2, d,1, d,0,进行修改，得到新的,d,3,d,2, d,1, d,0,，现在我们看是如何用消息对,d,3, d,2, d,1, d,0,进行修改的。对,d,3, d,2, d,1, d,0,的修改要用到一个函数,F(x,y,z),。,对,i,的解释,上述公式中的,i,就是指,16,个,32,比特的字的编号，取值范围为,0,1,15,。通过计算可知，当处理第,1,个字,(,即,i=1,),时，修改的是,d,0,当处理第,2,个字,(,即,i=2,),时，修改的是,d,3,依此类推，处理每个字时，修改的是那一个,d,都可以计算出来。每一个,i,修改一个,d,，,因为,i,的值有,16,个,，,只有,4,个,d,所以处理完一个,512,比特的分组，每个,d,都被重复修改了,4,次。,MD4,的第一轮函数,对,MD4,函数的解释,MD4,的每一轮运算就是要根据消息对,d,3, d,2, d,1, d,0,进行修改，得到新的,d,3, d,2, d,1, d,0,，现在我们看是如何用消息对,d,3, d,2, d,1, d,0,进行修改的。对,d,3, d,2, d,1, d,0,的修改要用到一个函数,F(x,y,z,),。,函数,F (x, y, z),输入,3,个,32,比特的字，输出一个,32,比特字。可以称为选择函数或者抽签函数。因为如果第一个输入,x,的第,i,比特为,1,，函数的第,i,比特就选择,y,的第,i,比特，如果第一个输入,x,的第,i,比特为,0,，函数的第,i,比特就选择,z,的第,i,比特。,If,x,then,y, else,z .,MD4,的第二轮运算,G ( x, y, z),在课本上称为择多函数，因为只有在输入的,3,个字的第,i,比特有,3,个，如果这,3,个比特中有,2,个以上为,1(0),输出的第,i,比特就为,1(0),。我们可以称之为投票函数，因为输出的第,i,比特，取决于,3,个输入的第,i,比特中的多数情况，多数为,1,，就输出,1,，多数为,0,就输出,0,第二轮中的计算,MD4,的第三轮函数,MD4,的第三轮运算,消息摘要值,将三轮运算完成之后，将最后所得的,连接起来，则,消息摘要值,Example,MD4(,The quick brown fox jumps over the lazy dog,) =,1bee69a46ba8 11185c194762abaeae90,MD4(,The quick brown fox jumps over the lazy cog,) =,b86e130ce702 8da59e672d56ad0113df,BACK,3.,安全散列算法,SHA-1,SHA-1,是,NIST,推荐的与,DSA,一起使用的散列算法，算法能处理的最长消息为,2,64,比特，输出,160,比特的单向散列函数值。这个算法与,MD4,类似，但是速度要慢一点，也更安全一些，对于每个消息分组，,SHA-1,进行,5,轮运算。在进行散列运算前，,SHA-1,也需要将消息填充成,512,比特的整数倍，填充的方法与,MD4,相同。这里不再赘述。,SHA-1,算法概述,SHA-1,的运算概述,SHA-1,的一次运算,SHA-1,算法细节,W,t,的生成,SHA-,的常数,SHA-1,的非线性函数,4.,对单向散列函数的攻击,对单向散列函数的攻击主要是穷举攻击，但是根据攻击者的目的不同可以有两种攻击：第,1,种是给定某个消息的散列值,h=Hash (M),，攻击者要逐个产生产生一些消息，从中找到一个消息,M,，使得,Hash (M)=Hash (M),。第二种攻击方法称为冲突攻击，攻击者寻找两个随机的消息,M,，,M,使得,Hash (M)=Hash (M),。,对单向散列函数的攻击,冲突攻击与生日悖论有重要的关系，有时也称为生日攻击。随便拉出来多少个人，才能找到至少一个人与你的生日相同？另一个问题是随便找多少个人在一起，才能使这些人中至少有两个人的生日相同的概率大于,0.5,？,答案是,253,和,23(,这个数字非常出人意料的小,),。,对单向散列函数的攻击,单向散列函数的长度：,64,比特的单向散列函数对付生日攻击来说显然太小。目前大多数的单向散列函数产生,128,比特的散列值，这就迫使试图进行生日攻击的人必须进行对,2,64,个随机文件进行散列运算才能够找到散列值相同的两个文件，但这也不足以维持散裂函数的安全性，因此,SHA-1,生成的是,160,比特的散列值。,生日攻击的计算公式,生日攻击的计算公式,BACK,5.,单向散列函数的特点,单向散列函数又称为压缩函数、收缩函数、消息摘要、消息指纹、密码校验和、鉴别性、操作检验码等。在数字签名、认证等方面有重要的应用。这是由单向散列函数的特点决定的。主要的特点有两个：,（,1,）两个消息只要稍有不同，计算出的单向散列值就是不同的。,（,2,）找到具有某个散列值的消息，或者找到具有相同散列值的两个消息在计算上是不可行的。,BACK,6.,单向散列函数的应用,(FIPS180-1),Applications: The SHA-1 may be used with the DSA in electronic mail, electronic funds transfer, software distribution, data storage, and other applications which require data integrity assurance and data origin authentication. The SHA-1 may also be used whenever it is necessary to generate a condensed version of a message.,完整性认证,(1),认证问题是网络应用中的重要问题，认证问题有两种：,(1),信息完整性认证：,Bob,收到,Alice,发送的信息，这个信息是不是,Alice,发送的原始信息，即信息在发送过程是否受到过篡改。,(2),实体身份认证：某个人声称她就是,Alice,，如何保证她确实就是,Alice,，而不是其他人冒充的。,完整性认证,(2),Alice,向,Bob,发送一个消息，为了保证消息的完整性，,Alice,在发送消息的同时计算消息的单向散列函数值。,Bob,收到消息及单向散列函数之值后，计算消息的单向散列函数值，如果计算的结果和收到的值相同，那么消息就是完整的，没有受到篡改。,(,可能的攻击,),单向散列函数应用,(3),(1) Alice,生成文件的单向散列函数值。,(2) Alice,用她的私人密钥对散列函数值加密，凭此表示对文件签名。,(3) Alice,将文件与对散列值的签名送给,Bob,。,(4) Bob,用相同的方法计算文件的散列函数值，并用,Alice,的公开密钥解密签名。如果解密出的结果与计算的散列值相同，则证明,Alice,确实对此文件进行过签名,BACK,