李斌，陳曉杰，馮峰，周清雷

（1.鄭州大學計算機與人工智能學院，河南 鄭州 450001；2.信息工程大學數(shù)學工程與先進計算國家重點實驗室，河南 鄭州 450001）

0 引言

隨著量子計算的發(fā)展，傳統(tǒng)公鑰密碼體制面臨著嚴重的安全問題?；诟窭щy的密碼算法具有加密效率高和抗量子攻擊等優(yōu)勢，成為研究熱點。美國國家標準與技術研究院（NIST,National Institute of Standards and Technology）從2016 年起征集了后量子密碼的標準化評選，提出了眾多基于格的后量子密碼方案[1]。在各種密碼方案中，公鑰加密體制是非常重要的一個分支，主要被應用于密鑰的分配和數(shù)字簽名。NIST 最近公布了第三輪4 個基于格的公鑰加密算法，CRYSTALS-Kyber 便是其中之一。

在Kyber 格密碼方案中[2]，多項式乘法運算是關鍵步驟，消耗了絕大部分時間和資源?，F(xiàn)有方案中，基于蝶形運算的數(shù)論變換[3]（NTT,number theoretic transform）可以快速實現(xiàn)多項式的乘法。但是，在NTT 計算過程中，蝶形運算會被執(zhí)行多次，且包含模加減、模乘、模約簡等多種運算[4]，極大影響了硬件整體計算效率。其次，NTT 控制邏輯包含多次循環(huán)嵌套的運算，計算結構復雜。最后，多項式系數(shù)的存取和調(diào)度復雜，且對通信帶寬具有較高的要求。因此，如何利用可重構硬件現(xiàn)場可編程門陣列（FPGA,field programmable gate array）實現(xiàn)高效的NTT多項式乘法，這一問題亟待解決。

當前，對于格密碼系統(tǒng)的實現(xiàn)，仍需要兼顧硬件的執(zhí)行效率和資源消耗，需要盡量多的并行結構，以實現(xiàn)更快的運算速度。由此，圍繞后量子密碼高效能的應用需求，本文開展了Kyber 算法的優(yōu)化設計研究。首先，對Kyber 算法進行了描述，分析了NTT、逆向數(shù)論變換（INTT,inverse NTT）及系數(shù)對位相乘（CWM,coefficient-wise multiplication）等算法流程。然后，詳細給出了流水線蝶形運算單元的優(yōu)化設計，并以多通道RAM 優(yōu)化訪存，減少計算時延。最后，以32 個蝶形運算單元并行運算，實現(xiàn)了FPGA 整體架構，提高了計算效率。

1 相關工作

1.1 Kyber 算法簡介

整數(shù)環(huán)用Z 表示，Zq表示整數(shù)環(huán)模q的商環(huán)，Rq=Zq[x]/?(x)表示模多項式?(x)的整系數(shù)多項式環(huán)，其中?(x)為不可約簡多項式。大部分情況下?(x)=xn+1，則Rq=Zq[x]/(xn+1)表示次數(shù)最多為n-1的多項式環(huán)。

NTT 是在離散傅里葉變換（DFT,discrete Fourier transform）數(shù)論基礎上實現(xiàn)的，是定義在環(huán)Zq上的線性正交變換，只在整數(shù)環(huán)上進行運算。對于多項式，有

在Kyber 算法中，NTT、INTT 和CWM 算法流程如算法1、算法2 和算法3 所示，其中brl-1(k)和brl-1(i)分別表示對k和i進行l(wèi)-1 位的比特逆序操作。

算法1NTT 算法

算法2INTT 算法

算法3CWM 算法

此外，在Kyber 算法中，對NTT/INTT 操作進行了優(yōu)化處理，將原有的256 次多項式拆分為2 個128 次多項式，并以2 個128 次多項式獨立進行計算。因此，在CWM 算法中，需要進行128 次二次多項式的乘法運算。

Kyber 算法的參數(shù)如表1 所示，其中k用于選擇多項式矩陣的維度，并調(diào)整算法安全等級。

表1 Kyber 算法參數(shù)

Kyber 算法的密鑰生成、加密和解密過程如下。

