基于FPGA 的ZUC-256 算法实现架构分析

贾旭光，徐 颂，白海通，邓 超

（1.华北计算机系统工程研究所，北京 100083；2.中电智能科技有限公司，北京 102209；3.中国人民解放军陆军，北京 100044）

0 引言

祖冲之密码(ZUC)算法为我国自主设计的密码算法，主要包含流加密算法和完整性算法。2011 年，ZUC算法被3GPP 批准成为4G LTE 国际密码算法标准。近年来，随着新一代移动通信5G-NR 标准的确定，我国也在大力推广5G 通信相关的研发和产业化。3GPP 在会议中明确5G 通信中使用128 bit 和256 bit 密钥的对称加密算法，并保持向4G 兼容。为此，我国在ZUC-128 的基础上提出了ZUC-256 算法。ZUC-256 由128 bit 密钥升级为256 bit 密钥，提供消息加密和认证功能，可广泛应用于5G 移动通信的安全保护。目前针对ZUC 算法的研究已经有多种快速软件实现和硬件优化实现方案[1-5]，本文通过分析ZUC 算法架构和工作流程，提出一种软硬协同实现方案，经验证，相比单硬件实现有较大的性能提升。

本文将内容分为3 个部分，第一部分为背景技术介绍，分析了ZUC-256 算法结构，并对比了ZUC-256 和ZUC-128 的差异；第二部分为FPGA 实现，首先分析了ZUC 算法涉及的运算单元，重点介绍了模231-1 加法器的实现方式，提出了4 种6 输入模231-1 加法器实现架构，然后通过分析关键路径以及引入流水线架构，提出了全硬件和软硬件协同架构实施方案，最后对不同实现架构进行了性能分析；第三部分为总结与展望。

1 背景技术介绍

首先分析了ZUC-256 算法的组成架构，仔细讨论了ZUC-256 与ZUC-128 算法差异，最后提出了一种兼容ZUC-256 和ZUC-128 算法的硬件实现架构。

1.1 ZUC-256 算法介绍

ZUC-256 算法主要包含三部分：线性反馈移位寄存器（Linear Feedback Shift Register，LFSR）、比特重组（Bit Reorganization，BR）和非线性函数（Finite State Machine，FSM）[6]。ZUC 算法运行过程包含两个阶段，初始化和密钥生成阶段。通过模式选择开关选择系统工作在初始化模式或密钥生成模式，ZUC 算法结构图如图1所示。

图1 ZUC 算法结构图

初始化阶段：将密钥和初始向量依次装入相应寄存器，进行33 轮运算，初始化阶段无输出。下半部分的输出W反馈到多输入加法器中。

密钥生成阶段：该阶段与初始化阶段大部分结构一致，输出W与Z直接异或生成密钥流输出。

1.2 ZUC-256 与ZUC-128 差异对比

ZUC-256 与ZUC-128 算法架构完全一致，保持了良好的向下兼容性。两者的差异仅仅为算法架构的输入密钥由128 bit 扩展为256 bit，初始向量由128 bit 扩展为184 bit。另外，初始化阶段的载入的初始向量和密钥也不相同。

通过以上分析，可以很容易地设计一种硬件实现架构同时运行ZUC-256 和ZUC-128 算法。

2 算法架构FPGA 实现分析

ZUC-256 算法涉及的运算主要有模232加法、模231-1加法、异或和比特连接等运算。模232加法可通过截取加法器输出的低32 位实现，比特连接不占用FPGA 资源。运算最为复杂的部分为模231-1 加法运算。接下来，将分别讨论2 输入和ZUC 算法用到的6 输入模231-1 加法器的实现架构。

2.1 2 输入模加法器架构实现

2 输入模231-1 加法器实现主要有3 种方式:(1)方式1如图2 所示，直接用两个31 bit 加法器级联实现，第一个加法器连接两个输入，第二个加法器输入为第一个加法器的进位与输出和。(2)方式2 如图3 所示，用两个加法器（一个半加器和一个全加器）和一个选择器实现，选择器根据进位选择结果为半加器还是全加器的输出。方式2 相比方式1，延迟由两个加法器延迟减为一个加法器加一个选择器延迟，因而能够提升工作频率。(3)文献[7]提到第3 种实现方式，如图4 所示，该方式占用两个加法器和一个选择器，延迟最高为两个加法器和一个选择器。方式3 在资源占用上差于方式1，延迟上差于方式2，因而不推荐使用。

图2 模231-1 加法器方式1

图3 模231-1 加法器方式2

图4 模231-1 加法器方式3

2.2 多输入模加法器架构实现分析

加法器结构的FPGA 实现通常有行波进位加法器（Ripple Carry Adder，RCA）、超前进位加法器（Carry Lookahead Adder，CLA）和进位保存加法器（Carry Save Adder，CSA）等方式。

RCA 行波进位加法器结构简单，仅需要级联全加器即可实现，缺点是高位运算需要等待低位运算结束才能开始，延迟很高。

