應用于格密碼的可重構多通道數論變換硬件設計

劉冬生 趙文定 劉子龍 張 聰 劉星杰

(華中科技大學光學與電子信息學院 武漢 430074)

1 引言

傳統(tǒng)的公鑰密碼體制所基于的數學難題，如RSA(Rivest-Shamir-Adleman)和橢圓曲線密碼(Elliptic Curve Cryptography, ECC)，早在1997年便被證明在量子計算下毫無安全性可言[1]。因此傳統(tǒng)公鑰密碼體制構建的信息安全系統(tǒng)及各種應用將面臨著嚴峻的安全問題，甚至是被完全破解的危險。因而能夠抵御量子攻擊的下一代密碼方案及其實現技術，即后量子密碼成為學界研究的熱點。

2019年9月，谷歌宣布實現“量子霸權”：一臺53量子比特的量子計算機在200 s內執(zhí)行的運算任務需要經典計算機運行10000年[2]。2020年7月，美國國家標準與技術研究所宣布了后量子密碼的第3輪候選方案。預計在2023年前后，后量子密碼標準將被確立。同年12月，中國信息協(xié)會發(fā)布《量子安全技術白皮書(2020)》[3]，從多個角度對量子時代下的信息安全進行了闡述。在后量子密碼標準的評選中，基于格難題的公鑰密碼，即格密碼方案處于優(yōu)勢地位：在現有的7種候選方案中，CRYSTALSKYBER[4]、數論研究單元算法(Number Theory Research Unit, NTRU)和SABER都是基于格的后量子密碼方案，因此格密碼有著重大的研究與應用價值。

在諸多格密碼方案中，多項式生成與多項式乘法運算是通用的核心算子，占用了絕大多數的時間資源開銷[5]。以基于環(huán)誤差學習(Ring-Learning With Error, Ring-LWE)格難題而構造的密碼方案[5]為例，多項式乘法運算占整個加解密時間的80%以上，對格密碼的實現與應用有著顯著影響。在現有的研究中，數論變換(Number Theoretic Transform,NTT)、快速傅里葉變換(Fast Fourier Transform,FFT)和School-book都能夠用于實現多項式乘法運算[5]。在時間方面進行比較，FFT和NTT的計算復雜度均為O(nlogn)，而School-book多項式乘法的計算復雜度為O(n2)[5,6]，隨著n增大，School-book所消耗的時間會以指數上升；在運算方面進行比較，FFT涉及復數和浮點運算，NTT只在整數域中進行運算。綜上所述，在格密碼的多項式乘法運算中，采用NTT來計算模內多項式乘法，更易于硬件的高效實現，能夠提升格密碼的整體運算性能。

目前對NTT的研究主要集中在以下3個方面：

(1) 降低資源消耗與功耗：通過混合基與多通道延遲換向器，以及單口存儲器合并多個內存部分，實現面積較小的NTT大整數乘法[7]。通過NTT非耦合結構，分別使用按時間抽取(Decimation In Time, DIT)與按頻率抽取(Decimation In Frequency, DIF)的蝶形運算單元來實現低功耗的NTT與數論逆變換(Inverse Number Theoretical Transform, INTT)運算[8,9]。

(2) 降低運算時間、減小內部時延：通過脈動陣列，將多個蝶形運算單元串行組合起來，以快速完成連續(xù)多個NTT運算[6,10]。通過多通道技術，優(yōu)化多通道地址分配方法與整體架構，以實現低時延[11,12]。

(3) 提高吞吐量：通過存儲優(yōu)化算法，對于單通道與多通道分別設計，以取得更高的吞吐量[13-15]。

本文從模乘算法和數論變換算法出發(fā)，研究基于隨機存取存儲器(Random Access Memory,RAM)的可重構模乘運算單元與多通道NTT架構。本文首先介紹了數論變換算法與多項式乘法，然后提出了基于RAM的模乘單元與多通道蝶形運算單元地址生成的硬件設計，進一步實現了支持4個不同參數n和15個不同參數q可重構NTT運算單元，最后給出了仿真驗證的結果。

2 負包裹卷積與數論變換算法

3 NTT硬件設計

3.1 基于RAM的可重構模乘單元

蝶形運算單元(Butterfly Arithmetic Unit, BAU)是NTT運算的核心。本文設計了用于BAU的基于RAM的模乘器(RAM-based Modular Multiplier,RMM)如圖1所示。該模乘器支持最高32 bit與32 bit的乘法，并可通過可重構操作改變模q的值，以實現不同模下的模乘運算，通過以下3步實現：

表1 基2 DIT-NTT算法

