最近研究非对称加密算法的实现，尽管RSA世界通行，但是SM2毕竟是国标，不重视不行。结果发现，SM2中的杂凑需要用SM3，所以不得不先搞懂SM3。
网上SM3的介绍资料和源码很多，回过头来看，站在我自己的角度，感觉有必要记录下自己的理解，或许更能适合某些与我思维习惯比较相似的读者。
一、SM3原理
哈希（hash）/杂凑/散列的用途广泛，这里不赘述。国标SM3的权威文件可以到国家密码管理局官网下载SM3密码杂凑算法
pdf文件，里面用的标准名称是杂凑。
一次SM3杂凑运算的输入可以视为二进制位串，输出为256位。理论上，输入的二进制位串长度可以是8字节长的无符号整数（因为填充时给的存放空间就是8个字节，见后面关于填充的描述），但实际应用中通常都是8的倍数，因为计算机用字节作为寻址的最小单位。SM3的运行结构和方式与国际上通行的SHA256很像，可以比照着学习。
主要的计算流程是：
1. 输入消息分组：
将输入的二进制串（设位长为L）按顺序分成 L//512（//代表整除）组，每组512位（64字节）。
2. 填充：
对于输入的二进制串分组后的剩余位串（长度应为L % 512，%代表取模，可以为0），通过填充形成1组或2组，每组还是512位。
填充的规则是先在消息后面补一个1，再填充若干个0（可以是0个），然后填充用8个字节表示的L值（这8个字节存放时高字节在前，即所谓的大端模式）。可见，填充的关键是确定补多少个0。
因为最后的64位（8个字节）要用来存L值，所以扩展的第1组，如果存放剩余位串，再加上必须补的一个1之后，剩余空间还可以放下8个字节（64位）的L值，那么只需填充成1组。否则，需要填充为2组：第1组剩余位数全部填充0，直到填满512位；第2组前最56字节填充0，后8字节存放L值。
简单算一下，512位 - 64位=448位，再减去必须补的一个1，为447位。因此，当L % 512 <= 447时，只需扩展为1组；否则需2组。当以字节作为最小输入粒度时，剩余数据字节长度大于等于56时则需填充成2组。
【例1】对消息01100001 01100010 01100011，其长度L=24，经填充得到二进制串为：
【例2】对消息11000001…… 01001111，其长度L=480，经填充得到2组二进制串为：
需要说明的是从国家密码管理局官网上下载的文档，也是存在错漏的。比如下图中红色框标识的8按照填充规则显然应该是0，实际程序运行测试也证明了这一点。
3. 迭代调用CF压缩函数：
对于上面所有组，依次调用CF压缩函数。CF压缩函数的输入参数为：8个32位压缩寄存器的值V，和512位的消息二进制串；输出为256位二进制串。8个32位压缩寄存器分别用A、B、C、D、E、F、G、H表示，合在一起256位，用V表示。前次CF压缩的输出即下次CF压缩的V，因此称为迭代调用。
第一次CF调用的V值由算法给定（即IV）。最后一次CF函数的输出即得到的最终hash结果。
那么，CF压缩是怎么做的呢？
首先，CF压缩函数从输入的512位消息二进制位串扩展生成132个字W0，W1，···，W67，W′0，W′1，···，W′63，每个字32位。其中W0至W15，由输入的512位依次截取而来，其它的116个字按照规定的运算规则产生。
然后，循环64次（第0到第63次）。第j轮次循环参与运算的有A、B、C、D、E、F、G、H共8个压缩寄存器，以及Wj、W‘j，还有Tj。T0，T1，···，T63是64个32位常量。
CF压缩算法中的运算都是针对字（指32位无符号整数）进行的，包括与、或、非、异或等布尔运算，循环移位等置换运算，以及截取低32位的求和运算。若干步运算组成算子，通常在程序中一个算子对应一个函数。
以上运算流程，对于SM3和SHA256都是一样的。两者不同的是IV、Tj的定义，W16、W17、···，W67，W′ 0，W′1，···，W′63的生成规则，以及每次循环运算的规则。
二、SM3的Python实现
网上有很多SM3源码，Python的代码也不少。同样的功能当然有各种编码方法，各有巧妙不同。下面我主要参考“python 编写SM3算法”，按自己的理解进行了部分改写，尽量多利用Python的特性，减少类似C语言的循环等，以简化编码，突出主要的算法逻辑。
1. 初始化常数IV，T0、T1、···，T63
# -*- coding: utf-8 -*-
"""
2020.5.10 in Wuhan
@author: oldgun
参考:https://blog.csdn.net/weixin_34144450/article/details/92916717
"""
import binascii
IV="7380166f 4914b2b9 172442d7 da8a0600 a96f30bc 163138aa e38dee4d b0fb0e4e".replace(" ", "")
a = []
for i in range(8):
a.append(int(IV[i*8 :(i+1)*8], 16))
IV = a
T_j = [0x79cc4519]*16 + [0x7a879d8a]*48
2. 定义算子和必要的转换函数
这些算子在CF压缩函数中都会用到。布尔算子对3个字进行运算，输出1个字，运算规则与循环的轮次j相关。置换算子对1个字进行运算，输出1个字。
# 将list数据拼成字节流
def bytesFromList(hashlist):
bytesStream = b''
for i in hashlist:
bytesStream += i.to_bytes(4, byteorder = 'big', signed=False)
return bytesStream
# 循环左移k位
def rotate_left(a, k):
k = k % 32
return ((a << k) & 0xFFFFFFFF) | ((a & 0xFFFFFFFF) >> (32 - k))
# 布尔算子：FF
def FF_j(X, Y, Z, j):
if 0 <= j and j < 16:
ret = X ^ Y ^ Z
elif 16 <= j and j < 64:
ret = (X & Y) | (X & Z) | (Y & Z)
return ret
# 布尔算子：GG
def GG_j(X, Y, Z, j):
if 0 <= j and j < 16:
ret = X ^ Y ^ Z
elif 16 <= j and j < 64:
ret = (X & Y) | ((~ X) & Z)
return ret
# 置换算子：P0
def P_0(X):
return X ^ (rotate_left(X, 9)) ^ (rotate_left(X, 17))
# 置换算子：P1
def P_1(X):
return X ^ (rotate_left(X, 15)) ^ (rotate_left(X, 23))
3. CF压缩函数
先是准备Wi和W’i，以及8个压缩寄存器的值。
然后循环64次，进行压缩。
# 压缩CF
def CF(V_i, B_i):
W = []
for j in range(16):
W.append(int.from_bytes(B_i[j*4:(j+1)*4], 'big'))
for j in range(16, 68):
W_j = P_1(W[j-16] ^ W[j-9] ^ (rotate_left(W[j-3], 15))) ^ (rotate_left(W[j-13], 7)) ^ W[j-6]
W.append(W_j)
W_1 = []
for j in range(64):
W_1.append(W[j] ^ W[j+4])
A, B, C, D, E, F, G, H = V_i
for j in range(64):
SS1 = rotate_left(((rotate_left(A, 12)) + E + (rotate_left(T_j[j], j))) & 0xFFFFFFFF, 7)
SS2 = SS1 ^ (rotate_left(A, 12))
TT1 = (FF_j(A, B, C, j) + D + SS2 + W_1[j]) & 0xFFFFFFFF
TT2 = (GG_j(E, F, G, j) + H + SS1 + W[j]) & 0xFFFFFFFF
D = C
C = rotate_left(B, 9)
B = A
A = TT1
H = G
G = rotate_left(F, 19)
F = E
E = P_0(TT2)
A = A & 0xFFFFFFFF
B = B & 0xFFFFFFFF
C = C & 0xFFFFFFFF
D = D & 0xFFFFFFFF
E = E & 0xFFFFFFFF
F = F & 0xFFFFFFFF
G = G & 0xFFFFFFFF
H = H & 0xFFFFFFFF
V_i_1 = [A ^ V_i[0], B ^ V_i[1], C ^ V_i[2], D ^ V_i[3],
E ^ V_i[4], F ^ V_i[5], G ^ V_i[6], H ^ V_i[7]]
return V_i_1
4. 分组和填充
对外的调用接口。第一个for循环对输入的消息按512位分割，接着的if…else对分组后剩余的消息进行填充。所有的组都存入msg_list列表中。最后就是对每个组依次迭代调用CF压缩函数。
# 输入数据类型应为字节流
def sm3(msg_bytes):
msg_len = len(msg_bytes)
msg_list = []
i = -1
# 按512位分组
for i in range(msg_len//64):
msg_list.append(msg_bytes[i*64 :(i+1)*64])
i += 1
rest_len = msg_len % 64
if(rest_len < 56): # 剩余位数小于448位，只需再加1组
# 补1个1和若干个0
tmpMsg = msg_bytes[i*64:] + b'\x80' + b'\x00'* (55 - rest_len)
# 补8字节，数值为参与hash数据的总位数
tmpMsg += (msg_len*8).to_bytes(8, byteorder='big', signed=False)
msg_list.append(tmpMsg)
else: # 剩余位数超过448位，需要再加2组
# 补1个1和若干个0，直到补满512位
tmpMsg = msg_bytes[i*64:] + b'\x80' + b'\x00'* (63 - rest_len)
msg_list.append(tmpMsg)
# 前面补56字节的0，再填写总位数
tmpMsg = b'\x00'*56 + (msg_len*8).to_bytes(8, byteorder='big', signed=False)
msg_list.append(tmpMsg)
V = IV
for msg in msg_list:
V = CF(V, msg)
return bytesFromList(V)
三、测试
国家密码管理局官网pdf文件中提供了2个示例，一个是abc（24位），一个是连续16个abcd（512位）。几乎所有的源码都会先用这两个示例作为测试样例。但是，显然仅仅这两个示例的结果正确并不能让人对程序正确性拥有足够的信心。SHA256有很多用于对比测试的软件，甚至是在线测试，可以自己输入各种长度的消息进行比对测试。但是SM3不具备这样的条件。因此，我从网上收集了SM3正确性运算实例，编写了相应的测试代码，基本能覆盖程序的各个分支。
# 用实例进行测试
# 国标示例
TEST_LIST = [ ("国标示例1",
"abc",
"66c7f0f4 62eeedd9 d1f2d46b dc10e4e2 4167c487 5cf2f7a2 297da02b 8f4ba8e0"
),
("国标示例2",
"abcd"*16,
"debe9ff9 2275b8a1 38604889 c18e5a4d 6fdb70e5 387e5765 293dcba3 9c0c5732"
),
]
for (name, msgStr, ansStr) in TEST_LIST:
msg = msgStr.encode() # 输入 ASCII字符串转为字节流
y = sm3(msg)
ansStr = ansStr.replace(" ", "")
ans = binascii.a2b_hex(ansStr) # 答案 十六进制字符串转为字节流
if(y == ans):
print(name, " Test PASS!\n")
else:
print(name, " Test FAILED!!!")
print("result: %s\n"%binascii.b2a_hex(y).decode('utf-8'))
# 验证实例 来源于 https://wenku.baidu.com/view/91b57a06a6c30c2259019eb5.htm
lTEST_LIST = [ ("实例 1",
"763AFC537F7876C2D0B59FDB68D762E90CEFD222BB358D0D6931867CE26538649BE3579A4004483EA5D84D005063F76FB1CE7E5F2F933B5ED757A718182F383C4D58291A6A5D8D07C081F66806031539093362D854883A8874F7B919925DABC74C173E2162F07E6780E311FF0AEF059AE620303DECB6289E97F72C018723C471",
"d3,2b,9d,79,3b,49,66,e1,8c,35,18,92,e6,52,77,75,6e,f0,cc,9d,28,db,95,4c,95,9f,bb,85,e3,94,84,42"
),
("实例 2",
"2F917420E702DBA970C071AE4971AD08DE3D7D0D90DC1E334ED20444E54F109BA80DD22F25C24FAA83D5AD58687F1AA68F1B749D0AD999DB9A1AC8E4DC",
"5e,11,d3,64,71,23,f4,43,18,7e,f2,5d,9e,fc,33,db,74,29,ce,c0,06,d6,3e,4c,9a,35,db,84,2f,73,4b,a8"
),
("实例 3",
"2F917420E702DBA970C071AE4971AD08DE3D7D0D90DC1E334ED20444E54F109BA80DD22F25C24FAA83D5AD58687F1AA68F1B749D0AD999",
"d1,e5,44,80,1f,8b,29,ac,fb,c8,cf,69,9f,0d,a3,7b,f3,18,74,eb,66,a0,eb,50,ae,ee,4a,4d,31,58,7c,2f"
),
("实例 4",
"2F917420E702DBA970C071AEDE3D7D0D90DC1E334ED20444E54F109BA80DD22F25C24FAA83D5AD58687F1AA68F1B749D0AD999",
"06,0f,dc,46,34,e0,70,ac,ab,54,8a,63,08,f7,44,58,68,1d,59,65,07,75,46,79,3c,16,8a,82,c4,a5,d7,ad"
),
("实例 5",
"E47F211542C022AC94542DE4EEC6A1B10BF54B6A9F3C439459F4D9779C4BE5326AEA06FF6EEE97F61E66978DFA8543D1520103CDA6AB7655B592BF2D40ECB937",
"33,D0,D0,AB,67,A3,11,F4,46,4D,B2,F7,40,45,F0,CE,D7,31,5A,1B,82,FE,5C,03,EA,CA,D3,B1,E8,D4,B7,50"
),
("实例 6",
"64055D80810171DCE32D71773ECFDC803203539DB5677401DDD6A2B538D0652978479B5BE524FE809CB35499BDCC4C8FC1081CB2E09BCB4458828C5168BE329D",
"B4,21,1F,6B,AB,65,19,B9,9A,30,13,F2,A1,4F,BF,32,04,9F,F2,F0,C4,47,0D,67,DA,32,99,5E,CB,4C,CE,D6"
),
("实例 7",
"8BF6F8D53AFBB995FFFC001F76FC8549F67BDDA730B38D3E75301C834FBA67E1395B8D63D07908367B3311E2BD3586DCD4498869994DF0D5006781C880E7C83B",
"3E,E8,77,50,BA,8A,B7,07,9C,3C,6A,2C,22,8C,14,84,0C,0C,7D,C2,B9,0E,93,B7,16,06,EC,2B,DB,C3,0D,46"
),
("实例 8",
"34523D2F917420E702DBA970C071AE4971AD08DE3D7D0D90DC1E334ED20444E54F109BA80DD22F25C24FAA83D5AD58687F1AA68F1B749D0AD999DB9A1AC8E4DC",
"4A,26,7A,B8,23,F7,5B,3B,49,90,F6,0F,49,D1,45,BE,F1,CF,87,B0,2C,86,A9,50,88,E8,FE,02,0D,85,C7,F5"
),
("实例 9",
"3366779900",
"47,9D,86,3F,D6,74,6F,47,57,0B,81,1F,F6,CF,39,D6,6B,49,57,49,73,BD,C2,AF,A6,DA,4B,23,93,4A,40,6F"
),
("实例10",
"3366779900881234567890",
"AE,95,25,33,F5,E2,41,97,B6,84,37,57,F5,34,E4,9C,15,C1,F6,5A,46,C0,D0,18,89,45,1C,39,29,4B,79,1B"
),
("实例11",
"4EB692FE05A6A6D83FC12B6EDC7F9D877C71F8A5",
"39,67,C5,14,1E,D3,45,E6,1B,9A,6D,69,17,39,5F,89,48,93,EA,FD,4F,46,77,ED,5C,4E,33,E9,10,E0,24,D9"
),
("实例12",
"3967C5141ED345E61B9A6D6917395F894893EAFD4F4677ED5C4E33E910E024D9",
"98,C1,7C,93,6B,46,68,E4,7B,B6,78,0A,47,3E,7F,65,9A,29,D9,65,9F,68,59,E0,1E,02,48,19,67,8C,08,87"
),
("实例13",
"69AECD12F42E310465B4301320B277E2E4DE21EA593C377C",
"9D,B8,4C,1D,01,24,94,A6,D6,79,EE,A4,5B,55,0B,44,CD,76,BB,F3,78,31,99,85,55,94,38,A1,49,B2,69,0D"
),
]
for (name, msgHexStr, ansStr) in TEST_LIST:
msgHexStr = msgHexStr.replace(",", "").replace(" ", "")
msg = binascii.a2b_hex(msgHexStr) # 输入 十六进制字符串转为字节流
y = sm3(msg)
ansStr = ansStr.replace(",", "")
ans = binascii.a2b_hex(ansStr) # 答案 十六进制字符串转为字节流
if(y == ans):
print(name, " Test PASS!\n")
else:
print(name, " Test FAILED!!!")
print("result: %s\n"%binascii.b2a_hex(y).decode('utf-8'))
上述代码和测试在python3.8.4上调试通过。基于SM3的工作，已经完成了完整的SM2 Python程序及其初步测试，以后抽空再整理成文。