陳 韜 李慧琴 李 偉 南龍梅 杜怡然

(戰(zhàn)略支援部隊信息工程大學(xué) 鄭州 450000)

1 引言

量子破譯算法對RSA, EIGamal, ECC公鑰密碼產(chǎn)生了嚴(yán)重的威脅。Shor[1]在1994年發(fā)表了名為《Polynomial Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer》(《量子計算機(jī)上的質(zhì)因數(shù)分解和離散對數(shù)的多項式時間算法》)的論文，認(rèn)為在量子計算機(jī)上實現(xiàn)大整數(shù)因式分解僅需多項式時間，而在經(jīng)典計算機(jī)上用現(xiàn)今最快的算法需要指數(shù)倍的時間。在此背景下，后量子公鑰密碼算法設(shè)計在網(wǎng)絡(luò)信息安全領(lǐng)域已成為新興的研究方向。

美國國家標(biāo)準(zhǔn)技術(shù)研究所(National Institute of Standards and Technology, NIST)從2012年開始啟動后量子密碼方向的研究。2018年，NIST進(jìn)行了第1輪入圍算法的討論，截止到2020年10月27日，NIST公布了第3輪入圍候選者[2,3]，其中包括基于格的算法、基于編碼的算法、多變量的算法和Hash函數(shù)的簽名算法。加密算法包括Classic McEliece, CRYSTALS-Kyber, NTRU與Saber，簽名算法包括CRYSTALS-Dilithium, Falcon與Rainbow，其中CRYSTALS-Kyber, NTRU, Saber, CRYSTALS-Dilithium與Falcon都屬于基于格的密碼。2022年，第3輪標(biāo)準(zhǔn)化結(jié)果公布，屬于格基密碼的CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon確定入選。與其他幾種后量子公鑰密碼算法相比，基于格的密碼算法有以下優(yōu)點：可證明安全性、公私鑰尺寸更小、計算速度更快以及在格理論密碼系統(tǒng)出現(xiàn)之前，沒有合適的問題可以用于構(gòu)造同態(tài)加密系統(tǒng)。綜上所述，格基密碼方案被認(rèn)為是最有前途的用于公鑰加密和數(shù)字簽名的后量子密碼算法。隨著格基后量子公鑰密碼的不斷發(fā)展與研究，國內(nèi)也開始為量子計算機(jī)對傳統(tǒng)密碼算法帶來的沖擊做準(zhǔn)備。2018年11月，由歐洲電信標(biāo)準(zhǔn)化協(xié)會主辦的第六屆量子安全國際會議在京開幕。中國科學(xué)院信息工程研究所副所長荊繼武在會上表示，中國或?qū)⒂?022年左右開展后量子密碼算法標(biāo)準(zhǔn)化的工作，于2025年左右實現(xiàn)商業(yè)化應(yīng)用落地。此表明未來常用格基公鑰密碼多樣，其中參數(shù)結(jié)構(gòu)迥異需要可重構(gòu)架構(gòu)去實現(xiàn)。因此，設(shè)計一種可滿足不同算法中的多項式乘法架構(gòu)具有重要意義。

針對不同參數(shù)，2019年，麻省理工學(xué)院的Banerjee等人[4]提出了一種采用Barrett取模算法可重構(gòu)不同模數(shù)的多項式乘法實現(xiàn)方法。最終在不加流水線前提下，最大頻率可達(dá)100 MHz。2020年，來自慕尼黑工業(yè)大學(xué)的Fritzmann等人[5]將格基后量子密碼擴(kuò)展到RISC-V架構(gòu)上實現(xiàn)了3種不同的算法，其中就模數(shù)不同的架構(gòu)和內(nèi)存上的訪問方案進(jìn)行了探究。此前大多數(shù)研究將NTT的旋轉(zhuǎn)因子進(jìn)行了預(yù)計算，并將其存儲在單獨的內(nèi)存中，但對于高次多項式會占用過大面積，考慮到動態(tài)計算延遲會增加，所以此設(shè)計結(jié)合預(yù)計算和動態(tài)微擾度計算的優(yōu)勢，提出了一種混合使用方法。對于次數(shù)較大的多項式，例如在NewHope-512和NewHope-1 024中，使用動態(tài)計算的方式，否則使用預(yù)先計算的表，例如在Kyber算法中應(yīng)用。針對不同項數(shù)和模數(shù)，2021年華中科技大學(xué)的劉冬生團(tuán)隊[6]針對數(shù)論變換參數(shù)的多樣性，提出一種基于隨機(jī)存取存儲器(Random Access Memory, RAM)的可重構(gòu)多通道數(shù)論變換單元。在數(shù)論變換單元設(shè)計中，按時間抽取的基礎(chǔ)上改進(jìn)多通道架構(gòu)，并提出一種優(yōu)化地址分配方法。

