李 超，張 強(qiáng)，曲英杰

(青島科技大學(xué) 信息科學(xué)與技術(shù)學(xué)院， 山東 青島 266061)

域橢圓曲線點(diǎn)乘的VLSI實(shí)現(xiàn)方法研究

李 超，張 強(qiáng)，曲英杰

(青島科技大學(xué) 信息科學(xué)與技術(shù)學(xué)院， 山東 青島 266061)

為了實(shí)現(xiàn)橢圓曲線密碼算法的高效性，提出了基于優(yōu)化的底層有限域算法的點(diǎn)乘設(shè)計(jì)方法;基于對(duì)二進(jìn)制有限域運(yùn)算的研究，提出并行模乘算法和基于歐幾里得算法的右移求逆算法，并在實(shí)現(xiàn)中進(jìn)行優(yōu)化，在此基礎(chǔ)上采用蒙哥馬利算法實(shí)現(xiàn)點(diǎn)乘的快速運(yùn)算；根據(jù)該算法，提出了ECC硬件電路實(shí)現(xiàn)方法，并用Verilog RTL進(jìn)行邏輯設(shè)計(jì)，最終在Xilinx的XC7A100T FPGA硬件平臺(tái)上驗(yàn)證實(shí)現(xiàn);通過仿真測(cè)試、綜合驗(yàn)證和時(shí)序后仿真的結(jié)果分析，所設(shè)計(jì)電路的時(shí)鐘頻率可以達(dá)到110 MHz,運(yùn)算速度可達(dá)2.92 ms，證明了設(shè)計(jì)的有效性和可行性。

橢圓曲線密碼；二進(jìn)制域；點(diǎn)乘；模乘；模逆

0 引言

橢圓曲線密碼算法(elliptic curve cryptography, ECC)因其密鑰長度小、安全強(qiáng)度高、便于硬件實(shí)現(xiàn)等優(yōu)點(diǎn)，廣泛的被用于硬件實(shí)現(xiàn)的加密系統(tǒng)中[1]。其中，點(diǎn)乘運(yùn)算是實(shí)現(xiàn)橢圓曲線密碼高效性的前提條件，而有限域算術(shù)運(yùn)算的有效實(shí)現(xiàn)則是點(diǎn)乘的關(guān)鍵[2]。目前廣泛采用的GF(2m)點(diǎn)乘算法實(shí)現(xiàn)主要是分別設(shè)計(jì)底層的有限域運(yùn)算單元，然后通過協(xié)處理器或者其他控制電路來調(diào)用底層其他各功能單元[3]。所以研究并有效實(shí)現(xiàn)域運(yùn)算層的各個(gè)模塊是研究基于FPGA的ECC點(diǎn)乘運(yùn)算的關(guān)鍵。通過研究近年的實(shí)現(xiàn)方案，文獻(xiàn)[4]采用Montgomery點(diǎn)乘算法實(shí)現(xiàn)并行調(diào)度分解，跳過點(diǎn)加和倍點(diǎn)的調(diào)用過程，解決了頂層調(diào)用復(fù)雜的問題，提高了頂層的運(yùn)算速度，但其底層四路的調(diào)度緩慢且復(fù)雜，導(dǎo)致資源開銷較大。文獻(xiàn)[5]中對(duì)于底層域乘法運(yùn)算的實(shí)現(xiàn)，雖然在運(yùn)算過程中對(duì)算法進(jìn)行了改進(jìn)，在運(yùn)算過程中同時(shí)完成了相乘和取模運(yùn)算，節(jié)約了資源，但是卻犧牲了運(yùn)算速度和效率?？紤]硬件電路實(shí)現(xiàn)的特點(diǎn)和優(yōu)勢(shì)，本文采用GF(2m)內(nèi)的橢圓曲線作為硬件的實(shí)現(xiàn)方案，選用實(shí)現(xiàn)效率高的蒙哥馬利點(diǎn)乘算法，通過設(shè)計(jì)并行的模乘算法和改進(jìn)的模逆算法，實(shí)現(xiàn)點(diǎn)乘運(yùn)算的電路結(jié)構(gòu)設(shè)計(jì)，取得了良好效果。

