韓煉冰，房利國，王 松，劉鴻博，楊敏旭

（中國電子科技集團(tuán)公司第三十研究所，四川 成都 610041）

0 引言

隨著量子計(jì)算技術(shù)的發(fā)展，量子計(jì)算機(jī)將能在人們可以接受的時(shí)間內(nèi)破解許多目前計(jì)算機(jī)無法破解的密碼，其中就包括目前大部分公鑰密碼系統(tǒng)所依賴的大整數(shù)質(zhì)數(shù)拆分問題和離散對數(shù)問題這兩大數(shù)學(xué)難題。

為應(yīng)對量子計(jì)算機(jī)為傳統(tǒng)密碼系統(tǒng)帶來的挑戰(zhàn)，后量子密碼[1]已成為國內(nèi)外眾多學(xué)者的重點(diǎn)研究對象。2016年，美國國家標(biāo)準(zhǔn)與技術(shù)研究院（Nation Institute of Standards and Technology，NIST）開始了一項(xiàng)針對抗量子密碼系統(tǒng)的征集計(jì)劃，旨在尋找、設(shè)計(jì)、開發(fā)和標(biāo)準(zhǔn)化抗量子密碼系統(tǒng)，以便于在未來取代現(xiàn)有的密碼系統(tǒng)標(biāo)準(zhǔn)。經(jīng)過3輪的征集提交和篩選，2022年7月NIST發(fā)布了首批入圍標(biāo)準(zhǔn)的4個(gè)抗量子算法：Crystals-kyber、CRYSTALSDILITHIUM、FALCON和SPHINCS+。這4個(gè)算法中有3個(gè)基于格的數(shù)學(xué)難題，另一個(gè)使用了散列函數(shù)。由此可見，基于格的密碼方案是抗量子計(jì)算密碼學(xué)中的研究熱點(diǎn)?；诟竦拿艽a算法中的運(yùn)算大多為線性運(yùn)算，因此較其他密碼系統(tǒng)，基于格的密碼系統(tǒng)具有計(jì)算速度快[2]、密鑰和密文較小等優(yōu)勢[3]。本文對格密碼中的關(guān)鍵模塊——多項(xiàng)式乘法進(jìn)行研究，給出了一種多項(xiàng)式乘法的運(yùn)算方法和硬件實(shí)現(xiàn)架構(gòu)，并在現(xiàn)場可編程門陣列（Field Program Gate Array，F(xiàn)PGA）中進(jìn)行了實(shí)現(xiàn)和評估，為格密碼硬件實(shí)現(xiàn)提供參考。

1 相關(guān)數(shù)學(xué)基礎(chǔ)

1.1 格密碼數(shù)學(xué)基礎(chǔ)

線性獨(dú)立空間上有集合v1,v2,…,vn∈Rn，格就是這些向量的線性組合，這一過程的表達(dá)式為：

式中：系數(shù)a均在整數(shù)域Z中。任意一組可以生成格的線性無關(guān)向量都稱為格的基，格的維度等于格的基中的向量個(gè)數(shù)。

目前常用的兩個(gè)基于格的困難問題是短整數(shù)問題（Shortest Integer Problem，SIS）和錯(cuò)誤學(xué)習(xí)問題（Learning With Error，LWE），但基于上述兩個(gè)問題的加密方案需要的密鑰量大、效率低、資源消耗高，無法在實(shí)際中運(yùn)用。因此，Lyubashevsky等人[4]在LWE的基礎(chǔ)上提出了環(huán)上錯(cuò)誤學(xué)習(xí)（Ring Learning With Errors，RLWE）問題?；赗LWE的加密方案在性能上有著顯著的優(yōu)勢[5]，這是現(xiàn)在許多格密碼算法的理論基礎(chǔ)。RLWE在環(huán)Zq[x]=f上進(jìn)行操作，其中f是n項(xiàng)的不可約多項(xiàng)式，通常f=xn+1，其中n是2的冪，q為素?cái)?shù)。

1.2 環(huán)多項(xiàng)式乘法

對于RLWE密碼算法，其中最為耗時(shí)的是環(huán)多項(xiàng)式乘法。環(huán)多項(xiàng)式乘法有兩種實(shí)現(xiàn)方式[6-7]，分別為經(jīng)典乘法和快速數(shù)論變換（Number Theoretic Transform，NTT）乘法。

1.2.1 經(jīng)典乘法

經(jīng)典乘法先把多項(xiàng)式a中的每一項(xiàng)與多項(xiàng)式b中的每一項(xiàng)相乘，再把每個(gè)多項(xiàng)式相加得到最終結(jié)果。如果多項(xiàng)式a和b的最高次項(xiàng)都為n-1，那么計(jì)算復(fù)雜度為O(n2)，需要n2個(gè)乘法和(n-1)2個(gè)加減法。

1.2.2 NTT乘法

