复旦大学：《信息安全原理》课程教学资源（PPT课件）第4章 密码应用（3/4）

散列函数的选取不能减弱签名方案的安 全性,它必须能够防止他人伪造。因此 一个好的散列函数应该具有以下特性: 弱无碰撞:给定一个消息x,找到一个满 足h(x)=h(x)的消息x,≠x是计算上不可 行的 强无碰撞:找到满足h(x)=h(x)并且x≠ x的消息x和x是计算上不可行的; 单向:给定一个消息摘要z,找到一个满 足h(x)=z的消息x是计算上不可行的

 散列函数的选取不能减弱签名方案的安 全性，它必须能够防止他人伪造。因此 一个好的散列函数应该具有以下特性：  弱无碰撞：给定一个消息x，找到一个满 足h(x‘) = h(x) 的消息x’  x 是计算上不可 行的；  强无碰撞：找到满足h(x‘) = h(x) 并且x’ x 的消息x‘ 和 x是计算上不可行的；  单向：给定一个消息摘要 z，找到一个满 足h(x) = z 的消息x 是计算上不可行的

Hash函数如何构造,以达到前面的要求? 一个最基本必须满足的要求应该是任何输 入串中单个比特发生变化,将会导致输出 比特串中大约一半的比特发生变化 构造方法主要有以下几种 利用某些对称密码体制,设计Hash函数 利用某些数学难题假设,设计Hash函数, 可以在某些难问题假设下证明是强务碰撞 的。 直接设计Hash函数

 Hash函数如何构造，以达到前面的要求？  一个最基本必须满足的要求应该是任何输 入串中单个比特发生变化，将会导致输出 比特串中大约一半的比特发生变化。  构造方法主要有以下几种  利用某些对称密码体制，设计Hash函数  利用某些数学难题假设，设计Hash函数， 可以在某些难问题假设下证明是强务碰撞 的。  直接设计Hash函数

422可证安全的散列函数 一个散列函数是这样设计的:p是一个 大素数,且q=(p-1)/2也是素数,设a和 β是域Zp的本原元,值ogB不公开 且假设求ogB在计算上是不可行的。 定义散列函数h:Zq×Zq→>Zp-{0}为 h(x1x2)=axB zmodp 定理:若给定该散列函数的一个碰撞, 则ogβ定能有效计算

 4.2.2 可证安全的散列函数  一个散列函数是这样设计的： p是一个 大素数，且q=(p-1)/2也是素数， 设  和 是域Zp的本原元，值log  不公开， 且假设求log  在计算上是不可行的。 定义散列函数h: Zq Zq Zp-{0} 为  h(x 1,x 2)=  x 1  x 2modp  定理：若给定该散列函数的一个碰撞， 则log  一定能有效计算

4.23MD5算法 MD5的全称是 message-digest algorithm5(信 息摘要算法),在90年代初由 MIT laboratory for computer science和 RSA data security inc的 ronald. rivest开发出来,经MD2、MD3和 MD4发展而来。 它的作用是让大容量信息在用数字签名软件签 署私人密匙前被“压缩”成一种保密的格式 (就是把一个任意长度的字节串变换成一定长 的大整数)。不管是MD2、MD4还是MD5, 它们都需要获得一个随机长度的信息并产生一 个128位的信息摘要

 4.2.3 MD5算法  MD5的全称是message-digest algorithm 5（信 息 -摘要算法），在90年代初由MIT laboratory for computer science 和RSA data security inc 的 ronald l. rivest开发出来，经MD2 、MD3 和 MD4发展而来。  它的作用是让大容量信息在用数字签名软件签 署私人密匙前被“压缩”成一种保密的格式 （就是把一个任意长度的字节串变换成一定长 的大整数）。不管是MD2 、MD4还是MD5 ， 它们都需要获得一个随机长度的信息并产生一 个128位的信息摘要

虽然这些算法的结构或多或少有些相似,但 MD2的设计与MD4和MD5完全不同,那是因 为MD2是为8位机器做过设计优化的,而MD4 和MD5却是面向32位的电脑。 Rivest在1989年开发出MD算法。在这个算法 中,首先对信息进行数据补位,使信息的字节 长度是16的倍数。然后,以一个16位的检验和 追加到信息末尾。并且根据这个新产生的信息 计算出散列值。后来, rogier和 chauvaud发现 如果忽略了检验将产生碰撞。MD2算法的加密 后结果是唯一的-既没有重复

 虽然这些算法的结构或多或少有些相似，但 MD2的设计与MD4 和MD5完全不同，那是因 为MD2是为 8位机器做过设计优化的，而MD4 和MD5却是面向32位的电脑。  Rivest 在1989年开发出MD2算法。在这个算法 中，首先对信息进行数据补位，使信息的字节 长度是16的倍数。然后，以一个16位的检验和 追加到信息末尾。并且根据这个新产生的信息 计算出散列值。后来，rogier 和chauvaud发现 如果忽略了检验将产生碰撞。MD2算法的加密 后结果是唯一的--既没有重复

