李斌,陳曉杰,馮峰,周清雷
(1.鄭州大學計算機與人工智能學院,河南 鄭州 450001;2.信息工程大學數學工程與先進計算國家重點實驗室,河南 鄭州 450001)
隨著量子計算的發展,傳統公鑰密碼體制面臨著嚴重的安全問題?;诟窭щy的密碼算法具有加密效率高和抗量子攻擊等優勢,成為研究熱點。美國國家標準與技術研究院(NIST,National Institute of Standards and Technology)從2016 年起征集了后量子密碼的標準化評選,提出了眾多基于格的后量子密碼方案[1]。在各種密碼方案中,公鑰加密體制是非常重要的一個分支,主要被應用于密鑰的分配和數字簽名。NIST 最近公布了第三輪4 個基于格的公鑰加密算法,CRYSTALS-Kyber 便是其中之一。
在Kyber 格密碼方案中[2],多項式乘法運算是關鍵步驟,消耗了絕大部分時間和資源?,F有方案中,基于蝶形運算的數論變換[3](NTT,number theoretic transform)可以快速實現多項式的乘法。但是,在NTT 計算過程中,蝶形運算會被執行多次,且包含模加減、模乘、模約簡等多種運算[4],極大影響了硬件整體計算效率。其次,NTT 控制邏輯包含多次循環嵌套的運算,計算結構復雜。最后,多項式系數的存取和調度復雜,且對通信帶寬具有較高的要求。因此,如何利用可重構硬件現場可編程門陣列(FPGA,field programmable gate array)實現高效的NTT多項式乘法,這一問題亟待解決。
當前,對于格密碼系統的實現,仍需要兼顧硬件的執行效率和資源消耗,需要盡量多的并行結構,以實現更快的運算速度。由此,圍繞后量子密碼高效能的應用需求,本文開展了Kyber 算法的優化設計研究。首先,對Kyber 算法進行了描述,分析了NTT、逆向數論變換(INTT,inverse NTT)及系數對位相乘(CWM,coefficient-wise multiplication)等算法流程。然后,詳細給出了流水線蝶形運算單元的優化設計,并以多通道RAM 優化訪存,減少計算時延。最后,以32 個蝶形運算單元并行運算,實現了FPGA 整體架構,提高了計算效率。
整數環用Z 表示,Zq表示整數環模q的商環,Rq=Zq[x]/?(x)表示模多項式?(x)的整系數多項式環,其中?(x)為不可約簡多項式。大部分情況下?(x)=xn+1,則Rq=Zq[x]/(xn+1)表示次數最多為n-1的多項式環。
NTT 是在離散傅里葉變換(DFT,discrete Fourier transform)數論基礎上實現的,是定義在環Zq上的線性正交變換,只在整數環上進行運算。對于多項式,有

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

算法2INTT 算法


算法3CWM 算法

此外,在Kyber 算法中,對NTT/INTT 操作進行了優化處理,將原有的256 次多項式拆分為2 個128 次多項式,并以2 個128 次多項式獨立進行計算。因此,在CWM 算法中,需要進行128 次二次多項式的乘法運算。
Kyber 算法的參數如表1 所示,其中k用于選擇多項式矩陣的維度,并調整算法安全等級。

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


