一種ECC快速簽名在電子政務(wù)中的應(yīng)用

李成霞 徐守志 周 歡

(三峽大學(xué)電氣信息學(xué)院,湖北宜昌 443002)

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展以及政府推進(jìn)電子政務(wù)力度的加強(qiáng),無(wú)紙化辦公已經(jīng)成為政府及各企業(yè)發(fā)展的一種趨勢(shì),但是電子公文涉及到各黨政機(jī)關(guān)的機(jī)密信息,因此安全問(wèn)題非常重要,只有解決好安全問(wèn)題才能推動(dòng)電子政務(wù)向前發(fā)展.安全問(wèn)題主要涉及到電子公文的安全傳輸和身份認(rèn)證問(wèn)題.簽名技術(shù)是密碼學(xué)的核心技術(shù)之一,可以保證信息在網(wǎng)絡(luò)傳輸過(guò)程中的完整性和不可否認(rèn)性.橢圓曲線密碼體制[1-2]是Neal Koblitz和VS Miller在1985年提出來(lái)的,它可以用較小的密鑰獲得較高的安全性,與已有的公鑰體制相比(比如RSA)具有安全性高、計(jì)算量小、處理速度快、存儲(chǔ)空間占用小的優(yōu)點(diǎn).因此將基于橢圓曲線的數(shù)字簽名用于解決電子公文的安全性問(wèn)題具有廣泛的應(yīng)用前景.本文主要運(yùn)用非相鄰二進(jìn)制法和變長(zhǎng)滑動(dòng)窗口相結(jié)合的方法提高橢圓曲線密碼體制中的點(diǎn)乘運(yùn)算效率,能在更長(zhǎng)的密鑰長(zhǎng)度下保證簽名的速度,并將其用于電子公文在傳輸過(guò)程中對(duì)機(jī)密信息的簽名,保證了安全性的同時(shí)也提高了簽名速度.

1 橢圓曲線密碼體制

1.1 ECDSA參數(shù)

ECDSA全局參數(shù)表示為(q,a,b,G,n,h),其中q為有限域的大小,本文探討素?cái)?shù)域上的ECC,選擇方程y2=x3-3x+bmodq,GF(q)表示一個(gè)有限域,a,b∈GF(q)為橢圓曲線E的參數(shù),基點(diǎn)G=(xG,yG),的階為素?cái)?shù)=#E(GF(q))/n.

用戶私鑰為隨機(jī)整數(shù)d∈[1,n-1],相應(yīng)的公鑰為Q=dG.

1.2 橢圓曲線數(shù)字簽名方案

發(fā)送端完成對(duì)信息m的簽名,簽名為(r,s):

(1)對(duì)于待簽名信息m,用哈希函數(shù)SHA-1,計(jì)算e=H(m),并轉(zhuǎn)化為一個(gè)160位的整數(shù);

(2)任意選取一個(gè)隨機(jī)整數(shù)k,k∈[1,n-1],計(jì)算kG=(x1,y1);

(3)計(jì)算r=x1modn,如果r=0,則返回(2)重新選擇k;

(4)計(jì)算s=k-1(e+dr)modn,如果s=0,則返回(2);

接收端驗(yàn)證簽名(r,s)是否是發(fā)送端對(duì)消息m的簽名:

(1)判斷(r,s)(r,s)是否屬于[1,n-1],否則簽名無(wú)效;

(2)計(jì)算e=H(m);計(jì)算w=s-1modn;計(jì)算u1=ewmodn,u2=rwmodn;

(3)計(jì)算X=u1G+u2Q,如果X=O表示簽名無(wú)效;否則X=(x1,y1)計(jì)算v=x1modn;

(4)若v=r,則簽名有效;否則無(wú)效.

1.3 基于可變窗口機(jī)制ECC快速簽名算法

從橢圓曲線簽名、驗(yàn)證方案可知,共需要4次點(diǎn)乘運(yùn)算,點(diǎn)乘算法是影響執(zhí)行效率的重要因素之一,因此如何提高點(diǎn)乘算法的運(yùn)算速度是提高整個(gè)ECC簽名的關(guān)鍵之一.

1.3.1 點(diǎn)乘算法

在給定的有限域上,一個(gè)橢圓曲線上的點(diǎn)P和一個(gè)隨機(jī)大整數(shù)K相乘被稱為點(diǎn)乘,也是P自身相加K次.KP運(yùn)算速度取決于整數(shù)K的二進(jìn)制長(zhǎng)度的縮短,或非零個(gè)數(shù)的減少.點(diǎn)加由非零個(gè)數(shù)決定,倍點(diǎn)是由二進(jìn)制位數(shù)決定的.一般一個(gè)確定的二進(jìn)制位數(shù)無(wú)法改變,所以倍點(diǎn)運(yùn)算次數(shù)無(wú)法改變,NAF、滑動(dòng)窗口法等主要是通過(guò)減少點(diǎn)加來(lái)提高運(yùn)算速度的.NAF法較“平方-乘”方法大約快1/8,在滑動(dòng)窗口算法中變長(zhǎng)滑動(dòng)窗口較占優(yōu)勢(shì)[3].NAF表示法具有最少的非零元素,而變長(zhǎng)滑動(dòng)窗口法可以靈活地改變窗口大小,所以采用NAF和變長(zhǎng)滑動(dòng)窗口相結(jié)合的方法實(shí)現(xiàn)點(diǎn)乘算法來(lái)提高速度.一個(gè)正整數(shù)K的非相鄰表達(dá)式為NAF(K)計(jì)算參考文獻(xiàn)[4].

