一、實驗要求與目的

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)) % 512m_bin += '0' * kl_bin = f'{l:064b}'m_bin += l_binreturn m_bindef left_rotate(x, n):n = n % 32return ((x << n) | (x >> (32 - n))) & 0xFFFFFFFFdef 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 = VW, 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 0x7A879D8ASS1 = 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]) & 0xFFFFFFFFTT2 = (GG(E, F_, G, j) + H + SS1 + W[j]) & 0xFFFFFFFFD = CC = left_rotate(B_, 9)B_ = AA = TT1H = GG = left_rotate(F_, 19)F_ = EE = 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 的主要區別有哪些？

項目	SM3	SHA-256
分組長度	512 bit	512 bit
輸出長度	256 bit	256 bit
常量結構	輪常量分段不同	固定64個常量
置換函數	P0, P1	無（直接計算）
安全標準	國密標準 GM/T 0004-2012	國際標準 FIPS PUB 180-4

3. SM3 安全性基于什么？

SM3 作為哈希函數，其安全性包括抗碰撞性、抗第二原像性等，核心基于消息擴展、壓縮函數的非線性變換和 Merkle-Damg?rd 結構的累積性。目前無有效攻擊能在 2^128 復雜度下破壞 SM3 的抗碰撞性。