基于GF(2m)域上Ⅱ型最優正規基的模乘算法及實現?

高 照 王慶年 樊 榮

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

1 引言

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

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

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

2 背景知識

2.1 Ⅱ型最優正規基和重序正規基［1］

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

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

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

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

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

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

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

2.2 正規基到Ⅱ型多項式的轉換

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

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

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

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

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

1）T1(e)=e。

2）當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變換，就能使得重序正規基變換到Ⅱ型多項式基

3 基于基轉換的正規基模乘算法

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

其中Tm為m階轉換矩陣，可由T變換得到。

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

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

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

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

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

4 基于基轉換的模乘算法的改進

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

圖1 m=131的轉換矩陣

圖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繼續半分，直到分為小于等于6項時停止。

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

1）通過式（1）將a,b的正規基表示轉換為重序正規基。

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由重序正規基排回正規基。

5 改進后的性能優勢

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

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

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

表1 不同算法性能比較

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

6 實現與測試

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

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

表2 綜合后LUTs數量對比

圖3 233bit乘法器RTL原理圖

圖4 233bit乘法器仿真結果

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

7 結語

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