一種高性能R-LWE格加密算法的電路結(jié)構(gòu)及其FPGA實(shí)現(xiàn)

芮康康 王成華 范賽龍 劉偉強(qiáng)

（南京航空航天大學(xué)電子信息工程學(xué)院，南京，211106）

引 言

在信息安全問題越來越突出的背景下，需要更高安全性的加密算法來保障個(gè)人信息和隱私。解決信息安全問題，最常用的手段是對(duì)信息進(jìn)行加密。目前，后量子密碼（Post-quantum cryptography）[1]已成為國(guó)內(nèi)外眾多學(xué)者的重點(diǎn)研究對(duì)象。此類加密技術(shù)基于特定數(shù)學(xué)領(lǐng)域的困難問題，不依賴于任何量子理論現(xiàn)象，但其計(jì)算安全性可以抵御當(dāng)前已知任何形式的量子計(jì)算攻擊。更為重要的是，它們與當(dāng)前網(wǎng)絡(luò)系統(tǒng)具有較高的兼容性。美國(guó)國(guó)家標(biāo)準(zhǔn)局（NIST）[2]、美國(guó)國(guó)家安全局（NSA）[3]以及歐洲電信標(biāo)準(zhǔn)協(xié)會(huì)(ETSI）[4]正在制定后量子密碼標(biāo)準(zhǔn)，預(yù)計(jì)2018年左右NIST將發(fā)布首批后量子密碼標(biāo)準(zhǔn)。

基于格難題的密碼算法是目前公鑰加密技術(shù)中一個(gè)新的研究熱點(diǎn)，此類密碼算法具有加密效率高、硬件實(shí)現(xiàn)簡(jiǎn)單及抗量子攻擊等優(yōu)點(diǎn)，是后量子時(shí)代極具潛力的密碼方案。而在由格難題構(gòu)造的公鑰密碼方案中，基于環(huán)錯(cuò)誤學(xué)習(xí)(Ring-learning with error,R-LWE)的加密方案在性能上有著較顯著的優(yōu)勢(shì)[5]，它不僅具有基于格難題構(gòu)造的公鑰加密方案的各種優(yōu)點(diǎn)，而且還支持理論安全性的證明[6]。文獻(xiàn)[7]設(shè)計(jì)了一種R-LWE加密方案中的多項(xiàng)式乘法器，它是一種基于快速傅里葉變換（Fast Fourier transformation，F(xiàn)FT）的高效乘法器，硬件資源消耗較少。在傳統(tǒng)設(shè)計(jì)中，人們通常通過降低系統(tǒng)時(shí)鐘頻率、減少冗余信號(hào)翻轉(zhuǎn)等方法來降低系統(tǒng)功耗[8]，但是工作效率和系統(tǒng)性能也會(huì)隨之下降。

本文提出了一種基于R-LWE格加密中多項(xiàng)式乘法的硬件結(jié)構(gòu)。為了加快多項(xiàng)式乘法的運(yùn)算速度，本文使用數(shù)論變換(Number theoretic transforms,NTT)方法，通過兩個(gè)并行的蝶形運(yùn)算PE（Processing element）處理單元，加速NTT的實(shí)現(xiàn)。在保證資源消耗較低的前提下，本文的實(shí)現(xiàn)較大地提升了運(yùn)算速度。

1 格加密算法原理

1.1 格加密理論

根據(jù)向量空間的概念，格的定義[9]如下：

定義v1，v2，…，vn∈ Rm設(shè)為一組線性無關(guān)的向量。由v1，v2，…,vn生成的格L指的是向量v1，v2，…，vn線性組合構(gòu)成的向量集合，且其所使用的系數(shù)均在整數(shù)域Z中，即L(v1，v2，…，vk)={a1v1+a2v2+…+anvn|a1，a2，…，an∈Z}。

任意一組可以生成格的線性無關(guān)的向量都稱為格的基，格的基中的向量個(gè)數(shù)稱為格的維度。任意兩組這樣的向量中，向量的個(gè)數(shù)相同。格類似于向量空間，但格是由基中的向量使用整數(shù)系數(shù)進(jìn)行線性組合而構(gòu)成的，而向量空間使用的則是任意系數(shù)。直觀上，經(jīng)常將格看成是按規(guī)律排列的屬于Rm的一系列點(diǎn)，每個(gè)點(diǎn)都是一個(gè)向量的末端。

目前最常用的兩個(gè)基于格的困難問題是短整數(shù)問題(Shortest integer problem，SIS)和錯(cuò)誤學(xué)習(xí)問題(Learning with error，LWE)，這兩個(gè)問題都可以看作等同于格問題的最短向量問題 (Shortest vector problem，SVP)上。但是基于SIS和LWE問題的加密方案都無法在實(shí)際中應(yīng)用，這是因?yàn)殡S著安全參數(shù)的增大，這些方案需要非常大的密鑰長(zhǎng)度，資源消耗會(huì)迅速增加，效率迅速降低。因此，為了解決這個(gè)問題，Lyubashevsky等在LWE問題的基礎(chǔ)上，提出了基于特定環(huán)上的LWE問題[10]。R-LWE算法是在環(huán)Zq[x]/(f)上進(jìn)行的操作，其中f是n的不可約多項(xiàng)式，在大部分情況下，f=xn+1，則環(huán)為R=Zq[x]/(xn+1)，其中n是2的冪，q是一質(zhì)數(shù)，如q=1 mod 2n。

