国密SM2数字签名算法与ECDSA算法对比分析研究

孙荣燕 蔡昌曙 周洲 赵燕杰 杨金铭

云南省电子政务网络管理中心 云南 650228

0 引言

在商用密码领域，中国使用国际标准的密码算法和自主定义的密码算法，但是对于自主定义的密码算法，没有公布。没有公布的密码算法其算法没有经过国际国内的广泛论证，在算法的正确性、效率、安全性等方面都很难得到人们的广泛认可。国际密码学领域普遍的观点认为，如果算法不公开就很难评估算法的安全性。而且由于公开的算法会得到更多人的关注，包括密码分析领域的专家和一些有组织或无组织的密码攻击单位或个人。这样如果该公开的算法能够经受住考验，则说明其安全性是可以信赖的。

在市场方面，由于国外厂商得不到国密算法，无法进入国内商密领域，对中国政府施压，而国内的密码厂商由于使用了国密算法，而国密算法不公开，得不到国际上的承认，也无法进入国际市场，被困在了国内市场。

2010年12月，为满足电子认证服务系统等应用需求，在国家商用密码管理管理办公室发布了国家密码管理局公告(第21号)，发布SM2椭圆曲线公钥密码算法。加上原来的SM1商密对称算法，中国自主定义的算法终于开始以自信、大方的姿态走上商用密码舞台。

信息安全从来都是一个国家必须守卫的数字领地，如同守卫我们的疆土一样。而信息的安全并不完全取决于算法是否公开，更重要的是算法要足够安全和可靠。

1 椭圆曲线数字签名算法ECDSA

椭圆曲线密码体制与1986年提出，经过20多年的理论研究与应用研究，已经走向成熟，并将逐步取代RSA密码体制，成为公钥密码算法的主流算法。ECC算法有基于素数域Fp域和基于二进制域F2m上的。二进制域F2m上的椭圆曲线是指 E/F2m： y2+xy =x3+ax2+b，a，b∈F2m。数乘算法是ECC的核心算法，ECC数乘算法参加文献。

可以利用ECC来模拟ElGamal类离散对数体制的数字签名。椭圆曲线数字签名算法(ECDSA)是数字签名算法的(DSA)的椭圆曲线版本。

ECDSA签名的生成：

输入：参数组D(q, FR, S, a,b,P,n,h)，私钥d,消息m。

输出：签名(r,s)。

(1) 选择随机数k∈[1,n-1]；

(2) 计算 kP=(x1,y1)，并将x1转化为整数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签名的验证：

输入：参数组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坐标转化为整数z，计算v=z mod n；

(8) 若v=r，则返回(“接受该签名”)，否则返回(“拒绝该签名”)。

2 SM2椭圆曲线数字签名算法

在 SM2椭圆曲线公钥算法的第二部分：数字签名算法中，定义SM2椭圆曲线数字签名算法(本文定义为ECDSASM2)为：设待签名的消息为M，为了获得M的数字签名，作为签名用户A实现以下步骤：

A3： 用随机数发生器产生随机数k∈[1,n-1]；

A4： 计算椭圆曲线点 (x1,y1) = kG，将x1转化为整数；

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： 将转化为字节串，消息M的签名为(r,s)。

数字签名验证算法：

为了验证收到的消息M′及其数字签名(r′，s′)，作为验证者用户B实现以下运算步骤：

B1： 检验r′∈[1,n-1]是否成立，若不成立验证不通过；

B2： 检验s′∈[1,n-1]是否成立，若不成立验证不通过；

B5： 将 r′， s′转化为整数，计算 t = (r′+s′) mod n，若t = 0，则验证不能通过；

B6： 计算椭圆曲线点(x1′,y1′)= s′G + tPA;

B7： 将 x1′转化为整数，计算 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椭圆曲线数字签名算法的对比分析

ECDSA与ECDSA-SM2两个数字签名算法都是基于相同的椭圆曲线(如素数域与二进制域)，它们的安全性都是基于椭圆曲线离散对数问题求解的困难性。ECDSA已经成为了国际标准，其依赖的椭圆曲线可以使用NIST等推荐的曲线，而SM2并没有给出推荐的曲线，曲线参数的产生需要利用一定的算法产生。下面就ECDSA与ECDSA-SM2进行分析对比：

(1) 对待签名信息的预处理

在 ECDSA中，对待签名消息 M 不做任何处理，而在ECDSA-SM2中，待签名信息预处理为=ZA || M，ZA=(ENTLA || IDA || a || b || xG || yG || xG || yG)，需要串接用户自身的一些信息和曲线的参数、基点、用户的公钥点信息，明显对待签名信息的预处理中包含了签名者自身的信息等，安全性大大提高，抗抵赖性更强。

(2) ECDLP问题

在签名的产生过程中，ECDSA和ECDSA-SM2中都存一个随机数k，攻击者由于不知道k和dA，需要解决两个椭圆曲线离散对数问题，在计算上是不可行的，可以认为ECDSA-SM2和ECDSA的安全性是同一个级别的。

(3) 哈希算法

在ECDSA中，没有规定其中使用哈希算法，可以选择MD5、SHA-1、SHA-224、SHA-256，SHA-384 和 SHA-512，而ECDSA-SM2中规定使用的哈希算法为SM3，SM3输出的比特串为256位。SM3的安全性基本上与SHA-256相当，但高于MD5、SHA-1、SHA-224。

(4) 安全性

由于ECDSA-SM2在待签名信息的预处理特点、对哈希算法的规定、以及同一样攻击ECDSA都需要解决两个椭圆曲线离散对数问题，总的来说，ECDSA-SM2和 ECDSA的安全性是同一个级别的，但安全性要高于 ECDSA，是一种可以信赖的安全算法。

4 结语

ECDSA-SM2和ECDSA都基于椭圆曲线的离散对数问题，虽然在算法的具体实现细节上面不同，但是算法的基本思想是相同的，总的来说，ECDSA-SM2和 ECDSA的安全性是同一个级别的，但安全性要高于 ECDSA，是一种可以信赖的安全算法。ECDSA算法已经成为了一种国际标准算法，广泛应用于安全软硬件上面，而ECDSA-SM2在国内商密应用领域已经广泛使用多年，随着SM2算法的公布， SM2将经受严格的论证和验证，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],张焕国等译.北京：电子工业出版社.2005.

[4]蔡昌曙.基于F2m域的圆锥曲线数乘算法与混合加密的研究与实现[D].云南师范大学硕士论文.2008.

[5]蔡昌许,蔡昌曙.椭圆曲线密码体制中的一种改进数乘快速算法[J].实验科学与技术.2008.

[6]蔡昌许,蔡昌曙.F2m域上圆锥曲线密码体制的曲线参数选取和混合加密[J].曲靖师范学院学报.2008.

[7]蔡昌许,蔡昌曙.NAF-2k圆锥曲线数乘算法[J].曲靖师范学院学报.2009.

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