正经夜光杯

这个屌丝很懒，什么也没留下！

热门标签

sm3算法基本原理

作者：正经夜光杯 | 2024-07-11 10:51:39

踩

sm3

sm3算法是一种消息摘要算法，与我们熟知的MD5、SHA1、SHA256算法一样，也可称为Hash算法。它的主要特征就是加密过程不需要密钥，并且加密后无法还原为明文，也即是不可逆的。

sm3算法的用途，一般用于生成消息以及文件的数字签名，以保证信息的完整性和不可否认性。

1. 算法执行过程

sm3算法的执行过程共有五部分，分别是：消息填充、消息分组、消息扩展、迭代压缩、输出结果。sm3算法是一个分组加密算法，即加密过程需要先将消息按每512比特（64字节）进行分组，然后对每组都进行消息扩展、消息压缩，执行到最后一组时进行消息填充，再压缩，最后输出结果，其执行过程如下图：

SM3执行过程

2. 初始IV

sm3使用8个字寄存器来存储每一轮迭代压缩的过程数据及结果，压缩过程中也会使用到这8个寄存器，规范中这8个寄存器分别定义为A,B,C,D,E,F,G,H，我们可以理解成8个unsigned int变量。

初始IV，即在算法开始执行前，8个字寄存器的初始值，其值为：

$IV=7380166f\ \ 4914b2b9\ \ 172442d7\ \ da8a0600\ \ a96f30bc\ \ 163138aa\ \ e38dee4d\ \ b0fb0e4e$

使用代码来表示就是：

unsigned int A = 0x7380166f;
unsigned int B = 0x4914b2b9;
unsigned int C = 0x172442d7;
unsigned int D = 0xda8a0600;
unsigned int E = 0xa96f30bc;
unsigned int F = 0x163138aa;
unsigned int G = 0xe38dee4d;
unsigned int H = 0xb0fb0e4e;
1
2
3
4
5
6
7
8

然后后续的迭代压缩过程中，会使用和修改这8个寄存器的值。计算完成后，这8个寄存器的值就是输出结果。

3. 消息填充

3.1 规范原文

假设消息m的长度为l比特。首先将比特“1”添加到消息的末尾，再添加k 个“0”，k是满足 $\equiv 448 \pmod {512}$ 的最小的非负整数。然后再添加一个64位比特串，该比特串是长度l的二进制表示。填充后的消息m′ 的比特长度为512的倍数。

例如：对消息01100001 01100010 01100011，其长度l=24，经填充得到比特串：
$01100001\quad101100010\quad101100011\quad1\quad\overbrace{00\cdots00}^{423比特}\quad\overbrace{\underbrace{00\cdots011000}_{l的二进制表示}}^{64比特}$

3.2 规范理解

可以理解为，不论你的消息多长，先添加一个值为1的比特到消息的最后，然后加k个0，最后添加64位比特串，使得消息的总长度是512比特的倍数。

通常的计算机内存储的数据，一般都是以字节为单位，不会到比特，所以在填充这个值为1的比特前，消息的比特长度都是8的倍数（因为一字节=8比特），而消息的最后添加的是64位比特串，也是8的倍数，如果按字节填充规则来算，例如：对消息01100001 01100010 01100011（十六进制表示就是616263），其长度l=24（3字节），经填充后，得到的比特串，按十六进制表示就是：

61626380 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000018
1
2

怎么得到的这个结果呢，前面那个消息原文十六进制表示是616263，这个不用说了吧，然后看后面立刻添加的值为1的比特，如果用字节来表示呢，就是一个字节的最高比特位置为1，十六进制表示就是0x80吧，消息的长度是24比特，十六进制表示就是0x18，规范上说这个长度是用一个64位来存储，也就是uint64_t来表示这个长度，最终就是00000000 00000018，那么这个消息现在先表示为

61626380 N个0x00 00000000 00000018
1

剩下就是要计算有多少个0x00了，消息的总长度必须是512比特的倍数，就是64字节的倍数。这样就很容易计算出来： $N = 64 - 3 - 1 - 8 = 52$ 。

