格密碼關(guān)鍵運(yùn)算模塊的硬件實(shí)現(xiàn)優(yōu)化與評估

陳朝暉 馬原 荊繼武

1. 中國科學(xué)院大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 北京 100049; 2. 中國科學(xué)院信息工程研究所信息安全國家重點(diǎn)實(shí)驗(yàn)室,北京 100093; 3. 中國科學(xué)院大學(xué)網(wǎng)絡(luò)空間安全學(xué)院, 北京 100049; 4. 北京大學(xué)軟件與微電子學(xué)院, 北京 102600;? 通信作者, E-mail: mayuan@iie.ac.cn

量子計(jì)算技術(shù)給現(xiàn)有 RSA 和橢圓曲線公鑰密碼算法的安全性帶來巨大的挑戰(zhàn)。Shor[1]提出一種可快速破解大整數(shù)分解和離散對數(shù)問題的量子算法, Gidney 等[2]發(fā)現(xiàn)只需要 2000 萬個(gè)量子比特即可在 8 小時(shí)內(nèi)破解的 RSA2048 算法。為征集合適的替代性公鑰密碼算法標(biāo)準(zhǔn), 美國國家標(biāo)準(zhǔn)與技術(shù)研究院(National Institute of Standards and Technology,NIST)自 2016 年起開始征集具有后量子特性的公鑰加密、密鑰交換和數(shù)字簽名方案。其中, 基于格上困難問題的方案具有計(jì)算速度較快[3]、密鑰和密文較小[4]等優(yōu)勢, 受到廣泛關(guān)注, 成為熱門的后量子密碼候選方案[5]。

Lyubashevsky 等[6]提出的環(huán)上錯(cuò)誤學(xué)習(xí)(ring learning with errors, RLWE)問題是許多格密碼算法的理論基礎(chǔ)。RLWE 密碼算法中的關(guān)鍵運(yùn)算是多項(xiàng)式乘法運(yùn)算, 可以采用基于蝶形運(yùn)算的數(shù)論變換(number theoretic transform, NTT)快速實(shí)現(xiàn)[7-8]。NTT要求密碼算法使用特定的模數(shù), 以 NewHope 算法[9]為代表的密鑰交換算法和以 BLISS 算法[10]為代表的數(shù)字簽名算法均選擇適用于 NTT 的參數(shù), 以便提高運(yùn)算速度。NTT 多項(xiàng)式乘法硬件的實(shí)現(xiàn)受到學(xué)術(shù)界的廣泛關(guān)注, 其設(shè)計(jì)難點(diǎn)在于, 一方面 NTT 控制邏輯包含多層循環(huán)嵌套的原位運(yùn)算結(jié)構(gòu), 存儲器中的多項(xiàng)式系數(shù)存取調(diào)度復(fù)雜且?guī)捯筝^高; 另一方面, 蝶形運(yùn)算在 NTT 計(jì)算過程中執(zhí)行次數(shù)多, 例如 512 維多項(xiàng)式每次 NTT 需要執(zhí)行 2304 次蝶形運(yùn)算, 而 1024 維多項(xiàng)式每次 NTT 需要執(zhí)行 5120 次蝶形運(yùn)算, NTT 中循環(huán)調(diào)用的蝶形運(yùn)算模塊包含模約減運(yùn)算, 這是多項(xiàng)式乘法硬件實(shí)現(xiàn)的性能瓶頸, 進(jìn)而影響密碼算法的整體效率和運(yùn)算時(shí)延。

在現(xiàn)有的硬件平臺中, FPGA 具有開發(fā)周期較短且通用性較強(qiáng)的優(yōu)勢。它由諸多可編程的邏輯資源組成, 廣泛地應(yīng)用于密碼算法的優(yōu)化、實(shí)現(xiàn)和評估中[11]。本文提出一種 NTT 多項(xiàng)式乘法優(yōu)化方法和硬件架構(gòu), 并對優(yōu)化的硬件實(shí)現(xiàn)以及現(xiàn)有硬件實(shí)現(xiàn)進(jìn)行評估, 為格密碼硬件設(shè)計(jì)提供參考。

1 相關(guān)工作

P?ppelmann 等[12]在 FPGA 上的 BLISS 數(shù)字簽名實(shí)現(xiàn)達(dá)到比 RSA 簽名和 ECDSA 簽名更大的吞吐量且占用面積更小。Bos 等[4]的研究表明, 使用 Newhope 密鑰交換算法, 通過 TLS 提供 web 頁面, 能夠?qū)崿F(xiàn)比 ECDHE 算法或 NTRU 算法更大的網(wǎng)絡(luò)吞吐量。Newhope 密鑰交換算法和 BLISS 數(shù)字簽名能夠高效實(shí)現(xiàn)的重要原因是均設(shè)定模數(shù)為 12289, 該模數(shù)支持基于 NTT 的多項(xiàng)式乘法, 可將多項(xiàng)式乘法的時(shí)間復(fù)雜度從O(n2)降低到O(nlogn)。

