文章目录

• 0x01 Hash 算法简介
• 0x02 常见的 Hash 算法
• 0x03 MD5
• • 一、算法发展
  • • 1.1 MD2
    • 1.2 MD4
  • 二、MD5 原理
  • • 2.1 数据填充
    • 2.2 添加长度
    • 2.3 初始化变量
    • 2.4 数据处理
    • 2.5 输出
• 0x04 SHA 系列
• • 一、发展历史
  • 二、 SHA2 原理
  • • 2.1 数据填充
    • 2.2 添加长度
    • 2.3 初始化变量
    • 2.4 数据处理
    • 2.5 输出
• 0x05 参考

0x01 Hash 算法简介

​ 单向散列函数算法也称 Hash（哈希）算法，是一种将任意长度的消息压缩到某一固定长度的函数，理论上这是一种单向函数（不可逆向推导），时常用于检验的信息的完整性，数字签名，信息认证检测等。

0x02 常见的 Hash 算法

​ Hash 算法并不是指一个算法，而是指一类算法，而我们常见的 Hash 算法有 MD5、SHA系列。其中MD5 算法已经被证明为是不安全的算法，已经可以被破解了，即可以找到一个明文加密后与原有的密文（即哈希值）一致。

相关的 MD5 破解文章：MD5破解的几种方法 - 知乎 (zhihu.com)

0x03 MD5

​ MD5 信息摘要算法（MD5 Message-Digest Algorithm），一种被广泛使用的密码散列函数，对于输入任意长度的消息都可以产生出一个128位（16字节）的散列值（hash value），用于确保信息传输完整一致。

一、算法发展

​ MD5 由 MD4、MD3、MD2 改进而来，主要增强算法复杂度和不可逆性。MD5 算法因其普遍、稳定、快速的特点，仍广泛应用于普通数据的加密保护领域

1.1 MD2

​ 这个算法首先对信息进行数据补位，使信息的字节长度是16的倍数.

​ 再以16位的检验和作为补充信息追加到原信息的末尾。

​ 最后根据这个新产生的信息计算出一个128位的散列值，MD2 算法由此诞生。

1.2 MD4

​ 在 MD2 基础上发展出 MD4 算法。

​ 同样需要填补信息以确保信息的比特位长度减去448后能被512整除（信息比特位长度mod 512 = 448）。

​ 一个以64位二进制表示的信息的最初长度被添加进来。信息被处理成 512 位damgard/merkle 迭代结构的区块，而且每个区块要通过三个不同步骤的处理。

​ 但很快就被他人发现了其中的不安全性，很快便改进出现了 MD5 。

二、MD5 原理

​ MD5 的加密主要是经过以下步骤：数据填充、添加长度、初始化变量、数据处理、输出

2.1 数据填充

​ 填充消息使其长度与 448 模 512 同余（即长度 ≡ 448 mod 512）。也就是说，填充后的消息长度比 512 的倍数仅小 64 位的数。

​ 即使消息长度本身已经满足上述长度要求，仍然需要填充。填充方法是附一个 1 在消息后面，然后用 0 来进行填充，直到消息的长度与 448 模 512同余。至少填充 1 位，至多填充 512 位。

2.2 添加长度

​ 在第一步的结果之后附上 64 位的消息长度。如果填充前消息的长度大于 2 64 2^{64} 264 ，则只使用其低 64 位。

​ 这时，在添加完填充位和消息长度之后，最终消息的长度正好就是 512 的整数倍了。令 M[0…N-1] 表示最终的消息，其中 N 是 16 的倍数。

2.3 初始化变量

​ 用到4个变量（A，B，C，D）来计算消息摘要。这里A，B，C，D分别都是一个32位的寄存器。这些寄存器以下面的十六进制数值来初始化：

​ A＝01234567h，B＝89abcdefh，C＝fedcba98h，D＝76543210h。

​ 并且在内存中是以低字节在前的形式来存储的

2.4 数据处理

​ 以 512 位分组为单位处理消息，首先定义 4 个辅助函数，每个都是以 3 个 32 位双字（四个字节）作为输入，输出一个32位双字。四个辅助函数如下

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

​ 这4轮变换是对进入主循环的512位消息分组的16个32位字分别进行如下操作：将A，B，C，D的副本a，b，c，d中的3个经F，G，H，I运算后的结果与第4个相加，再加上32位字和一个32位字的加法常数，并将所得之值循环左移若干位，最后将所得结果加上a，b，c，d之一，并回送至A，B，C，D，由此完成一次循环。

​ 从代码上来概括是这样的

for i in range(4):
    for j in range(16):
        F(a,b,c,d,M[j],s[j%4],T[j])# M[j] 是指 512 位的消息被划分为 16 份的分组
    for j in range(16):
        G(a,b,c,d,M[j],s[j%4 + 4],T[j])# T[j] 是指 32 位的加法常数，是一个固定的表，大小位 64 ，即每次使用都不一。
    for j in range(16):
        H(a,b,c,d,M[j],s[j%4 + 8],T[j])# s[j] 是用于移位的，也有一个固定的表，大小为 16 
    for j in range(16):
        I(a,b,c,d,M[j],s[j%4 + 12],T[j])
        