從Kyber 算法流程中可以看出，密鑰生成過程需要2k次NTT 和k2次CWM 運算；加密過程需要k次NTT、k+k2次CWM 和k+1 次INTT 運算；解密過程需要k次NTT、k次CWM 和一次INTT運算。

1.2 硬件相關實現(xiàn)

目前，對于Kyber 算法的研究主要集中在對NTT 算法的優(yōu)化加速，包括蝶形運算、存儲訪問和指令集的優(yōu)化。

為此，Yaman 等[5]以16 個蝶形運算單元加速了NTT/INTT的計算，但是其模約簡計算較復雜，仍有優(yōu)化空間。Huang 等[6]在Xilinx Artix-7 和Virtex-7 FPGA 上對Kyber 算法進行了優(yōu)化實現(xiàn)，并以流水線形式實現(xiàn)了NTT 模塊，但其NTT 計算周期較長。Mert 等[7]以蒙哥馬利模乘設計了蝶形運算單元，并可通過參數(shù)進行配置，以多運算單元（PE,processing element）并行完成NTT的計算。此外，Mert 等[8]又采用蒙哥馬利模乘，以字為單位對NTT進行了優(yōu)化，并通過PCIe 以直接存儲器訪問（DMA,direct memory access）方式完成了軟硬件協(xié)同實現(xiàn)。Xing 等[9]在Xilinx Artix-7 上實現(xiàn)了完整的Kyber 算法，包括SHA3 和NTT/INTT的計算，但程序仍以串行執(zhí)行為主，NTT的計算需要512 個時鐘周期。Ricci 等[10]在Xilinx Virtex UltraScale+XCVU7P 高性能FPGA 上實現(xiàn)了Kyber的NTT 運算，頻率達到了637 MHz，但其計算周期仍高達405 個時鐘周期。同時，Ricci 等[11]又在該FPGA 上實現(xiàn)了CRYSTALS-Dilithium 數(shù)字簽名算法，以4 個蝶形運算單元每次輸入2 組數(shù)據(jù)加速了計算。Chen 等[12]采用雙列順序存儲來解決RAM 讀寫沖突的問題，并以流水線技術優(yōu)化了蝶形運算。Seiler 等[13]以AVX2 指令集優(yōu)化了NTT 算法，并在Skylake 處理器上實現(xiàn)了6.3 倍的性能提升。Zijlstra 等[14]以高層次綜合（HLS,high-level synthesis）對Kyber 算法進行優(yōu)化實現(xiàn)，并對各種實現(xiàn)在資源和時間消耗方面進行了詳細對比。Basu 等[15]以HLS 對多個后量子公鑰加密算法和數(shù)字簽名算法進行了實現(xiàn)，并在資源和性能間進行了對比分析。Agrawal 等[16]實現(xiàn)了寄存器傳輸級（RTL, register transfer level）代碼庫以硬件原語的方式提供n個點的NTT 運算。Bisheh-Nias ar 等[17]采用K2-RED模約簡算法對NTT和INTT 進行了優(yōu)化，減少了資源占用，并提高了計算頻率。但K2-RED 算法需要額外對ω進行預計算，且不支持CWM的運算。Fritzmann等[18]在FPGA上設計了RISQ-V 指令集，加速了Kyber 算法的計算。

在國內(nèi)，陳朝暉等[19]采用乒乓結構存儲多項式系數(shù)，并以可選層級的流水線結構，減少了蝶形運算單元的邏輯資源占用。劉冬生等[20]在Xilinx Artix-7 上設計了一種基于RAM的可重構多通道數(shù)論變換單元，支持不同參數(shù)的可重構配置。華斯亮等[21]設計實現(xiàn)了基32的數(shù)論變換硬件結構，以操作數(shù)合并和快速取模，提高了蝶形運算的計算效率。沈詩羽等[22]給出了一種針對我國Aigis 后量子密碼算法的高效AVX2 和ARM 優(yōu)化方案，提升了算法整體性能。

