基于GF(2m)域上Ⅱ型最優(yōu)正規(guī)基的模乘算法及實現(xiàn)?

高 照 王慶年 樊 榮

（中國船舶集團有限公司第722研究所 武漢 430205）

1 引言

橢圓曲線密碼體制（ECC）自出現(xiàn)以來，由于其安全性更高、計算量更小等特點，引起了人們的關(guān)注與研究。在橢圓曲線密碼體系的應(yīng)用中，通常采用基于素數(shù)域或伽羅華域（二進制域）上的橢圓曲線點群，特別是GF(2m)域上的算法，易于硬件實現(xiàn)。

在有限域的運算中，乘法是極其重要的一部分。二進制域上最普遍使用兩種基：多項式基和正規(guī)基。其中正規(guī)基上的乘法較為緩慢且代價為多項式基的兩倍以上。但在正規(guī)基上的平方運算只需要進行移位，遠(yuǎn)遠(yuǎn)優(yōu)于多項式上的平方運算。因此正規(guī)基一般只在某些特殊情況下使用：硬件面積要求小，平方運算多或乘法運算較少。

本文主要研究二進制域上的正規(guī)基模乘運算，通過一種變化，使得正規(guī)基能夠使用多項式基的方法進行乘法運算，并在FPGA 中實現(xiàn)。結(jié)果表明，此方法比起傳統(tǒng)正規(guī)基算法效率提高且資源占用更少。

2 背景知識

2.1 Ⅱ型最優(yōu)正規(guī)基和重序正規(guī)基［1］

假設(shè)β是GF(2m)上m次不可約多項式的原根，如果集合中的元素互相線性無關(guān)，則集合N是GF(2m) 上的一組正規(guī)基。對于?a?GF(2m)有

對于任意的m，正規(guī)基總是存在的。高斯正規(guī)基是一種特殊類別的正規(guī)基，因其乘法運算更簡單、更有效，又可稱為低復(fù)雜度正規(guī)基。高斯正規(guī)基的特征值T是個衡量該基乘法復(fù)雜度的正整數(shù)。除了能被8 整除的m，二進制域GF(2m)中均存在高斯正規(guī)基。特征值T為1和2的高斯正規(guī)基被稱為最優(yōu)正規(guī)基，分別被稱為I 型最優(yōu)正規(guī)基和II型最優(yōu)正規(guī)基。

兩種正規(guī)基的差別在于定義中所采用的數(shù)學(xué)公式不同。但出于安全角度的考慮，Ⅰ型最優(yōu)正規(guī)基已經(jīng)被許多安全標(biāo)準(zhǔn)排除在外，如NIST ECDSA和ANSI X9.62。而Ⅱ型最優(yōu)正規(guī)基由于其更好的安全性，被廣泛應(yīng)用推廣及使用在密碼算法應(yīng)用中。判斷GF(2m)中是否存在II 型最優(yōu)正規(guī)基可以用如下定理［2］：

定理1 如果m不能被8 整除，且2m+1 是素數(shù)，且下面兩個條件之一成立：

1）2是模2m+1的原根；

2）2m+1 是模4 為3 的一個素數(shù)，并且2 模2m+1的次數(shù)為m。

則β=γ+γ-1可生成一組GF(2m)上的Ⅱ型最優(yōu)正規(guī)基，其中γ為2m+1次本原單位根。

2.2 正規(guī)基到Ⅱ型多項式的轉(zhuǎn)換

文獻［5］和文獻［6］研究了多項式基與正規(guī)基之間的聯(lián)系，以及它在實現(xiàn)正規(guī)基高性能乘法中的應(yīng)用。文獻［6］中描述了如何利用高斯生成正規(guī)基進行乘法，并進一步將乘法簡化為多項式乘法。文獻［7～8］則在前面的基礎(chǔ)上，提出了一種將正規(guī)基通過線性變換轉(zhuǎn)到多項式基后相乘，再將乘積通過線性變換的逆過程轉(zhuǎn)變回正規(guī)基的算法。文獻［8］將這種新的多項式基稱為Ⅱ型多項式基。

以GF(25) 為例：重序正規(guī)基為={γ+γ-1,γ2+γ-2,…,γ5+γ-5}，其中：

文獻［8］中將P稱為Ⅱ型多項式基，文獻［7］中證明了可以利用線性變換使得轉(zhuǎn)變?yōu)镻，并且P上可以使用任何適用于普通多項式的乘法算法。但文獻［7］中先將擴展到={1,γ+γ-1,γ2+γ-2,…,γm+γ-m}，然后變換到P'={1,γ+γ-1,(γ+γ-1)2,…,(γ+γ-1)m}。這種擴展使得原本的m項的乘法變?yōu)閙+1項。

文獻［8］在前者的基礎(chǔ)上提出了改進，給出了如下變換：

向量e?，ei為e中第i個元素，i?{1,2,…,k}，e=(e1,e2,…ek)。當(dāng)i不在{1,2,…,k}范圍內(nèi)時，ei=0。對于每個k≥1 定義一個轉(zhuǎn)換函數(shù)，規(guī)則如下：

1）T1(e)=e。

2）當(dāng)k≥2 時，j為在{1,2,…,k-1} 中最大的2 的冪。將向量e分為f和g，f=(e1,e2,…ej)，g=(ej+1,ej+2,…ek)，得到一個新的向量?，?i=fi+gj-i。

通過T變換，就能使得重序正規(guī)基變換到Ⅱ型多項式基

3 基于基轉(zhuǎn)換的正規(guī)基模乘算法

設(shè)GF(2m)中的重序正規(guī)基={γ+γ-1,γ2+γ-2,…,γm+γ-m} 和Ⅱ型多項式基P={γ+γ-1,(γ+γ-1)2,…,(γ+γ-1)5}。兩者間的關(guān)系為

