面向Saber 算法的并行乘法器

呂 杰 ,汪鵬君 ,張會紅

（1.寧波大學 信息科學與工程學院,浙江 寧波 315211;2.溫州大學 電氣與電子工程學院,浙江 溫州 325035）

公鑰密碼廣泛應用于信息網(wǎng)絡安全、國防安全等重要領域,其密碼系統(tǒng)的安全性基于數(shù)學難題[1],如基于大數(shù)分解質(zhì)因數(shù)的 RSA(Rivest Shamir Adleman,RSA)算法和基于離散對數(shù)問題的ECC(Elliptic Curve Cryptography,ECC)算法.然而隨著量子計算的發(fā)展,Shor算法和Grover搜索算法在理論上可攻破現(xiàn)有密碼系統(tǒng)[2].Shor 等[3]引入一種快速量子算法,其多項式時間內(nèi)求解任意正整數(shù)N的質(zhì)因數(shù)分解方法將完全破壞公鑰加密體制的安全性.Grover 等[4]提出解決無結構數(shù)據(jù)庫搜索的算法,將迫使對稱加密增加密鑰長度以應對此類攻擊.因此具備抵御量子攻擊的新型公鑰密碼方案,即后量子密碼(Post-Quantum Cryptography,PQC)備受密碼學者關注.

自2016 年以來,美國國家標準與技術研究院已經(jīng)開展了三輪PQC 方案的標準化競賽.預計在2024 年,PQC 的國際標準方案最終確立.基于“Module Learning with Rounding”難題的Saber算法作為候選者之一,以二次冪為模數(shù)的規(guī)則避免額外模約運算開銷與拒絕采樣操作[5],但是該算法的核心算子——模多項式間的乘法在算法整體時間開銷中占據(jù)較大比重[1],特別是其模數(shù)規(guī)則限制數(shù)論變換(Number Theoretic Transform,NTT)在模多項式相乘的直接應用.由于NTT 在素域中才生效[6],因此優(yōu)化Saber 算法內(nèi)核心算子能有效提高算法的整體性能.D’Anvers 等[7]融合Toom-Cook 和Karatsuba 算法,設計不依賴NTT 的計算流程,實現(xiàn)軟件層面的Saber 算法方案.Wang 等[8]使用ESP32 協(xié)處理器設計基于大整數(shù)協(xié)處理器的Saber算法方案,為Saber 算法在物聯(lián)網(wǎng)設備中的應用提供技術支撐.Paksoy 等[9]采用基于托普利茲矩陣的多項式模乘算法來簡化運算,實現(xiàn)ARM Cortex-M4 平臺上的Saber 算法方案.Bermudo 等[10]提出預計算方式的插值技術,以減少資源開銷,實現(xiàn)基于Toom-Cook 的乘法架構.此外,亦有學者開展硬件層面研究,如Maria 等[11]通過專用硬件協(xié)處理單元加速核心算子運算,以提高Saber 算法速度.Basso等[6]利用Schoolbook 相乘的便捷性,結合集中系數(shù)相乘的機制以減少面積開銷,實現(xiàn)3 種不同性能的乘法器.Sinha 等[12]提出一種多項式乘法的架構,以克服內(nèi)存訪問瓶頸,并完成Saber 算法的硬件方案.

綜上所述,基于Schoolbook 相乘方式的計算復雜度過高.依靠Toom-Cook 算法可有效降低運算的復雜度,但其多次劃分乘法運算會引入額外寄存器硬件開銷.而Karatsuba 算法可折中分解多項式乘法的運算,同時降低計算復雜度[10].鑒此,本文通過對Karatsuba 大數(shù)相乘分治策略的研究,分析Saber 算法中模多項式運算的關鍵路徑,利用Karatsuba 算法分解并壓縮核心算子關鍵路徑時長.同時利用DC(Design Compiler)設計可綜合的硬件電路,提取該乘法器的時序、功耗和面積等的性能參數(shù),實現(xiàn)并行乘法器電路設計.

1 Saber 算法和Karatsuba 算法分析

1.1 Saber 算法

