[Crypto]SM3算法分析

2401_87529702

1064人浏览 · 2026-04-24 16:40:43

2401_87529702 · 2026-04-24 16:40:43 发布

注：本blog参考《SM3密码杂凑算法》(GB/T 32905-2016)与python开源库gmssl中的sm3算法实现

国家标准全文公开系统：https://openstd.samr.gov.cn
作者个人博客：https://baymax-fools.github.io

算法基本信息

SM3是一种杂凑算法（就是一种哈希算法，类似SHA-256、MD5等等）
输入长度：小于 $2^{64}$ （理论）
输出长度：256bit
sm3对明文的填充是比较有特点的

填充

长度l的明文m，填充如下：
1.先加一比特1
2.在1后加k个0，使明文长度为 $\mod 512$
3.再加上一个64位比特串，这个比特串就是长度l的二进制表示（这里就能看出为什么sm3的理论输入长度要小于 $2^{64}$ ）

填充后的明文长度是512的倍数，后经迭代压缩，输出256bit的杂凑值
下面是gmssl库中的实现，注意一下，py中没办法一比特一比特填充，只能填充字节( $1 b y t e = 8 bi t$ )，所以实现起来会麻烦一点

def sm3_hash(msg):  
    # print(msg)  
    len1 = len(msg)     # 计算msg的字节长  
    reserve1 = len1 % 64    # 计算余数  
    
    msg.append(0x80)    # 在msg后加上'0b10000000'  
    # 这里有可能会产生一个问题，就是直接填充一个字节，如果要填充的k小于7的话，  
    # 即 ( l + 1 ) % 512 > 448 ，不会产生影响吗：  
    # 实际上，并不会有任何影响。  
    # 因为消息msg是以字节的形式传入的，说明msg的bit位长度一定是8的倍数，  
    # 如果是 448 长度的话，加上 1 就是449，需要填充一个模长  
    # 最接近的是 440 长度的，k = (448 - (l+1)） = 7 % 512，刚好就是0x80中的后面七个'0'  
    # 注：其实k的长度是能求出： k = 7 % 8    
    
    reserve1 = reserve1 + 1 # 余数加上0x80这一个字节    
    range_end = 56  # 剩下的8字节留给长度  
    if reserve1 > range_end:    # 如果成立，说明要填充一整个模长（512bit）  
        range_end = range_end + 64  
  
    for i in range(reserve1, range_end):    # 填充字节  
        msg.append(0x00)  
  
    bit_length = (len1) * 8 # 转换为比特数  
    bit_length_str = [bit_length % 0x100]   # 取最低8位  
    for i in range(7):  
        bit_length = int(bit_length / 0x100)  
        bit_length_str.append(bit_length % 0x100)   # 依次取更高8位  
    for i in range(8):  
        msg.append(bit_length_str[7-i])

定义函数

指的是在下面的迭代压缩中会出现的函数（在GB/T标准中定义好的）
有俩个布尔函数和俩个置换函数

$∧\land$ : 32bit与运算
$∨\lor$ ：32bit或运算
$⊕\oplus$ ：32bit异或运算
$¬\lnot$ ：32bit非运算

布尔函数

(1)
$\leqslant j \leqslant 15$ 时: $FFj(X,Y,Z)=X⊕Y⊕ZFF_j(X,Y,Z) = X \oplus Y \oplus Z$
$\leqslant j \leqslant 63$ 时: $FFj(X,Y,Z)=(X∧Y)∨(X∧Z)∨(Y∧Z)FF_j(X,Y,Z) = (X \land Y) \lor (X \land Z) \lor (Y \land Z)$

(2)
$\leqslant j \leqslant 15$ 时: $GGj(X,Y,Z)=X⊕Y⊕ZGG_j(X,Y,Z) = X \oplus Y \oplus Z$
$\leqslant j \leqslant 63$ 时: $GGj(X,Y,Z)=(X∧Y)∨(¬X∧Z)GG_j(X,Y,Z) = (X \land Y) \lor (\lnot X \land Z)$

其中 $X$ ， $Y$ ， $Z$ 为字

置换函数

（1） $P0(X)=X⊕(X<<<9)⊕(X<<<17)P_0(X) = X \oplus (X <<<9) \oplus (X<<<17)$

(2) $P1(X)=X⊕(X<<<15)⊕(X<<<23)P_1(X) = X \oplus (X<<<15) \oplus(X<<<23)$
其中X为字

代码实现：

没什么特别的地方

def sm3_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  
  
def sm3_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) & ((2 ** 32 - 1 - X) | Z)  
        ret = (x & y) | ((~ x) & z)  
    return ret  
  
def sm3_p_0(x):  
    return x ^ (rotl(x, 9 % 32)) ^ (rotl(x, 17 % 32))  
  
