国密SM2中k值选取的研究与改进

郇静 赵连军

摘要：区块链技术中的安全问题一部分取决于移动设备的能源算例和应用情况，这决定了设备会具有安全隐患，特别是智能卡等嵌入系统，它们特定应用情况下是无法支持随机源的，解决随机源选取问题从而加强密钥对的安全性是非常重要的。随着我国自主提出的公钥密码算法SM2的地位不断提高，该算法应用到设备和系统中是必然趋势，通过HMAC算法改进SM2签名生成中随机值k的选取方式，最终使SM2转换为确定性方案，提高嵌入式系统中随机源的质量，增加算法安全性，使之普遍适用。

关键词： SM2; HMAC; 随机源; ECDSA; ECC ;交易可锻性

中图分类号：TP9309.7        文献标识码：A

文章编号：1009-3044（2020）30-0054-03

Abstract：Part of the security problems in blockchain technology depend on the energy calculation examples and applications of mobile devices， which determines that devices will have security risks， especially embedded systems such as smart cards， which can not support random sources in specific applications. It is very important to solve the problem of random source selection so as to enhance the security of key pair. With the improvement of the status of public key cryptography algorithm SM2， which is proposed by our country， it is an inevitable trend to apply this algorithm to devices and systems. Through HMAC algorithm， we can improve the selection of random value K in SM2 signature generation， and finally transform SM2 into a deterministic scheme， improve the quality of random sources in embedded systems， increase the security of the algorithm， and make it universally applicable.

Key words：SM2; HMAC; random source ; ECDSA; ECC; transaction malleability

1 引言

自国家大力发展区块链技术以来，区块链技术在金融、政务、医疗等领域发挥着重要的作用。从中本聪创造的比特币问世，到第二代以太坊等各种区块链类型都会存在一个共性的问题——交易可锻性（Transaction Malleability），而这个问题是由区块链自身的特性决定的，是杜绝不了的，但可以规避它。在交易中，私钥等数据在发送之前对其进行加密和签名，接着最终获得哈希值为交易ID返回给用户。在验证交易的真实性时，大部分签名算法都是基于椭圆曲线数字签名算法（Elliptic Curve Digital Signature Algorithm ，ECDSA）[1]，它存在的一个问题是修改某个字节后而签名依然校验成功，交易依然能够成功进行，这就会导致非法攻击，使交易平台资金大量损失。

交易可锻性问题实质是加密和签名中的安全性问题。2010年底，我国国家密码管理局发布了SM2椭圆曲线公钥密码算法[2-6]，成为我国首个公钥密码算法标准，区块链中的密码学体系将逐渐被国密体系取代。SM2和ECDSA都采用了椭圆曲线密码体制（Elliptic Curve Cryptography，ECC）[7]，其中的数字签名技术应用广泛，电子商务和网络安全认证的核心技术就是数字签名，区块链技术其底层技术之一就是数字签名。相较其他公钥体制，椭圆曲线密码体制的主要优势是计算参数小，密钥更短[8]，运算速度更快，签名也更加短小[9]，效率也更高[10]，因此性能优良，应用广泛，尤其适用于存储空间、处理能力、带宽及功耗受限的场合[11]，比如智能卡嵌入设备、区块链应用设备等。

ECDSA是标准的数字签名方案，在各种协议中提供了真实的数据的完整性和可验证性。SM2作为与ECDSA同源的公钥密码算法，存在随机源k值的选取问题， 本文将对签名过程中的随机值k的选取进行改进，在随机选择的基础上加上HMAC算法，提高k值选取质量，增加加密和签名中随机源的安全性。

本文描述的方法过程具有以下特点：

（1）制定的签名与普通SM2完全兼容。验证签名的实体不需要更改，甚至不需要知道用于生成k的过程。

（2）密钥对的生成不会改变。现有的密钥对可以被用于确定性SM2。

（3）使用确定性SM2可以与普通的SM2应用在相同的输入上，即在要签名的消息上计算哈希值，使用安全加密哈希函數。

本文规定的确定性SM2定义采取了一些相对任意的选择;这样做是为了使它尽量普遍适用，以便最大化包含测试向量的有用性。

需要注意的是，密钥对的生成仍然需要一个随机源。在嵌入式系统的随机性是一个质量问题，它通常可以把生成密钥对发生在更多控制条件下，生成的关键可能是其他地方和进口设备。确定性SM2只处理签名生成时的随机性需要。

