密码学基础（一）：摘要算法

1. 什么是摘要算法

摘要算法是通过一系列的计算方法和规则，将输入的任意长度的数据转化成固定长度的返回值，这个值被称为hash值(哈希值)，而这种算法被称为摘要算法、哈希算法、散列算法。

摘要算法有以下特点：

1. 压缩性：任意长度的数据，算出的 MD5 值长度都是固定的（MD5(32)结果长度固定为128位）；

2. 容易计算：从原数据计算出MD5值很容易；

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

4. 强抗碰撞：已知原数据和其MD5值，想找到一个具有相同MD5值的数据（即伪造数据）是非常困难的；

5. 不可逆：无法从结果反推出原文；

当下 RSA （非对称加密）是最安全的加密算法，但是加密的文件过长时，效率很低，所以摘要算法常和非对称加密一起使用。使用摘要算法对原文计算得到一个固定长度的哈希值，再使用私钥对这个哈希值进行加密，接收方先使用同样的摘要算法对原文进行计算得到哈希值，再使用公钥解密被加密的哈希值，如果两个哈希值一致，则表示无中间人攻击的情况下，文件没有被篡改；

2. 主流的摘要算法

MD4、MD5：MD5生成 128 位固定长度的 hash 值，已经被破解
SHA-1：生成 164 位固定长度的 hash 值，已经被破解
SHA-2：生成 224、256、384、512 位的 hash 值
SHA-3：全新的算法和标准

随着生成的长度的增加，碰撞成功的概率会减小，因为只能暴力枚举破解，所以破解的难度也就增大。比如 128 位的 MD5，碰撞概率为 2 的 128 次方分之 1，而512 位则为 2 的 512 次方分之一。

3. 摘要算法的计算流程

以 MD5 为例，MD5 以 512 位对原数据进行分组加密，最后输出 32 个 16 进制，也就是 32x4=128 位，其加密的基本流程如下：

1. 补位

元数据如果位数不满足 Length = 512 * n + 448，也就是 512 取余值为 448 ，则对其补位使其满足规则，可以补 1 和 无限个 0。

在接下来的步骤中，MD5 算法会将元数据按照 512 位/每组，进行分组后加密（后面会讲到）。另外还会会预留 64 位来表示数据的原始信息，比如原始长度等。所以 TotalLength = 512 * n + 448 + 64 = 512x(n+1)，即进入第二步计算的数据长度为 512 byte 的整数倍；

关键点：预留 64 位 + 补位；

2. 设定初始值

MD5 的哈希结果长度为 128 位，按每 32 位分成一组共 4 组。这 4 组结果是由 4 个初始值 A、B、C、D 经过不断演变得到，官方实现中的4个初始值为：

A=0x01234567
B=0x89ABCDEF
C=0xFEDCBA98
D=0x76543210

3. 按照组数循环计算

见下文；

4. 拼接四个随机数

这一步就是单纯的拼接 A、B、C、D，最终输出得到哈希值。

其中，会存在MD5(32)和MD5(16)这些输出结果，其实MD5(16)就是截取MD5(32)的一部分得到的值，如下：

MD5

4. 循环过程

循环分为两种：

1. 主循环：TotalLength / 512 = n。即第一步中补位之后总长度为 512 的整数倍，MD5 算法会进行 n 次主循环；
2. 子循环：每组的 512 个原文会被分为 16 个长度为 32 位（和最初的4个变量长度相同）的变量 。A、B、C、D 别使用这 16 个变量进行 16 次子循环，总共进行 16 * 4 = 64 次子循环；

一个完整的子循环过程为：

子循环

1. 第一步：F 运算

图中的绿色F，代表非线性函数。官方MD5所用到的函数有四种：

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))

在主循环下面64次子循环中，F、G、H、I 交替使用，第一个 16 次使用 F，第二个 16 次使用 G，第三个 16 次使用 H，第四个 16 次使用 I。

对初始变量 A 进行计算时，函数中的三个参数就是另外三个初始变量 B、C、D，可以表示为：

// 以A为例
Value = F(B,C,D);

2. 相加运算

红色的田字代表相加的意思，这一步将要计算的初始变量只和另外三个初始变量经过 F 运算后的结果相加，可以表示为：

// 以 A 为例
Value = A + F(B,C,D)

3.Mi

