基于FPGA的有限域NTT算法設計與實現

謝星 孫玲 黃新明 韓賽飛

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

關鍵詞： 有限域NTT算法; FPGA平臺; 全同態加密; 大數乘法; 并行處理; 運行速度比較

中圖分類號： TN915.08?34? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼： 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? 引? 言

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

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

1? 全同態加密算法

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

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

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

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

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

2? 有限域快速數論變換NTT

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

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

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

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

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

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

得到快速數論變換（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]是一個素數。通過選擇一個適當的質數[p]，模乘法在有限域可以進行快速運算。對于FHE算法，選擇Solinas素數[5]，[p=][264-232+1]。質數[p]具有特殊的性質，如[296mod p=-1]，[264mod p=232-1]。式（6）中，[rN]是第[N]個的單位圓解[6]。在進行卷積計算時，為了保證最終結果不溢出，則[N2（b-1）2

2.1? 基?16NTT算法

在有限域[ZpZ]中，在硬件設計實現NTT的過程中模加、模減、模乘都是基于2的冪次方[7]，如果實現的是64位寬的操作，則每一個運算結果都要進行模[p]操作，占用了大量的硬件資源。所以將64位擴展為192位，采用“零填充”的方式進行數據位的擴展，這樣就避免了每次操作都進行模[p]操作[8]，而且有[2192mod p=（212）16mod p=1]。本設計選擇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的主要優點是計算不需要乘法，只需要模加法和移位操作。圖1給出了一個基數16的FFT體系結構示意圖，由圖1可見，該基數16的FFT模塊包含了16個移位寄存器和16個處理單元。各處理單元包括大量進位保存加法器電路來累加中間結果。在每個時鐘周期，16個樣本被發送到基數16的單元，然后移位和累加。流水線架構可以在一個時鐘周期加上若干個流水線延遲時鐘周期內輸出16點FFT結果，這符合高吞吐量設計目標。前期已經對16點NTT進行了設計和實現[9]。

2.2? 65 536點NTT算法設計

由于NTT點數取值較大時，如果直接進行計算是很復雜的。這時需要將NTT進行分解，使用4級基數為16的NTT構建這個64K有限域NTT模塊，根據NTT分解規則，下面列出了64K點NTT的分解公式。式（10）表示將一個64K點NTT分解為一個16點的NTT與4K點FFT的形式，式（11）將4K點NTT分解為16點與256點NTT的形式，式（12）將256點NTT分解為兩級的16點NTT運算。經過這三個公式就能將64K點NTT運算轉化為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硬件設計

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

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

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

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

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

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

4? 實驗結果分析

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

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

5? 結? 語

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

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

參考文獻

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

[2] 呂琴.云計算環境下數據存儲安全的關鍵技術研究[D].貴陽：貴州大學，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] 徐鵬，劉超，斯雪明.基于整數多項式環的全同態加密算法[J].計算機工程，2012，38（24）：1?4.

[7] 林如磊，王箭，杜賀.整數上的全同態加密方案的改進[J].計算機應用研究，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] 施佺，韓賽飛，黃新明，等.面向全同態加密的有限域FFT算法FPGA設計[J].電子與信息學報，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實現技術[J].現代電子技術，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].計算機學報，1995，18（11）：875?880.