針對不同格基后量子公鑰密碼算法，項數(shù)相同，且模數(shù)都在16 bit以內(nèi)的Kyber與Saber算法經(jīng)常作為可重構(gòu)多項式乘法的研究對象。2020年，文獻(xiàn)[7]中的設(shè)計采用單路迭代的方式，迭代使用模乘單元實現(xiàn)Kyber, Saber與Newhope算法中的多項式乘法，此方法花費時間較長但占用較小面積。2022年，華中科技大學(xué)團(tuán)隊基于此兩種算法采用Schoolbook和Toeplitz方法來實現(xiàn)[8]，針對每種算法進(jìn)行了資源效率和性能權(quán)衡策略下可變參數(shù)和指令編程的靈活實現(xiàn)。此外，以同一團(tuán)隊提出的Kyber與Dilithium算法為研究對象也是常見選擇[9]，針對不同模數(shù)進(jìn)行模乘單元的可擴(kuò)展重構(gòu)設(shè)計。清華大學(xué)劉雷波團(tuán)隊[10]提出的設(shè)計作為支持算法最多的硬件實現(xiàn)，可支持Kyber, Saber, NTRU, Dilithium, McEliece與Rainbow等6種格基后量子公鑰算法，采用陣列的形式最大限度地復(fù)用運算單元。因此，通過分析不同格基后量子公鑰密碼中多項式乘法運算特征，得到不同重構(gòu)參數(shù)需求，提出統(tǒng)一運算網(wǎng)絡(luò)是目前關(guān)鍵方向之一。

針對上述分析，本文提出一種面向多種難題格基后量子公鑰密碼算法的可重構(gòu)多項式乘法架構(gòu)。通過分析不同參數(shù)多項式乘法的PtNTT實現(xiàn)算法，就其核心操作特征設(shè)計得到一個滿足實現(xiàn)不同基次的4×4串并行可轉(zhuǎn)換運算單元架構(gòu)，并設(shè)計了其內(nèi)部的可重構(gòu)模乘單元。面向不同格基后量子密碼公鑰算法中的多項式乘法進(jìn)行系數(shù)地址的分配需求分析，具體體現(xiàn)在系數(shù)地址生成邏輯、同個RAM中Bank劃分邏輯以及實際地址與虛擬地址對應(yīng)邏輯。實際來看，是在前述運算單元最佳性能范圍內(nèi)實現(xiàn)數(shù)據(jù)分配機(jī)制的優(yōu)化，基于上述機(jī)制得到一種滿足基k-NTT的多Bank數(shù)據(jù)存儲結(jié)構(gòu)。

2 多項式乘法運算特征分析

2.1 多項式乘法重構(gòu)參數(shù)分析

面對未來對多種格基后量子密碼算法的需求，只是設(shè)計滿足一種參數(shù)或形式的多項式乘法具有局限性。本節(jié)希望采用同種形式算法，為多種參數(shù)形式的多項式乘法構(gòu)造出一種可重構(gòu)架構(gòu)。在NIST第3輪候選標(biāo)準(zhǔn)算法范圍內(nèi)，除了Falon算法需采用FFT來實現(xiàn)多項式乘法，其余算法都可采用NTT或變換后的算法實現(xiàn)。

依據(jù)不同算法中乘法的具體參數(shù)，將其總結(jié)為3種不同形式的差異——項數(shù)n、模數(shù)q以及模多項式f(x)。較多文獻(xiàn)針對的多項式乘法參數(shù)多為符合Kyber, Saber和Dilithium的2的冪次項數(shù)，關(guān)于NTRU中的素數(shù)項數(shù)涉及較少，通過文獻(xiàn)[11]的闡述，可通過擴(kuò)展項數(shù)使得其實現(xiàn)可使用NTT算法。模數(shù)中，有滿足q=1modn素數(shù)參數(shù)的Kyber與Saber算法，也有符合Dilithium與NTRU算法的2的冪次模數(shù)，前者可采用PtNTT算法架構(gòu)的實現(xiàn)方式達(dá)到高效的目標(biāo)，同時由于模數(shù)位數(shù)差別較大，需要構(gòu)造適應(yīng)不同參數(shù)的模乘運算硬件結(jié)構(gòu)，后者可通過擴(kuò)大模數(shù)的NTT操作后直接取低位。此外，需要注意不同模多項式對于采用算法中參數(shù)的影響。

其中，ωn=1 modq，ωn/2=-1 modq。如圖1(b)所示。通過對比上述兩種不同的模多項式，可觀察到不同算法除了對應(yīng)單位根不同，其運算結(jié)構(gòu)具有相似性。

圖1 不同模多項式依據(jù)中國剩余定理映射示意圖

在NTRU算法中，當(dāng)模多項式為(xn–1)/(x–1)=xn–1+xn–2+···+1時，可先使用NTT方法進(jìn)行擴(kuò)項數(shù)后的模xn–1的運算，再進(jìn)行模xp–1的運算。由于xp–1+xp–2+···+1是xp–1的因式，所以可以先進(jìn)行約簡高次多項式，再約簡因式低次多項式的方式。最后通過判斷比較系數(shù)得到模xp–1+xp–2+···+1的多項式。

上述重構(gòu)參數(shù)分析后可總結(jié)為不同格基后量子公鑰密碼算法的多項式乘法架構(gòu)特征：都可采用NTT算法的思想來實現(xiàn)，可采用相似的蝶形運算架構(gòu)；其具體操作包括不同長度的模乘與模加減，位寬在32 bit以內(nèi)；整體實現(xiàn)方式為多輪相同操作迭代完成，適合深度流水和高度并行操作處理。

2.2 可重構(gòu)多項式乘法運算網(wǎng)絡(luò)分析

基于上述關(guān)于格基后量子公鑰密碼算法中多項式乘法運算特征的分析，本小節(jié)將通過整理具體算法中的運算流程，總結(jié)出可重構(gòu)核心運算單元架構(gòu)?？芍貥?gòu)實現(xiàn)不同參數(shù)的多項式乘法時，將其分類為可直接用PtNTT算法實現(xiàn)、通過擴(kuò)大模數(shù)間接采用PtNTT算法以及通過同時擴(kuò)展模數(shù)和項數(shù)采用混合基PtNTT算法來實現(xiàn)。