盡管 NTT 大幅減少了多項(xiàng)式乘法的復(fù)雜度, 但NTT 多項(xiàng)式乘法需要預(yù)縮放和后縮放等運(yùn)算步驟,造成一定的運(yùn)算時(shí)延。此外, NTT 的原位運(yùn)算實(shí)現(xiàn)需要較大的數(shù)據(jù)存取帶寬, 一般的雙端口 RAM 不能直接滿足其數(shù)據(jù)存取需求。學(xué)者們提出針對多項(xiàng)式乘法中預(yù)縮放運(yùn)算和數(shù)據(jù)存取的優(yōu)化技術(shù)。Roy等[13]通過整合 NTT 正變換和預(yù)縮放運(yùn)算來減少模乘運(yùn)算次數(shù), 還提出一種高位寬的數(shù)據(jù)存儲結(jié)構(gòu),該方案雖然提高了存儲器的吞吐量, 但需要消耗額外的時(shí)鐘周期進(jìn)行數(shù)據(jù)重排。Oder 等[14]首次在FPGA 上完整地實(shí)現(xiàn) NewHope 密鑰交換算法, 但其模約減模塊中包含延時(shí)較大的關(guān)鍵路徑, 并且數(shù)據(jù)存取帶寬不足, 需占用額外的時(shí)鐘周期等待數(shù)據(jù)流。然而, 等待期間運(yùn)算單元處于空閑狀態(tài), 因此電路效率并不高。

由于多項(xiàng)式系數(shù)在商環(huán)中運(yùn)算, NTT 中蝶形運(yùn)算采用的模約減算法是多項(xiàng)式乘法優(yōu)化的一個(gè)重點(diǎn)。模約減算法與除法運(yùn)算密切相關(guān)。Poppelmann[15]提出一種基于長除法的基本模約減(Generic)算法, 并采用高層次綜合的方法, 在 FPGA 上實(shí)現(xiàn)該算法的流水線模塊?；灸＜s減算法采用“比較器-減法器”邏輯鏈的結(jié)構(gòu), 且邏輯鏈的長度與模數(shù)正相關(guān), 因此基本模約減算法往往需要較長的邏輯鏈。由于 Poppelmann[15]提出的電路面積消耗較大,且該電路的性能優(yōu)化過程中需要插入的流水線級數(shù)較多, 因此整個(gè)硬件模塊效率不高。Barrett 約減[16]是一種基于商估計(jì)的算法, 在蝶形運(yùn)算中有較多的應(yīng)用實(shí)例。2015 年, Liu 等[17]提出 SAMS2 模約減,該方法是一種以移位、加法、乘法和兩次減法組成的模約減算法優(yōu)化實(shí)現(xiàn), 適合在資源受限的微控制器上實(shí)現(xiàn)。Poppelmann[15]實(shí)現(xiàn)了完全采用移位和加減法代替乘法的 FPGA 硬件實(shí)現(xiàn), 該實(shí)現(xiàn)的電路面積比基本模約減算法顯著減小, 但電路最大工作頻率相對較低。Xing 等[18]在 FPGA 上實(shí)現(xiàn)一種對加法樹器優(yōu)化的 Barrett 約減方案, 能夠同時(shí)輸出商和剩余, 但由于乘數(shù)的漢明重量較大, 需構(gòu)建較復(fù)雜的加法器樹。Banerjee 等[19]提出一種模數(shù)可控制的模算術(shù)電路, 并給出其 ASIC 實(shí)現(xiàn)。由于 Barrett 約減原理的限制, 其硬件實(shí)現(xiàn)需要比較器-減法器電路, 用以解決商估計(jì)值存在的誤差。Montgomery約減、模乘和模冪算法[20]一直廣泛應(yīng)用于密碼優(yōu)化實(shí)現(xiàn)和實(shí)現(xiàn)領(lǐng)域, 但經(jīng)典的 Montgomery 約減實(shí)現(xiàn)中也需要比較器-減法器電路, 以便得到最終結(jié)果。Alkim 等[9]提出一種適用于蝶形運(yùn)算的不完全模約減(incomplete reduction)算法(ADPS 算法)。不完全模約減是將輸入約減到某個(gè)寬松的數(shù)值范圍,而不要求約減結(jié)果為非負(fù)最小剩余。ADPS 算法對加法結(jié)果采用不完全 Barrett 約減, 對乘法結(jié)果采用不完全 Montgomery 約減。當(dāng)模數(shù)取 12289 時(shí), ADPS算法通過選取合適的寄存器寬度和運(yùn)算參數(shù), 可恰好使乘法結(jié)果約減到 14 比特以內(nèi)的無符號整數(shù), 免去 Barrett 約減和 Montgomery 約減的判斷及減法操作。與傳統(tǒng) Barrett 或 Montgomery 相比, 不完全約減能夠節(jié)省比較器和減法器資源, 因此非常適合軟、硬件實(shí)現(xiàn)。Jati 等[21]在 FPGA 平臺上實(shí)現(xiàn) ADPS算法, 由于純組合電路的實(shí)現(xiàn)路徑延時(shí)較大, 該實(shí)現(xiàn)通過插入 3 級流水線來提高電路的最大工作頻率。