NTT是基于快速傅里葉變換（Fast Fourier Transform，F(xiàn)FT）實(shí)現(xiàn)的，其將FFT中的旋轉(zhuǎn)因子由復(fù)數(shù)變成了整數(shù)。設(shè)正整數(shù)序列x(n)，其所有元素均小于模數(shù)M，有如下NTT變換[8]：

式（2）為NTT正變換，式（3）為逆NTT變換。其中，a為模M的N階本原單位根，滿足：

amn是a-mn在模M下的逆元，滿足以下性質(zhì)：

NTT運(yùn)算是一個(gè)遞推的過程，圖1給出了N=8點(diǎn)的NTT運(yùn)算結(jié)構(gòu)。如圖1中的橢圓標(biāo)識所示，NTT變換后的結(jié)果順序與原輸入順序呈二進(jìn)制的倒序關(guān)系，因此為避免在計(jì)算完成后進(jìn)行順序變換，通常采用逆序的方式進(jìn)行運(yùn)算，運(yùn)算結(jié)構(gòu)如圖2所示。圖3為一次蝶形運(yùn)算。N通?？梢员硎緸?的冪的形式，N=2L，則N點(diǎn)NTT運(yùn)算需要執(zhí)行次蝶形運(yùn)算，所以8點(diǎn)NTT需要執(zhí)行12次蝶形運(yùn)算。

圖1 8點(diǎn)NTT運(yùn)算結(jié)構(gòu)

圖2 8點(diǎn)NTT逆序運(yùn)算結(jié)構(gòu)

圖3 蝶形運(yùn)算a

2 多項(xiàng)式乘法FPGA實(shí)現(xiàn)

2.1 多項(xiàng)式乘法算法

NTT中的每一次蝶形運(yùn)算都需要做一次乘法和乘法結(jié)果取模運(yùn)算，因此快速完成乘法和取模運(yùn)算是提高NTT運(yùn)算效率的關(guān)鍵。本文采用了Longa等人[9]提出的適用于模數(shù)M=k2p+1的高效取模算法，即LN取模算法，再結(jié)合FPGA內(nèi)部的高效乘法器來實(shí)現(xiàn)NTT快速運(yùn)算。

LN取模算法有K-RED和K-RED2x兩種形式[10]，如算法1和算法2所示。算法1適用于對加法結(jié)果取模，算法2適用于對乘法結(jié)果取模。

NTT變換和逆NTT變換算法如下：

算法3中M為模數(shù)，g為單位根，N為多項(xiàng)式的項(xiàng)數(shù)，如果N不滿足2的整數(shù)次冪需要補(bǔ)0。步驟6-9為一次蝶形運(yùn)算。步驟11正變換查t1，逆變換查t2。

算法4中的步驟7每運(yùn)算一次相當(dāng)于在該項(xiàng)上乘以了k，步驟8每運(yùn)算一次相當(dāng)于在該項(xiàng)上乘以k2，如果對步驟8中每個(gè)gg都乘以k-1，經(jīng)過步驟8運(yùn)算后也相當(dāng)于該項(xiàng)上乘以k。NTT每一項(xiàng)的運(yùn)算次數(shù)為算法4中步驟2總的循環(huán)次數(shù)，即log2N次（N為多項(xiàng)式的項(xiàng)數(shù)）。所以每項(xiàng)都增加了klog2N倍，增加部分可以通過預(yù)計(jì)算的方式消除。

算法5中的步驟1是為了消除NNT運(yùn)算時(shí)每項(xiàng)增加的klog2N倍而做的預(yù)處理。步驟6中的k-(4+log2N)N-1則是為了消除INNT運(yùn)算后擴(kuò)大的klog2N倍，并完成INNT運(yùn)算后的除法運(yùn)算。

2.2 多項(xiàng)式乘法FPGA實(shí)現(xiàn)

多項(xiàng)式乘法的FPGA實(shí)現(xiàn)如圖4所示。

圖4 多項(xiàng)式乘法FPGA實(shí)現(xiàn)

2.2.1 數(shù)據(jù)預(yù)運(yùn)算模塊

數(shù)據(jù)預(yù)運(yùn)算模塊用于對多項(xiàng)式數(shù)據(jù)進(jìn)行預(yù)處理，同時(shí)完成對多項(xiàng)式的倒位序。ROM地址表內(nèi)存放預(yù)計(jì)算好的位序映射表。根據(jù)ROM讀出的地址讀取原始序列，預(yù)運(yùn)算后寫入NTT模塊內(nèi)的存儲器中。

2.2.2 NTT模塊

圖5為NTT模塊的實(shí)現(xiàn)。

圖5 NTT實(shí)現(xiàn)

