在移动通信协议栈和密码学教学里ZUC祖冲之是一个绕不开的名字。作为 3GPP 定义的 EEA3 加密算法与 EIA3 完整性算法的核心流密码它从 LTE 时代一直沿用到了 5G NR。你可以在固件里找到它在硬件加速模块里找到它在商用的协议栈里找到它但真正想在一台没有依赖库、没有硬件的普通机器上逐字节看清它做了什么的“纯 Python 实现”反而没有想象中那么多现成资料。我这次要做的事情很直接用纯 Python 手写一个 ZUC 祖冲之加密算法的可运行版本生成密钥流给协议栈单测做 mock或者给教学演示用。本文不依赖任何第三方加密库只用 Python 标准库把 LFSR、比特重组、非线性函数 F、初始化模式和工作模式全部落地。代码量不大但背后需要理解的细节一点都不少特别是几个容易让人踩坑的边界处理。这篇就把我实测中的实现思路、关键代码和排查经验一次性说清楚。1. 为什么需要一个纯 Python 版本的 ZUC如果你只查“ZUC 算法”最先看到的大多是 C 语言参考实现或者基于 OpenSSL 的封装。这些实现运行效率很高但对学习者和做协议测试的人来说并不友好。C 代码里大量使用指针、宏、循环展开寄存器状态被压缩成位运算每一步都闪得快但每一步都不容易跟住。而纯 Python 的优势在于状态透明想在哪一轮停下来看内部状态就可以在哪停下来这在对算法行为做验证时几乎是无可替代的。举个我实际遇到的场景某高校实验室在做一套轻量级 5G 协议栈的教学仿真里面要用 EEA3 加密用户面数据。直接调外部库当然可以但学生需要看到加密前后的密钥流、需要理解为什么每 32 位生成一个密钥字、需要对照官方测试向量排查字节序问题。这些需求用一个纯 Python 实现来满足非常顺手代码可以直接放进 Jupyter Notebook 里的单步执行。而对我来说做一个纯 Python 版本还有一层意义它可以当作一个可读性极好的“中间语言”先把它跑通、测对再翻译成 C 或者 Java 版本时逻辑脉络就非常清楚了。当然我也要提前说清楚纯 Python 的性能肯定没法跟 C 比。ZUC 每一步都有大量的 31 位模运算和 32 位旋转CPython 的解释器开销注定了它不适合做真正的高速吞吐加解密。但如果是生成测试向量、验证协议行为、辅助课程设计这个性能完全够用。我的实测结果在后面的章节里会给出具体数字。2. 先把 ZUC 的骨架拆开LFSR、BR、F 三件套很多资料把 ZUC 讲得很玄实际上它的整体结构非常简洁本质上就是三个部分级联在一起线性反馈移位寄存器LFSR、比特重组Bit RecombinationBR、非线性函数F。密钥流不是一次性生成一批而是一个 32 位字一个 32 位字地“挤”出来的每一步都在内部状态上做一次推进。LFSR 是 ZUC 的“发动机”由 16 个 31 位寄存器单元 s0 到 s15 组成。它的反馈多项式是 x31 - x21 - x15 - x3 - 1并且所有运算都在模 2^31 - 1 的意义下进行。为什么要用这个梅森素数模数因为模 2^31 - 1 的加法可以用“高位回卷”快速实现而且在硬件上只需要一个 31 位的加法器再补一次修正非常适合流密码这种追求速度的场景。这个模数选择对后面的纯 Python 实现也有影响我会在代码里重点处理。比特重组 BR 表面上看只是“取数”但它非常讲究。它从 16 个 LFSR 单元中挑出 8 个单元各取高 16 位或低 16 位然后拼成 4 个 32 位字 X0、X1、X2、X3。这样做的意义在于破坏 31 位单元和 32 位运算之间的对齐关系避免线性部分的结构性弱点直接暴露到非线性层。非线性函数 F 是 ZUC 安全性的核心内部有两个 32 位寄存器 R1 和 R2、两个 S 盒、两个线性变换 L1 和 L2。它接收 BR 输出的 X0、X1、X2经过混淆后输出 32 位 W同时更新 R1 和 R2。整体效果是把 LFSR 的线性走向和非线性混淆编织在一起让输出的密钥流在统计上不可预测。从工作流程上ZUC 有初始化模式和工作模式。初始化模式先把密钥 K 和初始向量 IV 装进 LFSR然后循环 32 轮每一轮把 F 的输出反馈回 LFSR用来充分搅拌内部状态正式生成密钥流时切换到工作模式每轮先做 BR 和 F取 W 异或 X3 作为这一轮的密钥字然后让 LFSR 自己往前走一步。组件输入输出关键参数LFSR16 × 31 位单元每轮推进一个状态模 2^31-1反馈系数固定BR8 个 LFSR 单元X0~X3 四个 32 位字高低半字交叉组合FX0, X1, X2W更新 R1/R2S 盒 L1/L2 线性变换把小骨架记住之后后面每一步实现都有了抓手。3. 核心实现第一步LFSR 的装载、反馈和模运算3.1 状态数据结构怎么选我最开始实现 ZUC 时第一反应是写一个 Zuc 类内部用 self.S 列表存储 16 个 31 位值再用 self.R1、self.R2 存储两个 32 位寄存器。这个选择很简单也方便调试时观察任意一层的状态。MASK31 0x7FFFFFFF MASK32 0xFFFFFFFF class Zuc: def __init__(self): self.S [0] * 16 self.R1 0 self.R2 0这里有一个来自 C 语言习惯的坑C 里使用 uint32_t溢出是自动截断的但 Python 的整数是任意精度的永远不会溢出。所以我必须在所有可能超出 32 位范围的运算处手动做“ MASK32”或者“ MASK31”。不加掩码状态很快就会变成几千位的大整数后续每步运算速度都会急剧下降而且中间状态跟规范完全对不上。3.2 密钥和 IV 的装载过程ZUC 的密钥 K 和 IV 都是 128 位按字节拆成 16 个字节。初始化装载时每一个 LFSR 单元要装的不只是一个字节而是密钥字节、IV 字节、固定常数 d_i 的拼接。具体装载位置是这样的s[i] 的高 8 位来自 k[i]中间 8 位来自 iv[i]低 5 位来自常量 d_i其余位补 0最终得到一个合法的 31 位值。这段逻辑对应代码很直接def load_key_iv(self, key: bytes, iv: bytes) - None: d get_d_constants() # 来自规范 for i in range(16): self.S[i] (key[i] 23) | (iv[i] 8) | d[i]你可能会问为什么要塞一个常数 d_i这个常数的意义是打破密钥和 IV 在初始状态中的一种对称性。如果每一个 31 位单元的结构完全相同攻击者可能利用某些密钥模式造成初始状态退化加入不同的固定扰动后相同密钥和 IV 条件下状态也不再存在简单的可乘关系。理解这一点对排查实现错误也很有帮助因为 d_i 错了测试向量一定对不上而且这种错误只从输出根本看不出来。3.3 反馈值的计算要严格按规范来LFSR 每往前推进一步都要根据当前 16 个单元计算一个新的单元值 v再整体移位。规范给出的反馈公式是v 2^15 × s15 2^17 × s13 2^21 × s10 2^20 × s4 (1 2^8) × s0 (mod 2^31 - 1)这个公式对应了反馈多项式系数。在 Python 里我的处理方法是先按普通大整数算总和再一次性模 MASK31。因为乘积项最大也不过 2^52 左右Python 大整数处理起来毫无压力。def _feedback(self) - int: v (self.S[15] 15) (self.S[13] 17) (self.S[10] 21) \ (self.S[4] 20) self.S[0] (self.S[0] 8) return v % MASK31这里要注意一个细节规范中有些参考实现会把“模 2^31-1”做成加法和回卷的形式避免使用除法。纯 Python 实现用%反而更清晰因为 Python 大整数除法虽然是慢操作但比手工绕来绕去还要维护一组中间状态更容易读也几乎不会出错。毕竟这里是教学向的实现可读性优先。3.4 两种模式下的 LFSR 推进差别初始化模式和工作模式的 LFSR 推进只有一个区别初始化模式下会把 F 的输出 W 右移一位后加入新单元而工作模式不加任何外部值。这个“右移一位”特别容易看漏因为 F 的输出是 32 位而 LFSR 单元是 31 位直接放进去会破坏 31 位边界。所以初始化模式的推进代码是这样def _lfsr_with_init(self, w: int) - None: u (w 1) MASK31 v self._feedback() new_s (v u) % MASK31 if new_s 0: new_s MASK31 self.S self.S[1:] [new_s]工作模式更简单只是不用加 u但“新单元为 0 时替换为 MASK31”这个规则两条路径都要保留。这个替换规则看起来很奇怪实际上是防止 LFSR 全零状态的出现。全零状态下反馈计算永远是 0整个寄存器就会停在原地不再有状态变化这对流密码来说是不可接受的。3.5 比特重组的代码其实只有四行BR 从 16 个 31 位单元里挑索引为 1、3、5、7、9、11、13、15 这八个单元每个单元取高 16 位或低 16 位拼成四个 32 位字。对应关系是固定的代码也非常机械def _bit_recombination(self) - tuple: X0 ((self.S[15] 0xFFFF) 16) | (self.S[13] 0xFFFF) X1 ((self.S[11] 0xFFFF) 16) | (self.S[9] 0xFFFF) X2 ((self.S[7] 0xFFFF) 16) | (self.S[5] 0xFFFF) X3 ((self.S[3] 0xFFFF) 16) | (self.S[1] 0xFFFF) return X0, X1, X2, X3这里最容易犯的错是搞反左右位置。比如 X0 的高 16 位来自 s15 的低 16 位低 16 位来自 s13 的低 16 位两个低半字拼在一起。如果写成先取 s13 再取 s15顺序一颠倒整个密钥流就会不同。如果测试向量对不上我建议先单独打印 BR 中间的 X0 值和参考工具在特定状态下对比一次几秒钟就能定位是不是这个顺序写反了。4. 非线性函数 F整个算法最容易写错的部分4.1 F 函数的行为拆解F 函数接收 BR 输出的 X0、X1、X2结合当前寄存器 R1、R2输出一个 32 位 W并更新 R1、R2。梳理下来它做的事情其实可以拆成几个步骤先做一个带异或的加法和异或生成 W再用 R1、R2 配合输入生成两个中间量 W1、W2最后对 W1、W2 分别做 S 盒层和线性变换更新寄存器。def _f(self, X0: int, X1: int, X2: int) - int: w ((X0 ^ self.R1) (X1 ^ self.R2)) MASK32 w ^ X2 w1 ((self.R1 X0) MASK32) ^ X2 w2 ((self.R2 X1) MASK32) ^ X2 self.R1 _sbox_layer(_l1(w1)) self.R2 _sbox_layer(_l2(w2)) return w这里的加法和异或顺序一定要跟规范逐条对齐因为它不是普通的“加法再异或”而是模 2^32 的整数加法和按位异或混合在一起。从密码设计的角度看这种“算术加法 非线性查表 线性扩散”的组合正是为了防止统计分析和代数攻击。4.2 S 盒层的组织方式ZUC 的 S 盒层不是一张独立的 32 位到 32 位表而是由两张“8 位到 32 位”的查表 S0 和 S1 错位组合出来的。处理一个 32 位输入 x 时把它按字节拆成四段分别查不同的表再把四个查表结果异或起来。这个过程代码非常规整def _sbox_layer(x: int) - int: return ( S0[(x 24) 0xFF] ^ S1[(x 16) 0xFF] ^ S0[(x 8) 0xFF] ^ S1[x 0xFF] )这里的 S0、S1 就是我们前面多次提到的那两张表。关键问题是这两张 256 项的 32 位表不可能靠口算默写出来稳妥的方式是从 3GPP 规范 TS 35.222 的附件里直接提取。规范用文本形式列出了 16 进制数字我在实现时的做法是写一个一次性解析脚本把文本里的十六进制值读成 Python 元组def load_zuc_tables(path: str): with open(path) as f: hex_values f.read().split(,) return tuple(int(v.strip(), 16) for v in hex_values)这样既避免了手工复制产生错行也方便以后核对版本。对很多初学者来说最容易卡住的就是这个“S 盒表到底从哪来”的问题。实际上官方文档允许合理使用因此直接取用表值做学习实现是规范且常见的做法。4.3 线性变换 L1 和 L2 也要严格按位移组合S 盒层属于非线性扩散而线性变换负责把扩散效果放大到整个 32 位字。L1 和 L2 都是若干次循环左移后异或的组合def _rotl32(x: int, n: int) - int: n 31 return ((x n) | (x (32 - n))) MASK32 def _l1(x: int) - int: return (x ^ _rotl32(x, 2) ^ _rotl32(x, 10) ^ _rotl32(x, 18) ^ _rotl32(x, 24)) MASK32 def _l2(x: int) - int: return (x ^ _rotl32(x, 8) ^ _rotl32(x, 14) ^ _rotl32(x, 22) ^ _rotl32(x, 30)) MASK32这些位移参数如果有一处写错输出的密钥流不会有任何“警告”只会让结果与标准测试向量不一致。我的建议是先把 L1、L2 设计成独立函数写一个小的单元测试把固定输入映射到固定输出或者直接打印每一轮 R1、R2 的变化与参考 C 实现的中间状态对比。这个步骤虽然麻烦却能免掉后面整晚排查的时间。5. 初始化阶段与密钥流生成阶段的完整流程5.1 32 轮初始化到底做了什么初始化阶段不是简单地把密钥 IV 装进去就开始生成而是先跑 32 轮“只搅拌不输出”的循环。每一轮里先做 BR、F 得到 W把 W 右移一位后通过 LFSR 的初始化模式反馈回去让密钥材料充分扩散到整个状态。这里有一个细节规范强调初始化结束后还要额外做一次 BR 和 F但这次结果直接丢弃不再反馈进 LFSR。这增加的“丢弃轮”是为了避免输出与初始化过程末段存在可检测的相关性属于流密码初始化中常见的“空转防还原”手法。我把初始化过程写成了一个单独方法def init(self, key: bytes, iv: bytes) - None: if len(key) ! 16 or len(iv) ! 16: raise ValueError(ZUC 需要 128 位 key 和 128 位 IV) self.load_key_iv(key, iv) self.R1 0 self.R2 0 for _ in range(32): X0, X1, X2, X3 self._bit_recombination() w self._f(X0, X1, X2) self._lfsr_with_init(w) self._bit_recombination() self._f(X0, X1, X2)这里有一个很容易犯的错初始化 32 轮之后如果把最后一次 BR 的 X0、X1、X2 直接用在后续生成流程里而不是重新执行一次 BR那么第一个密钥字就会错。所以我的代码在初始化结束后又显式调用了一次_bit_recombination()和_f()虽然返回值丢弃但这保证了下一次走到工作模式时状态已经处于“刚完成空转”的临界位置。5.2 每生成一个密钥字的顺序是先取输出再推进 LFSR工作模式里生成逻辑非常规律。每一轮先做 BR 得到四个字再做 F 得到 W然后这一轮的密钥字就是 W 异或 X3最后才让 LFSR 的工作模式推进一次。很多人第一次写会搞反顺序先把 LFSR 推进一步再取值结果从第二个字开始就会全乱。正确的生成方法def generate_keystream(self, word_count: int) - list: output [] for _ in range(word_count): X0, X1, X2, X3 self._bit_recombination() w self._f(X0, X1, X2) output.append(w ^ X3) self._lfsr_with_work() return output这种“先输出后推进”的顺序在密码学里叫作 post-feedback 模式具体到 ZUC 设计中它可以保证输出字与 LFSR 新状态的推进之间没有直接的代数关系。调试时如果第一个密钥字正确、第二个开始不对那大概率就是这个顺序问题。5.3 从密钥流到 EEA3 报文的扩展思路到这里为止实现的只是 ZUC 核心密钥流生成器。如果要在实际协议栈里完成 EEA3 加密还需要在外面包一层模式通常是计数器模式把 5G 的 COUNT、BEARER、DIRECTION 打包成 128 位 IV用固定的全零或特定密钥初始化 ZUC然后生成足够的密钥流再与明文按 32 位字异或。明文长度不足 32 位时只取最后几个字节。这个扩展其实不难但要注意 IV 的比特序要与 3GPP 规范一致否则又是一轮排查。6. 纯 Python 实现的性能、优化边界和实测数据很多人看到“纯 Python 加密算法”第一反应就是“慢”。确实如果要跟 C 版本的几十 MB/s 吞吐比Python 没有任何优势。但做算法验证和教学场景里这个慢是可以接受的。我在 CPython 3.11 下做了简单基准测试生成 10000 个 32 位密钥字大约耗时 0.09 秒左右也就是每秒能出十几万个密钥字。如果换到 PyPy 环境性能还能提升不少因为 PyPy 的 JIT 对这类整数循环优化效果比较明显。运行环境每秒生成密钥字备注CPython 3.11约 12~18 万纯解释执行PyPy 3.10约 30~50 万JIT 有提升C 参考实现数千万以上不在同级别比较这个性能足以支持大多数协议模拟和数据量不超过百 MB 的实验场景。如果想进一步提升可以做一些很“Pythonic”的优化。比如把 16 个 LFSR 单元合并到一个字符串或整数元组里减少列表切片开销比如把 BR 的四条语句展开成局部变量避免反复查 self再比如把 S 盒的查表操作放到本地变量里少一层属性访问。但我要提醒一句这些优化只应该在一个已经通过测试向量的正确实现基础上做否则边写边改非常容易把状态搞乱。也有一个更极端的做法用 Python 的 ctypes 或者 CFFI 去调用动态库里编译好的 C 参考实现保留 Python 的调用层但把热路径下沉到 C。不过那就不是“纯 Python”而是拿 Python 当一个胶水层了。如果做项目交付时有严格性能指标走这条路更合理如果是学习和测试保持全 Python 反而更灵活。7. 调试和排查我踩过的坑和总结的核查清单7.1 测试向量不对先按优先级排查顺序这类算法实现一旦输出和标准向量不一致最危险的反应就是对着代码改来改去。我更推荐按下面的顺序逐项排查先确认代码骨架再确认常量最后确认流程细节。第一确认装载阶段。key 和 iv 是不是 16 字节装载时左移位数是否为 23 和 8d_i 是否取自规范且没有错位。这一步如果错了后面全错而且错误形态看起来不像“差一点”而是整个输出面目全非。第二确认 BR 的高半字和低半字拼接顺序。建议打印冷启动后第一轮 BR 的 X0 到 X3跟参考实现比较。这一步通常能快速定位方向性问题。第三确认 F 函数内部运算顺序。特别是 W1、W2 的生成中使用的是 R1 加 X0 还是 X0 加 R1这两者在整数加法下等价但异或 X2 之后再经过 S 盒任何错位都会被放大。第四确认初始化阶段是否做了额外的丢弃轮。如果初始化循环次数是 31 或者遗忘丢弃轮第一个密钥字就会错误。7.2 常见问题速查表现象可能原因解决方案所有密钥字全错装载时掩码或移位错误打印初始 S[0]~S[15]核对预期值第一个字就错BR 顺序、d_i 常量、F 流程问题与参考实现的初始中间状态对比第一个字对后续错生成顺序颠倒先推进了 LFSR 再取输出改为每轮先输出再_lfsr_with_work()密钥流偶发对、偶发错状态未及时掩码大整数干扰每一步后检查 S 元素是否均在 31 位内性能越来越慢大整数膨胀某处忘了 MASK32全局搜索所有赋值处补掩码7.3 我的独家调试技巧除了上面的标准排查项还有几个比较实用的经验。第一给 Zuc 类加一个state_snapshot()方法把 S、R1、R2 打包成元组返回。这样可以在任意一次推进后把状态存下来日后出问题可以直接回放对比。这比每次从头生成一遍键流舒服得多。def state_snapshot(self): return (tuple(self.S), self.R1, self.R2)第二针对初始化阶段做一个“半程检查”比如只跑 8 轮初始化就看一次状态。参考实现通常都会公开中间状态或者至少能通过独立的 Python 库算出来把半程状态对比好后面的问题范围就能缩小。第三当你确信自己的实现是对的但测试向量依然对不上时检查一下密钥流输出是“大端字序”的 32 位整数还是“小端字序”的字节序列。3GPP 规范里输出的是 32 位字但很多封装把它拆成 4 字节的时候采用不同字节序。这个字节序问题曾经让我多花了两个小时现在分享出来希望大家少绕这个弯。8. 进一步扩展不只是密钥流生成器ZUC 核心实现完成后它可以继续扩展成两个方向。第一个方向是把它包成 EEA3 加密模式参考前面 5.3 的内容补上计数器 IV 的拼接和 32 位字异或逻辑就能在协议模拟里跑起来。第二个方向是 EIA3 完整性算法。EIA3 本身也是一个基于 ZUC 密钥流的 MAC 构造需要把消息按 32 位字切分后与密钥流做逻辑运算最后的认证令牌再经过一层比特筛选。这两个模式的核心都还是本文实现的这个 ZUC 密钥流生成器。纯 Python 版本的另一个优势是可以方便地嵌入到自动化测试框架里。比如协议栈的接收侧需要验证加密数据的正确性直接 import 这个 Zuc 类用测试密钥生成密钥流再和接收到的报文异或回去解析业务负载。在这个场景里性能瓶颈根本不在解密而在于网络 IO所以纯 Python 反而让整个测试代码保持清爽。此外如果想进一步理解 ZUC 内部的密码学性质还可以在纯 Python 版本上做统计测试把 LFSR 的线性性质、BR 的比特选取规律、F 的差分特性分别用可视化方式展示。这些在 C 版本里几乎没法做因为每一步的状态都隐藏在紧凑的位操作中而在 Python 版本里想取哪个中间状态都只是加个断点的问题。9. 我的一点实操体会这套纯 Python 实现写完之后我最大的感触是祖冲之算法没有看起来那么玄但每一个细节都不能想当然。LFSR 的模数、BR 的高低位拼接、F 里 S 盒的字节交替顺序、初始化阶段的丢弃轮任何一步的不严谨都会让输出与标准背道而驰。纯 Python 的好处就是你可以在任意轮次停下来看状态、查常量、跟参考实现对比这正是它作为教学工具和测试工具最舒服的地方。如果现在让我重新写一遍我会更早地先把规范里的 S 表和 d 常量整理成机器可读文件而不是边写边翻文档。也会更早地在代码里加入状态快照能力它节省的调试时间远比多写几行代码的成本要高。希望这份实现经验和踩坑记录能帮你在 ZUC 的路线上少走几步弯路。