謝星 孫玲 黃新明 韓賽飛

摘? 要： 大數(shù)乘法是公鑰加密系統(tǒng)中最為核心的模塊，同時，也是RSA、全同態(tài)等加密方案里最耗時的模塊，因此，快速實現(xiàn)大數(shù)乘法是急需解決的問題。64K點有限域NTT作為大數(shù)乘法器的關(guān)鍵組件，文中采用并行架構(gòu)實現(xiàn)NTT的運算，運算中基本采用加法和移位操作，以保證實現(xiàn)大量的并行處理，提高了處理速度。該組件在Stratix?V FPGA上得到了實現(xiàn)，工作在123.78 MHz頻率下，運行結(jié)果表明，在FPGA上的效率是CPU上運行速度的60倍。運行結(jié)果與GMP運算庫進(jìn)行比較，驗證了有限域64K點NTT算法的正確性。

關(guān)鍵詞： 有限域NTT算法; FPGA平臺; 全同態(tài)加密; 大數(shù)乘法; 并行處理; 運行速度比較

中圖分類號： TN915.08?34? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： A? ? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）09?0079?04

Design and implementation of finite field NTT algorithm based on FPGA

XIE Xing1， 2， 3， SUN Ling3， HUANG Xinming3， HAN Saifei3

（1. Nantong University Xinglin College， Nantong 226019， China; 2. Engineering Training Center， Nantong University， Nantong 226019， China;

3. School of Electronic Information， Nantong University， Nantong 226019， China）

Abstract： The large number multiplication unit is the most important core module in the public key encryption system， and is the most time?consuming module in RSA and fully homomorphic encryption schemes. Therefore， it is urgent for researchers to realize fast large number multiplication. A 64K?point finite field NTT （number theoretical transform） is a key module of large number multiplier. A parallel architecture is adopted in this paper to realize the operation of the NTT. Basically， the addition and shifting operations are adopted in the operation to ensure the realization of a large number of parallel processing， which improves the processing speed. The module is implemented based on Stratix?V FPGA （field programmable gate array）. The operating results show when the working frequency of the module is at 123.78 MHz， its speed when running on FPGA is 60 times higher than the speed when running on CPU. The operation results were compared with that of the GMP arithmetic library， which verified the correctness of the 64K?point finite field NTT algorithm.

Keywords： finite field NTT algorithm; FPGA platform; fully homomorphic encryption; large number multiplication; parallel processing; operation speed comparison

0? 引? 言

云存儲和云計算服務(wù)已然成為一種新興的市場趨勢，數(shù)據(jù)的私密性也成為人們享用云服務(wù)過程中關(guān)心的熱點和難點問題[1]?，F(xiàn)有技術(shù)中，即使用戶對數(shù)據(jù)加密，也仍然需要向云端提供密鑰才能進(jìn)行運算或搜索等。同態(tài)加密方案允許云服務(wù)器在密文上直接進(jìn)行任意的運算，即數(shù)據(jù)在加密狀態(tài)下被處理，不會暴露原文信息[2]。然而，同態(tài)加密方案的算法復(fù)雜度極高，導(dǎo)致實際運行效率很低。因為在現(xiàn)有全同態(tài)加密（FHE）算法基礎(chǔ)上，為了保證同態(tài)計算安全，密鑰被做得非常大，即使對于小的安全設(shè)置尺寸2 048，每個源被加密到約750K位。隨后所有的計算將直接對這些密文進(jìn)行操作，都是大數(shù)的運算。

大數(shù)乘法是同態(tài)加密運算中的基本單元，廣泛應(yīng)用于其中的每一步。本文對大數(shù)乘法器中的關(guān)鍵組件64K點有限域NTT單元進(jìn)行了設(shè)計與實現(xiàn)，最終運算結(jié)果與GMP運算庫進(jìn)行比較，驗證了設(shè)計的正確性。本文首先簡要分析了全同態(tài)加密方案以及大數(shù)乘法的特點;然后詳細(xì)給出了64K點有限域NTT單元算法原理，提出了該單元的硬件設(shè)計架構(gòu)，并完成了硬件設(shè)計，在FPGA上進(jìn)行了功能仿真與驗證，對仿真結(jié)果進(jìn)行了驗證。該高效有限域NTT模塊還可以在其他密碼學(xué)算法中廣泛應(yīng)用，下面給出64K點有限域NTT的具體分析設(shè)計過程。

1? 全同態(tài)加密算法