Longa 等[22]提出一種適用于模數(shù)q=k·2p+1 的模約減算法(LN 模約減), 并應(yīng)用于 NTT 多項(xiàng)式乘法中。LN 模約減也是一種不完全約減算法, 包括用于加法結(jié)果約減的 K-RED 算法以及用于乘法結(jié)果約減的 K-RED2x 算法, 且運(yùn)算過程中采用有符號整數(shù)表示參數(shù), 實(shí)驗(yàn)結(jié)果表明基于 LN 模約減的NTT 比基于 ADPS 算法的 NTT 軟件實(shí)現(xiàn)速度提高86%以上。Kuo 等[23]提出的 LN 模約減算法同樣適用于硬件實(shí)現(xiàn), 為適配 FPGA 片上的數(shù)字信號處理器單元(DSP)并避免寄存器中數(shù)值溢出, 他們將原方案中參數(shù)的有符號數(shù)表示調(diào)整為無符號數(shù)表, 由此實(shí)現(xiàn)一種適用于 FPGA 的流水線電路結(jié)構(gòu), 并達(dá)到較高的電路性能。但是, 該實(shí)現(xiàn)中使用的加法器數(shù)量較多。

綜上所述, 設(shè)計(jì) NTT 中高帶寬的多項(xiàng)式系數(shù)存取方案以及蝶形運(yùn)算中模約減的高效實(shí)現(xiàn)方法, 仍是多項(xiàng)式乘法硬件實(shí)現(xiàn)中困難的問題。本文提出一種基于 LN 模約減的 NTT 多項(xiàng)式乘法硬件實(shí)現(xiàn)優(yōu)化方法, 并提供不同層級的流水線優(yōu)化實(shí)現(xiàn)。

2 多項(xiàng)式乘法的高效算法

整數(shù)環(huán)用 Z 表示, Zq為模整數(shù)q的商環(huán), R=Z[X]/ (Xn+ 1)是模多項(xiàng)式Xn+1 的整系數(shù)多項(xiàng)式環(huán),其中n為多項(xiàng)式維度即多項(xiàng)式系數(shù)的個(gè)數(shù), Rq=Zq[X]/(Xn+1)表示系數(shù)模q的整系數(shù)多項(xiàng)式環(huán)。對于n維 多項(xiàng)式a= (a0, …,an-1),b= (b0, … ,bn-1)∈Rq,其中a0, …,an-1,b0, …,bn-1∈Zq表示多項(xiàng)式系數(shù), 多項(xiàng)式乘法運(yùn)算ab是一種卷積形式的運(yùn)算, 如果直接計(jì)算, 則 Rq上的多項(xiàng)式乘法需要n2次模乘運(yùn)算[7]。本節(jié)主要介紹整系數(shù)模q運(yùn)算采用的高效模約減算法, 以及采用 NTT 計(jì)算 Rq上的多項(xiàng)式乘法。

2.1 高效模約減算法

LN 模約減適用于形如q=k· 2p+ 1的模數(shù), 其中k為奇數(shù), 且2p＞k。對于a,b∈ Zq, 以求乘積x=a·b對模數(shù)q的模運(yùn)算為例, 其思路是利用k· 2p≡-1 modq的特性, 把xmodq的計(jì)算轉(zhuǎn)化為x· kmodq,再消去乘k的影響。特別地,q取 12289 時(shí),k取 3,p取 12。LN 模約減包含 K-RED 和 K-RED2x 兩種算法形式, K-RED 算法將x表示為x=x0+ 2px1, 從而得到算法 1。

算法 1 和算法 2 的輸出r均為有符號數(shù), Kuo 等[23]采用 LN 模約減, 并對r加一個(gè)模數(shù)q的整數(shù)倍, 確保約減最終結(jié)果非負(fù)。其加法結(jié)果的約減采用KRED 算法, 乘法結(jié)果的約減采用 K-RED-2x 算法,約減過程引入的k和k2均可以通過預(yù)計(jì)算等方式消除。

2.2 NTT 多項(xiàng)式乘法