1 橢圓曲線加密系統(tǒng)

二進(jìn)制有限域GF(2m)上的Weierstrass方程如式(1)所示：

y2+xy=x3+ax2+b,a,b∈GF(2m),b≠0

(1)

當(dāng)b=1時(shí)稱為Koblitz曲線。此類曲線在橢圓曲線密碼體制的實(shí)現(xiàn)中速度是最快的。橢圓曲線密碼方案的安全性問題是基于橢圓曲線的離散對(duì)數(shù)問題(elliptic curve discrete logarithm problem, ECDLP)，這也是它優(yōu)于包括RSA在內(nèi)等公鑰密碼體制的原因。橢圓曲線離散對(duì)數(shù)問題是：給定有限域Fq和定義在其域上的橢圓曲線E(Fq)，若已知橢圓曲線上的點(diǎn)P，求Q=KP很容易，但是反過來，在已知P和Q，求K值就非常困難，這樣就可以把Q看做為公鑰，K為私鑰[6]，這就是橢圓曲線的點(diǎn)乘原理。由于在ECC中，多項(xiàng)式f(x)為稀疏多項(xiàng)式，且多用三項(xiàng)式或者五項(xiàng)式，即f(x)的二進(jìn)制表示僅僅只有3或者5位為1，其余值全為0。在后文的討論中，本文采用的都是三項(xiàng)式基f(x)=x233+x74+1，即m=233。

2 有限域運(yùn)算的電路結(jié)構(gòu)設(shè)計(jì)

為了順利實(shí)現(xiàn)點(diǎn)乘算法，本文將重點(diǎn)放在設(shè)計(jì)有限域運(yùn)算模塊上，該模塊可以完成有限域上的加減法、模乘、模逆和除法運(yùn)算。其中，二進(jìn)制域的加減法器結(jié)構(gòu)簡單，可采用逐位異或的電路結(jié)構(gòu)處理[7]，即用N個(gè)異或門實(shí)現(xiàn)，在時(shí)鐘上升沿且復(fù)位電平無效時(shí)，在一個(gè)周期內(nèi)即可完成m位數(shù)據(jù)的逐位異或，實(shí)現(xiàn)簡單且速度較快，如圖1所示。

圖1 模加(減)異或門

2.1 模乘算法分析與改進(jìn)

模乘運(yùn)算是橢圓曲線點(diǎn)乘運(yùn)算高效實(shí)現(xiàn)的關(guān)鍵，用域元素a,b∈GF(2m)分別表示多項(xiàng)式A(x) =am-1xm-1+... +a1x+a0和B(x) =bm-1xm-1+... +b1x+b0，則域元素a與b的乘積公式為：

P(x) =A(x)×B(x)bmodF(x) =

這里F(x)是域不可約多項(xiàng)式。

從乘積公式可以看出，模乘的過程包括相乘和取模兩個(gè)過程。傳統(tǒng)的乘法是將兩個(gè)m位操作數(shù)相乘，然后對(duì)其進(jìn)行f(x)求模。二進(jìn)制域上的乘法實(shí)現(xiàn)有多種形式，主要有串行結(jié)構(gòu)，并行結(jié)構(gòu)，串并相結(jié)合的數(shù)位并行結(jié)構(gòu)。為了提高模乘算法的效率，參照文獻(xiàn)[7]中所介紹的典型移位串行算法，并對(duì)其進(jìn)一步優(yōu)化，其中文獻(xiàn)[7]中的算法如下：

輸入：A(x) =am-1xm-1+... +a1x+a0,B(x) =bm-1xm-1+... +b1x+b0，不為零的最高位為m的多項(xiàng)式f(x)。

輸出：a(x)·b(x)modf(x)。

1)若a-1modf(x)=1,則有C=B，否則C=0；

2)i從1到n-1循環(huán);

(1)b=(b<<1)modf(x) ;

(2) 若ai=1，則c=cmodb;

3)返回c。