從Kyber 算法流程中可以看出,密鑰生成過程需要2k次NTT 和k2次CWM 運算;加密過程需要k次NTT、k+k2次CWM 和k+1 次INTT 運算;解密過程需要k次NTT、k次CWM 和一次INTT運算。
目前,對于Kyber 算法的研究主要集中在對NTT 算法的優化加速,包括蝶形運算、存儲訪問和指令集的優化。
為此,Yaman 等[5]以16 個蝶形運算單元加速了NTT/INTT的計算,但是其模約簡計算較復雜,仍有優化空間。Huang 等[6]在Xilinx Artix-7 和Virtex-7 FPGA 上對Kyber 算法進行了優化實現,并以流水線形式實現了NTT 模塊,但其NTT 計算周期較長。Mert 等[7]以蒙哥馬利模乘設計了蝶形運算單元,并可通過參數進行配置,以多運算單元(PE,processing element)并行完成NTT的計算。此外,Mert 等[8]又采用蒙哥馬利模乘,以字為單位對NTT進行了優化,并通過PCIe 以直接存儲器訪問(DMA,direct memory access)方式完成了軟硬件協同實現。Xing 等[9]在Xilinx Artix-7 上實現了完整的Kyber 算法,包括SHA3 和NTT/INTT的計算,但程序仍以串行執行為主,NTT的計算需要512 個時鐘周期。Ricci 等[10]在Xilinx Virtex UltraScale+XCVU7P 高性能FPGA 上實現了Kyber的NTT 運算,頻率達到了637 MHz,但其計算周期仍高達405 個時鐘周期。同時,Ricci 等[11]又在該FPGA 上實現了CRYSTALS-Dilithium 數字簽名算法,以4 個蝶形運算單元每次輸入2 組數據加速了計算。Chen 等[12]采用雙列順序存儲來解決RAM 讀寫沖突的問題,并以流水線技術優化了蝶形運算。Seiler 等[13]以AVX2 指令集優化了NTT 算法,并在Skylake 處理器上實現了6.3 倍的性能提升。Zijlstra 等[14]以高層次綜合(HLS,high-level synthesis)對Kyber 算法進行優化實現,并對各種實現在資源和時間消耗方面進行了詳細對比。Basu 等[15]以HLS 對多個后量子公鑰加密算法和數字簽名算法進行了實現,并在資源和性能間進行了對比分析。Agrawal 等[16]實現了寄存器傳輸級(RTL, register transfer level)代碼庫以硬件原語的方式提供n個點的NTT 運算。Bisheh-Nias ar 等[17]采用K2-RED模約簡算法對NTT和INTT 進行了優化,減少了資源占用,并提高了計算頻率。但K2-RED 算法需要額外對ω進行預計算,且不支持CWM的運算。Fritzmann等[18]在FPGA上設計了RISQ-V 指令集,加速了Kyber 算法的計算。
在國內,陳朝暉等[19]采用乒乓結構存儲多項式系數,并以可選層級的流水線結構,減少了蝶形運算單元的邏輯資源占用。劉冬生等[20]在Xilinx Artix-7 上設計了一種基于RAM的可重構多通道數論變換單元,支持不同參數的可重構配置。華斯亮等[21]設計實現了基32的數論變換硬件結構,以操作數合并和快速取模,提高了蝶形運算的計算效率。沈詩羽等[22]給出了一種針對我國Aigis 后量子密碼算法的高效AVX2 和ARM 優化方案,提升了算法整體性能。
綜上可以看出,想要提高Kyber 算法的FPGA實現速度,一是要對關鍵路徑進行分解,深度優化,提高計算效率;二是要增加并行度,包括各模塊間的并行和同時處理數據的能力。雖然上述方案在一定程度上加速了Kyber 算法的計算,但大部分方案的NTT 計算周期長,并行程度不高,仍無法滿足高性能計算的需求。同時,部分方案僅實現了NTT和INTT 運算,并不支持CWM 運算。為此,本文從Kyber的NTT、INTT 和CWM 各計算階段著手分析,針對不同的運算、存儲和通信特征選擇合適的實現方式,提高計算效率。
為提高Kyber 算法硬件實現整體靈活性和可擴展性,在FPGA 內放置32 個蝶形運算單元,各個蝶形運算單元可獨立執行。其次,放置多RAM通道對多項式系數和每次迭代的結果進行存取。對于參數ω,采用預計算的方式提前計算好,并以ROM的形式進行存儲。最后,由控制邏輯完成對蝶形運算單元的輸入輸出的控制、RAM 存取地址的控制及參數ω的讀取控制。FPGA 整體結構如圖1 所示。

圖1 FPGA 整體結構
從NTT、INTT 算法流程中可以看出,每次迭代讀取和寫入的參數是不同的。因此,需要通過仲裁對RAM 進行讀寫。同時,在CWM 算法中,需要多次計算模乘,因此在蝶形運算單元中以M輸出中間模乘的結果,并再次送入蝶形運算單元進行最終結果的計算??梢钥闯?,FPGA 整個架構以松耦合方式互連,并可根據參數配置,靈活完成NTT、INTT 和CWM 這3 種運算。
蝶形運算單元是NTT、INTT 和CWM 計算的核心。這里,采用流水線的結構進行實現,并根據控制信號,選擇NTT、INTT 和CWM 不同計算的流程。蝶形運算單元結構如圖2 所示。

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

圖3 流水線階段示意
在蝶形運算單元中,模加減可由組合邏輯進行實現,并根據加減結果是否超出素數q(q=3 329)的范圍,再進行處理判斷,其結構如圖4 和圖5 所示。

圖4 模加硬件結構

圖5 模減硬件結構
在圖4 和圖5 中,A和B為12 bit的輸入,C為12 bit的輸出,R和Rq為13 bit的中間計算結果,并根據R或Rq的最高位進行判斷輸出最終的模加減結果。而模約簡和模乘需要根據Kyber 算法參數進行深度優化,以減少資源消耗并提高運算速度。具體地,本文通過Barrett 算法實現模約簡,再以邏輯公式變換優化模乘,詳細介紹如下。
2.2.1Barrett 模約簡
Barrett 算法利用乘法和模約簡運算代替了高成本的除法來實現取模運算,可計算任何參數的模乘。對于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),因此需要再根據dif 高2 位進行判斷處理。最后,將zm 與q進行比較判斷,并計算輸出最終結果。
2.2.2模乘優化