其中Tm為m階轉(zhuǎn)換矩陣，可由T變換得到。

對于任意a,b?GF(2m)及其乘積c?GF(2m)，以排序正規(guī)基表示：

令z=γ+γ-1，結(jié)合式（3～5）可得a,b在多項式下的表示為a',b'：

將式（6）、（7）兩個m項多項式相乘，得到一個2m-1項的多項式：

將(p2m,…,p3,p2) 補充為(p2m,…,p3,p2,0)，然后通過逆變換得到c'：

由此便得到了a×b的結(jié)果c=(cm,…,c2,c1)。

4 基于基轉(zhuǎn)換的模乘算法的改進

T變換生成的轉(zhuǎn)換矩陣Tm是一個上三角矩陣，如圖1所示，因此逆變換對應(yīng)的矩陣也是一個上三角陣。約減的過程也可以看成是向量乘上一個約減矩陣R，約減矩陣如圖2所示。

圖1 m=131的轉(zhuǎn)換矩陣

圖2 m=131約減矩陣

另外在多項式乘法上，選擇使用改進的karatsuba 算法。原karatsuba 算法是將m項多項式擴展為m+1 項或縮短為m-1 項后進行二分，改進思路則是將m分解為m=2k+d，然后再對2k進行二分：

對于多項式A=a1x+a2x2+…+amxm，將其分為

由此，多項式A與B相乘等于

其中AL和BL為2k項多項式。然后再對AL和BL進行半分，即

其中n=2k，對ALH和ALL繼續(xù)半分，直到分為小于等于6項時停止。

將改進后karatsuba 算法同改進后的轉(zhuǎn)換算法合并，得到的過程如下：

1）通過式（1）將a,b的正規(guī)基表示轉(zhuǎn)換為重序正規(guī)基。

2）計算a'=(am,…,a2,a1)×Tm和b'=(bm,…,b2,b1)×Tm。

3）由a',b'算出多項式p=p2mz2m+…+p3z3+p2z2。

4）計 算c=(p2m,…,p3,p2,0)×TR=(cm,…,c2,c1)。

5）利用式（1）將c由重序正規(guī)基排回正規(guī)基。

5 改進后的性能優(yōu)勢

改進后整個計算過程涉及到兩次排序（正規(guī)基與重序正規(guī)基）、兩次矩陣乘法和一次m項的多項式相乘。其中排序時，因為兩種基（正規(guī)基和重序正規(guī)基）之間是一一對應(yīng)關(guān)系，所以不占用任何資源。Tm變換所需要的XOR 運算為而多項式計算需要的運算XOR 和AND 為M(m)，取決于所采用的方法。約減則因為我們將逆變換和約減部分合并后省去。所以整個算法過程所需要的XOR 和AND 運算約為，相比于原算法節(jié)省了m。

多項式計算上使用改進后的karatsuba 算法，改進后需要2d(2k+1)-1 個XOR 和2d2k個AND，故整個計算過程需要的XOR 和AND 運算為

常用的高斯正規(guī)基算法還有IEEE 規(guī)定的標(biāo)準(zhǔn)算法［9］、Massey-Omura［10～12］、Τeoplize 矩陣［13～14］以及ΤMVP［15］等，所需的算法復(fù)雜度如表1所示。

表1 不同算法性能比較

本文設(shè)計上可以看成是一個多項式乘法加上兩次基轉(zhuǎn)換，因此可以看到，相比于其他傳統(tǒng)的正規(guī)基乘法，即使多項式乘法上采用直接相乘，即M(m)=2m2，本文的設(shè)計在復(fù)雜度上也是更低的。

6 實現(xiàn)與測試

為了驗證本文改進算法的正確性并對其資源開銷及其運算性能進行評估，我們選擇在GF(2131)和GF(2233) 兩條曲線上進行實現(xiàn)。硬件選型為Xilinx Artix-7 FPGA（XC7A50T-1FTG256C），進行實際驗證與測試。

圖3、4 分別為GF(2233)上實現(xiàn)的乘法器的RTL原理圖以及仿真結(jié)果。另外，我們以100MHz時鐘頻率進行綜合，并將結(jié)果與將正規(guī)基基轉(zhuǎn)換到普通多項式基后進行模乘，再將結(jié)果轉(zhuǎn)回正規(guī)基的方法進行對比。結(jié)果如表2所示，由于從重序正規(guī)基到Ⅱ型多項式的變換是線性的，與正規(guī)基到普通多項式基的轉(zhuǎn)換矩陣不同，因此LUTs的數(shù)量減少了近40%。

表2 綜合后LUTs數(shù)量對比

圖3 233bit乘法器RTL原理圖

圖4 233bit乘法器仿真結(jié)果

此外，文獻［15］中實現(xiàn)了m=255 的乘法器，LUTs數(shù)量為19997。盡管我們只在m=233 上實現(xiàn)乘法器，但與其支持位寬較為接近，且LUTs數(shù)量僅僅是其60%。因此我們估計在位寬相同情況下，本文所設(shè)計的乘法器將優(yōu)于前者。

7 結(jié)語

本文介紹了最優(yōu)正規(guī)基、排序正規(guī)基、Ⅱ型多項式等相關(guān)概念，在現(xiàn)有算法基礎(chǔ)進行改進，提出了新的Ⅱ型最優(yōu)正規(guī)基乘法方案，并在GF(2131)和GF(2233)兩條曲線上進行了實現(xiàn)。從算法復(fù)雜度和綜合后的結(jié)果來看，本文設(shè)計相比于其他正規(guī)基乘法算法實現(xiàn)了較大的提升。