R-LWE問題與LWE問題在形式上十分相似，并且具有標(biāo)準(zhǔn)LWE問題的很多特性，兩者的搜索問題和判定問題幾乎可以等價(jià)。Lyubashevsky等證明了：如果用多項(xiàng)式量子時(shí)間算法求解理想格上的SVP問題是困難的，那么對(duì)于任何的量子時(shí)間算法來說，求解R-LWE問題也將是困難的[10]。

綜上，R-LWE加密方案的不足之處在于加解密過程中使用到了多項(xiàng)式乘法，使得R-LWE方案的電路設(shè)計(jì)較之于LWE方案更為復(fù)雜（LWE公鑰長(zhǎng)度大），電路開銷也變得更大。但是與RSA,ECC等涉及到指數(shù)運(yùn)算的加密方案相比，R-LWE方案仍舊比較易于設(shè)計(jì)且節(jié)省資源。經(jīng)典和后量子公鑰密碼對(duì)比如表1所示。

表1 經(jīng)典和后量子公鑰密碼對(duì)比Tab.1 Comparison between classical and post quantum public key cryptography

1.2 格加密算法流程

格加密算法方案主要包括密鑰生成、加密和解密3個(gè)部分[11]，具體實(shí)現(xiàn)如算法1所示。

算法1基于R-LWE的公鑰密碼算法

密鑰：選擇r1,r2服從高斯分布Dσ，令p=r1-t·r2∈ R。則公鑰為p，私鑰為r2。r1為高斯噪聲，生成密鑰后不再需要。t∈R在加密過程中保持不變，滿足均勻分布。

加密：輸入信息為m∈{0,1}n，選擇e1,e2,e3服從高斯分布Dσ。令=f(m)∈R。則密文為[c1=

解密：解密的結(jié)果為m′=c1·r2+c2∈ {0,1}n。其中，Dσ是整數(shù)域上的離散高斯分布，期望是0，標(biāo)準(zhǔn)差是σ；R是多項(xiàng)式環(huán)Zq[x]/(xn+1)，q為素?cái)?shù)且q=1 mod 2n，n為多項(xiàng)式的最高次數(shù)，f(m)實(shí)現(xiàn)模域變換，將輸入信息從[0,1]信息范圍轉(zhuǎn)換到[0,q-1]的范圍。

2 環(huán)多項(xiàng)式乘法

對(duì)于R-LWE密碼算法，其中最為重要且耗時(shí)的是環(huán)多項(xiàng)式乘法。環(huán)多項(xiàng)式乘法有兩種實(shí)現(xiàn)方式，分別為SchoolBook乘法和NTT數(shù)論變換乘法方法。