全同態(tài)加密[R]和[S]是域，加密函數(shù)[E]：[R]→[S]，在使得[x]和[y]的信息不泄露的前提下，如果存在一種有效算法，使得[E（x+y）=E（x）⊕E（y）]或者[x+y=D（E（x）⊕E（y））]成立，則稱函數(shù)[E]為加法同態(tài);在使得[x]和[y]的信息不泄露的前提下，如果存在一種有效算法，使得[E（xy）=E（x）?E（y）]或者[xy=D（E（x）?E（y））]成立，則稱函數(shù)[E]為乘法同態(tài);如果函數(shù)[E]既是加法同態(tài)又是乘法同態(tài)，那稱[E]為全同態(tài)加密。

Gentry?Halevi提出的基于整數(shù)的同態(tài)加密方案，包括密鑰生成、加密、解密和重加密（Recryption）過程[3]。其中，密鑰可以離線生成，所以相應(yīng)模塊不需要硬件設(shè)計。如式（1）所示，加密過程是用公共密鑰[（d，r）]對原文進(jìn)行多項式求值運算從而得到[c]密文，[b]是1 bit的原文數(shù)據(jù)。如式（2）所示，解密過程主要完成一個模乘運算，其中，[w]是私鑰。在Gentry的實現(xiàn)中[4]，密鑰一般為785 000 bit，正是因為密鑰如此之大，導(dǎo)致同態(tài)加密方案的復(fù)雜度非常高。因為所有加密、解密以及重加密運算都是基于785 000 bit的模乘運算，所以快速的大數(shù)模乘運算成為該加密方案首要解決的關(guān)鍵問題。

[c=[u（r）]d=b+2i=1n-1uirid] （1）

[m=[c*w]dmod 2] （2）

式中[ui]為加密過程中隨機(jī)生成的“噪聲矢量”。

2? 有限域快速數(shù)論變換NTT

通常來說，快速傅里葉變換（FFT）計算在復(fù)頻域進(jìn)行浮點運算被廣泛應(yīng)用于信號處理。但復(fù)域FFT的乘法運算需要舍入操作，計算量大，可能導(dǎo)致誤差增大。此外，與定點運算進(jìn)行比較，浮點運算消耗大量的硬件資源。離散傅里葉變換（DFT）公式如下：

[Xk=n=0N-1xne-2πiNnk，? ? 0≤k≤N-1] （3）

離散傅里葉逆變換公式為：

[xn=1Nk=0N-1Xke2πiNnk，? ? 0≤n≤N-1] （4）

在FFT中，通過[n]次單位復(fù)根進(jìn)行運算，而對于NTT，則是將[rp-1N（mod p）]等價于[e-2πiN]，其中，[r]是模素數(shù)[p]的原根（由于[p]是素數(shù)，則原根一定存在），即：

[e-2πiN≡rp-1N（mod p）] （5）

得到快速數(shù)論變換（NTT）的公式為：

[Xk=n=0N-1xn（rN）nk（mod p），? ? 0≤k≤N-1] （6）

NTT的逆變換（INTT）公式為：

[xn=1Nk=0N-1Xk（rN）-nk（mod p），? ? 0≤n≤N-1] （7）

