Saber 算法的多項式乘法FPGA 實現(xiàn)研究*

范建南 高獻偉 薛文瀚

北京電子科技學(xué)院，北京市 100070

1 引言

為了抵抗量子算法的攻擊，美國國家標(biāo)準與技術(shù)研究院（National Institute of Standards and Technology，NIST）于2016 年正式啟動了后量子密碼標(biāo)準征集［1］。 經(jīng)過三輪激烈的競爭，基于格結(jié)構(gòu)的Saber 算法憑借帶寬低、靈活性高等特點［2］，成為最終7 種候選算法之一。 Saber 算法具有較為獨特的參數(shù)集設(shè)計，其模數(shù)n為2 的整數(shù)次冪，非常適合硬件實現(xiàn)。 許多學(xué)者正努力對Saber 算法進行硬件高效實現(xiàn)，以促進Saber 算法設(shè)計方案的不斷完善，從而影響后量子密碼的標(biāo)準化進程。

文獻［3］對基于格的后量子密碼算法展開了全面的調(diào)查研究，指出基于格的后量子密碼算法有兩大關(guān)鍵問題，分別是多項式乘法與離散高斯采樣。 作為Saber 算法的核心部件，多項式乘法成為了算法實現(xiàn)的主要加速瓶頸。 近年來，國內(nèi)外有多個團隊使用不同方法對多項式乘法進行硬件實現(xiàn)研究。 文獻［4］提出了格密碼的一種指令集協(xié)處理器結(jié)構(gòu)，并實現(xiàn)了高度并行的schoolbook 多項式乘法器，只需要256 個循環(huán)便能計算1 次多項式乘法，但會消耗大量的硬件邏輯資源。 文獻［5］在Saber 算法的高速SW／HW代碼設(shè)計中，使用256 個帶13 位輸入的DSP（digital signal process，數(shù)字信號處理）單元設(shè)計了基于schoolbook 的乘法器。 文獻［6］針對現(xiàn)有的SPMA（schoolbook polynomial multiplication algorithm） 結(jié)構(gòu)， 提出了一種優(yōu)化的 SPMAKaratsuba 結(jié)構(gòu)，以92.06%的額外硬件開銷，獲得了2.09 倍的速度。 清華大學(xué)團隊采用8 級分層Karatsuba 算法實現(xiàn)多項式乘法，降低了面積開銷［7］。 文獻［8］在軟硬件協(xié)同實現(xiàn)中，設(shè)計了一種基于Toom-Cook 算法的Saber 乘法器。 文獻［9］在實現(xiàn)NTRU 算法非3－系數(shù)多項式乘法時，采用Toom-Cook-3 way 算法將一個n系數(shù)多項式乘法拆分為5 個n／3 系數(shù)乘法，然后使用5個奇偶Karatsuba 乘法器對n／3 系數(shù)乘法并行計算。

為了進一步提高硬件實現(xiàn)的效率，本文在分析schoolbook 算法、Karatsuba 算法、Toom-Cook算法基礎(chǔ)上，融合這三種方法，針對Saber 算法中的256×256 多項式乘法，提出五種基于Toom-Cook 算法的多項式乘法改進方案，并完成改進方案的FPGA（field programmable gate array，現(xiàn)場可編程門陣列）設(shè)計，在通過功能仿真的基礎(chǔ)上，使用具有自主知識產(chǎn)權(quán)的國產(chǎn)FPGA 芯片進行綜合，對五種方案的性能進行嚴謹?shù)姆治霰容^，找到了Saber 算法中高效實現(xiàn)多項式乘法運算的一種設(shè)計方法。

2 多項式乘法

2.1 Saber 算法的多項式乘法

Saber 算法具有三個參數(shù)集，分別對應(yīng)不同的安全等級。 對于任意參數(shù)集，所有的運算都在環(huán)Z q［x］／（xn ＋1） 上進行。 其中，階數(shù)n ＝256表示多項式中變量的最高次數(shù)為255，即每個多項式都有256 個系數(shù)，模數(shù)q ＝213表示多項式的每個系數(shù)都有13 位，模數(shù)的如此設(shè)計能夠避免模約減運算，便于算法的硬件實現(xiàn)。 實現(xiàn)多項式乘法的方法很多，目前最快的算法是快速數(shù)論變換（number theoretic transforms，NTT），然而，使用NTT 算法要求模數(shù)必須為素數(shù)［10］，對于模數(shù)q ＝213的Saber 算法并不適用。 因此，考慮使用算法復(fù)雜度略高的常用方法，在優(yōu)化改進后實現(xiàn)Saber 算法的多項式乘法。

