应用密码学 | SHA-256哈希算法原理详解

SHA-2（Secure Hash Algorithm 2），一种散列函数算法标准，由美国国家安全局研发，由美国国家标准与技术研究院（NIST）在2001年发布，属于SHA算法之一，是SHA-1的后继者。其下又分为六个不同的算法标准，包括：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。

这些变体除了生成摘要的长度、循环运行的次数等一些细微差异之外，基本结构是一致的。本文主要介绍SHA256。

1.概述

对于任意长度的消息，SHA256都会产生一个256位的哈希值，称作消息摘要。

比如原文为：

Do you like me?

经过哈希函数SHA256后的哈希值为：

83e369c7c2e9c0afee6f754505da85e128545ede909608ee33f3431dac7266dc

总体上，SHA256与MD4、MD5以及SHA-1等哈希函数的操作流程类似，主要分为以下两个步骤：

（1）消息预处理

• 补位：对消息进行补位处理，使的最终的长度是512位的倍数
• 分块：以512位为单位对消息进行分块为M^{(1)},\,M^{(2)},...,M^{(N)}

（2）计算哈希值

对消息区块进行逐个处理。从一个固定的初始哈希H^{(0)}开始，进行以下序列的计算：

H^{(i)}=H^{(i-1)}+C_{M^{(i)} }(H^{(i-1)}) \\

其中C是SHA256的压缩函数，+是mod 2^{32}加法（将两个数字加在一起，结果对2^{32}取余）, H^{(i)}是第 i 消息区块的哈希值。

下面对这个过程做详细的讲解。

2、SHA256算法流程详解

2.1、消息预处理

在计算消息的哈希值之前，需要对消息进行预处理，主要是补位和消息分块。

补位：假设消息M的二进制编码长度为l位，首先在消息末尾补上一位"1", 然后再补上k个"0", 其中k为下列方程的最小非负整数：

l+1+k\equiv448\mod 512 \\

然后，再在上述字符串后面补上 l 的二进制表示形式（编码方式为64-bit big-endian integer，见3.4）。

举个例子，设消息为“abc”，则补位过程可以描述如下。

（1）计算abc的二进制编码

原始字符    ASCII码    二进制编码
a          97         01100001
b          98         01100010
c          99         01100011

可知“abc”的二进制编码为为:01100001 01100010 01100011

（2）第一次补位, 首先在消息末尾补上一位"1", 结果为:01100001 01100010 01100011 1;

（3）第二次的补位, 因为l=24, 可以得到k=423, 在第一步补位后的消息后面再补423个"0", 结果如下:

01100001 \, 01100010 \, 01100011 \,1\, \underbrace{00...0}_{423} \\（4）第三次补位，这里补的是原消息"abc"的二进制长度l=24的二进制表示形式（64位）：00...011000, 补完以后的结果如下:

01100001 \, 01100010 \, 01100011 \,1\, \underbrace{00...0}_{423}\,\underbrace{00...011000}_{64} \\

最终补完以后，消息二进制位数长度是512的倍数。

消息分块：将补码处理后的消息以512位为单位分块为:M^{(1)},\,M^{(2)},...,M^{(N)}。其中第i个消息块的前32位表示为:M^{(i)}_0, 第二个32位为:M^{(i)}_1, 以此类推, 最后32位的消息块可表示为:M^{(i)}_{15}

2.2、哈希函数的主循环

SHA256的压缩函数逻辑如下:

• For\, i = 1 \to N (N = 补码后消息块个数)
• 用第 (i - 1)次哈希值来对 a,b,c,d,e,f,g,h进行初始化, 当i=1时, 使用初始化哈希值 H^{(0)} （定义见3.1）, 即:

\begin{align} a&\gets H^{(i-1)}_1\\ b&\gets H^{(i-1)}_2\\ &\vdots\\ h&\gets H^{(i-1)}_8 \end{align} \\

• 应用SHA256的压缩函数来更新a,b,...,h（函数定义见3.2）
• For\, j = 0 \to 63

\begin{align} T_1 &\gets h+\Sigma_1(e)+Ch(e,f,g)+K_j+W_j\\ T_2&\gets \Sigma_0(a)+M_{aj}(a,b,c)\\ h&\gets g\\ g&\gets f\\ f&\gets e\\ e&\gets d+T_1\\ d&\gets c\\ c&\gets b\\ b&\gets a\\ a&\gets T_1+T_2 \end{align} \\