(1) 更新RAM內的值：Ref_din[31:0], Ref_addr[9:0]和Ref_ramchoose[1:0]用于為RMM中的兩個雙端口RAM提供數據與控制信號以進行更新。通過將乘法器MUL的積截取后作為地址信號輸入RAM，能夠直接得到RAM中存入的計算機預先計算好的求模結果。

(2) 改變積的截取方式：根據Ref_q_choosed[3:0]信號，IO_Ctrl模塊分解MUL_out[63:0]，將其按位傳送給RAMs和MOD_q(對輸入的數據進行判斷是否)。例如，當q為32 bit時，MUL_out[63:0]將被分解為{[63:56], [55:48], [47:40], [39:32],[31:0]}；當q為14位時，信號被分解為{8’d0, {2d’0,[27:22]}, [24:14], [13:0]}。

(3) 采用位截取模加法器：ADD0, ADD1,ADD2和ADD3對輸入的信號進行求和，并將結果分為兩路，一路減去模q、一路直接輸出，根據減法運算中的進位信號選擇一路，最后根據Ref_q_choosed [3:0]信號對數據按照模的位數截取、高位置0，輸出模加結果。

為了達到高性能與資源開銷的平衡，根據模q的最大位數，選擇RAM的數量，以實現資源與性能的適配。因而本設計采用兩個雙口RAM實現，如圖1所示。如使用1個雙口RAM構成模運算器，則不需要模加法器，但需要消耗32×2×216位的內存容量。因而本設計采用4個模加法器，消耗內存容量為32×4×28位，顯著減少了內存消耗，做到了較好的平衡。

根據所提出RMM結構可以實現任意q的模運算，隨著q位的增加，RAM消耗的資源將呈指數級增長。相比而言，針對特定參數優(yōu)化的模乘器在資源消耗方面具有明顯的優(yōu)勢，但不適用于多參數可重構設計。

3.2 多通道蝶形運算地址生成的硬件設計

位反轉(bit-reversed)能夠簡化DIT-NTT的地址生成。然而在多通道DIT-NTT的硬件實現中，地址的生成會變得十分復雜。因而本文設計了多通道蝶形運算地址架構，并采用Block RAM(BRAM)存儲數據以取得更高的速度與利用效率。對于d通道DIT-NTT(長度n)，則2d為BRAM數量。DITNTT運算有3個步驟：

(1)數據應按照順序存入BRAMs中，例如{0,1, cdots, n/d-1}于BRAM0, {n/d, n/d+1, cdots, 2n/d-1}于BRAM1, cdots,{(d ?1)×n/d,...,n ?1}于BRAMd-1。

(2)如圖2所示，所有的BRAM被分為兩部分，低位部分地址為0～k/2-1 (k=n/d)，高位地址部分為k/2～n-1。然后，BRAM0的一個端口和BRAM_d/2的端口連接到BAU0的a和b端口；BRAM0的b端口和BRAM_d/2的b端口連接到B A U 1 的a 和b 端口。B A U 2 的輸入端口連接BRAM1的a端口和BRAM_d/2+1的a端口，依此類推。BAUd-1對應于BRAM_d/2-1和BRAM_d-1。

圖1 基于RAM的模乘器結構圖

圖2 4通道NTT數據流向圖

(3)每一輪結束后，輸入Four_BRAMs和輸出Four_BRAMs進行交換。在所有回合結束后，NTT結果將被存儲到BRAM中，并以地址順序遞增的方式存儲。

3.3 可重構NTT結構

高性能、可重構的多通道NTT結構如圖3所示。BAUs包括RMM、位截取模加法器和位截取模減法器以及用于執(zhí)行NTT蝶形運算的寄存器陣列。Ctrl包括狀態(tài)機和一些控制信號的生成和反饋。ADDR生成Four_BRAMs和Wn_BRAMs的地址。NTT可重構設置將在多項式乘法之前進行：

(1) RAM中的數據更新。通過Ref_din[31:0],Ref_addr[11:0]和Ref_ramchoose[3:0]，連接到Wn_BRAMs與BMM中的RAM，對其進行數據更新。Ref_ramchoose[3:0]從低到高，分別為R M M 中的R A M 0, R A M 1 與W n_B R A M 0,Wn_BRAM1的讀寫控制信號。

(2) 參數n與q的設置：Ref_n[1:0]和Ref_q[3:0]分別按表2的順序設置參數n和q。n傳遞至狀態(tài)機；模q傳遞至RMM、模加/減器中，參與運算或對根據模q的位數對信號取最低位。

為了獲得最大的吞吐量和最少的時鐘周期消耗，兩個雙口BRAM分別進行讀寫操作來減少NTT操作所消耗的時鐘周期至1/2。初始數據存儲在Four_BRAMs_0中。多項式乘法包含以下6個步驟(n=2048)：

