《信息安全引论》课件Chapter4

1、 身份的认证与完整性认证是现代密码学的关键问题。认证性解决方案与单向散列函数、数字签名密切相关。前面已经学习过数字签名，在本章我们先学习单向散列函数并集中力量研究认证问题。第4章 单向散列函数本章内容第1节 单向散列函数综述第2节 MD4算法第3节 SHA-1算法第4节 单向散列函数特点第5节 单向散列函数应用小结 单向散列函数是密码学的一个重要概念，在密码学中有重要的应用。本章讲述了对于单向散列函数的要求，两个重要的单向散列函数算法MD4和SHA-1。介绍了单向散列函数的特点以及单向散列函数的主要应用。作业题 1. 请你认真思考，还有什么密码学的问题，可以用单向散列函数解决？或者为单向散列函

2、数找两个新的应用？ 2. 为什么单向散列函数要设计的那么复杂?有简单的算法吗? 如有,请提出改进意见。The End1. 单向散列函数综述 字符串的长度：一个字符串的长度是指字符串中所包含的字符的个数。字符串1001010101的长度是9，123546的长度是6单向散列函数应当满足以下要求单向散列函数的形式定义单向散列函数 设计一个以任意长度的消息为自变量的函数不是件容易的事；再要求单向就更难了。实际上设计单向散列函数时，往往采用与对称加密算法DES相同的方法，对任意长度的消息，先进行分组，然后对每个分组进行若干轮运算，而每一轮的输入是一个消息分组与前一轮计算的输出，最后一个分组的最后一轮输出

3、作为最后的单向散列函数值。单向散列函数单向散列函数 单向散列函数的算法有很多，例如Snefru算法(函数值为128或256比特)，N-Hash算法(日本电报电话公司设计的算法，函数值为128比特)，MD4算法，MD5算法，SHA安全散列算法，HAVAL算法，GOST散列函数(俄罗斯的散列函数标准，产生256比特的函数值)。应用最多的是MD5和SHA。限门单向函数 限门单向函数是有一个秘密限门的特殊的单向函数。它在一个方向上计算很容易而反方向却很难计算，但是如果你知道那个秘密限门，反方向计算也就变得很容易。即很容易计算F(x), 但是给定F(x)要求x却很难。然而有一个秘密消息y,如果知道F(x

4、)和y，就很容易计算x.BACK2. 单向散列函数MD4 MD4进行计算的消息长度L必须是512比特的整数倍，如果消息长度不是512比特的整数倍，需要填充到长度512的整数倍，至少为512比特。如果L是512的整数倍，需要额外填充512比特。填充方法如图所示。MD4算法概述MD4概述(1) MD4产生的消息摘要是128比特的数据。每次处理的是512比特的分组。将这个512比特的分组分成16个32比特的字，分别记作m0, m1, m2, ., m15。首先给消息摘要一个固定的值。用这16个32比特的字依次去修改消息摘要的值。然后每次运算都取出当前的消息摘要与消息的下一个分组进行运算，以得到MD4

5、概述(2)新的消息摘要。每次计算都对消息分组进行三轮运算，每轮运算就重复运用这16个32比特的字。每次计算都将计算的结果与上一次计算的结果中对应的字相加，然后与一个32比特的消息相加，并进行一定数量的循环移位。最后的结果就是消息摘要。MD4算法概述(3)MD4算法概述(5)MD4中所用的操作MD4算法概述(4)首先我们看消息摘要的初值：消息摘要用4个字来表示，每个字为8个16进制数或者说一个32比特的数。MD4的第一轮函数 MD4的每一轮运算就是要根据消息对d3, d2, d1, d0 进行修改，得到新的d3,d2, d1, d0 ，现在我们看是如何用消息对d3, d2, d1, d0 进行修

6、改的。对d3, d2, d1, d0的修改要用到一个函数F(x,y,z)。对i的解释 上述公式中的i 就是指16个32比特的字的编号，取值范围为0,1,15。通过计算可知，当处理第1个字(即i=1)时，修改的是d0, 当处理第2个字(即i=2)时，修改的是d3, 依此类推，处理每个字时，修改的是那一个d都可以计算出来。每一个i修改一个d，因为i的值有16个，只有4个d, 所以处理完一个512比特的分组，每个d都被重复修改了4次。MD4的第一轮函数 对MD4函数的解释MD4的每一轮运算就是要根据消息对d3, d2, d1, d0进行修改，得到新的d3, d2, d1, d0 ，现在我们看是如何用

7、消息对d3, d2, d1, d0进行修改的。对d3, d2, d1, d0的修改要用到一个函数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)。我们可以称之为投

8、票函数，因为输出的第i比特，取决于3个输入的第i比特中的多数情况，多数为1，就输出1，多数为0就输出0第二轮中的计算MD4的第三轮函数MD4的第三轮运算消息摘要值将三轮运算完成之后，将最后所得的连接起来，则消息摘要值ExampleMD4(The quick brown fox jumps over the lazy dog) = 1bee69a46ba8 11185c194762abaeae90MD4(The quick brown fox jumps over the lazy cog) = b86e130ce702 8da59e672d56ad0113df BACK3. 安全散列算法SHA

9、-1 SHA-1是NIST推荐的与DSA一起使用的散列算法，算法能处理的最长消息为264比特，输出160比特的单向散列函数值。这个算法与MD4类似，但是速度要慢一点，也更安全一些，对于每个消息分组，SHA-1进行5轮运算。在进行散列运算前，SHA-1也需要将消息填充成512比特的整数倍，填充的方法与MD4相同。这里不再赘述。SHA-1算法概述SHA-1的运算概述SHA-1的一次运算SHA-1算法细节Wt 的生成SHA-的常数SHA-1的非线性函数4. 对单向散列函数的攻击 对单向散列函数的攻击主要是穷举攻击，但是根据攻击者的目的不同可以有两种攻击：第1种是给定某个消息的散列值h=Hash (M

10、)，攻击者要逐个产生产生一些消息，从中找到一个消息M，使得Hash (M)=Hash (M)。第二种攻击方法称为冲突攻击，攻击者寻找两个随机的消息M，M使得Hash (M)=Hash (M)。对单向散列函数的攻击 冲突攻击与生日悖论有重要的关系，有时也称为生日攻击。随便拉出来多少个人，才能找到至少一个人与你的生日相同？另一个问题是随便找多少个人在一起，才能使这些人中至少有两个人的生日相同的概率大于0.5？ 答案是253和23(这个数字非常出人意料的小)。 对单向散列函数的攻击 单向散列函数的长度：64比特的单向散列函数对付生日攻击来说显然太小。目前大多数的单向散列函数产生128比特的散列值，这

11、就迫使试图进行生日攻击的人必须进行对264个随机文件进行散列运算才能够找到散列值相同的两个文件，但这也不足以维持散裂函数的安全性，因此SHA-1生成的是160比特的散列值。生日攻击的计算公式生日攻击的计算公式BACK5. 单向散列函数的特点 单向散列函数又称为压缩函数、收缩函数、消息摘要、消息指纹、密码校验和、鉴别性、操作检验码等。在数字签名、认证等方面有重要的应用。这是由单向散列函数的特点决定的。主要的特点有两个： （1）两个消息只要稍有不同，计算出的单向散列值就是不同的。 （2）找到具有某个散列值的消息，或者找到具有相同散列值的两个消息在计算上是不可行的。BACK6. 单向散列函数的应用(

12、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收到消息及单向散列函数之值后，计算消息的单向散列函数值，如果计算的结果和收到的