4. 消息分组

消息分组，就是将我们需要计算sm3摘要值的消息按每512比特（也即64字节）为一组进行拆分，每64字节为一轮进行消息扩展、迭代压缩，这样循环往复，直到最后一组执行完，然后A,B,C,D,E,F,G,H这8个寄存器里的值就是sm3的摘要值。

在进行消息分组前，需要先进行消息填充。我们在写算法实现的时候，不可能一次性把要计算的消息全部都出来，然后进行消息填充，再分组，再一轮一轮的计算，这样如果我们计算一个很大的文件，比如十几GB文件的sm3的摘要值，那内存会吃不消的，算法性能也不高。

所以一般做法是，每读满64字节就计算一轮，然后把已计算的消息长度保存起来，到最后一字节消息读完后，再执行消息填充，这样算法性能高，也不用担心内存会爆。

因为消息的填充规则里，只用到了消息的总长度，没有用到其它内容，所以我们只要暂存消息的总长度就可以进行消息的填充

5. 消息扩展

5.1 规范原文

将消息分组 $B^{(i)}$ 按以下方法扩展生成132个字 $W_0, W_1, · · · , W_{67}, W_0' , W_1', · · · , W_{63}'$ ，用于压缩函
数CF ：

a) 将消息分组 $B^{(i)}$ 划分为16个字 $W_0 , W_1 , · · · , W_{15}$ 。
b) $FOR\ j= 16\ TO\ 67$
$W_j \gets P_1 (W_{j−16} \oplus W_{j−9} \oplus (W_{j−3} \lll 15)) \oplus (W_{j−13} \lll 7) ⊕ W_{j−6}$
$EN D FOR$
c) $FOR\ j=0\ TO\ 63$
$W_j' = W_j \oplus W_{j+4}$
$EN D FOR$

5.2 大小端