NTT 的原理是將標(biāo)準(zhǔn)域的多項(xiàng)式乘法運(yùn)算轉(zhuǎn)換為 NTT 域上多項(xiàng)式系數(shù)對位點(diǎn)乘運(yùn)算。對于一個(gè)滿足維度n為 2 的正整數(shù)次冪且模數(shù)q≡ 1mod2n的多項(xiàng)式a, NTT 正變換如算法 3 所示, 其中ωn是Zq中的本原n階單位根,φ是ωn模q的平方根。

由于多項(xiàng)式a的系數(shù)均由隨機(jī)采樣獲得, 可認(rèn)為采樣結(jié)果是倒位序的, 從而將算法 3 的第 1 行省去[23]。算法 3 的第 10～14 行即蝶形運(yùn)算, 處于 NTT變換的最內(nèi)層循環(huán), 在串行實(shí)現(xiàn)的 NTT 變換中, 蝶形運(yùn)算作為一個(gè)算術(shù)邏輯單元被循環(huán)調(diào)用。由于每次 K-RED 算法將結(jié)果縮放k倍, K-RED2x 算法將結(jié)果縮放k2倍, 若將算法 3 中每個(gè)ωn在預(yù)計(jì)算時(shí)均乘以k-1, 則最終得到的～a相當(dāng)于每個(gè)多項(xiàng)式系數(shù)都乘以縮放系數(shù)klogn。NTT 逆變換與算法 3 類似, 區(qū)別在于其中預(yù)計(jì)算的φ冪替換為φ-1冪, 且最后需要給各系數(shù)乘以縮放因子n-1。

在采用 NTT 計(jì)算多項(xiàng)式乘法時(shí), 首先采用基于蝶形運(yùn)算的 NTT 正變換, 將標(biāo)準(zhǔn)域下的多項(xiàng)式轉(zhuǎn)化為 NTT 域下的多項(xiàng)式, 兩個(gè) NTT 域多項(xiàng)式將系數(shù)對位點(diǎn)乘, 點(diǎn)乘結(jié)果再通過 NTT 逆變換轉(zhuǎn)換到標(biāo)準(zhǔn)域, 如算法 4 所示。

算法 4 中, 除正反 NTT 變換和系數(shù)對位點(diǎn)乘運(yùn)算外, 還包括正 NTT 變換前乘φi的預(yù)縮放(第 2～3行)和逆 NTT 變換后乘φ-i的后縮放(第 12 行), 其中算法 4 的后縮放已經(jīng)與乘n-1運(yùn)算合并。此外, 為消除 LN 模約減引入的系數(shù)k冪, 需要在運(yùn)算中引入相應(yīng)的逆系數(shù)。

3 面向硬件實(shí)現(xiàn)的優(yōu)化

盡管現(xiàn)有模約減和多項(xiàng)式乘法已有較高效的算法, 但其硬件實(shí)現(xiàn)技術(shù)還不成熟。本節(jié)以 NewHope密鑰交換算法和 BLISS 數(shù)字簽名算法中通用的 Rq(q=12289) 為例, 介紹多項(xiàng)式乘法算法的硬件優(yōu)化方法。

3.1 基于LN 模約減的蝶形運(yùn)算硬件優(yōu)化

LN 模約減包含由層級的加法器級聯(lián)形成的加法樹結(jié)構(gòu), Kuo 等[23]的硬件實(shí)現(xiàn)廣泛采用二輸入加法器構(gòu)建加法樹結(jié)構(gòu)。在主流 FPGA 架構(gòu)中, 六輸入查找表(LUT)結(jié)構(gòu)可以高效地例化為三輸入加法器, 其占用的邏輯資源量與二輸入加法器相同[24],因此三輸入加法器的路徑延時(shí)與普通加法器的差異很小而集約程度更高。

基于優(yōu)化 LN 模約減的蝶形運(yùn)算結(jié)構(gòu)如圖 1 所示。優(yōu)化的思路是盡可能采用三輸入加法器構(gòu)建硬件模塊, 有助于節(jié)省 LUT 邏輯資源。圖 1 中的 KRED 算法使用一個(gè)三輸入加法器, K-RED2x 算法模塊使用兩個(gè)三輸入加法器, 整個(gè)蝶形運(yùn)算模塊共使用 5 個(gè)三輸入加法器。Kuo 等[23]中提出的硬件結(jié)構(gòu)使用 10 個(gè)加法器, 而本文采用三輸入加法器合并加減法邏輯, 可節(jié)省 50%的加法器數(shù)量。

圖1 基于優(yōu)化LN 模約減的蝶形運(yùn)算結(jié)構(gòu)Fig. 1 Butterfly operation structure based on optimized LN modular reduction

3.2 多項(xiàng)式乘法的硬件優(yōu)化

