什么是哈希函数

admin管理员组

文章数量:1530936

2024年7月25日发(作者：)

什么是哈希函数

哈希（Hash）函数在中文中有很多译名，有些人根据Hash的英文原意译为“散列函

数”或“杂凑函数”，有些人干脆把它音译为“哈希函数”，还有些人根据Hash函数的功

能译为“压缩函数”、“消息摘要函数”、“指纹函数”、“单向散列函数”等等。

1、Hash算法是把任意长度的输入数据经过算法压缩，输出一个尺寸小了很多的固定

长度的数据，即哈希值。哈希值也称为输入数据的数字指纹（Digital Fingerprint）或消

息摘要（Message Digest）等。Hash函数具备以下的性质：

2、给定输入数据，很容易计算出它的哈希值；

3、反过来，给定哈希值，倒推出输入数据则很难，计算上不可行。这就是哈希函数的

单向性，在技术上称为抗原像攻击性；

4、给定哈希值，想要找出能够产生同样的哈希值的两个不同的输入数据，（这种情况

称为碰撞，Collision），这很难，计算上不可行，在技术上称为抗碰撞攻击性；

5、哈希值不表达任何关于输入数据的信息。

哈希函数在实际中有多种应用，在信息安全领域中更受到重视。从哈希函数的特性，

我们不难想象，我们可以在某些场合下，让哈希值来“代表”信息本身。例如，检验哈希