CLA 超前进位加法器，进位部分采用专用逻辑电路设计，减小延迟，然而随着加法器输入位宽的增加，超前部分的电路结构也越来越复杂，不适合高位宽加法器设计。

CSA 进位保存加法器，将和与进位部分单独运算，最后将和与进位相加得到输出结果，适合FPGA 实现。

对于6 输入加法器，如果用直接加法器实现需要5个2 输入加法器实现，延迟为n-1 个加法器延迟。采用加法树结构，延迟减少为log2(n)个加法器。

ZUC-256 算法中加法器的输入位宽为31 bit，RCA结构的高延迟和CLA 结构的复杂的进位逻辑不适合本算法。本文以CSA 加法器和普通加法器（由综合工具决定具体实现策略）作为基本单元，结合加法树结构，提出了4 种6 输入加法器结构，即全部采用普通加法器或CSA 加法器以及同时使用普通加法器和CSA 加法器的混合结构，如图5 所示。

图5 6 输入加法器结构图

方案a 包含三级加法树，加法单元全部采用普通加法器，每过一级，加法单元位宽加一，第三级加法器的输出分为两部分，低31 位和剩余高位接入上节提到的2 输入模231-1 加法器得到最终输出结果。方案b 包含四级加法树，前三级采用CSA 加法单元，第四级采用普通加法器单元，输出同样接入2 输入模231-1 加法器。方案c和方案d 为混合结构，加法单元同时采用CSA 和普通加法器。4 种方案的实现结果将在下文全硬件和软硬件结合方案中阐述。

2.3 关键路径分析

通过分析ZUC-256 算法架构，可以看出关键路径主要分为LFSR 和FSM 两部分。

2.3.1 LFSR

LFSR 的数据处理路径为:

（1）初始化阶段

①V=(215·S15+217·S13+221·S10+220·S4+(1+28)·S0) mod(231-1)

②若V=0，则V=231-1

③S16=(V+W) mod (231-1)

④若S16=0，则S16=231-1

⑤(S15,S14,…,S1,S0)＜=(S16,S15,…,S2,S1)

（2）工作阶段

①S16=(215·S15+217·S13+221·S10+220·S4+(1+28)·S0)mod (231-1)

②(S15,S14,…,S1,S0)＜=(S16,S15,…,S2,S1)

上述数据处理包含两部分，加法和检查结果是否为零。LFSR 寄存器S15的值必须确保在集合{1,2,…，231-1}中。文献[8]指出，模231-1 加法器的输入只要有一个不为零，输出就不为零。LFSR 的所有寄存器初始值均不为零，即使FSM 的输出结果为零，通过模231-1 加计算得到的S16也不为零，因此可以省掉检测输出是否为零的步骤，进而节省了2 个选择器。

省略掉选择器后，可以对ZUC 算法架构进一步优化。以加法树方案a 为例，优化后的LFSR 部分数据流程图如图6 所示。

图6 LFSR 关键路径图

假设2 输入模231-1 加法器采用方式2，则关键路径延迟为6 个加法器+2 个选择器。关键路径太长，会造成工作频率Fmax无法提升，可以通过在中间加入寄存器减小关键路径，寄存器的引入会造成密钥流输出多一个时钟节拍。为了满足每个时间节拍均输出密钥流，同时在中间加入寄存器减小关键路径尽可能大的提升Fmax，需要引入流水线结构。

文献[9]-[10]均提出了ZUC 算法使用流水线架构的思路，文献[9]采用5 级流水，关键路径仅为一个模231-1加法器，然而，需要耗费大量寄存器资源作为中间缓存；文献[10]采用2 级流水，寄存器单元加在图6 的虚线4处，本文将该流水线架构进一步优化，可在图6 中的1～4虚线处加入寄存器缓存单元。由于2 输入模231-1 加法器延迟为一个加法器加上一个选择器，结合理论分析，在虚线3 处加入寄存器能最大程度减小关键路径延迟。经Vivado 软件综合实现验证，实际结果与理论分析相符。

2.3.2 FSM

FSM 部分数据处理流程：

（1）W=(X0⊕R1+R2) mod (232)

（2）W1=(R1+X1) mod (232)

（3）W2=R2⊕X2

（4）R1=S(L1(W1L||W2H))

（5）R2=S(L2(W2L||W1H))

其中，符号⊕表示按位异或运算，符号||表示字符串拼接，符号mod 表示取模运算。L1、L2采用和ZUC-128 相同的MDS 矩阵[11]。S函数也与ZUC-128 采用的S-盒相同。S-盒可以用ROM 实现或查找表实现，用ROM 实现会占用一个时钟周期，用查找表实现会占用大量的slice资源。同样，对于R1和R2，既可以使用寄存器也可以使用wire 类型实现。同时采用有限状态机和ROM 的方式实现FSM 部分会只占用两个时钟周期，缩减为一个时钟周期的方式为用组合逻辑实现S-盒，或用组合逻辑实现R1与R2。

