雙有限域模乘和模逆算法及其硬件實現

陳光化 朱景明 劉 名 曾為民

①(上海大學微電子中心 上海 200072)

②(上海市電站自動化技術重點實驗室 上海 200072)

1 引言

橢圓曲線密碼體系(Elliptic Curve Cryptography，ECC)與傳統的RSA密碼體系相比具有加密強度高，密鑰尺寸短，占用帶寬少等諸多優點[1]，因此受到越來越來越多的關注。ECC算法根據橢圓曲線選取的有限域不同又可分為基于素數域GF(P)和二進制域GF(2m)兩種。無論在哪個有限域，模乘和模逆運算都是作為其中的核心運算，同時也是相對復雜的運算操作，因此如何快速高效實現這兩個運算對于ECC的應用意義重大。

適合素數域或者二進制域的模乘和模逆算法有很多，但大多數只是在其中的一個有限域上實現。然而隨著ECC研究的不斷深入及其應用的日益廣泛，對于雙有限域模乘和模逆算法的研究正在成為一種趨勢和熱點，近年來有些文獻提出能夠同時支持兩種有限域的模乘算法[2,3]和模逆算法[4]，但是組合在一起的算法在運算速度上和單獨的算法相比并不具備優勢。由于在雙有限域上設計算法面臨著如下的難點：首先是素數域和二進制域的表現形式不同；其次是素數域和二進制域的加減法運算不同；再者素數域和二進制域的取模或者約減運算也不同。因此一個優秀的雙有限域算法不僅要能夠解決以上難題，完成兩種有限域算法的有效合并，還應該具備良好的單個有限域的算法性能，Wang等人[4]在擴展Euclidean算法的基礎上提出的一種能夠同時支持兩種有限域的模逆算法，比較好地實現了這一目標。Ma等人[5]針對擴展Euclidean算法中存在的大整數比較問題，提出了一種可以避免大整數比較的算法結構；Yan等人[6]則針對其每次迭代中只能右移一位的情況提出了一種具有更高移位效率的改進算法。

本文在Blakley算法基礎上提出一種改進的radix-4快速雙有限域模乘算法；在擴展Euclidean求逆算法的基礎上提出一種能夠同時支持GF(P)和GF(2m)兩種有限域運算的模逆算法。而且，針對這兩種算法特點設計出一種能夠同時支持雙有限域上模乘和模逆操作的統一硬件結構。在本文第2節介紹了radix-4快速雙有限域模乘算法；第3節提出了基于擴展Euclidean算法的雙有限域模逆算法；第4節設計了一種能夠同時支持雙有限域模乘和模逆運算的統一硬件結構；第5節給出了實現硬件電路的仿真以及性能比較；最后部分總結了全文。

2 雙有限域模乘算法

由于Blakley算法中只有簡單的加減和移位操作，并且可以直接輸出最終結果，非常易于硬件實現，更重要的一點是該算法在兩種有限域上的運算步驟非常相似，比較適合用來設計雙有限域統一算法。但是該算法中存在普通加減法的進位傳播延時和大數比較問題，一種改進方法是采用CSA加法器代替CPA加法器來消除進位傳播延時，但同時由于要采用查找表技術會使得設計面積大幅增加，并且與模數P以及操作數相關的預處理也限制了其靈活性[7]；還有一種是采用冗余數法，通過對操作數進行Booth編碼以減少迭代次數并利用冗余加法代替普通加法來消除進位傳播延時，但同時冗余數和二進制數之間的轉換代價會隨著操作數位長的增加而增大。

本文在該算法基礎上采用Booth算法[8]對乘數進行編碼，按照從最低有效位到最高有效位的順序每次處理操作數的兩位，直接將原算法中循環迭代次數減少一半，并且減少了中間結果的累加次數；為了避免原算法每次約減前的大整數比較操作，本文采用一種符號估計技術[9]來提高約減的效率。只需要依據中間結果的最高有效位和次高有效位的值就可以進行下一步的約減操作，不僅提高了算法的運算速度，也簡化了算法在實現過程中控制單元的設計；由于該算法在兩種有限域上的運算步驟基本相同，因此只需將素數域的算法移植到二進制上即可

完成雙有限域模乘算法的設計，其偽代碼如下：

算法1 雙有限域模乘算法見表1。

表1 雙有限域模乘算法

在步驟2.1，2.4，2.5采用符號估計技術來避免大數比較從而直接完成與模數“P.”有關的加、減或者異或操作，如表2所示。其中“n+2”，“n+1”分別表示相應操作數的第n+2位和第n+1位的數值，“field”表示域選擇變量，“field”為0表示二進制域，為1表示素數域。

表2 采用符號估計技術的計算規則

3 雙有限域模逆算法