2.2.3CWM 調度優化
對于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 個時鐘周期內完成二次多項式乘法,還提高了CWM的計算效率。具體地,CWM 中二次多項式調用流程如圖6 所示。

圖6 CWM 中二次多項式乘法調用流程
對于N個點的NTT,共需要執行lbN輪蝶形運算,且每輪對RAM的訪問需要唯一的地址來存取參數。8 個點的蝶形運算和RAM 訪問如圖7 所示,灰色節點表示蝶形運算。
從圖7(a)中可以看出,在第1 階段,4 組系數對(0,4)、(1,5)、(2,6)和(3,7)會分別進行蝶形運算。因此需要在一個時鐘周期內,從RAM 中讀取各組系數對。那么,可以采用2 個RAM(RAM0 和RAM1)分別存儲第0、1、2、3 和4、5、6、7 個系數進行實現。此外,由于每個階段的系數對都會發生變化。在第2 個階段,參與蝶形運算的4 組系數對為(0,2)、(1,3)、(4,6)和(5,7)。因此需要將第1階段(0,4)和(1,5)的輸出結果存入RAM0 中,(2,6)和(3,7)的結果存入RAM1 中。如此,可以確保在第2 階段,仍在一個時鐘周期內從RAM0 和RAM1中讀取到相應的系數對。同理,對于第3 階段的計算,也需要調整第2 階段RAM的存儲。

圖7 8 個點的蝶形運算和RAM 訪問
對于Kyber 算法,多項式有256 個系數,由于將其拆分為2 個128 次多項式,則共需要執行7 輪蝶形運算,對RAM的存取更為復雜。以下給出Kyber 算法的訪存優化方法。
2.3.1多RAM 存儲
首先,本文方案共有32 個蝶形運算單元,則需要采用64 個RAM,每個RAM 對應有4 個地址,共有64×4=256 個參數。RAM 初始化參數存儲如圖8所示。

圖8 RAM 初始化參數存儲
圖8 中,每2 個RAM 對應一個蝶形運算單元,且第2i個和第2i+1 個(0≤i< 32,i=i+2)RAM分別存取各自的系數對。如此,32 個蝶形運算單元可獨立并行讀取參數并執行。
其次,由于采用64 個RAM 對中間結果進行存取,需要確保RAM 地址的讀寫順序,防止讀寫沖突。為此,對RAM 進行了擴容,將RAM 分為高低2 個地址段。以NTT 為例,在首輪參數存入RAM后,從地址0~3 開始讀取數據,并將蝶形運算的結果寫入地址4~7。而后再從地址4~7 讀取數據,并將蝶形運算的結果寫入地址0~3。如此循環,以低地址空間和高地址空間的交替迭代操作,實現了每輪參數的有序存取。RAM 存取模式如圖9 所示。

圖9 RAM 存取模式
最后,對于ω的讀取,由于每輪蝶形運算輸入的參數不同,需要預處理后,按一定的規則進行存儲。具體地,對于NTT,從地址0 到22;對于INTT,從地址23 到45;對于CWM,從地址46 到49,每個地址分別有32 個數據,存入ROM 中。以NTT 運算為例,其ROM 存儲內容如圖10 所示。

圖10 NTT 中ω的ROM 存儲
2.3.2數據存取控制
Kyber 每輪蝶形運算讀寫的參數不同,且地址唯一。在讀取參數時,為方便操作,對參數進行重排,統一讀取64 個RAM的某一地址,獲取所有256 個參數并組成系數對。因此,在寫入中間結果時,需要對輸出的E和O分別按不同的地址進行存儲,以保證在下一輪可以從同一個地址再次讀取到對應的系數對。具體地,這里采用一個地址raddr對所有RAM 進行讀取,2 個地址waddre 和waddro分別完成E和O的RAM 寫入。
另外,由于RAM 空間被分為低地址空間和高地址空間,每輪交替使用高地址空間或低地址空間。因此需要對raddr、waddre 和waddro的高位進行交替翻轉,低位則按照每輪讀寫的地址正常進行變化。以NTT 運算為例,具體的raddr、waddre 和waddro 計算如算法5 和算法6 所示。
算法5RAM 讀地址的變換

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