2 预备知识

国外标准中的数字签名算法有很多，我们用ECDSA来代表国外标准中基于ECC的数字签名算法。ECDSA中在Hash函数选取中没有明确规定，通常采用SHA-256。

SM2算法的密钥生成过程与ECDSA算法一致，但其签名及验证过程与ECDSA算法有一定的不同，在Hash函数的选取上，ECDSA没有明确指定，而SM2中规定使用SM3[12]哈希算法。SM2签名算法为：设待签名的消息为M，为了获得M的数字签名，作为签名用户A实现以下步骤：

SM2的一个特点是对于每一次签名生成，都需要产生一个新的随机值（以下称为k），为了有效性和安全性，k必须从一组模整数中随机并且一致的选取，并且整个过程使用加密安全。

对加密安全随机源的需求阻碍了SM2签名方案的部署。在加密算法系统中，RSA[13]签名算法用于指定的公开密钥加密标准PKCS#1[14][RFC3447]，它计算更昂贵，由于RSA（这种填充方案）是确定的，因此不需要随机性的来源。

SM2的随机性由于随机源的选取困难，使实现更难测试。自动测试无法可靠地检测是否使用了足够高质量的随机源。这使得实现过程更容易出现灾难性故障的攻击，而这种攻击通常是在系统部署并成功攻击之后才被发现的。

通过使用产生“随机”值k的确定性过程，可以将SM2转换为确定性方案。该过程必须满足一定的密码特性，才能维持签名方案的可验证性和不可伪造性，也就是说对于不知道签名私钥的人来说，从输入消息到对应的k值映射在计算上必须从随机且一致的选择函数（从消息集合到可能的k值集合）来返回。

3 SM2与ECDSA的比较

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

（1）对于签名信息的预处理，ECDSA中队消息M不做任何处理，而在SM2中，消息=ZA‖M，ZA=（ENTLA‖IDA‖a‖b‖xG‖yG‖xA‖yA），串接用户和曲线信息后，大大提高安全性，加强抗抵赖性。

（2）ECDSA和SM2中都存在随机数k，在k和dA都不知道的情况下需要解决两个椭圆曲线离散对数问题，在计算上是不可行的。我们可以认为它们属于同一个安全性级别的。

（3）ECDSA没有规定哈希算法的使用，SM2中规定使用SM3，SM3输出比特串为256，安全性于SHA-256相当，但高于MD5、SHA-1、SHA-224。

（4）综合来看，SM2是与ECDSA同源相似的一种密钥算法，但其安全性要高于ECDSA，是一种可信赖的安全算法。

4 选取k值方法的改进

基于SM2与ECDSA的相似性，我们可以针对随机源的确定性随机选取过程进行改进，我将它定义为确定性SM2。

确定性SM2是通过使用标准的SM2签名生成过程在输入消息M上生成SM2签名的过程，只是k值不再是随机生成的，而是通過下面描述的过程得到的。

4.1 构建块HMAC

HMAC[16][RF2014]是使用哈希函数和密钥构造的消息身份验证代码（Hash-based Message Authentication Code）的缩写。这里，我们使用HMAC，其哈希函数H与用在签名生成或验证之前处理输入消息的哈希函数H相同。我们用以下方式表示键值为K的HMAC在数据V上的应用过程：

HMAC_K（V）

它的返回长度为hlen（底层哈希函数的输出长度H）的比特序列。

4.2 k的产生

首先给定输入消息m，应用以下过程：

a.通过哈希函数H处理m，得到

h1=H（m）

（h1是hlen位的序列）

b.设置：V=0x01 0x01 0x01 ... 0x01

使V的长度（以比特为单位）等于8×ceil（hlen/8）。例如，在一个八进制的系统中，如果H是SHA-256，那么V被设置为一个值位1的32个八进制序列。需要注意的是，在这一步和后面的所有步骤中，我们使用与步骤a相同的H函数来处理输入消息。

c.设置：K = 0x00 0x00 0x00 ... 0x00

这样K的长度（以比特为单位）等于8×ceil（hlen/8）。

d.设置：

K = HMAC_K（V||0x00||int2octets（x）||bits2octets（h1））

其中“||”表示连接。换句话说，我们使用K值计算HMAC，按照以下顺序链接：V的当前值、值0的八位序列、SM2私钥x的编码和散列消息（可能根据bits2octets的变换来指定被截断和扩展的信息），HMAC的结果是K的新值。请注意，私钥x在[1，q-1]范围内，因此为int2ocets提供了适当的输入，从而产生输出的rlen位，即整数个八位字节（rlen是8的倍数）。