在NAF法與變長(zhǎng)滑動(dòng)窗口法相結(jié)合中,可以將NAF(K)中的元素劃分為零窗口和非零窗口,例如可以計(jì)算出NAF(1031)={1,0,0,0,0,0,0,1,0,0,-1},觀察窗口中的元素:含有6個(gè)和2個(gè)連續(xù)的零,所以分別將其劃為零窗口,因此窗口最后劃分為E4、E3、E2、E1、E0,其中E4 窗口元素為{1},長(zhǎng)度為 1;E3窗口為{0,0,0,0,0,0},長(zhǎng)度為6;E2窗口元素為{1},長(zhǎng)度為1;E1窗口元素為{0,0},窗口長(zhǎng)度為2;E0窗口元素為{-1},長(zhǎng)度為1.結(jié)合NAF法和變長(zhǎng)滑動(dòng)窗口法,本文所設(shè)計(jì)的點(diǎn)乘算法流程圖如圖1所示.可以計(jì)算出1031P=210P+23P-P=21(22(21(26P+0P)+1P)+0P)+(-1)P,所以點(diǎn)乘KP的計(jì)算公式可以表示為是第i個(gè)窗口,l(Ei)是第i個(gè)窗口的長(zhǎng)度.

圖1 點(diǎn)乘算法流程圖

因?yàn)镹AF(K)中沒(méi)有兩個(gè)連續(xù)的非零元素,所以在窗口劃分為零窗口和非零窗口時(shí),只可能是{1}、{-1}、{0,0,…0}這3種情形的窗口,所以圖2非零窗口的計(jì)算式Q0=ki?2i?P中的ki只能為±1,因此在整個(gè)計(jì)算中最費(fèi)時(shí)的是Q0=2iP.所以在進(jìn)行該點(diǎn)乘算法時(shí),先分析NAF(K)中非零元素的位置并進(jìn)行適當(dāng)預(yù)計(jì)算(2iP),在綜合時(shí)間和空間條件下,提高整個(gè)點(diǎn)乘算法的運(yùn)算速度.

1.3.2 點(diǎn)加和倍點(diǎn)

點(diǎn)乘可以分解為倍點(diǎn)和點(diǎn)加運(yùn)算,在點(diǎn)加和倍點(diǎn)的計(jì)算中主要考慮避免求逆,因?yàn)樵贔q域上的求逆操作相當(dāng)慢,大概相當(dāng)于80多次乘法操作.各坐標(biāo)中點(diǎn)加和倍點(diǎn)計(jì)算[5]所需域操作個(gè)數(shù)如表1:求逆(I),平方(S),乘法(M).由表1可知,雅可比投射坐標(biāo)下倍點(diǎn)速度最快,且利用所選取的橢圓曲線方程(y2=x3-3x+bmodq)時(shí),倍點(diǎn)速度可以達(dá)到 4M+4S,雅可比-仿射坐標(biāo)下點(diǎn)加速度最快.在點(diǎn)乘中,Q始終以雅可比投射坐標(biāo)系(X∶Y∶Z)形式表示,Q0以仿射坐標(biāo)(x,y)表示,Q=Q+Q0中,輸入以雅可比投射坐標(biāo)表示的Q和仿射坐標(biāo)表示的Q0,調(diào)用雅可比-仿射的點(diǎn)加算法[5]得到以雅可比投射坐標(biāo)表示的點(diǎn)加結(jié)果Q=kp=(X∶Y∶Z),最后再轉(zhuǎn)化為仿射坐標(biāo)表示(XZ-2,XZ-3).

表1 各坐標(biāo)下點(diǎn)加和倍點(diǎn)所需域操作數(shù)

2 ECC快速數(shù)字簽名技術(shù)在電子政務(wù)中的應(yīng)用

公文涉及到各黨政機(jī)關(guān)及企業(yè)內(nèi)部機(jī)密信息,所以公文在網(wǎng)上傳輸時(shí)安全問(wèn)題變得特別重要.數(shù)字簽名是主要的密碼技術(shù)之一,數(shù)字簽名使得信息的接收者能夠驗(yàn)證信息來(lái)源的真實(shí)性、驗(yàn)證信息是否完整,還提供了不可抵賴性,該特性能夠保證信息的發(fā)送者無(wú)法否認(rèn)自己確實(shí)發(fā)送了這個(gè)信息,公文的傳輸采用數(shù)字簽名技術(shù)能夠保證公文在傳輸過(guò)程中不被違法者截取、任意修改、刪除、以及不被違法者冒充生成并發(fā)送.

