基于FPGA的有限域NTT算法設(shè)計(jì)與實(shí)現(xiàn)

謝星 孫玲 黃新明 韓賽飛

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

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

中圖分類號(hào)： TN915.08?34? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)： 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? 引? 言

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

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

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

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

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

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

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

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

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

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

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

在FFT中，通過(guò)[n]次單位復(fù)根進(jìn)行運(yùn)算，而對(duì)于NTT，則是將[rp-1N（mod p）]等價(jià)于[e-2πiN]，其中，[r]是模素?cái)?shù)[p]的原根（由于[p]是素?cái)?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]下運(yùn)算，[p]是一個(gè)素?cái)?shù)。通過(guò)選擇一個(gè)適當(dāng)?shù)馁|(zhì)數(shù)[p]，模乘法在有限域可以進(jìn)行快速運(yùn)算。對(duì)于FHE算法，選擇Solinas素?cái)?shù)[5]，[p=][264-232+1]。質(zhì)數(shù)[p]具有特殊的性質(zhì)，如[296mod p=-1]，[264mod p=232-1]。式（6）中，[rN]是第[N]個(gè)的單位圓解[6]。在進(jìn)行卷積計(jì)算時(shí)，為了保證最終結(jié)果不溢出，則[N2（b-1）2

2.1? 基?16NTT算法

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

2.2? 65 536點(diǎn)NTT算法設(shè)計(jì)

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

[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點(diǎn)NTT硬件設(shè)計(jì)

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

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

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

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

4） 地址生成單元：對(duì)于本設(shè)計(jì)的64K點(diǎn)NTT方案來(lái)說(shuō)，初始數(shù)據(jù)以每4 096個(gè)為一組分別存入到16個(gè)RAM存儲(chǔ)器中。64K點(diǎn)NTT序列抽取按照倒序輸入順序輸出的方案進(jìn)行地址抽取，根據(jù)第一級(jí)運(yùn)算中抽取間隔為4 096，第二級(jí)抽取間隔為256，第三級(jí)抽取間隔為16，第四級(jí)抽取間隔為1這個(gè)規(guī)律進(jìn)行讀取，每16個(gè)為一組，一共4 096個(gè)周期。若存入同一個(gè)存儲(chǔ)器中則會(huì)導(dǎo)致地址沖突，所以需要將同一組的數(shù)據(jù)存放在不同的存儲(chǔ)器中。根據(jù)FFT無(wú)沖突地址思想[14]，可以將64K個(gè)數(shù)據(jù)進(jìn)行存儲(chǔ)，如式（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]為原始序列的編號(hào)，原序列共有64K個(gè)，因此可以使用16位二進(jìn)制數(shù)的地址來(lái)表示。

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

4? 實(shí)驗(yàn)結(jié)果分析

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

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

5? 結(jié)? 語(yǔ)

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

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

參考文獻(xiàn)

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

[2] 呂琴.云計(jì)算環(huán)境下數(shù)據(jù)存儲(chǔ)安全的關(guān)鍵技術(shù)研究[D].貴陽(yáng)：貴州大學(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ù)多項(xiàng)式環(huán)的全同態(tài)加密算法[J].計(jì)算機(jī)工程，2012，38（24）：1?4.

[7] 林如磊，王箭，杜賀.整數(shù)上的全同態(tài)加密方案的改進(jìn)[J].計(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ì)[J].電子與信息學(xué)報(bào)，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] 占席春，蔡費(fèi)楊，王偉.多路并行FFT算法的FGPA實(shí)現(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處理器無(wú)沖突地址生成方法[J].計(jì)算機(jī)學(xué)報(bào)，1995，18（11）：875?880.