綜上可以看出，想要提高Kyber 算法的FPGA實現(xiàn)速度，一是要對關鍵路徑進行分解，深度優(yōu)化，提高計算效率；二是要增加并行度，包括各模塊間的并行和同時處理數(shù)據(jù)的能力。雖然上述方案在一定程度上加速了Kyber 算法的計算，但大部分方案的NTT 計算周期長，并行程度不高，仍無法滿足高性能計算的需求。同時，部分方案僅實現(xiàn)了NTT和INTT 運算，并不支持CWM 運算。為此，本文從Kyber的NTT、INTT 和CWM 各計算階段著手分析，針對不同的運算、存儲和通信特征選擇合適的實現(xiàn)方式，提高計算效率。

2 算法優(yōu)化設計

2.1 整體結構

為提高Kyber 算法硬件實現(xiàn)整體靈活性和可擴展性，在FPGA 內(nèi)放置32 個蝶形運算單元，各個蝶形運算單元可獨立執(zhí)行。其次，放置多RAM通道對多項式系數(shù)和每次迭代的結果進行存取。對于參數(shù)ω，采用預計算的方式提前計算好，并以ROM的形式進行存儲。最后，由控制邏輯完成對蝶形運算單元的輸入輸出的控制、RAM 存取地址的控制及參數(shù)ω的讀取控制。FPGA 整體結構如圖1 所示。

圖1 FPGA 整體結構

從NTT、INTT 算法流程中可以看出，每次迭代讀取和寫入的參數(shù)是不同的。因此，需要通過仲裁對RAM 進行讀寫。同時，在CWM 算法中，需要多次計算模乘，因此在蝶形運算單元中以M輸出中間模乘的結果，并再次送入蝶形運算單元進行最終結果的計算?？梢钥闯觯現(xiàn)PGA 整個架構以松耦合方式互連，并可根據(jù)參數(shù)配置，靈活完成NTT、INTT 和CWM 這3 種運算。

2.2 蝶形運算單元

蝶形運算單元是NTT、INTT 和CWM 計算的核心。這里，采用流水線的結構進行實現(xiàn)，并根據(jù)控制信號，選擇NTT、INTT 和CWM 不同計算的流程。蝶形運算單元結構如圖2 所示。

圖2 蝶形運算單元

由于NTT 先計算模乘，再計算模加減，而INTT先計算模加減再計算模乘，兩者計算的先后順序不同。因此在蝶形運算單元中插入了多個緩存寄存器，用來緩存中間結果，并根據(jù)控制信號，進行仲裁輸出。同時，通過緩存也降低了蝶形運算的邏輯層級，避免產(chǎn)生較大的路徑時延。其次，NTT/INTT每次存取參數(shù)的RAM 不一致，且輸出的E和O這2 個結果可能存入同一RAM 中，因此需要E和O按次序?qū)懭?。具體地，在NTT/INTT 中，輸出E需要3 個時鐘周期，輸出O需要4 個時鐘周期，并按先E后O寫入RAM。再次，對于CWM 算法，需要多次計算模乘和模加，由此需要對中間模乘結果M進行緩存，并以狀態(tài)機控制傳值完成后續(xù)計算。最后，使用DSP 實現(xiàn)乘法器，充分利用FPGA 芯片資源。蝶形運算單元流水線各階段如圖3 所示。

圖3 流水線階段示意

在蝶形運算單元中，模加減可由組合邏輯進行實現(xiàn)，并根據(jù)加減結果是否超出素數(shù)q（q=3 329）的范圍，再進行處理判斷，其結構如圖4 和圖5 所示。

圖4 模加硬件結構

圖5 模減硬件結構

在圖4 和圖5 中，A和B為12 bit的輸入，C為12 bit的輸出，R和Rq為13 bit的中間計算結果，并根據(jù)R或Rq的最高位進行判斷輸出最終的模加減結果。而模約簡和模乘需要根據(jù)Kyber 算法參數(shù)進行深度優(yōu)化，以減少資源消耗并提高運算速度。具體地，本文通過Barrett 算法實現(xiàn)模約簡，再以邏輯公式變換優(yōu)化模乘，詳細介紹如下。

2.2.1Barrett 模約簡