第1種分類具體包括Kyber和Dilithium算法，項數(shù)256都為4的冪次，且模數(shù)和項數(shù)都滿足q≡1modn，不同的僅有模數(shù)大小，需通過可重構(gòu)模乘單元的設(shè)計來解決不同模數(shù)位數(shù)大小的現(xiàn)狀。第2種分類只包括Saber算法，其模數(shù)為2的冪次，不能直接使用NTT算法來實現(xiàn)，可通過將模數(shù)擴(kuò)展為NTT友好的數(shù)據(jù)量，且要求為最小友好數(shù)據(jù)。既保證了可采用NTT這一本身計算復(fù)雜度低的算法，又可盡量減少多余位數(shù)增加的面積消耗和時間損耗成本。最后一種分類則是以NTRU為主體的不同參數(shù)算法，其項數(shù)為素數(shù)，模數(shù)為2的冪次。此類項數(shù)已不滿足n為2的冪次這一條件，為了解決此問題，只能通過擴(kuò)展項數(shù)使其可通過NTT算法來實現(xiàn)。在擴(kuò)域過程中，由于此類算法模多項式有(xp-1)/(x-1)與xp-1，先采用NTT算法實現(xiàn)模xn-1， 再根據(jù)傳統(tǒng)模多項式的算法進(jìn)行模xp-1操作。這就要求在擴(kuò)域時，項數(shù)擴(kuò)展必須大于原來的兩倍，且盡可能小。在選擇擴(kuò)展后的項數(shù)時，需使用混合基NTT的算法，為實際減小項數(shù)帶來的面積和時間成本大幅度降低提供可行性。最終適于可重構(gòu)架構(gòu)的多項式乘法參數(shù)如表1所示。

表1 適于可重構(gòu)架構(gòu)的多項式乘法參數(shù)

其中出現(xiàn)次數(shù)最多的項數(shù)為256，且為4的冪次，其余項數(shù)509, 677, 821與701可分別擴(kuò)展為256×4, 512×3, 9×64×3與512×3。256, 512,9×64代表采用NTT算法的項數(shù)，其中包括2, 3與4的冪次，說明可重構(gòu)架構(gòu)需同時滿足基2, 基3與基4的基本運算操作；“×4”“×3”則說明需要分成3組和4組進(jìn)行PtNTT算法的分組點乘計算。以NTRUhps4096821算法為例，其實際運算流程為如算法1所示。

根據(jù)上述流程需要確定可重構(gòu)核心運算單元所支持的基k-NTT算法，最頻繁出現(xiàn)的為基4操作，且實質(zhì)上是基2操作的兩層復(fù)合操作，所以需要盡可能通過并行或串行基2來實現(xiàn)基4；基3則是為支持盡可能減少較大項數(shù)出現(xiàn)的操作，其完整實現(xiàn)也是必不可少的。算法2—算法4詳細(xì)描述了不同基k-NTT算法的核心運算流程。

其中，i=0,1,2,...,n/3-1。

如表1所示，算法5中的T0, T1與算法6中的T2,T3進(jìn)行的是相同的運算，算法5中的T2, T3與算法6中的T0, T1進(jìn)行的是相同的運算，具有可重構(gòu)的基礎(chǔ)。此外，已知需要一種架構(gòu)同時實現(xiàn)基4、基3與基2的蝶形運算，且基4的基本操作需要4個乘法，可同時滿足4次基2的操作，基3的基本操作則是需要3個乘法，選擇基4或基2與基3重構(gòu)需要明確。若選擇基2與基3蝶形運算進(jìn)行重構(gòu)，實現(xiàn)1次核心操作，基2運算會浪費1個乘法單元，基4運算會浪費2個乘法單元；若選擇基4與基3蝶形運算進(jìn)行重構(gòu)，僅基3運算浪費1個乘法單元。所以采用基4核心基本運算單元，在此基礎(chǔ)上，進(jìn)行其他運算功能的增加。

則a(x)=a0(z)+x·a1(z)+x2·a2(z)， 同 理b(x)=b0(z)+x·b1(z)+x2·b2(z)。最終乘積結(jié)果多項式用c(x)表示。

算法1 NTRUhps4096821采用混合基PtNTT的多項式乘法

算法5 基4-NTT算法的核心運算操作拆解，其中μ=ωn/4

上述公式推導(dǎo)了3路采用PtNTT算法進(jìn)行點乘運算的具體流程，4路點乘運算與之同理，下述表格中的算法具體列出了化簡后的流程。由于點乘操作是在多項式乘法中NTT與INTT之間進(jìn)行的，故僅將點乘流程在下述表格中體現(xiàn)出來，如算法7、算法8所示。

算法7 4路PtNTT中的點乘算法

通過上述分析，不同格基后量子密碼算法中多項式乘法核心操作的實現(xiàn)都有共通之處，通過提煉相似操作，以最小的面積冗余實現(xiàn)不同參數(shù)的多項式乘法。

3 可重構(gòu)多項式乘法運算架構(gòu)設(shè)計

3.1 串并行可轉(zhuǎn)換型運算單元架構(gòu)

依據(jù)第2節(jié)關(guān)于核心運算可重構(gòu)過程的建立，需構(gòu)建一個同時滿足基4、基3與基2操作的核心蝶形運算架構(gòu)。根據(jù)算法5中針對基4-NTT核心運算操作拆解，具體結(jié)構(gòu)如圖2所示。

圖2 基4-NTT/INTT核心蝶形運算架構(gòu)圖