• 计算第i次的哈希值H^{(i)}

\begin{align} H^{(i)}_1 &\gets a + H^{(i-1)}_1\\ H^{(i)}_2 &\gets b+ H^{(i-1)}_2\\ &\vdots\\ H^{(i)}_8 &\gets h+H^{(i-1)}_8 \end{align} \\

• 当 i=N 时停止，得到H^{(N)}=(H^{(N)}_1,H^{(N)}_2,...,H^{(N)}_8)，为最终需要的哈希M。

3. 函数说明

3.1 初始化哈希值

初始哈希值H^{(0)}取自自然数中前面8个素数(2,3,5,7,11,13,17,19)的平方根的小数部分, 并且取前面的32位. 下面举个例子: \sqrt{2}小数部分约为0.414213562373095048, 而其中

0.414213562373095048 \approx 6*16^{-1}+a*16^{-2}+0*16^{-3}+... \\

于是, 质数2的平方根的小数部分取前32位就对应0x6a09e667.

如此类推, 初始哈希值H^{(0)}由以下8个32位的哈希初值构成:

\begin{align} H^{(0)}_1&=6a09e667\\ H^{(0)}_2&=bb67ae85\\ H^{(0)}_3&=3c6ef372\\ H^{(0)}_4&=a54ff53a\\ H^{(0)}_5&=510e527f\\ H^{(0)}_6&=9b05688c\\ H^{(0)}_7&=1f83d9ab\\ H^{(0)}_8&=5be0cd19 \end{align} \\

3.2 公式说明

6个逻辑函数：SHA256算法当中所使用到的6个逻辑函数如下，每个函数都对32位字节进行操作，并输出32位字节。

\begin{align} Ch(x,y,z)&=(x\wedge y)\oplus(\lnot x \wedge z)\\ M_{aj}(x,y,z)&=(x\wedge y)\oplus(x\wedge z)\oplus(y\wedge z)\\ \Sigma_0(x)&=S^2(x)\oplus S^{13}(x)\oplus S^{22}(x)\\ \Sigma_1(x)&=S^6(x)\oplus S^{11}(x) \oplus S^{25}(x)\\ \sigma_0(x)&=S^7(x)\oplus S^{18}(x) \oplus R^3(x)\\ \sigma_1(x)&=S^{17}(x)\oplus S^{19}(x) \oplus R^{10}(x) \end{align} \\

W_j ：扩展消息块W_j,j=0 \to 63通过以下方式进行计算：

\begin{align} W_j&=M^{(i)}_j, \,for\,j=0\to15\\ W_j&= \sigma_1(W_{j-2})+W_{j-7}+\sigma_0(W_{j-15})+W_{j-16},for \,j= 16\to 63\end{align} \\

K_j ：是第 j 个密钥，对应64个常量，取自然数中前面64个素数的立方根的小数部分的前32位, 如果用16进制表示, 则相应的常数序列如下:

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

3.3 运算符说明

• \oplus: 按位异或
• \wedge: 按位与
• \vee: 按位或
• \lnot: 补位
• +: 相加以后对2^{32}求余
• R^n: 右移n位
• S^n: 循环右移n位

以上所有的操作都是针对32位字节。

3.4 大端和小端（Big endian and Little endian）

对于整型、长整型等数据类型，都存在字节排列的高低位顺序问题。

Big endian 认为第一个字节是最高位字节（按照从低地址到高地址的顺序存放数据的高位字节到低位字节）

而 Little endian 则相反，它认为第一个字节是最低位字节（按照从低地址到高地址的顺序存放据的低位字节到高位字节）。

例如，假设从内存地址 0x0000 开始有以下数据：

假设我们去读取一个地址为 0x0000 的四个字节变量.

若字节序为big-endian，则读出结果为0x1234abcd；

若字节序为little-endian，则读出结果为0xcdab3412。

如果我们将0x1234abcd 写入到以 0x0000 开始的内存中，则Little endian 和 Big endian 模式的存放结果如下：

【参考】
[1]知乎-一文读懂SHA256算法原理及其实现
[2]SHA256算法原理详解_随煜而安的专栏-CSDN博客_sha256

—— 更多内容，请访问专栏：【隐私计算】