为了加强算法的安全性,rive在1990年又 开发出MD4算法。MD4算法同样需要填补 信息以确保信息的字节长度加上448后能被 512整除(信息字节长度mod512=448)。 然后,一个以64位二进制表示的信息的最初 长度被添加进来。信息被处理成512位迭代 结构的区块,而且每个区块要通过三个不同 步骤的处理。 Den boer和 Bosselaers以及其 他人很快的发现了攻击MD4版本中第一步 和第三步的漏洞。 Dobbertin向大家演示了 如何利用一部普通的个人电脑在几分钟内找 到MD4完整版本中的碰撞。毫无疑问, MD4就此被淘汰掉了

 为了加强算法的安全性，rivest 在1990年又 开发出MD4算法。MD4算法同样需要填补 信息以确保信息的字节长度加上448后能被 512整除（信息字节长度mod 512 = 448）。 然后，一个以64位二进制表示的信息的最初 长度被添加进来。信息被处理成512位迭代 结构的区块，而且每个区块要通过三个不同 步骤的处理。Den boer 和Bosselaers以及其 他人很快的发现了攻击MD4版本中第一步 和第三步的漏洞。Dobbertin向大家演示了 如何利用一部普通的个人电脑在几分钟内找 到MD4完整版本中的碰撞。毫无疑问， MD4就此被淘汰掉了

1991年, Rivest开发出技术上更为趋近成熟 的MD5算法。它在MD4的基础上增加了 “安全带子”( safety- belts)的概念。虽 然MD5比MD4稍微慢一些,但却更为安全。 这个算法由四个和MD4设计有少许不同的 步骤组成。在MD5算法中,信息-摘要的大 小和填充的必要条件与MD4完全相同。Den boer和 Bosselaers曾发现MD5算法中的假碰 撞( pseudo- collisions)

 1991年，Rivest开发出技术上更为趋近成熟 的MD5算法。它在MD4的基础上增加了 “安全 -带子”（safety-belts）的概念。虽 然MD5 比MD4稍微慢一些，但却更为安全。 这个算法由四个和MD4设计有少许不同的 步骤组成。在MD5算法中，信息 -摘要的大 小和填充的必要条件与MD4完全相同。Den boer 和Bosselaers曾发现MD5算法中的假碰 撞（pseudo-collisions）

MD5算法生成了四个32比特长的字,在 实际应用中可以将这四个字连接起来形 成一个128比特长的字,作为明文压缩的 结果。 如果位数仍不能达到要求,则只要对上 述算法及程序稍加修改即可。 2004年8月17日的美国加州圣巴巴拉,正 在召开的国际密码学会议( Crypto2004) 安排了三场关于杂凑函数的特别报告。 来自山东大学的王小云教授做了破译 MD5、 HAVAL-128、MD4和 RIPEMD 算法的报告

 MD5算法生成了四个32比特长的字，在 实际应用中可以将这四个字连接起来形 成一个128比特长的字，作为明文压缩的 结果。  如果位数仍不能达到要求，则只要对上 述算法及程序稍加修改即可。  2004 年 8 月17日的美国加州圣巴巴拉，正 在召开的国际密码学会议（Crypto’2004 ） 安排了三场关于杂凑函数的特别报告。 来自山东大学的王小云教授做了破译 MD5 、HAVAL-128 、 MD4 和RIPEMD 算法的报告

王小云发现,可以很快的找到MD5的 “碰撞”,由于版本问题,作者在提交 会议论文时使用的一组常数和先行标准 不同; 在会议发现这一问题之后,王小云教授 立即改变了那个常数,在很短的时间内 就完成了新的数据分析,这更加证明了 论文的信服力,攻击方法的有效性,凸 显了研究工作的成功

 王小云发现，可以很快的找到MD5 的 “碰撞”，由于版本问题，作者在提交 会议论文时使用的一组常数和先行标准 不同；  在会议发现这一问题之后，王小云教授 立即改变了那个常数，在很短的时间内 就完成了新的数据分析，这更加证明了 论文的信服力，攻击方法的有效性，凸 显了研究工作的成功

MD5的设计者,同时也是国际著名的公钥加密 算法标准RSA的第一设计者R. Rives在邮件中 写道:“这些结果无疑给人非常深刻的印象,她 应当得到我最热烈的祝贺,当然,我并不希望看 到MD5就这样倒下,但人必须尊崇真理。” MD5破解工程权威网站http://www.md5crk.com/ 是为了公开征集专门针对MD5的攻击而设立的, 网站于2004年8月17日宣布:“中国研究人员发 现了完整MD5算法的碰撞;Wang,Feng,Lai与 Yu公布了MD5、MD4、 HAVAL-128、 RIPEMD-128几个Hash函数的碰撞。这是近年 来密码学领域最具实质性的研究进展。使用他们 的技术,在数个小时内就可以找到MD5碰 撞。……)于这个里程碑式的发现,MD5CRK 项目将在随后48小时内结束

 MD5的设计者，同时也是国际著名的公钥加密 算法标准RSA的第一设计者 R．Rivest在邮件中 写道：“这些结果无疑给人非常深刻的印象，她 应当得到我最热烈的祝贺，当然，我并不希望看 到MD5就这样倒下，但人必须尊崇真理。”  MD5破解工程权威网站http://www.md5crk.com/ 是为了公开征集专门针对MD5的攻击而设立的， 网站于2004 年 8 月17日宣布：“中国研究人员发 现了完整MD5算法的碰撞；Wang, Feng, Lai 与 Yu公布了MD5 、MD4 、HAVAL-128 、 RIPEMD-128几个 Hash函数的碰撞。这是近年 来密码学领域最具实质性的研究进展。使用他们 的技术，在数个小时内就可以找到MD5 碰 撞。……由于这个里程碑式的发现，MD5CRK 项目将在随后48小时内结束