Hash函数的相关知识

Crypto Hash

Word count: 1.5kReading time: 5 min

 2020/10/10   Share

Hash

基本概念

Hash也就是我们俗称的哈希，也叫”散列”,意思是“混杂、拼凑、杂乱”
Hash其实可以看做是排序的一种相反的操作，排序是按照某种规则将元素排列起来，而散列通过计算哈希值将元素之间的关系打破，形成新的序列

Hash的作用

Hash 算法的原理是试图将一个空间的数据集映射到另外一个空间（通常比原空间要小），并利用质数将数据集能够均匀的映射。
Hash通过计算大幅度缩小查找范围，比直接从全部数据里面查找速度更快

Hash的特点

免碰撞：即不会出现输入 x≠y ，但是H(x)=H(y) 的情况，其实这个特点在理论上并不成立，比如目前比特币使用的 SHA256 算法，会有 2^256 种输出，如果我们进行 2^256 + 1 次输入，那么必然会产生一次碰撞，事实上，通过理论证明，通过 2^130 次输入就会有99%的可能性发生一次碰撞，不过即使如此，即便是人类制造的所有计算机自宇宙诞生开始一直运算到今天，发生一次碰撞的几率也是极其微小的。
1. 隐匿性：也就是说，对于一个给定的输出结果 H(x) ，想要逆推出输入 x ，在计算上是不可能的。如果想要得到 H(x) 的可能的原输入，不存在比穷举更好的方法。

简单来说，Hash函数应该保证信息的安全性

Hash函数

Hash函数是一种映射类型，将一个数据集空间映射到另一个数据集空间并且理论上映射后的空间比映射前的数据集空间小
表达式表示为：
e = H[e]
其中e表示经过Hash函数变换后的值，H表示Hash函数，e表示明文

以下是几种常见类型：

MD4

MD4是麻省理工学院教授 Ronald Rivest 于1990年设计出来的算法。其摘要长度为128位，一般用32位的十六进制来表示。

2004年8月清华大学教授王小云，指出在计算MD4时可能发生杂凑冲撞。不久之后，Dobbertin 等人发现了MD4在计算过程中第一步和第三步中的漏洞，并向大家演示了如何利用一部普通电脑在几分钟内找到MD4中的冲突，毫无疑问，MD4就此被淘汰掉了。

MD5

1991年，Rivest 开发出技术上更为趋近成熟的MD5算法，它在MD4的基础上增加了”安全-带子”（safety-belts）的概念。虽然 MD5 比 MD4 复杂度大一些，但却更为安全。这个算法很明显的由四个和 MD4 设计有少许不同的步骤组成。

MD5 拥有很好的抗修改性，即对原数据进行任何改动，哪怕只修改1个字节，所得到的MD5值都有很大区别。

MD5很好的用在了大文件的断点续传上：如果有一个 5MB 的文件客户端把它分割成5片 1MB 的文件在上传的时候上传两个 MD5 值，一个是当前上传的文件片的 MD5 还有一个就是拼接之后的 MD5 (如果现在上传的是第二片这个MD5就应该是第一片加上第二片的MD5)，通过这样的方式能保证文件的完整性。

当如果文件传到一半断了，服务器可以通过验证文件 MD5 值就可以得知用户已经传到了第几片，并且知道之前上传的文件有没有发生变化，就可以判断出用户需要从第几片开始传递。

不过在2004年8月的国际密码学会议（Crypto’2004），王小云提出了一种快速找到 MD5 碰撞的方法（参见其论文），降低了 MD5 的安全性，人们开始寻求更加可靠的加密算法。

SHA系列

SHA的全称是Secure Hash Algorithm(安全hash算法)，SHA系列有五个算法，分别是 SHA-1、SHA-224、SHA-256、SHA-384，和SHA-512，由美国国家安全局（NSA）所设计，并由美国国家标准与技术研究院（NIST）发布，是美国的政府标准。后四者有时并称为 SHA-2。SHA-1在许多安全协定中广为使用，包括 TLS/SSL 等，是 MD5 的后继者。