2.2 經(jīng)典schoolbook 多項式乘法算法

對于Saber 算法中的256×256 多項式乘法運算，一個簡單易行的方法為schoolbook 算法。事實上，schoolbook 算法屬于傳統(tǒng)的乘法運算方法，經(jīng)過2 層的嵌套迭代，共計256×256 次乘法運算，便可求得最終結(jié)果。 算法1 給出了該算法的詳細描述，對于具有256 個系數(shù)的多項式a與多項式b的乘法運算，多項式a的第1 個系數(shù)a0經(jīng)過第1 層256 次迭代，分別乘以多項式b的256 個系數(shù)b0……b255，在第2 層循環(huán)迭代中依次將多項式a的剩余系數(shù)a1……a255重復(fù)執(zhí)行第1 層運算操作，然后與對應(yīng)位置的中間值進行累加，取模后完成256×256 次乘法運算。 對于n階多項式乘法運算，采用schoolbook 算法具有二次復(fù)雜度n2， 單一地使用全并行schoolbook 算法實現(xiàn)256×256 多項式乘法運算將消耗大量的硬件資源。

算法1：schoolbook 求解256×256 多項式乘法輸入：階數(shù)為256 的多項式a階數(shù)為256 的多項式b輸出：階數(shù)為511 的多項式c計算過程：1. for i ＝0 to 255 do 2. for j ＝0 to 255 do 3. c［i ＋j］ ＋＝a［i］·b［j］mod（213） ；4. return c

2.3 基于Karatsuba 的多項式乘法算法

Karatsuba 算法是由A. Karatsuba 于1960 年發(fā)現(xiàn)的一種快速乘算法［11］，該算法采用“分治”思想，通過循環(huán)遞歸將多項式乘法運算逐步二分拆解，直至拆解后的最小運算單元結(jié)構(gòu)簡單、易于求解，再進行小數(shù)乘法，并重組所乘的全部中間值，求得多項式乘法運算的最終結(jié)果。

以計算A（x）× B（x） 為例，假設(shè)A（x） 和B（x） 是環(huán)Z q［x］／（xn ＋1） 上的兩個n階多項式，分別取A（x）＝an－1xn－1＋…＋a1x ＋a0，B（x）＝bn－1xn－1＋…＋b1x ＋b0。 階數(shù)n可能為素數(shù)，而Karatsuba 算法的“分治”思想要求n為2 的整數(shù)次冪。 如果n是2 的整數(shù)次冪，則直接使用Karatsuba 算法；如果n不是2 的整數(shù)次冪，則可以通過給高位系數(shù)補上若干個“0”，使得新的階數(shù)nnew變成2 的整數(shù)次冪。 對于后量子Saber 算法，其階數(shù)n ＝256，恰好是2 的整數(shù)次冪，可直接使用Karatsuba 算法進行迭代計算。

使用Karatsuba 算法計算A（x）× B（x） 時，首先將多項式A（x）、B（x） 直接拆分為兩部分，即：

總共需要四組乘法才能完成運算，而Karatsuba 算法巧妙地通過增加加法和減法運算，減少了乘法運算，求解表達式如式（3）所示。

其中，P1、P2、P3分別由式（4）、（5）、（6）共三組乘法計算得來。

相較于式（2）中的經(jīng)典方法，Karatsuba 算法減少了一組乘法運算。

圖1 以aw1× bw1為例，給出了Karatsuba 算法的原理框圖。

圖1 Karatsuba 算法的原理框圖

