hash算法

一、Hash散列算法介绍

1.引言

每个人在这个社会上生存，都会有一个属于自己的标记，用于区分不同的个体。通常使用名字就可以了。但是一个名字也并不能完全表示一个人，因为重名的人很多。所以我们可以使用一个身份证号或者指纹来表示独一无二的一个人。

同样在互联网的世界，使用一个符号来表示一个独一无二的事物也很重要。比如我们下载一个文件，文件的下载过程中会经过很多网络服务器、路由器的中转，如何保证这个文件下载过程中没有丢包，被完整的下载下来了呢？我们不可能去检测这个文件的每个字节，也不能简单地利用文件名、文件大小这些极容易伪装的信息去判断。这时候，我们就需要一种指纹一样的标志来检查文件的可靠性，这种指纹就是我们现在所用的Hash算法(也叫散列算法)。

比如从mysql官网下载mysql时，在软件包的右下角，都会有一个MD5算法算出来的hash值。这个hash值有什么用呢？其实这是给我们校验下载的软件包是否完整用的。当我们下载完成后，可以通过相关的手段，比如在linux系统中可以通过md5sum这个命令，计算我们下载的软件包的hash值，然后和官网给出的hash值进行比较，如果两个相等，就表示文件被完整的下载了。

所谓数据的完整性，指的是数据在网络传输中是否被篡改、是否丢包，发送方发出的数据和接收方接收的数据是一样的，就表明数据是完整的。如何评估数据的完整性？通常使用Hash散列函数。散列函数的主要任务是验证数据的完整性。通过散列函数计算得到的结果叫做散列值，这个散列值也常常被称为数据的指纹( Fingerprint)。

2.介绍

1.哈希（Hash）散列算法是将目标文本转换成具有相同长度的、不可逆的杂凑字符串的一种散列算法。

2.不同的目标文本转换的hash值可能是一样的,是多对一的。

二、1.hash散列算法的数学公式

上面就是hash算法的数学公式,能看懂吗,看不懂,我们不用懂,只知道它的作用是啥就行了.后面讲的几种hash算法的种类都是由这个数学公式进行不同的修改而得到的.

三、Hash散列算法的特征

一个优秀的散列算法有几个重要的特征：

1.固定长度。散列函数可以接受任意大小的数据，并输出固定长度的散列值。比如MD5这个hash函数为例，不管原始数据有多大，计算得到的hash散列值总是128比特。
2.雪崩效应。原始数据哪怕只有一个字节的修改，得到的hash值都会发生巨大的变化。
3.单向。只能从原始数据计算得到hash值，不能从hash值计算得到原始数据。所以散列算法不是加密解密算法，加密解密是可逆的，散列算法是不可逆的。
4.避免冲突。几乎不可能找到一个数据和当前计算的这个数据计算出一样的hash值，因此散列函数能够确保数据的唯一性。目前标准的MD5算法理论碰撞概率是2的128次方分之一。正是因为这种算法的碰撞概率很小，所以说我们在实际使用的过程之中才是可以无视这个数而直接使用MD5数据确定唯一性。

四、哈希算法的种类

目前主流的哈希算法有两个大类

• 加密型：MD(Message Digest)：消息摘要算法
• 加密型：SHA(Secure Hash Algorithm)：安全散列算法
• 非加密型：CRC、MurmurHash算法

1.消息摘要(密码加密)算法

MD算法家族包括：MD2，MD4，MD5，它们生成的消息摘要都是 128位 的，通常用16进制表示为32个字符

MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年设计的

MD5（RFC 1321）是Rivest于 1991 年对MD4的改进版本,比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。

MD5算法具有以下特点：

1、压缩性：任意长度的数据，算出的MD5值长度都是固定的。 2、容易计算：从原数据计算出MD5值很容易。 3、抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的MD5值都有很大区别。 4、强抗碰撞：已知原数据和其MD5值，想找到一个具有相同MD5值的数据（即伪造数据）是非常困难的。

MD5应用场景：

1、一致性验证 2、数字签名 3、安全访问认证

从安全性上说：MD5 > MD4 > MD2

2.安全散列算法

安全散列算法是一个 密码散列函数家族，是FIPS所认证的安全散列算法，它是一个能计算出数字消息所对应到的，长度固定(又称消息摘要)的算法

SHA家族的五个算法，分别是 SHA-1、SHA-224、SHA-256、SHA-384、SHA-512，后面四个有时统称为 SHA-2

SHA-1可将一个最大 2的64次方位(也就是17179PB) 的讯息，转换成一串 160位 的讯息摘要，而后四个算法生成的摘要长度为它们名字 后面的数字，如SHA-256算法，它生成的摘要长度为256位，因此它的抗穷举（brute-force）性比MD更好

SHA1有如下特性：

不可以从消息摘要中复原信息；两个不同的消息不会产生同样的消息摘要。

3.非加密型

MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。 由Austin Appleby在2008年发明， 并出现了多个变种，都已经发布到了公有领域。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。其在Redis，Memcached，Cassandra，HBase，Lucene都使用了这种hash算法。所有很有必要说一下。

Redis在实现字典时用到了两种不同的哈希算法，MurmurHash便是其中一种（另一种是djb）。MurmurHash在Redis中应用十分广泛，包括数据库、集群、哈希键、阻塞操作等功能都用到了这个算法。发明算法的作者被邀到google工作，该算法最新版本是MurmurHash3，基于MurmurHash2改进了一些小瑕疵，使得速度更快，实现了32位（低延时）、128位HashKey，尤其对大块的数据，具有较高的平衡性与低碰撞率。