數(shù)據(jù)RAM1和數(shù)據(jù)RAM2為多項(xiàng)式系數(shù)存儲區(qū)，由于FPGA內(nèi)部實(shí)現(xiàn)的RAM通常只有2路通道，不能滿足蝶形運(yùn)算同時(shí)對RAM的2次讀和寫操作。為了解決這個(gè)問題，本文設(shè)計(jì)了RAM1和RAM2兩個(gè)數(shù)據(jù)存儲區(qū)。當(dāng)RAM1作為數(shù)據(jù)讀取區(qū)時(shí)，蝶形運(yùn)算的結(jié)果寫入RAM2區(qū)，當(dāng)RAM2作為數(shù)據(jù)讀取區(qū)時(shí)，蝶形運(yùn)算的結(jié)果寫入RAM1區(qū)，由內(nèi)部控制模塊乒乓切換兩個(gè)數(shù)據(jù)區(qū)的讀寫模式。

預(yù)計(jì)算查找表用于存放蝶形運(yùn)算所需的預(yù)計(jì)算數(shù)據(jù)，該數(shù)據(jù)可以預(yù)先計(jì)算好后固化在存儲區(qū)內(nèi)部，不占用NTT的計(jì)算時(shí)間。預(yù)計(jì)算的數(shù)據(jù)包括k-1ai，k-1a-i，k-(2+log2N)和k-(4+log2N)N-1。

蝶形運(yùn)算及控制模塊通過狀態(tài)機(jī)控制NTT的3層循環(huán)，以及每次蝶形數(shù)據(jù)和預(yù)計(jì)算數(shù)據(jù)的讀取，調(diào)用K-RED和K-RED2x完成運(yùn)算。因蝶形運(yùn)算下一次的輸入數(shù)據(jù)不會用到上一次的結(jié)果，所以蝶形運(yùn)算可實(shí)現(xiàn)流水操作，從而提升運(yùn)算性能。

2.2.3 乘法模塊

乘法模塊用于完成算法5的步驟4和步驟6。其中乘法模塊1用于完成兩個(gè)多項(xiàng)式轉(zhuǎn)換到NTT域后各項(xiàng)的相乘，并根據(jù)ROM地址表內(nèi)存放的地址讀取多項(xiàng)式的值相乘，將結(jié)果存放在NNT的RAM內(nèi)，用于逆NNT運(yùn)算。乘法模塊2用于完成逆NTT運(yùn)算結(jié)果除N運(yùn)算和消除K-RED2x運(yùn)算產(chǎn)生的k2縮放。由于k通常都不大，K-RED2x內(nèi)部的k2x0和kx1可以轉(zhuǎn)換為由移位和加法實(shí)現(xiàn)，不需要乘法運(yùn)算。

3 實(shí)現(xiàn)結(jié)果評估

為了便于結(jié)果評估，本文選用模數(shù)M=12 289，并設(shè)多項(xiàng)式的項(xiàng)數(shù)N=1 024，測試平臺采用Xilinx公司的XC7K325T型號FPGA。

Kuo等人[11]運(yùn)用了適合于硬件實(shí)現(xiàn)的模約減方法，但使用了較多的加法器，編譯頻率不高。Oder等人[12]使用的模約減模塊包含延時(shí)較大的關(guān)鍵路徑，且存取效率不高，編譯頻率也較低。本文的蝶形運(yùn)算模塊及LN模運(yùn)算模塊均采用流水線實(shí)現(xiàn)，所以實(shí)現(xiàn)頻率較高，達(dá)到了320 MHz。由于采用流水實(shí)現(xiàn)，預(yù)算模塊和NTT運(yùn)算可以并行執(zhí)行，且NTT內(nèi)部的蝶形運(yùn)算模塊同樣為流水結(jié)構(gòu)，從而大大提高了運(yùn)算性能。表1為本文多項(xiàng)式乘法硬件實(shí)現(xiàn)與現(xiàn)有一些硬件實(shí)現(xiàn)的比較結(jié)果。其中，查找表（Look-Up-Table，LUT）、寄存器（REGister，REG）、塊存儲器（Block RAM，BRAM）和乘法器（Digital Signal Processing，DSP）分別為FPGA內(nèi)硬件資源。

表1 多項(xiàng)式乘法硬件評估結(jié)果

4 結(jié)語

本文提出的多項(xiàng)式乘法硬件實(shí)現(xiàn)方法，采用不完全模約減的方式取模，大大減少了取模的時(shí)間。同時(shí)采用了乒乓切換、流水技術(shù)和雙NTT模塊架構(gòu)，一方面提高了存儲器讀寫帶寬，另一方面減少了運(yùn)算過程中的等待時(shí)間，從而提升了運(yùn)算性能。此外，由于采用了流水設(shè)計(jì)，編譯主頻也較高，達(dá)到了320 MHz。因此，本設(shè)計(jì)無論是在資源占用方面還是在處理性能方面都具有一定的優(yōu)勢，對基于格的后量子密碼的硬件實(shí)現(xiàn)具有一定的參考意義。