首先，將aw1和bw1分別拆分為長度相等的兩部分aw1＿H、aw1＿L及bw1＿H、bw1＿L， 然后分別將aw1及bw1的高低兩部分相加得到中間量aHaL＿p及bHbL＿p，使用三次乘法運算將對應(yīng)部分相乘，其中，中間量的乘積結(jié)果ab＿p減去另外兩部分的乘積結(jié)果，得到ab11＿h、ab11＿l及ab11＿m后，經(jīng)移位重組求得最終的乘法運算結(jié)果。 算法2 給出了使用Karatsuba 算法求解2n ×2n多項式乘法的詳細步驟，其中，圖1 中的重組過程即為算法2 中第11 行的移位加法操作。 算法中的RM（recursive multiplication）表示子多項式的迭代乘法運算，通過調(diào)用下一輪的Karatsuba 算法，計算更小單元的多項式乘法。 算法2 中第7－10行便是使用若干輪的RM 運算進行子多項式迭代乘法，計算得到的結(jié)果ab＿L、ab＿H、ab＿M即為圖1 中的運算中間值ab11＿l、ab11＿h、ab11＿m。

算法2：Karatsuba 求解2n × 2n 多項式乘法輸入：階數(shù)為2n 的多項式a階數(shù)為2n 的多項式b輸出：階數(shù)為4n－ 1 的多項式c計算過程：

算法2：Karatsuba 求解2n × 2n 多項式乘法1. a＿L ＝a［n－ 1 ∶0］ ；2. a＿H ＝a［2n－ 1：n］ ；3. b＿L ＝b［n－ 1 ∶0］ ；4. b＿H ＝b［2n－ 1：n］ ；5. a＿P［n－ 1 ∶0］ ＝a＿H ＋a＿L；6. b＿P［n－ 1 ∶0］ ＝b＿H ＋b＿L；7. ab＿L［2n－ 2 ∶0］ ＝RM（a＿L，b＿L） ；8. ab＿H［2n－ 2 ∶0］ ＝RM（a＿H，b＿H） ；9. ab＿P［2n－ 2 ∶0］ ＝RM（a＿P，b＿P） ；10. ab＿M［2n－ 2 ∶0］ ＝ab＿P－ab＿L－ab＿H；11. c［4n－2∶0］ ＝（ab＿H?2n） ＋（ab＿M?n） ＋ab＿L；12. return c說明：每步計算完成后都進行mod（213） 約減操作

因此，對于2n ×2n的多項式乘法，1 輪Karatsuba 算法便可將其轉(zhuǎn)化為3 個n × n乘法，減少了開銷較大的乘法運算。 那么，對于Saber 算法的256×256 多項式乘法運算，使用8 輪Karatsuba 算法循環(huán)迭代就能將其轉(zhuǎn)化為最小單元的乘法運算。 使用Karatsuba 算法計算長度為n的多項式乘法，k輪迭代的示意圖如圖2 所示。

圖2 Karatsuba 算法k 輪迭代示意圖

Karatsuba 算法將長度為n的多項式進行迭代二分，每迭代一輪，長度縮短一半。 經(jīng)過k輪循環(huán)迭代，長度變?yōu)閚／2k。 如果將多項式迭代二分為最小的單數(shù)乘法，即n／2k ＝1， 則k ＝log2n，總共需要log2n輪迭代二分。 每輪Karatsuba 算法迭代，都巧妙地用3 次乘法運算代替4次乘法運算。 那么，k輪迭代后，算法的時間復(fù)雜度計算推導(dǎo)如式（7），Karatsuba 算法的時間復(fù)雜度為n1.585， 這比schoolbook 算法的二次復(fù)雜度更優(yōu)。

2.4 基于Toom-Cook 的多項式乘法算法

Toom-Cook 算法是Karatsuba 算法的更快推廣［12］，Karatsuba 算法可以看做Toom-Cook-k way在k ＝2 時的一種特例，其本質(zhì)都是利用了“分治”思想。 實際上，Toom-Cook-k way 算法由“拆分”、“評估”、“迭代乘法”、“插值”、“重組”五個步驟組成［13］。 對于兩個階數(shù)為n的多項式，Toom-Cook-k way 算法分別將其拆分為k個子多項式，在2k－1 個點上進行逐點評估，再將兩個多項式的評估值進行逐點乘法，隨后經(jīng)過插值求解出2k－1 組中間值，最后移位重組得到兩個多項式的乘法運算結(jié)果。 其中，k的取值較為靈活，如果k值取得較小，無法減小算法的時間復(fù)雜度，但k值取得較大，會增加評估及插值過程中的復(fù)雜計算。 綜合考慮Saber 算法的參數(shù)集特性，我們決定基于Toom-Cook-4 way 進行算法改進設(shè)計。 因此，下面給出Toom-Cook-4 way 求解n ×n多項式乘法A（x）×B（x） 五個步驟的具體描述。