該算法通過串行移位的方法，一個(gè)時(shí)鐘進(jìn)行一次移位的操作，然后進(jìn)入下一步的異或運(yùn)算，那么完成m位的運(yùn)算則需要m個(gè)clock，所需時(shí)間較長。根據(jù)二進(jìn)制模約減運(yùn)算的特點(diǎn)，在求模運(yùn)算中，其實(shí)上是判斷被模數(shù)的最高位數(shù)值。最高位為1的話，就將被模數(shù)與f(x)進(jìn)行異或處理；反之不變，保留原值。故可以考慮采用并行的思想，可以首先并行的得到(1)步驟中所有bi的值，然后采用并行的方式完成步驟(2)中的運(yùn)算。改進(jìn)算法描述如下：

輸入：a,b∈GF(2m),a≠0,b≠0,約減多項(xiàng)式f(x)。

輸出：c=a·bmodf(x)。

1)若a-1modf(x)=1,則有C=B，否則C=0；

2)i從1到n-1循環(huán)

(1)b=b<<1

若bm-1=1,則b=b⊕f(x)；

否則b=b；

(2)若ai=1，則c=c⊕b;

3)返回c。

根據(jù)移位方法并行獲取bi的思想，如表1所示，考慮到最高位，即b(233)、bi(233)都為1，為了表示簡潔，此處略過這項(xiàng)。

觀察表1，232個(gè)233位的bi，只與b，bi(0)，bi(232)有關(guān)。

(1)對(duì)于bi(0)，有：

b(232)=1，則b1(0)=1；b(232)=0，則b1(0)=0;

b1(232)=1，則b2(0)=1；b(232)=0，則b2(0)=0;

類推;

bi(232)=1，則bi+1(0)=1；bi(232)=0，則bi+1(0)=0；

所以b1(0)～b158(0)僅與b(232)～b(75)有關(guān)，可以一次并行得到；對(duì)于b159(0)～b232(0)與b1(74)～b74(74)有關(guān)。由此，下面先討論bi(74)的計(jì)算，然后再討論b159(0)～b232(0)的求取。

表1 bi的求取過程

(2)對(duì)于bi(74)，有：

b(232)=1，則b1(74)=～b(73)；b(232)=0，則b1(74)=b(73);

b1(232)=1，則b2(74)=～b1(73)=～b(72)；b1(232)=0，則b2(74)=b1(73)=b(72);

類推：

當(dāng)i<=74：

bi(232)=1，則bi(74)=～b(74-i)；bi(232)=0，則bi(74)=b(74-i);

當(dāng)i>74：

bi(232)=1，則bi(74)=～bi-74+1(0)；bi(232)=0，則bi(74)=bi-74+1(0);

故b1(74)～b158(74)僅與b(232)～b(75)有關(guān)，可以一次并行得到；對(duì)于b159(0)～b232(0)以及b159(74)～b232(74),與b1(74)～b74(74)有關(guān)，而這74個(gè)值也只與b(232)～b(159)有關(guān)，可見bi表格中的數(shù)據(jù)全部依賴于輸入b,，故可以一次全并行得到全部的bi值。然后將所有bi值進(jìn)行存儲(chǔ)，便于下面步驟中的異或操作，最終通過計(jì)算獲得模乘的運(yùn)算結(jié)果。

2.2 二進(jìn)制域模逆算法分析與改進(jìn)