Barrett 算法利用乘法和模約簡運算代替了高成本的除法來實現(xiàn)取模運算，可計算任何參數(shù)的模乘。對于0 ≤x＜q，0 ≤y＜q，則xy＜q2。為計算zm=xymodq，0 ≤ zm ＜q，令sp=xy，如果存在wa 使sp=qwa +zm，即可求得zm。

具體地，Barrett 模約簡如算法4 所示。

算法4Barrett 模約簡

對于結果dif，其取值范圍為[-3q,2q)，因此需要再根據(jù)dif 高2 位進行判斷處理。最后，將zm 與q進行比較判斷，并計算輸出最終結果。

2.2.2模乘優(yōu)化

2.2.3CWM 調(diào)度優(yōu)化

對于CWM，需要在 Zq[x]/(x2-ω)上計算二次多項式乘法(a0+a1x)(b0+b1x)。在算法3 中，可以看到需要分別計算a0b1、a1b0、a1b1W和a0b0，共5 次模乘和2 次模加。對于模乘需要3 個時鐘進行計算，而模加只要需要一個時鐘周期。由此，在第1 個時鐘周期先計算a1b0，并在第4 個時鐘周期將a1b0緩存的結果與a0b1共同輸入蝶形運算單元，在a0b1做完模乘運算后，直接完成a1b0+a0b1的模加運算。同理，先計算a1b1，再計算a0b0。如此，不僅減少了CWM 中間等待的過程，并可在8 個時鐘周期內(nèi)完成二次多項式乘法，還提高了CWM的計算效率。具體地，CWM 中二次多項式調(diào)用流程如圖6 所示。

圖6 CWM 中二次多項式乘法調(diào)用流程

2.3 多RAM 訪存優(yōu)化

對于N個點的NTT，共需要執(zhí)行l(wèi)bN輪蝶形運算，且每輪對RAM的訪問需要唯一的地址來存取參數(shù)。8 個點的蝶形運算和RAM 訪問如圖7 所示，灰色節(jié)點表示蝶形運算。

從圖7(a)中可以看出，在第1 階段，4 組系數(shù)對(0,4)、(1,5)、(2,6)和(3,7)會分別進行蝶形運算。因此需要在一個時鐘周期內(nèi)，從RAM 中讀取各組系數(shù)對。那么，可以采用2 個RAM（RAM0 和RAM1）分別存儲第0、1、2、3 和4、5、6、7 個系數(shù)進行實現(xiàn)。此外，由于每個階段的系數(shù)對都會發(fā)生變化。在第2 個階段，參與蝶形運算的4 組系數(shù)對為(0,2)、(1,3)、(4,6)和(5,7)。因此需要將第1階段(0,4)和(1,5)的輸出結果存入RAM0 中，(2,6)和(3,7)的結果存入RAM1 中。如此，可以確保在第2 階段，仍在一個時鐘周期內(nèi)從RAM0 和RAM1中讀取到相應的系數(shù)對。同理，對于第3 階段的計算，也需要調(diào)整第2 階段RAM的存儲。

圖7 8 個點的蝶形運算和RAM 訪問

對于Kyber 算法，多項式有256 個系數(shù)，由于將其拆分為2 個128 次多項式，則共需要執(zhí)行7 輪蝶形運算，對RAM的存取更為復雜。以下給出Kyber 算法的訪存優(yōu)化方法。

2.3.1多RAM 存儲

首先，本文方案共有32 個蝶形運算單元，則需要采用64 個RAM，每個RAM 對應有4 個地址，共有64×4=256 個參數(shù)。RAM 初始化參數(shù)存儲如圖8所示。

圖8 RAM 初始化參數(shù)存儲

圖8 中，每2 個RAM 對應一個蝶形運算單元，且第2i個和第2i+1 個（0≤i＜ 32,i=i+2）RAM分別存取各自的系數(shù)對。如此，32 個蝶形運算單元可獨立并行讀取參數(shù)并執(zhí)行。