Mi 是第一步处理后的原文。在第一步中，处理后原文的长度是 512 的整数倍。把原文的每 512 位再分成16等份，命名为 M0~M15，每一等份长度 32。在 64 次子循环中，每 16 次循环，都会交替用到M1~M16之一。

4.Ki

一个常量，在 64 次子循环中，每一次用到的常量都是不同的；

5. 位移运算

黄色的<<< S 表示左移 S 位，S 的值也是常量。

6. 相加运算

这一步直接上面计算的结果和初始变量 B 当前的值进行相加，至于为什么恒定是 B 随机数，暂未深究；

使用公式可以概括为：

// A为例
新A = B + ( (A + F(B,C,D) + Mj + ti) <<< s)
// B 为例
新B = B + ( (B + F(A,C,D) + Mj + ti) <<< s)

即：64 次子循环中的每次循环都有 A、B、C、D 四个随机数参与；

现在起四个新的函数来表示这个过程，定义如下：

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)

所以，第一轮的 16 次子循环表示如下：

// A = B + ( (A + F(B,C,D) + Mj + ti) <<< s)
a = FF(a, b, c, d, groups[0], S11, 0xd76aa478L); /* 1 */
// D = B + ( (D + F(A,B,C) + Mj + ti) <<< s)
d = FF(d, a, b, c, groups[1], S12, 0xe8c7b756L); /* 2 */
// C = B + ( (C + F(D,A,B) + Mj + ti) <<< s)
c = FF(c, d, a, b, groups[2], S13, 0x242070dbL); /* 3 */
// B = B + ( (B + F(C,D,A) + Mj + ti) <<< s)
b = FF(b, c, d, a, groups[3], S14, 0xc1bdceeeL); /* 4 */
--- 四个随机数完成了第一次的变化 --- 

// 新的开始
a = FF(a, b, c, d, groups[4], S11, 0xf57c0fafL); /* 5 */
d = FF(d, a, b, c, groups[5], S12, 0x4787c62aL); /* 6 */
c = FF(c, d, a, b, groups[6], S13, 0xa8304613L); /* 7 */
b = FF(b, c, d, a, groups[7], S14, 0xfd469501L); /* 8 */
a = FF(a, b, c, d, groups[8], S11, 0x698098d8L); /* 9 */
d = FF(d, a, b, c, groups[9], S12, 0x8b44f7afL); /* 10 */
c = FF(c, d, a, b, groups[10], S13, 0xffff5bb1L); /* 11 */
b = FF(b, c, d, a, groups[11], S14, 0x895cd7beL); /* 12 */
a = FF(a, b, c, d, groups[12], S11, 0x6b901122L); /* 13 */
d = FF(d, a, b, c, groups[13], S12, 0xfd987193L); /* 14 */
c = FF(c, d, a, b, groups[14], S13, 0xa679438eL); /* 15 */
b = FF(b, c, d, a, groups[15], S14, 0x49b40821L); /* 16 */

第二轮：

a = GG(a, b, c, d, groups[1], S21, 0xf61e2562L); /* 17 */
d = GG(d, a, b, c, groups[6], S22, 0xc040b340L); /* 18 */
c = GG(c, d, a, b, groups[11], S23, 0x265e5a51L); /* 19 */
b = GG(b, c, d, a, groups[0], S24, 0xe9b6c7aaL); /* 20 */
a = GG(a, b, c, d, groups[5], S21, 0xd62f105dL); /* 21 */
d = GG(d, a, b, c, groups[10], S22, 0x2441453L); /* 22 */
c = GG(c, d, a, b, groups[15], S23, 0xd8a1e681L); /* 23 */
b = GG(b, c, d, a, groups[4], S24, 0xe7d3fbc8L); /* 24 */
a = GG(a, b, c, d, groups[9], S21, 0x21e1cde6L); /* 25 */
d = GG(d, a, b, c, groups[14], S22, 0xc33707d6L); /* 26 */
c = GG(c, d, a, b, groups[3], S23, 0xf4d50d87L); /* 27 */
b = GG(b, c, d, a, groups[8], S24, 0x455a14edL); /* 28 */
a = GG(a, b, c, d, groups[13], S21, 0xa9e3e905L); /* 29 */
d = GG(d, a, b, c, groups[2], S22, 0xfcefa3f8L); /* 30 */
c = GG(c, d, a, b, groups[7], S23, 0x676f02d9L); /* 31 */
b = GG(b, c, d, a, groups[12], S24, 0x8d2a4c8aL); /* 32 */

