張 賀,孫 旭,吳婷婷
(成都理工大學(xué) 信息科學(xué)與技術(shù)學(xué)院,成都 610059)
·計算機(jī)及網(wǎng)絡(luò)技術(shù)應(yīng)用·
基于橢圓曲線的數(shù)字簽名快速算法研究
張 賀,孫 旭,吳婷婷
(成都理工大學(xué) 信息科學(xué)與技術(shù)學(xué)院,成都 610059)
橢圓曲線密碼;數(shù)字簽名;快速驗證
數(shù)字簽名技術(shù)是電子商務(wù)和安全認(rèn)證的重要技術(shù)之一,主要用于防止偽造、抵賴、冒充和篡改等安全問題,可以保證數(shù)據(jù)在網(wǎng)絡(luò)傳輸過程中的完整性和不可否認(rèn)性[1]。目前使用的數(shù)字簽名算法主要有整數(shù)因子分解算法(RSA)、離散對數(shù)算法(DSA)、橢圓曲線離散對數(shù)算法(ECDSA)等。
Koblitz[2]和Miller[3]在1985年提出了橢圓曲線密碼體制,它可以使用較短的密鑰獲得較高的安全性,使用比RSA短得多的密鑰就可以達(dá)到相同的安全系數(shù),在運(yùn)算能力、存儲量、帶寬和軟硬件條件受限的情況下,橢圓曲線密碼體制更容易實現(xiàn),并具有更高的安全性。例如,橢圓曲線算法使用160 bit密鑰就可以實現(xiàn)RSA算法使用1 024 bit密鑰提供的安全性[4]。
橢圓曲線數(shù)字簽名算法是數(shù)字簽名算法的橢圓曲線版本。最廣泛、標(biāo)準(zhǔn)化的橢圓曲線數(shù)字簽名包括ANSI X9.62、FIPS186-2、IEEE1363-2000和ISO/IEC15946-2標(biāo)準(zhǔn),以及一些標(biāo)準(zhǔn)的草案[5]。國內(nèi)外學(xué)者研究的重點(diǎn)傾向于如何獲得更高的計算效率。本文從簽名和驗證算法方案的角度研究如何提高計算效率,并使用軟件進(jìn)行驗證。
橢圓曲線密碼體制使用的是變元和系數(shù)均為有限域中元素的橢圓曲線。密碼應(yīng)用中所使用的兩類橢圓曲線是定義在GF(p)上的素曲線和在GF(2m)上構(gòu)造的二元曲線[6]。其中,GF(p)上的橢圓曲線更適合加密、更容易軟件實現(xiàn)[7],因此,主要介紹素域的橢圓曲線密碼。
對于GF(p)上的橢圓曲線,其變元和系數(shù)均在GF(p)里取值,方程形式如下:
y2modp=(x3+ax+b)modp
式中:p是一個大素數(shù);a、b是兩個小于p的非負(fù)整數(shù),滿足條件:
(4a3+27b2)modp≠0modp
Ep(a,b)表示素域上的橢圓曲線群,是指素域上方程的解集和一個無窮遠(yuǎn)點(diǎn)O構(gòu)成的點(diǎn)集。對橢圓曲線上任意點(diǎn)P,Q∈Ep(a,b)有:
1)P+O=P,O為加法單位元;
2)如果P=(xp,yp),則點(diǎn)(xp,-yp)是P的負(fù)元,記為-P;
3)點(diǎn)加。若有點(diǎn)P=(x1,y1)和點(diǎn)Q=(x2,y2),且P≠-Q,則有點(diǎn)R=(x3,y3)使R=P+Q,其中,
4)點(diǎn)乘或倍乘。點(diǎn)p=(x1,y1),p≠-p,則2p=(x3,y3),其中,
2.1 數(shù)字簽名概述
普通的物理簽名代表著一個人的身份和所獲得的權(quán)限。普通的物理簽名可通過模仿筆跡偽造簽名,而數(shù)字簽名則是只有信息發(fā)送者才能產(chǎn)生,別人不可偽造的消息摘要,數(shù)字簽名的大概流程如圖1所示。
圖1 數(shù)字簽名流程
1)簽名過程。(1)發(fā)送者將原文通過Hash算法計算得到數(shù)據(jù)摘要,將數(shù)據(jù)摘要加密得到數(shù)字簽名;(2)將獲得的簽名和原文一起發(fā)送給接受者。
2)驗證過程。(1)將接收到的簽名用相應(yīng)的公鑰解密得到數(shù)據(jù)摘要;(2)接收的原文通過Hash算法計算得到數(shù)據(jù)摘要,如果兩個摘要相同,則驗證成功,否則驗證失敗。
要保證實際應(yīng)用的安全,數(shù)字簽名還必須滿足以下條件:
1)防止偽造性。數(shù)字簽名可以使接受者確定發(fā)送者的身份從而確定消息的正確性。
2)數(shù)據(jù)完整性。數(shù)字簽名是通過將要發(fā)送的消息進(jìn)行運(yùn)算形成消息摘要而獲得的,接受方可以通過驗證判斷消息是否在傳輸過程中被修改,從而保證消息的完整性。
3)不可抵賴性。數(shù)字簽名可以證明消息的來源,接受方可以判斷出消息發(fā)送者從而防止發(fā)送方的抵賴行為。
4)如果收發(fā)雙方對數(shù)字簽名的真假存在異議,則有可靠第三方(如CA)協(xié)調(diào)解決。
2.2 橢圓曲線數(shù)字簽名算法
目前,數(shù)字簽名中使用較為廣泛的公鑰加密體制是RSA算法,然而,隨著計算機(jī)運(yùn)算能力的快速提升,RSA算法越來越不能滿足數(shù)字簽名安全度的要求。橢圓曲線密碼算法的密鑰短、速度快、適用于軟硬件受限的情況,因此,橢圓曲線密碼算法在數(shù)字簽名中應(yīng)用越來越廣泛?;跈E圓曲線密碼體制的數(shù)字簽名算法是橢圓曲線數(shù)字簽名算法(ECDSA)[8]。
ECDSA主域參數(shù)有:
D=(q,FR,a,b,G,n,h)
1)選擇素數(shù)域GF(p),q=p;
2)一個域表示法FR來表示域中的元素;
3)a和b表示GF(p)域中的兩個元素;
4)G為橢圓曲線上的基點(diǎn),用域上的xG和yG兩個元素來定義;
6)余因子h。
另外,還有消息摘要算法哈希函數(shù)SHA-1或SHA-256。
令橢圓曲線的基點(diǎn)為G(x1,y1)時,橢圓曲線數(shù)字簽名的算法如下[9]:
1)生成簽名算法
(1)選擇隨機(jī)數(shù)或偽隨機(jī)數(shù)k∈[1,n-1];
(2)計算R=kG(x1,y1),得到R橫坐標(biāo)為X;
(3)計算r=Xmodn,如果r=0,則返回1;
(4)計算k-1modn;
(5)e=SHA-1(m),m為所發(fā)送的消息;
(6)計算s=k-1(e+dr)modn,如果s=0,則返回1;
(7)對消息的簽名為(r,s),將(r,s,m)發(fā)送給接收方。
2)接收方接收到簽名和消息后,驗證算法
(1)驗證r和s是[1,n-1]內(nèi)的整數(shù);
(2)計算e=SHA-1(m);
(3)計算w=s-1modn;
(4)計算u1=ewmodn,u2=rwmodn;
(5)計算R=u1G+u2Q;
(6)如果R=0,驗證失敗,否則,R=(X1,Y1),計算v=X1modn;
(7)如果v=r,驗證成功。
3.1 改進(jìn)的橢圓曲線數(shù)字簽名
ECDSA一般是用(s,e,r)去置換簽名方程xk=y+dzmodn中的(x,y,z),得到sk=e+drmodn,從而計算出s,形成簽名信息(r,s)。改進(jìn)算法用(1,s+e+r,1)去置換簽名方程,得到s=k-e-r-d。則改進(jìn)的快速數(shù)字簽名算法步驟如下:[10]
1)從橢圓曲線上獲得主域參數(shù)
D=(q,FR,a,b,G,n,h)
2)簽名過程
(1)選擇一個隨機(jī)數(shù)k∈[1,n-1];
(2)計算kG=(X1,Y1),r=X1modn,如果r=0,返回1;
(3)計算e=SHA-1(m),m為明文;
(4)計算s=k-e-r-d,如果s=0,則返回1;
(5)傳送消息m和簽名(r,s)。
3)驗證過程
(1)驗證r和s是[1,n-1]內(nèi)的整數(shù);
(2)計算e=SHA-1(m);
(3)計算w=s+e+rmodn;
(4)計算R=wG+Q=kG=(X1,Y1),如果R=0,則簽名無效;否則,計算v=X1modn;
(5)如果v=r,則接受簽名;否則,簽名無效。
3.2 改進(jìn)算法分析
3.2.1 改進(jìn)的簽名算法正確性分析
簽名方程:
k=s+e+r+dmodn
s=k-e-r-d
對應(yīng)的驗證方程:
R= (s+e+r)G+Q=
(k-e-r-d+e+r)G+dG=
(k-d)G+dG=kG
因此,改進(jìn)的簽名算法可以正確完成簽名和驗證過程。
3.2.2 改進(jìn)算法耗時分析
在ECDSA算法中,主要耗時是模乘、模逆和標(biāo)量乘,本文分別用[M]、[I]和[S]表示,其他的加減運(yùn)算可以忽略不計。在文獻(xiàn)[11]中,分析了三種運(yùn)算的耗時比例,可以得到[I]=9[M]和[S]≈173[M]+75[I]=848[M]。
經(jīng)典ECDSA算法在簽名過程進(jìn)行了1次模乘、2次模逆和1次標(biāo)量乘,則耗時為N1=[M]+18[M]+848[M]=867[M];在驗證過程進(jìn)行了1次模逆、2次模乘和2次標(biāo)量乘,則耗時為N2=1 696[M]+2[M]+9[M]=1 707[M],總共耗時為N=N1+N2=2 564[M]。
改進(jìn)ECDSA算法在簽名過程僅進(jìn)行了1次標(biāo)量乘,與經(jīng)典ECDSA算法相比避免了模乘和模逆,耗時為N1=848[M];在驗證過程也只進(jìn)行了1次標(biāo)量乘,同樣避免了模乘和模逆,耗時為N2=848[M],總耗時為N=1 696[M]。
3.3 改進(jìn)的數(shù)字簽名的驗證實現(xiàn)
為了比較兩種算法實際耗時,可以利用軟件進(jìn)行測試。橢圓曲線數(shù)字簽名算法的軟件實現(xiàn)已經(jīng)成熟,在Windows平臺下能夠友好地顯示用戶界面,使用vs2008運(yùn)行完整的軟件,根據(jù)改進(jìn)的數(shù)字簽名算法過程,使用C++語言編寫快速數(shù)字簽名的簽名和驗證過程代碼,替換到軟件代碼中,并利用clock()函數(shù)分別獲得簽名過程和驗證過程的程序執(zhí)行時間。改進(jìn)的數(shù)字簽名算法的關(guān)鍵代碼如下:
1)簽名過程
Point P;BigInteger k,temp1(1); L:srand(unsigned(GetTickCount())); k=temp1+Rand(n-temp1);
P=G;P=Point_Multiply(G,k);
s=k-e-r-d;
if(Compare(s)){goto L;}
2)驗證過程
BigInteger temp1(1);
if(Compare(r,n-temp1)||Compare(s,n-temp1))
{return false;}
if(Compare(w)){return false;}
Point R,R1;
R1=Point_Multiply(G,w);
R=Point_Calculate(R1,Q);
if(Compare(R.x)&&Compare(R.y))
{return false;}
if(Compare(v,r)){return false;}
return ture;軟件在搭載intel酷睿雙核、主頻為2.1 GHz的處理器T6500的計算機(jī)上運(yùn)行結(jié)果如圖2所示。首先,生成橢圓曲線的主域參數(shù)D=(q,FR,a,b,G,n,h);然后,生成公鑰Q和私鑰d;最后進(jìn)行簽名和驗證并得到簽名和驗證的時間共0.098 s。
圖2 改進(jìn)后軟件測試結(jié)果
表1 算法程序執(zhí)行的時間比較 s
[1]趙澤茂.數(shù)字簽名理論[M].北京:科技出版社,2007:23-45.
[2] Koblitz N. Elliptic curve cryptosystems[J]. Mathematics of Computation,1987,48(177):203-209.
[3] Miller V. Uses of elliptic curves in crytography[C]//Advances in Cryptology-CRYPTO'85,LNCS218. Santa Barbara, Calif:Springer-Verlag, 1986:417-426.
[4] 王暉,張方國,王育民. 大素數(shù)域上橢圓曲線密碼體制的軟件實現(xiàn)[J]. 西安電子科技大學(xué)學(xué)報:自然科學(xué)版,2002,29(3):426-428.
[5] 蔡永泉.數(shù)字鑒別與認(rèn)證[M].北京:北京航空航天大學(xué)出版社, 2011.
[6] William Stallings.密碼編碼學(xué)與網(wǎng)絡(luò)安全——原理與實踐[M].5版.北京:電子工業(yè)出版社,2012:222-223.
[7] 張鵬.ECC橢圓曲線加密算法在軟件注冊中的應(yīng)用[D].太原:太原理工大學(xué),2010:43-45.
[8] 張巖.基于橢圓曲線的數(shù)字簽名算法研究[D].成都:西南交通大學(xué),2010:25-26.
[9] 羅濤,易波.關(guān)于橢圓曲線數(shù)字簽名算法研究[J].計算機(jī)工程與應(yīng)用,2003(29):184-187.
[10] 陳亮,橢圓曲線數(shù)字簽名算法的優(yōu)化和軟件實現(xiàn)[D].杭州:杭州電子科技大學(xué),2011:34-37.
Research of Digital Signature Algorithm Based on Elliptic Curve
ZHANG He,SUN Xu,WU Tingting
(College of Information Science and Technology,Chengdu University of Technology,Chengdu 610059,China)
elliptic curve code;digital signature;fast verification
2013-10-15
張 賀(1990-),男,碩士研究生,研究方向:通信網(wǎng)絡(luò)與信息安全技術(shù)。
TP311.1;TN918.4
A
10.3969/j.issn.1672-4550.2014.06.014