与MD5这些讲究安全性的摘要算法比，MurmurHash并不关注安全性，比如在Redis内部只是为主键做个Hash而已，就不需要安全性了。因此MurmurHash是一种non-cryptographic的hash算法，比安全散列算法快几十倍。

MD5应用地方：

比如Guava包、Jedis包，Cassandra包

MurmurHash算法总结：高运算性能，低碰撞率。

四、Hash散列算法的使用

3.1文件传输

在文件传输时，散列算法就是一种以较短的信息来保证文件唯一性的标志，这种标志与文件的每一个字节都相关，而且难以找到逆向规律。因此，当原有文件发生改变时，其标志值也会发生改变，从而告诉文件使用者当前的文件已经不是你所需求的文件。

这种场景，对hash碰撞的要求要低于计算的速度，因为文件较大时，计算的速度会更重要。

3.2消息摘要(密码加密)

在密码学中，hash算法的作用主要是用于消息摘要（Message Digest），它主要用于对整个消息的完整性进行校验。举个例子，我们登陆B站的时都需要输入密码，那么B站的数据库会保存明文的密码吗？如果会明文保存，B站的DBA肯定会看到每个人的密码是什么，很不安全；同时如果用户在注册登录时也是明文在网络上传输账号密码，这个信息也会被人恶意截取，都会有很多安全问题。

通常一个系统都不会明文存储用户的密码，一般，用户在注册的时候，密码在用户侧还未提交时，就会使用密码的明文计算一个hash值，然后传输到后端系统，并将密文记录到数据库中，用户登录时，在用户侧在使用相同的算法对密码计算一个hash值，传到后端后，将这个hash值和数据库中的hash值进行比较，如果相同就登录成功；这样就避免了在网络传输或公司的DBA泄露用户密码，而且密码始终是在用户侧，所以只要用户知道密码的明文是什么。

在这些应用场景里，对于抗碰撞和抗篡改能力要求较高，对速度的要求在其次。一个设计良好的hash算法，其抗碰撞能力是很高的。以MD5为例，其输出长度为128位，碰撞的概率是2的128次方分之一

3.3数据结构

在用到hash进行管理的数据结构中，就对速度比较重视，对抗碰撞不太看中，只要保证hash均匀分布就可以。比如Hashmap，hash值（key）存在的目的是加速键值对的查找，key的作用是为了将元素适当地放在各个桶里，对于抗碰撞的要求没有那么高。换句话说，hash出来的key，只要保证value大致均匀的放在不同的桶里就可以了。但整个算法的set性能，直接与hash值产生的速度有关，所以这时候的hash值的产生速度就尤为重要：

五、Hash算法的安全性

MD5、SHA1等hash算法作为一种不可逆算法，一定程度上保证了密码的安全性，但是MD5等hash算法真的是完全安全的吗，其实不然。

从概率来说，2的128次方遍历后至少出现两个相同的MD5值，但是2的128次方有多大？3402823669209384634633746074317.7亿，就算全世界最快的超级计算机也要跑几十亿年才能跑完。可是，王小云院士破解了MD5。这里所说的破解，并不是给王小云院士一个MD5散列值，然后她就能通过计算还原出原文来。从密文推算出明文理论上是不可能的，所以王小云的研究成果不能通过 MD5 的散列值逆向推算出明文。王小云的研究成果是给定消息 M1，能够计算获取 M2，使得 M2 产生的散列值与 M1 产生的散列值相同。这样，MD5 的抗碰撞性就不满足了，使得 MD5 不再是安全的散列算法。从而导致MD5 用于数字签名将存在严重问题，因为可以篡改原始消息，而生成相同的 Hash 值。因此，业界专家普林斯顿计算机教授Edward Felten等强烈呼吁信息体系的设计者赶快更换签名算法，而且他们侧重这是一个需要当即处理的问题。

同时美国国家技能与规范局（NIST）于2004年8月24日宣布专门谈论，谈论的首要内容为：“在近来的世界暗码学会议（Crypto 2004）上，研究人员宣布他们发现了破解数种HASH算法的办法，其间包含MD4，MD5，HAVAL-128，RIPEMD还有 SHA-0。剖析标明，于1994年代替SHA-0成为联邦信息处理规范的SHA-1的削弱条件的变种算法能够被破解；但完好的SHA-1并没有被破解，也没有找到SHA-1的碰撞。研究结果阐明SHA-1的安全性暂时没有问题，但随着技能的发展，技能与规范局计划在2010年之前逐步筛选SHA-1，换用别的更长更安全的算法（如SHA-224、SHA-256、SHA-384和SHA-512）来代替。”

所以从这里也可以看出，单步的hash算法还是存在很大的漏洞，容易被碰撞。那么该如何进一步的加强hash算法的安全性呢，可以使用如下的办法：

5.1.hash+盐（salt）

salt可以简单的理解成：随机产生的一定长度的，可以和密码相结合，从而使hash算法产生不同结果的字符串。也就相当于你的新密码 = 旧密码 + 随机的盐值，然后对新密码进行hash。 优点：这种方法会极大防止受到彩虹表的攻击，因为即便攻击者构造出彩虹表，因为你使用了 hash(密码+ salt)，攻击者彩虹表里的哈希值hash(密码)和你数据库中的哈希值是不同的。

5.2.增加计算的时间(哈希+salt+Iteration)

通过迭代计算的方式增加计算密码的成本。迭代的周期控制在用户可以接受范围内，这样攻击者的计算和时间成本就会大大增加。

一般到此时，hash结果就比较安全了。但是如果还需要更加地安全，可以继续对这种方法计算出来的hash值使用加密算法加密。