高 照 王慶年 樊 榮

（中國(guó)船舶集團(tuán)有限公司第722研究所 武漢 430205）

1 引言

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

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

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

2 背景知識(shí)

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

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

對(duì)于任意的m，正規(guī)基總是存在的。高斯正規(guī)基是一種特殊類別的正規(guī)基，因其乘法運(yùn)算更簡(jiǎn)單、更有效，又可稱為低復(fù)雜度正規(guī)基。高斯正規(guī)基的特征值T是個(gè)衡量該基乘法復(fù)雜度的正整數(shù)。除了能被8 整除的m，二進(jìn)制域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 是素?cái)?shù)，且下面兩個(gè)條件之一成立：

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

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

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

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

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

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

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

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

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

1）T1(e)=e。

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

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

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

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

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

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

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

將式（6）、（7）兩個(gè)m項(xiàng)多項(xiàng)式相乘，得到一個(gè)2m-1項(xiàng)的多項(xiàng)式：

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

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

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

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

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

圖2 m=131約減矩陣

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

對(duì)于多項(xiàng)式A=a1x+a2x2+…+amxm，將其分為

由此，多項(xiàng)式A與B相乘等于

其中AL和BL為2k項(xiàng)多項(xiàng)式。然后再對(duì)AL和BL進(jìn)行半分，即

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

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

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

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

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

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

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

5 改進(jìn)后的性能優(yōu)勢(shì)

改進(jìn)后整個(gè)計(jì)算過程涉及到兩次排序（正規(guī)基與重序正規(guī)基）、兩次矩陣乘法和一次m項(xiàng)的多項(xiàng)式相乘。其中排序時(shí)，因?yàn)閮煞N基（正規(guī)基和重序正規(guī)基）之間是一一對(duì)應(yīng)關(guān)系，所以不占用任何資源。Tm變換所需要的XOR 運(yùn)算為而多項(xiàng)式計(jì)算需要的運(yùn)算XOR 和AND 為M(m)，取決于所采用的方法。約減則因?yàn)槲覀儗⒛孀儞Q和約減部分合并后省去。所以整個(gè)算法過程所需要的XOR 和AND 運(yùn)算約為，相比于原算法節(jié)省了m。

多項(xiàng)式計(jì)算上使用改進(jìn)后的karatsuba 算法，改進(jìn)后需要2d(2k+1)-1 個(gè)XOR 和2d2k個(gè)AND，故整個(gè)計(jì)算過程需要的XOR 和AND 運(yùn)算為

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

表1 不同算法性能比較

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

6 實(shí)現(xiàn)與測(cè)試

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

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

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

圖3 233bit乘法器RTL原理圖

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

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

7 結(jié)語

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