值是否发生改变，借以判断信息本身是否发生了改变。`

怎样构建数字签名

好了，有了Hash函数，我们可以来构建真正实用的数字签名了。

发信者在发信前使用哈希算法求出待发信息的数字摘要，然后用私钥对这个数字摘要，

而不是待发信息本身，进行加密而形成一段信息，这段信息称为数字签名。发信时将这个

数字签名信息附在待发信息后面，一起发送过去。收信者收到信息后，一方面用发信者的

公钥对数字签名解密，得到一个摘要H；另一方面把收到的信息本身用哈希算法求出另一

个摘要H’，再把H和H’相比较，看看两者是否相同。根据哈希函数的特性，我们可以

让简短的摘要来“代表”信息本身，如果两个摘要H和H’完全符合，证明信息是完整的；

如果不符合，就说明信息被人篡改了。

数字签名也可以用在非通信，即离线的场合，同样具有以上功能和特性。

由于摘要一般只有128位或160位比特，比信息本身要短许多倍，USB Key或IC卡

中的微处理器对摘要进行加密就变得很容易，数字签名的过程一般在一秒钟内即可完成。

哈希函数的安全性

哈希函数的安全性直接关系到数字签名的安全性，如果哈希函数被攻破，数字签名的

有效性就会受到质疑。

目前，已经发明的Hash函数有多种，如Snefru、N-Hash、LOKI、AR、GOST、

MD、SHA等。它们在数学上实现的方法各有不同，安全性也各有不同。目前比较常用的

Hash函数是MD5和SHA-1。 MD5哈希函数以512位来处理输入数据，每一分组又划

分为16个32位的子分组。算法的输出由4个32位分组组成，将它们级联起来，形成一

个128位的固定长度的哈希值，即输入数据的摘要。SHA-1哈希函数在MD4的基础上增

加了数学运算的复杂程度，即SHA=MD4+扩展转换+附加轮+更好的雪崩效应（哈希值中，

为0的比特和为1的比特，其总数应该大致相等；输入数据中一个比特的变化，将导致哈

希值中一半以上的比特变化，这就叫做雪崩效应）。SHA能够产生160位的哈希值。对SHA

还没有已知的密码攻击，并且由于它产生的哈希值位数长于MD5，所以它能更有效地抵抗

穷举攻击（包括生日攻击）。

但是，任何一种算法都有其漏洞和局限性。任何一个哈希函数都会存在碰撞——即在

一些特定情况下，两个不同的文件或信息会指向同一个数字摘要。在一般情况下，类似碰

撞只能尽可能地减少，而不能完全避免。从理论上讲，没有攻不破的密码。随着密码科学

的发展，也许会找到攻破某一种密码算法的途径。

评价Hash算法的一个最好方法是看敌手找到一对碰撞消息所花的代价有多高。一般

地，假设攻击者知道Hash算法，攻击者的主要攻击目标是找到一对或更多对碰撞消息。

目前已有一些攻击Hash算法和计算碰撞消息的方法。在这些方法中，有些是一般的方法，

可用于攻击任何类型的Hash算法，比如“生日攻击”；而另一些是特殊的方法，只能用于

攻击某些特殊的Hash算法，比如适合于攻击具有分组链结构Hash算法的“中间相遇攻

击”，适用于攻击基于模运算的Hash函数的“修正分组攻击”。坚固的哈希函数可通过设

计有效的碰撞处理机制，或增加数字摘要的位数来增加复杂度，以减少碰撞出现的概率，

2004年8月17日，在美国召开的国际密码学会议（Crypto’ 2004）上，一些国家

的密码学者作了破译Hash函数的新进展的报告，其中我国山东大学的王小云教授做了破

译MD5、HAVAL-128、MD4、和RIPE MD算法的报告。

到2005年2月，据王小云教授的研究报告，他们已经研究出了搜索SHA-1碰撞的一

系列新技术。他们的分析表明，SHA-1的碰撞能在小于2^69次Hash操作中找到。对完

整的80轮SHA-1的攻击，这是第一次在小于2^80次Hash操作这个理论界限的情况下

找到碰撞。根据他们的估计，对于缩减到70轮的SHA-1能够用现在的超级计算机找出“实

碰撞”。他们的研究方法，能自然地运用到SHA-0和缩减轮数的SHA-1的破译分析上。

2005年3月6日，Arjen Lenstra，王小云，Benne de Weger 宣布，他们构造出一

对基于MD5 Hash函数的X.509证书，产生了相同的签名。他们提出了一种构造X.509

证书的方法，在他们所构造出的证书对中，由于使用了MD5算法，签名部分产生了碰撞。

因此，当证书发布者使用MD5作为Hash函数时，发布者就会在证书中产生相同的签名，

导致PKI的基础原理遭到可信性破坏。这意味着，从单独某个证书无法确定是否存在另一

个不同证书有着相同的签名。由于第二个相同签名证书存在的可能性，证书发布机构无法

验证私钥的“拥有证明”，即无法验证证书中的签名。因此，使用“基于MD5函数”公钥

证书的任何一方都无法确保所谓的证书拥有者是否真实拥有相应的私钥。

他们也想构造一对基于SHA-1的X.509证书，产生相同的签名。然而，他们还做不

到这一点。因为产生SHA-1碰撞还需要相当长一段时间的研究。

专家指出：a和王小云等人声称已经成功地构造了两张符合X．509证书数据

结构，拥有同样签名而内容却不同的证书，但该构造方法对证书的部分域要有特殊安排，

签名算法RSA的密钥也是按照特殊规律生成的，要用来攻击某个实际应用的电子签名系统

仍需时日。而对于SHA-1算法，说其从理论上被破解都还为时过早，只能说其破解工作取

得了重大突破，破解所需要运算次数已从原来设计时估算的2^80次降低为2^69次，这

比穷举法快了２０４８倍，但2^69次运算需要６０００年左右的时间，在实际计算上仍

然是不可行的。

除了运算方面的瓶颈外，哈希函数的不可逆性决定了攻击者无法轻易得手，没有人可

以保证通过这个发现的每个碰撞都是“可用”的碰撞。在漫长的运算后，你得到的也许包

含一些有价值的信息，也许就是理论上存在的单纯碰撞，运算瓶颈和信息匮乏都会使黑客

们的种种努力成为徒劳……据业内人士估计，在当前的技术条件下，２^50或２^ ６０次

运算量的范围内的攻击方法才会为我们带来麻烦，即引发实际意义上的攻击行为。在新研

究成果发布前的一段时间内，SHA-1 算法只能被称作不完美，但还是安全的。基于PKI

技术进行电子签名的最终用户，目前还不用担心自己的签名被伪造或遭遇签名人抵赖。

另外，安全专家强调：一种算法被破译，和整个企业的安全系统被攻破，是两个不同

的概念。因为随着攻击技术和能力的提高，算法也会“水涨船高”，向前发展进步。王教授

所取得的成就提醒密码学家研究新的算法，提醒有关标准化机构要提前修改算法标准，也

提醒有关CA和电子签名产品开发商支持新的算法。当然，有些完全基于摘要算法的密押

系统和电子货币系统，还需要尽早考虑替换方案。

美国国家技术与标准局（NIST）曾经发表如下评论：“研究结果说明SHA-1的安全性

暂时没有问题，但随着技术的发展，技术与标准局计划在2010年之前逐步淘汰SHA-1，

换用其他更长更安全的算法（如：SHA-224, SHA-256, SHA-384和SHA-512）来代替。”

本文标签： 算法信息函数碰撞攻击