擴展Euclidean算法在素數域和二進制域上都用簡單的加法、減法(異或)和移位操作代替了復雜耗時的乘法和除法運算，非常適合硬件實現，更重要的是其在兩種域的運算步驟上有很多相似之處，很容易將兩種域上的算法統一起來，王健[10]基于該算法提出了一種能夠同時支持雙有限域的模逆算法。然而在其算法的每次迭代中都存在大整數的比較操作，不僅占用硬件資源，而且浪費時鐘周期；其次，當操作數中出現多個連續的“0”時，該算法每次迭代中只能右移一位的操作就顯得不夠高效。為此，本文在擴展Euclidean算法的基礎上提出了一種能夠同時支持兩種有限域的改進模逆算法。該算法用單分支結構代替原算法中雙分支結構，使其在每次迭代中只處理某個固定操作數，從而避免了大整數比較操作；并且當操作數中有連續多個“0”時，用同時右移兩位甚至三位的操作代替原先每次迭代只能右移一位來提高算法的運算效率，改進后的算法偽代碼如下所示。

算法2 雙有限域模逆算法見表3。

表3 雙有限域模逆算法

在上述算法的偽代碼中，當“field”為1時表示素數域上的求逆操作，為0時表示二進制域上的求逆運算。符號“⊕”表示異或操作，步驟3中“g2←(g2/4) mod p”在不同的條件下要進行相應的操作，“g2←(g2/2) mod p”操作與上述情況類似，具體操作情況如表4所示，u1和g1_1只是用來對算法進行解釋，在實際硬件實現過程中是不需要的。

表4 步驟3中的各種可能操作

4 硬件實現結構

為了實現在GF(P)和GF(2m)兩個有限域上硬件單元結構的統一，本文采用了一種被稱作雙有限域加/減法器的單元，其結構如圖1所示[2]。將n個雙有限域加/減法器單元進行級聯就構成了一個完整的n位的雙有限域加/減法器，通過這種單元搭建設計中的所有加/減法器，可以實現在兩種有限域內相對統一的硬件結構，將額外的硬件開銷降低至最小。

4.1 模乘單元設計

模乘算法完成的操作主要包括部分積的累加、中間結果的取模約減以及對輸入操作數的Booth編碼，其結構如圖2所示。主要由3個部分組成，用來存放操作數、中間結果和最終結果的寄存器堆，用來執行加減法和編碼操作的計算單元(1個Booth編碼器和2個雙有限域加/減法器)，用來控制整個模乘運算流程的控制單元。

圖1 雙有限域加/減法器單元結構

模乘運算開始前，乘數A，被乘數B以及模數P分別寫入到寄存器REG_U，REG_V，REG_P中，并將寄存器REG_2V和REG_R清零。BOOTH CODER編碼器在每次循環中按照從最低有效位到最高有效位的順序處理乘數的兩位，對乘數進行重編碼操作；在每次迭代中被乘數都要完成兩次移位操作，每次左移一位，兩次移位操作完成后都是調用DFAS_1對移位結果進行符號估計約減操作；而DFAS_2主要是完成部分積的累加操作以及對部分積的符號估計約減操作。圖中的REG_U，REG_V，REG_2V，REG_P，REG_R均為256位，而一般情況下運算時間與數據處理位寬W的取值成反比，W的取值越大，運算越快，但是相應的芯片面積也會越大，本文綜合考慮時間和面積確定本單元中的W=32。

4.2 模逆單元設計

模逆單元也是主要由3個部分組成：一個是用來存儲操作數以及中間和最終結果寄存器堆，包括兩個雙有限域加/減法器計算單元，控制整個模逆的計算流程控制單元。雙有限域模逆單元的數據通路如圖3所示。

圖3 模逆單元的數據通路

模逆運算初始化時，寄存器REG_U，REG_V，REG_G1，REG_G2，REG_P，REG_P3分別被賦值操作數A，模數P，0，1，模數P，3P (模數P的3倍)。雙有限域加/減法器DFAS_1主要是用來完成寄存器REG_U和寄存器REG_V內容的減法操作(或者對應二進制域上的異或操作)和REG_V內容的取反操作；而DFAS_2主要用來完成寄存器REG_G1，REG_G2內容的減法操作(或者對應二進制域上的異或操作)和寄存器REG_G2內容的取模運算。圖中的REG_U，REG_V，REG_G1，REG_G2，REG_P，REG_P3均為256位寄存器，綜合考慮時間和面積因素我們將本單元的數據處理寬度W也設定為32位，最終的運算結果將存放在REG_G1中。

4.3 模乘和模逆單元統一架構設計

在采用上述的雙有限域加/減法器后，模乘模塊的計算單元主要包括兩個雙有限域加/減法器和一個booth編碼器，而模逆模塊的計算單元主要就是兩個雙有限域加/減法器，因此可以將這兩個計算單元的硬件資源復用；另外，兩個模塊用來存放操作數以及中間結果和最終結果的寄存器堆也可以復用，因此模乘和模逆單元的統一架構也可以主要分為與模逆單元相似的3個部分，只是控制單元較原來要復雜一些，如圖4所示。圖中“MODE”為一個2位二進制數的域選擇變量，“00”，“01”，“10”，“11”分別表示電路在進行二進制模乘運算、二進制域模逆運算、素數域模乘運算、素數域模逆運算；MI_ALU表示該統一硬件電路的計算單元，包括兩個雙有限域加/減法器和一個Booth編碼器；當電路進行模乘操作初始化時，操作數“X”，“Y”，“P”分別寫到“REG_U”，“REG_V”，“REG_P”中，而在進行模逆操作初始化時，除了注意將輸入“Y”設定為1寫入“REG_G2”中，其它如圖3中的操作基本相同。

