大整数乘法器的FPGA设计与实现
|
摘要
大整数乘法是公钥加密中最为核心的计算环节,实现运算快速的大数乘法单元是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.
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.
引文
[1]光炎,祝跃飞,顾纯祥,等.一种针对全同态加密体制的密钥恢复攻击[J].电子与信息学报,2013,35(12):2999-3004.doi:10.3724/SP.J.1146.2013.00300.GUANG Yan,ZHU Yuefei,GU Chunxiang,et al.A key recovery attack on fully homomorphic encryption scheme[J].Journal of Electronics&Information Technology,2013,35(12):2999-3004.doi:10.3724/SP.J.1146.2013.00300.
[2]FENG Xiang and LI Shuguo.Design of an area-effcient million-bit integer multiplier using double modulus NTT[J].IEEE Transactions on Very Large Scale Integration(VLSI)Systems,2017,25(9):2658-2662.doi:10.1109/TVLSI.2017.2691727.
[3]陈智罡.基于格的全同态加密研究与设计[D].[博士论文],南京航空航天大学,2015:1-5.CHEN Zhigang.Research and design of fully homomorphic encryption based on lattice[D].[Ph.D.dissertation],Nanjing University of Aeronautics and Astronautics,2015:1-5.
[4]GENTRY C and HALEVI S.Implementing Gentry’s fullyhomomorphic encryption scheme[C].The 30th Annual International Conference on Theory and Applications of Cryptographic Techniques:Advances in Cryptology,Tallinn,Estonia,2011:129-148.
[5]GENTRY C.A fully homomorphic encryption scheme[D].[Ph.D.dissertation],Stanford University,2009.
[6]施佺,韩赛飞,黄新明,等.面向全同态加密的有限域FFT算法FPGA设计[J].电子与信息学报,2018,40(1):57-62.doi:10.11999/JEIT170312.SHI Quan,HAN Saifei,HUANG Xinming,et al.Design of finite field FFT for fully homomorphic encryption based onFPGA[J].Journal of Electronics&Information Technology,2018,40(1):57-62.doi:10.11999/JEIT170312.
[7]?ZTüRK E,DOR?Z Y,SAVA?E,et al.A custom accelerator for homomorphic encryption applications[J].IEEE Transactions on Computers,2017,66(1):3-16.doi:10.1109/TC.2016.2574340.
[8]YE J H and SHIEH M D.Low-complexity VLSI design of large integer multipliers for fully homomorphic encryption[J].IEEE Transactions on Very Large Scale Integration(VLSI)Systems,2018,26(9):1727-1736.doi:10.1109/TVLSI.2018.2829539.
[9]POLLARD J M.The fast Fourier transform in a finite field[J].Mathematics of Computation,1971,25(114):365-374.doi:10.1090/S0025-5718-1971-0301966-0.
[10]WANG Wei,HUANG Xinming,EMMART N,et al.VLSIdesign of a large-number multiplier for fully homomorphic encryption[J].IEEE Transactions on Very Large Scale Integration(VLSI)Systems,2014,22(9):1879-1887.doi:10.1109/TVLSI.2013.2281786.
[11]RAFFERTY C,O’NEILL M,and HANLEY N.Evaluation of large integer multiplication methods on hardware[J].IEEE Transactions on Computers,2017,66(8):1369-1382.doi:10.1109/TC.2017.2677426.
[12]ROY S S,VERCAUTEREN F,VLIEGEN J,et al.Hardware assisted fully homomorphic function evaluation and encrypted search[J].IEEE Transactions on Computers,2017,66(9):1562-1572.doi:10.1109/TC.2017.2686385.
[13]DOR?Z Y,?ZTüRK E,and SUNAR B.Accelerating fully homomorphic encryption in hardware[J].IEEE Transactions on Computers,2015,64(6):1509-1521.doi:10.1109/TC.2014.2345388.
[14]WANG Wei,HU Yin,CHEN Lianmu,et al.Accelerating fully homomorphic encryption using GPU[C].2012 IEEEConference on High Performance Extreme Computing,Waltham,USA,2012:1-5.doi:10.1109/HPEC.2012.6408660.
[15]HUANG Xinming and WANG Wei.A novel and efficient design for an RSA cryptosystem with a very large key size[J].IEEE Transactions on Circuits and Systems II:Express Briefs,2015,62(10):972-976.doi:10.1109/TCSII.2015.2458033.
[16]JOHNSON L G.Conflict free memory addressing for dedicated FFT hardware[J].IEEE Transactions on Circuits and Systems II:Analog and Digital Signal Processing,1992,39(5):312-316.doi:10.1109/82.142032.
[17]FENG Xiang and LI Shuguo.Accelerating an FHE integer multiplier using negative wrapped convolution and PingPong FFT[J].IEEE Transactions on Circuits and Systems II:Express Briefs,2019,66(1):121-125.doi:10.1109/TCSII.2018.2840108.
[18]WANG Wei and HUANG Xinming.FPGA implementation of a large-number multiplier for fully homomorphic encryption[C].Proceedings of 2013 IEEE International Symposium on Circuits and Systems,Beijing,China,2013:2589-2592.doi:10.1109/ISCAS.2013.6572408.
[2]FENG Xiang and LI Shuguo.Design of an area-effcient million-bit integer multiplier using double modulus NTT[J].IEEE Transactions on Very Large Scale Integration(VLSI)Systems,2017,25(9):2658-2662.doi:10.1109/TVLSI.2017.2691727.
[3]陈智罡.基于格的全同态加密研究与设计[D].[博士论文],南京航空航天大学,2015:1-5.CHEN Zhigang.Research and design of fully homomorphic encryption based on lattice[D].[Ph.D.dissertation],Nanjing University of Aeronautics and Astronautics,2015:1-5.
[4]GENTRY C and HALEVI S.Implementing Gentry’s fullyhomomorphic encryption scheme[C].The 30th Annual International Conference on Theory and Applications of Cryptographic Techniques:Advances in Cryptology,Tallinn,Estonia,2011:129-148.
[5]GENTRY C.A fully homomorphic encryption scheme[D].[Ph.D.dissertation],Stanford University,2009.
[6]施佺,韩赛飞,黄新明,等.面向全同态加密的有限域FFT算法FPGA设计[J].电子与信息学报,2018,40(1):57-62.doi:10.11999/JEIT170312.SHI Quan,HAN Saifei,HUANG Xinming,et al.Design of finite field FFT for fully homomorphic encryption based onFPGA[J].Journal of Electronics&Information Technology,2018,40(1):57-62.doi:10.11999/JEIT170312.
[7]?ZTüRK E,DOR?Z Y,SAVA?E,et al.A custom accelerator for homomorphic encryption applications[J].IEEE Transactions on Computers,2017,66(1):3-16.doi:10.1109/TC.2016.2574340.
[8]YE J H and SHIEH M D.Low-complexity VLSI design of large integer multipliers for fully homomorphic encryption[J].IEEE Transactions on Very Large Scale Integration(VLSI)Systems,2018,26(9):1727-1736.doi:10.1109/TVLSI.2018.2829539.
[9]POLLARD J M.The fast Fourier transform in a finite field[J].Mathematics of Computation,1971,25(114):365-374.doi:10.1090/S0025-5718-1971-0301966-0.
[10]WANG Wei,HUANG Xinming,EMMART N,et al.VLSIdesign of a large-number multiplier for fully homomorphic encryption[J].IEEE Transactions on Very Large Scale Integration(VLSI)Systems,2014,22(9):1879-1887.doi:10.1109/TVLSI.2013.2281786.
[11]RAFFERTY C,O’NEILL M,and HANLEY N.Evaluation of large integer multiplication methods on hardware[J].IEEE Transactions on Computers,2017,66(8):1369-1382.doi:10.1109/TC.2017.2677426.
[12]ROY S S,VERCAUTEREN F,VLIEGEN J,et al.Hardware assisted fully homomorphic function evaluation and encrypted search[J].IEEE Transactions on Computers,2017,66(9):1562-1572.doi:10.1109/TC.2017.2686385.
[13]DOR?Z Y,?ZTüRK E,and SUNAR B.Accelerating fully homomorphic encryption in hardware[J].IEEE Transactions on Computers,2015,64(6):1509-1521.doi:10.1109/TC.2014.2345388.
[14]WANG Wei,HU Yin,CHEN Lianmu,et al.Accelerating fully homomorphic encryption using GPU[C].2012 IEEEConference on High Performance Extreme Computing,Waltham,USA,2012:1-5.doi:10.1109/HPEC.2012.6408660.
[15]HUANG Xinming and WANG Wei.A novel and efficient design for an RSA cryptosystem with a very large key size[J].IEEE Transactions on Circuits and Systems II:Express Briefs,2015,62(10):972-976.doi:10.1109/TCSII.2015.2458033.
[16]JOHNSON L G.Conflict free memory addressing for dedicated FFT hardware[J].IEEE Transactions on Circuits and Systems II:Analog and Digital Signal Processing,1992,39(5):312-316.doi:10.1109/82.142032.
[17]FENG Xiang and LI Shuguo.Accelerating an FHE integer multiplier using negative wrapped convolution and PingPong FFT[J].IEEE Transactions on Circuits and Systems II:Express Briefs,2019,66(1):121-125.doi:10.1109/TCSII.2018.2840108.
[18]WANG Wei and HUANG Xinming.FPGA implementation of a large-number multiplier for fully homomorphic encryption[C].Proceedings of 2013 IEEE International Symposium on Circuits and Systems,Beijing,China,2013:2589-2592.doi:10.1109/ISCAS.2013.6572408.