國密SM2數(shù)字簽名算法與ECDSA算法對比分析研究

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

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

0 引言

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

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

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

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

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

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

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

ECDSA簽名的生成：

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

輸出：簽名(r,s)。

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

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

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

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

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

(6) 返回(r,s)。

ECDSA簽名的驗證：

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

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

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

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

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

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

(5) 計算X= u1P+ u2Q；

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

(7) 將X的x坐標轉化為整數(shù)z，計算v=z mod n；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2) ECDLP問題

在簽名的產(chǎn)生過程中，ECDSA和ECDSA-SM2中都存一個隨機數(shù)k，攻擊者由于不知道k和dA，需要解決兩個橢圓曲線離散對數(shù)問題，在計算上是不可行的，可以認為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相當，但高于MD5、SHA-1、SHA-224。

(4) 安全性

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

4 結語

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

[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ù)乘算法與混合加密的研究與實現(xiàn)[D].云南師范大學碩士論文.2008.

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

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

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

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