4. SM4 软件实现：纯 Python 实现、性能优化与查表法加速

SM4 算法，说白了就是咱们国密标准里的对称分组密码。很多刚接触的朋友会问：这东西跟 AES 比怎么样？我的回答是：设计理念不同，但安全性相当。今天咱们就聊聊怎么在软件里把它跑起来，而且跑得快。

4.1 纯 Python 实现：先跑通再说

我个人习惯，不管什么算法，先用纯 Python 写一版。为什么？调试方便，逻辑清晰。你想想看，要是上来就搞查表法、指令集优化，出了问题你都不知道是算法写错了还是优化写错了。

SM4 的核心结构其实不复杂：32 轮迭代，每轮用一个 32 位的轮密钥。它的 S 盒是 8 位输入、8 位输出，一共 256 个值。咱们先把这个 S 盒定义好：

S_BOX = [
    0xd6, 0x90, 0xe9, 0xfe, 0xcc, 0xe1, 0x3d, 0xb7,
    0x16, 0xb6, 0x14, 0xc2, 0x28, 0xfb, 0x2c, 0x05,
    # ... 共 256 个值
]

然后就是轮函数 F。它做了三件事：异或、S 盒替换、线性变换 L。我刚开始写的时候，把线性变换的循环移位写反了，结果加解密对不上。嗯，这里要注意：L 变换是左移，不是右移。

def sm4_round(x0, x1, x2, x3, rk):
    # 异或
    tmp = x1 ^ x2 ^ x3 ^ rk
    # S 盒替换
    s = (S_BOX[(tmp >> 24) & 0xff] << 24) | \
        (S_BOX[(tmp >> 16) & 0xff] << 16) | \
        (S_BOX[(tmp >> 8) & 0xff] << 8) | \
        (S_BOX[tmp & 0xff])
    # 线性变换 L
    l = s ^ ((s << 2) & 0xffffffff) ^ ((s << 10) & 0xffffffff) ^ \
        ((s << 18) & 0xffffffff) ^ ((s << 24) & 0xffffffff)
    return x0 ^ l

纯 Python 版本跑起来有多慢？我测过，加密 1MB 数据大概要 3-5 秒。这在生产环境肯定不行，但用来验证算法正确性足够了。

4.2 性能优化技巧：从秒级到毫秒级

纯 Python 慢在哪？循环和位运算。Python 的 for 循环效率很低，32 轮迭代还好，但每轮里还有 4 次 S 盒查表、1 次线性变换，加起来就是 128 次查表 + 32 次 L 变换。数据量一大，性能就崩了。

我踩过几个坑，分享给你：

• 用 PyPy 代替 CPython：PyPy 的 JIT 编译器能把循环优化得很好，我试过，性能提升 3-5 倍。但要注意，PyPy 对某些 C 扩展不兼容。
• 减少函数调用：把轮函数内联到主循环里，避免每次调用开销。别小看这个，能省 10%-15% 的时间。
• 用局部变量：把 S_BOX、轮密钥等全局变量赋值给局部变量，Python 访问局部变量比全局变量快得多。

举个例子，优化后的循环体大概长这样：

def sm4_encrypt_block(plaintext, rk):
    x0, x1, x2, x3 = plaintext
    sbox = S_BOX  # 局部变量
    for i in range(32):
        tmp = x1 ^ x2 ^ x3 ^ rk[i]
        s = (sbox[(tmp >> 24) & 0xff] << 24) | \
            (sbox[(tmp >> 16) & 0xff] << 16) | \
            (sbox[(tmp >> 8) & 0xff] << 8) | \
            (sbox[tmp & 0xff])
        l = s ^ ((s << 2) & 0xffffffff) ^ ((s << 10) & 0xffffffff) ^ \
            ((s << 18) & 0xffffffff) ^ ((s << 24) & 0xffffffff)
        x0, x1, x2, x3 = l, x0, x1, x2
    return (x3, x2, x1, x0)  # 反序输出

这些优化做完，1MB 数据能从 3 秒降到 1 秒左右。但说实话，还是不够。真正的杀手锏是查表法。

4.3 查表法加速：把计算变成查表

查表法的核心思想很简单：把 S 盒替换和线性变换 L 合并成一张大表。你想想看，S 盒输出 8 位，L 变换是 32 位运算，那能不能提前算好所有可能的组合？

具体做法是：对每个可能的 8 位输入，提前计算 S 盒输出经过 L 变换后的 32 位结果。这样，原来需要 4 次 S 盒查表 + 1 次 L 变换，现在只需要 4 次查表 + 3 次异或。

我画了张图，帮你理解这个流程：

查表法的代码实现也很简洁：

# 预计算 T 表
T_TABLE = []
for i in range(256):
    s = S_BOX[i]
    t = s ^ ((s << 2) & 0xffffffff) ^ ((s << 10) & 0xffffffff) ^ \
        ((s << 18) & 0xffffffff) ^ ((s << 24) & 0xffffffff)
    T_TABLE.append(t)

def sm4_round_t(x0, x1, x2, x3, rk):
    tmp = x1 ^ x2 ^ x3 ^ rk
    t = T_TABLE[(tmp >> 24) & 0xff] ^ \
        ((T_TABLE[(tmp >> 16) & 0xff] >> 8) | (T_TABLE[(tmp >> 16) & 0xff] << 24)) ^ \
        ((T_TABLE[(tmp >> 8) & 0xff] >> 16) | (T_TABLE[(tmp >> 8) & 0xff] << 16)) ^ \
        ((T_TABLE[tmp & 0xff] >> 24) | (T_TABLE[tmp & 0xff] << 8))
    return x0 ^ t

你可能会问：为什么还要移位？因为 T 表是按字节对齐的，但实际输入是 32 位，每个字节的位置不同，需要循环移位对齐。这个细节我当初也搞错过，查了半天才发现是移位方向反了。

4.4 查表法的进阶技巧

查表法虽然快，但有个问题：内存占用。4 张 T 表，每张 256 个 32 位整数，一共 4KB。这在 PC 上不算什么，但在嵌入式系统里可能是个负担。

我遇到过这种情况：一个 IoT 设备，RAM 只有 64KB，还要跑 SM4。怎么办？用 1 张 T 表 + 循环移位。虽然每次查表后要多做一次移位，但内存占用从 4KB 降到 1KB。对于资源受限的场景，这个取舍很值得。

另外，查表法对缓存友好。T 表只有 1KB，完全能塞进 L1 缓存。你想想看，32 轮迭代，每轮 4 次查表，总共 128 次查表，全在缓存里命中，速度能不快吗？

最后，分享一个我自己的经验：查表法不是银弹。如果你的数据量很小（比如每次只加密几个字节），查表法的初始化开销反而会拖慢性能。这时候，纯位运算版本可能更快。所以，根据场景选方案，别盲目追求极致优化。