2.1 SchoolBook乘法

SchoolBook多項(xiàng)式算法公式為

經(jīng)典的SchoolBook多項(xiàng)式乘法復(fù)雜度為O(n2)，需要n2個(gè)乘法和(n-1)2個(gè)加減法。由于n是2的冪，模n操作可以實(shí)現(xiàn)為一個(gè)右移的寄存器，對(duì)于時(shí)，它等于1，否則i+j≤ 2n-2時(shí)等于-1。對(duì)于經(jīng)典的SchoolBook算法實(shí)現(xiàn)，資源消耗較少，但是運(yùn)算耗時(shí)較長(zhǎng)。

2.2 NTT數(shù)論變換乘法

NTT是在FFT的數(shù)論基礎(chǔ)上實(shí)現(xiàn)的。由于FFT是在復(fù)數(shù)域上的變換，而且還是浮點(diǎn)運(yùn)算，存在精度和效率的問題。而在很多應(yīng)用中，需要對(duì)整數(shù)商環(huán)內(nèi)的序列進(jìn)行變換，在這種情況下FFT性能無法滿足要求，而NTT卻能很好地解決這一問題。NTT變換形式與FFT一樣，只是將FFT中的旋轉(zhuǎn)因子由復(fù)數(shù)變成了整數(shù)，避免了浮點(diǎn)運(yùn)算，使得運(yùn)算效率也大為提高[12]。

數(shù)論變換是以正整數(shù)q為模的整數(shù)環(huán)Zq上定義的線性正交變換。設(shè)x(n)∈Zq，n=0,1,2,…,N-1，k=0,1,2,…,N-1，則稱

為NTT，式(2)和式（3）分別為NTT正變換和NTT反變換。其中w為模q的N階本原單位根，滿足

為整數(shù)且滿足

用時(shí)間抽取算法將原序列x(n)按照序號(hào)的奇偶性拆分成兩個(gè)序列x1(n)和x2(n)，則對(duì)應(yīng)的NTT變換變?yōu)?/p>

通過將原N點(diǎn)的NTT變換進(jìn)行拆分，得到的新序列X1(k)，X2(k)變?yōu)镹/2點(diǎn)的NTT變換。繼續(xù)將X1(k)，X2(k)進(jìn)行拆分，得到N/4點(diǎn)的NTT變換。依此類推，直到得到2點(diǎn)的NTT變換，即

將k的取值范圍變?yōu)樵瓉淼囊话?，則式中xr(n)為x(n)序列序號(hào)位倒置之后的排列。

以上進(jìn)行的運(yùn)算稱之為蝶形運(yùn)算，求一個(gè)N點(diǎn)的NTT，共需要執(zhí)行l(wèi)og2N輪的蝶形運(yùn)算。為便于理解，NTT變換的過程可以用蝶形圖來描述，本文以8點(diǎn)的蝶形圖為例，具體如圖1所示。

圖1 8點(diǎn)NTT蝶形運(yùn)算結(jié)構(gòu)Fig.1 Butterfly structure of eight-point NTT

對(duì)于NTT多項(xiàng)式乘法而言，需要先將多項(xiàng)式進(jìn)行數(shù)論變換，然后對(duì)應(yīng)元素相乘，最后再進(jìn)行逆數(shù)論變換，即可得到多項(xiàng)式乘法結(jié)果。NTT多項(xiàng)式乘法算法如算法2所示。

算法2NTT多項(xiàng)式乘法算法

輸入：a,b∈Zq

輸出：c∈Zq

A=NTT(a),B=NTT(b)

fori=0：n-1

C[i]=A[i]·B[i]

end

c=NTT-1(C)

returnc

3 NTT環(huán)多項(xiàng)式高效乘法器硬件設(shè)計(jì)

本文所使用的參數(shù)取自于文獻(xiàn)[7]：多項(xiàng)式環(huán)系數(shù)的最高次數(shù)n=128，模質(zhì)數(shù)q=216+1=65 537。本文設(shè)計(jì)的多項(xiàng)式乘法器電路結(jié)構(gòu)如圖2所示。

