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

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

24
1
23
23 0
0 q 24
0
23
23 24 MSB1 1
1
23 MSB22 >>1 23 0 1
q 24 1
0
(q+1)/2 23
MSB1 1 1
25 MSB1 1
0
23 >>1 23
q 23 MSB22 0
1 1
MSB1 1 (q+1)/2 23 1 23 46 Reduction 25 0
MSB1 LS B1 2 MSB1 1 23 q 0
0 1

23
1

图 2 紧凑型蝴蝶运算单元 (脉动阵列的基本运算单元)

[0,q−1] 中, 常用的约减算法有 Montgomery 算法和
在运算过程中需要确保最终的输出结果被规约到范围
Barrett 算法这两种 [42,43] , 在本文提出的硬件设计方案中, 相比之下 Barrett 约减算法有两点重要的优势: 首先,
Montgomery 算法的约减结果存在区间 (−q,q) 中, 在硬件层面意味着每个系数都要多一比特的符号位, 而 Barrett
(0,q) 中, 不存在负数的情况, 更加适合在硬件设计中统一使用无符号数的方式. 其次, Barrett
算法的约减结果存在区间
约减算法的结果同时包括了约减结果 res 和商值 quo. 考虑到在 Dilithium 算法中还存在运算过程 Decompose (r,α),
q
± r 1 := (r −r 0 )/α, 结果刚好与余数 res 和商值 quo
其核心功能为计算 r 的高位和低位, 即运算过程 r 0 := r mod α 和
分别对应. 综合上述两点分析, 本文选择基于 Barrett 算法设计约减模块. 如后文图 3 所示, 根据延迟寄存器的布局
结构可知, 约减单元存在 3 级流水运算, 在考虑输入输出端的延迟条件下, 一次完整的约减过程需要 5 个时钟周
期, 这同时也是蝴蝶单元上路数据流需要设置延迟寄存器进行时序规约的主要原因. 在第 1 级运算中, 根据最低汉
明重量原则分解 Dilithium 算法的模值 q 可得 2 −2 +1, 在此基础上将 Barrett 算法中的两次乘法操作使用加减
23
13
法代替, 从而节约了 DSP 资源的消耗. 第 2 级运算核心是将初步的约减结果进行修正, 修正依据是初步约减结果
的高三比特位数据, 共对应 8 种情况, 修正的结果存在于一个较大的范围 [ 0,2 −1 中. 在最后的第 3 级运算中, 对
]
24
[ 23 24 ]
于范围 2 ,2 −1 中的数据再进行一次模减运算, 可得到最终正确的约运算的结果. 如上文所述, 运算过程
Decompose (r,α) 对应的功能模块同构于后文图 3 所示的 3 级运算的硬件架构, 区别在于此时存在 190 466 和 523 776
q
19
9
18
16
13
两种模值的情况, 对应的分解结果分别为 2 −2 −2 +2 11 和 2 −2 , 同时, 为了节约硬件资源, 在实现 8 380 417
对应的约减模块时, 采用不带除的设计模式.
3.3 多功能置换网络设计
根据上文分析可知, 脉动阵列运算单元的输入端具有顺序敏感性的特点, 即运算结果的正确性与输入数据的
匹配具有强依赖关系, 同时采样得到的多项式系数初始顺序、参与运算的输入顺序、运算完成后的输出结果顺序
三者不完全一致. 因此, 为了确保多项式运算的正确性, 需要对于脉动阵列单元的输入或输出端的数据匹配关系进
行重排序操作. 本文将采样得到的多项式系数排序顺序设定为初始顺序, 基于核心的多项式运算类型的特点, 设计
并实现了包含 4 种工作模式的多功能置换网络, 如图 4 所示, 其中系数 x 的下标使用十六进制计数方式, 用来表示
多项式中的系数索引值. 具体地, 第 1 种置换模式将初始顺序转化为 NTT 运算的输入顺序, 如图 4(a) 所示, 每组正