Page 70 - 《软件学报》2025年第10期

胡跃 等: 基于 FPGA 的格基数字签名算法硬件优化 4467

19. κ ⇐ κ +l
20. return σ = (˜c,z, h)
′
Verify (pk, M , σ)
1. ˆ A ∈ R k×l ⇐ ExpandA(ρ)
q
2. tr ⇐ H (pk,64)
3. µ ∈ {0,1} 512 ⇐ (H (tr ∥ M ))
′
4. c ∈ R q ⇐ SampleInBall (˜c)
( )
( )
5. w ⇐ UseHint q (h,NTT −1 ˆ A◦NTT(z)−NTT(c)◦NTT t 1 ◦2 d ,2γ 2 )
′
1
[[ ]] [[ ( )]]
6. return ∥ z∥ ∞ < γ 1 −β and ˜ c = H µ ∥ w ′
1
3 Dilithium 算法硬件实现方案
从硬件实现的层面分析算法 1 可得到如下结论: 首先, Dilithium 算法中存在大量高维度的多项式向量和多项
式矩阵, 这对应大量的多项式乘法运算过程. 其次, 签名算法中的子运算类型较多, 主要包含 3 种核心的采样算法
及 10 余种辅助运算. 考虑到上述两个关键的运算瓶颈, 在进行硬件实现时需要针对性地设计专用功能模块, 同时
合理规划数据调度、资源复用、时钟周期等多种因素的约束, 进而设计并实现高效的时序状态控制逻辑, 从顶层
进一步的提升整体的签名运算效率. 根据上述分析, 本文设计的顶层架构主要由 4 个部分组成.
(1) 基于延迟转向型硬件架构、并满足多参数集的多项式运算模块, 采用 8 级流水的蝴蝶单元阵列满足多种
类型的系数运算需求, 包括 NTT 运算、逆 NTT 运算、累加模运算和模乘运算. 更重要的是, 针对 Dilithium 算法
高维向量/矩阵的特点, 流水线型的设计架构可以连续执行运算操作, 极大地提升了整个模块的数据吞吐量.
(2) 针对 Dilithium 算法中核心采样运算和哈希运算的输入输出数据的具体特点, 设计了两种不同的采样模块,
并针对专用于采样运算的功能模块进行了合理的优化, 辅以用于数据规整化的数据编解码子功能模块, 以更低的
资源消耗实现了采样运算效率的加倍.
(3) 以安全等级 5 对应的参数集为基准设计统一的存储单元阵列, 并根据顶层模块输入的片选信号决定多项
式系数的组合规则和存储深度, 基于可重构的设计思想, 以更高的资源利用率实现可满足全参数集条件下的多项
式向量/矩阵存储需求.
(4) 通过分析签名过程核心运算步骤的子运算类型, 根据细粒度重组的设计思想对其进行分解和组合, 有效提
升单次输入运算阵列的多项式系数总量, 从硬件逻辑上有效降低单个系数对应的无效延迟时间. 其次, 将顶层的采
样模块和运算阵列模块的并行度尽可能地提高, 在不产生数据冲突的前提下进一步提升整体硬件架构的时钟周期
资源的利用率以及签名运算效率.
3.1 多项式运算模块设计
如图 1 所示, 多项式运算模块以延迟转向架构为基础设计实现, 其核心部分为基二蝴蝶单元 (butterfly unit,
BFU) 构成的运算阵列, 辅以 40 个移位寄存器和 20 个多路选择器 (delay register and multiplex selector, DM), 因此
也可称为脉动阵列运算单元. 如上文所述, 在 Dilithium 算法中的数论变换过程为标准的 8 级迭代运算, 与硬件模
块的运算阵列一一对应, 同时相邻阵列在寄存器和选择器的辅助下实现正确的操作数匹配, 相当于将 NTT/INTT
运算的每一级运算过程使用硬件资源进行固化. 因此, 运算模块输入端可以持续填充数据, 每个时钟周期最多可送
入 8 个参与运算的操作数, 在多级流水的设计结构下可实现对高维多项式向量/矩阵的持续运算. 根据上述运算模
块的硬件结构可知, 总时间消耗由两部分组成: 输入端填充数据的时钟周期, 这部分时间与单次参与运算的数据总
量成正比; 运算过程的延迟时周期数, 这部分时间与输入数据在运算模块内部的流通路径和运算级深度相关. 对于
一种特定的运算类型, 延迟时间由参与系数运算的蝴蝶单元及其延迟转向单元的数量确定, 因此这部分延迟时间
是一个固定值. 在参数 n 为 256 的前提下, 一个完整的多项式系数可在 32 个时钟周期内完成输入, 假设对于 K 个