同理,在算法6 中,當bau_stage 大于1 時,可直接根據bau_loop 獲取RAM的寫地址,而其他情況要根據當前bau_stage 和bau_loop 進行計算,從而獲得RAM的寫地址。最后,在步驟5)~步驟7),對waddre[2]和waddro[2]高位進行翻轉。
由于RAM的讀寫需要先獲取地址,然后才能讀寫數據,即RAM的操作需要一定的時間間隔。而蝶形運算是以流水線方式執行的,可連續對數據進行處理。因此需要處理好流水線和RAM 訪問之間的關系,防止數據中斷出錯。
如圖11 所示,將數據送入流水線時,預先計算出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)的所需參數寫入RAM。然后在CWM 計算過程中,可直接從2 組RAM 中讀取數據,并將多項式乘法結果再次存入其中一組RAM 中。隨后,再由控制信號完成INNT運算,并寫入其中一組RAM 中。通過2 組RAM的復用,不僅減少了外部通信次數,同時減少了FPGA 片上RAM 資源的消耗。

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

圖13 DMA 通信調度
具體地,Kyber 算法的通信調度流程如下。
1) 通過DMA 對RAM 組1 和RAM 組2 進行參數配置;
2) 由NTT 使能信號,按先A(x)再B(x)進行NTT計算,并將結果保存在對應的RAM 組1 和RAM組2 中;
3) 由CWM 使能信號,從RAM 組1 和RAM組2 中讀取數據,完成CWM 計算,并將結果保存在RAM 組1 中;
4) 再由控制信號完成INNT運算,并寫入RAM組1;
5) 最后,將結果由DMA 傳出。
本文實驗的硬件平臺為FPGA 加速卡,芯片型號為Xilinx公司的xc7z035ffg676-2,其查找表(LUT,look up table)資源是171 900,觸發器(FF,flip flop)資源是343 800,塊RAM(BRAM,block RAM)存儲器資源是500,數字信號處理器(DSP,digital signal processing)資源是900。軟件平臺為集設計、仿真、綜合、布線、生成于一體的Vivado 2019.2軟件。
首先,實驗通過對算法的各模塊進行深度優化,給出了綜合布線后的資源占用情況。其次,通過仿真分析了各模塊計算周期,并在可運行的最高頻率下,給出了硬件的具體性能和能效比。最后,與其他Kyber 算法設計方案進行了綜合對比,并對結果進行了分析說明。
Kyber 算法中各模塊資源占用如表2 所示。其中蝶形運算單元以流水線方式實現;控制單元以串行方式實現;多RAM 通道以并行方式實現;ROM存儲以串行方式實現。Kyber 算法通過串并混合設計,提高整體計算性能。

表2 Kyber 算法各模塊資源占用
從表2 中可以看出,蝶形運算單元占用資源較少,且僅消耗了一個DSP 即可完成乘法運算。而控制單元消耗了更多的LUT 資源,這是因為需要計算各種計數、地址及控制信號使能,包括蝶形運算輪次、本輪迭代次數、RAM 和ROM的讀寫地址、讀寫使能信號及等待控制等。其次,對于多RAM通道和ROM 存儲,需要存儲Kyber 算法計算過程中的全部參數,僅消耗了FPGA 部分BRAM 資源。最后,對于Kyber 整體實現,通過Vivado 軟件綜合布線后,LUT 資源占用比例為8.51%,FF 占用為1.66%,BRAM 占用為13.80%,DSP 占用為3.56%,資源消耗適中。
描述Kyber 算法硬件平臺的指標有性能、功率、能效比。其中性能指硬件平臺單位時間內的密碼計算速率,簡記為speed。功率用于計算硬件設備工作時的能耗,簡記為power。能效比表示平臺性能與設備功率之比,簡記為eer,計算式如下

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

表3 Kyber 算法的各項硬件性能指標
電路面積與運算時間的乘積AT[17,19]客觀反映了資源消耗和算法性能之間的關系。AT 值越低,表明在有限的資源條件下,與性能之間取得了更好的平衡。為了方便與其他方案對比,所有硬件實現均用AT 值進行歸一化處理。
具體地,本文采用的AT 值計算式如下

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

表4 與其他FPGA 實現方案的綜合對比
總體而言,本文提出的Kyber 算法的FPGA多路并行優化實現,至少縮短了36.23%的NTT 計算周期,并縮短了37.50%計算時間,在保證較高的工作頻率下,充分利用了芯片邏輯資源,具有較優的AT 值。
基于格密碼方案對于未來后量子密碼標準,乃至對未來信息系統的安全都有至關重要的作用。本文通過對Kyber 格密碼的描述,首先,深入剖析了NTT、INTT 及CWM 算法;然后,采用流水線技術實現了蝶形運算單元的優化,并以多通道RAM 優化參數存取,降低整體計算時延;最后,以32 個蝶形運算單元并行計算,實現了FPGA 整體架構,提高了計算效率。顯然,本文實現方案具有很高的研究和實際應用價值。
在實際應用中,側信道分析攻擊仍是密碼攻擊的主要手段。因此,在硬件層面如何提供Kyber 格密碼的安全防護策略,顯得至關重要。這不僅增加了額外的資源消耗,且提高了設計難度,仍需要探索解決,也是未來的研究工作。