Saber 算法是現(xiàn)有公鑰密碼體系的分支,由密鑰生成、加密和解密三者構成Saber 公鑰加密方案.核心算子——模多項式間的乘法在三階段中均涉及密鑰生成階段,公鑰包含多項式矩陣AL×L和多項式向量bL×1,私鑰包含SL×1.b由A和S乘積的縮放舍入操作生成.加密階段: 明文m與v′=bTs′的運算構成密文c,同時密文還包括b′ 的信息,b′的生成與密鑰b生成類似;解密階段: 明文m′從v中恢復原有信息,v的生成亦存在多項式向量間的模乘運算.Saber 方案整體框架和參數(shù)細節(jié)可參考第三輪原始Saber 方案,核心算子如下[5]:

上述公式中,Aij、Sij分別以多項式向量(a255,a254,…,a0)、(s255,s254,…,s0)簡化表示.P為有限域內(nèi)的不可約多項式,用于進行模運算化簡.L為可配置參數(shù),圖1 中L取3.矩陣-向量相乘運算結構如圖1 所示,模乘運算的關鍵路徑為

圖1 矩陣-向量相乘

根據(jù)矩陣-向量相乘規(guī)則,矩陣A的行向量乘以列向量S得向量C.如R1為(A11·S11) modP;R2為(A12·S21) modP;R3為(A13·S31) modP;R4為(A21·S11) modP;R5為(A22·S21) modP;R6為(A23·S31)modP;R7為(A31·S11) modP;R8為(A32·S21) modP;R9為(A33·S31) modP;R1、R2、R3三者累加得數(shù)值C11;同理計算數(shù)值C21和C31.Aij、Sij和Cij多項式向量均為高位寬.

1.2 Karatsuba 算法

Karatsuba 算法是以分治策略為思想的快速乘法.該算法在折中分解計算時,用加法代替原有乘法,降低運算復雜度,以額外寄存器和加法器替換乘法的開銷.因此Karatsuba 算法可降低直接相乘O(n2)的時間復雜度至O(n1+ε,0 ＜ε＜ 1),其原理見式(6)～式(9)[10-11].n-1階多項式f(x)、g(x)以式(6)和式(7)折中分解,二者乘積見式(8).fH、fL、gH和gL均為多項式向量的n/2項高位系數(shù)和n/2項低位系數(shù).在式(9)中,替換式(8)的與式(8)相比,式(9)復用fH·gH和fL·gL乘法單元,減少重復運算.

將多項式向量Aij、Sij分別以式(6)、式(7)的形式代入式(9),結合Saber 算法模約規(guī)則,得式(10).P0、P1和P2均包含多項式的256 位系數(shù),其包含的乘加運算參見式(11)～式(13),此處的乘加運算均指向多項式間的運算.AH、AL、SH和SL均為各向量的128 項高、低位系數(shù),參見式(14)、式(15).至此,核心算子關鍵路徑被Karatsuba 算法壓縮為并行預加 (AH+AL,SH+SL)、并行乘法 (P0,P1,P2)和后加.

上述公式的取模運算可參見Saber 算法的模數(shù)規(guī)則[5].mod8192 和mod9 通過直接限定數(shù)據(jù)位寬實現(xiàn)模約電路,同時modP利用Saber 算法的模約規(guī)則,通過更改系數(shù)正負號實現(xiàn).促成Karatsuba算法與Schoolbook 相乘方式的融合.Rk計算如圖2所示,具體可分為3 個階段: 預加(Pre-add)、乘法(Multiplication)和后加(Post-add),分別對應圖中算法的(1)～(3).

圖2 基于Karatsuba 的多項式并行模乘

2 多項式乘法器設計

2.1 多項式乘法器的狀態(tài)機

由式(9)的分解過程可知,應用于Saber 算法乘法器的硬件電路有6 種狀態(tài)(圖3),空閑(Idle)狀態(tài)、加載數(shù)據(jù)(Load)狀態(tài)、預加狀態(tài)(Pre-add)、乘法狀態(tài)(Multiplication)、后加狀態(tài)(Post-add)、完成狀態(tài)(done).預加狀態(tài)、乘法狀態(tài)和后加狀態(tài)分別對應圖2 中的3 個步驟.其中,Tclk為單個時鐘周期.在131Tclk乘法狀態(tài)的關鍵時序中,128Tclk用于并行乘法計算,3Tclk用于滿足數(shù)字后端的建立時間的時序要求.

