基于 FPGA 的格密碼關(guān)鍵運算模塊的設(shè)計與實現(xiàn)

隨著量子計算技術(shù)的發(fā)展，量子計算機將能在人們可以接受的時間內(nèi)破解許多目前計算機無法破解的密碼，其中就包括目前大部分公鑰密碼系統(tǒng)所依賴的大整數(shù)質(zhì)數(shù)拆分問題和離散對數(shù)問題這兩大數(shù)學(xué)難題。為應(yīng)對量子計算機為傳統(tǒng)密碼系統(tǒng)帶來的挑戰(zhàn)，后量子密碼已成為國內(nèi)外眾多學(xué)者的重點研究對象。2016年，美國國家標(biāo)準(zhǔn)與技術(shù)研究院（NationInstituteofStandardsandTechnology，NIST）開始了一項針對抗量子密碼系統(tǒng)的征集計劃，旨在尋找、設(shè)計、開發(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個抗量子算法：Crystals-kyber、CRYSTALSDILITHIUM、FALCON和SPHINCS+。這4個算法中有3個基于格的數(shù)學(xué)難題，另一個使用了散列函數(shù)。由此可見，基于格的密碼方案是抗量子計算密碼學(xué)中的研究熱點?；诟竦拿艽a算法中的運算大多為線性運算，因此較其他密碼系統(tǒng)，基于格的密碼系統(tǒng)具有計算速度快、密鑰和密文較小等優(yōu)勢。本文對格密碼中的關(guān)鍵模塊——多項式乘法進行研究，給出了一種多項式乘法的運算方法和硬件實現(xiàn)架構(gòu)，并在現(xiàn)場可編程門陣列（FieldProgramGateArray，F(xiàn)PGA）中進行了實現(xiàn)和評估，為格密碼硬件實現(xiàn)提供參考。１相關(guān)數(shù)學(xué)基礎(chǔ)1.1格密碼數(shù)學(xué)基礎(chǔ)線性獨立空間上有集合格就是這些向量的線性組合，這一過程的表達式為：式中：系數(shù)a均在整數(shù)域Z中。任意一組可以生成格的線性無關(guān)向量都稱為格的基，格的維度等于格的基中的向量個數(shù)。目前常用的兩個基于格的困難問題是短整數(shù)問題（ShortestIntegerProblem，SIS）和錯誤學(xué)習(xí)問題（LearningWithError，LWE），但基于上述兩個問題的加密方案需要的密鑰量大、效率低、資源消耗高，無法在實際中運用。因此，在LWE的基礎(chǔ)上提出了環(huán)上錯誤學(xué)習(xí)（RingLearningWithErrors，RLWE）問題?；赗LWE的加密方案在性能上有著顯著的優(yōu)勢，這是現(xiàn)在許多格密碼算法的理論基礎(chǔ)。RLWE在環(huán)上進行操作，其中f是n項的不可約多項式，通常其中n是2的冪，q為素數(shù)。1.2環(huán)多項式乘法對于RLWE密碼算法，其中最為耗時的是環(huán)多項式乘法。環(huán)多項式乘法有兩種實現(xiàn)方式，分別為經(jīng)典乘法和快速數(shù)論變換（NumberTheoreticTransform，NTT）乘法。1.2.1經(jīng)典乘法經(jīng)典乘法先把多項式a中的每一項與多項式b中的每一項相乘，再把每個多項式相加得到最終結(jié)果。如果多項式a和b的最高次項都為那么計算復(fù)雜度為需要個乘法和個加減法。1.2.2NTT乘法NTT是基于快速傅里葉變換（FastFourierTransform，F(xiàn)FT）實現(xiàn)的，其將FFT中的旋轉(zhuǎn)因子由復(fù)數(shù)變成了整數(shù)。設(shè)正整數(shù)序列其所有元素均小于模數(shù)M，有如下NTT變換：式（2）為NTT正變換，式（3）為逆NTT變換。其中，a為模M的N階本原單位根，滿足：在模M下的逆元，滿足以下性質(zhì)：NTT運算是一個遞推的過程，圖1給出了N=8點的NTT運算結(jié)構(gòu)。如圖1中的橢圓標(biāo)識所示，NTT變換后的結(jié)果順序與原輸入順序呈二進制的倒序關(guān)系，因此為避免在計算完成后進行順序變換，通常采用逆序的方式進行運算，運算結(jié)構(gòu)如圖2所示。圖3為一次蝶形運算。N通?？梢员硎緸?的冪的形式，則N點NTT運算需要執(zhí)行次蝶形運算，所以8點NTT需要執(zhí)行12次蝶形運算。圖18

點NTT運算結(jié)構(gòu)圖28點

NTT逆序運算結(jié)構(gòu)圖3蝶形運算２多項式乘法FPGA實現(xiàn)2.1多項式乘法算法NTT中的每一次蝶形運算都需要做一次乘法和乘法結(jié)果取模運算，因此快速完成乘法和取模運算是提高NTT運算效率的關(guān)鍵。本文采用了Longa等人提出的適用于模數(shù)的高效取模算法，即LN取模算法，再結(jié)合FPGA內(nèi)部的高效乘法器來實現(xiàn)NTT快速運算。LN取模算法有K-RED和K-RED2x兩種形式，如算法1和算法2所示。算法1適用于對加法結(jié)果取模，算法2適用于對乘法結(jié)果取模。NTT變換和逆NTT變換算法如下：算法3中M為模數(shù)，為單位根，N為多項式的項數(shù)，如果N不滿足2的整數(shù)次冪需要補0。步驟6-9為一次蝶形運算。步驟11正變換查逆變換查算法4中的步驟7每運算一次相當(dāng)于在該項上乘以了k，步驟8每運算一次相當(dāng)于在該項上乘以如果對步驟8中每個都乘以經(jīng)過步驟8運算后也相當(dāng)于該項上乘以k。NTT每一項的運算次數(shù)為算法4中步驟2總的循環(huán)次數(shù)，即次（N為多項式的項數(shù)）。所以每項都增加了倍，增加部分可以通過預(yù)計算的方式消除。算法5中的步驟1是為了消除NNT運算時每項增加的倍而做的預(yù)處理。步驟6中的則是為了消除INNT運算后擴大的倍，并完成INNT運算后的除法運算。2.2多項式乘法FPGA實現(xiàn)多項式乘法的FPGA實現(xiàn)如圖4所示。圖4多項式乘法FPGA實現(xiàn)2.2.1數(shù)據(jù)預(yù)運算模塊數(shù)據(jù)預(yù)運算模塊用于對多項式數(shù)據(jù)進行預(yù)處理，同時完成對多項式的倒位序。ROM地址表內(nèi)存放預(yù)計算好的位序映射表。根據(jù)ROM讀出的地址讀取原始序列，預(yù)運算后寫入NTT模塊內(nèi)的存儲器中。2.2.2NTT模塊圖5為NTT模塊的實現(xiàn)。圖5NTT實現(xiàn)數(shù)據(jù)RAM1和數(shù)據(jù)RAM2為多項式系數(shù)存儲區(qū)，由于FPGA內(nèi)部實現(xiàn)的RAM通常只有2路通道，不能滿足蝶形運算同時對RAM的2次讀和寫操作。為了解決這個問題，本文設(shè)計了RAM1和RAM2兩個數(shù)據(jù)存儲區(qū)。當(dāng)RAM1作為數(shù)據(jù)讀取區(qū)時，蝶形運算的結(jié)果寫入RAM2區(qū)，當(dāng)RAM2作為數(shù)據(jù)讀取區(qū)時，蝶形運算的結(jié)果寫入RAM1區(qū)，由內(nèi)部控制模塊乒乓切換兩個數(shù)據(jù)區(qū)的讀寫模式。預(yù)計算查找表用于存放蝶形運算所需的預(yù)計算數(shù)據(jù)，該數(shù)據(jù)可以預(yù)先計算好后固化在存儲區(qū)內(nèi)部，不占用NTT的計算時間。預(yù)計算的數(shù)據(jù)包括蝶形運算及控制模塊通過狀態(tài)機控制NTT的3層循環(huán)，以及每次蝶形數(shù)據(jù)和預(yù)計算數(shù)據(jù)的讀取，調(diào)用K-RED和完成運算。因蝶形運算下一次的輸入數(shù)據(jù)不會用到上一次的結(jié)果，所以蝶形運算可實現(xiàn)流水操作，從而提升運算性能。2.2.3乘法模塊乘法模塊用于完成算法5的步驟4和步驟6。其中乘法模塊1用于完成兩個多項式轉(zhuǎn)換到NTT域后各項的相乘，并根據(jù)ROM地址表內(nèi)存放的地址讀取多項式的值相乘，將結(jié)果存放在NNT的RAM內(nèi)，用于逆NNT運算。乘法模塊2用于完成逆NTT運算結(jié)果除N運算和消除運算產(chǎn)生的縮放。由于k通常都不大，內(nèi)部的和可以轉(zhuǎn)換為由移位和加法實現(xiàn)，不需要乘法運算。３實現(xiàn)結(jié)果評估為了便于結(jié)果評估，本文選用模數(shù)M=12289，并設(shè)多項式的項數(shù)N=1024，測試平臺采用Xilinx公司的XC7K325T型號FPGA。Kuo等人運用了適合于硬件實現(xiàn)的模約減方法，但使用了較多的加法器，編譯頻率不高。Oder等人使用的模約減模塊包含延時較大的關(guān)鍵路徑，且存取效率不高，編譯頻率也較低。本文的蝶形運算模塊及LN模運算模塊均采用流水線實現(xiàn)，所以實現(xiàn)頻率較高，達到了320MHz。由于采用流水實現(xiàn)，預(yù)算模塊和NTT運算可以并行執(zhí)行，且NTT內(nèi)部的蝶形運算模塊同樣為流水結(jié)構(gòu)，從而大大提高了運算性能。表1為本文多項式乘法硬件實現(xiàn)與現(xiàn)有一些硬件實現(xiàn)的比較結(jié)果。其中，查找表（Look-Up-Table，LUT）、寄存器（REGister，REG）、塊存儲器（BlockRAM，BRAM）和乘法器（DigitalSignalProcessing，DSP）分別為FPGA內(nèi)硬件資源。表1?多項式乘法硬件評估結(jié)果４結(jié)?語本文提出的多項式乘法硬件實現(xiàn)方法，采用不