孫榮燕 蔡昌曙 周洲 趙燕杰 楊金銘

云南省電子政務(wù)網(wǎng)絡(luò)管理中心 云南 650228

0 引言

在商用密碼領(lǐng)域，中國使用國際標(biāo)準(zhǔn)的密碼算法和自主定義的密碼算法，但是對于自主定義的密碼算法，沒有公布。沒有公布的密碼算法其算法沒有經(jīng)過國際國內(nèi)的廣泛論證，在算法的正確性、效率、安全性等方面都很難得到人們的廣泛認(rèn)可。國際密碼學(xué)領(lǐng)域普遍的觀點(diǎn)認(rèn)為，如果算法不公開就很難評估算法的安全性。而且由于公開的算法會得到更多人的關(guān)注，包括密碼分析領(lǐng)域的專家和一些有組織或無組織的密碼攻擊單位或個人。這樣如果該公開的算法能夠經(jīng)受住考驗(yàn)，則說明其安全性是可以信賴的。

在市場方面，由于國外廠商得不到國密算法，無法進(jìn)入國內(nèi)商密領(lǐng)域，對中國政府施壓，而國內(nèi)的密碼廠商由于使用了國密算法，而國密算法不公開，得不到國際上的承認(rèn)，也無法進(jìn)入國際市場，被困在了國內(nèi)市場。

2010年12月，為滿足電子認(rèn)證服務(wù)系統(tǒng)等應(yīng)用需求，在國家商用密碼管理管理辦公室發(fā)布了國家密碼管理局公告(第21號)，發(fā)布SM2橢圓曲線公鑰密碼算法。加上原來的SM1商密對稱算法，中國自主定義的算法終于開始以自信、大方的姿態(tài)走上商用密碼舞臺。

信息安全從來都是一個國家必須守衛(wèi)的數(shù)字領(lǐng)地，如同守衛(wèi)我們的疆土一樣。而信息的安全并不完全取決于算法是否公開，更重要的是算法要足夠安全和可靠。

1 橢圓曲線數(shù)字簽名算法ECDSA

橢圓曲線密碼體制與1986年提出，經(jīng)過20多年的理論研究與應(yīng)用研究，已經(jīng)走向成熟，并將逐步取代RSA密碼體制，成為公鑰密碼算法的主流算法。ECC算法有基于素?cái)?shù)域Fp域和基于二進(jìn)制域F2m上的。二進(jìn)制域F2m上的橢圓曲線是指 E/F2m： y2+xy =x3+ax2+b，a，b∈F2m。數(shù)乘算法是ECC的核心算法，ECC數(shù)乘算法參加文獻(xiàn)。

可以利用ECC來模擬ElGamal類離散對數(shù)體制的數(shù)字簽名。橢圓曲線數(shù)字簽名算法(ECDSA)是數(shù)字簽名算法的(DSA)的橢圓曲線版本。

ECDSA簽名的生成：

輸入：參數(shù)組D(q, FR, S, a,b,P,n,h)，私鑰d,消息m。

輸出：簽名(r,s)。

(1) 選擇隨機(jī)數(shù)k∈[1,n-1]；

(2) 計(jì)算 kP=(x1,y1)，并將x1轉(zhuǎn)化為整數(shù)z；

(3) 計(jì)算 r=z mod n，若r=0，跳至步驟1；

(4) 計(jì)算 e=H(m)；

(5) 計(jì)算 s= k-1(e+dr) mod n。若s=0，則跳至步驟1；

(6) 返回(r,s)。

ECDSA簽名的驗(yàn)證：

輸入：參數(shù)組D(q, FR, S, a, b, P, n, h)，公鑰Q,消息m，簽名(r,s)。

輸出：判斷簽名是否合法。

(1) 檢驗(yàn) r，s∈[1,n-1]，若不成立，返回拒絕簽名；

(2) 計(jì)算 e=H(m)；

(3) 計(jì)算w=s-1mod n；

(4) 計(jì)算 u1=ew mod n和u2=rw mod n；

