參數(shù)可選的橢圓曲線加密算法的整體設(shè)計(jì)

摘 要：ECC算法的實(shí)現(xiàn)比較困難，往往需要通過(guò)專門的硬件來(lái)加速算法實(shí)現(xiàn)。討論了定義在GF(2n)上的參數(shù)可選的橢圓曲線密碼體制（ECC）的整體設(shè)計(jì)，分析了其中的關(guān)鍵算法，給出了幾個(gè)關(guān)鍵算法的設(shè)計(jì)問(wèn)題。該方案適合硬件實(shí)現(xiàn)。

關(guān)鍵詞：橢圓曲線； 有限域； 加密

中圖分類號(hào)：TP309.7文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)06-0145-02

ECC的實(shí)現(xiàn)有軟件和硬件兩種方式。從安全性角度上考慮，硬件方式實(shí)現(xiàn)更具有優(yōu)越性。有關(guān)ECC實(shí)現(xiàn)的文獻(xiàn)已有很多。硬件方式實(shí)現(xiàn)ECC的報(bào)道最早見(jiàn)于文獻(xiàn)[1]，該文獻(xiàn)在GF(2155)上實(shí)現(xiàn)了ECC加密算法，加密速度大約為4×104 bps。文獻(xiàn)[2]中給出了基于FPGA實(shí)現(xiàn)的ECC處理器，面積約五萬(wàn)門，加密時(shí)數(shù)據(jù)吞吐率為1.6×104 bps，文獻(xiàn)[3]中基于微代碼形式實(shí)現(xiàn)的芯片，在GF(2176)上50MHz時(shí)鐘下的點(diǎn)乘運(yùn)算時(shí)間在10 ms以上。

以上文獻(xiàn)報(bào)道的ECC設(shè)計(jì)，絕大多數(shù)都是針對(duì)某一個(gè)固定有限域設(shè)計(jì)的，但在具體應(yīng)用場(chǎng)合，有時(shí)需要系統(tǒng)參數(shù)可選擇。本文廣泛研究了ECC實(shí)現(xiàn)中各層次問(wèn)題，將其作為一個(gè)整體綜合考慮，并以實(shí)驗(yàn)和測(cè)試結(jié)果為依據(jù)，提出一套完整的高效的參數(shù)可選的ECC加密算法實(shí)現(xiàn)方案，該方案具有良好的通用性和靈活性，適合硬件實(shí)現(xiàn)。

1 基于ONB的有限域運(yùn)算法則

在有限域GF(2n) 上進(jìn)行乘法運(yùn)算時(shí)，多項(xiàng)式基比正規(guī)基表示法簡(jiǎn)單，但在該域上進(jìn)行乘方運(yùn)算時(shí)，多項(xiàng)式基比正規(guī)基表示法困難［4］。優(yōu)化正規(guī)基（Optimal Normal Base，ONB）是一種特殊的正規(guī)基?；贠NB表示法的域元素在執(zhí)行平方運(yùn)算時(shí)非常高效，僅需對(duì)表示元素的矢量進(jìn)行循環(huán)移位。在冪運(yùn)算方面ONB表示法也比多項(xiàng)式表示法有效得多。在ANSI X.9.62和ANSI X.9.63中強(qiáng)調(diào)：有限域中元素以正規(guī)基表示時(shí)，優(yōu)先選取存在Ⅱ型優(yōu)化正規(guī)基，并且在選取的域GF(2n)中，當(dāng)n為合數(shù)與n為素?cái)?shù)時(shí)相比，ECC的安全性會(huì)降低，所以本文設(shè)計(jì)中采用Koblitz曲線，選取n為素?cái)?shù)，存在Ⅱ型優(yōu)化正規(guī)基的有限域GF(2191)和GF(2233)，域元素用優(yōu)化正規(guī)基表示。