(1) Four_BRAMs_0將多項式a和b分別存儲在2048低位地址和2048高位地址。

(2)執(zhí)行NTT(a)。NTT(a)的結果存儲在Four_BRAMs_1的低位2048地址中。在這個過程中，Four_BRAMs_0和Four_BRAMs_1都被用來存儲中間變量。

(3) 執(zhí)行NTT(b)。NTT(b)的結果存儲在4個Four_BRAMs_1的高2048地址中。

(4) F o u r_B R A M s_1 輸出N T T(a)和NTT(b)到BAU中計算的模內點乘(NTT(a)與Wn_in相連，NTT(b)與b_in相連，如圖1所示)。結果N T T(a)⊙N T T(b)將被存儲在F o u r_BRAMs_0的2048低位地址中。

(5) 執(zhí)行INTT(NTT(a)⊙NTT(b))。結果c將存儲在Four_BRAMs_1中。

(6) 執(zhí)行inv⊙c運算。結果c將存儲在Four_BRAMs_0中。

對于不同的n和q，q不會改變存儲最終結果的BRAM。當n=256或1024時，結果將存儲在Four_BRAMs_0中；當n=512或2048時，結果將存儲在Four_ BRAMs_1中。所有的模q可以在不需要改變硬件結構的前提下改變，只需要更新相應BRAM中存儲的數據即可。本設計可以從13 bit到32 bit實現任意15種模q參數的可重構。該設計在不同參數下具有相同的速度和資源消耗。為了滿足最大n和q下NTT運算的需要，當n和q為其他的值時會有一部分存儲空間與數據線路的高位被閑置。

圖3 可重構NTT結構圖

表2 可重構參數表

當q需要更改時，BRAM中的所有數據都需要更新以實現新的NTT操作。從理論上講，該設計可以推廣到任意參數n和q的可重構NTT的實現，所消耗的資源僅與最大的n和q有關。與Feng等人[11]提出的多通道Stockham結構相比，本設計具有參數靈活、動態(tài)可配置的優(yōu)點。除此之外，本設計采用DIT-NTT結構，合并了負包裹卷積引入的參數，減少了1次多項式的點乘運算。因此本設計有很強的可拓展性與研究價值。

4 實現結果及對比

本文在Xilinx Artix-7(xca35tftg256)FPGA上實現了可重構多通道NTT設計。對于不同的參數，該設計消耗相同的資源(4780 Luts,1744 Slices,16 DSPs和24 BRAMs)，通過更新設置以及模乘器中的數據實現可重構操作。每個BAU包含6個32 bit模加法器、2個32 bit模減法器和1個32 bit×32 bit乘法器。BAU平均消耗資源為454 Slices。

多項式乘法的實現結果如表3所示。通過對傳統(tǒng)NTT的優(yōu)化，在單通道BAU下，1.5nlgn+2n時鐘周期是極限值。本設計與NTT[5], NTT[6],NTT[11], FFT[12]進行了比較。與17 bit NTT的流水線結構[6]相比，該設計實現了32 bit NTT運算與可重構操作。由于模q的數據位數對資源消耗有顯著影響，在ATP接近時，本設計的設計效率較NTT[6]而言更高。

表3 多項式乘法結果比較表

與采用FFT結構[12]進行多項式乘法相比，該設計在時間和資源消耗方面具有明顯的優(yōu)勢。本設計采用4通道，理論需要(1.5nlgn+2n)/4個時鐘周期。值得注意的是，多通道NTT[11]的(nlgn+2n)/d (d=16)時鐘周期是由NTT(常數多項式a)的結果預存來實現的。這只能用于帶誤差的環(huán)學習(Ring-LWE)應用，在基于格的后量子加密方案中并不具備普適性。在n=512的情況下，16通道NTT設計[11]消耗了約本設計10倍的資源，延遲時間為(1.5n×9+2n)/(n×9+2n) ×1.77 = 2.49 μs。因此，所提4通道NTT結構具有第2小的ATP。根據實現結果，在n=1024時(時鐘周期為4.3 ns)，1次NTT操作的延遲為6.71 μs(256為2.01 μs，512為3.57 μs，2048為13.43 μs)。

5 結論

為了解決NTT時延長與應用于不同加密環(huán)境的問題，本文提出一種可重構多通道NTT硬件設計。通過對多通道蝶形運算進行改進，設計了多通道NTT架構與基于RAM的可重構蝶形運算單元，以實現簡單高效的可重構NTT運算，并在Xilinx Artix-7 FPGA平臺上進行了驗證。本設計的最大工作頻率為232 MHz，能在6.71 μs內完成多項式長度為1024的NTT運算，并擁有第2小的ATP，具備很高的研究與應用價值。