大整數(shù)乘法器的FPGA設(shè)計與實現(xiàn)

謝星; 黃新明; 孫玲; 韓賽飛

doi:10.11999/JEIT180836

大整數(shù)乘法器的FPGA設(shè)計與實現(xiàn)

doi: 10.11999/JEIT180836

謝星^{1, 2},
黃新明¹,
孫玲^1, ,,
韓賽飛¹

1.
南通大學電子信息學院 ??南通 ??226019
2.
南通大學工程訓練中心 ??南通 ??226019

基金項目: 國家自然科學基金(61571246)，江蘇省研究生科研與實踐創(chuàng)新計劃項目(KYCX17-1920)

詳細信息

作者簡介:
謝星：男，1985年生，博士生，研究方向為信息安全

黃新明：男，1974年生，教授，研究方向為VLSI設(shè)計、高性能計算

孫玲：女，1976年生，教授，研究方向為專用集成電路設(shè)計、系統(tǒng)集成技術(shù)

通訊作者:
孫玲　sun.l@ntu.edu.cn

中圖分類號: TN918.91; TN492
計量
- 文章訪問數(shù): 3984
- HTML全文瀏覽量: 2318
- PDF下載量: 205
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2018-08-27
- 修回日期: 2019-02-15
- 網(wǎng)絡(luò)出版日期: 2019-02-25
- 刊出日期: 2019-08-01

FPGA Design and Implementation of Large Integer Multiplier

Xing XIE^{1, 2},
Xinming HUANG¹,
Ling SUN^{1
, ,},
Saifei HAN¹

1.
School of Electronic Information, Nantong University, Nantong 226019, China
2.
Engineering Training Center, Nantong University, Nantong 226019, China

Funds: The National Natural Science Foundation of China (61571246), The Postgraduate Research & Practice Innovation Program of Jiangsu Province (KYCX17-1920)

摘要

摘要: 大整數(shù)乘法是公鑰加密中最為核心的計算環(huán)節(jié)，實現(xiàn)運算快速的大數(shù)乘法單元是RSA, ElGamal，全同態(tài)等密碼體制中急需解決的問題之一。針對全同態(tài)加密(FHE)應(yīng)用需求，該文提出一種基于Sch?nhage-Strassen算法(SSA)的768 kbit大整數(shù)乘法器硬件架構(gòu)。采用并行架構(gòu)實現(xiàn)了其關(guān)鍵模塊64k點有限域快速數(shù)論變換(NTT)的運算，并主要采用加法和移位操作以保證并行處理的最大化，有效提高了處理速度。該大整數(shù)乘法器在Stratix-V FPGA上進行了硬件驗證，通過與CPU上使用數(shù)論庫(NTL)和GMP庫實現(xiàn)的大整數(shù)乘法運算結(jié)果對比，驗證了該文設(shè)計方法的正確性和有效性。實驗結(jié)果表明，該方法實現(xiàn)的大整數(shù)乘法器運算時間比CPU平臺上的運算大約有8倍的加速。
- 全同態(tài)加密 /
- 現(xiàn)場可編程門陣列 /
- 大數(shù)乘法 /
- GMP庫
Abstract: 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 64k-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.
- Fully Homomorphic Encryption (FHE) /
- FPGA /
- Large number multiplication /
- GMP library

HTML全文

圖 1 樹形大數(shù)求和單元結(jié)構(gòu)圖

下載: 全尺寸圖片幻燈片

圖 2 基-32 NTT運算結(jié)構(gòu)圖

下載: 全尺寸圖片幻燈片

圖 3 1024點NTT架構(gòu)圖

下載: 全尺寸圖片幻燈片

圖 4 64k點硬件架構(gòu)圖

下載: 全尺寸圖片幻燈片

圖 5 大整數(shù)乘法器架構(gòu)圖

下載: 全尺寸圖片幻燈片

表 1 主要大整數(shù)乘法算法時間復雜度

算法	時間復雜度
grammar-school	$O({N^2})$
Karatsuba-Ofman	$O({N^{\ln 3/\ln 2}})$
Toom-Cook	$O({N^{\ln (2k - 1)/\ln (k)}})$
Sch?nhage-Strassen (SSA)	$O(N\log N\log \log N)$

下載: 導出CSV

表 2 素數(shù)p的單位根${r_N}$

NTT點數(shù)	單位根${r_N}$
2	2⁹⁶
4	2⁴⁸
8	2²⁴
16	2¹²
32	2⁶
64	2³

下載: 導出CSV

表 3 Stratix-V FGPA綜合結(jié)果

邏輯單元	Stratix V
邏輯單元	占用資源數(shù)	總資源數(shù)	利用率(%)
ALUTs	240229	718400	33
Logic registers	236088	1436800	16
Total block Memory (bit)	16252928	54067200	30
Total DSP blocks	288	352	82
最大頻率(MHz)	98.02

下載: 導出CSV

表 4 CPU和FPGA上性能比較

	計算時間(ms)	加速倍數(shù)
I7-7700 CPU	3.350	1
本文設(shè)計	0.419	8

下載: 導出CSV

表 5 實現(xiàn)結(jié)果對比

設(shè)計	位數(shù)(kbit)	頻率(MHz)	計算時間(ms)	占用資源數(shù)
文獻[17]	768	181	2.30	7.6k ALUTs+3.4k regisiters
文獻[18]	768	100	–	463k ALUTs+336k regisiters
本文	768	98.02	0.419	240k ALUTs+236k regisiters

下載: 導出CSV

參考文獻(18)

光炎, 祝躍飛, 顧純祥, 等. 一種針對全同態(tài)加密體制的密鑰恢復攻擊[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

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

陳智罡. 基于格的全同態(tài)加密研究與設(shè)計[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.

GENTRY C and HALEVI S. Implementing Gentry’s fully-homomorphic encryption scheme[C]. The 30th Annual International Conference on Theory and Applications of Cryptographic Techniques: Advances in Cryptology, Tallinn, Estonia, 2011: 129–148.

GENTRY C. A fully homomorphic encryption scheme[D]. [Ph.D. dissertation], Stanford University, 2009.

施佺, 韓賽飛, 黃新明, 等. 面向全同態(tài)加密的有限域FFT算法FPGA設(shè)計[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 on FPGA[J]. Journal of Electronics &Information Technology, 2018, 40(1): 57–62. doi: 10.11999/JEIT170312

?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

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

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

WANG Wei, HUANG Xinming, EMMART N, et al. VLSI design 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

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

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

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

WANG Wei, HU Yin, CHEN Lianmu, et al. Accelerating fully homomorphic encryption using GPU[C]. 2012 IEEE Conference on High Performance Extreme Computing, Waltham, USA, 2012: 1–5.

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

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

FENG Xiang and LI Shuguo. Accelerating an FHE integer multiplier using negative wrapped convolution and Ping-Pong FFT[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2019, 66(1): 121–125. doi: 10.1109/TCSII.2018.2840108

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.

相關(guān)文章

施引文獻

資源附件(0)

訪問統(tǒng)計