def F(a,b,c,d,Mj,sj,Tj):
    return a + Mj + Tj + (b & c) | ((~a) & c)

def G(a,b,c,d,Mj,sj,Tj):
    return a + Mj + Tj + (b & d) | (c & (~d))
    
def H(a,b,c,d,Mj,sj,Tj):
    return a + Mj + Tj + (b ^ c ^d)
    
def I(a,b,c,d,Mj,sj,Tj):
    return a + Mj + Tj + b ^ (c | (~d))
        

2.5 输出

​ 上面我们每一段的 512 位的消息计算出的结果相加，所得的最终结果即为 MD5 值。

0x04 SHA 系列

​ 安全散列算法（Secure Hash Algorithm）简称 SHA，有 SHA-1、SHA-256、SHA-384和SHA-512 几种，分别产生 160位、256位、384 位和 512 位的散列值。

一、发展历史

​ SHA由美国标准与技术研究所（NIST）设计并于1993年发表，该版本称为SHA-0，由于很快被发现存在安全隐患，1995年发布了SHA-1。

2002年，NIST分别发布了SHA-256、SHA-384、SHA-512，这些算法统称SHA-2。2008年又新增了SHA-224。

由于SHA-1已经不太安全，目前SHA-2各版本已成为主流。

二、 SHA2 原理

​ 以下介绍现在常用的 SHA-512 算法，主要步骤和 MD5 类似有：数据填充、添加长度、初始化变量、数据处理、输出

2.1 数据填充

​ 填充消息使其长度与 896 模 1024 同余（即长度 ≡ 896 mod 1024）。也就是说，填充后的消息长度比 1024 的倍数仅小 128 位的数。

​ 即使消息长度本身已经满足上述长度要求，仍然需要填充。填充方法是附一个 1 在消息后面，然后用 0 来进行填充，直到消息的长度与 896 模 1024 同余。至少填充 1 位，至多填充 1024 位。

2.2 添加长度

​ 在填充完必的消息后，追加 128 位的原始消息长度，因为消息的长度不会超过 2 128 2^{128} 2128 位，所以其长度数据的值不会超过 128 位，这也是为什么上一步中需要取模余 896 的原因。最后的数据一定位1024 的倍数

2.3 初始化变量

​ 将我们将要处理的消息进行分组，由于一定是 1024 的倍数，所以每 1024 分一组，一组内还可以分为 16 小份，每份 64 位，记为 H(i)。(i=0,1,…,15)

​ 和 MD5 一样，SHA-512 都是有着辅助函数，不过 SHA-512 有 6 个辅助函数每一个函数输入为 3 个 64 位的输入。

CH( x, y, z) = (x & y) | ( (~ x) & z)

MAJ( x, y, z) = (x & y) | (x & z) XOR (y & z)

BSIG0(x) = ROTR^28(x) | ROTR^34(x) | ROTR^39(x)

BSIG1(x) = ROTR^14(x) | ROTR^18(x) | ROTR^41(x)

SSIG0(x) = ROTR^1(x) | ROTR^8(x) | SHR^7(x)

SSIG1(x) = ROTR^19(x) | ROTR^61(x) | SHR^6(x)

其中 ROTR 指循环右移，SHR 指循环左移

​ 此外还有 80 个常数序列 K(i) ，值为固定的，还有散列值 H(i) ，共有 8 个，值同样固定且有规律。

2.4 数据处理

​ 处理过程可以理解为：先将我们得到的 16 组 64 位消息进行处理，得到 80 组消息处理过程如下：

for i in range(16,79):
    s0 = SSIG0( W[i-15] ) # 此处的 SSIG0 即为前面的辅助函数
    s1 = SSIG1( W[i-2] ) # w[i] 为我们输入的 64 位的消息
    W[i] = w[i-16] + s0 + w[i-7] + s1

​ 然后利用 8 个散列值 H(i) ，分别赋给 a，b，c，d，e，f，g，h 。

​ 再进行 80 次迭代计算，

for i in range (79):
    t1 = h + BSIG1(e) + CH(e,f,g) + Kt + Wt
    t2 = BSIG0(a) + MAJ(a,b,c)
    h = g
	g = f
	f = e
	e = d + T1
	d = c
	c = b
	b = a
	a = t1 + t2

​ 我们由此可以得到新的 H(i)

h0= h0 + a
h1= h1 + b
h2= h2 + c
h3= h3 + d
h4= h4 + e
h5= h5 + f
h6= h6 + g
h7= h7 + h

​ 此值作为下一组消息的 H(i) 值。

2.5 输出

​ 最终得到的 H(i) 连接为 512 位的 SHA 值。

0x05 参考

看雪：《加密与解密》（第三版）

MD5_百度百科 (baidu.com)

MD系列算法-wx5fae55eb1de50的博客-51CTO博客

MD5算法详解_123-CSDN博客_md5算法

信息摘要算法之四：SHA512算法分析与实现 - Moonan - 博客园 (cnblogs.com)

SHA-512摘要算法（带示例）_u013073067的博客-CSDN博客_sha512算法