其次，由于采用64 個RAM 對中間結果進行存取，需要確保RAM 地址的讀寫順序，防止讀寫沖突。為此，對RAM 進行了擴容，將RAM 分為高低2 個地址段。以NTT 為例，在首輪參數(shù)存入RAM后，從地址0～3 開始讀取數(shù)據(jù)，并將蝶形運算的結果寫入地址4～7。而后再從地址4～7 讀取數(shù)據(jù)，并將蝶形運算的結果寫入地址0～3。如此循環(huán)，以低地址空間和高地址空間的交替迭代操作，實現(xiàn)了每輪參數(shù)的有序存取。RAM 存取模式如圖9 所示。

圖9 RAM 存取模式

最后，對于ω的讀取，由于每輪蝶形運算輸入的參數(shù)不同，需要預處理后，按一定的規(guī)則進行存儲。具體地，對于NTT，從地址0 到22；對于INTT，從地址23 到45；對于CWM，從地址46 到49，每個地址分別有32 個數(shù)據(jù)，存入ROM 中。以NTT 運算為例，其ROM 存儲內(nèi)容如圖10 所示。

圖10 NTT 中ω的ROM 存儲

2.3.2數(shù)據(jù)存取控制

Kyber 每輪蝶形運算讀寫的參數(shù)不同，且地址唯一。在讀取參數(shù)時，為方便操作，對參數(shù)進行重排，統(tǒng)一讀取64 個RAM的某一地址，獲取所有256 個參數(shù)并組成系數(shù)對。因此，在寫入中間結果時，需要對輸出的E和O分別按不同的地址進行存儲，以保證在下一輪可以從同一個地址再次讀取到對應的系數(shù)對。具體地，這里采用一個地址raddr對所有RAM 進行讀取，2 個地址waddre 和waddro分別完成E和O的RAM 寫入。

另外，由于RAM 空間被分為低地址空間和高地址空間，每輪交替使用高地址空間或低地址空間。因此需要對raddr、waddre 和waddro的高位進行交替翻轉，低位則按照每輪讀寫的地址正常進行變化。以NTT 運算為例，具體的raddr、waddre 和waddro 計算如算法5 和算法6 所示。

算法5RAM 讀地址的變換

在算法5的步驟1)中，當bau_stage 大于1 時，直接根據(jù)bau_loop 即可獲取RAM的讀地址。對于步驟2)，則需要根據(jù)當前bau_stage 和bau_loop 進行額外的計算，從而獲得RAM的讀地址。最后，在步驟4)～步驟6)，當raddr[1:0]由0 累加到3 時，raddr[2]會進行翻轉，從而使raddr[2:0]由4到7進行地址累加。

算法6RAM 寫地址的變換

同理，在算法6 中，當bau_stage 大于1 時，可直接根據(jù)bau_loop 獲取RAM的寫地址，而其他情況要根據(jù)當前bau_stage 和bau_loop 進行計算，從而獲得RAM的寫地址。最后，在步驟5)～步驟7)，對waddre[2]和waddro[2]高位進行翻轉。

由于RAM的讀寫需要先獲取地址，然后才能讀寫數(shù)據(jù)，即RAM的操作需要一定的時間間隔。而蝶形運算是以流水線方式執(zhí)行的，可連續(xù)對數(shù)據(jù)進行處理。因此需要處理好流水線和RAM 訪問之間的關系，防止數(shù)據(jù)中斷出錯。

如圖11 所示，將數(shù)據(jù)送入流水線時，預先計算出RAM 讀寫地址，并對地址進行打拍緩存。具體地，在蝶形運算的前2 輪，中間需要等待2～3 個時鐘周期。這是由于前2 輪，地址不是按序讀寫的，需要額外的等待。在第3～7 輪，中間只需要等待一個時鐘周期，即在當前RAM 地址寫入后，下一個時鐘可立即讀取。

圖11 RAM 讀寫等待示意

2.3.3RAM 資源復用

Kyber 算法中需要輸入2 個多項式A(x)和B(x)，為此通過2 組RAM 分別存儲，如圖12 所示。這樣可一次將A(x)和B(x)的所需參數(shù)寫入RAM。然后在CWM 計算過程中，可直接從2 組RAM 中讀取數(shù)據(jù)，并將多項式乘法結果再次存入其中一組RAM 中。隨后，再由控制信號完成INNT運算，并寫入其中一組RAM 中。通過2 組RAM的復用，不僅減少了外部通信次數(shù)，同時減少了FPGA 片上RAM 資源的消耗。