圖2 本文實(shí)現(xiàn)的多項(xiàng)式乘法器結(jié)構(gòu)Fig.2 Structure of the polynomial multiplier implemented in this work

本文設(shè)計(jì)的R-LWE方案中的多項(xiàng)式乘法器結(jié)構(gòu)由PE,NTT和MUL等部件組成。PE單元是NTT的一部分，本文在圖中把PE獨(dú)立出來，是為了單獨(dú)說明PE單元，本文的代碼實(shí)現(xiàn)中PE與NTT也放在了兩個(gè)不同模塊。首先是BITREV模塊，該功能是進(jìn)行NTT變換之前的預(yù)處理，將原序列進(jìn)行位置置換排序，得到蝶形運(yùn)算的順序，并控制從存儲(chǔ)器RAM中讀寫數(shù)據(jù)。接著是RAMA和RAMB存儲(chǔ)模塊，這兩個(gè)模塊用來存儲(chǔ)多項(xiàng)式系數(shù)a和b，RAM的大小是128×17 bit。系數(shù)ai和bi按序加載到乘法器中，并存進(jìn)RAM。NTT模塊也具有逆NTT的功能，區(qū)別是輸入的旋轉(zhuǎn)因子不同，它與PE處理單元相連，共同完成NTT數(shù)論變換的功能。此處的NTT模塊主要是控制從存儲(chǔ)器中讀取相應(yīng)的數(shù)據(jù)，然后將相應(yīng)的數(shù)據(jù)按序送入蝶形運(yùn)算單元，接著將蝶形運(yùn)算單元輸出的結(jié)果返回到NTT中，再調(diào)用下一次蝶形運(yùn)算，每次變換均需要2×7輪操作，每一輪運(yùn)算的結(jié)果作為下一輪運(yùn)算的初始值。PE處理單元模塊就是蝶形運(yùn)算單元，包括乘加和取余操作，每個(gè)時(shí)鐘周期計(jì)算NTT的一個(gè)節(jié)點(diǎn)，將處理完成的結(jié)果返回NTT模塊。進(jìn)行NTT數(shù)論變換后，a,b各個(gè)系數(shù)將在MUL乘法單元中對(duì)應(yīng)相乘，然后將得到的結(jié)果送到逆NTT模塊中，進(jìn)行逆數(shù)論變換得到最終的結(jié)果。

圖3 PE處理單元結(jié)構(gòu)Fig.3 Structure of PE processing element

PE處理單元的結(jié)構(gòu)電路如圖3所示。根據(jù)蝶形運(yùn)算規(guī)則，將系數(shù)a和旋轉(zhuǎn)因子相乘然后取余，最后是加減b運(yùn)算。對(duì)于取余操作，余數(shù)是p=216+1=65 537。因此可得

因此可將取余操作轉(zhuǎn)化為簡(jiǎn)單的加減操作，比起直接調(diào)用Xilinx的取余IP核大大節(jié)省了資源消耗。

本文多項(xiàng)式乘法器的設(shè)計(jì)包含了兩個(gè)PE處理單元和兩個(gè)NTT數(shù)論變換模塊，這樣在進(jìn)行NTT變換時(shí)，a和b兩個(gè)多項(xiàng)式系數(shù)可以同時(shí)進(jìn)行變換運(yùn)算。蝶形運(yùn)算需要的旋轉(zhuǎn)因子是相同的，因此兩個(gè)模塊旋轉(zhuǎn)因子可以直接獲取得到，不需要重復(fù)調(diào)用，性能得到了大幅提升。在執(zhí)行逆向NTT時(shí)，由于只有一個(gè)多項(xiàng)式需要運(yùn)算，故只需要用到一個(gè)逆NTT模塊，PE模塊為NTT和逆NTT模塊重復(fù)調(diào)用，節(jié)省了資源，也不消耗額外的時(shí)鐘。本文的設(shè)計(jì)采用并行電路結(jié)構(gòu)，是一種以提升速度為目的的硬件實(shí)現(xiàn)，文獻(xiàn)[8]中的設(shè)計(jì)則采用串行電路結(jié)構(gòu)，資源消耗相對(duì)較低，兩種設(shè)計(jì)將會(huì)有不同的應(yīng)用領(lǐng)域。

