【应用密码学】实验七 Hash函数——SM3

一、实验要求与目的

1. 理解哈希函数的基本原理及在密码学中的应用；
2. 掌握国密哈希标准 SM3 的算法结构；
3. 编程实现 SM3 摘要算法，包括消息填充、消息扩展、压缩函数及摘要输出；
4. 对中间变量 W、W′ 和 A~H 的迭代过程进行可视化，深入理解其内部机制。

二、实验内容与步骤记录（只记录关键步骤与结果，可截图，但注意排版与图片大小）

SM3 是一种基于 Merkle-Damgård结构 的杂凑算法，其流程可分为以下五大步骤：

消息预处理（填充 + 分组），消息扩展（生成 W 和 W′），压缩函数（A~H 迭代更新），状态反馈（初始向量 XOR 当前结果），输出摘要（256-bit）。所以我们分别对这些步骤进行设计

1．消息填充与分组处理

首先将输入字符串转换为二进制串，每个字符使用8位ASCII编码表示。

按照 SM3 填充规则：在消息后添加一个 1；添加 k 个 0，使得 l + 1 + k ≡ 448 mod 512；在末尾添加原始长度 l 的 64-bit 表示；

最终使得填充结果为 512 的整数倍（本实验为1组512位）。

2．消息扩展模块实现

W0–W15：初始划分

对每个 512bit 块 Bi，按 32bit 为单位划分为 16 个整数 W0​,W1​,...,W15​。

W16–W67：扩展计算

通过如下公式递推生成：

Wj=P1(Wj−16⊕Wj−9⊕(Wj−3⋘15))⊕(Wj−13⋘7)⊕Wj−6(16 ≤j < 68)

其中 P1(x)=x⊕(x⋘15)⊕(x⋘23)

W′0–W′63 计算

Wj′=Wj⊕Wj+4(0≤j<64)

可视化输出

实验中通过 print_expansion() 函数输出 W 与 W′ 的值（十六进制格式），验证扩展逻辑正确性。

3．压缩函数（64轮迭代）实现与输出

根据国密标准设定初始寄存器 A~H：

A = 0x7380166F

B = 0x4914B2B9

C = 0x172442D7

...

H = 0xB0EB0E4E

每一轮（共64轮）执行如下操作：

SS1 = ROTL((ROTL(A, 12) + E + ROTL(Tj, j)) & 0xFFFFFFFF, 7)

SS2 = SS1 ^ ROTL(A, 12)

TT1 = (FF(A,B,C,j) + D + SS2 + W′[j]) & 0xFFFFFFFF

TT2 = (GG(E,F,G,j) + H + SS1 + W[j]) & 0xFFFFFFFF

然后更新：

mathematica

D = C, C = ROTL(B,9), B = A, A = TT1

H = G, G = ROTL(F,19), F = E, E = P0(TT2)

每轮后输出一次 A~H 的状态：

j=00 → A=8742F2C2 B=7380166F ...

j=01 → A=4C71DB3E B=8742F2C2 ...

这样可跟踪 A~H 的变化趋势，验证压缩操作的动态过程。

4. 向量反馈与摘要输出

64轮结束后，将当前 A~H 与前一状态向量 V 进行逐位异或，形成新的向量：

V_next[i] = V[i] ^ current[i]  for i in 0..7

如果还有后续分组，则继续迭代。

当所有分组处理完成后，V 就是最终的 SM3 杂凑值。拼接 A~H，输出为 256bit 十六进制字符串：

66c7f0f462eeedd9d1f2d46bdc10e4e24167c4875cf2f7a2297da02b8f4ba8e0

该值与 SM3 标准样例一致，验证算法正确性。

三、源代码记录（关键代码需备注）

# -------------- 基础函数 ----------------#
def str_to_bin(msg: str) -> str:
    return ''.join(f'{ord(c):08b}' for c in msg)


def padding_sm3(msg: str) -> str:
    m_bin = str_to_bin(msg)
    l = len(m_bin)
    m_bin += '1'
    k = (448 - (l + 1)) % 512
    m_bin += '0' * k
    l_bin = f'{l:064b}'
    m_bin += l_bin
    return m_bin


def left_rotate(x, n):
    n = n % 32
    return ((x << n) | (x >> (32 - n))) & 0xFFFFFFFF


def split_blocks(m_bin: str, block_size=512):
    return [m_bin[i:i + block_size] for i in range(0, len(m_bin), block_size)]


def binstr_to_int_list(block_512bit: str):
    return [int(block_512bit[i:i + 32], 2) for i in range(0, 512, 32)]


# -------------- 扩展函数 ----------------#
def P1(X):
    return X ^ left_rotate(X, 15) ^ left_rotate(X, 23)


