散列算法(也叫：摘要算法)

一时失言乱红尘 2023-10-05 21:05 64阅读 0赞

**散列算法(也叫：摘要算法)：**

**特点：**  
① 无论输入的消息有多长，计算出来的消息摘要的长度总是固定的。  
② 消息摘要看起来是“随机的”。这些比特看上去是胡乱的杂凑在一起的。  
③ 一般地，只要输入的消息不同，对其进行摘要以后产生的摘要消息也必不相同；但相同的输入必会产生相同的输出。  
④ 消息摘要函数是无陷门的单向函数，即只能进行正向的信息摘要，而无法从摘要中恢复出任何的消息，甚至根本就找不到任何与原信息相关的信息。  
⑤ 好的摘要算法，无法找到两条消息，使它们的摘要相同。

## 1、**MD5加密（128bit）-摘要算法** ##

MD5 ：message-digest algorithm 5（信息-摘要算法）。经常说的“MD5加密”，就是它→信息-摘要算法。

md5其实就是一种算法。可以将一个字符串、文件、压缩包，执行md5后，就可以生成一个固定长度为**128bit**的串。这个串，基本上是唯一的。

所以，有人修改过压缩包后，就会生成新的串，这时就可以拿网站提供的串和新生成的串对比，如果不同，那就是被人修过过了。

**加密**和**摘要**，是不一样的：

**加密后的消息是****完整****的**；具有解密算法，可得到原始数据；

**摘要得到的消息是****不完整****的**；通过摘要的数据，不能得到原始数据。

**S****pringboot自带Md5加密工具类：**org.springframework.util.**DigestUtils**

### 1.1、**MD5的作用** ###

①一致性检验，最上面那个例子。

②数字签名，还是最上面那个例子。只是把md5看成了一个指纹，按了个手印说明[独一无二][Link 1]了。

③安全访问认证，这个就是平时系统设计的问题了。

在用户注册时，会将密码进行md5加密，存到数据库中。这样可以防止那些可以看到数据库数据的人，恶意操作了。

### 1.2、**MD5算法的不足。** ###

现在看来，MD5已经较老，散列长度通常为128位，随着计算机运算能力提高，找到“碰撞”是可能的。因此，在安全要求高的场合不使用MD5。

### 1.3、**MD5原理** ###

MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。

*  **第一步、填充**

如果输入信息的长度(bit)对512求余的结果不等于448，就需要填充使得对512求余的结果等于448。填充的方法是填充一个1和n个0。填充完后，信息的长度就为N\*512+448(bit)；

*  **第二步、记录信息长度**

用64位来存储填充前信息长度。这64位加在第一步结果的后面，这样信息长度就变为N\*512+448+64=(N+1)\*512位。

*  **第三步、装入标准的幻数（四个整数）**

标准的幻数（物理顺序）是（A=(01234567)16，B=(89ABCDEF)16，C=(FEDCBA98)16，D=(76543210)16）。如果在程序中定义应该是（A=0X67452301L，B=0XEFCDAB89L，C=0X98BADCFEL，D=0X10325476L）。有点晕哈，其实想一想就明白了。

首先清楚整型的位表示方法，其次标准文档上要求的是：四个幻数在内存地址上从低到高为：  
A: 01 23 45 67  
B: 89 ab cd ef  
C: fe dc ba 98  
D: 76 54 32 10  
采用小端表示法表示为A=0X67452301L，则在地址中就是A=01 23 45 67

小端法和大端法区别如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ4MjgxNg_size_16_color_FFFFFF_t_70][]

*  **第四步、四轮循环运算**

1.把消息分以512位为一分组进行处理  
2.每一个分组进行4轮变换，以上面所说4个标准的幻数为起始变量进行计算，重新输出4个变量  
3.以这4个变量再进行下一分组的运算，如果已经是最后一个分组，则这4个变量为最后的结果，即MD5值。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ4MjgxNg_size_16_color_FFFFFF_t_70 1][]

**循环的次数是分组的个数（N+1）**  
1）将每一512字节细分成16个小组，每个小组64位（8个字节）  
2）先认识四个线性函数(&是与,|是或,~是非,^是异或)

F(X,Y,Z)=(X&Y)|((~X)&Z)

G(X,Y,Z)=(X&Z)|(Y&(~Z))

H(X,Y,Z)=X^Y^Z

I(X,Y,Z)=Y^(X|(~Z))

3）设Mj表示消息的第j个子分组（从0到15），<<< s表示循环左移s位，则四种操作为：

FF(a,b,c,d,Mj,s,ti)表示a=b+((a+F(b,c,d)+Mj+ti)<<<s)

GG(a,b,c,d,Mj,s,ti)表示a=b+((a+G(b,c,d)+Mj+ti)<<<s)