模逆運(yùn)算是有限域算術(shù)運(yùn)算中最復(fù)雜，同時(shí)也是最耗時(shí)的，這里我們簡單的用非零元素a來表示二進(jìn)制多項(xiàng)式a(x)。在二進(jìn)制域中，非零元素a的逆元素是域GF(2m)的唯一的一個(gè)元素g，在域GF(2m)上滿足ag=1,即滿足ag≡1(modf)。這個(gè)逆元素用符號(hào)a-1modf表示，也可直接表示為a(x)。目前廣泛采用的主要有基于擴(kuò)展的歐幾里得算法和基于費(fèi)馬小定理的模逆算法來實(shí)現(xiàn)[8]?；谫M(fèi)馬小定理的算法是將求逆運(yùn)算換成模乘和模平方運(yùn)算，算法評(píng)估完成模逆運(yùn)算需要log2(m-1)+w(m-1)-1次模乘和m+1次模平方運(yùn)算[9]，這樣不僅會(huì)使軟硬件的設(shè)計(jì)復(fù)雜度有所增加，同時(shí)在運(yùn)算過程中由于反復(fù)調(diào)用模乘和模平方運(yùn)算，性能也會(huì)因此大打折扣。而基于擴(kuò)展的歐幾里得算法因?yàn)樵谶\(yùn)算過程中只涉及到移位、判斷和異或運(yùn)算，并沒有大量的乘法運(yùn)算，所以比較容易硬件上的實(shí)現(xiàn)，可以方便的并行化設(shè)計(jì)。因此針對(duì)目前廣泛采用的歐幾里得算法[10]，進(jìn)行進(jìn)一步的改進(jìn)，使其可以在運(yùn)算過程中同時(shí)進(jìn)行求逆和取模的運(yùn)算。如此，在運(yùn)算過程中同時(shí)進(jìn)行移位判斷的操作，所以輸入為m位的求逆運(yùn)算，最多只需2m個(gè)時(shí)鐘周期就可以完成，從而大大提高運(yùn)算效率。本文采用的模逆算法如下描述：

輸入：次數(shù)不高于m的非零多項(xiàng)式a(x)、b(x)和既約多項(xiàng)式f(x)。

輸出：a-1modf(x)。

1)u=a,v=f;

2)若mode=0,x1=1,若mode=1,x1=b;x2=0。

3)當(dāng)u≠1和v≠1時(shí)，重復(fù)執(zhí)行：

(1)當(dāng)u是偶數(shù)時(shí)，重復(fù)執(zhí)行：

u=u/2;

若x1是偶數(shù)，則x1=x1/2;

在水利工程施工中，機(jī)械的使用費(fèi)約占產(chǎn)值的30%。水利行業(yè)特點(diǎn)決定了水利工程施工對(duì)機(jī)械設(shè)備有特殊要求：首先要求機(jī)械設(shè)備適應(yīng)水利工程交通不便，受水文、氣象、地形等因素的影響較大及大部分水利工程施工周期較短等特點(diǎn)；其次是要適應(yīng)和滿足水利工程項(xiàng)目自身的施工要求。

否則，x1=(x1⊕f)>>1;

(2)當(dāng)v是偶數(shù)時(shí)，重復(fù)執(zhí)行:

v=v/2;

若x2是偶數(shù)，則x2=x2/2;

否則，x2=(x2⊕f)>>1.

(3)當(dāng)u≥v，則u=(u⊕v)>>1;

若x1和x2的奇偶性相同，則x1=(x1⊕x2)>>1;

否則，v=(v⊕u)>>1;

若x1和x2的奇偶性相同，則x2=(x1⊕x2)>>1;

若x1和x2的奇偶性不同，則x2=(x1⊕x2⊕f)>>1.

4)若u=1,則返回(x1)；否則，返回(x2)。

本算法中，添加一個(gè)mode模式控制位，當(dāng)mode=1時(shí)，將初始條件變?yōu)閤1=b;x2=0，便可以計(jì)算模除b/amodp，可以通過Euclidean傳統(tǒng)算法證明驗(yàn)證。如此，通過mode的值選擇即可完成模除或者模逆的運(yùn)算，如步驟2所示：當(dāng)mode=0時(shí)，進(jìn)行模逆運(yùn)算，mode=1時(shí)，進(jìn)行模除的運(yùn)算。通過將模除和模逆運(yùn)算合并為一個(gè)運(yùn)算，電路設(shè)計(jì)中就可以復(fù)用一套電路，再添加一些額外的條件判斷電路和控制電路即可同時(shí)完成兩種運(yùn)算，節(jié)省大量的操作，從而達(dá)到節(jié)約資源，優(yōu)化電路面積的效果。

3 橢圓曲線點(diǎn)乘的FPGA實(shí)現(xiàn)