def P0(X):
    return X ^ left_rotate(X, 9) ^ left_rotate(X, 17)


def message_expand(block_512bit: str):
    W = binstr_to_int_list(block_512bit)
    for j in range(16, 68):
        term = P1(W[j - 16] ^ W[j - 9] ^ left_rotate(W[j - 3], 15))
        term = term ^ left_rotate(W[j - 13], 7) ^ W[j - 6]
        W.append(term & 0xFFFFFFFF)

    W_ = [(W[j] ^ W[j + 4]) & 0xFFFFFFFF for j in range(64)]
    return W, W_


def print_expansion(W, W_):
    print("=== W[0..67] ===")
    for i in range(68):
        print(f"W[{i:02}] = {W[i]:08X}")
    print("\n=== W′[0..63] ===")
    for i in range(64):
        print(f"W′[{i:02}] = {W_[i]:08X}")


# -------------- 压缩函数 ----------------#
def FF(X, Y, Z, j):
    return (X ^ Y ^ Z) if j < 16 else ((X & Y) | (X & Z) | (Y & Z))


def GG(X, Y, Z, j):
    return (X ^ Y ^ Z) if j < 16 else ((X & Y) | (~X & Z))


def CF(V, B):
    A, B_, C, D, E, F_, G, H = V
    W, W_ = message_expand(B)
    print("\n>>> [压缩函数初始化] <<<")
    print(f"A={A:08X} B={B_:08X} C={C:08X} D={D:08X} E={E:08X} F={F_:08X} G={G:08X} H={H:08X}")
    for j in range(64):
        Tj = 0x79CC4519 if j < 16 else 0x7A879D8A
        SS1 = left_rotate((left_rotate(A, 12) + E + left_rotate(Tj, j)) & 0xFFFFFFFF, 7)
        SS2 = SS1 ^ left_rotate(A, 12)
        TT1 = (FF(A, B_, C, j) + D + SS2 + W_[j]) & 0xFFFFFFFF
        TT2 = (GG(E, F_, G, j) + H + SS1 + W[j]) & 0xFFFFFFFF

        D = C
        C = left_rotate(B_, 9)
        B_ = A
        A = TT1
        H = G
        G = left_rotate(F_, 19)
        F_ = E
        E = P0(TT2)
        print(f"j={j:02} → A={A:08X} B={B_:08X} C={C:08X} D={D:08X} E={E:08X} F={F_:08X} G={G:08X} H={H:08X}")

    print(">>> [压缩函数结束] <<<")
    return [(v ^ n) & 0xFFFFFFFF for v, n in zip(V, [A, B_, C, D, E, F_, G, H])]


# -------------- 哈希函数主控 ----------------#
def sm3_hash(msg: str, visual=True):
    IV = [
        0x7380166F, 0x4914B2B9, 0x172442D7, 0xDA8A0600,
        0xA96F30BC, 0x163138AA, 0xE38DEE4D, 0xB0EB0E4E
    ]

    padded = padding_sm3(msg)
    blocks = split_blocks(padded)

    print("原始长度：", len(str_to_bin(msg)), "bits")
    print("填充后总长度：", len(padded), "bits")
    print("填充后分组数量：", len(blocks))
    print("填充结果前64位：", padded[:64])
    print("填充结果末64位：", padded[-64:])

    V = IV[:]
    for i, block in enumerate(blocks):
        print(f"\n>>> 第 {i} 块 <<<")
        W, W_ = message_expand(block)
        if visual:
            print_expansion(W, W_)
        V = CF(V, block)

    digest = ''.join(f'{x:08x}' for x in V)
    print("\n最终 SM3 摘要为：")
    print(digest)
    return digest


# -------------- 测试入口 ----------------#
if __name__ == "__main__":
    msg = "abc"  # 可以改为 input("请输入消息: ")
    sm3_hash(msg)

四、实验思考

1. SM3 摘要为什么不是最后一轮 A–H 值拼接？

SM3 采用 Merkle-Damgård 构架，每轮压缩结束后必须将前一状态 V 与当前 A–H 异或（XOR）。若直接使用 A~H 拼接会破坏反馈结构，易受长度扩展攻击。因此摘要为：

digest=Vn=Vn−1⊕[A,B,...,H]\text{digest} = V_n = V_{n-1} \oplus [A,B,...,H]digest=Vn​=Vn−1​⊕[A,B,...,H]

2. SM3 与 SHA-256 的主要区别有哪些？

3. SM3 安全性基于什么？

SM3 作为哈希函数，其安全性包括抗碰撞性、抗第二原像性等，核心基于消息扩展、压缩函数的非线性变换和 Merkle-Damgård 结构的累积性。目前无有效攻击能在 2^128 复杂度下破坏 SM3 的抗碰撞性。