2）評估：在7 個點上對式（8）中的多項式A（y）、B（y） 逐點評估，即將7 個點的值分別帶入A（y）、B（y） 的表達式，求得7 組評估結(jié)果。為了盡可能減少乘法運算，進一步提高運算效率，選取y ＝｛0，±1／2，±1，2，∞｝ 作為評估的7個點。 此時，評估過程中的乘法因子要么是計算簡單的0、±1、∞，要么是2 的整數(shù)次冪，這可通過簡單的移位操作實現(xiàn)。 式（9）給出對多項式A（x） 進行評估的表達式，多項式B（x） 的評估表達式與此類似。

4）插值：與評估相反，插值是求解7 個線性無關(guān)的方程組，在y ＝｛0，±1／2，±1，2，∞｝ 上，根據(jù)式（10）與式（11）可以得到C（y） 的7 組迭代乘法值與各組系數(shù)C0、C1、C2、C3、C4、C5、C6的關(guān)系如下：

此時，對上述矩陣關(guān)系進行變形，可得：

求出式（13）中系數(shù)矩陣的逆，可得：

其中，步驟3）的迭代乘法運算，可通過Toom-Cook-4 way 算法對子多項式乘法進行若干輪循環(huán)迭代，將寬系數(shù)乘法轉(zhuǎn)化為窄系數(shù)乘法，寬系數(shù)乘法為含有較多系數(shù)的多項式乘法，窄系數(shù)乘法為含有較少系數(shù)的多項式乘法，窄系數(shù)乘法的計算復(fù)雜度優(yōu)于寬系數(shù)乘法。 在Toom-Cook-4 way 算法步驟中，每經(jīng)過1 輪循環(huán)迭代，多項式的階數(shù)便降為原來的四分之一。 Saber 算法中乘法多項式的階數(shù)n ＝256，恰好為4 的4次冪，那么，對于Saber 算法中的256×256 多項式乘法，經(jīng)過4 輪Toom-Cook-4 way 算法循環(huán)迭代，即可轉(zhuǎn)化為最小的單數(shù)乘法，進而求得最終結(jié)果。 上述五個步驟中，插值過程較為復(fù)雜［14］，算法3 根據(jù)插值公式（14），結(jié)合步驟5）的移位累加思路，給出了Toom-Cook-4 way 算法求解256×256 多項式乘法時插值與重組過程的偽代碼。

算法3：Toom-Cook-4 way 算法的插值與重組輸入：含有127 個系數(shù)的7 個數(shù)組w1 至w7輸出：含有511 個系數(shù)的數(shù)組c計算過程：／ ／插值過程1. for i ＝0 to 126 do 2. r1 ＝w1［i］；r2 ＝w2［i］；r3 ＝w3［i］ ；3. r4 ＝w4［i］；r5 ＝w5［i］；r6 ＝w6［i］ ；4. r7 ＝w7［i］；r2 ＝r2 ＋r5；r6 ＝r6－r5；5. r4 ＝（（r4－r3） ＞＞1） ；6. r5 ＝（（r5－r1－ （r7 ＜＜6）） ＜＜1） ＋r6；7. r3 ＝r3 ＋r4；r2 ＝r2－ （r3 ＜＜6）－r3；8. r3 ＝r3－r7－r1；r2 ＝r2 ＋45*r3；9. r5 ＝（（（r5－ （r3 ＜＜3））*43691） ＞＞3） ；10. r6 ＝r6 ＋r2；r3 ＝r3－r5；11. r2 ＝（（（r2 ＋（r4 ＜＜4））*36409） ＞＞1） ；12. r6 ＝（（（（30*r2）－r6）*61167） ＞＞2） ；13. r4 ＝－ （r4 ＋r2）；r2 ＝r2－r6；／ ／重組過程14. c［i］ ＋＝r7；c［i ＋64］ ＋＝r6；c［i ＋128］ ＋＝r5；15. c［i ＋192］ ＋＝r4；c［i ＋256］ ＋＝r3；16. c［i ＋320］ ＋＝r2；c［i ＋384］ ＋＝r1；17.return c說明：每步計算完成后都進行mod（213） 約減操作