在解析这个规范之前的，不得不先复习一下大小端的问题，因为W和 $W^{'}$ 都是字，规范中字都是大端存储的，所以先复习一下。

以unsigned int v = 0x12345678为例，如果我们用unsigned char buf[4]来表示v这个数字的话，分别来看大端和小端存储有什么不同，先来看大端模式：

大端模式： 大端模式是低地址存储高位，v的高位是0x12，buf的低地址是buf[0]，那么最终存储结果就是

低地址--  buf[0] = 0x12  --高　位
　｜　    buf[1] = 0x34    　｜　
　｜　    buf[2] = 0x56    　｜　
高地址--  buf[3] = 0x78  --低　位
1
2
3
4

小端模式： 小端模式是低地址存储低位，v的低位是0x78，buf的低地址是buf[0]，那么最终存储结果就是

低地址--  buf[0] = 0x78  --低　位
　｜　    buf[1] = 0x56    　｜　
　｜　    buf[2] = 0x34    　｜　
高地址--  buf[3] = 0x12  --高　位
1
2
3
4

5.3 步骤a

将消息分组 $B^{(i)}$ 划分为16个字 $W_0 , W_1 , · · · , W_{15}$

这时我们再回过头来看规范中的步骤a，就比较清晰了，其实就是将一个消息分组（64字节）分别按4字节、4字节…4字节这样划分到 $W_0 , W_1 , · · · , W_{15}$ 这16个字中。而每4字节，又是按大端的模式存储到W中。

5.4 步骤b

$FOR\ j= 16\ TO\ 67$
　　 $W_j \gets P_1 (W_{j−16} \oplus W_{j−9} \oplus (W_{j−3} \lll 15)) \oplus (W_{j−13} \lll 7) ⊕ W_{j−6}$
$EN D FOR$

这里的涉及的符号，先作一个解析：

$\oplus$ ：异或运算
$\lll$ ：循环左移运算
$P_1(X) = X \oplus (X \lll 15) \oplus (X \lll 23)$

那么步骤b的伪代码就比较简单了，我们令GM_SM3_ROTL表示循环左移，那么伪代码如下：

for(int j = 16; j < 68; j++) {
    tmp = W[j - 16] ^ W[j - 9] ^ GM_SM3_ROTL(W[j - 3], 15);
    p1 = tmp ^ GM_SM3_ROTL(tmp, 15) ^ GM_SM3_ROTL(tmp, 23);
    W[j] = p1 ^ GM_SM3_ROTL(W[j - 13], 7) ^ W[j - 6];
}
1
2
3
4
5

5.5 步骤c

$FOR\ j=0\ TO\ 63$
　　 $W_j' = W_j \oplus W_{j+4}$
$EN D FOR$

步骤c没什么好说的，超简单，我们直接上伪代码：

unsigned int W1[64] = {0};

for(int j = 0; j < 64; j++) {
    W1[j] = W[j] ^ W[j + 4];
}
1
2
3
4
5

这里的W[j+4]是不会溢出的，因为前面步骤b的时候，我们已经计算到W[67]了。

6. 迭代压缩

前面我们说了，要计算一个消息 $m$ 的摘要，先要将消息进行填充得到 $m^{'}$ ，然后将 $m^{'}$ 按每64字节为一组进行分组，每一组都执行消息扩展以及迭代压缩，最终得到摘要值。

有了这个背景前提，我们再来理解一下规范的原文。

6.1 规范原文

将填充后的消息 $m^{'}$ 按512比特进行分组： $B^{(0)}\ B^{(1)}\ \cdots\ B^{(n−1)}$

对 $m^{'}$ 按下列方式迭代：

$FOR\ i=0\ TO\ n-1$
　　 $V^{(i+1)} = CF(V^{(i)},\ B^{(i)})$
$EN D FOR$

其中CF是压缩函数， $V^{(0)}$ 为256比特初始值IV， $B^{(i)}$ 为填充后的消息分组，迭代压缩的结果为 $V^{(n)}$ 。

n：这里的n，就是填充后的消息 $m^{'}$ 的总字节长度除以 64。n表示的就是一共要迭代多少轮
V：其实就是用来计算过程中暂存A,B,C,D,E,F,G,H这8个字寄存器的，每执行完一轮后，将它们存储在V里面
$V^{(0)}$ ： 表示的就是迭代压缩前V的初始值，也即我们第2章节提到的初始IV

6.2 CF压缩函数

令A,B,C,D,E,F,G,H为字寄存器， $SS_1,SS_2,TT_1,TT_2$ 为中间变量，压缩函数 $V^{i+1}\ =\ CF(V^{(i)},\ B^{(i)}),\ 0 \leq i \leq n−1$ 。计算过程描述如下：

\begin{aligned} A B C D E F G H \leftarrow V^{(i)} \\ F O R j = 0 T O 63 \\ S S_{1} \leftarrow ((A ⋘ 12) + E + (T_{j} ⋘ j)) ⋘ 7 \\ S S_{2} \leftarrow S S_{1} \oplus (A ⋘ 12) \\ T T_{1} \leftarrow F F_{j} (A, B, C) + D + S S_{2} + W_{j}^{'} \\ T T_{2} \leftarrow G G_{j} (E, F, G) + H + S S_{1} + W_{j} \\ D \leftarrow C \\ C \leftarrow B ⋘ 9 \\ B \leftarrow A \\ A \leftarrow T T_{1} \\ H \leftarrow G \\ G \leftarrow F ⋘ 19 \\ F \leftarrow E \\ E \leftarrow P_{0} (T T_{2}) \\ E N D F O R \\ V^{(i + 1)} \leftarrow A B C D E F G H \oplus V^{(i)} \end{aligned}

$\begin{aligned} &ABCDEFGH \gets V^{(i)} \\ &FOR\ j=0\ TO\ 63 \\ &\quad SS_1 \gets ((A \lll 12) + E + (T_j \lll j)) \lll 7 \\ &\quad SS_2 \gets SS_1 \oplus (A \lll 12) \\ &\quad TT_1 \gets FF_j (A, B, C) + D + SS_2 + W_j' \\ &\quad TT_2 \gets GG_j (E, F, G) + H + SS_1 + W_j \\ &\quad D \gets C \\ &\quad C \gets B \lll 9 \\ &\quad B \gets A \\ &\quad A \gets TT_1 \\ &\quad H \gets G \\ &\quad G \gets F \lll 19 \\ &\quad F \gets E \\ &\quad E \gets P_0 (TT_2) \\ &ENDFOR \\ &V^{(i+1)} \gets ABCDEFGH \oplus V^{(i)} \end{aligned}$

A BC D EFG H \leftarrow V^{(i)} FOR j = 0 TO 63 S S_{1} \leftarrow ((A ⋘ 12) + E + (T_{j} ⋘ j)) ⋘ 7 S S_{2} \leftarrow S S_{1} \oplus (A ⋘ 12) T T_{1} \leftarrow F F_{j} (A, B, C) + D + S S_{2} + W_{j}^{'} T T_{2} \leftarrow G G_{j} (E, F, G) + H + S S_{1} + W_{j} D \leftarrow C C \leftarrow B ⋘ 9 B \leftarrow A A \leftarrow T T_{1} H \leftarrow G G \leftarrow F ⋘ 19 F \leftarrow E E \leftarrow P_{0} (T T_{2}) EN D FOR V^{(i + 1)} \leftarrow A BC D EFG H \oplus V^{(i)}

这里主要讲一下压缩函数中涉及到的一些变量和公式的含义：

$T_j$ ： 是一个常量，当 $\leq j \leq 15$ 时，它的值是0x79cc4519，当 $\leq j \leq 63$ 时，它的值是0x7a879d8a
$FF_j$ ： 这是一个函数，它在规范文档定义如下：
$FF_j(X,Y,Z)=$
${\begin{cases} X \oplus Y \oplus Z & 0 \leq j \leq 15 \\ (X \land Y) \lor (X \land Z) \lor (Y \land Z) & 16 \leq j \leq 63 \end{cases}$
FFj(X,Y,Z)={X⊕Y⊕Z(X∧Y)∨(X∧Z)∨(Y∧Z)0≤j≤1516≤j≤63
FF这个函数的定义理解起来比较简单，函数的入参有X,Y,Z三个：
- 当 $\leq j \leq 15$ 时： 函数的返回值为 X ^ Y ^Z，^是异或运算
- 当 $\leq j \leq 63$ 时： 函数的返回值为(X & Y) | (X & Z) | (Y & Z)，&是与运算，|是或运算
$GG_j$ ： 这是一个函数，它在规范文档定义如下：
$GG_j(X,Y,Z)=$
${\begin{cases} X \oplus Y \oplus Z & 0 \leq j \leq 15 \\ (X \land Y) \lor (\neg X \land Z) & 16 \leq j \leq 63 \end{cases}$
GGj(X,Y,Z)={X⊕Y⊕Z(X∧Y)∨(¬X∧Z)0≤j≤1516≤j≤63
与FF函数类似，GG这个函数的入参也是X,Y,Z三个：
- 当 $\leq j \leq 15$ 时： 函数的返回值为 X ^ Y ^Z，^是异或运算
- 当 $\leq j \leq 63$ 时： 函数的返回值为(X & Y) | ((~X) & Z)，&是与运算，|是或运算，~是非运算
$P_0$ ： 它是一个置换函数，与我们前面讲到的 $P_1$ 类似，它的函数定义如下：
$P_0(X)=X \oplus (X \lll 9) \oplus (X \lll 17)$
令GM_SM3_ROTL表示循环左移，那么 $P_0$ 的伪代码如下：
```
function P0(X) {
	return X ^ GM_SM3_ROTL(X, 9) ^ GM_SM3_ROTL(X, 17);
}
1
2
3
```

至此sm3实现的算法原理，我们就讲完了，通篇读完之后，再回头来看sm3的规范文档，理解起来就不难了，有信心的同学，可对照本文来实现一下吧，如有疑问，欢迎加入QQ群进行提问：859626351

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/正经夜光杯/article/detail/809867