圖12 RAM 資源復用

2.4 通信調(diào)度

通過DMA的方式，以AXI FIFO 實現(xiàn)數(shù)據(jù)的傳輸，如圖13 所示。由于RAM 組入口數(shù)據(jù)位寬為384 bit，而FIFO 傳輸數(shù)據(jù)位寬為64 bit，因此需要對位寬進行轉換。同時，通過增加的FIFO 和位寬轉換模塊，使算法的實現(xiàn)與數(shù)據(jù)之間進行解耦合，各模塊操作的端口相互獨立，最大化地減少各模塊之間的相關性，從而降低布線路由的復雜度。然后，以AXI BRAM 實現(xiàn)控制信號的傳輸，并在解析后完成對Kyber 蝶形運算單元陣列的調(diào)度控制。

圖13 DMA 通信調(diào)度

具體地，Kyber 算法的通信調(diào)度流程如下。

1) 通過DMA 對RAM 組1 和RAM 組2 進行參數(shù)配置；

2) 由NTT 使能信號，按先A(x)再B(x)進行NTT計算，并將結果保存在對應的RAM 組1 和RAM組2 中；

3) 由CWM 使能信號，從RAM 組1 和RAM組2 中讀取數(shù)據(jù)，完成CWM 計算，并將結果保存在RAM 組1 中；

4) 再由控制信號完成INNT運算，并寫入RAM組1；

5) 最后，將結果由DMA 傳出。

3 實驗結果與分析

3.1 實驗環(huán)境

本文實驗的硬件平臺為FPGA 加速卡，芯片型號為Xilinx公司的xc7z035ffg676-2，其查找表（LUT,look up table）資源是171 900，觸發(fā)器（FF,flip flop）資源是343 800，塊RAM（BRAM,block RAM）存儲器資源是500，數(shù)字信號處理器（DSP,digital signal processing）資源是900。軟件平臺為集設計、仿真、綜合、布線、生成于一體的Vivado 2019.2軟件。

首先，實驗通過對算法的各模塊進行深度優(yōu)化，給出了綜合布線后的資源占用情況。其次，通過仿真分析了各模塊計算周期，并在可運行的最高頻率下，給出了硬件的具體性能和能效比。最后，與其他Kyber 算法設計方案進行了綜合對比，并對結果進行了分析說明。

3.2 各模塊實現(xiàn)

Kyber 算法中各模塊資源占用如表2 所示。其中蝶形運算單元以流水線方式實現(xiàn)；控制單元以串行方式實現(xiàn)；多RAM 通道以并行方式實現(xiàn)；ROM存儲以串行方式實現(xiàn)。Kyber 算法通過串并混合設計，提高整體計算性能。

表2 Kyber 算法各模塊資源占用

從表2 中可以看出，蝶形運算單元占用資源較少，且僅消耗了一個DSP 即可完成乘法運算。而控制單元消耗了更多的LUT 資源，這是因為需要計算各種計數(shù)、地址及控制信號使能，包括蝶形運算輪次、本輪迭代次數(shù)、RAM 和ROM的讀寫地址、讀寫使能信號及等待控制等。其次，對于多RAM通道和ROM 存儲，需要存儲Kyber 算法計算過程中的全部參數(shù)，僅消耗了FPGA 部分BRAM 資源。最后，對于Kyber 整體實現(xiàn)，通過Vivado 軟件綜合布線后，LUT 資源占用比例為8.51%，F(xiàn)F 占用為1.66%，BRAM 占用為13.80%，DSP 占用為3.56%，資源消耗適中。

3.3 性能分析

描述Kyber 算法硬件平臺的指標有性能、功率、能效比。其中性能指硬件平臺單位時間內(nèi)的密碼計算速率，簡記為speed。功率用于計算硬件設備工作時的能耗，簡記為power。能效比表示平臺性能與設備功率之比，簡記為eer，計算式如下

