橢圓曲線加密算法的實(shí)現(xiàn)有軟件和硬件兩種方式。從安全性角度上考慮，硬件方式實(shí)現(xiàn)更具有優(yōu)越性。但是絕大多數(shù)都是針對(duì)某一個(gè)固定有限域設(shè)計(jì)的，具體到應(yīng)用場(chǎng)合，有時(shí)需要系統(tǒng)參數(shù)可選擇。那么我今天就給大家介紹一種參數(shù)可選的橢圓曲線加密算法。

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

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

1）乘法。當(dāng)Fn2域元素用ONB表示時(shí)，其乘法法則是由一個(gè)n×n的矩陣M（乘法矩陣）來表征的。

設(shè)有限域GF（2n）中進(jìn)行乘法的兩個(gè)域元素用正規(guī)基表示為a=（an-1，…，a1，a0），b=（bn-1，…，b1，b0），乘法運(yùn)算的結(jié)果為c=（cn-1，…，c1，c0），用ak、bk分別表示a、b循環(huán)左移k比特后的序列，則ck=akMbtrk。

（2）求逆。費(fèi)爾馬定理：若a∈F2n（a≠0），則a的逆元a-1=a2n-2=a2+22+…+2n-1

正規(guī)基表示下的元素求逆通常使用費(fèi)爾馬定理，但是直接應(yīng)用需要的乘法次數(shù)太多。完成一次求逆運(yùn)算所需乘法次數(shù)最少為I（m）=[log2（n-1）]+ω（n-1）-1次。其中ω（n-1）表示域GF（2n）中n-1的二進(jìn)制數(shù)表示中1的個(gè)數(shù)。在此基礎(chǔ)上，Sandhooh和ChangHanKim提出優(yōu)化求逆算法（OptimalInverseAlgorithm，OIA）。該算法求逆主要用到乘法和平方運(yùn)算，乘法次數(shù)和Itoh的算法相同。

二、橢圓曲線加密算法實(shí)現(xiàn)的硬件結(jié)構(gòu)

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

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

有限域運(yùn)算模塊主要負(fù)責(zé)有限域的各種算術(shù)運(yùn)算，通過狀態(tài)機(jī)控制，完成域GF（2n）中的有限域加法、乘法、平方和求逆運(yùn)算。運(yùn)算控制級(jí)中的點(diǎn)乘狀態(tài)機(jī)通過對(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ū)挼模颂幹贿x擇了兩個(gè)域?qū)挕?/p>

橢圓曲線加密算法加/解密控制單元完成兩個(gè)域?qū)捪碌臋E圓曲線加密算法加/解密運(yùn)算。

設(shè)計(jì)中采用了兩個(gè)寄存組，分別存儲(chǔ)GF（2191）和GF（2233）的外部輸入?yún)?shù)。當(dāng)數(shù)據(jù)總線輸入191bits下的參數(shù)時(shí)，選擇域?qū)?91bits下的橢圓曲線加密算法加密；數(shù)據(jù)總線輸入233bits下的參數(shù)時(shí)，選擇域?qū)?91bits下的ECC加密。本設(shè)計(jì)可以進(jìn)行擴(kuò)展，只要增加寄存器組，對(duì)域?qū)捒刂茊卧骱?jiǎn)單修改，便可以完成更多域?qū)捪碌臋E圓曲線加密算法運(yùn)算。

1、點(diǎn)乘單元設(shè)計(jì)

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

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

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

其加密算法描述如下：

k的冗余編碼：k=（kn-1，kn-2，…，k0）

（1）初始化：temp=G

（2）依次對(duì)（kn-1，kn-2，…，k0）進(jìn)行下列運(yùn)算：

①倍點(diǎn):temp=temp+temp；

②如果ki為1，點(diǎn)加計(jì)算：temp=temp+P；

③如果ki為-1，點(diǎn)減計(jì)算：temp=temp-P

P=（x，y），由-P=（x，x+y），有temp-P=temp+（-P），故點(diǎn)減運(yùn)算轉(zhuǎn)換為點(diǎn)加來進(jìn)行。冗余編碼后計(jì)算點(diǎn)乘平均需要t/4次點(diǎn)加，t次點(diǎn)倍;最壞需要t/2次點(diǎn)加，t次點(diǎn)倍。冗余編碼后，平均情況下減少了t/4個(gè)點(diǎn)加運(yùn)算、點(diǎn)乘運(yùn)算速度。

圖3為KP運(yùn)算結(jié)構(gòu)圖。在它的組成部分中，有限域運(yùn)算模塊包括乘法運(yùn)算器、求逆運(yùn)算器、加法及平方運(yùn)算器，負(fù)責(zé)完成有限域上的各種算術(shù)運(yùn)算功能。移位寄存器為線性反饋寄存器，其中保存經(jīng)過冗余編碼后的私鑰值K。點(diǎn)加和點(diǎn)倍運(yùn)算為兩個(gè)獨(dú)立的單元，分別通過狀態(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、有限域運(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ì)算出的ck值進(jìn)行拼接，得到最后的乘法結(jié)果。設(shè)計(jì)中寄存器的寬度為233位，當(dāng)輸入191位乘數(shù)時(shí)233位的寄存器的前191位保存運(yùn)算結(jié)果。這樣做的好處是不需要另外用寄存器來存儲(chǔ)191位乘法時(shí)的運(yùn)算值，可以節(jié)約面積。

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

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

（1）模式選擇信號(hào)CompType是由選擇信號(hào)發(fā)生器產(chǎn)生的，主要控制運(yùn)算的類型:乘法還是求逆。進(jìn)行乘法運(yùn)算時(shí)，模式選擇信號(hào)低有效，對(duì)輸入A和輸入B執(zhí)行乘法過程，輸出A×B;進(jìn)行求逆運(yùn)算時(shí)，逆使能信號(hào)（Invstr）高有效，模式選擇信號(hào)保持為高，對(duì)輸入A執(zhí)行求逆運(yùn)算，輸出A的逆運(yùn)算。在這種情況下，輸入B沒有作用。運(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)。

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

admin

收藏 海報(bào)分享