若本設(shè)計以上述蝶形運算架構(gòu)為基礎(chǔ)進(jìn)行可重構(gòu)單元的搭建，帶來的面積冗余過大。以紅框內(nèi)的3個模乘單元為基準(zhǔn)，前后需要各添加1個模乘單元，模加減單元數(shù)量并不會降低。觀察到其拆解運算具有高度重合性，將具有相同操作的連線用相同顏色標(biāo)注出來，整體可重構(gòu)運算單元與單個基4-NTT/INTT內(nèi)包含的模乘單元數(shù)量相同，將操作分為4個部分，即PE0, PE1, PE2與PE3。同理，基3蝶形運算也可在4個PE內(nèi)實現(xiàn)。

故實現(xiàn)基4數(shù)論變換算法結(jié)構(gòu)至少為2×2、包含4種不同分操作的基本運算單元 (PE0, PE1,PE2與PE3)，其中的具體分操作是對基4與基3的可重構(gòu)轉(zhuǎn)化。本設(shè)計面向算法的參數(shù)要求為0～32 bit，若僅將其中最大位寬固定到32 bit，對于小位寬的多項式乘法，將帶來3/4面積上的冗余，不滿足可重構(gòu)中關(guān)于“有效利用硬件資源從而達(dá)到節(jié)約邏輯資源”的要求[12]。此擴(kuò)展性設(shè)計被舍棄，故將最大位寬縮小到16 bit，滿足最小參數(shù)為3 329(12位)的要求。因此，2×2運算單元可實現(xiàn)1次16 bit的基4/3的核心操作。當(dāng)實現(xiàn)16～32 bit參數(shù)的多項式乘法時，一個2×2運算單元僅能實現(xiàn)1次32 bit基4/3的核心操作中涉及乘法的1個步驟。考慮到對于最大工作頻率的限制，需要全流水實現(xiàn)。若通過復(fù)用此基本運算單元架構(gòu)，浪費時間周期數(shù)較多，帶來的性能損耗較大，故設(shè)計為4×2×2(4×4)的整體運算單元架構(gòu)，可完整實現(xiàn)1次32 bit的基4/3的核心操作。整體電路結(jié)構(gòu)如圖3所示。

圖3 串并行可轉(zhuǎn)換型運算單元結(jié)構(gòu)圖

上述結(jié)構(gòu)圖對重構(gòu)設(shè)計進(jìn)行了描述，其中4個可重構(gòu)核心運算單元(單元1—單元4)構(gòu)成了整體運算架構(gòu)，僅在并行計算點乘中的Ri,j時，其支持的運算略有不同。此外，在實現(xiàn)32 bit模乘時，各單元內(nèi)的PEi共同實現(xiàn)圖4的功能，每個PEi完成其中的1個乘法和附加運算，實際上PEi內(nèi)的單個乘法實現(xiàn)的是32 bit乘法(圖4單元中的選擇信號sel為0時)。

圖4 適于Kyber算法的4-Bank存儲系數(shù)情況

圖3將單元一的運算框圖進(jìn)行了具體描繪，其復(fù)雜的連接和選擇關(guān)系代表可同時實現(xiàn)16 bit基4/3/2的NTT和INTT算法操作，紅藍(lán)箭頭代表虛線框內(nèi)基于數(shù)據(jù)選擇器的互連關(guān)系。①代表單元內(nèi)部PEi之間的互連，實現(xiàn)16 bit基4/3/2的NTT和INTT算法操作；②代表單元之間同種PE以及不同單元之間首末PEi的互連，實現(xiàn)32 bit基4/3/2的NTT和INTT算法操作。

3.2 可重構(gòu)模乘單元設(shè)計

根據(jù)第2節(jié)針對模數(shù)的總結(jié)分析，模數(shù)支持位寬為0～16 bit與17～32 bit。直接設(shè)置大比特位寬是一種解決思路，然而相較于小比特位寬具有較大的面積冗余，且為了支持未來可能出現(xiàn)的其他位寬模數(shù)，本設(shè)計將通過串行16 bit的模乘來實現(xiàn)3 bit的模乘，同時通過運算單元的并置來實現(xiàn)4個16 bit的模乘。既解決了實現(xiàn)小比特位寬運算帶來的面積冗余，也避免了小比特位寬串行實現(xiàn)導(dǎo)致的時間成本的增加。

選擇具體模乘算法實現(xiàn)時，Montgomery算法與Barrett算法均具有較好的可重構(gòu)功能，支持任意比特的模乘。32 bit Montgomery模乘算法具體需要3個32 bit乘法，但需要進(jìn)行預(yù)處理與后處理，時間成本會成倍增加；32 bit Barrett模乘算法則具體需要4個32 bit乘法，32 bit乘法可通過4個16 bit乘法組合實現(xiàn)，16 bit Barrett模乘算法也可通過此4個16 bit乘法實現(xiàn)，如算法9所示。從而可獲得既可實現(xiàn)16 bit模乘又可實現(xiàn)32 bit乘法的可重構(gòu)模乘單元結(jié)構(gòu)。

4 多項式乘法存儲數(shù)據(jù)分配機(jī)制

4.1 滿足基k-NTT的數(shù)據(jù)分配機(jī)制

(1) Kyber與Saber算法

整體采取基4-2PtNTT方法來實現(xiàn)，即整體4×4單元其中每1×4單元實現(xiàn)n=64的基4 NTT操作。以裝載64個多項式系數(shù)的空間為1個RAM單元，需要同時讀寫4個數(shù)據(jù)?？傻玫骄唧w的分組情況如圖4所示。