采用Montgomery算法實(shí)現(xiàn)橢圓曲線點(diǎn)乘運(yùn)算設(shè)計(jì)主要分為三個(gè)過程：1)預(yù)處理模塊；2)循環(huán)運(yùn)算模塊；3)坐標(biāo)轉(zhuǎn)換模塊。根據(jù)Montgomery算法特性[11]，在模塊運(yùn)算中并不涉及縱坐標(biāo)y的計(jì)算，輸入仿射坐標(biāo)p(x,y)和二進(jìn)制數(shù)(ki-1,...,k1,k0)2。

預(yù)處理模塊主要完成數(shù)據(jù)的初始化工作，并為下一模塊的輸入提供數(shù)據(jù)，通過輸入點(diǎn)P的仿射坐標(biāo)(x,y)產(chǎn)生投影點(diǎn)P1(X1,Z1)，并調(diào)用一次倍點(diǎn)運(yùn)算產(chǎn)生P2(X2,Z2)，以供循環(huán)模塊使用。由于P1和P2相對(duì)應(yīng)，因此投影點(diǎn)P1的橫坐標(biāo)初值為X1=x，Z1=1，投影點(diǎn)P2的橫坐標(biāo)是P1經(jīng)過倍點(diǎn)運(yùn)算得到。

在第二部分的主循環(huán)運(yùn)算，是其中最耗時(shí)的模塊，同時(shí)也是控制部分最復(fù)雜的設(shè)計(jì)模塊。主要包括移位單元以及群運(yùn)算層的點(diǎn)加和倍點(diǎn)運(yùn)算，這也是點(diǎn)乘運(yùn)算中最耗時(shí)的運(yùn)算單元。當(dāng)輸入值k的二進(jìn)制位ki=0時(shí)，(X1,Z1)作為倍點(diǎn)模塊的輸入，(X1,Z1)和(X2,Z2)作為點(diǎn)加模塊的輸入。

第三部分的坐標(biāo)轉(zhuǎn)換模塊主要功能是在模逆運(yùn)算完成后，將投影坐標(biāo)再次轉(zhuǎn)換為仿射坐標(biāo)。由于在第一部分的預(yù)處理模塊中，已經(jīng)事先將點(diǎn)的仿射坐標(biāo)轉(zhuǎn)換為了投影坐標(biāo)，所以在進(jìn)行點(diǎn)加和倍點(diǎn)運(yùn)算的時(shí)候就不需要再進(jìn)行模逆運(yùn)算，只需要在最后一次模逆運(yùn)算完成后進(jìn)行坐標(biāo)的逆變換即可。

根據(jù)Montgomery算法特點(diǎn)，由于點(diǎn)加和倍點(diǎn)不存在數(shù)據(jù)相關(guān)性，可以并行調(diào)度點(diǎn)加和倍點(diǎn)，點(diǎn)加和倍點(diǎn)運(yùn)算又同時(shí)調(diào)度有限域運(yùn)算，因此可以將這個(gè)調(diào)度過程理解為點(diǎn)乘對(duì)有限域運(yùn)算的調(diào)度。點(diǎn)乘完成一次迭代運(yùn)算需要調(diào)用1次點(diǎn)加和1次倍點(diǎn)，主循環(huán)部分共需要完成m-1次迭代。在有限域調(diào)度中，用M表示模乘時(shí)間，I表示模逆時(shí)間，AS表示模加時(shí)間，在投影坐標(biāo)下，一次點(diǎn)加調(diào)用需要時(shí)間6M+2AS，一次倍點(diǎn)調(diào)用6M+1AS。所以點(diǎn)乘運(yùn)算的一次迭代共調(diào)用12次模乘運(yùn)算和3次模加運(yùn)算，采用并行調(diào)度后，完成一次迭代時(shí)間就相當(dāng)于6個(gè)模乘時(shí)間(模加時(shí)間可忽略)。再加上最后坐標(biāo)逆變換的一次模逆運(yùn)算，所以完成一次點(diǎn)乘時(shí)間為6M*(m-1)+I?？紤]到模乘、模逆實(shí)現(xiàn)所需要的時(shí)鐘周期，所以一次點(diǎn)乘需要6m*(m-1)+2m個(gè)時(shí)鐘周期。最終輸出結(jié)果坐標(biāo)即為標(biāo)量乘法kP的坐標(biāo)(X2,Z2)。

