參數可選的橢圓曲線加密算法的整體設計
2007-01-01 00:00:00郁濱蔡振國陳韜
計算機應用研究 2007年6期
摘 要：ECC算法的實現比較困難，往往需要通過專門的硬件來加速算法實現。討論了定義在GF(2n)上的參數可選的橢圓曲線密碼體制（ECC）的整體設計，分析了其中的關鍵算法，給出了幾個關鍵算法的設計問題。該方案適合硬件實現。
關鍵詞：橢圓曲線； 有限域； 加密
中圖分類號：TP309.7文獻標志碼：A
文章編號：1001-3695(2007)06-0145-02
ECC的實現有軟件和硬件兩種方式。從安全性角度上考慮，硬件方式實現更具有優越性。有關ECC實現的文獻已有很多。硬件方式實現ECC的報道最早見于文獻[1]，該文獻在GF(2155)上實現了ECC加密算法，加密速度大約為4×104 bps。文獻[2]中給出了基于FPGA實現的ECC處理器，面積約五萬門，加密時數據吞吐率為1.6×104 bps，文獻[3]中基于微代碼形式實現的芯片，在GF(2176)上50MHz時鐘下的點乘運算時間在10 ms以上。
以上文獻報道的ECC設計，絕大多數都是針對某一個固定有限域設計的，但在具體應用場合，有時需要系統參數可選擇。本文廣泛研究了ECC實現中各層次問題，將其作為一個整體綜合考慮，并以實驗和測試結果為依據，提出一套完整的高效的參數可選的ECC加密算法實現方案，該方案具有良好的通用性和靈活性，適合硬件實現。
1 基于ONB的有限域運算法則
在有限域GF(2n) 上進行乘法運算時，多項式基比正規基表示法簡單，但在該域上進行乘方運算時，多項式基比正規基表示法困難［4］。優化正規基（Optimal Normal Base，ONB）是一種特殊的正規基。基于ONB表示法的域元素在執行平方運算時非常高效，僅需對表示元素的矢量進行循環移位。在冪運算方面ONB表示法也比多項式表示法有效得多。在ANSI X.9.62和ANSI X.9.63中強調：有限域中元素以正規基表示時，優先選取存在Ⅱ型優化正規基，并且在選取的域GF(2n)中，當n為合數與n為素數時相比，ECC的安全性會降低，所以本文設計中采用Koblitz曲線，選取n為素數，存在Ⅱ型優化正規基的有限域GF(2191)和GF(2233)，域元素用優化正規基表示。
(1）乘法。
(2）求逆。
正規基表示下的元素求逆通常使用費爾馬定理，但是直接應用需要的乘法次數太多。Itoh［6］指出，完成一次求逆運算所需乘法次數最少為I(m)=[log2(n-1)]+ω(n-1)-1次。其中ω(n-1)表示域GF(2n)中n-1的二進制數表示中1的個數。在此基礎上，Sand ho oh 和Chang Han Kim［7］提出優化求逆算法(Optimal Inverse Algorithm，OIA)。該算法求逆主要用到乘法和平方運算，乘法次數和Itoh的算法相同。有關算法介紹可參閱文獻[7]。本文有限域元素求逆采用的就是OIA算法。
2 ECC實現的硬件結構
從圖1分析，ECC加密算法可分為三個層次，即輸入/輸出控制、有限域運算模塊控制、ECC加/解密運算控制。
有關ECC曲線的參數，基點P的坐標、密鑰通過外部存儲器接口由32位總線輸入到存儲器中，在I/O狀態機的控制下，由串并轉換模塊將有關數據輸入到內部寄存器組中。寄存器組由233位的存儲單元組成，主要存放運算過程中所需的中間變量和運算所需的系統參數。
圖1 ECC加密算法結構圖
有限域運算模塊主要負責有限域的各種算術運算，通過狀態機控制，完成域GF（2n）中的有限域加法、乘法、平方和求逆運算。
運算控制級中的點乘狀態機通過對有限域運算模塊的合理調用，完成橢圓曲線上P=Q和P≠Q的加法運算，快速得到KP的結果，KP的計算也是整個ECC設計的核心。加/解密控制則是利用KP的值進行數據加/解密運算。
本文設計的支持多域寬的ECC加密系統模塊如圖2所示。域寬控制單元是選擇域寬的，此處只選擇了兩個域寬。ECC加/解密控制單元完成兩個域寬下的ECC加/解密運算。設計中采用了兩個寄存組，分別存儲GF(2191)和GF(2233)的外部輸入參數。當數據總線輸入191bits下的參數時，選擇域寬191bits下的ECC加密；數據總線輸入233bits下的參數時，選擇域寬191bits下的ECC加密。本設計可以進行擴展，只要增加寄存器組，對域寬控制單元作簡單修改，便可以完成更多域寬下的ECC運算。
圖2 支持雙域寬的ECC加密系統模塊圖
2.1 點乘單元設計
ECC算法的核心是求點乘KP的運算。點乘運算層是通過對點加和點倍進行調度來實現。求點乘的算法主要有二進制算法、m進制方法、符號數字表示法、滑動窗口法等。本文實現ECC時采用的點乘法算法為冗余編碼的二進制方法［8］，其理由如下：
（1）該方法簡單，易于硬件實現；
（2）M進制方法和滑動窗口方法都需要預計算，需要較大的存儲空間，需要資源較大，并且編程復雜，不利于硬件實現。
其算法描述如下：
圖3為KP運算結構圖。在它的組成部分中，有限域運算模塊包括乘法運算器、求逆運算器、加法及平方運算器，負責完成有限域上的各種算術運算功能。移位寄存器為線性反饋寄存器，其中保存經過冗余編碼后的私鑰值K。點加和點倍運算為兩個獨立的單元，分別通過狀態機對有限域運算模塊進行調度，完成點加與點倍運算。點乘狀態控制器根據移位寄存器中存儲的數值，選擇進行點加或是點倍運算，完成點乘KP的計算。
2.2 有限域運算單元設計
圖4是支持多域寬的乘法器結構。其主要單元功能如下：
(1)域寬轉換單元根據外部輸入參數的不同，協同乘法器控制單元完成不同域寬下的乘法運算。
(2)與或陣列1與2分別對應GF(2191)和GF(2233)的與或陣列表。運算時，根據SEL值選擇不同的與或陣列完成不同域寬的乘法運算。
(3)輸出控制單元對兩個與或陣列分別計算出的ck值進行拼接，得到最后的乘法結果。設計中寄存器的寬度為233位，當輸入191位乘數時233位的寄存器的前191位保存運算結果。這樣做的好處是不需要另外用寄存器來存儲191位乘法時的運算值，可以節約面積。
圖4 支持多域寬的乘法器結構
基于有限域乘法模塊，本文設計了一個逆控制器：具有求逆和乘法的雙重功能。
基于串并結合結構的乘法模塊，本文設計了一個逆控制器：具有求逆和乘法的雙重功能。其單元模塊如圖5所示，它的主要組成部分是有限域逆控制器、模式選擇器、求逆狀態機和有限域乘法模塊。
圖5 求逆控制單元結構圖
（1）模式選擇信號CompType是由選擇信號發生器產生的，主要控制運算的類型：乘法還是求逆。進行乘法運算時，模式選擇信號低有效，對輸入A和輸入B執行乘法過程，輸出A×B；進行求逆運算時，逆使能信號(Invstr)高有效，模式選擇信號保持為高，對輸入A執行求逆運算，輸出A的逆運算。在這種情況下，輸入B沒有作用。運算結果存儲在有限域乘法模塊的寄存器中。
（2）控制器的主要功能是接收輸入信號，按照求逆算法產生控制序列，控制乘法器執行操作。當運算完成時，由乘法模塊中的寄存器輸出結果，并置Finish為高電平。
（3）有限域乘法模塊為串并結合結構的乘法器，完成乘法功能。
（4）求逆狀態機根據OIA算法協同控制器對求逆運算進行控制。
加法器：正規基下的加法器十分簡單，有限域任意兩元素相加，結果是各自矢量表達位的逐位異或（XOR）。做加法運算時，輸入/輸出寄存器均選擇并行工作模式，整個運算只需要一個時鐘周期。
平方器：正規基下的元素平方是元素矢量表達式循環移位，完成整個運算也只需要一個時鐘周期，這是選擇正規基的突出優點。
4 結束語
本文通過對ECC算法進行研究，從點乘與群運算層的設計出發，給出了一種參數可選的ECC加密算法的FPGA實現方案。在調試階段，本設計選擇了存在Ⅱ型優化正規基的191 bits和233 bits有限域為例，采用VHDL語言進行描述，Altera公司的QuartusⅡ開發軟件作為編譯及綜合工具。設計原形在Altera Cyclone的 EP1C12Q240C8器件上實現并進行了驗證，共占用17 733個邏輯單元，最高時鐘頻率可達73.82 MHz。在50 MHz的時鐘頻率下，F2191上，平均一次橢圓曲線點乘運算時間為14.365 ms；F2233上，平均一次橢圓曲線點乘運算時間為19.565 ms，本文的設計突破了單一結構、參數固定的ECC專用芯片形式，使之能滿足不同用戶的需要。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