根據(jù) Poppelmann[15]提出的方法, 算法 4 中第2～3 行的預(yù)縮放運(yùn)算可以整合在正 NTT 變換中。該優(yōu)化只需要調(diào)整每次蝶形運(yùn)算中ω的取值, 即將NTT 算法 3 中第 8 行改為ω= ROM[m+i]。采用該優(yōu)化得到的 NTT 正變換結(jié)果與帶有預(yù)縮放的普通NTT 運(yùn)算結(jié)果一致, 可減少算法 4 中 10.5%的模乘運(yùn)算, 得到算法 5。

與算法 4 相比, 算法 5 的另一個(gè)優(yōu)勢是節(jié)省預(yù)計(jì)算參數(shù)對存儲的占用, 算法 4 需要 3n個(gè)預(yù)計(jì)算參數(shù), 而算法 5 需要 2.5n個(gè)預(yù)計(jì)算參數(shù), 可以減少16.7%的只讀存儲器空間占用。算法 5 將 LN 模約減引入的系數(shù)k冪在后縮放階段(第 8 行)消除。

算法 3 中, 由于每次蝶形運(yùn)算需要獲取兩個(gè)多項(xiàng)式系數(shù)并寫入兩個(gè)多項(xiàng)式系數(shù), 但每個(gè)雙端口存儲器每個(gè)時(shí)鐘周期僅能讀或?qū)憙蓚€(gè)地址的數(shù)據(jù), 因此蝶形運(yùn)算的直接原位運(yùn)算實(shí)現(xiàn)需要額外的時(shí)鐘周期執(zhí)行數(shù)據(jù)讀寫, 造成數(shù)據(jù)駐留[14]。為提高存儲器的吞吐, 本文采用乒乓結(jié)構(gòu)的存儲器存取方式, 即例化兩個(gè)相同大小的存儲器 RAM0 和 RAM1, 多項(xiàng)式系數(shù)的初始值存儲在 RAM0 中, 當(dāng)算法 3 中 logt為奇數(shù)時(shí), 蝶形運(yùn)算模塊從 RAM0 讀取多項(xiàng)式系數(shù),RAM1 寫入蝶形運(yùn)算得到的新系數(shù)結(jié)果; 當(dāng) logt為偶數(shù)時(shí), 蝶形運(yùn)算模塊從 RAM1 讀取多項(xiàng)式系數(shù),RAM0 寫入蝶形運(yùn)算得到的新系數(shù)結(jié)果。對于 logn為偶數(shù)的情況, NTT 的最終結(jié)果將存儲在 RAM0 中。

4 基于 FPGA 的多項(xiàng)式乘法運(yùn)算實(shí)現(xiàn)

4.1 基于 LN 模約減的蝶形運(yùn)流水線設(shè)計(jì)

在 FPGA 平臺上, 由于多項(xiàng)式數(shù)據(jù)量較大, 其系數(shù)存儲一般采用塊 RAM (block RAM, BRAM)實(shí)現(xiàn), 而較高位寬的乘法運(yùn)算一般采用 DSP 實(shí)現(xiàn)。BRAM 和 DSP 都有豐富的邏輯資源, 可采用流水線技術(shù)達(dá)到高工作頻率。

基于優(yōu)化 LN 模約減的蝶形運(yùn)算流水線實(shí)現(xiàn)如圖 2 所示。灰色的流水線層級作為基本流水線, 能確保一般時(shí)鐘頻率要求, 白色的流水線層級間僅有一層算術(shù)邏輯, 可供更高性能要求的實(shí)現(xiàn)選擇插入。硬件實(shí)現(xiàn)方面采用以下 3 個(gè)方面的設(shè)計(jì)優(yōu)化。

圖2 基于優(yōu)化LN 模約減的蝶形運(yùn)算流水線實(shí)現(xiàn)Fig. 2 Pipeline implementation of butterfly operation based on optimized LN modular reduction

1) 可選的流水線層級。由于圖 1 所示的組合邏輯層級較多, 其組合邏輯產(chǎn)生的路徑延時(shí)較大。為改善路徑延時(shí), 我們在 u_o 和 v_o 對應(yīng)的路徑插入相同級數(shù)的流水線, 確保結(jié)果在同一時(shí)鐘周期輸出。流水線層級可通過條件編譯選擇, 從而調(diào)整電路所需的面積和最大工作頻率。

2) 充分利用移位寄存器資源。在 FPGA 中, 部分 LUT 資源可以作為移位寄存器使用, 從而節(jié)省FPGA 的觸發(fā)器(FF)資源。調(diào)用移位寄存器時(shí), 要求流水線層級間不存在組合邏輯, 例如圖 2 中減法器輸出至 u_o 路徑不是關(guān)鍵路徑, 其作為時(shí)延插入的流水線結(jié)構(gòu)可采用移位寄存器實(shí)現(xiàn)。

