哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　1、第第8章章 Hash 函数Hash函数定义v数据安全数据安全 机密性机密性 完整性完整性 认证性认证性v密码技术主要保证数据的机密性密码技术主要保证数据的机密性vHash函数能保证数据的完整性和认证性函数能保证数据的完整性和认证性Hash函数定义vHash函数常用来构造数据的短函数常用来构造数据的短“指纹指纹”：消息的：消息的发送者使用所有的消息产生一个附件也就是短发送者使用所有的消息产生一个附件也就是短“指纹指纹”，并将该短，并将该短“指纹指纹”与消息一起传输给与消息一起传输给接收者。接收者。v即使数据存储在不安全的地方，接收者重新计算即使数据存储在不安全的地方，接收者重新计算数据的指纹，并

　　2、验证指纹是否改变，就能够检测数据的指纹，并验证指纹是否改变，就能够检测数据的完整性。这是因为一旦数据在中途被破坏，数据的完整性。这是因为一旦数据在中途被破坏，或改变，短指纹就不再正确。或改变，短指纹就不再正确。 Hash函数定义vHash函数定义：函数定义：Hash函数是一个将任意长度的函数是一个将任意长度的消息（消息（message）映射成固定长度消息的函数。）映射成固定长度消息的函数。vHash函数是一个函数，它以一个变长的报文作为函数是一个函数，它以一个变长的报文作为输入，并产生一个定长的散列码，有时也称为报输入，并产生一个定长的散列码，有时也称为报文摘要，作为函数的输出。文摘要，作为函

　　3、数的输出。vHash函数（函数（hash function），或称为哈希函数、），或称为哈希函数、散列函数。对于任何消息散列函数。对于任何消息x ，将，将h(x)称为称为x的的Hash值、散列值、消息摘要（值、散列值、消息摘要（message digest）。）。Hash函数作用vHash函数最主要的作用于是用于鉴别，鉴函数最主要的作用于是用于鉴别，鉴别在网络安全中起到举足轻重的地位。鉴别在网络安全中起到举足轻重的地位。鉴别的目的有以下两个：第一，验证信息的别的目的有以下两个：第一，验证信息的发送者是真正的，而不是冒充的，同时发发送者是真正的，而不是冒充的，同时发信息者也不能抵赖，此为信源识别

　　4、；第二，信息者也不能抵赖，此为信源识别；第二，验证信息完整性，在传递或存储过程中未验证信息完整性，在传递或存储过程中未被篡改，重放或延迟等。被篡改，重放或延迟等。 8.1Hash 函数的性质vHash函数的碰撞（collision） 设设x、x是两个不同的消息，如果是两个不同的消息，如果 h(x)=h(x) 则称则称x和和x是是Hash函数函数h的一个（对）碰撞的一个（对）碰撞.8. 1 Hash 函数的性质vHash函数的分类函数的分类 单向单向Hash函数（函数（one way） 给定一个给定一个Hash值值y，如果寻找一个消息，如果寻找一个消息x，使得，使得y=h (x)是计算上不可行的

　　5、，则称是计算上不可行的，则称h是单向是单向Hash函数函数. 弱抗碰撞弱抗碰撞Hash函数（函数（weakly collision free） 任给一个消息任给一个消息x，如果寻找另一个不同的消息，如果寻找另一个不同的消息x，使得，使得h(x) =h(x)是计算上不可行的，则称是计算上不可行的，则称h是弱抗碰撞是弱抗碰撞Hash函函数数. 强抗碰撞强抗碰撞Hash函数函数 （strongly collision free） 如果寻找两个不同的消息如果寻找两个不同的消息x和和x，使得，使得h(x)=h(x)是计算是计算上不可行的，则称上不可行的，则称h是强抗碰撞是强抗碰撞Hash函数函数. 8.

　　6、 1 Hash 函数的性质 hash函数在现代密码学中起着重要的作用，主要用于函数在现代密码学中起着重要的作用，主要用于对数据完整性和消息认证对数据完整性和消息认证 压缩性：任意长度的数据，算出的摘要长度都固定。压缩性：任意长度的数据，算出的摘要长度都固定。 容易计算：从原数据容易算出摘要。容易计算：从原数据容易算出摘要。 抗修改性：对原数据进行任何改动，哪怕只修改抗修改性：对原数据进行任何改动，哪怕只修改1个个字节，所得到的摘要都有很大区别。字节，所得到的摘要都有很大区别。 弱抗碰撞：已知原数据和其摘要，想找到一个具有弱抗碰撞：已知原数据和其摘要，想找到一个具有相同摘要的数据（即伪造数据），