def sm3_p_1(x):  
    return x ^ (rotl(x, 15 % 32)) ^ (rotl(x, 23 % 32))

压缩函数

注：在sm3中，要进行压缩函数的运算前是要先对消息进行扩展的，这里先说压缩函数，消息扩展在后面。

定义：
<-是左向赋值
W为字（32比特串）
A、B、C、D、E、F、G、H为字寄存器
SS1、SS2、TT1、TT2为中间变量
$V^0$ 为256bit初始值IV， $V^n$ 为迭代压缩结果， $B^i$ 为明文分组
$T_i$ 是算法定义好的值（随i值的变化而变化）
压缩函数： $V^{i+1}=CF(V^i,B^i)$

过程：
将 $V^i$ 存入ABCDEFGH后进入循环

可能看着有点乱，可以看代码实现来辅助理解：

T_j = [  
    2043430169, 2043430169, 2043430169, 2043430169, 2043430169, 2043430169,  
    2043430169, 2043430169, 2043430169, 2043430169, 2043430169, 2043430169,  
    2043430169, 2043430169, 2043430169, 2043430169, 2055708042, 2055708042,  
    2055708042, 2055708042, 2055708042, 2055708042, 2055708042, 2055708042,  
    2055708042, 2055708042, 2055708042, 2055708042, 2055708042, 2055708042,  
    2055708042, 2055708042, 2055708042, 2055708042, 2055708042, 2055708042,  
    2055708042, 2055708042, 2055708042, 2055708042, 2055708042, 2055708042,  
    2055708042, 2055708042, 2055708042, 2055708042, 2055708042, 2055708042,  
    2055708042, 2055708042, 2055708042, 2055708042, 2055708042, 2055708042,  
    2055708042, 2055708042, 2055708042, 2055708042, 2055708042, 2055708042,  
    2055708042, 2055708042, 2055708042, 2055708042  
]
# 前16是一个值，其他是一个值
###########################################################################

a, b, c, d, e, f, g, h = v_i  
  
for j in range(0, 64):  
    ss_1 = rotl(  
        ((rotl(a, 12 % 32)) +  
        e +  
        (rotl(T_j[j], j % 32))) & 0xffffffff, 7 % 32  
    )  
    
    # w和w_1是消息扩展数组，文章后面会讲
    ss_2 = ss_1 ^ (rotl(a, 12 % 32))  
    tt_1 = (sm3_ff_j(a, b, c, j) + d + ss_2 + w_1[j]) & 0xffffffff  
    tt_2 = (sm3_gg_j(e, f, g, j) + h + ss_1 + w[j]) & 0xffffffff  
    d = c  
    c = rotl(b, 9 % 32)  
    b = a  
    a = tt_1  
    h = g  
    g = rotl(f, 19 % 32)  
    f = e  
    e = sm3_p_0(tt_2)  
  
    a, b, c, d, e, f, g, h = map(  
        lambda x:x & 0xFFFFFFFF ,[a, b, c, d, e, f, g, h])  
    # 将各个字寄存器保留低32位后保存  
  
v_j = [a, b, c, d, e, f, g, h]  
return [v_j[i] ^ v_i[i] for i in range(8)]

迭代压缩

第一步：消息填充

对消息填充后按512比特分组： $m'=B^0B^1...B^{n-1}$ ，其中 $n = (l + k + 65) /512$

group_count = round(len(msg) / 64)  
  
B = []  
for i in range(0, group_count):  
    B.append(msg[i*64:(i+1)*64])  # 同样因为py中是以字节为一个单位的（8*64）

第二步：消息扩展

将 $B^i$ 扩展成132个消息字 $W_0,W_1,...,W_{67}$ , $W'_0, W'_1,..., W'_{63}$ ，后会用在压缩函数里。

先将消息分组 $B^i$ 划分成16个字 $W_0,W_1,...,W_{15}$ ，后经过下面俩个循环扩展。

FOR j = 16 TO 67
$W_i$ <- $P1(Wi−16⊕Wi−9⊕(Wi−3<<<15))⊕(Wi−13<<<7)⊕Wi−6P_1(W_{i-16}\oplus W_{i-9} \oplus (W_{i-3} <<< 15))\oplus (W_{i-13}<<< 7)\oplus W_{i-6}$
ENDFOR

FOR j = 0 TO 63
$W'_i$ = $Wi⊕Wi+4W_i\oplus W_{i+4}$
ENDFOR

成功将消息扩展成132个消息字