3) 充分利用 DSP 單元資源。蝶形運(yùn)算中的乘法運(yùn)算需要占用一個(gè) DSP 單元, 除乘法器資源外,我們的流水線實(shí)現(xiàn)還使用 DSP 單元的 3 層流水線寄存器資源, 有利于減少 DSP 外部 FF 的占用。

4.2 系統(tǒng)總體結(jié)構(gòu)設(shè)計(jì)

如圖 3 所示, 多項(xiàng)式乘法處理器的硬件結(jié)構(gòu)主要包含控制模塊、蝶形運(yùn)算模塊和存儲模塊?？刂颇K負(fù)責(zé)控制蝶形運(yùn)算模塊的運(yùn)算邏輯以及存儲模塊的讀寫地址、寫使能以及乒乓轉(zhuǎn)換; 蝶形運(yùn)算模塊可以實(shí)現(xiàn)蝶形運(yùn)算以及模乘運(yùn)算; 存儲模塊包括RAM 和 ROM, RAM 存儲多項(xiàng)式系數(shù)及其運(yùn)算中間值, ROM 存儲多項(xiàng)式乘法運(yùn)算過程中的預(yù)計(jì)算參數(shù), 執(zhí)行正 NTT 變換時(shí), 從 ROM 讀取k-1φ i區(qū)域?qū)?yīng)參數(shù), 執(zhí)行逆 NTT 變換時(shí), 從 ROM 讀取區(qū)域?qū)?yīng)參數(shù), 執(zhí)行后縮放運(yùn)算時(shí), 從 ROM 讀取φ-ik-(4+2logn)n-1區(qū)域?qū)?yīng)參數(shù)。

圖3 多項(xiàng)式乘法處理器總體架構(gòu)Fig. 3 Overall architecture of polynomial multiplication processor

對于流水線層級為ε的蝶形運(yùn)算模塊, 數(shù)據(jù)輸出和讀入之間有ε個(gè)時(shí)鐘周期的延時(shí)。因此, 當(dāng)一個(gè)存儲器由讀向?qū)懛较蚋淖儠r(shí), 另一個(gè)存儲器還未完成寫操作, 即在讀寫方向改變時(shí)會造成ε個(gè)時(shí)鐘周期的流水線數(shù)據(jù)駐留。本文采用備份 RAM 作為緩沖區(qū), 確保數(shù)據(jù)存取時(shí)數(shù)據(jù)通路始終保持全流水。備份 RAM 的原理是, 當(dāng)原 RAM 寫入沒有完成時(shí), 控制模塊選通備份 RAM 讀出多項(xiàng)式系數(shù), 確保這部分?jǐn)?shù)據(jù)與原 RAM 對應(yīng)地址的數(shù)據(jù)相同。例如, 起始時(shí) ROM0 為讀出方向, ROM1 和 RAM1備份同時(shí)寫入; ROM0 讀出完成時(shí), 控制模塊選通RAM1備份讀出多項(xiàng)式系數(shù), RAM1 繼續(xù)完成ε個(gè)時(shí)鐘周期的寫入操作; RAM1 寫入完成后, 控制模塊選通 RAM1 讀出多項(xiàng)式系數(shù), ROM0 和 RAM0備份同時(shí)寫入。由于ε數(shù)值較小, 當(dāng)兵乓方向轉(zhuǎn)換時(shí), 從RAM0備份讀出的數(shù)據(jù)與 ROM0 相同, 且整個(gè)運(yùn)算過程不會產(chǎn)生讀寫地址沖突, 可以確保運(yùn)算結(jié)果的正確性。

5 實(shí)驗(yàn)結(jié)果與評估

為比較采用不同模約減算法的蝶形運(yùn)算模塊的面積和性能, 我們將本文提出的硬件實(shí)現(xiàn)優(yōu)化方法與現(xiàn)有實(shí)現(xiàn)方法進(jìn)行對比評估。實(shí)驗(yàn)參數(shù)采用通用的模數(shù)q=12289, 多項(xiàng)式維度n=1024。測試平臺采用 Xilinx 公司的 XC7A200T 型號 FPGA。

5.1 蝶形運(yùn)算硬件評估

分別給出基于優(yōu)化 LN 模約減的蝶形運(yùn)算模塊及其他現(xiàn)有蝶形運(yùn)算模塊在低面積、均衡型以及高速率 3 種頻率設(shè)計(jì)要求下的實(shí)現(xiàn)數(shù)據(jù), 以便充分地比較各方案在不同時(shí)序要求下的性能。低面積表示占用邏輯資源較少, 以 3 級流水線實(shí)現(xiàn); 均衡型表示兼顧資源占用量與運(yùn)算速度, 以 5 級流水線實(shí)現(xiàn);高速率表示工作頻率高, 以 8 級以上流水線實(shí)現(xiàn)。評估結(jié)果如表 1 所示, Montgomery, Barrett 和 Generic算法所在的行表示該硬件實(shí)現(xiàn)的蝶形運(yùn)算模塊中采用對應(yīng)的模約減算法。FPGA 中的資源類型較多,本文只列舉占用基本邏輯資源(Slice)及其中 LUT 和FF 資源的數(shù)量。表中所有硬件實(shí)現(xiàn)均占用 1 個(gè) DSP單元。

