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

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

0 引言

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

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

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

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

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

橢圓曲線密碼體制與1986年提出，經(jīng)過(guò)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來(lái)模擬ElGamal類離散對(duì)數(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)證不通過(guò)；

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

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

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)證通過(guò)，否則驗(yàn)證不通過(guò)。

本文對(duì)ECDSA-SM2正確性的證明說(shuō)下：

ECDSA-SM2的簽名和驗(yàn)證依賴于橢圓曲線上的兩個(gè)點(diǎn)(x1,y1)與(x1′,y1′)這兩個(gè)點(diǎn)應(yīng)該是相等的，如果簽名結(jié)果沒(méi)有被非法篡改過(guò)，應(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ù)字簽名算法的對(duì)比分析

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

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

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

(2) ECDLP問(wèn)題

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

(3) 哈希算法

在ECDSA中，沒(méi)有規(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)、對(duì)哈希算法的規(guī)定、以及同一樣攻擊ECDSA都需要解決兩個(gè)橢圓曲線離散對(duì)數(shù)問(wèn)題，總的來(lái)說(shuō)，ECDSA-SM2和 ECDSA的安全性是同一個(gè)級(jí)別的，但安全性要高于 ECDSA，是一種可以信賴的安全算法。

4 結(jié)語(yǔ)

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

[1]國(guó)家密碼管理局.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],張煥國(guó)等譯.北京：電子工業(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é)報(bào).2008.

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

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