(1）乘法。

(2）求逆。

正規(guī)基表示下的元素求逆通常使用費(fèi)爾馬定理，但是直接應(yīng)用需要的乘法次數(shù)太多。Itoh［6］指出，完成一次求逆運(yùn)算所需乘法次數(shù)最少為I(xiàn)(m)=[log2(n-1)]+ω(n-1)-1次。其中ω(n-1)表示域GF(2n)中n-1的二進(jìn)制數(shù)表示中1的個(gè)數(shù)。在此基礎(chǔ)上，Sand ho oh 和Chang Han Kim［7］提出優(yōu)化求逆算法(Optimal Inverse Algorithm，OIA)。該算法求逆主要用到乘法和平方運(yùn)算，乘法次數(shù)和Itoh的算法相同。有關(guān)算法介紹可參閱文獻(xiàn)[7]。本文有限域元素求逆采用的就是OIA算法。

2 ECC實(shí)現(xiàn)的硬件結(jié)構(gòu)

從圖1分析，ECC加密算法可分為三個(gè)層次，即輸入/輸出控制、有限域運(yùn)算模塊控制、ECC加/解密運(yùn)算控制。

有關(guān)ECC曲線的參數(shù)，基點(diǎn)P的坐標(biāo)、密鑰通過(guò)外部存儲(chǔ)器接口由32位總線輸入到存儲(chǔ)器中，在I/O狀態(tài)機(jī)的控制下，由串并轉(zhuǎn)換模塊將有關(guān)數(shù)據(jù)輸入到內(nèi)部寄存器組中。寄存器組由233位的存儲(chǔ)單元組成，主要存放運(yùn)算過(guò)程中所需的中間變量和運(yùn)算所需的系統(tǒng)參數(shù)。

圖1 ECC加密算法結(jié)構(gòu)圖

有限域運(yùn)算模塊主要負(fù)責(zé)有限域的各種算術(shù)運(yùn)算，通過(guò)狀態(tài)機(jī)控制，完成域GF（2n）中的有限域加法、乘法、平方和求逆運(yùn)算。

運(yùn)算控制級(jí)中的點(diǎn)乘狀態(tài)機(jī)通過(guò)對(duì)有限域運(yùn)算模塊的合理調(diào)用，完成橢圓曲線上P=Q和P≠Q(mào)的加法運(yùn)算，快速得到KP的結(jié)果，KP的計(jì)算也是整個(gè)ECC設(shè)計(jì)的核心。加/解密控制則是利用KP的值進(jìn)行數(shù)據(jù)加/解密運(yùn)算。

本文設(shè)計(jì)的支持多域?qū)挼腅CC加密系統(tǒng)模塊如圖2所示。域?qū)捒刂茊卧沁x擇域?qū)挼?，此處只選擇了兩個(gè)域?qū)挕CC加/解密控制單元完成兩個(gè)域?qū)捪碌腅CC加/解密運(yùn)算。設(shè)計(jì)中采用了兩個(gè)寄存組，分別存儲(chǔ)GF(2191)和GF(2233)的外部輸入?yún)?shù)。當(dāng)數(shù)據(jù)總線輸入191bits下的參數(shù)時(shí)，選擇域?qū)?91bits下的ECC加密；數(shù)據(jù)總線輸入233bits下的參數(shù)時(shí)，選擇域?qū)?91bits下的ECC加密。本設(shè)計(jì)可以進(jìn)行擴(kuò)展，只要增加寄存器組，對(duì)域?qū)捒刂茊卧骱?jiǎn)單修改，便可以完成更多域?qū)捪碌腅CC運(yùn)算。

圖2 支持雙域?qū)挼腅CC加密系統(tǒng)模塊圖

2.1 點(diǎn)乘單元設(shè)計(jì)

ECC算法的核心是求點(diǎn)乘KP的運(yùn)算。點(diǎn)乘運(yùn)算層是通過(guò)對(duì)點(diǎn)加和點(diǎn)倍進(jìn)行調(diào)度來(lái)實(shí)現(xiàn)。求點(diǎn)乘的算法主要有二進(jìn)制算法、m進(jìn)制方法、符號(hào)數(shù)字表示法、滑動(dòng)窗口法等。本文實(shí)現(xiàn)ECC時(shí)采用的點(diǎn)乘法算法為冗余編碼的二進(jìn)制方法［8］，其理由如下：

（1）該方法簡(jiǎn)單，易于硬件實(shí)現(xiàn)；

（2）M進(jìn)制方法和滑動(dòng)窗口方法都需要預(yù)計(jì)算，需要較大的存儲(chǔ)空間，需要資源較大，并且編程復(fù)雜，不利于硬件實(shí)現(xiàn)。

其算法描述如下：

圖3為KP運(yùn)算結(jié)構(gòu)圖。在它的組成部分中，有限域運(yùn)算模塊包括乘法運(yùn)算器、求逆運(yùn)算器、加法及平方運(yùn)算器，負(fù)責(zé)完成有限域上的各種算術(shù)運(yùn)算功能。移位寄存器為線性反饋寄存器，其中保存經(jīng)過(guò)冗余編碼后的私鑰值K。點(diǎn)加和點(diǎn)倍運(yùn)算為兩個(gè)獨(dú)立的單元，分別通過(guò)狀態(tài)機(jī)對(duì)有限域運(yùn)算模塊進(jìn)行調(diào)度，完成點(diǎn)加與點(diǎn)倍運(yùn)算。點(diǎn)乘狀態(tài)控制器根據(jù)移位寄存器中存儲(chǔ)的數(shù)值，選擇進(jìn)行點(diǎn)加或是點(diǎn)倍運(yùn)算，完成點(diǎn)乘KP的計(jì)算。

2.2 有限域運(yùn)算單元設(shè)計(jì)

圖4是支持多域?qū)挼某朔ㄆ鹘Y(jié)構(gòu)。其主要單元功能如下：