e.设置：V = HMAC_K（V）

f.设置：K = HMAC_K（V||0x01||int2octets（x）||bits2octets（h1））

注意内部八位字节这时候是0x01.

g.设置：V = HMAC_K（V）

h.应用以下算法直接找到k

1.将T设置为空序列。T的长度（以位为单位）表示为tlen;因此在这一步上，tlen=0.

2.当tlen

V = HMAC_K（V）

T = T || V

4.3 计算

k = bits2int（T）

如果k的值在[1，q-1]范围内，并且适用于SM2（即它产生的r值不是0），则k的生成完成，所得k值用于SM2。否则，计算

K = HMAC_K（V || 0x00）和V = HMAC_K（V）并循环（尝试生成一个新的T）。

请注意，当k由T生成时，bits2int的结果与G进行比较，而不是取q的模，如果值不在1到q-1之间，则进行循环。执行一个简单的模块简化会对签名安全性产生有害的偏差。

5 结束语

从区块链的交易可锻性问题出发，发现此问题是受使用的签名算法安全性影响的，签名算法的安全性受随机源影响，SM2国密算法以ECC椭圆曲线数字签名算法为基础，本文通过改进ECC密码算法中的随机数k的生成算法，修改随机源的选取办法，提高了随机源的确定性，降低了智能系统当中因为随机源的不确定性而产生安全隐患的可能性。

参考文献：

[1] Johnson D，Menezes A，Vanstone S. The elliptic curve digital signature algorithm（ECDSA）[J]. International Journal of Information Security，2001，1：36-63.

[2] 国家密码管理局. SM2椭圆曲线公钥密码算法第1部分：总则 ：GM/T 0003.1-2012[S].北京：中国标准出版社，2012：8.

[3] 国家密码管理局.SM2椭圆曲线公钥密码算法第2部分：数字签名算法：GM/T 0003.2-2012[S].北京：中国标准出版社，2012：8.

[4] 国家密码管理局.SM2椭圆曲线公钥密码算法第3部分：密钥交换协议：GM/T 0003.3-2012[S].北京：中国标准出版社，2012：8.

[5] 国家密码管理局.SM2椭圆曲线公钥密码算法第4部分：公钥加密算法：GM/T 0003.4-2012[S].北京：中国标准出版社，2012：8.

[6] 国家密码管理局. SM2椭圆曲线公钥密码算法第5部分：参数定义 ：GM/T 0003.5-2012[S].北京：中国标准出版社，2012：8.

[7] Miller V. Uses of Elliptic Curves in Cryptography[J].Proc. Ann. Intl Cryptology Conf. Advances in Cryptology，1985： 417-426.

[8] Gura N，Patel A，Wander A，et al.Comparing elliptic curve cryptography and RSA on 8-bit CPUs[C]//Cryptographic Hardware and Embedded Systems（CHES 2004）.Berlin，Heidelberg：Springer，2004：119-132.

[9] Lenstra A K，Verheul E R.Selecting cryptographic key sizes[J].Journal of Cryptology，2001，14（4）：255-293.

[10] Potlapally N R，Ravi S，Raghunathan A，et al.A study of the energy consumption characteristics of cryptographic algorithms and security protocols[J].IEEE Trans on Mobile Comput，2006，5（2）：128-143.

[11] 楊晓元，魏立线.计算机密码学[M].西安：西安交通大学出版社， 2015.

[12] 国家密码管理局.SM3密码杂凑函数;GMT 0004.5-2012[S].北京：中国标准出版社，2012：8.

[13] Rivest R L，Shamir A，Adleman L M.A method for obtaining digital signatures and public-key cryptosystems[J].Communications of the ACM，1978，21（2）：120-126.

[14] Jonsson J，Kaliski B.Public-key cryptography standards （PKCS）#1：RSA cryptography specifications version2.1[R]. 2003.

[15] 孙荣燕，蔡昌曙，周洲，等.国密SM2数字签名算法与ECDSA算法对比分析研究[J].网络安全技术与应用，2013（2）：60-62.

[16] Pub F.the keyed-hash message authentication code（HMAC）[J].Federal Information Processing Standards Publication，2002，198.

【通联编辑：代影】