安全系列之——主流Hash散列算法介绍和使用

超、凢脫俗 2022-12-01 05:11 117阅读 0赞

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

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

![format_png][]

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

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

## 一、Hash散列算法介绍 ##

概括来说，哈希（Hash）是将目标文本转换成具有相同长度的、不可逆的杂凑字符串（或叫做消息摘要）。

而加密（Encrypt）是将目标文本转换成具有不同长度的、可逆的密文。Hash算法严格上来说并不属于加密算法，而是与加密算法属于并列关系的一种算法。

有加密就有解密，而hash算法是**不可逆**，因此不能算加密算法。这里的不可逆既指不能根据转换后的结果逆转回原文，也指对于两个输入，即使其转换结果相同也不能说这两个输入就一定相同。因为，Hash算法的定义域是一个无限集合，但是值域确是一个有限集合，将一个无限集合映射到有限集合上，每个哈希结果都存在无数个可能的目标文本，因此哈希是一个多对一的映射，所以它也不存在逆映射。但是对于加密算法，它的结果往往取决于输入，其定义域和值域都是无限集合，明显是一个一一映射，对于一一映射，理论上都是可逆的。

常见的Hash算法有：MD5、SHA-1、HMAC、HMAC-MD5、HMAC-SHA1等

## 二、Hash散列算法的特征 ##

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

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

## 三、散列算法的使用 ##

### 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值的产生速度就尤为重要：