圖4所示的4-Bank存儲系數(shù)的劃分情況完全符合圖5所示Kyber算法中多項式乘法NTT/INTT要求的地址互斥關(guān)系。其次就地址生成規(guī)律與劃分規(guī)律進(jìn)行討論分析。理論上需要3種計數(shù)器進(jìn)行地址的生成，應(yīng)將其進(jìn)行精簡優(yōu)化。根據(jù)算法要求，分配方案需要同一周期在一個RAM(N/4，也為下面論述中的n項)中讀出4個數(shù)據(jù)，其余3項數(shù)據(jù)可在基數(shù)據(jù)的基礎(chǔ)上進(jìn)行改變。例如在第1子輪16項數(shù)據(jù)的基礎(chǔ)上加上0x010000, 0x100000與0x110000。最外部需要1個計數(shù)器Cnt0，總共運行l(wèi)og4n輪，內(nèi)部循環(huán)Cnt1計數(shù)n/4次。內(nèi)部循環(huán)每滿4log2n-1-Cnt0加上 4log2n-Cnt0，變化量實質(zhì)上與Cnt0有關(guān)，所以無需新添計數(shù)器的數(shù)目。

圖5 Kyber算法中多項式乘法NTT/INTT地址互斥連通圖

故第1 子輪基數(shù)據(jù)為0 x 0 0 X X X X，其中XXXX代表Cnt1值，循環(huán)加1；第2子輪基數(shù)據(jù)為0xXX00XX；第3子輪基數(shù)據(jù)為0xXXXX00。其余3項數(shù)據(jù)在基數(shù)據(jù)基礎(chǔ)上，將其中00替換為01, 10和11。所以最終地址在Cnt0和Cnt1的控制下進(jìn)行轉(zhuǎn)換。

整體劃分規(guī)律則是按照二進(jìn)制“1”的奇偶個數(shù)進(jìn)行劃分，偶數(shù)個“1”劃分為第0、第2個Bank，奇數(shù)個“1”劃分為第1、第3個Bank。然后按照a[0]^a[4], a[3]進(jìn)行劃分，在第0、第2個Bank中，當(dāng)a[3]為1且a[0]^a[4]為0或a[3]為0且a[0]^a[4]為1時，劃分為第2個Bank，反之分為第0個Bank。在第1、第3個Bank中，當(dāng)a[3]為1且a[0]^a[4]為0或a[3]為0且a[0]^a[4]為1時，劃分為第1個Bank，反之分為第3個Bank。高log2n–2位代表其在Bank內(nèi)的實際地址。Saber算法參數(shù)類型與之相同。

(2) Dilithium算法

與Kyber相似，Dilithium算法內(nèi)多項式乘法項數(shù)同為256，但其模數(shù)以及適應(yīng)NTT形式不同。此算法可完全按照傳統(tǒng)NTT算法來實現(xiàn)，本文為減少控制結(jié)構(gòu)的復(fù)雜性，故同樣采用基4-2PtNTT算法來實現(xiàn)，由于模數(shù)長度為Kyber算法的兩倍，需要4×4個運算單元，每1×4個運算單元實現(xiàn)基4中1個階段的32 bit模乘運算，最終共同實現(xiàn)1次32 bit基4操作。一個裝載64個多項式系數(shù)的RAM單元，也需要同時讀寫4個數(shù)據(jù)。地址生成規(guī)律、Bank劃分規(guī)律與Kyber算法相同，只是將a[3]轉(zhuǎn)換為a[3]^a[7]。

算法9 16 bit模乘、32 bit乘法

(3) NTRUhps2048509算法

經(jīng)過第2節(jié)針對NTRU算法進(jìn)行NTT友好型參數(shù)轉(zhuǎn)換后，其項數(shù)為1 024，整體采用基4-2Pt-NTT方法。以裝載256個多項式系數(shù)的空間為一個RAM單元，需要同時讀寫4個數(shù)據(jù)。與前兩種分配方式相比，每個Bank內(nèi)的存儲量增加，不同類算法可重構(gòu)實現(xiàn)表明可共用存儲面積。且為了控制結(jié)構(gòu)復(fù)雜度降低，分配方式需要同時滿足兩者的要求。所以前文所滿足的多種分配方式既需要滿足此算法的要求，也需要降低控制結(jié)構(gòu)復(fù)雜度。

實際上，在對Kyber與Dilithium中小項數(shù)的劃分情況進(jìn)行分析時，其具體分組情況具有多樣性，并不如圖4所示僅有1種劃分情況。為保證此算法中對應(yīng)的大項數(shù)劃分可成功實現(xiàn)，減少由于地址生成邏輯復(fù)雜性的提高帶來整體單位面積性能的降低，將劃分情況更加偏向大項數(shù)劃分，在滿足此類情況的劃分前提下同時滿足Kyber, Dilithium中小項數(shù)的劃分情況，即Bank劃分規(guī)律上述算法是相一致的。

地址生成規(guī)律實質(zhì)上也與第(1)節(jié)陳述類似，本質(zhì)在于項數(shù)不同帶來的計數(shù)范圍的不同。Cnt0,Cnt1分別與log4n, n/4有關(guān)。其地址生成規(guī)律變?yōu)榱说? 子輪基數(shù)據(jù)為0 x 0 0 X X X X X X，其中XXXXXX代表Cnt1值，循環(huán)加1；第2子輪基數(shù)據(jù)為0xXX00XXXX；第3子輪基數(shù)據(jù)為0xXXXX00XX；第4子輪基數(shù)據(jù)為0xXXXXXX00。其余3項數(shù)據(jù)在基數(shù)據(jù)基礎(chǔ)上，將其中00替換為01, 10和11。