Kuo 等[23]僅提供一種流水線設(shè)計(jì), 我們將基于優(yōu)化LN 模約減的均衡型實(shí)現(xiàn)與他們的方案進(jìn)行對比。結(jié)果表明, 由于三輸入加法器的引入, 本文的優(yōu)化共減少 12.7%的 Slice, 并減少 32.2%的 LUT 資源占用。

基于優(yōu)化 LN 模約減的低面積實(shí)現(xiàn)需要的硬件資源最少, 與基于優(yōu)化 LN 模約減的均衡型實(shí)現(xiàn)相比, 進(jìn)一步節(jié)省 27.1%?；趦?yōu)化 LN 模約減的高性能實(shí)現(xiàn)能達(dá)到最高的工作頻率, 且比基于 ADPS 模約減的高性能實(shí)現(xiàn)節(jié)省 21.3%的硬件資源。

在完全約減的實(shí)現(xiàn)方案中, 基于 Montgomery算法的蝶形運(yùn)算模塊資源占用較少, 且工作效率較高, 也能夠滿足 250 MHz 以上的工作頻率要求, 與Barrett 算法和 Generic 算法相比, 優(yōu)勢較為明顯。Poppelmann 等[15]給出的基于高層次綜合的實(shí)現(xiàn)方法雖然能夠?qū)崿F(xiàn)相對較高的工作頻率, 但占用的邏輯資源較多。相較而言, 基于不完全約減的蝶形運(yùn)算實(shí)現(xiàn)在面積和性能上均優(yōu)于完全約減的蝶形運(yùn)算, 基于優(yōu)化 LN 模約減的蝶形運(yùn)算實(shí)現(xiàn)綜合效果最優(yōu)。

5.2 多項(xiàng)式乘法運(yùn)算硬件評估

采用表 1 中基于優(yōu)化 LN 模約減的蝶形運(yùn)算模塊高性能實(shí)現(xiàn)完成算法 5 的硬件實(shí)現(xiàn), 共占用151 個(gè) Slice。本文多項(xiàng)式乘法硬件實(shí)現(xiàn)與現(xiàn)有硬件實(shí)現(xiàn)的比較結(jié)果如表 2 所示, 其中 AT 積(area time product)表示電路面積與運(yùn)算時(shí)延的乘積, AT 積越小表示電路效率越高。為便于比較, 表 2 中所有硬件實(shí)現(xiàn)的 AT 積均做歸一化處理。

表1 蝶形運(yùn)算硬件實(shí)現(xiàn)評估Table 1 Evaluation of butterfly operations on hardware

可以看出, 相比其他多項(xiàng)式乘法硬件實(shí)現(xiàn), 本文硬件實(shí)現(xiàn)的工作頻率最高, 可達(dá) 300 MHz 以上,主要得益于合理的流水線設(shè)計(jì)。多項(xiàng)式乘法模塊的硬件實(shí)現(xiàn)要根據(jù)設(shè)計(jì)的目標(biāo)工作頻率確定蝶形運(yùn)算模塊的流水線級數(shù)。對于工作頻率要求較低的硬件實(shí)現(xiàn), 蝶形運(yùn)算模塊的模約減運(yùn)算一般為關(guān)鍵路徑,可選擇適當(dāng)?shù)牧魉€級數(shù), 達(dá)到目標(biāo)工作頻率; 對于工作頻率要求較高的硬件實(shí)現(xiàn), 蝶形運(yùn)算可以采用流水線技術(shù)進(jìn)一步優(yōu)化, 但 NTT 控制邏輯的循環(huán)嵌套會產(chǎn)生較復(fù)雜的選通電路, 且其插入流水線的成本很高, 因此控制邏輯更容易成為關(guān)鍵路徑。