w = []  
for i in range(16):  # 处理16个字  
    weight = 0x1000000  # 初始权重，用于按字节组合成32位字  
    data = 0  # 临时存储组合成的32位字  
    # 每4个字节组成一个字（大端序）  
    for k in range(i * 4, (i + 1) * 4):  # 遍历当前字的4个字节  
        data = data + b_i[k] * weight  # 将字节放到对应位置  
        weight = int(weight / 0x100)  # 权重右移8位（除以256）  
    w.append(data)  # 添加第i个字到w[0..15]  
  
for j in range(16, 68):  # 生成第16到第67个字  
    w.append(0)  # 为了下行数组的索引安全，先添加占位元素  
    w[j] = sm3_p_1(w[j - 16] ^ w[j - 9] ^ (rotl(w[j - 3], 15 % 32))) ^ (rotl(w[j - 13], 7 % 32)) ^ w[j - 6]  
    str1 = "%08x" % w[j]  # 转换为十六进制字符串（可用于调试）  
  
w_1 = []    
for j in range(0, 64):  # 生成64个W'字  
    w_1.append(0)  # 与上个循环同理  
    w_1[j] = w[j] ^ w[j + 4]  
    str1 = "%08x" % w_1[j]

第三步：迭代

对 $m^{'}$ 进行迭代：
FOR i = 0 TO n-1
$V^{i+1} = CF(V^i,B^i)$
ENDFOR

$V^0$ 为256bit初始值IV， $V^n$ 为迭代压缩结果
迭代完成输出256比特杂凑值： $y = A B C D E F G H$ <- $V^n$

V = []  
V.append(IV)  
for i in range(0, group_count):  
    V.append(sm3_cf(V[i], B[i]))  
  
y = V[i+1]  
result = ""  
for i in y:  
    result = '%s%08x' % (result, i)  
return result

注：本文的gmssl代码演示，因展示顺序可能导致有函数被拆成几部分，详细请看gmssl库源码

密钥派生函数

gmssl中还实现用sm3来实现的密钥派生函数

# 密钥派生函数  
def sm3_kdf(z, klen): # z为16进制表示的比特串（str），klen为密钥长度（单位byte）  
    klen = int(klen)  
    ct = 0x00000001  
    rcnt = ceil(klen/32)  
    zin = [i for i in bytes.fromhex(z.decode('utf8'))]  
    ha = ""  
    for i in range(rcnt):  
        msg = zin  + [i for i in binascii.a2b_hex(('%08x' % ct).encode('utf8'))]  
        ha = ha + sm3_hash(msg)  
        ct += 1  
    return ha[0: klen * 2]

总源码

import binascii
from math import ceil
from .func import rotl, bytes_to_list

IV = [
    1937774191, 1226093241, 388252375, 3666478592,
    2842636476, 372324522, 3817729613, 2969243214,
]

T_j = [
    2043430169, 2043430169, 2043430169, 2043430169, 2043430169, 2043430169,
    2043430169, 2043430169, 2043430169, 2043430169, 2043430169, 2043430169,
    2043430169, 2043430169, 2043430169, 2043430169, 2055708042, 2055708042,
    2055708042, 2055708042, 2055708042, 2055708042, 2055708042, 2055708042,
    2055708042, 2055708042, 2055708042, 2055708042, 2055708042, 2055708042,
    2055708042, 2055708042, 2055708042, 2055708042, 2055708042, 2055708042,
    2055708042, 2055708042, 2055708042, 2055708042, 2055708042, 2055708042,
    2055708042, 2055708042, 2055708042, 2055708042, 2055708042, 2055708042,
    2055708042, 2055708042, 2055708042, 2055708042, 2055708042, 2055708042,
    2055708042, 2055708042, 2055708042, 2055708042, 2055708042, 2055708042,
    2055708042, 2055708042, 2055708042, 2055708042
]

def sm3_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

def sm3_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) & ((2 ** 32 - 1 - X) | Z)
        ret = (x & y) | ((~ x) & z)
    return ret

def sm3_p_0(x):
    return x ^ (rotl(x, 9 % 32)) ^ (rotl(x, 17 % 32))

def sm3_p_1(x):
    return x ^ (rotl(x, 15 % 32)) ^ (rotl(x, 23 % 32))