第三轮：

a = HH(a, b, c, d, groups[5], S31, 0xfffa3942L); /* 33 */
d = HH(d, a, b, c, groups[8], S32, 0x8771f681L); /* 34 */
c = HH(c, d, a, b, groups[11], S33, 0x6d9d6122L); /* 35 */
b = HH(b, c, d, a, groups[14], S34, 0xfde5380cL); /* 36 */
a = HH(a, b, c, d, groups[1], S31, 0xa4beea44L); /* 37 */
d = HH(d, a, b, c, groups[4], S32, 0x4bdecfa9L); /* 38 */
c = HH(c, d, a, b, groups[7], S33, 0xf6bb4b60L); /* 39 */
b = HH(b, c, d, a, groups[10], S34, 0xbebfbc70L); /* 40 */
a = HH(a, b, c, d, groups[13], S31, 0x289b7ec6L); /* 41 */
d = HH(d, a, b, c, groups[0], S32, 0xeaa127faL); /* 42 */
c = HH(c, d, a, b, groups[3], S33, 0xd4ef3085L); /* 43 */
b = HH(b, c, d, a, groups[6], S34, 0x4881d05L); /* 44 */
a = HH(a, b, c, d, groups[9], S31, 0xd9d4d039L); /* 45 */
d = HH(d, a, b, c, groups[12], S32, 0xe6db99e5L); /* 46 */
c = HH(c, d, a, b, groups[15], S33, 0x1fa27cf8L); /* 47 */
b = HH(b, c, d, a, groups[2], S34, 0xc4ac5665L); /* 48 */

第四轮：

a = II(a, b, c, d, groups[0], S41, 0xf4292244L); /* 49 */
d = II(d, a, b, c, groups[7], S42, 0x432aff97L); /* 50 */
c = II(c, d, a, b, groups[14], S43, 0xab9423a7L); /* 51 */
b = II(b, c, d, a, groups[5], S44, 0xfc93a039L); /* 52 */
a = II(a, b, c, d, groups[12], S41, 0x655b59c3L); /* 53 */
d = II(d, a, b, c, groups[3], S42, 0x8f0ccc92L); /* 54 */
c = II(c, d, a, b, groups[10], S43, 0xffeff47dL); /* 55 */
b = II(b, c, d, a, groups[1], S44, 0x85845dd1L); /* 56 */
a = II(a, b, c, d, groups[8], S41, 0x6fa87e4fL); /* 57 */
d = II(d, a, b, c, groups[15], S42, 0xfe2ce6e0L); /* 58 */
c = II(c, d, a, b, groups[6], S43, 0xa3014314L); /* 59 */
b = II(b, c, d, a, groups[13], S44, 0x4e0811a1L); /* 60 */
a = II(a, b, c, d, groups[4], S41, 0xf7537e82L); /* 61 */
d = II(d, a, b, c, groups[11], S42, 0xbd3af235L); /* 62 */
c = II(c, d, a, b, groups[2], S43, 0x2ad7d2bbL); /* 63 */
b = II(b, c, d, a, groups[9], S44, 0xeb86d391L); /* 64 */

如此，64 轮子循环计算完毕得到全新的 A、B、C、D，接下来就是直接组合 ABCD 得到 128 位的哈希值，该值就是摘要算法的结果；