(4) NTRUhps2048677與NTRUhrss701算法

第2節(jié)針對NTRU算法進(jìn)行NTT友好型參數(shù)轉(zhuǎn)換后，其項數(shù)都為1 536(512×3)，整體采用基2數(shù)論變換與3路預(yù)處理相結(jié)合的方法。以裝載512個多項式系數(shù)的空間為一個RAM單元。作為分組數(shù)據(jù)較大的算法，且針對32 bit基2蝶形操作的4路并行實現(xiàn)方案，需要同時讀寫4個數(shù)據(jù)。

其地址生成規(guī)律與基二蝶形操作相關(guān)，與上述基4操作具有相通之處。Cnt0, Cnt1分別與log2n,n/2有關(guān)。其地址生成規(guī)律變?yōu)榈?子輪基數(shù)據(jù)為0 x 0 X X X X X X X X，其中X X X X X X X X 代表Cnt1值，循環(huán)加1；第2子輪基數(shù)據(jù)為0xX0XXXXXXX；依此類推，最后1子輪基數(shù)據(jù)為0xXXXXXXXX0。其余一項數(shù)據(jù)在基數(shù)據(jù)基礎(chǔ)上，將其中0替換為1。

(5) NTRUhps4096821算法

作為NTT友好型參數(shù)轉(zhuǎn)換后項數(shù)最大的多項式乘法，其項數(shù)為1 728(9×64×3)，整體采用混合基數(shù)論變換與3路預(yù)處理相結(jié)合的方法。需要先進(jìn)行基3數(shù)論變換運算，再進(jìn)行基4數(shù)論變換運算，然后進(jìn)行點乘，最后進(jìn)行逆數(shù)論變換運算。

由于是混合基次數(shù)論變換，其地址生成邏輯與上述論述出入較大，同樣保證以簡單的布爾邏輯與循環(huán)計數(shù)來實現(xiàn)?；?數(shù)論變換以64為數(shù)量單位的地址塊為整體進(jìn)行地址轉(zhuǎn)換，則簡化為n=9的蝶形操作，擴(kuò)展到64×9可直接通過移位實現(xiàn)；基4數(shù)論變換則以9為數(shù)量單位的地址塊為整體進(jìn)行地址轉(zhuǎn)換，與上述基4數(shù)論變換地址生成規(guī)律吻合，即與第(1)節(jié)論述完全相同。

在對Bank劃分規(guī)律進(jìn)行分析前，需要注意的是，在混合基次過程中基數(shù)變換的這一階段，由于存在讀出的數(shù)據(jù)經(jīng)過運算不再寫回到原來的地址上這一問題。若以增加存儲面積作為代價，多出1倍的存儲區(qū)，分別用來存儲3-Bank與4-Bank的數(shù)據(jù)。本身作為最大項數(shù)的多項式乘法，其存儲面積占用較大，使得其他算法的實際有效占用率較低。此問題主要出現(xiàn)在基3與基4混合基操作時，同一系數(shù)在不同分配操作中占據(jù)不同的Bank與實際內(nèi)存地址。所以解決思路為不額外占用存儲面積的前提下完成虛擬地址與實際地址的相統(tǒng)一。

為使地址相統(tǒng)一，將RAM劃分為3與4的最小公倍數(shù)——12個Bank。同時以兩種劃分規(guī)律為抓手，分為0.BankA、1.BankB、···、2.BankC與2.BankD。但實際上，若是均勻分配(按照63×11+70)，最終并不能正確匹配實際運算過程中的地址，會出現(xiàn)讀寫數(shù)據(jù)有可能會存在于同一Bank中從而產(chǎn)生讀寫數(shù)據(jù)沖突。需通過整塊地址的調(diào)整最終得到可同時滿足基3與基4的多Bank數(shù)據(jù)存儲方案。

以適應(yīng)基3的存儲量9的存儲單元為整體，稱為存儲塊。存儲塊內(nèi)的系數(shù)地址是連續(xù)變化的，則存儲塊的塊號是以適應(yīng)基4的存儲量64進(jìn)行計數(shù)，可劃分為4個Bank；當(dāng)以適應(yīng)基4的存儲量64的存儲單元為整體，稱為存儲條。存儲條內(nèi)的系數(shù)地址是連續(xù)變化的，則存儲塊的塊號是以適應(yīng)基3的存儲量9進(jìn)行計數(shù)，可劃分為3個Bank。最后綜合來看可分為12個Bank。為方便實際地址到內(nèi)存地址的轉(zhuǎn)換，以存儲塊的形式進(jìn)行保存。最終具體12Bank地址劃分如圖6所示。

圖6 12-Bank地址劃分標(biāo)識圖

設(shè)計在應(yīng)用于多種算法中的多項式乘法時，此RAM存儲方式中1 Bank中存儲數(shù)據(jù)量最大為54，第(1)(2)(3)節(jié)中每個Bank最大存儲量為64，與之相近，無需修正。但只占用4個Bank，在控制邏輯中，可將其余無用Bank不添加進(jìn)可選擇范圍內(nèi)。第(4)節(jié)中每個Bank最大存儲量為128，為最大限度增大存儲面積的有效占用率，可將此類算法存儲模式分為8個Bank，將每個Bank存儲量降為64，前提需將此Bank劃分滿足其地址的讀寫互斥關(guān)系。