例如:公文發(fā)送者A和公務(wù)接收者B之間完成一種公文簽名及傳輸?shù)牧鞒倘鐖D2所示.

圖2 公文簽名和傳輸過(guò)程

公文發(fā)送者A的過(guò)程:

(1)A要選取散列函數(shù)SHA-1和橢圓曲線參數(shù)T=(q,a,b,G,n,b)發(fā)給接收者;

(2)A根據(jù)T產(chǎn)生自己的私鑰dA,計(jì)算公鑰QA=dAG,并分別將公鑰發(fā)給CA;

(3)A從CA那獲取B的公鑰QB,計(jì)算共享密鑰key=dAQB;

(4)用共享密鑰加密A所需要發(fā)給B的公文M,得出密文C,e=S HA-1(C);

(5)A選擇一個(gè)隨機(jī)數(shù)k,k∈[1,n-1];

(7)計(jì)算s=k-1(e+dAr)modn,若s=0,返回(5);

(8)將(r,s,C)發(fā)給B.

公文接受者B的過(guò)程:

(1)從A那獲得散列函數(shù)SHA-1和橢圓曲線參數(shù)T=(q,a,b,G,n,b);

(2)利用橢圓曲線參數(shù)生成自己私鑰dB,計(jì)算公鑰QB=dBG,并將公鑰發(fā)給CA中心;

(3)從CA中心獲取A的公鑰QA,計(jì)算共享密鑰key=dBQA,因?yàn)閗ey=dAQB=dBQA;

(4)對(duì)A發(fā)過(guò)來(lái)的(r,s,C),分解得簽名(r,s)和密文C;

(5)驗(yàn)證s,r是否為(1,n-1)間的整數(shù),若是,則繼續(xù),否則無(wú)效;

(6)B利用散列函數(shù)對(duì)C產(chǎn)生摘要e=SHA-1(C);

(7)計(jì)算w=s-1modn;計(jì)算u1=ewmodn,u2=rwmodn;

(8)利用A的公鑰QA計(jì)算X=u1G+u2QA,如果X=O表示簽名無(wú)效;否則X=(x1,y1)計(jì)算v=x1modn;

(9)若r=v,則接受該簽名,用共享密鑰key解密C,得M.

整個(gè)過(guò)程可以保證在公文傳輸過(guò)程中,滿足了信息安全的所有目標(biāo).身份認(rèn)證性:簽名時(shí),使用私鑰加密,公鑰解密,就可以確認(rèn)消息是否由私鑰的所有者發(fā)出;數(shù)據(jù)完整性:生成簽名(r,s),然后將(r,s,C)作為一個(gè)混合的整體數(shù)據(jù)發(fā)給接受方,不可能篡改,從而保證了數(shù)據(jù)的完整性,保證了內(nèi)容不被篡改;不可否認(rèn)性:發(fā)送者不可能事后否認(rèn)他發(fā)送過(guò)的信息,信息的接受方可以向CA證實(shí)發(fā)送方確實(shí)發(fā)送了信息;防止偽造:其他人不能偽造對(duì)信息的簽名,因?yàn)樗借€只有簽名者自己知道.

3 結(jié) 論

政府在網(wǎng)上辦公已經(jīng)成為一種趨勢(shì),但是在公文的傳輸和簽名中,安全性和效率是制約其發(fā)展的重要因素之一,因此一個(gè)安全的公文傳輸解決方案是非常必要的.本文首先對(duì)組成橢圓曲線密碼系統(tǒng)的點(diǎn)乘算法的效率進(jìn)行提高,然后利用橢圓曲線密碼體制來(lái)實(shí)現(xiàn)公文的數(shù)字簽名,同時(shí)采用共享密鑰對(duì)發(fā)送的公文進(jìn)行加密,滿足了電子政務(wù)系統(tǒng)的安全性要求,解決了認(rèn)證性、機(jī)密性、完整性、不可否認(rèn)性,使得安全性、有效性均得到了提高.

[1]Qiu Qizhi,Xiong Qianxing.Research on Elliptic Curve Cryptograph[J].The 8th International Conference on Computer Supported Cooperative Work in Design Proceedings,2004:698-701.

[2]Rahim Ali.Elliptic Curve Cryptography A New Way for Encryption[J].International Symposium on Biometric and Security Technologies,2008:1-5.

[3]劉雙根,李 萍,胡予濮.橢圓曲線密碼中標(biāo)量算法的改進(jìn)方案[J].計(jì)算機(jī)工程,2006,32(17):28-29.

[4]Wang Bangju,Zhang Huanguo,Wang Yuhua.An Efficient Elliptic Curves Scalar Multiplication for Wireless Network[J].2007 IFIP Intermational Conference on Network and Parallel Computing Workshops,2007:131-134.

[5]Daisuke Adachi,Tomio Hirata.Combination of Mixed Coordinates Strategy and Direct Computations for Efficient Scalar M ultiplications[J].2005 IEEE Pacific Rim Conference on Communications,Computers and Signal Processing,2005:117-120.