本文硬件實(shí)現(xiàn)的電路面積同樣具有優(yōu)勢, 其特點(diǎn)是具有均衡的 LUT 和 FF 數(shù)量, 并且充分利用DSP 和 BRAM 中的邏輯資源, 因此即使插入更多級數(shù)的流水線, 電路面積并沒有大幅增加。Xing等[23]、Kuo 等[18]和 Neng 等[25]通過例化 2～4 個(gè)并行的蝶形運(yùn)算模塊, 實(shí)現(xiàn)更低的運(yùn)算時(shí)延, 相應(yīng)的代價(jià)是電路面積明顯大于本文硬件實(shí)現(xiàn)。Kuo 等[23]采用了基于 LN 模約減的蝶形運(yùn)算, 且 4 個(gè)并行的蝶形運(yùn)算模塊有效地提高了運(yùn)算速度, 但該實(shí)現(xiàn)沒有消除預(yù)縮放運(yùn)算, 也需要更多 BRAM 存儲預(yù)計(jì)算的參數(shù)值, 且工作頻率不高, 因此各硬件資源的效率不高。Xing 等[18]提出的 4 路蝶形運(yùn)算模塊并行實(shí)現(xiàn)的運(yùn)算時(shí)延最小, 且該硬件實(shí)現(xiàn)不占用 BRAM, 但其蝶形運(yùn)算模塊采用優(yōu)化的 Barrett 約減導(dǎo)致整體工作頻率不高, 且該硬件實(shí)現(xiàn)同樣未消除預(yù)縮放運(yùn)算, 因此 LUT, FF 與 DSP 的效率均明顯低于本文的硬件實(shí)現(xiàn)。文獻(xiàn)[25]中 FF 的效率更高, 但考慮到現(xiàn)有 FPGA 器件每個(gè) Slice 結(jié)構(gòu)中 FF 與 LUT 的數(shù)量比值一般為 2, 而文獻(xiàn)[25]中 LUT 和 FF 的利用很不均衡, 最終 Slice 的占用會受數(shù)量較多的 LUT 影響, 因此其基本邏輯資源的 AT 積約為本文硬件實(shí)現(xiàn)的1.3 倍, DSP 和BRAM 的 AT 積效率與本文硬件實(shí)現(xiàn)接近。Oder 等[14]實(shí)現(xiàn)了較少的邏輯資源占用, 但其單次多項(xiàng)式系數(shù)讀取和模約減運(yùn)算均需要大于 1 個(gè)時(shí)鐘周期, 造成流水線數(shù)據(jù)駐留, 因此其各類硬件資源的效率不高。文獻(xiàn)[21]的多項(xiàng)式乘法運(yùn)算采用Alkim 等[9]的模約減方法, 比本文硬件實(shí)現(xiàn)效率較低。表 2 中 Fritzmann 等[26]的時(shí)延未計(jì)入系數(shù)對位乘法步驟, 其工作頻率按照等同于本文硬件實(shí)現(xiàn)的工作頻率計(jì)算, 該硬件實(shí)現(xiàn)可作為 RISC-V 處理器的密碼協(xié)處理器, 盡管比軟件實(shí)現(xiàn)具有更高的性能,但需要額外的軟硬件通信開銷, 因此與純硬件實(shí)現(xiàn)相比, 在效率上不占優(yōu)勢。

表2 多項(xiàng)式乘法運(yùn)算硬件實(shí)現(xiàn)評估Table 2 Evaluation of polynomial multiplication module on hardware

總體而言, 本文提出的多項(xiàng)式乘法硬件實(shí)現(xiàn)技術(shù)至少能夠提高 22.3%的工作頻率, 并提高 FPGA邏輯資源 22.8%的效率。根據(jù) Xing 等[18]的實(shí)現(xiàn)結(jié)果, 在免去順序倒置操作的情況下, 多項(xiàng)式乘法運(yùn)算約占 NewHope 算法全部密碼運(yùn)算時(shí)延的 80%, 本研究對多項(xiàng)式乘法運(yùn)算的頻率提升大約能夠減少New-Hope 算法 15%的密碼運(yùn)算時(shí)延。

6 總結(jié)

本文提出一種格密碼中多項(xiàng)式乘法的硬件實(shí)現(xiàn)優(yōu)化方法, 能夠使用更小的電路面積實(shí)現(xiàn)更高的工作頻率, 對基于格的后量子密碼實(shí)現(xiàn)具有一定的參考價(jià)值。本文給出的蝶形運(yùn)算模塊流水線實(shí)現(xiàn)能夠滿足不同的時(shí)序要求, 包括低面積、均衡型和高性能實(shí)現(xiàn)。其中, 低面積實(shí)現(xiàn)可以達(dá)到 150 MHz 以上的頻率要求, 且占用電路資源少; 均衡型實(shí)現(xiàn)提供較好的性能與電路面積權(quán)衡, 能夠滿足 250 MHz 以上的中高頻率要求; 高性能實(shí)現(xiàn)能夠提供 350 MHz 以上的高頻率要求。實(shí)驗(yàn)結(jié)果表明, 與現(xiàn)有的硬件實(shí)現(xiàn)方法相比, 多項(xiàng)式乘法硬件優(yōu)化技術(shù)能夠得到 22.8%的效率提升。