第4章hash函数.

主讲人：侯红霞通信与信息工程学院第4章Hash函数主要内容4.1Hash函数与随机预言模型•在实际的通信保密中，除了要求实现数据的保密性之外，对传输数据安全性的另一个基本要求是保证数据的完整性。•密码学中的Hash函数的主要功能是提供有效的数据完整性检验。数据的完整性是指数据从发送方产生后，经过传输或存储以后，未被以未授权的方式修改的性质。4.1.1Hash函数•Hash函数是一个将任意长度的消息序列映射为较短的、固定长度的一个值的函数。•密码学上的Hash函数能够保障数据的完整性。•通常被用来构造数据的“指纹”（即函数值），当被检验的数据发生改变的时候，对应的“指纹”信息也将发生变化。•对于Hash函数的安全要求，如果对于①原像问题②第二原像问题③碰撞问题•这三个问题都是难解的，则认为该Hash函数是安全的。定义4.1.1原像问题（PreimageProblem）：设:HXY是一个Hash函数，yY。是否能够找到xX，使得()Hxy。X—消息集合Y—消息摘要集合不能有效解决原像问题的Hash函数称为单向的或原像稳固的。定义4.1.2第二原像问题（SecondPreimageProblem）：设:HXY是一个Hash函数，xX。是否能够找到xX，使得xx，并且()()HxHx。不能有效解决第二原像问题的Hash函数称为第二原像稳固的。定义4.1.3碰撞问题（CollisionProblem）：设:HXY是一个Hash函数。是否能够找到,xxX，使得xx，并且()()HxHx。不能有效解决碰撞问题的Hash函数称为碰撞稳固的。•实际应用中的Hash函数可分为:简单的Hash函数带密钥的Hash函数•一个带密钥的Hash函数通常用来作为消息认证码MAC（Messageauthenticationcode）•定义4.1.4一个带密钥的Hash函数包括以下构成要素：–X:所有消息的集合（有限级或无限级）–Y:所有消息摘要构成的有限集合–K:密钥集合–对任意的都存在一个Hash函数如果则二元组称为在密钥k下是有效的kK()kHxy(,)xyXY•Hash函数的性质：（1）能够用于任何大小的数据分组（2）能产生定长的输出（3）易于计算，便于软硬件实现（4）原像稳固（5）第二原像稳固（6）碰撞稳固这3个条件是用于消息认证的基本要求单向性防止伪造防止生日攻击•Hash函数的目的是确定消息是否被修改。•对Hash函数攻击的目标是–生成这样的修改后消息：其Hash函数值与原始消息的Hash函数值相等。例如，如果Oscar找到了一对消息M1和M2，使得12()()HMHM，而消息M1是Alice发送的，那么Oscar就可以用M2来替换M1，从而达到攻击的目的。生日攻击生日攻击的思想来源于概率论中一个著名的问题----生日问题。该问题是问一个班级中至少要有多少个学生才能够使得有两个学生生日相同的概率大于1/2。该问题的答案是23。即只要班级中学生的人数大于23人，则班上有两个人生日相同的概率就将大于1/2。基于生日问题的生日攻击意味着要保证消息摘要对碰撞问题是安全的，则安全消息摘要的长度就有一个下界。如果消息摘要为m位长度，则总的消息数为2m，因此需要检查大约2m/2个消息，可使两条消息具有相同Hash函数值的概率大于50%。•Oscar可以生成下述形式的可接受消息：例Ipromiseagreetolendloan25twentyfivedollarstomygoodbestfriendOscarwhichhewillrepayreturntomein10tendaysorlesssooner,,YoursSincerelyAlice•也可以生成下述形式的不可接受的消息：Ipromiseagreetogiveoffer25twentyfivedollarstomygoodbestfriendOscarasagiftpresentwhichheshouldnotwillnotrepaybecauseIknowheneedthishelpaid,,YoursSincerelyAlice•在对所有512条消息取Hash函数值后，Oscar也许会发现，“Ipromisetolend25dollarstomybestfriendOscarwhichhewillreturntomein10daysorlessYours,Alice”“Iagreetooffertwenty-fivedollarstomygoodfriendOscarassgiftwhichheshouldnotrepaybecauseIknowheneedsthisaidSincerely,Alice”•有相同的Hash函数值。这意味着Oscar可用后者来替换前者。4.1.2随机预言模型•由Bellare和Rogaway提出的随机预言模型（RandomOracleModel）是一种“理想化”的Hash函数数学模型。•在这个模型中，随机从Fx,y中选出一个Hash函数H，我们仅仅允许预言器访问函数H这表示对于任一个消息x，随机预言模型都不会给出一个公式或者算法来计算消息摘要H(x)的值。计算H(x)值的惟一方法是询问预言器相当于根据给出的消息x，在一本关于随机数的书中查询H(x)的值对于每一个x，都有一个完全随机的H(x)与之对应定义4.1.5令,XYF是所有从X到Y的函数集合。假定XN，YM，则,XYNFM。任何Hash函数族,XYFF被称为一个(,)NM－Hash族。对于随机预言模型，以下结论是成立的。定理4.1随机选择,XYHF并取子集合0XX。假设当且仅当0xX时，()Hx的值由查询预言器确定，那么对于所有的0\xXX和yY，1(())PHxyM。M的值越大，相应的产生碰撞的概率就越小。4.2迭代的Hash函数•1979年，Merkle基于数据压缩函数建议了一个Hash函数的通用模式。•数据值由消息分组组成，对所有数据分组进行迭代处理。compresscompressm位压缩值t位数据值ym位输出图4-1迭代Hash函数系统结构compresscompresscompressZ0Y1Z1Y2Zn-1Yn-1Zn输入Yn-1基于消息x构造y=y1||y2||…yr，yr长度为t输入Zn具体的迭代过程如下：101()zcompresszy1()rrrzcompresszy最终得到长度是m的位串rz。输出：设:{0,1}{0,1}mtg是一个公开函数，定义()()rHxgz。则有：1:{0,1}{0,1}itimtH4.3MD•MD（MessageDigest，消息摘要）算法由RonRivest在1990年10月提出，1992年4月，RonRivest公布了相应的改进算法。人们通常把RonRivest在1990年提出的算法称为MD4把相应的改进算法称为MD54.3.1MD5•MD5以512位的分组长度来处理消息，每一个分组又被划分为16个32位的子分组。•算法的输出由4个32位的分组组成，它们串联成一个128位的消息摘要。•MD5将任意长度的“字节串”变换成一个128bit的大整数，并且是一个不可逆的字符串变换算法。图4-2MD5产生报文摘要的过程具体过程具体步骤：(1)填充消息使其长度正好为512位的整数倍–末尾处附上64比特消息长度的二进制表示–然后在消息后面填充一个“1”和多个“0”–填充后的消息恰好是512比特的整倍长L。64比特•消息长度为704位M0M1M2…M13M14M15例消息704填充256位消息长度64位1000000……00000……10110000002x512=1024分组M0M1M2…M13M14M15消息704填充256位消息长度64位512512•(2)初始化缓冲区–算法中使用了128位的缓冲区，每个缓冲区由4个32比特的寄存器A，B，C，D组成，先把这4个寄存器初始化为：回合運算(共16次單元運算)回合運算(共16次單元運算)回合運算(共16次單元運算)回合運算(共16次單元運算)ABCD32ABCD32ABCD32ABCD32128qCV++++1281qCV512qY+:相加後再模322单个分组的MD5处理过程(3)处理512位消息块Yq，进入主循环第一轮中的Mi为填充之后的M0……M15第二，三四轮中的Mi由公式计算得出包含4轮操作，每一轮由16次迭代操作组成，上一轮的输出作为下一轮的输入。消息块第q次输出第q+1次输出MiMiMiMiMi为Yq中的16个字AABBCCDD从第二轮到第四轮则依次通过下面的置换实现。2()(15)mod16jj3()(53)mod16jj4()7mod16jj4轮循环中每一轮用的16个Mi如下表所示M0M1M2M3M4M5M6M7M8M9M10M11M12M13M14M15M1M6M11M0M5M10M15M4M9M14M3M8M13M2M7M12M5M8M11M14M1M4M7M10M13M0M3M6M9M12M15M2M0M7M14M5M12M3M10M1M8M15M6M13M4M11M2M9图4-4基本MD5操作(单步)ABCDABCD+++sCLS+X[k]T[i]g回合數運算函數g1234),,(DCBg)()(DBCB),,(DCBF)()(DCDB),,(DCBG)(DCB),,(DCBH)(DBC),,(DCBI4个非线性函数分别为：一轮具体操作Mi常数•b）常数tj：常数表T[i]共有64个元素，每个元素32位长，tj＝232abs(sin(i))的整数部分,其中j是弧度。处理每一个消息块Yi时，每一轮使用常数表T[i]中的16个，正好用4轮。•c)循环左移数：–每轮中每步左循环移位的位数按下表执行。步数轮数123456789101112131415161234754612911101714161522202321754612911101714161522202321754612911101714161522202321754612911101714161522202321每一轮不断地更新缓冲区A，B，C，D中的内容4轮之后进入下一个主循环，直到处理完所有消息块为止。输出,,,AAAABBBBCCCCDDDD()HxABCD得到128位的消息摘要•MD5相对MD4进行了以下一些改进：增加了主循环中的操作次数，由三轮操作改进为四轮操作；操作的每一步均有惟一的加法常数；减弱函数的对称性；改变了第二轮和第三轮中访问消息子分组的次序，使得其形式更加不相似；近似优化了每一轮中循环移位的位移量，各轮的位移量各不相同。••MD5算法有以下性质：Hash函数的每一位均是输入消息序列中每一位的函数。保证了在Hash函数计算过程中产生基于消息x的混合重复，从而使得生成的Hash函数结果混合得非常理想。也就是说，随机选取两个有着相似规律性的两组消息序列，也很难产生相同的Hash函数值。4.3.2MD4•MD4算法的具体过程如下：–首先输入任意长度的消息x，由x构造一个数组序列–给定4个寄存器A,B,C,D对其赋初值：[0][1][1]MMMMn67452301A89Befcdab98Cbadcfe10325476D–计算–将已有的4个寄存器中的数组分别存放到另外4个寄存器中–执行第一轮操作。[][16]XjMij((,,)[4])3AAFBCDXk((,,)[41])7DDFABCXk((,,)[42])11CCFDABXk((,,)[43])19BB