圖3 多項式乘法器的狀態(tài)機轉(zhuǎn)換圖

2.2 基于選擇器的累加器

乘積累加器(Multiply Accumulator,MAC)根據(jù)文獻[6]提出的預先相乘方式設計,部分乘法單元替換為數(shù)據(jù)選擇器,復用128 次相同的乘法,從而減少面積開銷.基于Karatsuba 的多項式并行模乘電路中包含2 種類型的MAC,記圖2 內(nèi)P0和P1的運算電路為MACI,P2的運算電路為MACII.在計算式(12)過程中,AL和SL中的系數(shù)分別存儲在2組系數(shù)寄存器中.由于sj的系數(shù)通過兩隨機變量的漢明之差獲得,且取值為[ -4,4],因此ai×sj共有4 種不同數(shù)值(正負用符號位表示).由圖4可見,該電路將預先相乘的輸出(ai,2ai,3ai,4ai)作為數(shù)據(jù)選擇器的輸入;同時,sj為并行數(shù)據(jù)選擇器的選擇信號,選擇對應的預乘結果;然后通過移位操作累加至寄存器組,此移位操作與ai系數(shù)項x的冪次相關.完成上述累加共需計算128 次,輸出P1.圖4中,MAC 處理的操作為多項向量 (a127,…,a0)和(s127,…,s0)間的乘累加運算.ai依次與 (s127,…,s0)的128項系數(shù)相乘,以sj信號選擇預乘結果(ai,2ai,3ai,4ai)中的數(shù)值代替直接相乘的結果.因此每次ai· (s127,… ,s0)計算均能復用128 輪的預乘結果.預乘的方式復用128 輪乘法運算,節(jié)省并行硬件電路的開銷.MACII的設計類似,但ai×sj有8 種不同的數(shù)值.

圖4 基于選擇器的MAC 電路

2.3 基于Karatsuba 的多項式并行模乘

基于Karatsuba 的多項式并行模乘電路框架如圖5 所示,包括3 個計算電路: 并行預加電路、并行乘法電路和后加電路,分別對應圖2 中(1)～(3).通過預加電路并行計算RA和Rs,如RA=(AH+AL)·mod8192 表示 (a255,…,a128)與(a127,…,a0)對應位置的系數(shù)相加,(a255+a127)mod8192為其中1 組預加電路,共128 組電路構成計算Aij的預加電路.同理,Rs的計算方式類似,每個對應系數(shù)s相加,但其結果的數(shù)值范圍從[ -4,4]變?yōu)閇 -8,8],對應圖5 中右邊Sij的預加電路陣列.預加電路輸出的信號RA和Rs將被傳輸至并行乘法電路(MACII)的輸入端.

在并行乘法電路中,MACI的輸入從存儲AH、AL、SH和SL的寄存器獲取.該單元用于計算P0和P1,而MACII單元用于處理RA和Rs的乘積,所產(chǎn)生的信號P0、P1和P2將被裝載至后加電路的寄存器隊列.電路結構如圖5 所示,包括2 組MACI和1 組MACII.該電路以壓縮關鍵路徑時長為目的,利用各模塊電路的并行執(zhí)行策略來縮短運算的執(zhí)行時間.

圖5 基于Karatsuba的多項式并行模乘電路

后加電路的功能為調(diào)整各自系數(shù)正負再累加.該步驟對應于Saber 算法運算內(nèi)部的模約規(guī)則,實現(xiàn)冪次的降冪化簡,如ax256化簡后為 -ax0,ax257化簡后為 -ax1,逐一降冪化簡.在并行乘法電路中,P0、P1和P2均為255×13 bits,其最高次冪為254,因此無需降冪化簡.但后加電路涉及降冪化簡操作,如圖2 中(3)的P0x256運算,即P0x256中每一項的冪次均超過255.根據(jù)Saber 算法以P為不可約多項式的模約規(guī)則,P0中所有系數(shù)均變?yōu)樨撎?因此P0x256+P1經(jīng)后加電路計算變?yōu)镻1-P0.此處的運算對應于同冪次系數(shù)間的計算,共256 項的并行運算;同理 (P2-P0-P)x128的降冪化簡類似.最終運算得結果Rk,其對應于圖1 算法中的輸出.