在算法插值過程中，除了乘法、加法和減法外，需特別關(guān)注除法運算。 當(dāng)除以一個奇數(shù)時，就相當(dāng)于乘以該奇數(shù)在mod（213） 下的逆，算法3 第9、11、12 行的數(shù)值43691、36409、61167 分別是乘數(shù)因子3、9、15 在mod（213） 下的逆；當(dāng)除以2 的整數(shù)次冪時，相當(dāng)于進行右移操作，右移操作可能會造成精度的損失，從而導(dǎo)致結(jié)果的錯誤。 整個Toom-Cook-4 way 算法的計算過程最多右移3 位，為了保證結(jié)果的正確性，需額外3位的精度，算法設(shè)計的數(shù)據(jù)位寬最少應(yīng)為16位［8］。 使用Toom-Cook-4 way 算法計算長度為n的多項式乘法，進行k輪迭代的示意圖如圖3所示。

圖3 Toom-Cook-4 way 算法k 輪迭代示意圖

Toom-Cook-4 way 算法將長度為n的多項式進行迭代運算，每迭代一輪將其拆分為7 次乘法，長度縮短為原來的四分之一。 經(jīng)過k輪迭代，長度變?yōu)閚／4k，如果將多項式迭代為最小的單數(shù)乘法，即n／4k ＝1，那么，k ＝log4n ＝（1／2）·log2n，總共需要（1／2）·log2n輪迭代。k輪迭代后，算法的時間復(fù)雜度計算推導(dǎo)如下：

3 基于Toom-Cook 的多項式乘法算法改進方案

Toom-Cook 算法相較于經(jīng)典schoolbook 算法及Karatsuba 算法，具有更低的時間復(fù)雜度。 但插值、重組等過程引入了乘法及較多的加減法運算，對于階數(shù)n ＝256 的多項式乘法并沒有帶來最優(yōu)的實現(xiàn)效果。 本文結(jié)合第2 章中介紹的Karatsuba 算法及經(jīng)典schoolbook 算法，設(shè)計一種基于Toom-Cook 的多項式乘法算法改進方案。設(shè)計的基本思想是使用1 輪Toom-Cook-4 way 算法，加上若干輪Karatsuba 算法循環(huán)迭代，底層調(diào)用schoolbook 算法，高效完成多項式乘法運算，該設(shè)計的關(guān)鍵問題是確定Karatsuba 算法的迭代輪數(shù)。 根據(jù)章節(jié)2.3 中的分析，Karatsuba 算法通過增加簡單的加減法運算減少復(fù)雜的乘法運算，但是隨著迭代輪數(shù)的增加，大量增加的加減法運算并不能起到加速多項式乘法運算的效果。找到合適的Karatsuba 算法迭代輪數(shù)，對高效實現(xiàn)整個256×256 多項式乘法尤為重要。

該設(shè)計方法的原理如圖4 所示，首先使用1輪Toom-Cook-4 way 算法，將階數(shù)為256 的多項式A（x） 與多項式B（x） 拆分為四部分，每一部分的階數(shù)為64，在7 個點y ＝｛0，±1／2，±1，2，∞｝ 上分別對其進行逐點評估，將256×256 多項式乘法轉(zhuǎn)化為7 個64×64 多項式乘法，再使用若干輪Karatsuba 算法對64×64 多項式乘法進一步二分拆解，每迭代一輪，長度縮短一半。 在Karatsuba 算法迭代過程中，不斷調(diào)用schoolbook 算法進行全乘。 將迭代乘法所得的7 組中間值（每組含有127 個系數(shù)），利用插值求出C（x） 的7 組系數(shù)，然后經(jīng)移位重組得到含有511 個系數(shù)的多項式乘法運算結(jié)果C（x）。

