基于2KNTT的多项式乘法单元设计

在格基抗量子公钥密码算法的基础运算中,多项式乘法在硬件实现上消耗大量的时间.为提高实际运算性能,本文通过分析多项式乘法运算中数论变换的快速实现算法,提出一种面向CRYSTALS-Kyber算法、适应硬件实现的2n次单位根预处理型快速数论变换算法架构,利用小位宽数论变换的并行处理与复杂度低的计算形式来减少运算时间.整体运算架构在结合算法特殊性质后,确定了32路并行的设计模型.在此基础上,设计了一种与该架构匹配的统一化运算单元和数据读写不冲突、地址分配最优的存储单元.实验结果表明,在65 nm的互补金属氧化物半导体(CMOS)工艺下,97 ns完成一组项数为256、模数为3329的多项式乘法运算,花费108个周期,最高工作频率可达到1.1 GHz,面积时间积为20.7(kGE·μs).

NTT架构研究及其FPGA硬件优化实现

量子计算机的发展对现有公钥体系的影响是实质性的.在众多后量子密码流派中,格基密码方案因其安全性、高效性等优良特点而成为了主流技术路线.密码算法在各实现平台的运行效率是后量子算法评估进程中的重要指标.FPGA(Field Programmable Gate Array)具有并行性架构,是密码体系实际部署时的重要硬件平台.近年来,后量子算法的硬件优化实现研究吸引了越来越多的关注.针对格基密码算法中计算复杂度最高、耗时最长的操作——环上多项式乘法计算,本文对主流的加速技术——数论变换技术(Number-Theoretic Transform,NTT)进行了系统研究,根据参数不同将其分为标准NTT(Standard-NTT,SNTT)、删减NTT(Truncated-NTT,TNTT)、混合NTT(Hybrid-NTT,HNTT).为了提高适用性,设计了一种统一型、可常数时间执行、支持多参数的硬件电路,支持三种NTT架构,结合Karatsuba技巧,将对应系数相乘中乘法次数减少20%.针对NTT的核心操作——蝴蝶变换,设计了一种紧凑型、低时延的电路结构,可实现正向NTT、对应系数相乘、逆向NTT功能,同时支持CooleyTukey和Gentleman-Sande两种结构;提出一种新的系数访存模式,采用“交叉存储型”结构,使用双口BRAM将计算后的系数“对角交叉”变换位置后存储在原地址,利用双Bank存储模式满足蝴蝶变换单元的数据吞吐量;对Barrett约减算法进行修改,提出一种适用于多模值的模约减硬件单元,用加法和移位代替其中的乘法操作,减少乘法器资源的消耗.本方案使用Verilog HDL语言在Xilinx公司Artix-7系列XC7A200TFBG484-2型号FPGA芯片上进行了纯硬件优化实现.与当前研究相比,本设计在面积上减少12%-62.6%,时间上提升5.5%-49.8%.此外,我们还对高吞吐量的并行设计进行了优化实现,优化后的二并行、四并行架构时间上分别加速两倍、四倍,面积消耗仅为单结构的1.45倍、2.58倍.