圖2 基于蒙哥馬利算法的橢圓曲線點(diǎn)乘運(yùn)算的系統(tǒng)結(jié)構(gòu)

在確定了標(biāo)量乘的總體框架后，本設(shè)計(jì)的重點(diǎn)放在有限域的電路結(jié)構(gòu)設(shè)計(jì)上。這個(gè)模塊功能強(qiáng)大，根據(jù)本文提到的有限域算法，在控制器的作用下完成具體的電路運(yùn)算。并且改進(jìn)的求逆算法在判斷條件上具有并行性，運(yùn)算步驟可以流水處理，基于FPGA設(shè)計(jì)了高效的并行執(zhí)行結(jié)構(gòu)，在算術(shù)邏輯運(yùn)算中主要由加法器、減法器、移位控制電路、異或電路、比較器和一些邏輯電路組成。實(shí)現(xiàn)的硬件結(jié)構(gòu)如圖3所示。

圖3 有限域運(yùn)算結(jié)構(gòu)圖

4 實(shí)驗(yàn)結(jié)果分析與性能比較

為了驗(yàn)證電路結(jié)構(gòu)的正確性和有效性，同時(shí)為了與其它研究成果進(jìn)行對(duì)比，選用創(chuàng)龍的開發(fā)板作為硬件驗(yàn)證平臺(tái)進(jìn)行點(diǎn)乘運(yùn)算電路的FPGA原型驗(yàn)證，平臺(tái)芯片為Xilinx的ARTIX 7芯片,型號(hào)為XC7A100T，封裝為FGG484。使用Verilog硬件描述語言進(jìn)行RTL級(jí)模型代碼描述，并通過Xilinx公司的Vivado 2015開發(fā)軟件進(jìn)行編譯綜合、布局布線和時(shí)序分析。通過Mentor Graphics公司的modelsim10.1開發(fā)軟件編寫Testbench，輸入測(cè)試激勵(lì)進(jìn)行了功能調(diào)試仿真。綜合和布局布線之后，進(jìn)行相應(yīng)的時(shí)序約束，在滿足電路內(nèi)部寄存器的建立保持時(shí)間，沒有時(shí)序違規(guī)的前提下，時(shí)鐘頻率最高可達(dá)110 Mhz，且輸出結(jié)果完全正確。當(dāng)m=233時(shí)，根據(jù)前文所得的時(shí)鐘周期數(shù)，可以計(jì)算完成一次點(diǎn)乘運(yùn)算時(shí)間為2.92 ms。同時(shí)，為了驗(yàn)證邏輯功能是否正確，時(shí)序是否符合要求，先單獨(dú)對(duì)獨(dú)立的有限域模塊進(jìn)行測(cè)試，所用參數(shù)是NIST推薦的GF(2m)域上長度為233的橢圓曲線。圖4，圖5分別是對(duì)模逆模塊和標(biāo)量乘模塊進(jìn)行的仿真測(cè)試結(jié)果。

圖4 二進(jìn)制域模逆仿真波形圖

圖5 二進(jìn)制域標(biāo)量乘仿真波形圖

1)模逆仿真測(cè)試：向量輸入a_in，模逆輸出結(jié)果值 c_out。

a_in=233'h1b7b7b7b7b7b7b7b7b7b7b7b7b7b7b7b7b7b7b7

b4d8d8d8d8d8d8d8d8d8

c_out=233’ff

2)標(biāo)量乘模塊測(cè)試：向量輸入k，x0_in和y0_in，點(diǎn)乘輸出結(jié)果為x_out和y_out。

k=6；

x0_in=233’h17232ba853a7e731af129f22ff4149563a419c

26bf50a4c9d6eefad6126；

y0_in=233’h1db537dece819b7f70f555a67c427a8cd9bf18

aeb9b56e0c11056fae6a3；

