芮康康 王成華 范賽龍 劉偉強

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

引 言

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

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

本文提出了一種基于R-LWE格加密中多項式乘法的硬件結(jié)構(gòu)。為了加快多項式乘法的運算速度，本文使用數(shù)論變換(Number theoretic transforms,NTT)方法，通過兩個并行的蝶形運算PE（Processing element）處理單元，加速NTT的實現(xiàn)。在保證資源消耗較低的前提下，本文的實現(xià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)的向量都稱為格的基，格的基中的向量個數(shù)稱為格的維度。任意兩組這樣的向量中，向量的個數(shù)相同。格類似于向量空間，但格是由基中的向量使用整數(shù)系數(shù)進行線性組合而構(gòu)成的，而向量空間使用的則是任意系數(shù)。直觀上，經(jīng)常將格看成是按規(guī)律排列的屬于Rm的一系列點，每個點都是一個向量的末端。

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

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

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

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

1.2 格加密算法流程

格加密算法方案主要包括密鑰生成、加密和解密3個部分[11]，具體實現(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，標準差是σ；R是多項式環(huán)Zq[x]/(xn+1)，q為素數(shù)且q=1 mod 2n，n為多項式的最高次數(shù)，f(m)實現(xiàn)模域變換，將輸入信息從[0,1]信息范圍轉(zhuǎn)換到[0,q-1]的范圍。

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

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

2.1 SchoolBook乘法

SchoolBook多項式算法公式為

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

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

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

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

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

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

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

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

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

算法2NTT多項式乘法算法

輸入：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)多項式高效乘法器硬件設(shè)計

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

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

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

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

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

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

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

4 結(jié)果分析

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

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

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

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

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

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

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

5 結(jié)束語

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