　　7、在计算上是困难相同摘要的数据（即伪造数据），在计算上是困难的。的。 强抗碰撞：想找到两个不同的数据，使它们具有相强抗碰撞：想找到两个不同的数据，使它们具有相同的摘要，在计算上是困难的。同的摘要，在计算上是困难的。 Hash函数的安全性函数的安全性v对对Hash函数的攻击是指寻找一对碰撞消息函数的攻击是指寻找一对碰撞消息的过程的过程v 与传统密码体制的攻击方式相比，对散列与传统密码体制的攻击方式相比，对散列函数的攻击方法主要有两种：函数的攻击方法主要有两种： 穷举攻击：它可以用于任何类型的散列函数的攻击，穷举攻击：它可以用于任何类型的散列函数的攻击，最典型的方式就是所谓的最典型的方式就是所谓的“

　　8、生日攻击生日攻击”。采用生日。采用生日攻击的攻击者将产生许多明文消息，然后计算这些攻击的攻击者将产生许多明文消息，然后计算这些明文消息的指纹（摘要），进行比较。明文消息的指纹（摘要），进行比较。 利用散列函数的代数结构：攻击其函数的弱性质。利用散列函数的代数结构：攻击其函数的弱性质。通常的有中间相遇攻击、修正分组攻击和差分分析通常的有中间相遇攻击、修正分组攻击和差分分析攻击等。攻击等。 v生日悖论（birthday paradox） 生日问题：假设每个人的生日是等概率的，每年生日问题：假设每个人的生日是等概率的，每年有有365天，在天，在k个人中至少有两个人的生日相同的个人中至少有两个人的生日

