大整数乘法器的FPGA设计与实现

FPGA Design and Implementation of Large Integer Multiplier

大整数乘法是公钥加密中最为核心的计算环节,实现运算快速的大数乘法单元是RSA, ElGamal,全同态等密码体制中急需解决的问题之一。针对全同态加密(FHE)应用需求,该文提出一种基于Sch?nhage-Strassen算法(SSA)的768 kbit大整数乘法器硬件架构。采用并行架构实现了其关键模块64k点有限域快速数论变换(NTT)的运算,并主要采用加法和移位操作以保证并行处理的最大化,有效提高了处理速度。该大整数乘法器在Stratix-V FPGA上进行了硬件验证,通过与CPU上使用数论库(NTL)和GMP库实现的大整数乘法运算结果对比,验证了该文设计方法的正确性和有效性。实验结果表明,该方法实现的大整数乘法器运算时间比CPU平台上的运算大约有8倍的加速。

Large integer multiplication is the most important part in public key encryption, which often consumes most of the computing time in RSA, ElGamal, Fully Homomorphic Encryption(FHE) and other cryptosystems. Based on Sch?nhage-Strassen Algorithm(SSA), a design of high-speed 768 kbit multiplier is proposed. As the key component, an 64 k-point Number Theoretical Transform(NTT) is optimized by adopting parallel architecture, in which only addition and shift operations are employed and thus the processing speed is improved effectively. The large integer multiplier design is validated on Stratix-V FPGA. By comparing its results with CPU using Number Theory Library(NTL) and GMP library, the correctness of this design is proved. The results also show that the FPGA implementation is about eight times faster than the same algorithm executed on the CPU.