Kyber 算法實現(xiàn)的各項硬件性能指標如表3 所示。其中，能效比計算對應的芯片功耗為1.088 W。從表3 中可以看出，利用FPGA 實現(xiàn)的Kyber 算法不僅性能達到了每秒百萬級別的計算速度，且功耗較低，具有很高的能效比，適合在物聯(lián)網(wǎng)、云計算、高性能計算等多種場景中使用。

表3 Kyber 算法的各項硬件性能指標

3.4 與其他方案對比

電路面積與運算時間的乘積AT[17,19]客觀反映了資源消耗和算法性能之間的關系。AT 值越低，表明在有限的資源條件下，與性能之間取得了更好的平衡。為了方便與其他方案對比，所有硬件實現(xiàn)均用AT 值進行歸一化處理。

具體地，本文采用的AT 值計算式如下

其中，時間為執(zhí)行一次NTT 運算所消耗的時間，即時間=NTT 周期/ 頻率。

本文方案與其他Kyber 算法的FPGA 實現(xiàn)方案在NTT 周期、頻率、資源消耗和AT 值等方面綜合對比如表4 所示。

在表4 中，本文方案具有最短的計算周期。這是由于本文采用32 個蝶形運算單元并行執(zhí)行，且工作在較高的頻率，縮短了整體計算周期。同時，合理利用了芯片的DSP 和RAM 資源。在AT 值方面本文方案優(yōu)于大部分方案，但差于文獻[17]文案和文獻[10]文案。文獻[5]文案采用的是16 個蝶形運算單元，縮短了計算周期，但其模約簡計算稍復雜，且消耗了更多的LUT 資源，AT 值稍高。文獻[9]方案在FPGA 內(nèi)放置了2 個蝶形運算單元，并支持CWM 運算，但程序仍以串行執(zhí)行為主，導致NTT計算周期長，AT 值較高。文獻[10]方案使用的是Xilinx 高端芯片，采用全新架構，資源密度是本文Zynq-7035的6.37 倍，其工作頻率也是所有方案中最高的。該方案放置了4 個蝶形運算單元，并消耗了28 個DSP 完成模乘運算。由于其DSP 工作頻率高，降低了模乘運算時間，AT 值也是最低的。但該方案的NTT 和INTT 各自獨立實現(xiàn)，其INTT 還需要額外消耗60 個DSP，邏輯復用率低，占用了更多的資源。文獻[12]方案以運算邏輯復用實現(xiàn)各步操作，占用資源最少，但導致并行程度低，NTT計算周期長，AT 值最高。文獻[17]方案雖然具有較好的AT 值，占用資源少，但它采用了K2-RED 模約簡算法，通過預計算的方式僅能實現(xiàn)NTT 和INTT 運算，無法直接實現(xiàn)CWM 運算。

表4 與其他FPGA 實現(xiàn)方案的綜合對比

總體而言，本文提出的Kyber 算法的FPGA多路并行優(yōu)化實現(xiàn)，至少縮短了36.23%的NTT 計算周期，并縮短了37.50%計算時間，在保證較高的工作頻率下，充分利用了芯片邏輯資源，具有較優(yōu)的AT 值。

4 結束語

基于格密碼方案對于未來后量子密碼標準，乃至對未來信息系統(tǒng)的安全都有至關重要的作用。本文通過對Kyber 格密碼的描述，首先，深入剖析了NTT、INTT 及CWM 算法；然后，采用流水線技術實現(xiàn)了蝶形運算單元的優(yōu)化，并以多通道RAM 優(yōu)化參數(shù)存取，降低整體計算時延；最后，以32 個蝶形運算單元并行計算，實現(xiàn)了FPGA 整體架構，提高了計算效率。顯然，本文實現(xiàn)方案具有很高的研究和實際應用價值。

在實際應用中，側信道分析攻擊仍是密碼攻擊的主要手段。因此，在硬件層面如何提供Kyber 格密碼的安全防護策略，顯得至關重要。這不僅增加了額外的資源消耗，且提高了設計難度，仍需要探索解決，也是未來的研究工作。