　　9、相同的概率大于概率大于1/2，问，问k最小应是多少？最小应是多少？ k人生日都不同的概率是：人生日都不同的概率是： .36511.3652136511k有有P(365,23)=0.5073。即在。即在23个人中，至少有两个人中，至少有两个人生日相同的概率大于个人生日相同的概率大于0.5，这个数字比人们，这个数字比人们直观猜测的结果小得多，因而称为生日悖论。直观猜测的结果小得多，因而称为生日悖论。.36511.),365(kkP 2k人生日相同的概率为：人生日相同的概率为：人中至少有人中至少有v生日攻击法生日攻击法 生日悖论原理可以用于构造对生日悖论原理可以用于构造对Has

　　10、h函数函数的攻击的攻击v设设Hash函数值有函数值有n个比特，个比特，m是真消息，是真消息，M是伪造的假消息，分别把消息是伪造的假消息，分别把消息m和和M表示成表示成r和和R个变形的消息。消息与其变形消息具有个变形的消息。消息与其变形消息具有不同的形式，但有相同的含义。将消息表示不同的形式，但有相同的含义。将消息表示成变形消息的方法很多，例如增加空格、使成变形消息的方法很多，例如增加空格、使用缩写、使用意义相同的单词、去掉不必要用缩写、使用意义相同的单词、去掉不必要的单词等。的单词等。Hash函数的安全性Hash函数的安全性v生日攻击法 分别把消息分别把消息m和和M表示成表示成r和和R个变形的

　　11、消息个变形的消息v生日攻击法 计算真消息计算真消息m的变形与假消息的变形与假消息M的变形发生碰撞的的变形发生碰撞的概率概率 由于由于n比特长的散列值共有比特长的散列值共有2n个，所以对于给定个，所以对于给定m的变形的变形mi和和M的变形的变形Mj，mi与与Mj不碰撞的概率是不碰撞的概率是1-1/2n。由于。由于M共有共有R个变形，所以个变形，所以M的全部变形的全部变形都不与都不与mi碰撞的概率是：碰撞的概率是： 1 1/2.RnHash函数的安全性因为消息m共有r个变形，因此m的变形与M的变形都不碰撞的概率是：.2/1rRn1m的变形与M的变形发生碰撞的概率是：.12111)(2nrRrRne

　　12、nPv生日攻击法 当当r=R=2n/2时，时，P(n)=1 e 1 0.63。对于。对于Hash值值长度为长度为64比特的比特的Hash函数，生日攻击的时间复杂函数，生日攻击的时间复杂度约为度约为232，所以是不安全的。，所以是不安全的。为了抵抗生日攻击，建议Hash值长度至少为128 比特.Hash函数的安全性8. 2 基于分组密码的Hash 函数基于分组密码的CBC 工作模式的Hash 函数H首先选取一个初始向量令 然后计算基于分组密码的CFB 工作模式的Hash 函数H令 然后计算首先选取一个初始向量8.3 hash函数函数MD4vMD4是麻省理工学院教授是麻省理工学院教授Ronald

　　13、Rivest于于1990年设计的一种信息摘要算法。它是一种用来测试年设计的一种信息摘要算法。它是一种用来测试信息完整性的密码散列函数的实行。其摘要长度信息完整性的密码散列函数的实行。其摘要长度为为128位。这个算法影响了后来的算法如位。这个算法影响了后来的算法如MD5、SHA 家族和家族和RIPEMD等。等。 vMD5算法是算法是1991年发布的一项数字签名加密算法，年发布的一项数字签名加密算法，它当时解决了它当时解决了MD4算法的安全性缺陷，成为应用算法的安全性缺陷，成为应用非常广泛的一种算法。非常广泛的一种算法。8.3 hash函数函数MD4vMD4算法的输入可以是任意长度的消息算法的输入

　　14、可以是任意长度的消息x，对输入消息按对输入消息按512位的分组为单位进行处理，位的分组为单位进行处理，输出输出128位的散列值位的散列值MD(x)。整个算法分为。整个算法分为五个步骤。五个步骤。 步骤步骤1: 增加填充位增加填充位 步骤步骤2: 附加消息长度值附加消息长度值 步骤步骤3: 初始化初始化MD缓冲区缓冲区 步骤步骤4: 以以512位的分组位的分组(16个字个字)为单位处理消为单位处理消息息 步骤步骤5: 输出输出消息的预处理步骤：消息的预处理步骤：设x 是一个消息, 用二进制表示。首先由x 生成一个数组是长度为32 比特(bit)的(0,1) 序列,M 由x 生成：d = (447

　　15、 -x)mod 512 令l 为 的二进制表示。 l 的长度为64 比特(bit)。如果l 的长度不足64 比特(bit), 则在l 的左端添0 补足M =这里x表示x 的长度, 表示序列的联接, 譬如xy 表示将序列y 排在序列x 的右端。v步骤1: 增加填充位 在消息在消息x右边增加若干比特，使其长度与右边增加若干比特，使其长度与448模模512同余。也就是说，填充后的消息同余。也就是说，填充后的消息长度比长度比512的某个倍数少的某个倍数少64位。位。 即使消息本身已经满足上述长度要求，仍即使消息本身已经满足上述长度要求，仍然需要进行填充。然需要进行填充。 例如，若消息长为例

　　16、如，若消息长为448，则仍需要填充，则仍需要填充512位使其长度为位使其长度为960位。填充位数在位。填充位数在1到到512之间。填充比特的第一位是之间。填充比特的第一位是1，其它均为，其它均为0。步骤步骤2: 附加消息长度值附加消息长度值 用用64位表示原始消息位表示原始消息x的长度，并将其附加的长度，并将其附加在步骤在步骤1所得结果之后。若填充前消息长度大所得结果之后。若填充前消息长度大于等于于等于264，则使用其，则使用其64位。填充方法是把位。填充方法是把64比特的长度分成两个比特的长度分成两个32比特的字，低比特的字，低32比特比特字先填充，高字先填充，高32比特字后填充。比特字后填

　　17、充。v步骤1与步骤2一起称为消息的预处理 经预处理后，原消息长度变为经预处理后，原消息长度变为512的倍数的倍数 设原消息设原消息x经预处理后变为消息经预处理后变为消息 Y=Y0 Y1 YN 1， 其中其中Yi（i =0,1,N 1）是）是32比特比特 在后面的步骤中，将对在后面的步骤中，将对512比特的分组比特的分组Yi进行进行处理处理 v例8.1 假设消息为: x=“abcde”=01100001 01100010 01100011 01100100 01100101=(61 62 63 64 65)16, x=40=(28)16. 步骤步骤1在在x的右边填充的右边填充1个个“1”和和

　　20、00. v步骤3: 初始化MD缓冲区 MD4算法的中间结果和最终结果都保存在算法的中间结果和最终结果都保存在128位的缓冲区里，缓冲区用位的缓冲区里，缓冲区用4个个32位的寄存器表位的寄存器表示。示。 4个缓冲区记为个缓冲区记为A、B、C、D，其初始值为下，其初始值为下列列32位整数（位整数（16进制表示）：进制表示）： A=67 45 23 01, B=EF CD AB 89, C=98 BA DC FE, D=10 32 54 76. 上述初始值以小端格式存储上述初始值以小端格式存储(字的最低有效字字的最低有效字节存储在低地址位置节存储在低地址位置 )为：为： 字字A=01 23 45 6

　　21、7, 字字B=89 AB CD EF, 字字C=FE DC BA 98, 字字D=76 54 32 10.v步骤步骤4: 以以512位的分组位的分组(16个字个字)为单位处理消息为单位处理消息 MD4是迭代是迭代Hash函数函数, 其压缩函数为其压缩函数为: 步骤步骤4是是MD4算法的主循环，它以算法的主循环，它以512比特作比特作为分组，重复应用压缩函数为分组，重复应用压缩函数HMD4，从消息，从消息Y的第一个分组的第一个分组Y0开始，依次对每开始，依次对每16个分组个分组Yi进行压缩，直至最后分组进行压缩，直至最后分组N/16-1，然后输出，然后输出消息消息x的的Hash值。可见，值。可见

　　22、，MD4的循环次数等的循环次数等于消息于消息Y中中512比特分组的数目比特分组的数目L。.1 , 01 , 0 :1285121284MDHv步骤5: 输出v依次对消息的依次对消息的L个个512比特的分组进行比特的分组进行处理，第处理，第L个分组处理后的输出值即是个分组处理后的输出值即是消息消息x的散列值的散列值MD(x)。8. 3 Hash函数MD4MD4 算法如下设A、B、C、D 是四个32 位的寄存器, 其初值(用十六进制表示) 分别为A=67452301、B =efcdab89、C =98badcfe、D=10325476:对i = 0 至N/16 - 1 执行第3 步至第8 步对j

　　24、年作为联邦信息处理标准（FIPS 180）发）发布布v修改版于修改版于1995年发布（年发布（FIPS 180 1），通常），通常称之为称之为SHA 1。该标准称为。该标准称为安全安全Hash函数函数。vRFC 3174也给出了也给出了SHA 1，它基本上是复制，它基本上是复制FIPS 180 1的内容，但增加了的内容，但增加了C代码实现。代码实现。vSHA 1算法的输入是长度小于算法的输入是长度小于264的任意消息的任意消息x，输出输出160位的散列值。位的散列值。8.4安全Hash算法SHAvSHA 1处理消息的过程与处理消息的过程与MD4类似，对输入消类似，对输入消息按息按512位的分组

　　25、为单位进行处理，整个算法分位的分组为单位进行处理，整个算法分为五个步骤为五个步骤v步骤步骤1: 增加填充位增加填充位 在消息右边增加若干比特，使其长度与在消息右边增加若干比特，使其长度与448模模512同同余。即使消息本身已经满足上述长度要求，仍然需要余。即使消息本身已经满足上述长度要求，仍然需要进行填充。填充位数在进行填充。填充位数在1到到512之间。填充比特的第一之间。填充比特的第一位是位是“1”，其它均为，其它均为“0”。8.4安全Hash算法SHAv步骤步骤2: 附加消息长度值附加消息长度值 用用64位表示原始消息位表示原始消息x的长度，并将其的长度，并将其附加在步骤附加在步骤1所得结

　　26、果之后。所得结果之后。v步骤步骤1与步骤与步骤2一起称为消息的预处理一起称为消息的预处理 经预处理后，原消息长度变为经预处理后，原消息长度变为512的倍的倍数。设原消息数。设原消息x经预处理后变为消息经预处理后变为消息M=M0 M1 MN 1，其中，其中Mi（i =0,1,N 1）是）是32比特。在后面的步骤中，将对比特。在后面的步骤中，将对512比特的分比特的分组进行处理。组进行处理。8.4安全Hash算法SHAv 步骤步骤3: 初始化缓冲区初始化缓冲区 SHA 1算法的中间结果和最终结果保存在算法的中间结果和最终结果保存在160位的缓冲区里，位的缓冲区里，缓冲区用缓冲区用5个个32位的寄存

　　27、器表示。位的寄存器表示。5个缓冲区记为个缓冲区记为A、B、C、D、E，其初始值为下列，其初始值为下列32位整数（位整数（16进制表示）：进制表示）： A=67 45 23 01, B=EF CD AB 89, C=98 BA DC FE , D=10 32 54 76, E=C3 D2 E1 F0. 其中，前其中，前4个初始值与个初始值与MD5的初始值相同。的初始值相同。SHA 1以大端格式以大端格式存储缓冲区的值，即字的最高有效字节存于低地址字节位置。存储缓冲区的值，即字的最高有效字节存于低地址字节位置。因此，上述初始值存储为（十六进制）：因此，上述初始值存储为（十六进制）： 字字A=67

　　28、45 23 01, 字字B=EF CD AB 89, 字字C=98 BA DC FE, 字字D=10 32 54 76, 字字E=C3 D2 E1 F0.8.4安全Hash算法SHAv 步骤步骤4: 以以512位的分组（位的分组（16个字）为单位处理消息个字）为单位处理消息 SHA 1是迭代是迭代Hash函数，其压缩函数为：函数，其压缩函数为：. 160512160SHA1 , 01 , 0:H 步骤步骤4是是SHA 1算法的主循环，它以算法的主循环，它以512比特作为分比特作为分组，重复应用压缩函数组，重复应用压缩函数HSHA，从消息的第一个分组开，从消息的第一个分组开始，依次对每个分组进行

　　30、HA 压缩函数压缩函数HSHA的四轮处理过程的算法结构相同，每一轮的四轮处理过程的算法结构相同，每一轮要对缓冲区要对缓冲区ABCDE进行进行20次迭代，每次迭代的运算形次迭代，每次迭代的运算形式为式为 TEMP=(A5)+ft(B,C,D)+E+Xk+Kt E=D D=C C=B30 B=A A=TEMPDCBD)(CD)(BC)(BDCBD)B(C)(BSHASHA 1 1的压缩函数的压缩函数H HSHASHA 基本逻辑函数基本逻辑函数f 每一轮使用一个基本逻辑函数每一轮使用一个基本逻辑函数f，每个基本逻，每个基本逻辑函数的输入是三个辑函数的输入是三个32位的字，输出是一个位的字，输出是一个

　　31、32位的字，它执行位逻辑运算，即输出的第位的字，它执行位逻辑运算，即输出的第n位是其三个输入第位是其三个输入第n位的函数。位的函数。轮数轮数基本逻辑函数基本逻辑函数ff(B, C, D)1234f1(B, C, D)f2(B, C, D)f3(B, C, D)f4(B, C, D)SHA1的压缩函数HSHA 字组Xt t（0t79）代表迭代步数，依次表示第一、二、三、四轮）代表迭代步数，依次表示第一、二、三、四轮处理过程进行的迭代次序处理过程进行的迭代次序 Xt(0t79)是是32比特的字，它的前面比特的字，它的前面16个字个字X0,X1,X15依次依次取自当前输入分组取自当前输入分组Mi，其

　　34、j - 3 Xj - 8 Xj -14 Xj -16) 1 执行Round4点此查看Round3SHA1和MD5的比较v SHA1与MD5的算法类似，所以它们的性质极为相似v 抗穷举攻击的能力 SHA 1抗穷举攻击的能力比抗穷举攻击的能力比MD5强强 用穷举攻击方法产生具有给定散列值的消息用穷举攻击方法产生具有给定散列值的消息 MD5需要的代价为需要的代价为2128数量级数量级 SHA 1需要的代价为需要的代价为2160数量级数量级 用穷举攻击方法产生两个具有相同散列值的消息用穷举攻击方法产生两个具有相同散列值的消息 MD5需要的代价为需要的代价为264数量级数量级 SHA 1需要的代价为需要

　　35、的代价为280数量级数量级 v 抗密码分析的能力 MD5算法抗密码分析的能力较弱 SHA1算法抗密码分析的能力似乎并不弱 SHA1和MD5的比较v速度 SHA1执行的速度比MD5的速度慢得多 v简洁性 SHA1和MD5两种算法都易于描述和实现，不需要使用大的程序和置换表 v数据的存储方式 MD5使用littleendian方式，SHA1使用bigendian方式。这两种方式没有本质的差异 点击此处返回点击此处返回点击此处返回点击此处返回所使用的函数为所使用的常数(用十六进制表示) 为Round1 为对k = 0 至19 执行点击此处返回所使用的函数为所使用的常数(用十六进制表示) 为Round2 为对k = 20 至39 执行点击此处返回所使用的函数为所使用的常数(用十六进制表示) 为Round3 为对k = 40 至59 执行点击此处返回所使用的函数为所使用的常数(用十六进制表示) 为Round4 为对k = 60 至79 执行