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

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

1 引言

量子破譯算法對(duì)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ì)算機(jī)上的質(zhì)因數(shù)分解和離散對(duì)數(shù)的多項(xiàng)式時(shí)間算法》)的論文，認(rèn)為在量子計(jì)算機(jī)上實(shí)現(xiàn)大整數(shù)因式分解僅需多項(xiàng)式時(shí)間，而在經(jīng)典計(jì)算機(jī)上用現(xiàn)今最快的算法需要指數(shù)倍的時(shí)間。在此背景下，后量子公鑰密碼算法設(shè)計(jì)在網(wǎng)絡(luò)信息安全領(lǐng)域已成為新興的研究方向。

美國國家標(biāo)準(zhǔn)技術(shù)研究所(National Institute of Standards and Technology, NIST)從2012年開始啟動(dòng)后量子密碼方向的研究。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)點(diǎn)：可證明安全性、公私鑰尺寸更小、計(jì)算速度更快以及在格理論密碼系統(tǒng)出現(xiàn)之前，沒有合適的問題可以用于構(gòu)造同態(tài)加密系統(tǒng)。綜上所述，格基密碼方案被認(rèn)為是最有前途的用于公鑰加密和數(shù)字簽名的后量子密碼算法。隨著格基后量子公鑰密碼的不斷發(fā)展與研究，國內(nèi)也開始為量子計(jì)算機(jī)對(duì)傳統(tǒng)密碼算法帶來的沖擊做準(zhǔn)備。2018年11月，由歐洲電信標(biāo)準(zhǔn)化協(xié)會(huì)主辦的第六屆量子安全國際會(huì)議在京開幕。中國科學(xué)院信息工程研究所副所長荊繼武在會(huì)上表示，中國或?qū)⒂?022年左右開展后量子密碼算法標(biāo)準(zhǔn)化的工作，于2025年左右實(shí)現(xiàn)商業(yè)化應(yīng)用落地。此表明未來常用格基公鑰密碼多樣，其中參數(shù)結(jié)構(gòu)迥異需要可重構(gòu)架構(gòu)去實(shí)現(xiàn)。因此，設(shè)計(jì)一種可滿足不同算法中的多項(xiàng)式乘法架構(gòu)具有重要意義。

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

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

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

2 多項(xiàng)式乘法運(yùn)算特征分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法1 NTRUhps4096821采用混合基PtNTT的多項(xiàng)式乘法

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

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

算法7 4路PtNTT中的點(diǎn)乘算法

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

3 可重構(gòu)多項(xiàng)式乘法運(yùn)算架構(gòu)設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1) Kyber與Saber算法

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

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

圖5 Kyber算法中多項(xiàng)式乘法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項(xiàng)數(shù)據(jù)在基數(shù)據(jù)基礎(chǔ)上，將其中00替換為01, 10和11。所以最終地址在Cnt0和Cnt1的控制下進(jìn)行轉(zhuǎn)換。

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

(2) Dilithium算法

與Kyber相似，Dilithium算法內(nèi)多項(xiàng)式乘法項(xiàng)數(shù)同為256，但其模數(shù)以及適應(yīng)NTT形式不同。此算法可完全按照傳統(tǒng)NTT算法來實(shí)現(xiàn)，本文為減少控制結(jié)構(gòu)的復(fù)雜性，故同樣采用基4-2PtNTT算法來實(shí)現(xiàn)，由于模數(shù)長度為Kyber算法的兩倍，需要4×4個(gè)運(yùn)算單元，每1×4個(gè)運(yùn)算單元實(shí)現(xiàn)基4中1個(gè)階段的32 bit模乘運(yùn)算，最終共同實(shí)現(xiàn)1次32 bit基4操作。一個(gè)裝載64個(gè)多項(xiàng)式系數(shù)的RAM單元，也需要同時(shí)讀寫4個(gè)數(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é)針對(duì)NTRU算法進(jìn)行NTT友好型參數(shù)轉(zhuǎn)換后，其項(xiàng)數(shù)為1 024，整體采用基4-2Pt-NTT方法。以裝載256個(gè)多項(xiàng)式系數(shù)的空間為一個(gè)RAM單元，需要同時(shí)讀寫4個(gè)數(shù)據(jù)。與前兩種分配方式相比，每個(gè)Bank內(nèi)的存儲(chǔ)量增加，不同類算法可重構(gòu)實(shí)現(xiàn)表明可共用存儲(chǔ)面積。且為了控制結(jié)構(gòu)復(fù)雜度降低，分配方式需要同時(shí)滿足兩者的要求。所以前文所滿足的多種分配方式既需要滿足此算法的要求，也需要降低控制結(jié)構(gòu)復(fù)雜度。

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

地址生成規(guī)律實(shí)質(zhì)上也與第(1)節(jié)陳述類似，本質(zhì)在于項(xiàng)數(shù)不同帶來的計(jì)數(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項(xiàng)數(shù)據(jù)在基數(shù)據(jù)基礎(chǔ)上，將其中00替換為01, 10和11。

(4) NTRUhps2048677與NTRUhrss701算法

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

(5) NTRUhps4096821算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)果與比較

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

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

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

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

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

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

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

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

6 結(jié)束語

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