SHA256算法原理

1. SHA256算法简介

1.1 起源

HASH

​ 要说SHA算法，我们需要先知道hash的准确定义。wiki的定义如下：hash（散列），又称散列算法，哈希函数。是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。通俗的来讲，哈希值就是将一些字符串、数字文件等经过一系列的操作产生一个唯一不变的、等长的数据摘要。

SHA256

​ 而SHA256（security hash algorithm 256），就是由美国NSA设计的SHA-2（第二代安全散列算法，比特币中使用较多，而更新的以太坊使用第三代的安全散列算法）的成员之一。SHA-2根据不同的算法标准分为了：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256等算法。这些算法除了生成摘要的长度 、循环运行的次数等一些微小差异外，算法的基本结构是一致的。

2. SHA256算法原理

2.1 原理基础

​ 为了更好的理解SHA256算法，我们将算法的三个核心模块单独讲解。

2.1.1 常量初始化

​ SHA256算法将自然数中前8个质数（2,3,5,7,11,13,17,19）的平方根的小数部分去前32位来生成8个哈希初值。我们以第一个质数2为例，具体步骤如下：

  1. 对2取平方根 $\sqrt2$ 得到近似小数 $1.414213562373095048$ ；
  2. 取 $\sqrt2$ 的小数部分转为16进制约为 $6 * 16{-1} + A * 16{-2} + 0 * 16^{-3} + ...$ ；
  3. 整理得第一个哈希初值为 $0x6a09e667$ ；

依照上述方法可得八个哈希初值如下：
$$
h0 := 0x6a09e667 \
h1 := 0xbb67ae85 \
h2 := 0x3c6ef372 \
h3 := 0xa54ff53a \
h4 := 0x510e527f \
h5 := 0x9b05688c \
h6 := 0x1f83d9ab \
h7 := 0x5be0cd19
$$
​ 另外，SHA256算法使用类似的方法，取自然数的前64个质数经过立方根的小数部分，然后取前32位作为64个常量。

得到的内容如下：
$$
428a2f98\quad 71374491\quad b5c0fbcf\quad e9b5dba5\
3956c25b\quad 59f111f1\quad 923f82a4\quad ab1c5ed5\
d807aa98\quad 12835b01\quad 243185be\quad 550c7dc3\
72be5d74\quad 80deb1fe\quad 9bdc06a7\quad c19bf174\
e49b69c1\quad efbe4786\quad 0fc19dc6\quad 240ca1cc\
2de92c6f\quad 4a7484aa\quad 5cb0a9dc\quad 76f988da\
983e5152\quad a831c66d\quad b00327c8\quad bf597fc7\
c6e00bf3\quad d5a79147\quad 06ca6351\quad 14292967\
27b70a85\quad 2e1b2138\quad 4d2c6dfc\quad 53380d13\
650a7354\quad 766a0abb\quad 81c2c92e\quad 92722c85\
a2bfe8a1\quad a81a664b\quad c24b8b70\quad c76c51a3\
d192e819\quad d6990624\quad f40e3585\quad 106aa070\
19a4c116\quad 1e376c08\quad 2748774c\quad 34b0bcb5\
391c0cb3\quad 4ed8aa4a\quad 5b9cca4f\quad 682e6ff3\
748f82ee\quad 78a5636f\quad 84c87814\quad 8cc70208\
90befffa\quad a4506ceb\quad bef9a3f7\quad c67178f2
$$

2.1.2 信息预处理

​ 为了保证无论是多长的数据最终生成的哈希值的长度相同，SHA256算法通过预处理在想要hash的数据后补充信息，使其满足一定的结构，具体补充的规则如下：

  1. 附加填充bit

    ​ 我们知道SHA256生成的哈希值是一个64位的16进制数，为了保证得到的哈希值位数准确，我们需要对数据进行填充，使其长度在对512取模后的余数为448.具体填充过程如下：

    • 补充第一个bit为1
    • 检查长度是否满足对512取模后余数为448
    • 不满足则补充0，返回第二步
    • 满足则停止

    由上面的步骤我们可知道，第一步补充的bit位1是必须的，即使数据本身长度满足对512取模的448也一样，这个时候，数据就需要补充512位来满足条件；因此，填充的bit位最少1位，最多512位。

  2. 附加长度值

    有一个问题不知道你是否发现？为什么要求余数是448？有什么含义么？