圖4 基于Toom-Cook 算法的改進型設(shè)計原理圖

由于該多項式乘法是在環(huán)Z213［x］／（x256＋1） 上進行的，還需額外進行mod（x256＋1） 約減，得到含有256 個系數(shù)（每個系數(shù)含有13 位）的多項式乘法最終結(jié)果C′（x）。

考慮到Karatsuba 算法迭代輪數(shù)能決定整個改進型設(shè)計方法的效率，因此根據(jù)Karatsuba 算法迭代輪數(shù)的不同，可得到下面五種設(shè)計方案。

方案1 ∶1 輪Toom-Cook-4 way 算法＋1 輪Karatsuba 算法＋schoolbook 算法32×32 全乘。使用1 輪Toom-Cook-4 way 算法將256×256 算法轉(zhuǎn)化為7 個64×64 多項式乘法，然后使用1 輪Karatsuba 算法，將每1 個64×64 多項式乘法轉(zhuǎn)化為3 個32×32 多項式乘法，隨后直接調(diào)用schoolbook 算法完成32×32 多項式乘法運算；

方案2 ∶1 輪Toom-Cook-4 way 算法＋2 輪Karatsuba 算法＋schoolbook 算法16×16 全乘。與方案1 類似，增加1 輪Karatsuba 算法迭代，在計算32 × 32 多項式乘法時， 再使用1 輪Karatsuba 算法，將每1 個32×32 多項式乘法轉(zhuǎn)化為3 個16×16 多項式乘法，隨后直接調(diào)用schoolbook 算法完成16×16 多項式乘法運算；

方案3 ∶1 輪Toom-Cook-4 way 算法＋3 輪Karatsuba 算法＋schoolbook 算法8×8 全乘。 在方案2 基礎(chǔ)上，使用第3 輪Karatsuba 算法將每1個16×16 多項式乘法轉(zhuǎn)化為3 個8×8 多項式乘法，隨后直接調(diào)用schoolbook 算法完成8×8 多項式乘法運算；

方案4 ∶1 輪Toom-Cook-4 way 算法＋4 輪Karatsuba 算法＋schoolbook 算法4×4 全乘。 在方案3 基礎(chǔ)上，再使用1 輪Karatsuba 算法將每1個8×8 多項式乘法轉(zhuǎn)化為3 個4×4 多項式乘法，隨后直接調(diào)用schoolbook 算法完成4×4 多項式乘法運算；

方案5 ∶1 輪Toom-Cook-4 way 算法＋5 輪Karatsuba 算法＋schoolbook 算法2×2 全乘。 在方案4 基礎(chǔ)上，再使用1 輪Karatsuba 算法將每1個4×4 多項式乘法轉(zhuǎn)化為3 個2×2 多項式乘法，隨后直接調(diào)用schoolbook 算法完成2×2 多項式乘法運算；

這五種方案相似，只是Karatsuba 算法迭代輪數(shù)不同。 Karatsuba 算法本身是一種天然的迭代算法，在本設(shè)計中，為了計算7 個64×64 多項式乘法，需要重復(fù)調(diào)用Karatsuba 算法，Karatsuba算法的每次循環(huán)迭代結(jié)構(gòu)相似、操作相同。 根據(jù)這一特性，采用循環(huán)迭代設(shè)計方法，如圖5 所示，即一個時鐘周期調(diào)用1 次Karatsuba 算法。 以方案2 為例，進行2 輪Karatsuba 算法迭代，每輪重復(fù)調(diào)用3 次Karatsuba 算法，總共需要9（3×3）個時鐘周期。 那么，對于Toom-Cook-4 way 中的迭代乘法過程，也只需要63（7×3×3）個時鐘周期，便可調(diào)用到最底層的schoolbook 算法計算16×16 多項式乘法。 該設(shè)計方法的特點是通過循環(huán)迭代復(fù)用運算單元，減少硬件資源的消耗，盡管在一定程度上會降低計算速度，但由于迭代輪數(shù)并不多，所消耗的時鐘周期增加的并不明顯，能夠達到較佳的實現(xiàn)效果。

圖5 循環(huán)迭代設(shè)計方法