圖4 模乘和模逆單元的統一硬件框圖

5 仿真與綜合結果

二進制域上選用既約多項式P(Z)=Z233+Z74+1，而在素數域上選用模數P=2224-296+1。模乘和模逆操作在素數域上的仿真波形如圖5和圖6所示，二進制域上的仿真波形也完全正確。

素數有限域上的模乘操作，輸入的操作數a=0x00000000_53f2fdee_00c4bb9b_d7f20a19_

2e8f0608 _35af165b_d919ae51_2365fc6d，b=0x00000000_4389169d_0d4330b1_07c1f8c9_ f357 8a75_234bd366_f4fa0999_c5972c0a，仿真結果如圖5所示，與標準結果r=0x0000013e _B11d a482_21ee4ada_d89f1cfc_dd853c0e_ b49 9a1ec_6b bcb421_ c99b8971相一致。

圖5 GF(P)上模乘運算仿真波形

圖6 GF(P)上模逆運算仿真波形

素數有限域上的模逆操作，輸入的操作數a=0x00000000_1907f524_d5db74fc_8028d812_c7c5 63c5_d11ffd04_aae42961_aed6c8df，仿真結果如圖6所示，與標準結果b=0x00000000_ e8dadd0f_ab1eeb9c_78d82233_1fe94388_8846f58f_90806ec7_f7fd7b7a相一致。

本設計由Verilog HDL語言實現并采用Synopsys公司的Design Compiler進行綜合，選用的是SMIC 0.18 μm的工藝庫。DC綜合后的結果表明：256位的模乘和模逆統一硬件電路與其它同類型的設計相比較在電路面積沒有增加的情況下，模乘運算速度提高68%，而模逆運算的速度也提高了17.4%。具體信息參見表5。

表5 電路性能比較

6 結束語

本文對雙有限域上橢圓曲線密碼體系的兩個核心運算的實現算法進行了研究。在Blakley算法的基礎上提出一種改進的Radix-4快速雙有限域模乘算法，該算法采用Booth算法對乘數進行編碼以減少迭代次數，并采用符號估計技術避免原算法中大整數比較操作；在擴展Euclidean求逆算法的基礎上提出一種雙有限域高效模逆算法，該算法不僅避免了原算法中的大整數比較而且提高了操作數的移位效率。然后針對這兩個算法特點設計出一種能夠同時完成雙有限域上模乘和模逆操作的統一硬件結構。實現結果表明：256位的統一硬件電路與其它同類型設計相比較，電路面積沒有增加，而運算速度顯著提高。

[1] Hankerson D, Menezes A, and Vanstone S. Guide to Elliptic Curve Cryptography. New York: Springer Verlag New York Inc, 2004: 25-147.

[2] Savas E and Koc C K. A scalable and unified multiplier architecture for finite fields GF(P) and GF(2m).Cryptographic Hardware and Embedded Systems(CHES)2000, Worcester, MA, USA, Augst 17-18, 2000: 277-292.

[3] Chiou C W, Lee C Y, and Lin J M. Unified dual-field multiplier in GF(P) and GF(2k). Information Security, 2009,3(2): 45-52.

[4] Wang Jian and Jiang An-ping. A high-speed dual field arithmetic unit and hardware implementation, ASICON'07,Guilin, China, Oct. 22-25, 2007: 213-216.

[5] Ma Shi-wei, Hao Yuan-ling, and Pan Zhong-qiao. Fast implementation for modular inversion and scalar multiplication in the elliptic curve cryptography, IITA '08,Beijing, China, Dec. 20-22, 2008: 488-492.

[6] Yan Xiao-dong and Li Shu-guo. Modified modular inversion algorithm for VLSI implementation, ASICON'07, Guilin,China, Oct. 22-25, 2007: 90-93.

[7] Shieh M D, Chen J H, and Lin W C. A new algorithm for high-speed modular multiplication design. Circuits and Systems, 2009, 56(9): 2009-2019.

[8] Hussin R, Shakaff A Y M, and Idris N. An efficient modified Booth multiplier architecture electronic design, ICED'08,Beijing, China, Dec. 1-3, 2008: 1-4.

[9] Nibouche O, Nibouche M, and Bouridane A. New iterative algorithm for modular multiplication, ICECS 2001, St.Julians. Malta, Sept. 2-5, 2001: 879-882.

[10] 王健. 橢圓曲線加密體制的雙有限域算法及其硬件實現. [博士論文], 北京大學, 2008.Wang Jian. A dual-field algorithm for elliptic curve cryptosystem and its hardware implementation. [Ph.D.dissertation], Peking University, 2008.