4.2 滿足基k-NTT的存儲單元設(shè)計

數(shù)據(jù)分配機(jī)制確定后，需要根據(jù)具體算法的實際需求設(shè)計出具有精簡式控制結(jié)構(gòu)的存儲單元，控制完成多項式系數(shù)的調(diào)度，計數(shù)使能信號的產(chǎn)生和轉(zhuǎn)換以及其他關(guān)鍵控制信號的產(chǎn)生。

在此基礎(chǔ)上精簡存儲單元的復(fù)雜度，并行度為16，RAM分組組數(shù)為12，每一輪運算地址的轉(zhuǎn)換需要計數(shù)器進(jìn)行輔助設(shè)計。以最簡單的基4蝶形操作為例，l og4(n/4)輪運算之間需要1個計數(shù)器Cnt0進(jìn)行輪數(shù)k的更新；每一輪運算內(nèi)部需要1個計數(shù)器Cnt1進(jìn)行4k次系數(shù)的調(diào)度；具體進(jìn)行系數(shù)調(diào)度時，計數(shù)器Cnt2進(jìn)制/與第1個輪數(shù)計數(shù)值Cnt0有關(guān)，每當(dāng)加到(n/16)4k重新以全新的數(shù)字進(jìn)行計數(shù)。若按照此設(shè)計方法至少需要3個計數(shù)器，最終4個讀地址由3個計數(shù)器的值加減組合得到。針對這一問題，需要通過布爾函數(shù)，移位等簡單邏輯運算將地址轉(zhuǎn)換進(jìn)行優(yōu)化，從而減少計數(shù)器的數(shù)目。

將計數(shù)器Cnt1(Cnt_Addr)進(jìn)數(shù)值設(shè)置為基本的n/4，實際系數(shù)是在此基礎(chǔ)上通過移位或其他簡單運算產(chǎn)生；計數(shù)器Cnt0(Cnt_RAM)將Cnt1的進(jìn)位信號作為計數(shù)使能信號；Cnt2則是計數(shù)器Cnt0值和Cnt1值共同決定，不需要再設(shè)置冗余的計數(shù)器。最終讀寫地址則是由計數(shù)器Cnt1值硬連線形成，根據(jù)Cnt_RAM值的不同，在讀數(shù)時，決定在不同的位置插入“00”, “01”, “10”或“11”。A ddr={2′bZ0,Cnt_Addr[log2n/4-1,0]}，填充的數(shù)據(jù)取決于不同的Bank選擇，填充位置則是由實現(xiàn)NTT的輪數(shù)Cnt0有關(guān)。根據(jù)地址漢明重量的奇偶性以及其中3位的不同將其分為4組。對于不同Bank地址的選擇生成邏輯具體為

對于單個Bank的地址生成邏輯Addr_Bank_wt=Addr_wt>>2， Addr_Bank_rd=Addr_rd>>2。對于圖7中的sel_x信號對應(yīng)上述地址選擇生成公式括號內(nèi)的判斷條件。

圖7 多端口RAM單元硬件設(shè)計框圖

若是較為復(fù)雜的混合基運算，由于在不同的基k蝶形操作中，存儲塊內(nèi)的數(shù)據(jù)量是不同的。整體以塊號為地址生成邏輯的基礎(chǔ)，之前基地址的簡化生成方式實際上利用了二進(jìn)制表示的優(yōu)勢，所以基3操作中基地址的形成以及其余地址的衍生不能伴隨簡單的硬連線完成。只能通過算法中簡單的乘加實現(xiàn)，×3通過移位和加來實現(xiàn)，×9則是迭代實現(xiàn)兩次×3。其次針對混合基多Bank的劃分規(guī)律進(jìn)行分析，實際上是基于數(shù)據(jù)量為9存儲塊的塊號進(jìn)行劃分，則是先根據(jù)基3的Bank劃分規(guī)律——當(dāng)(a[0]+a[1])mod3=0，劃分到第0個Bank；當(dāng)(a[0]+a[1])mod3=1，劃分到第1個Bank；當(dāng)(a[0]+a[1])mod3=2，劃分到第2個Bank。再根據(jù)上述基4蝶形操作中Bank劃分規(guī)律得到12Bank的具體劃分形式。最后將問題聚焦到系數(shù)對應(yīng)虛擬地址至Bank內(nèi)實際地址的轉(zhuǎn)換，混合基中多Bank中不再是上述可以直接通過簡單移位來實現(xiàn)地址轉(zhuǎn)換。且為了更容易兼容未來不同種情況的混合基地址轉(zhuǎn)換情況，設(shè)置4個查找表，將虛擬地址與實際地址進(jìn)行對應(yīng)，即4個6×576 bit大小的ROM存儲其對應(yīng)關(guān)系。最終基于PtNTT算法中其中一個分組對應(yīng)的存儲單元及對應(yīng)控制結(jié)構(gòu)如圖7所示。

存儲單元進(jìn)行Bank分配不沖突的優(yōu)化，實現(xiàn)了在不同的運算階段，讀出和輸入地址不沖突且Bank數(shù)量最小，從而保證了地址分配最優(yōu)的多端口RAM設(shè)計。

5 結(jié)果與比較

本文通過Vivado 2 019.1軟件進(jìn)行仿真綜合，芯片型號為Artix-7中的xc7a35tfgg484-3，最高工作頻率可達(dá)到152 MHz，共占用13 794個LUT硬件資源。