HH(a,b,c,d,Mj,s,ti)表示a=b+((a+H(b,c,d)+Mj+ti)<<<s)

II(a,b,c,d,Mj,s,ti)表示a=b+((a+I(b,c,d)+Mj+ti)<<<s)

4）四轮运算

第一轮 a=FF(a,b,c,d,M0,7,0xd76aa478)

b=FF(d,a,b,c,M1,12,0xe8c7b756)

c=FF(c,d,a,b,M2,17,0x242070db)

d=FF(b,c,d,a,M3,22,0xc1bdceee)

a=FF(a,b,c,d,M4,7,0xf57c0faf)

b=FF(d,a,b,c,M5,12,0x4787c62a)

c=FF(c,d,a,b,M6,17,0xa8304613)

d=FF(b,c,d,a,M7,22,0xfd469501)

a=FF(a,b,c,d,M8,7,0x698098d8)

b=FF(d,a,b,c,M9,12,0x8b44f7af)

c=FF(c,d,a,b,M10,17,0xffff5bb1)

d=FF(b,c,d,a,M11,22,0x895cd7be)

a=FF(a,b,c,d,M12,7,0x6b901122)

b=FF(d,a,b,c,M13,12,0xfd987193)

c=FF(c,d,a,b,M14,17,0xa679438e)

d=FF(b,c,d,a,M15,22,0x49b40821)

第二轮 a=GG(a,b,c,d,M1,5,0xf61e2562)

b=GG(d,a,b,c,M6,9,0xc040b340)

c=GG(c,d,a,b,M11,14,0x265e5a51)

d=GG(b,c,d,a,M0,20,0xe9b6c7aa)

a=GG(a,b,c,d,M5,5,0xd62f105d)

b=GG(d,a,b,c,M10,9,0x02441453)

c=GG(c,d,a,b,M15,14,0xd8a1e681)

d=GG(b,c,d,a,M4,20,0xe7d3fbc8)

a=GG(a,b,c,d,M9,5,0x21e1cde6)

b=GG(d,a,b,c,M14,9,0xc33707d6)

c=GG(c,d,a,b,M3,14,0xf4d50d87)

d=GG(b,c,d,a,M8,20,0x455a14ed)

a=GG(a,b,c,d,M13,5,0xa9e3e905)

b=GG(d,a,b,c,M2,9,0xfcefa3f8)

c=GG(c,d,a,b,M7,14,0x676f02d9)

d=GG(b,c,d,a,M12,20,0x8d2a4c8a)

第三轮 a=HH(a,b,c,d,M5,4,0xfffa3942)

b=HH(d,a,b,c,M8,11,0x8771f681)

c=HH(c,d,a,b,M11,16,0x6d9d6122)

d=HH(b,c,d,a,M14,23,0xfde5380c)

a=HH(a,b,c,d,M1,4,0xa4beea44)

b=HH(d,a,b,c,M4,11,0x4bdecfa9)

c=HH(c,d,a,b,M7,16,0xf6bb4b60)

d=HH(b,c,d,a,M10,23,0xbebfbc70)

a=HH(a,b,c,d,M13,4,0x289b7ec6)

b=HH(d,a,b,c,M0,11,0xeaa127fa)

c=HH(c,d,a,b,M3,16,0xd4ef3085)

d=HH(b,c,d,a,M6,23,0x04881d05)

a=HH(a,b,c,d,M9,4,0xd9d4d039)

b=HH(d,a,b,c,M12,11,0xe6db99e5)

c=HH(c,d,a,b,M15,16,0x1fa27cf8)

d=HH(b,c,d,a,M2,23,0xc4ac5665)

第四轮 a=II(a,b,c,d,M0,6,0xf4292244)

b=II(d,a,b,c,M7,10,0x432aff97)

c=II(c,d,a,b,M14,15,0xab9423a7)

d=II(b,c,d,a,M5,21,0xfc93a039)

a=II(a,b,c,d,M12,6,0x655b59c3)

b=II(d,a,b,c,M3,10,0x8f0ccc92)

c=II(c,d,a,b,M10,15,0xffeff47d)

d=II(b,c,d,a,M1,21,0x85845dd1)

a=II(a,b,c,d,M8,6,0x6fa87e4f)

b=II(d,a,b,c,M15,10,0xfe2ce6e0)

c=II(c,d,a,b,M6,15,0xa3014314)

d=II(b,c,d,a,M13,21,0x4e0811a1)

a=II(a,b,c,d,M4,6,0xf7537e82)

b=II(d,a,b,c,M11,10,0xbd3af235)

c=II(c,d,a,b,M2,15,0x2ad7d2bb)

d=II(b,c,d,a,M9,21,0xeb86d391)