答案就是：515-448=64；没错，SHA256算法在完成填充后的数据后附加了64位的值来存储原始数据长度。也因此我们可以知道，SHA256算法可以计算的数据长度并不是无限的，其数据长度必须要小于 $2^{64}$ 。当然，这个数据也不小。

2.1.3逻辑运算函数和消息摘要

逻辑运算函数

​ SHA256算法是个非常复杂的算法，是在的说，时至本文写作之时，我也没有完全吃透，因此，我尽量用清晰的、准确的语言来描述这个算法的逻辑原理。

​ SHA256算法具体用到了如下的函数，我们先列出了，具体的使用会在下方标注。
$$
Ch(x,y,z)=(x∧y)⊕(¬x∧z)\
Ma(x,y,z)=(x∧y)⊕(x∧z)⊕(y∧z)\
Σ_0(x)=S2(x)⊕S{13}(x)⊕S{22}(x)\
Σ_1(x)=S6(x)⊕S{11}(x)⊕S{25}(x)\
σ_0(x)=S7(x)⊕S{18}(x)⊕R3(x)\
σ_1(x)=S{17}(x)⊕S{19}(x)⊕R{10}(x)
$$
其中符号∧表示按位与，符号¬表示按位补，符号⊕表示按位异或，符号S^nb表示循环右移n个bit，符号R^n表示右移n个bit。

消息摘要

​ 在进行逻辑运算之前，SHA需要先将消息分解成512-bit大小的块。

image-20210612173140632

如图所示，假设消息Message可以分为n个等大小的512-bit的块，那么整个逻辑运算迭代n次后即可得最终的哈希值，即256bit的数字摘要。大致流程如下：

  1. 初始时，有一个256bit的初始摘要$h_0$，设置i=1；
  2. 将$h_$经过第i个数据块运算，得到第一次迭代的结果$h_i$。
  3. 重复第二步直到i=n；

而在一个块内，是如何形成hi呢？其具体流程如下图所示。

在SHA256算法中的最小运算单元为“字（word）”，长为32位；因此一个数据块被分为8个字，每个字都有一个哈希初值，通过与数据块进行 映射函数的运算得到哈希值，这里的8个哈希初值也就是之前提到的8个初值。

image-20210612173208052

image-20210612173236391

2.2 逻辑运算

这里的逻辑运算指的是在每一次迭代中进行的工作，也就是映射函数 $Map(H_)=H_i$ 完成的具体工作。

2.2.1 构造64个字（word）

前面我们已经提到，一个字为32位。对于每一个块，我们可以将其分解成16个32-bit的字（在这里我们记住在SHA256算法中，这16个字为大端），我们假设这16个字分别为w[0],w[1], … ,w[15]。这便是标题所示的64个字的前16个。后面的48个字由如下公式得到：
$$
w_t=σ_1(w_)+w_+σ_0(w_)+w_
$$

2.2.2 进行64次循环

映射函数 $Map(H_)=H_i$ 包含了64次加密循环。

也就是说完成64次加密循环后即完成了一个数据块的迭代。

每次加密循环的详细流程如下图：

image-20210612173422296

如图所示：其中ABCDEFGH这8个字在按照一定的规律自行更新，侧面的蓝色方块为之前已经叙述的非线性逻辑函数。红色方块代表$mod 2^{32} addition$ ，即将两个参数相加取模。8个字的初始值分别为哈希初值，kt为第t个密钥，即我们上文提到的64个常量。Wt为本区块产生的第t个字。因为原消息被切割成n个512bit的数据块，对每一个区块，产生64个字，通过重复运行循环n次对ABCDEFGH这八个字循环加密。最后一次循环所产生的八个字合起来即是第i个块对应到的散列字符串Hi。

Q.E.D.

If you don't come, I will snow.