通過查閱并列舉近幾年相關(guān)文獻(xiàn)，發(fā)現(xiàn)與NTRU算法中的多項式乘法可重構(gòu)架構(gòu)相對較少，Kyber算法則是作為較易重構(gòu)的架構(gòu)，由于與Saber算法中項數(shù)相同易于重構(gòu)，與Dilithium則是同一團(tuán)隊研發(fā)，可采用相同的NTT算法架構(gòu)。本文則是將上述4種格基后量子密碼算法中的多項式乘法進(jìn)行重構(gòu)。

從可重構(gòu)功能和具體實現(xiàn)方式來說，文獻(xiàn)[7]中的設(shè)計支持NewHope, Kyber和Saber中16 bit以內(nèi)的多項式乘法，且為低并行度實現(xiàn)，占用面積小但花費周期數(shù)較多。文獻(xiàn)[8]雖然同時支持Kyber, Saber中的多項式乘法，然而分別采用Schoolbook和Toeplitz方法來實現(xiàn)，實際上使用兩種不同的乘法器，并不是可復(fù)用的，起碼會占用36個Toeplitz乘法器與支持Kyber算法中NTT實現(xiàn)方法的模乘單元。

文獻(xiàn)[9]、文獻(xiàn)[10]都是支持Kyber與Dilithium中多項式乘法的重構(gòu)。文獻(xiàn)[9]中兩種參數(shù)的花費時鐘周期數(shù)相同，說明其關(guān)鍵路徑限制在32 bit相乘，再加上32路蝶形運算單元，優(yōu)點是時鐘周期數(shù)較少，但單位面積性能不高。文獻(xiàn)[10]支持算法眾多，主要分為兩類—采用NTT方法實現(xiàn)的Kyber與Dilithium算法，采用分層Karatsuba方法的Saber,NTRU算法，在25 nm工藝下工作頻率高達(dá)500 MHz。雖然其占用面積較大，然而實現(xiàn)功能較多，可支持基于不同難題算法對應(yīng)的多項式乘法。文獻(xiàn)[13]中則是將Dilithium與Saber算法中的多項式乘法同時采用NTT架構(gòu)來實現(xiàn)的，通過改變擴(kuò)大Saber算法中的模數(shù)共用蝶形單元架構(gòu)，與本文設(shè)計思想相近。要說明的是，文獻(xiàn)[10]與文獻(xiàn)[13]是基于ASIC條件下完成，故未在表2中體現(xiàn)。

表2 基于FPGA不同多項式乘法架構(gòu)性能對比

文獻(xiàn)[14]提出了一種高效的混合基數(shù)MDF NTT架構(gòu)，適用于高性能大規(guī)模數(shù)據(jù)密碼處理器。靈活的設(shè)計使NTT架構(gòu)適應(yīng)各種參數(shù)集并且基數(shù)值的合理選擇有助于實現(xiàn)高性能。其支持Kyber以及與之參數(shù)要求相同的NewHope算法(現(xiàn)已落選)，靈活性范圍有限。文獻(xiàn)[6]則提出一種基于隨機(jī)存取存儲器(Random Access Memory, RAM)的可重構(gòu)多通道數(shù)論變換單元支持實現(xiàn)項數(shù)256～2048，模數(shù)在32 bit范圍內(nèi)。靈活性強(qiáng)的關(guān)鍵在于設(shè)計了基于RAM的可重構(gòu)模乘單元，針對特定參數(shù)(滿足q≡1mod2n條件)優(yōu)化的模乘器在資源消耗方面具有明顯的優(yōu)勢，但不適用于多參數(shù)可重構(gòu)設(shè)計。

通過上述分析，本文設(shè)計了實現(xiàn)Kyber, Saber,Dilithium和NTRU等4類算法中多項式乘法的可重構(gòu)架構(gòu)。在面向未來可能出現(xiàn)的格基后量子公鑰算法的形勢下，本文提出的架構(gòu)具有高靈活性的優(yōu)勢。經(jīng)對比可得，采用PtNTT算法的多項式乘法單元架構(gòu)其時延性能較多優(yōu)于其他文獻(xiàn)中的數(shù)據(jù)。這是由于選用算法本身帶來的時間復(fù)雜度低，4×4并行結(jié)構(gòu)和統(tǒng)一化運算單元保證在性能上的提升。

整體來看，本文所提基于PtNTT算法可重構(gòu)多項式乘法架構(gòu)，支持4種格基后量子公鑰密碼，為未來針對可重構(gòu)目標(biāo)的多項式乘法提供架構(gòu)設(shè)計建議。

6 結(jié)束語

本文通過論述針對多項式重構(gòu)參數(shù)的分析，為后續(xù)可重構(gòu)網(wǎng)絡(luò)的建立提供理論基礎(chǔ)。具體來看，通過分析不同參數(shù)多項式乘法的PtNTT實現(xiàn)算法，就其核心操作特征設(shè)計得到一個滿足實現(xiàn)不同基次的4×4串并行可轉(zhuǎn)換運算單元架構(gòu)，并設(shè)計了其內(nèi)部的可重構(gòu)模乘單元。面向不同格基后量子密碼公鑰算法中的多項式乘法進(jìn)行系數(shù)地址的分配需求分析，具體體現(xiàn)在系數(shù)地址生成邏輯、同個RAM中Bank劃分邏輯以及實際地址與虛擬地址對應(yīng)邏輯，基于上述機(jī)制得到一種滿足基k-NTT的多Bank數(shù)據(jù)存儲結(jié)構(gòu)。為可重構(gòu)多項式乘法提供架構(gòu)設(shè)計建議。