(1)域?qū)掁D(zhuǎn)換單元根據(jù)外部輸入?yún)?shù)的不同，協(xié)同乘法器控制單元完成不同域?qū)捪碌某朔ㄟ\(yùn)算。

(2)與或陣列1與2分別對(duì)應(yīng)GF(2191)和GF(2233)的與或陣列表。運(yùn)算時(shí)，根據(jù)SEL值選擇不同的與或陣列完成不同域?qū)挼某朔ㄟ\(yùn)算。

(3)輸出控制單元對(duì)兩個(gè)與或陣列分別計(jì)算出的ck值進(jìn)行拼接，得到最后的乘法結(jié)果。設(shè)計(jì)中寄存器的寬度為233位，當(dāng)輸入191位乘數(shù)時(shí)233位的寄存器的前191位保存運(yùn)算結(jié)果。這樣做的好處是不需要另外用寄存器來(lái)存儲(chǔ)191位乘法時(shí)的運(yùn)算值，可以節(jié)約面積。

圖4 支持多域?qū)挼某朔ㄆ鹘Y(jié)構(gòu)

基于有限域乘法模塊，本文設(shè)計(jì)了一個(gè)逆控制器：具有求逆和乘法的雙重功能。

基于串并結(jié)合結(jié)構(gòu)的乘法模塊，本文設(shè)計(jì)了一個(gè)逆控制器：具有求逆和乘法的雙重功能。其單元模塊如圖5所示，它的主要組成部分是有限域逆控制器、模式選擇器、求逆狀態(tài)機(jī)和有限域乘法模塊。

圖5 求逆控制單元結(jié)構(gòu)圖

（1）模式選擇信號(hào)CompType是由選擇信號(hào)發(fā)生器產(chǎn)生的，主要控制運(yùn)算的類型：乘法還是求逆。進(jìn)行乘法運(yùn)算時(shí)，模式選擇信號(hào)低有效，對(duì)輸入A和輸入B執(zhí)行乘法過(guò)程，輸出A×B；進(jìn)行求逆運(yùn)算時(shí)，逆使能信號(hào)(Invstr)高有效，模式選擇信號(hào)保持為高，對(duì)輸入A執(zhí)行求逆運(yùn)算，輸出A的逆運(yùn)算。在這種情況下，輸入B沒(méi)有作用。運(yùn)算結(jié)果存儲(chǔ)在有限域乘法模塊的寄存器中。

（2）控制器的主要功能是接收輸入信號(hào)，按照求逆算法產(chǎn)生控制序列，控制乘法器執(zhí)行操作。當(dāng)運(yùn)算完成時(shí)，由乘法模塊中的寄存器輸出結(jié)果，并置Finish為高電平。

（3）有限域乘法模塊為串并結(jié)合結(jié)構(gòu)的乘法器，完成乘法功能。

（4）求逆狀態(tài)機(jī)根據(jù)OIA算法協(xié)同控制器對(duì)求逆運(yùn)算進(jìn)行控制。

加法器：正規(guī)基下的加法器十分簡(jiǎn)單，有限域任意兩元素相加，結(jié)果是各自矢量表達(dá)位的逐位異或（XOR）。做加法運(yùn)算時(shí)，輸入/輸出寄存器均選擇并行工作模式，整個(gè)運(yùn)算只需要一個(gè)時(shí)鐘周期。

平方器：正規(guī)基下的元素平方是元素矢量表達(dá)式循環(huán)移位，完成整個(gè)運(yùn)算也只需要一個(gè)時(shí)鐘周期，這是選擇正規(guī)基的突出優(yōu)點(diǎn)。

4 結(jié)束語(yǔ)

本文通過(guò)對(duì)ECC算法進(jìn)行研究，從點(diǎn)乘與群運(yùn)算層的設(shè)計(jì)出發(fā)，給出了一種參數(shù)可選的ECC加密算法的FPGA實(shí)現(xiàn)方案。在調(diào)試階段，本設(shè)計(jì)選擇了存在Ⅱ型優(yōu)化正規(guī)基的191 bits和233 bits有限域?yàn)槔捎肰HDL語(yǔ)言進(jìn)行描述，Altera公司的QuartusⅡ開發(fā)軟件作為編譯及綜合工具。設(shè)計(jì)原形在Altera Cyclone的 EP1C12Q240C8器件上實(shí)現(xiàn)并進(jìn)行了驗(yàn)證，共占用17 733個(gè)邏輯單元，最高時(shí)鐘頻率可達(dá)73.82 MHz。在50 MHz的時(shí)鐘頻率下，F2191上，平均一次橢圓曲線點(diǎn)乘運(yùn)算時(shí)間為14.365 ms；F2233上，平均一次橢圓曲線點(diǎn)乘運(yùn)算時(shí)間為19.565 ms，本文的設(shè)計(jì)突破了單一結(jié)構(gòu)、參數(shù)固定的ECC專用芯片形式，使之能滿足不同用戶的需要。

本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。