5）每轮循环后，将A，B，C，D分别加上a，b，c，d，然后进入下一循环。

## 2、**SHA1算法(160bit)-消息摘要** ##

SHA1(安全哈希算法Secure Hash Algorithm)摘要加密算法主要适用于数字签名标准里面定义的数字签名算法。对于长度小于2^64位的消息，SHA1会产生一个160位的消息摘要，由于SHA1算法的雪崩效应（改变一位消息数据会使输出值大幅度变动）与不可逆性，可用于验证数据完整性与消息验证。

SHA1(安全哈希算法Secure Hash Algorithm)主要适用于数字签名标准里面定义的**数字签名算法**。对于长度小于2^64位的消息，SHA1会产生一个

**160位****的消息摘要**。当接收到消息的时候，这 个消息摘要可以用来验证数据的完整性。在传输的过程中，数据很可能会发生变化，那么这时候就会产生不同的消息摘要。SHA1不可以从消息摘要中复原信息， 而两个不同的消息不会产生同样的消息摘要。这样，SHA1就可以验证数据的完整性，所以说SHA1是为了**保证文件完整性**的技术。

## 3、**MAC算法（含有密钥的散列算法）** ##

MAC算法**结合了MD5和SHA算法的优势，并加入密钥的支持**，是一种更为安全的消息摘要算法。

MAC（Message Authentication Code，消息认证码算法）是含有密钥的散列函数算法，兼容了MD和SHA算法的特性，并在此基础上加入了密钥。其次，我们也**常把MAC称为****HMAC**（keyed-Hash Message Authentication Code）。

MAC算法主要集合了MD和SHA两大系列消息摘要算法。

MD系列的算法有HmacMD2、HmacMD4、HmacMD5三种算法；

SHA系列的算法有HmacSHA1、HmacSHA224、HmacSHA256、HmacSHA384、HmacSHA512五种算法。

MAC就是消息验证码（Message Authentication Code）的简称，是一种与密钥相关的单向散列函数，它能够做到验证消息是来自发送者发送的，正确的没有被篡改过的。具体做法是：

1、发送方和接收方事先共享同一个密钥。

2、发送方将发送消息和密钥进行MAC运算，得到MAC值，并把MAC值与消息一同发送给接收方。

3、接收方接收到消息后，将消息部分与事先共享的密钥进行MAC运算，得到MAC值，将MAC值与发送方发送的MAC值进行比较，如果一致，证明消息是来自发送方。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ4MjgxNg_size_16_color_FFFFFF_t_70 2][]

在发送方处，将消息和MAC值一起发送给接收方，接收方将收到的密文消息与事先共享的密钥进行MAC运算，最后和发送方发来的MAC值比对，如果一致，证明消息没有被篡改，是来自发送方的。因为MAC值来自于消息与密钥的运算得到，如果消息一旦有修改，那么MAC值也会不同，且由于密钥是通信双方事先共享的，没有密钥也就没有办法解出MAC值，**MAC算法是与密钥相关的单向散列算法**，根据消息和密钥得到MAC值，由于单向性，在知道散列值（MAC值）的情况下，也没办法解出原始信息，因为单向散列函数产生的散列值是和原始信息完全不同的比特序列，它并不是一种加密，所以无法逆向根据散列值得到原始信息，消息验证码MAC算法就是通过这样保证消息没有被篡改的。

### 3.1、**CBC-MAC和HMAC** ###

消息验证码MAC算法有两种，CBC-MAC和HMAC。

CBC-MAC从名称上看就知道使用到了块密码算法的密文分组连接模式，简单回顾下CBC模式，就是先将密文等分成多个分组数据块，从第一块数据块开始先与一个随机生成的初始化向量IV进行异或运算，运算结果再和密钥进行加密运算，得到第一块分组密文。第二块数据块把前一块数据块的分组密文当作IV，先与其进行异或运算，再和密钥进行加密得到第二块分组密文，这样下去，第n个分组数据块会与第n-1个密文分组进行异或运算，然后和密钥进行加密，得到第n个分组密文，最后将所有分组密文按顺序组合在一起，得到完整的密文。**CBC-MAC**算法就是**将最后一个密文分组的值作为MAC值**。

HMAC算法，哈希消息验证码，很复杂，不过是最常用的，HMAC使用Hash算法做加密基元，加密基元就是指一些基础的加密算法，如Hash，一些复杂的加密算法是根据基础的Hash算法构建出来的，如最上面例子中，对称加密里，使用口令pass和salt加Hash运算得到密钥，Hash算法作为加密基元，每次salt都不同，保证相同的口令可以生成不同的密钥。与HMAC配合使用的散列函数有SHA-1，SHA256和SHA512等，通过Hash函数和密钥得到MAC值，将其与密文一起发送给接收方，待接收方进行验证。