3 實驗結果與分析

使用Modelsim 和MATLAB 軟件對設計的硬件電路進行仿真,并在TSMC 65 nm 工藝下,利用Synopsys公司的DC軟件進行電路的可綜合性驗證.通過仿真平臺提取電路的性能參數(shù),采用時序、功耗和面積作為評估指標.

3.1 并行乘法器的時序

時序信息反映電路的工作狀態(tài).圖6 為并行乘法器時序仿真波形,分為初始化(80tclk)和相乘(137tclk)兩個工作狀態(tài).由于本文融合Karatsuba 算法與壓縮關鍵路徑的策略可彌補核心算子時序路徑過長的計算缺陷,因此相乘的狀態(tài)可分為3 個計算階段.階段1,預加狀態(tài)(Pre-add)占用4tclk計算時長,該并行預加狀態(tài)(Parallelpre-Add)的波形分別對應于圖5 中RA、Rs的計算電路;階段2,乘法狀態(tài)占用 131tclk計算時長;階段3,后加狀態(tài)(Post add)以2tclk時長結束RK的計算.依據(jù)流水線的計算特點,下一輪數(shù)據(jù)(Next data)的加載可在 137tclk的相乘階段同時進行.因此可不考慮初始化的數(shù)據(jù)加載,單次乘法所需計算周期為 137tclk,該并行運算方式將加速Saber 算法中向量間的內(nèi)積計算和矩陣-向量相乘.

圖6 并行乘法器時序仿真波形

表1 為本文與不同文獻在電路性能上的數(shù)據(jù)比較.在時鐘頻率為250 MHz 條件下,RK運行所需的計算周期為 137tclk,較文獻[6]-High Speed I 256、文獻[12]均提速46.50%.式(16)表明該并行乘法器具有較高的速度性能.

表1 本文與相關文獻的電路性能數(shù)據(jù)比較

式中,tclk1和tclk2分別代表對比文獻的計算周期和本文乘法器的計算周期;tclk為單個時鐘周期.

3.2 并行乘法器的面積功耗

由表1 可知,本文乘法器的面積開銷為927.32 kμm2,較文獻[6]-High Speed I 256、文獻[12]大5～7倍;功耗開銷為87.83 mW,較文獻[6]-High Speed I 256、文獻[12]大6～7 倍.由此可知,Karatsuba 算法提升乘法器運算速度的同時,也增加面積與功耗的開銷.

圖7 為并行乘法器各模塊面積占比和功耗占比.由圖可知,預加電路面積和功耗占比均最低,分別為2.35%和1.90%;在硬件電路中,并行乘法電路面積和功耗占比均最高,分別占54.48%和41.48%.另外由于Karatsuba 算法的引入,控制電路也占據(jù)28.78%的面積開銷和42.15%的功耗開銷.控制部分的開銷多數(shù)源自寄存器的消耗,后加電路的面積和功耗分別占據(jù)14.39%和14.48%.綜合分析,面向Saber 算法并行乘法器的硬件資源開銷主要分布于控制電路和并行相乘電路.

圖7 各模塊面積占比和功耗占比

4 結論

通過對Saber 算法內(nèi)模多項式運算瓶頸和Karatsuba 算法的分析,在分解核心算子的運算機制基礎上結合并行運算電路,實現(xiàn)面向Saber 算法的并行乘法器設計.本方案使用壓縮關鍵路徑的方式彌補核心算子時序路徑過長的缺陷.實驗結果表明,在工作頻率250 MHz 下,并行乘法器的計算周期為137tclk,功耗為87.83 mW,面積為927.32 kμm2.與常規(guī)計算方式相比,該乘法器可減少46.50%的運算時間.由于核心算子分布于Saber 算法內(nèi)部的密鑰生成、加密和解密各個階段,所以采用并行壓縮的流水線設計思想,對提高Saber 算法的硬件IP 核性能具有理論研究意義和實際應用價值.