def sm3_cf(v_i, b_i):
    w = []
    for i in range(16):  # 处理16个字
        weight = 0x1000000  # 初始权重，用于按字节组合成32位字
        data = 0  # 临时存储组合成的32位字
        # 每4个字节组成一个字（大端序）
        for k in range(i * 4, (i + 1) * 4):  # 遍历当前字的4个字节
            data = data + b_i[k] * weight  # 将字节放到对应位置
            weight = int(weight / 0x100)  # 权重右移8位（除以256）
        w.append(data)  # 添加第i个字到w[0..15]

    for j in range(16, 68):  # 生成第16到第67个字
        w.append(0)  # 为了下行数组的索引安全，先添加占位元素
        w[j] = sm3_p_1(w[j - 16] ^ w[j - 9] ^ (rotl(w[j - 3], 15 % 32))) ^ (rotl(w[j - 13], 7 % 32)) ^ w[j - 6]
        str1 = "%08x" % w[j]  # 转换为十六进制字符串（可用于调试）

    w_1 = []
    for j in range(0, 64):  # 生成64个W'字
        w_1.append(0)  # 与上个循环同理
        w_1[j] = w[j] ^ w[j + 4]
        str1 = "%08x" % w_1[j]

    a, b, c, d, e, f, g, h = v_i

    for j in range(0, 64):
        ss_1 = rotl(
            ((rotl(a, 12 % 32)) +
            e +
            (rotl(T_j[j], j % 32))) & 0xffffffff, 7 % 32
        )
        ss_2 = ss_1 ^ (rotl(a, 12 % 32))

        # w和w_1是消息扩展数组，文章后面会讲
        tt_1 = (sm3_ff_j(a, b, c, j) + d + ss_2 + w_1[j]) & 0xffffffff
        tt_2 = (sm3_gg_j(e, f, g, j) + h + ss_1 + w[j]) & 0xffffffff
        d = c
        c = rotl(b, 9 % 32)
        b = a
        a = tt_1
        h = g
        g = rotl(f, 19 % 32)
        f = e
        e = sm3_p_0(tt_2)

        a, b, c, d, e, f, g, h = map(
            lambda x:x & 0xFFFFFFFF ,[a, b, c, d, e, f, g, h])
        # 将各个字寄存器保留低32位后保存

    v_j = [a, b, c, d, e, f, g, h]
    return [v_j[i] ^ v_i[i] for i in range(8)]

def sm3_hash(msg):
    # print(msg)
    len1 = len(msg)     # 计算msg的字节长
    reserve1 = len1 % 64    # 计算余数
    msg.append(0x80)    # 在msg后加上'0b10000000'
    # 这里有可能会产生一个问题，就是直接填充一个字节，如果要填充的k小于7的话，
    # 即 ( l + 1 ) % 512 > 448 ，不会产生影响吗：
    # 实际上，并不会有任何影响。
    # 因为消息msg是以字节的形式传入的，说明msg的bit位长度一定是8的倍数，
    # 如果是 448 长度的话，加上 1 就是449，需要填充一个模长
    # 最接近的是 440 长度的，k = (448 - (l+1)） = 7 % 512，刚好就是0x80中的后面七个'0'
    # 注：其实k的长度是能求出： k = 7 % 8

    reserve1 = reserve1 + 1 # 余数加上0x80这一个字节
    # 56-64, add 64 byte
    range_end = 56  # 剩下的8字节留给长度
    if reserve1 > range_end:    # 如果成立，说明要填充一整个模长（512bit）
        range_end = range_end + 64

    for i in range(reserve1, range_end):    # 填充字节
        msg.append(0x00)

    bit_length = (len1) * 8 # 转换为比特数
    bit_length_str = [bit_length % 0x100]   # 取最低8位
    for i in range(7):
        bit_length = int(bit_length / 0x100)
        bit_length_str.append(bit_length % 0x100)   # 依次取更高8位
    for i in range(8):
        msg.append(bit_length_str[7-i])

    group_count = round(len(msg) / 64)

    B = []
    for i in range(0, group_count):
        B.append(msg[i*64:(i+1)*64])

    V = []
    V.append(IV)
    for i in range(0, group_count):
        V.append(sm3_cf(V[i], B[i]))

    y = V[i+1]
    result = ""
    for i in y:
        result = '%s%08x' % (result, i)
    return result

# 密钥派生函数
def sm3_kdf(z, klen): # z为16进制表示的比特串（str），klen为密钥长度（单位byte）
    klen = int(klen)
    ct = 0x00000001
    rcnt = ceil(klen/32)
    zin = [i for i in bytes.fromhex(z.decode('utf8'))]
    ha = ""
    for i in range(rcnt):
        msg = zin  + [i for i in binascii.a2b_hex(('%08x' % ct).encode('utf8'))]
        ha = ha + sm3_hash(msg)
        ct += 1
    return ha[0: klen * 2]

题目

后续遇到具体题目会再进行补充。。。（希望不会鸽了）

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

大学毕业论文纯人工去AI痕迹、降AIGC率全套方法

目前高校AIGC检测核心判定标准为文本句式机械化、表达模板化、逻辑过于规整、内容缺乏主观思考与研究细节。绝大多数AI生成内容存在高度同质化问题，仅依靠同义词替换无法有效降低AI检测率。本文整理适用于本科、专科毕业论文的，全程无需任何改写工具，修改后文本更贴近学生原创写作风格，可有效规避各大平台AI查重。