底層的schoolbook 算法復(fù)雜度相對較高，但處理的乘法為窄系數(shù)多項式乘法，考慮到該算法需要被上層多次調(diào)用，為了加速整個融合算法，底層schoolbook 算法采用并行循環(huán)迭代結(jié)構(gòu)，如圖6所示。 對于調(diào)用schoolbook 算法計算n × n的多項式乘法，使用n個并行的乘法運算單元，1 個時鐘周期迭代1 輪，每輪并行完成n個乘法運算，經(jīng)過n個時鐘周期，便可完成全部n × n乘法運算，既不會消耗過多的硬件資源，也能減少時鐘周期。

圖6 并行循環(huán)迭代設(shè)計方法

4 仿真結(jié)果與性能分析

4.1 仿真結(jié)果

對于本文所設(shè)計的基于Toom-Cook 的多項式乘法算法改進方案，采用Verilog HDL 對五種設(shè)計方案進行編程，并在Modelsim SE 10.2c 中進行了多組數(shù)據(jù)的仿真實驗，驗證了其正確性。其中一組數(shù)據(jù)的仿真結(jié)果如圖7 所示，從仿真時間點t ＝0.01ns 開始運算（EndFlag 由無效值跳變?yōu)?），經(jīng)過7.63ns 的計算，在仿真時間點t ＝7.64ns 結(jié)束運算（EndFlag 由0 跳變?yōu)?），得到多項式乘法的最終運算結(jié)果。 對于Saber 算法中的256×256 多項式乘法運算，隨機生成若干組含有256 個系數(shù)的多項式a與多項式b，每個系數(shù)含有13 位，將其分別存放在256×16 的向量中，輸入算法后經(jīng)過計算得到長度為256×13 的多項式c。 我們對多組隨機多項式的乘法運算進行了仿真，并調(diào)用Saber 算法公開的C 源碼對這些多項式乘法進行驗算，所求結(jié)果皆與本設(shè)計的仿真結(jié)果一致，驗證了本設(shè)計的正確性。

圖7 256×256 多項式乘法的運算結(jié)果

4.2 基于國產(chǎn)FPGA 的多項式乘法改進方案性能分析

在對設(shè)計方案完成功能仿真后，為了更好評估算法性能，從五種方案中找出較為高效的多項式乘法運算方法，可進一步對其進行分析綜合。當(dāng)前，國家正大力推進芯片產(chǎn)業(yè)振興發(fā)展，許多優(yōu)質(zhì)的國產(chǎn)芯片、國產(chǎn)平臺應(yīng)運而生。 本文選擇深圳紫光同創(chuàng)電子有限公司開發(fā)的FPGA 設(shè)計平臺Pango Design Suite，F(xiàn)PGA 器件選擇該公司設(shè)計的Titan 系列。 作為中國第一款具有自主知識產(chǎn)權(quán)的千萬門級高性能FPGA 產(chǎn)品，Titan 系列采用了具有成熟工藝和自主產(chǎn)權(quán)的體系結(jié)構(gòu)。我們選用的器件是Titan 系列PGT180H－7FFBG676，該器件有145016 個LUT（look-up tables，查找表），217524 個FF（flip flop，觸發(fā)器），以及224 個APM（arithmetic process module，算術(shù)處理單元）。 在Pango Design Suite 上使用該器件對五種設(shè)計方案進行綜合，表1 給出了不同設(shè)計方案的性能分析。

表1 五種多項式乘法設(shè)計方案的性能分析

主要的性能指標(biāo)為算法所使用的基本邏輯單元LUT、FF 和算術(shù)處理單元APM，以及算法運行的最高頻率Fmax 和時鐘數(shù)Clock，不同設(shè)計方案的這五個性能指標(biāo)數(shù)據(jù)都已在表1 中列出。 FPGA 設(shè)計主要目標(biāo)是高速度或小面積，為了得到一個最優(yōu)的速度與面積的折中方案，本文采用性能指標(biāo)AFR（area-frequency ratio，面頻比率），該指標(biāo)的計算公式為：