x_out=233’h0e15_ae1d_3e03_5c8d_4c92_5391_63f2_3d13_243f_eb57_b45a_dbe4_cf7e_c619_57f6;

y_out=233’h160f_13ec_3651_671f_201b_b64d_ff8d_f25a_f3eb_c5c3_f9bf_c5cb_17b2_2037_03a8;

表2列出了本設(shè)計(jì)與近年其他一些文獻(xiàn)研究的實(shí)驗(yàn)數(shù)據(jù)對(duì)比，主要包括完成一次點(diǎn)乘所需時(shí)間和邏輯資源的消耗情況。通過采用Synopsys公司的Design Compiler進(jìn)行仿真后綜合，查看系統(tǒng)設(shè)計(jì)的綜合報(bào)告可以看出，本設(shè)計(jì)共用9302個(gè)LUT，大概4651個(gè)slice。通過查閱對(duì)比相關(guān)文獻(xiàn)，雖然各文獻(xiàn)所實(shí)現(xiàn)的硬件平臺(tái)不一樣，但是我們依然可以參考設(shè)計(jì)的運(yùn)行時(shí)間、面積規(guī)模和域的不同來進(jìn)行對(duì)比，分析電路的執(zhí)行速度和邏輯資源消耗情況。文獻(xiàn)[12]通過改進(jìn)了模乘算法，面積上得到了優(yōu)化，但是卻犧牲了點(diǎn)乘的實(shí)現(xiàn)效率，在82M的時(shí)鐘主頻下，本設(shè)計(jì)的速度相對(duì)提升了54%。文獻(xiàn)[13]采用了點(diǎn)乘的并行分解調(diào)度運(yùn)算，但是未提出域運(yùn)算層次的算法優(yōu)化，雖然比本設(shè)計(jì)速度占優(yōu)勢(shì)，但是硬件資源消耗比本設(shè)計(jì)多了48%。相對(duì)于其他設(shè)計(jì)，本設(shè)計(jì)也取得了面積和速度的較好折中，資源消耗也有明顯改善，經(jīng)濟(jì)性上更為突出。

表2 FPGA設(shè)計(jì)速度比較

5 結(jié)束語

本文通過研究橢圓曲線有限域的算術(shù)運(yùn)算，根據(jù)ECC的多項(xiàng)式的稀疏特點(diǎn)，提出并行的模乘思想，并改進(jìn)傳統(tǒng)的歐幾里得右移求逆算法，使其可同時(shí)完成模逆和模除運(yùn)算，以此為基礎(chǔ)設(shè)計(jì)了有效的點(diǎn)乘電路并進(jìn)行FPGA原型驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，當(dāng)數(shù)據(jù)位寬為233位時(shí)，只需2.92 ms即可完成標(biāo)量乘運(yùn)算。相較于其他算法，本設(shè)計(jì)大大提高了運(yùn)算速度，資源消耗較少，取得了面積和速度的較好折中，在已公開的文獻(xiàn)中性價(jià)比較高。盡管本文采用的模多項(xiàng)式是三項(xiàng)式基，但對(duì)于其他多項(xiàng)式基同樣適用，同時(shí)只需修改電路設(shè)計(jì)輸入的參數(shù)值即可實(shí)現(xiàn)其他不同位寬數(shù)據(jù)的要求，保證了設(shè)計(jì)的有效性、通用性和可研究性。

[1] 賴忠喜,陶東婭,張占軍.GF(2n)域橢圓曲線密碼體制中快速標(biāo)量乘算法的研究[J].計(jì)算機(jī)應(yīng)用與軟件, 2014,31(8):324-326.

[2] 謝天藝. 素?cái)?shù)域橢圓曲線密碼SoC的設(shè)計(jì)與實(shí)現(xiàn)[D].杭州:浙江大學(xué), 2015.