4 結(jié)果分析

在Vivado2016.4軟件平臺(tái)上進(jìn)行硬件代碼設(shè)計(jì)，然后在Kintex-7 KC705 FPGA開發(fā)板上進(jìn)行板級(jí)測(cè)試，對(duì)應(yīng)的參數(shù)n=128,q=65 537，測(cè)試最高頻率可達(dá)330 MHz，仿真測(cè)試圖如圖4所示。

圖4 本設(shè)計(jì)仿真測(cè)試Fig.4 Simulation of the proposed design

本文還編寫了MATLAB測(cè)試腳本來測(cè)試代碼結(jié)果數(shù)據(jù)的正確性，經(jīng)過測(cè)試，F(xiàn)PGA硬件輸出數(shù)據(jù)正確，所得波形與預(yù)期一致。

在Vivado軟件中綜合實(shí)現(xiàn)后，電路的資源消耗報(bào)告如表2所示。由表中數(shù)據(jù)可以看出，本文設(shè)計(jì)的多項(xiàng)式乘法器的結(jié)構(gòu)資源消耗較少，只用了461個(gè)Slice。這是因?yàn)橐粋€(gè)Slice含有4個(gè)LUT和8個(gè)FF，所以設(shè)計(jì)中大量消耗LUT資源是不明智的。本文的設(shè)計(jì)最高頻率可達(dá)330 MHz，而且完成一次環(huán)多項(xiàng)式乘法只需要1 358個(gè)時(shí)鐘周期，即完成一次多項(xiàng)式乘法需要4.12 μs。

對(duì)比表中文獻(xiàn)[7]的實(shí)現(xiàn)，同是NTT乘法實(shí)現(xiàn)，本模塊使用了兩個(gè)NTT和兩個(gè)PE，使得乘法處理速度大大提高，并且優(yōu)化了部分結(jié)構(gòu)的設(shè)計(jì)，使得消耗的Slice數(shù)目也相對(duì)較少，雖然多使用了一個(gè)DSP，但性能比現(xiàn)有文獻(xiàn)中的更好。SchoolBook實(shí)現(xiàn)消耗的資源數(shù)非常少，但是卻會(huì)消耗大量的時(shí)鐘數(shù)，這是由于它的復(fù)雜度是O(n2)，本文設(shè)計(jì)復(fù)雜度為O(nlog2n)，速度比它要快得多。綜合來看，本設(shè)計(jì)在資源消耗不大的情況下，速度(周期)較NTT乘法提高了42%，較SchoolBook乘法提高了92%，資源和性能對(duì)比如圖5所示。可見，本設(shè)計(jì)在格密碼系統(tǒng)硬件上具有巨大的性能優(yōu)勢(shì)。

表2 本設(shè)計(jì)電路資源消耗表Tab.2 Circuit resource consumption of the proposed design

圖5 資源消耗、最大頻率和時(shí)鐘周期對(duì)比圖Fig.5 Comparison of resource consumption,maximum frequency and clock cycle

5 結(jié)束語

本文設(shè)計(jì)采用兩個(gè)NTT模塊和兩個(gè)PE處理單元的并行電路結(jié)構(gòu)，使多項(xiàng)式乘法的處理速度幾乎提高了一半，并且優(yōu)化了部分結(jié)構(gòu)，使得資源消耗也較少。結(jié)果表明，當(dāng)參數(shù)為n=128，q=65 537時(shí)，完成一次環(huán)多項(xiàng)式乘法只需要1 358個(gè)時(shí)鐘周期，最快只需要4.12 μs即可完成，是一種高速的多項(xiàng)式乘法器設(shè)計(jì)。因此，本設(shè)計(jì)能夠更好地應(yīng)用在格密碼方案的硬件系統(tǒng)中，有助于提高密碼系統(tǒng)的整體處理速度。