(5) 計(jì)算X= u1P+ u2Q；

(6) 若 X=∞ ，返回(“拒絕該簽名”)；

(7) 將X的x坐標(biāo)轉(zhuǎn)化為整數(shù)z，計(jì)算v=z mod n；

(8) 若v=r，則返回(“接受該簽名”)，否則返回(“拒絕該簽名”)。

2 SM2橢圓曲線數(shù)字簽名算法

在 SM2橢圓曲線公鑰算法的第二部分：數(shù)字簽名算法中，定義SM2橢圓曲線數(shù)字簽名算法(本文定義為ECDSASM2)為：設(shè)待簽名的消息為M，為了獲得M的數(shù)字簽名，作為簽名用戶A實(shí)現(xiàn)以下步驟：

A3： 用隨機(jī)數(shù)發(fā)生器產(chǎn)生隨機(jī)數(shù)k∈[1,n-1]；

A4： 計(jì)算橢圓曲線點(diǎn) (x1,y1) = kG，將x1轉(zhuǎn)化為整數(shù)；

A5： 計(jì)算r=(e + x1) mod n，若r=0或者 r + k = n，則返回A3；

A6： 計(jì)算 s=(1 + dA )-1·(k - r·dA)mod n，若s = 0，則返回 A3；

A7： 將轉(zhuǎn)化為字節(jié)串，消息M的簽名為(r,s)。

數(shù)字簽名驗(yàn)證算法：

為了驗(yàn)證收到的消息M′及其數(shù)字簽名(r′，s′)，作為驗(yàn)證者用戶B實(shí)現(xiàn)以下運(yùn)算步驟：

B1： 檢驗(yàn)r′∈[1,n-1]是否成立，若不成立驗(yàn)證不通過；

B2： 檢驗(yàn)s′∈[1,n-1]是否成立，若不成立驗(yàn)證不通過；

B5： 將 r′， s′轉(zhuǎn)化為整數(shù)，計(jì)算 t = (r′+s′) mod n，若t = 0，則驗(yàn)證不能通過；

B6： 計(jì)算橢圓曲線點(diǎn)(x1′,y1′)= s′G + tPA;

B7： 將 x1′轉(zhuǎn)化為整數(shù)，計(jì)算 R=(e′+ x1′)mod n，檢驗(yàn)R=r′是否成立，若成立，驗(yàn)證通過，否則驗(yàn)證不通過。

本文對ECDSA-SM2正確性的證明說下：

ECDSA-SM2的簽名和驗(yàn)證依賴于橢圓曲線上的兩個點(diǎn)(x1,y1)與(x1′,y1′)這兩個點(diǎn)應(yīng)該是相等的，如果簽名結(jié)果沒有被非法篡改過，應(yīng)該有(r′，s′)=(r,s)。

下面證明(x1,y1)=(x1′, y1′)：

因?yàn)?r=(e + x1) mod n，s=(1 + dA )-1·(k - r·dA)mod n，所以(x1′, y1′)=s′G + tPA = s′G + (r′+s′)· dA G = (1 + dA)s′G +r′·dA G=(1+dA)(1+dA)-1(k-rdA)G+r′dAG =(k-rdA)G+r′dAG=KG=(x1,y1)

3 ECDSA與SM2橢圓曲線數(shù)字簽名算法的對比分析

ECDSA與ECDSA-SM2兩個數(shù)字簽名算法都是基于相同的橢圓曲線(如素?cái)?shù)域與二進(jìn)制域)，它們的安全性都是基于橢圓曲線離散對數(shù)問題求解的困難性。ECDSA已經(jīng)成為了國際標(biāo)準(zhǔn)，其依賴的橢圓曲線可以使用NIST等推薦的曲線，而SM2并沒有給出推薦的曲線，曲線參數(shù)的產(chǎn)生需要利用一定的算法產(chǎn)生。下面就ECDSA與ECDSA-SM2進(jìn)行分析對比：

(1) 對待簽名信息的預(yù)處理