2.4 全硬件和软硬件协同架构

赛灵思创新性地将ARM 硬核引入FPGA 器件中，将整个FPGA 分为PS 和PL 两部分，并提供多种PS 和PL间的高速总线作为连接通道。Zynq-7000 系列FPGA 一经推出，便受到市场追捧。嵌入式和可编程逻辑的结合，可作为ZUC-256 算法软硬件协同实现的硬件平台。Zynq-7000 系列FPGA，PS 端为双核ARM A9，最高主频可达1 GHz，PL 端根据低端和高端分别配置与Artix-7或Kintex-7 系列同等规格的FPGA 资源。Zynq-7000 器件提供3 种AXI 总线满足PS 和PL 通信需求，分别为面向高性能地址映射通信的AXI4 总线和面向高速路数据流通信的AXI4-Stream 总线以及轻量级的AXI4-Lite 总线。全硬件架构是指仅用PL 即逻辑资源实现全部ZUC-256 算法，而软硬件协同架构则通过AXI4-Lite 总线同时使用PS 和PL 实现ZUC-256 算法。

在上一节中，详述了LFSR 和FSM 部分的硬件实现，BR 部分不占用资源，除此之外，仅剩寄存器初始化单元模块，ZUC-256 和ZUC-128 寄存器初始化单元不同，通过选择器选择不同的初始化单元即可实现一种硬件架构兼容两种算法。

初始化单元仅在初期运行阶段使用，随着ZUC-256密钥的增大，初始化单元占用大量的逻辑单元，因此可以将该部分放在软件端进行。软件端运行完毕后将结果载入S0-S15寄存器和R1、R2寄存器，即可继续执行输出密钥流阶段。初始化阶段放在软件端，软硬件协同架构，也可以很容易地实现ZUC-256 和ZUC-128 复用。另外，软硬件协同架构LFSR 部分结构进一步缩减掉一个加法器和一个选择器，从而进一步减小关键路径。

软件端可采用前文提到的ZUC-256 算法快速软件实现方法。FPGA PS 端运行初始化阶段完毕后，依次通过AXI4-Lite 总线写入PL 端的R1、R2和S0～S15寄存器，最后一个寄存器S15写入后拉高load 信号，指示PL 端开始运行密钥输出阶段。软硬件协同架构图如图7 所示。

图7 ZUC 软硬件协同架构图

以密钥和初始向量均为零为例，初始化阶段运行结束后R1、R2和S0～S15寄存器依次为 0xa870958e，0x783f6cd9,0x7307b910,0x18826230,0x02177063,0x47acb519,0x20757378,0x245ed478,0x2c3cd51e,0x29a8a61e,0x03fe3241,0x5f04fb97,0x578905be,0x20ffcf8e,0x6e895b73,0x62b5d1ad,0x538967b5,0x1d7307be。将上述值加载到相应寄存器运行仿真图如图8 所示。

图8 ZUC-256 软硬件协同仿真图

从图8 中可以看出，在寄存器载入后的第二个时钟，密钥流data 开始输出，输出数据依次为0x58d03ad6,0x2e032ce2,0xdafc683a，…，另外，更换为ZUC-128 所用测试集，所得输出也与预计结果一致[12]。

2.5 性能对比

本文以XC7Z045 为例，详细对比了上述4 种加法器结构在全硬件和软硬件协同架构下的资源占用量和关键路径延迟。2 输入模231-1 加法器采用方式2，Vivado软件的综合和实现策略均设置为性能优先，全硬件架构和软硬件协同架构资源占用和性能对比如表1 和表2所示。

表1 全硬件架构资源占用及性能对比

表2 软硬件协同架构资源占用及性能对比

从表1 可以看出，全部采用加法器的方案a，关键路径延迟最小，但面积占用最大；采用CSA 的加法树结构的方案b 关键路径延迟最大；混合架构的面积占用和延迟均折中。从表2 可以看出，方案a 延迟最小，面积占用也最小。随着加法树结构中CSA 加法器单元占比的增加，关键路径延迟逐渐增大。表1 和表2 比，软硬件协同架构比全硬件架构，方案a 资源占用节省了56%，延迟降低了21%。软硬件协同架构的吞吐率可达6 180 Mb/s。

3 结论

本文提出了4 种实现6 输入模加法器架构，并提出了全硬件和软硬件协同架构实施方案，用户可以根据所用器件和使用场景，在面积和速度间折中，选择最终实现方案，具有很高的实用价值。同时，本文提出了灵活的流水线实现架构，在增加少量寄存器的代价下进一步提高工作频率，实现每个时钟输出一个密钥数据，极大地提高了吞吐率，也可以通过选用UltraScale 系列FPGA进一步提升吞吐率。本文提出的实现架构向下兼容ZUC-128 算法，易于FPGA 实现，可广泛应用于4G-LTE和5G-NR 移动通信中。