后量子密碼CRYSTALS-Kyber的FPGA多路并行優(yōu)化實(shí)現(xiàn)

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

（1.鄭州大學(xué)計(jì)算機(jī)與人工智能學(xué)院，河南 鄭州 450001；2.信息工程大學(xué)數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，河南 鄭州 450001）

0 引言

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

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

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

1 相關(guān)工作

1.1 Kyber 算法簡(jiǎn)介

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

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

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

算法1NTT 算法

算法2INTT 算法

算法3CWM 算法

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

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

表1 Kyber 算法參數(shù)

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

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

1.2 硬件相關(guān)實(shí)現(xiàn)

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

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

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

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

2 算法優(yōu)化設(shè)計(jì)

2.1 整體結(jié)構(gòu)

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

圖1 FPGA 整體結(jié)構(gòu)

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

2.2 蝶形運(yùn)算單元

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

圖2 蝶形運(yùn)算單元

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

圖3 流水線階段示意

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

圖4 模加硬件結(jié)構(gòu)

圖5 模減硬件結(jié)構(gòu)

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

2.2.1Barrett 模約簡(jiǎn)

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

具體地，Barrett 模約簡(jiǎn)如算法4 所示。

算法4Barrett 模約簡(jiǎn)

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

2.2.2模乘優(yōu)化

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

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

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

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

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

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

圖7 8 個(gè)點(diǎn)的蝶形運(yùn)算和RAM 訪問

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

2.3.1多RAM 存儲(chǔ)

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

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

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

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

圖9 RAM 存取模式

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

圖10 NTT 中ω的ROM 存儲(chǔ)

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

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

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

算法5RAM 讀地址的變換

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

算法6RAM 寫地址的變換

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

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

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

圖11 RAM 讀寫等待示意

2.3.3RAM 資源復(fù)用

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

圖12 RAM 資源復(fù)用

2.4 通信調(diào)度

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

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

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

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

2) 由NTT 使能信號(hào)，按先A(x)再B(x)進(jìn)行NTT計(jì)算，并將結(jié)果保存在對(duì)應(yīng)的RAM 組1 和RAM組2 中；

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

4) 再由控制信號(hào)完成INNT運(yùn)算，并寫入RAM組1；

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

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

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

3.2 各模塊實(shí)現(xiàn)

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

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

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

3.3 性能分析

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

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

表3 Kyber 算法的各項(xiàng)硬件性能指標(biāo)

3.4 與其他方案對(duì)比

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

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

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

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

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

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

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

4 結(jié)束語

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

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