/** * HashMap对象的hash() */
    static final int hash(Object key) { 
        int h;
        //计算hashCode，并无符号移动到低位
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    /** * Object对象的hashCode() */
    public int hashCode() { 
        int h = hash;
        //hash default value : 0 
        if (h == 0 && value.length > 0) { 
            //value : char storage
            char val[] = value;
            for (int i = 0; i < value.length; i++) { 
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

很简洁的一个乘加迭代运算，在不少的hash算法中，使用的是异或+加法进行迭代。

## 四、Hash算法的使用 ##

### 4.1.MD5算法 ###

Message Digest Algorithm MD5（消息摘要算法5）为计算机安全领域广泛使用的一种散列函数，用以提供消息的完整性保护。是计算机广泛使用的杂凑算法之一，将数据（如汉字）运算为另一固定长度值，是杂凑算法的基础原理，MD5的前身有MD2、MD3和MD4。

MD5算法具有以下特点：

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

MD5应用场景：

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

MD5代码测试：

package com.wuxiaolong.EncrypteDecrypt;
    
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.IOException;
    import java.io.UnsupportedEncodingException;
    import java.security.MessageDigest;
    import java.security.NoSuchAlgorithmException;
    
    /** * Description: * * @author 诸葛小猿 * @date 2020-08-25 */
    public class MD5Test { 
    
        public static void main(String[] args) { 
    
            // 字符串的Md5
            String content = "诸葛小猿";
            String hashStr = md5(content);
            System.out.println(content +" => "+ hashStr);
    
            //文件的MD5
            String filePath = "G:\\FiddlerSetup.exe";
            File file = new File(filePath);
            String fileHash = md5(file);
            System.out.println("file hash =>" + fileHash);
        }
    
        /** * 计算字符串的MD5值 * @param string 明文 * @return 字符串的MD5值 */
        public static String md5(String string) { 
            if (string.isEmpty()) { 
                return "";
            }
            MessageDigest md5 = null;
            try { 
                md5 = MessageDigest.getInstance("MD5");
                byte[] bytes = md5.digest(string.getBytes("UTF-8"));
                String result = "";
                for (byte b : bytes) { 
                    String temp = Integer.toHexString(b & 0xff);
                    if (temp.length() == 1) { 
                        temp = "0" + temp;
                    }
                    result += temp;
                }
                return result;
            } catch (NoSuchAlgorithmException e) { 
                e.printStackTrace();
            } catch (UnsupportedEncodingException e) { 
                e.printStackTrace();
            }
            return "";
        }
    
        /** * 计算文件的MD5值 * @param file 文件File * @return 文件的MD5值 */
        public static String md5(File file) { 
            if (file == null || !file.isFile() || !file.exists()) { 
                return "";
            }
            FileInputStream in = null;
            String result = "";
            byte buffer[] = new byte[0124];
            int len;
            try { 
                MessageDigest md5 = MessageDigest.getInstance("MD5");
                in = new FileInputStream(file);
                while ((len = in.read(buffer)) != -1) { 
                    md5.update(buffer, 0, len);
                }
                byte[] bytes = md5.digest();
    
                for (byte b : bytes) { 
                    String temp = Integer.toHexString(b & 0xff);
                    if (temp.length() == 1) { 
                        temp = "0" + temp;
                    }
                    result += temp;
                }
            } catch (Exception e) { 
                e.printStackTrace();
            }finally { 
                if(null!=in){ 
                    try { 
                        in.close();
                    } catch (IOException e) { 
                        e.printStackTrace();
                    }
                }
            }
            return result;
        }
    }

运行结果：

诸葛小猿  => 591a998db81be040be8591d7e2c2ddc2
    file hash =>8adb254960a54c08c4453775d10574ba

### 4.2.SHA1算法 ###

安全哈希算法（Secure Hash Algorithm）主要适用于数字签名标准里面定义的数字签名算法（Digital Signature Algorithm DSA）。对于长度小于2^64位的消息，SHA1会产生一个160位的消息摘要。当接收到消息的时候，这个消息摘要可以用来验证数据的完整性。在传输的过程中，数据很可能会发生变化，那么这时候就会产生不同的消息摘要。

SHA1算法原理：

首先进行SHA1分组：对于任意长度的明文，SHA1可以产生160位的摘要。对明文的分组处理过程如下：

> 1）对数据流尾部添加0x80标记。任意长度的明文首先需要添加位数，使明文总长度为448（mod512）位。将0x80字节追加到数据流尾部以后，源数据流的整个长度将会发生变化，考虑到还要添加64位（8个字节）的位长度，必须填充0 以使修改后的源数据流是64字节（512位）的倍数。在明文后添加位的方法是第一个添加位是1，其余都是0。
> 
> 2）然后将真正明文的长度（没有添加位以前的明文长度）以64位表示，附加于前面已添加过位的明文后，此时的明文长度正好是 512位的倍数。当明文长度大于2的64次方时，仅仅使用低64位比特填充，附加到最后一个分组的末尾。
> 
> 3）经过添加处理的明文，其长度正好为512位的整数倍，然后按512位的长度进行分组（block），可以划分成L份明文分组，我们用Y0，Y1，……，YL-1表示这些明文分组。
> 
> 4）Sha1默认数据流以big endian 方式存放。

分组之后，对所得到的若干分组反复重复处理。对每个明文分组的摘要生成过程如下：

> 1）将512位划分成16个子明文分组，每个子分组32位
> 
> 2）申请5个链接变量a、b、c、d、e，初始为H0、H1、H2、H3、H4
> 
> 3）将16个子分组扩展为80份
> 
> 4）80个子分组进行4轮运算，得到新的a、b、c、d、e值
> 
> 5）新的链接变量与原始链接变量进行求和
> 
> 6）链接变量作为下一个明文分组的初始链接变量
> 
> 7）最后一个分组的5个链接变量就是SHA1摘要

SHA1有如下特性：

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

MD5代码测试：

计算SHA1值的Java代码与计算MD5值的代码基本相同，区别只在于

MessageDigest.getInstance("MD5"); //将"MD5"替换为"SHA1"。

可以将的上面计算MD5值的两个函数`md5(String string)`和`hash(File file)`进行简单的修改，将算法也作为参数传入，`hash(String string, String algorithm)`和`hash(File file, String algorithm)`，就可以动态支持MD5和SHA1两种算法了。

### 4.3.MurmurHash算法 ###

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算法，比安全散列算法快几十倍。

在Java中，有很多地方都使用了MurmurHash，比如Guava包、Jedis包，Cassandra包中都有这种hash算法。

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

package com.wuxiaolong.EncrypteDecrypt;
    
    import com.google.common.base.Charsets;
    import com.google.common.base.Stopwatch;
    import com.google.common.collect.Sets;
    import com.google.common.hash.HashCode;
    import com.google.common.hash.HashFunction;
    import com.google.common.hash.Hashing;
    import org.apache.commons.codec.digest.DigestUtils;
    
    import java.nio.charset.StandardCharsets;
    import java.util.Set;
    
    /** * Description: * 需要jar: * <dependency> * <groupId>com.google.guava</groupId> * <artifactId>guava</artifactId> * <version>23.0</version> * </dependency> * * @author 诸葛小猿 * @date 2020-08-25 */
    public class MurmurHashTest { 
    
    
        public static void main(String[] args) { 
    
            int testCount = 100000;
            String msg = "诸葛小猿";
    
            long totalTime = 0L;
    
            long start = System.currentTimeMillis();
    
            // Hashing.murmur3_32(seed)
            HashFunction murmur3 = Hashing.murmur3_32();
    
            Set<String> set = Sets.newHashSet();
            for (int i = 0; i < testCount; i++) { 
    
                // 计算每一次hash的耗时
                Stopwatch w = Stopwatch.createStarted();
    
                HashCode murmur3HashCode = murmur3.hashString(msg + i, Charsets.UTF_8);
                String murmur3HashCodeStr = murmur3HashCode.toString();
    
                System.out.println(String.format("murmur3's hashCode:%s,length:%s,it consumes:%s", murmur3HashCodeStr, murmur3HashCodeStr.length(), w));
    
                set.add(murmur3HashCodeStr);
            }
    
            long end = System.currentTimeMillis();
    
            totalTime = end - start;
    
            System.out.println("set的元素个数" + set.size());
    
            System.out.println("总耗时" + totalTime);
    
        }
    
    }

部分运行结果：

murmur3's hashCode:a2e96039,length:8,it consumes:2.500 μs
    murmur3's hashCode:12c86afb,length:8,it consumes:2.400 μs
    murmur3's hashCode:ad6ff257,length:8,it consumes:1.200 μs
    murmur3's hashCode:b71c537d,length:8,it consumes:1.200 μs
    murmur3's hashCode:92508a73,length:8,it consumes:1.100 μs
    set的元素个数99998
    总耗时984

这里运行了100000次，但是Set中去重后只有99998个元素，可以使用`Hashing.murmur3_32(seed)`的seed降低元素的重复。

MurmurHash的应用除了上面说的redis，在很多时候都可以应用到，比如短连接服务生成短连接、BloomFilter都可以使用。

## 五、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值使用加密算法加密。

参考文章：

https://blog.csdn.net/qq\_33408113/article/details/82635009

https://www.oschina.net/translate/state-of-hash-functions

https://blog.csdn.net/qq\_24280381/article/details/72024860

https://blog.csdn.net/weiliangliang111/article/details/51457874

关注公众号，输入“**java-summary**”即可获得源码。

完成，收工！

![aHR0cHM6Ly9naXRlZS5jb20vd3V4aWFvbG9uZ2FoL2phdmEtc3VtbWFyeS9yYXcvbWFzdGVyL2ltZy82X3FyY29kZV9jaGUuZ2lm][]

【**传播知识，共享价值**】，感谢小伙伴们的关注和支持，我是【**诸葛小猿**】，一个彷徨中奋斗的互联网民工。

![format_png 1][]

[format_png]: /images/20221123/8002b86f89044a4d9fda008b941299b6.png
[aHR0cHM6Ly9naXRlZS5jb20vd3V4aWFvbG9uZ2FoL2phdmEtc3VtbWFyeS9yYXcvbWFzdGVyL2ltZy82X3FyY29kZV9jaGUuZ2lm]: /images/20221123/63101467e0044a93a8118b0391c6959f.png
[format_png 1]: /images/20221123/168e1f949d1147ff8022c35791839723.png