在 ECDSA中，對待簽名消息 M 不做任何處理，而在ECDSA-SM2中，待簽名信息預(yù)處理為=ZA || M，ZA=(ENTLA || IDA || a || b || xG || yG || xG || yG)，需要串接用戶自身的一些信息和曲線的參數(shù)、基點(diǎn)、用戶的公鑰點(diǎn)信息，明顯對待簽名信息的預(yù)處理中包含了簽名者自身的信息等，安全性大大提高，抗抵賴性更強(qiáng)。

(2) ECDLP問題

在簽名的產(chǎn)生過程中，ECDSA和ECDSA-SM2中都存一個隨機(jī)數(shù)k，攻擊者由于不知道k和dA，需要解決兩個橢圓曲線離散對數(shù)問題，在計(jì)算上是不可行的，可以認(rèn)為ECDSA-SM2和ECDSA的安全性是同一個級別的。

(3) 哈希算法

在ECDSA中，沒有規(guī)定其中使用哈希算法，可以選擇MD5、SHA-1、SHA-224、SHA-256，SHA-384 和 SHA-512，而ECDSA-SM2中規(guī)定使用的哈希算法為SM3，SM3輸出的比特串為256位。SM3的安全性基本上與SHA-256相當(dāng)，但高于MD5、SHA-1、SHA-224。

(4) 安全性

由于ECDSA-SM2在待簽名信息的預(yù)處理特點(diǎn)、對哈希算法的規(guī)定、以及同一樣攻擊ECDSA都需要解決兩個橢圓曲線離散對數(shù)問題，總的來說，ECDSA-SM2和 ECDSA的安全性是同一個級別的，但安全性要高于 ECDSA，是一種可以信賴的安全算法。

4 結(jié)語

ECDSA-SM2和ECDSA都基于橢圓曲線的離散對數(shù)問題，雖然在算法的具體實(shí)現(xiàn)細(xì)節(jié)上面不同，但是算法的基本思想是相同的，總的來說，ECDSA-SM2和 ECDSA的安全性是同一個級別的，但安全性要高于 ECDSA，是一種可以信賴的安全算法。ECDSA算法已經(jīng)成為了一種國際標(biāo)準(zhǔn)算法，廣泛應(yīng)用于安全軟硬件上面，而ECDSA-SM2在國內(nèi)商密應(yīng)用領(lǐng)域已經(jīng)廣泛使用多年，隨著SM2算法的公布， SM2將經(jīng)受嚴(yán)格的論證和驗(yàn)證，SM2將有望成為成為一種國際標(biāo)準(zhǔn)，這將大大推動SM2的廣泛應(yīng)用。

[1]國家密碼管理局.SM2橢圓曲線公鑰密碼算法.http：//www.oscca.gov.cn/UpFile/2010122214822692.pdf,2012.

[2]V.S.Miller.Use of Elliptic Curves in Cryptography.Advances in Cryptology-CRYPTO'85,H.C.Williams, Ed., LNCS 218 Springer-Verlag.1986.

[3]Darrel Hankerson, Alfred Menezes, scott Vanstone.Guide to Elliptic Curve Cryptography[M],張煥國等譯.北京：電子工業(yè)出版社.2005.

[4]蔡昌曙.基于F2m域的圓錐曲線數(shù)乘算法與混合加密的研究與實(shí)現(xiàn)[D].云南師范大學(xué)碩士論文.2008.

[5]蔡昌許,蔡昌曙.橢圓曲線密碼體制中的一種改進(jìn)數(shù)乘快速算法[J].實(shí)驗(yàn)科學(xué)與技術(shù).2008.

[6]蔡昌許,蔡昌曙.F2m域上圓錐曲線密碼體制的曲線參數(shù)選取和混合加密[J].曲靖師范學(xué)院學(xué)報.2008.

[7]蔡昌許,蔡昌曙.NAF-2k圓錐曲線數(shù)乘算法[J].曲靖師范學(xué)院學(xué)報.2009.

[8]Johnson, Menezes, Vanstoone.The elliptic curve digital signature algorithm (ECDSA).International Journal of Information Secutrity.2001.