[3] 賴忠喜,張占軍,陶東婭.橢圓曲線底層域快速算法的研究[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(3):67-70.

[4] 賴忠喜, 張占軍. 橢圓曲線底層域快速算法的優(yōu)化[J]. 計(jì)算機(jī)工程與應(yīng)用, 2015, 51(22):115-118.

[5] 張莉華, 藺 莉. 一種安全高效的橢圓曲線密碼抗功耗攻擊算法[J]. 測(cè)控技術(shù), 2016, 35(8):118-121.

[6] 胡詩瑋,徐和根.有限域GF(2～(256))上橢圓曲線密碼算法的硬件設(shè)計(jì)[J].機(jī)電一體化, 2015,21(2):71-75.

[7] 鄭建宏,周 亮. 橢圓曲線加密算法在衛(wèi)星通信中的應(yīng)用[J]. 信息通信,2016,31(02):209-210.

[8] 石亞娟, 黃輝輝, 陳建華. 基于智能卡的動(dòng)態(tài)身份認(rèn)證協(xié)議[J]. 電子技術(shù)應(yīng)用, 2015, 41(3):97-100.

[9] 尹 恒. ECC標(biāo)量乘算法在抗邊信道攻擊上的應(yīng)用研究[D].貴陽:貴州大學(xué),2015.

[10] 白永祥. 橢圓曲線密碼算法在VPN安全握手中的應(yīng)用[J]. 電子設(shè)計(jì)工程, 2015, 23(13):18-20.

[11] 郭高峰,崔強(qiáng)強(qiáng).基于GF(2～m)的橢圓曲線求逆算法的改進(jìn)研究[J].現(xiàn)代電子技術(shù),2014,37(18):19-22.

[12] 操志輝.GF(2～m)域上ECC標(biāo)量乘的設(shè)計(jì)與FPGA實(shí)現(xiàn)[D].武漢:武漢理工大學(xué),2014.

[13] Urbano-Molano F A，Trujillo-Olaya V，Velasco-Medina J. Design of an elliptic curve crypto processor using optimal normal basis over GF( 2233) [A].2013 IEEE Fourth Latin American Symposium on Circuits and Systems( LASCAS)[C]. Cusco：IEEE，2013：1-4.

[14] 田 祎, 劉愛軍, 申衛(wèi)昌. 基于梳狀算法的橢圓曲線密碼標(biāo)量乘改進(jìn)方案[J]. 微電子學(xué)與計(jì)算機(jī), 2015, 32(5):99-103.

[15] 王云峰，王 靜，黃世偉．一種兩路并行調(diào)度的點(diǎn)乘算法硬件實(shí)現(xiàn)[J]．新型工業(yè)化，2014，4(7)：20-27.

Research and Implementation of Point Multiplication Over Elliptic Curve F2mBased on VLSI

Li Chao，Zhang Qiang，Qu Yingjie

(School of Information Science & Technology, Qingdao University of Science and Technology, Qingdao 266061, China)

To realize the elliptic curve cryptography (ECC) effectively, the design method of modular multiplication based on optimized binary finite filed algorithm was presented. By the study of the binary finite fields, paralleled modular multiplication algorithm and inversion algorithm which was based on Euclidean algorithm were presented. The two algorithms were optimized during the process and then realized the fast evaluation of point multiplication by adopting Montgomery algorithm. ECC hardware implementation design was proposed based on the algorithm, and converted to logic designs using Verilog RTL, finally it worked on the XC7A100T FPGA platform of Xilinx. By pre-simulation, synthetical verification and analyzing the results of post simulation, the clock frequency of the designed circuit could reach up to 110MHz and the operating rate attained to 2.92 ms which demonstrated the feasibility and effectiveness of the project.

elliptic curve cryptography ; GF(2m); point multiplication; modular multiplication; modular inversion

2017-05-18；

2017-06-06。

山東省科技計(jì)劃項(xiàng)目(2013YD01038)。

李 超(1990-)，男，山東棗莊人，碩士研究生，主要從事集成電路設(shè)計(jì)與嵌入式系統(tǒng)方向的研究。

曲英杰(1964-)，男，山東青島人，博士，教授，碩士生導(dǎo)師，主要從事集成電路設(shè)計(jì)與數(shù)據(jù)加解密方向的研究。

1671-4598(2017)12-0232-05

10.16526/j.cnki.11-4762/tp.2017.12.060

TN918

A