• 摘要算法不可逆的原因：
  如上图所示，F 为 4 个非线性函数中的一个，4 个非线性函数都是由位运算构成，另外还有 <<<s1 左位移运算。64次子循环 * n 次主循环中，A、B、C、D 的每次变化都会发生位运算导致原文丢失。比如0101左移 2 位后为0100` 。因为原文发生了丢失，不管什么算法都无法还原原文，这就是摘要算法不可逆的原因。想要破解摘要算法，只能暴力穷举；

5. 摘要算法在证书中的使用

单纯的签名就是数据的完整性，也就是数据未被篡改。通常签名和数字签名或者数字证书一起出现。

签名

摘要算法可以保证数据的hash值的唯一性，但是攻击者可以修改元数据的同时修改hash值，所以摘要算法+RSA构成了数字证书体系(个人)，使用私钥加密hash值并将公钥附加在证书中，这样就可以避免攻击者对元数据和hash值的同时篡改。

自签名证书

但是个人公私钥毕竟容易被攻击和窃取，为了防范这种情况，CA机构的介入让(摘要算法+RSA+CA)构成了CA证书体系。一般的电脑系统以及主流的工具(比如浏览器)都会和CA机构合作，也就是嵌入了CA机构的公钥，理论上只要CA机构的私钥不被窃取，这一套加密规则就是安全的。而apple中的签名机制则是根据自己的发布模式进行了强化，形成了自己的一套签名加密规则。所以在向apple申请证书时发送给apple的csr文件就包含个人信息和个人公钥：

csr文件

CA机构的作用可以说的更详细一点，CA机构可以依靠自己的权威形象给自己站台，另外一个CA机构可以给个人/机构站台。一般来讲，个人奖自己的公钥和信息发送给CA机构，CA机构用自己的私钥进行签名，也就是用自己的私钥对个人/机构的信息和公钥进行加密之后发布数字证书，数字证书里面包含：个人/机构的信息、个人/机构的公钥、CA机构的信息、加密的规则的一些信息

CA数字证书

6. 使用摘要算法来验证数据完整性

这种情况下，早期可能会用于接口传输时，入参的一致性对比，但是现在基本不会使用到了，要使用也会有一套相对复杂的规则来保证安全。比较常见而且现在仍然在被广泛使用的一个场景是：文件下载时验证文件的完整性。

官方对自己文件进行MD5计算并将对应的MD5值公布到官网上，用户下载后只要对自己下载的文件进行MD5操作后校验这两个hash值，就知道自己下载的文件是否安全。这种情况下，只有攻击者攻克了官方网站并且让用户下载到了攻击者指定的文件，且用户在校验MD5码时官网还处于未恢复的情况下，攻击才会有效，这基本不可能，也没有太大意义。

MD5验证文件完整性

7. hash表

hash表一般用于数据存储，这也是对摘要算法的碰撞处理的一个典型。

8. 摘要算法用于秘钥的加密传输

早期传输用户的密码，或者服务器保存用户密码时，会将用户的密码经过MD5加盐，以密文的形式保存在数据库中，这样可以保证在不知道加盐规则的情况下，即使数据库被攻击，攻击者拿到的也只是密文，无法解密出明文，即使知道了加盐规则，仍然需要暴力加盐枚举。另外，有良心的服务商也不愿意去存储用户的密码，所以这种模式下的服务商，不大会提供找回原密码的服务，只会提供重置密码服务，因为MD5的不可逆性，他自己也不知道原密码是啥。

9. 被破解了还能用吗

学习一个东西就要知道其使用场景。另外，理论上没有绝对安全的加密规则。破解的本质就是成本和代价的权衡。

如上所讲，摘要算法的破解只有在秘钥传输上有较大的意义，通过暴力枚举之后获取到对应的密码以帮助自己获利。在安全要求较高的金融行业，已经不使用MD5加密相关信息了，就算是普通行业，仍然可以通过MD5加盐、MD5后再次MD5、使用相对安全的SHA-2来实现加密。综上，摘要算法虽然已经被破解，但是仍然可以在很多地方发挥作用，尤其是数字证书上。

10. 总结

1. 采取会丢失原文的算法得到长度固定结果，只能暴力穷举；
2. 证书体系中，因为非对称加密效率不高，通常会使用私钥对原文的摘要进行 RSA 加密，接收者使用公钥解密之后和原文的摘要进行对比，确认信息是否被篡改；

摘要算法计算流程总结：

1. 对原文填充且预留出 64 位来记录原文的信息，最终原本长度变成 512 位的整数倍；
2. 原文长度为 512 的 n 倍则需要进行 n 次主循环；
3. 给定 4 个初始变量，长度为 8个 16进制位共 128 位；
4. 将当前主循环的 512 位原文按照 128 位切分为 16 个随机数，长度和 4 个初始变量相同；
5. 4 个初始变量交替开启子循环，A = B + ( (A + F(B,C,D) + Mj + ti) <<< s)。子循环总共 64 次，且每隔 16 次子循环更换一次 F 函数，总共 4 个 F 函数；
6. 所有主循环结束后将最终的 A、B、C、D 相加得到 128 位的哈希值；
7. 如果是 MD5(16)，则取中间的 64 位作为结果；