A 為占用的硬件資源面積，包含LUT、FF 等基本邏輯單元的數(shù)目；T ＝t／f表示算法運行一次所需要的時間，其中，t為使用的時鐘數(shù)目，f為算法運行的最高頻率。 面頻比率AFR 越小，則說明占用的硬件資源面積小且運行速度快，這是FPGA 設(shè)計所追求的目標(biāo)。 綜合分析可知，方案1 與方案2 由于Karatsuba 迭代輪數(shù)少，直接調(diào)用底層schoolbook 算法進行較寬系數(shù)的全乘運算，一方面會使用較多的算術(shù)處理模塊APM，且耗費更多的硬件邏輯資源，另一方面也會拖慢算法運行速度，性能表現(xiàn)并不佳。 方案3、4、5 所使用的邏輯資源相差不大，主要區(qū)別體現(xiàn)在運行速度上，隨著Karatsuba 算法迭代輪數(shù)的增加，算法運行所能達到的最高頻率也不斷增大，對比發(fā)現(xiàn)，方案5 使用的LUT 及FF 數(shù)目雖然比方案3及方案4 更多一些，但其面頻比率AFR 更小，運行速度更快，且使用了更少的算術(shù)處理模塊，是五種方案中最佳的多項式乘法設(shè)計方案。

為了更好地評估方案5 的算法性能，將其與其他文獻的實現(xiàn)方法進行對比分析。 文獻［9］使用經(jīng)典schoolbook 算法實現(xiàn)了Saber 算法256×256 多項式乘法，最高頻率達到370MHz，且只需要256 個Clock，實現(xiàn)了算法運行的高速度，但卻消耗了11426 個LUT 及8727 個FF，占用了較多的硬件邏輯資源。 文獻［6］結(jié)合Karatsuba 算法與schoolbook 算法，實現(xiàn)了后量子R-LWE（ring-learning with error，環(huán)錯誤學(xué)習(xí)）算法（參數(shù)選擇為n＝256、q＝7681）的多項式乘法，僅使用了1125 個LUT 及1034 個FF，且最高頻率為335.8MHz，但完成一次運算卻需要8787 個Clock。 對比發(fā)現(xiàn)，本文設(shè)計的方案5，雖然沒有文獻［9］的高速度，也沒有文獻［6］的低面積，卻彌補了上述兩種方法的缺陷，找到了速度與面積的平衡折中，在使用較少的硬件資源下，達到了較快的運算速度。 因此，后量子Saber 算法在進行256×256 多項式乘法時，較高效的算法是使用1 輪Toom-Cook-4 way 算法結(jié)合5 輪Karatsuba算法及schoolbook 算法2×2 全乘。

5 結(jié)束語

本文針對后量子Saber 算法的核心部件多項式乘法運算，結(jié)合Karatsuba 算法及經(jīng)典schoolbook 算法，提出了五種基于Toom-Cook 的多項式乘法算法改進方案，并在國產(chǎn)FPGA 開發(fā)平臺Pango Design Suite 上進行了Verilog HDL設(shè)計，核心部分采用循環(huán)迭代方法實現(xiàn)結(jié)構(gòu)優(yōu)化。 最后，使用Modelsim SE 10.2c 對五種方案的硬件設(shè)計進行功能仿真，并在國產(chǎn)FPGA 器件上進行了分析綜合。 為了較好地衡量運行速度與硬件邏輯資源之間的關(guān)系，引入性能指標(biāo)——面頻比率AFR。 從綜合結(jié)果來看：隨著改進方案中Karatsuba 算法迭代輪數(shù)的增加，所耗費的硬件資源相對穩(wěn)定，乘法運算的速度卻有明顯加快，面頻比率AFR 逐漸減小，性能不斷優(yōu)化。 相較于經(jīng)典的單一多項式乘法運算方法，將1 輪Toom-Cook-4 way 算法與5 輪Karatsuba 算法及schoolbook 算法2×2 全乘結(jié)合起來，具有較為明顯的優(yōu)勢。 后續(xù)打算進一步優(yōu)化提升乘法的速度，將該多項式乘法方法應(yīng)用于后量子Saber 算法具體實現(xiàn)中，并推廣至NIST 第三輪后量子密碼標(biāo)準征集中的其他候選算法，對后量子算法的硬件實現(xiàn)起到加速作用。