選擇在有限域[ZpZ]下運算，[p]是一個素數(shù)。通過選擇一個適當(dāng)?shù)馁|(zhì)數(shù)[p]，模乘法在有限域可以進(jìn)行快速運算。對于FHE算法，選擇Solinas素數(shù)[5]，[p=][264-232+1]。質(zhì)數(shù)[p]具有特殊的性質(zhì)，如[296mod p=-1]，[264mod p=232-1]。式（6）中，[rN]是第[N]個的單位圓解[6]。在進(jìn)行卷積計算時，為了保證最終結(jié)果不溢出，則[N2（b-1）2

2.1? 基?16NTT算法

在有限域[ZpZ]中，在硬件設(shè)計實現(xiàn)NTT的過程中模加、模減、模乘都是基于2的冪次方[7]，如果實現(xiàn)的是64位寬的操作，則每一個運算結(jié)果都要進(jìn)行模[p]操作，占用了大量的硬件資源。所以將64位擴(kuò)展為192位，采用“零填充”的方式進(jìn)行數(shù)據(jù)位的擴(kuò)展，這樣就避免了每次操作都進(jìn)行模[p]操作[8]，而且有[2192mod p=（212）16mod p=1]。本設(shè)計選擇16點NTT作為基本單元，運算過程中不需要乘法，只需要移位和模加操作。4 096是第16個單位圓解，16點有限域NTT和INTT公式為：

[X（k）=n=015x（n）212·nk%192mod p] （8）

[x（n）=116k=015X（k）2（192-12nk）%192mod p] （9）

正如前面所提到的，有限域NTT的主要優(yōu)點是計算不需要乘法，只需要模加法和移位操作。圖1給出了一個基數(shù)16的FFT體系結(jié)構(gòu)示意圖，由圖1可見，該基數(shù)16的FFT模塊包含了16個移位寄存器和16個處理單元。各處理單元包括大量進(jìn)位保存加法器電路來累加中間結(jié)果。在每個時鐘周期，16個樣本被發(fā)送到基數(shù)16的單元，然后移位和累加。流水線架構(gòu)可以在一個時鐘周期加上若干個流水線延遲時鐘周期內(nèi)輸出16點FFT結(jié)果，這符合高吞吐量設(shè)計目標(biāo)。前期已經(jīng)對16點NTT進(jìn)行了設(shè)計和實現(xiàn)[9]。

2.2? 65 536點NTT算法設(shè)計

由于NTT點數(shù)取值較大時，如果直接進(jìn)行計算是很復(fù)雜的。這時需要將NTT進(jìn)行分解，使用4級基數(shù)為16的NTT構(gòu)建這個64K有限域NTT模塊，根據(jù)NTT分解規(guī)則，下面列出了64K點NTT的分解公式。式（10）表示將一個64K點NTT分解為一個16點的NTT與4K點FFT的形式，式（11）將4K點NTT分解為16點與256點NTT的形式，式（12）將256點NTT分解為兩級的16點NTT運算。經(jīng)過這三個公式就能將64K點NTT運算轉(zhuǎn)化為4級的16點FFT運算。

[X（k）=n1=015Wn1k116n2=04 095x（n）Wn2k24 096Wn1k216×4 096] （10）

[X（k）=n1=015Wn1k116n2=0255x（n）Wn2k2256Wn1k24 096] （11）

[X（k）=n1=015Wn1k116n2=015x（n）Wn2k216Wn1k216×16] （12）

3? 65 536點NTT硬件設(shè)計

在硬件架構(gòu)上，使用4級基數(shù)為16的NTT構(gòu)建64K點有限域NTT模塊，同時，這個模塊也可以被用于轉(zhuǎn)換INTT結(jié)果。圖2為64K點NTT單元的串行架構(gòu)，該架構(gòu)中主要包括：ROM單元、RAM單元、數(shù)據(jù)交換單元、基?16NTT處理單元、地址生產(chǎn)單元、信號控制單元、模乘單元。下面就對每個模塊進(jìn)行說明：

1） ROM單元：在整個系統(tǒng)中需要用到16個ROM，因此，通過調(diào)用ROM的IP核可以生成16個IP資源，每個ROM的數(shù)據(jù)深度為4 096，數(shù)據(jù)位寬為64 bit。ROM里儲存計算NTT和INTT所需的旋轉(zhuǎn)因子[10]，旋轉(zhuǎn)因子預(yù)先通過C語言編寫的代碼計算好，然后存儲到ROM里。

2） RAM單元：在本設(shè)計中RAM結(jié)構(gòu)選用的是具有獨立讀寫地址和讀寫使能信號的雙口RAM，這樣可以有利于提高數(shù)據(jù)的讀寫效率，節(jié)省了運算時間[11?13]。每個RAM的數(shù)據(jù)深度為4 096，數(shù)據(jù)位寬為64 bit。

3） 數(shù)據(jù)交換單元：在數(shù)據(jù)進(jìn)行處理之前，對數(shù)據(jù)重新進(jìn)行排序，數(shù)據(jù)處理之后也要進(jìn)行排序，然后存儲到RAM單元中。

4） 地址生成單元：對于本設(shè)計的64K點NTT方案來說，初始數(shù)據(jù)以每4 096個為一組分別存入到16個RAM存儲器中。64K點NTT序列抽取按照倒序輸入順序輸出的方案進(jìn)行地址抽取，根據(jù)第一級運算中抽取間隔為4 096，第二級抽取間隔為256，第三級抽取間隔為16，第四級抽取間隔為1這個規(guī)律進(jìn)行讀取，每16個為一組，一共4 096個周期。若存入同一個存儲器中則會導(dǎo)致地址沖突，所以需要將同一組的數(shù)據(jù)存放在不同的存儲器中。根據(jù)FFT無沖突地址思想[14]，可以將64K個數(shù)據(jù)進(jìn)行存儲，如式（13），式（14）所示：

[blockNumber=（[d15+d14+d13+d12]+? ? ? ? ? ? ? ? ? [d11+d10+d9+d8]+[d7+d6+d5+d4]+? ? ? ? ? ? ? ? ? [d3+d2+d1+d0]） mod 16] （13）

[Address=[d15，d14，…，d4]] （14）

式中，[d15，d14，…，d0]為原始序列的編號，原序列共有64K個，因此可以使用16位二進(jìn)制數(shù)的地址來表示。

5） 模乘單元：兩個64位數(shù)相乘為128位，模乘單元利用模[p]的性質(zhì)將128位數(shù)化簡為32位數(shù)的相加和相減。

4? 實驗結(jié)果分析

本文在CPU平臺和FPGA平臺分別實現(xiàn)了64K點有限域NTT算法，使用的CPU平臺是Intel? coreTM i7?7700處理器，其主頻為3.4 GHz，內(nèi)存為64 GB，操作系統(tǒng)為Ubuntu 16.04，使用GMP和NTL庫上實現(xiàn)64K點有限域NTT算法。在FPGA上使用的是Stratix?V 5SGXEABN2F45I2，設(shè)計軟件使用的是QuartusⅡ 13.0和ModelSim 10.4軟件，運行該結(jié)果與GMP運算庫進(jìn)行比較，驗證了有限域64K點NTT算法的正確性，最后利用Altera synthesize tool對其進(jìn)行綜合，綜合結(jié)果如表1所示。

FPGA工作在123.78 MHz下，64K點有限域NTT運算的速度是在CPU下運行的60倍左右，如表2所示。

5? 結(jié)? 語

本文設(shè)計并實現(xiàn)了基于FPGA的有限域NTT算法，有限域NTT計算的優(yōu)勢在于只通過使用移位與加法操作就可以實現(xiàn)NTT運算。本文利用16點NTT搭建了64K點NTT單元，通過調(diào)用Quartus Ⅱ中的ROM以及RAM存儲器IP核，分別用來存儲旋轉(zhuǎn)因子和中間過程的數(shù)據(jù)。采用4級16點NTT處理模式，設(shè)計了NTT無沖突地址進(jìn)行中間計算數(shù)據(jù)的存取，完成了64K點NTT計算。最終，64K點NTT運算單元在Altera的Stratix?V綜合實現(xiàn)，最高處理頻率為123.78 MHz，運算速度是在CPU上實現(xiàn)的60倍，因此在信息安全領(lǐng)域具有很高的使用價值。

注：本文通訊作者為黃新明。

參考文獻(xiàn)

[1] 段新東.基于密文操作的云平臺數(shù)據(jù)保護(hù)技術(shù)研究[J].現(xiàn)代電子技術(shù)，2016，39（11）：90?94.

[2] 呂琴.云計算環(huán)境下數(shù)據(jù)存儲安全的關(guān)鍵技術(shù)研究[D].貴陽：貴州大學(xué)，2015.

[3] GENTRY C， HALEVI S. Implementing Gentry′s fully?homomorphic encryption scheme [C]// International Conference on Theory and Applications of Cryptographic Techniques： Advan?ces in Cryptology. Tallinn， Estonia： Springer， 2011： 129?148.

[4] GENTRY C. A fully homomorphic encryption scheme [D]. California： Stanford University， 2009.

[5] SOLINAS J A. Generalized Mersenne numbers [J]. Journal of Jishou University， 1999， 38（1/2）： 103?109.

[6] 徐鵬，劉超，斯雪明.基于整數(shù)多項式環(huán)的全同態(tài)加密算法[J].計算機(jī)工程，2012，38（24）：1?4.

[7] 林如磊，王箭，杜賀.整數(shù)上的全同態(tài)加密方案的改進(jìn)[J].計算機(jī)應(yīng)用研究，2013，30（5）：1515?1519.

[8] WANG W， HU Y， CHEN L. Accelerating fully homomorphic encryption using GPU [C]// High Performance Extreme Compu?ting. Waltham， USA： IEEE， 2013： 1?5.

[9] 施佺，韓賽飛，黃新明，等.面向全同態(tài)加密的有限域FFT算法FPGA設(shè)計[J].電子與信息學(xué)報，2018，40（1）：57?62.

[10] MACINDOE G， MAVRIDIS L， VENKATRAMAN V， et al. HexServer： an FFT?based protein docking server powered by graphics processors [J]. Nucleic acids research， 2010， 38（5）： 445?449.

[11] BRISARD S， DORMIEUX L. FFT?based methods for the mechanics of composites： a general variational framework [J]. Computational materials science， 2010， 49（3）： 663?671.

[12] 占席春，蔡費楊，王偉.多路并行FFT算法的FGPA實現(xiàn)技術(shù)[J].現(xiàn)代電子技術(shù)，2015，38（19）：34?39.

[13] 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.

[14] 馬余泰.FFT處理器無沖突地址生成方法[J].計算機(jī)學(xué)報，1995，18（11）：875?880.