消息验证码MAC算法计算得到MAC值（摘要值），上图举例了使用SHA-1散列函数直接对明文计算MAC值，然后输出到外部文件，和使用SHA-1散列函数加密钥计算MAC值两种方式。

### 3.2、**消息验证码的不足** ###

加密算法对消息进行加密处理，即使消息被中间截获了，如果没有密钥，也很难破解出明文，也就无法篡改，如果直接篡改密文，那么接收方解密出来的明文很可能就是一串乱码或者意义不明的语句，以发现消息被篡改。为了验证消息来自发送者，且是正确的没有被篡改过的，就要配合使用MAC算法。

消息验证码也有无法解决的问题，例如无法向其他人证明该消息是来自对方的，还是自己的。假设A和B双方进行通信，他们之间事先共享密钥，使用消息验证码的方式计算MAC值。对于不在通信方的C来说，假设A收到来自B的消息，计算MAC值正确，可以证明消息正确来自B，但是A无法向C证明该消息是来自B的，因为密钥在A和B之间共享，C可以认为这个消息是来自A自己的，因为A也有密钥，也可以计算出正确的MAC值，所以，**消息验证码的方式，****无法向第三方证明消息的发送方。**

3.3、**MAC系列算法支持表**

<table style="margin-left:-.6pt;width:326.2pt;"> 
 <tbody> 
 <tr> 
 <td style="width:95.25pt;"> 算法 </td> 
 <td style="width:84.5pt;"> 摘要长度 </td> 
 <td style="width:146.45pt;"> 备注 </td> 
 </tr> 
 <tr> 
 <td> HmacMD5 </td> 
 <td> 128 </td> 
 <td style="width:146.45pt;"> JAVA6实现 </td> 
 </tr> 
 <tr> 
 <td> HmacSHA1 </td> 
 <td> 160 </td> 
 <td style="width:146.45pt;"> JAVA6实现 </td> 
 </tr> 
 <tr> 
 <td> HmacSHA256 </td> 
 <td> 256 </td> 
 <td style="width:146.45pt;"> JAVA6实现 </td> 
 </tr> 
 <tr> 
 <td> HmacSHA384 </td> 
 <td> 384 </td> 
 <td style="width:146.45pt;"> JAVA6实现 </td> 
 </tr> 
 <tr> 
 <td> HmacSHA512 </td> 
 <td> 512 </td> 
 <td style="width:146.45pt;"> JAVA6实现 </td> 
 </tr> 
 <tr> 
 <td> HmacMD2 </td> 
 <td> 128 </td> 
 <td style="width:146.45pt;"> BouncyCastle实现 </td> 
 </tr> 
 <tr> 
 <td> HmacMD4 </td> 
 <td> 128 </td> 
 <td style="width:146.45pt;"> BouncyCastle实现 </td> 
 </tr> 
 <tr> 
 <td> HmacSHA224 </td> 
 <td> 224 </td> 
 <td style="width:146.45pt;"> BouncyCastle实现 </td> 
 </tr> 
 </tbody> 
</table>

### 3.4、**ANSI X9.9 MAC算法介绍** ###

1、该算法只使用单倍长密钥，也就是8字节密钥；

2、MAC数据按8字节分组，尾部以字节00补齐；

3、用MAC密钥加密第一个8字节分组，加密结果与第二个8字节分组异或，然后再用MAC密钥加密，重复该步骤，直至所有分组结束，取最后结果的左半部作为MAC。

### 3.5、**ANSI X9.19 MAC算法介绍** ###

1、 ANSI X9.19MAC算法只使用**双倍长密钥**，也就是16字节密钥；

2、MAC数据按8字节分组，表示为D0～Dn，如果Dn不足8字节时，尾部以字节00补齐；

3、 用MAC密钥左半部加密D0，加密结果与D1异或作为下一次的输入。

4、将上一步的加密结果与下一分组异或，然后用MAC密钥左半部加密。

5、直至所有分组结束。

6、 用MAC密钥右半部解密(5)的结果。

7、 用MAC密钥左半部加密(6)的结果。

8、取(7)的结果的左半部作为MAC。

**该算法也是中国银联终端所使用的MAC算法，在实际中，可能有加密机不支持该算法，需要通过ANSI X9.9算法多次调用加密机。**

[Link 1]: https://www.baidu.com/s?wd=%E7%8B%AC%E4%B8%80%E6%97%A0%E4%BA%8C&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ4MjgxNg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210305102703150.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ4MjgxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ4MjgxNg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210305102718988.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ4MjgxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ4MjgxNg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210305102824881.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ4MjgxNg==,size_16,color_FFFFFF,t_70