一种高效的SM2数字签名批量验证算法

阮 鸥，陈吉晨，毛 浩

(湖北工业大学计算机学院，湖北 武汉 430068)

1 引言

数字签名常用于身份认证、抗抵赖性等方面。例如，银行发薪资问题，假设用户B为中国邮政银行经理，用户A为中国邮政集团公司(有100万员工)的会计人员，用户A每个月底需要把所有员工(约100万)的薪资数据及其签名发送给中国邮政银行，以便用户B将薪资转账给所有员工，此时用户B需要一一验证用户A发送过来的每一位员工的薪资数据及其签名，需要做100万次验证，产生大量的计算工作，显著降低了银行转账系统的效率，此时数字签名批量验证显得尤为重要。Naccache等人[1]最早提出了批量验证(Batch Verification)算法。批量验证算法的基本思想是将多个签名(可能来自不同的签名者)组成一个新的集合，并对新的集合进行验证。如果该集合通过验证，则接受该集合中的所有签名，否则，拒绝集合中所有签名。目前，对于DSA(Digital Signature Algorithm)、RSA(Rivest, Shamir, Adleman)和ECDSA(Elliptic Curve Digital Signature Algorithm) 等数字签名，研究者均提出了相应的批量验证算法，其中Harn[2]针对DSA设计了一种交互式的批量验证算法，Hwang等人[3]提出了DSA、RSA的批量验证算法，Cheon等人[4]针对ECDSA*设计了一种快速批量验证多个数字签名的方案。

在数据外包、智能汽车、智能电网和物联网等现代应用领域中，为了提高数字签名批量验证速度，研究者提出了不同的方案。Zhang等人[5]提出了基于外包功能的批量验证计算方案，客户端查询请求数据时，由服务器进行批量身份验证，而客户端使用更少的时间来验证服务器计算的正确性。Bayat等人[6]提出了一种具有批量验证功能的安全认证方案，将批量验证应用于车联网中，车辆与车辆进行通信，以及车辆与固定的路边单位或云平台进行通信时，使用批量验证能够更快速地处理数据，减少事故，改善交通状况。Guo等人[7]提出基于批量验证轻量级隐私保护数据聚合的智能电网方案，数据聚合者能够对加密电力数据进行批量验证，从而提高整个系统的计算效率。Xiong等人[8]提出了一种安全高效无证书批量验证的物联网方案，方案中的信任模型可帮助网关节点识别受信任的传感器节点执行批量验证。

SM2算法[9]是我国科研人员基于ECC椭圆曲线密码理论自主研发设计的，采用素数域256位椭圆曲线作为标准曲线生成密钥对。在ECDSA数字签名算法中，对待签名消息M不做任何处理，而SM2数字签名算法对待签名消息M进行了处理，其中包含用户的可辨别标识、部分椭圆曲线系统参数和用户公钥的杂凑值，使得安全性和抵赖性更强，因此在数字签名方面SM2优于ECDSA、ECDH(Elliptic Curve Diffie-Hellman key exchange)等算法。目前，SM2还被应用于盲签名[10]、代理签名[11]、门限密码体制[12]和安全双方协作[13]等领域。然而，SM2的批量验证算法还没有人进行研究。本文针对SM2数字签名，提出了相同签名者与不同签名者的批量验证算法。

本文提出了一种安全高效的SM2批量验证算法。算法并非在每一次签名完之后立即验证，而是一次同时验证多个签名。因为在SM2数字签名验证过程中，点乘运算是一项非常耗时的运算，所以本文通过减少点乘运算来缩短验证时间，进而提高算法效率。实验数据表明，在消息数量相同的情况下，批量验证算法的效率远高于单个验证算法的效率，例如当签名数量达到约100万(220)时，单个验证算法大约需要1 h，而批量验证算法仅需2 s。

2 相关工作

1991年，美国政府提出了数字签名标准DSS(Digital Signature Standard)作为联邦标准，使用数字签名算法(DSA)签署电子文档。DSA数字签名算法是一种基于离散对数问题的ElGamal型签名方案[14]，其验证每个签名至少需要2次模幂运算。由于模幂运算是一项非常耗时的计算，因此需要使用专用硬件或高效的软件算法加速验证过程。

1994年，Naccache等人[1]首次提出了一种交互式DSA批量验证算法，同年，Lim等人[15]指出这种交互式DSA批量验证算法是不安全的，此方案中敌手可以伪造一个签名集合来满足批量验证公式。1995年，Harn[2]针对DSA数字签名算法，设计了一种交互式的批量验证算法，其中签名者与验证者交互生成n个签名，验证者对n个签名进行验证。1998年，Harn[16]再次针对DSA数字签名算法，提出了一种非交互式的批量验证算法，它充分利用签名者的公钥作为验证纽带，摒弃了签名者产生签名时需要与验证者交互的过程。2001年，Hwang等人[17]指出文献[16]的方案中签名者可以伪造个人签名，并使得错误的批量验证有效。

1998年，Harn[18]针对RSA数字签名算法，提出了一种批量验证方案，使用相同私钥对多个消息进行签名，并且对多个签名进行批量验证。2000年，Hwang等人[19]使用2种方法证明了文献[18]的方案中，验证者无法验证签名是否合法。2001年，Hwang等人[3]提出了2种简单批量验证多个数字签名的算法：BV-DSA与BV-RSA，其中BV-RSA方案与文献[18]方案具有相同的安全缺陷，即不诚实的签名者可以伪造个人数字签名，使虚假的批量验证有效。2006年，Bao等人[20]针对文献[3]中的BV-RSA方案进行了密码分析与改进。2017年，Kittur等人[21]针对RSA数字签名算法，提出了一种快速验证方案，研究了各种RSA数字签名算法的批量验证方法，指出数字签名批量验证在物联网应用中是一个很有前途的研究方向。

ECDSA数字签名验证算法相比于DSA和RSA算法，具有速度快、强度高和签名短等优势[22]。ECDSA*是ECDSA的一种改进，它能应用于Naccache等人[1]针对DSA数字签名提出的批量验证算法中。2005年，Adtipa等人[23]提出了一种加速验证ECDSA数字签名的方案，能够加速验证ECDSA签名的效率，在不增加算法复杂度的前提下，使其效率提升40%以上。 2007年，Cheon等人[4]设计针对ECDSA*数字签名设计了一种快速批量验证多个数字签名的方案，针对相同签名者与不同签名者提出了不同的批量验证算法。2012年，Bernstein等人[24]针对椭圆曲线签名提出了一种快速批量伪造识别的策略，进而降低了椭圆曲线签名批量伪造识别的成本。2014年，Karati等人[25]提出了一种新的ECDSA数字签名批量验证算法。2019年，Kittur等人[26]针对ECDSA*提出了一种更高效的批量验证算法，在不同的批处理规模上表现更好。

3 SM2数字签名批量验证算法

定义p为大素数，Fp为有限域.选择a,b∈Fp作为椭圆曲线E的参数。定义(x,y)为椭圆曲线E上的一点，并且将其作为群G的生成元。群G的阶为n。定义Hv()为摘要长度为v比特的哈希算法。

3.1 相同签名者的批量验证算法

3.1.1 签名(Sign)

假设签名者是A，其公私密钥对为(dA,PA)，对于待签名消息Mi，随机选取ki∈[1,n-1]，计算：

(xi,yi)=kiG

ri=(ei+xi) modn

(1)

si=((1+dA)-1·(ki-ridA)) modn

(2)

签名者A将(ri,si)(i=1,2,…,l)作为消息Mi的签名发送给验证者B。

3.1.2 批量验证(Batch Verification)

验证者B收到所有消息的签名(M′i,r′i,s′i) ((i=1,2,…,l)，步骤1～步骤5中i相同)，进行批量验证。

步骤1检验r′i∈[1，n-1]是否成立，若不成立则验证不通过。

步骤2检验s′i∈[1，n-1]是否成立，若不成立则验证不通过。

步骤5计算ti=(r′i+s′i) modn，若ti=0，则验证不通过。

(3)

(4)

(5)

步骤10根据式(4)和式(5)计算椭圆曲线上的点：

(x′,y′)=uG+wPA

(6)

步骤11根据式(3)和式(6)计算R′的值：R′=(d+x′) modn，检验R′=R是否成立，若成立则验证通过；否则验证不通过。

3.1.3 正确性分析

因为M′=M，(r′,s′)=(r,s)，则e′=e。又因为ri=(ei+xi)(i=1,2,…,l)，则：

对于相同签名者的批量验证公式为：

只需验证：

根据式(1)、式(2)、式(4)、式(5)以及r′i=ri,s′i=si得：

uG+wPA=

kG=(x,y)=右边

这就证明了批量验证相同签名者产生的数字签名方案的正确性。

3.1.4 安全性分析

定理1在签名者相同的情况下，SM2数字签名批量验证算法是安全的，具有和单个验证算法一样的强度。

证明本文利用反证法的思想，证明相同签名者下SM2批量验证算法的安全性，即如果SM2批量验证算法不安全，则可以推导出SM2标准单个验证算法不安全，故SM2批量验证算法是安全的。具体证明如下：

在相同签名者批量验证方案中，需要验证:

其中，r′i=s′iG+tiPA+e′i。

假设敌手成功篡改了签名后的消息Mi，并且能够满足：

但不能够改变签名后的r1,r2,…,rl。因为签名过程中针对不同的消息Mi，能够生成r1,r2,…,rl，敌手必须揭示r1,r2,…,rl是SM2签名的一部分。

在验签过程中，本文计算所有消息Mi的密码杂凑函数值e′i，根据式(6)计算椭圆曲线上的点(xi,yi)，给定这些xi坐标和验证条件R=R′，对于相应的y坐标y1,y2,…,yl，r1,r2,…,rl存在唯一的解。只要l被限制为小的常数值，敌手只需要适度的计算就可以确定y1,y2,…,yl的唯一值，这意味着敌手可以揭示坐标xi与ri，进而知道ri的所有点坐标(xi,yi)。

以上论证基于解的唯一性定理，r1,r2,…,rl满足标准SM2数字签名验证条件，若敌手可以篡改SM2数字签名批量验证算法中的数据，那么敌手也可以篡改标准SM2数字签名中算法的数据，因此SM2数字签名批量验证算法的安全性不低于SM2单个数字签名验证算法的安全性。

□

3.2 不同签名者的批量验证算法

假设签名者是Ai，其公私密钥对为(dAi,PAi)，针对不同的消息MAi，产生的签名消息为(rAi,sAi)(i=1,2,…,l)。假设验证者是B，则B需要对Ai发送过来的签名(MAi,rAi,sAi)进行验证，判断其签署者是否为Ai。在进行数字签名验证过程中，点乘运算是一项非常耗时的运算，即计算椭圆曲线点(x′Ai,y′Ai)=s′AiG+tAiPAi。因此，本文先分别计算出s′Ai与tAiPAi的累加和，再计算椭圆曲线上的点(x′Ai,y′Ai)时，仅需1次点乘运算，进而提高数字签名验证效率。

3.2.1 签名(Sign)

假设签名者是Ai(i=1,2,…,l)，其公私密钥对为(dAi,PAi)，对于待签名消息MAi，随机选取kAi∈[1,n-1]，计算：

(xAi,yAi)=kAiG，

rAi=(eAi+xAi) modn

(7)

sAi=((1+dAi)-1·(kAi-rAidAi)) modn

(8)

签名者Ai将(rAi,sAi)作为消息MAi的签名发送给验证者B。

3.2.2 批量验证(Batch Verification)

验证者B收到所有消息的签名(MAi,rAi,sAi) ((i=1,2,…,l)，步骤1～步骤5中i相同)，进行批量验证。

步骤1检验r′Ai∈[1,n-1]是否成立，若不成立则验证不通过。

步骤2检验s′Ai∈[1,n-1]是否成立，若不成立则验证不通过。

步骤5计算tAi=(r′Ai+s′Ai) modn，若tAi=0，则验证不通过。

(9)

(10)

步骤9根据式(10)计算椭圆曲线上的点：

(11)

步骤10根据式(9)和式(11)计算R′的值：R′=(d+x′Ai) modn，检验R′=R是否成立，若成立则验证通过；否则验证不通过。

3.2.3 正确性分析

因为M′Ai=MAi，(r′Ai,s′Ai)=(rAi,sAi)，则e′Ai=eAi。又因为rAi=(eAi+xAi)(i=1,2,…,l)，则：

对于不同签名者Ai的批量验证公式为：

只需验证：

根据式(7)、式(8)、式(10)以及r′Ai=rAi,s′Ai=sAi得：

这就证明了批量验证不同签名者产生的数字签名方案的正确性。

3.2.4 安全性分析

定理2在签名者不同的情况下，SM2数字签名批量验证算法是安全的，具有和单个验证算法一样的强度。

定理2的证明与定理1的证明相似，略。

4 批量验证算法的实现与性能分析

为了比较单个验证算法与批量验证算法的运行效率，本文使用C语言编程实现2个方案，通过调用OpenSSL密码库实现椭圆曲线上的计算。基于PC端开发，运行环境如下：

中央处理器：Intel i5-6300HQ&2.3 GHz；

内存：4 GB；

硬盘：500 GB；

操作系统：Windows 10专业版。

椭圆曲线各参数的取值与GB/T 32918.2-2016中的附录A.2中各参数的取值一致。

本文分别执行2个方案10次，获取数据平均值，以ms作为时间单位。在相同签名者与不同签名者方案中，密钥生成阶段相同签名者方案仅需生成1对公私密钥对，而不同签名者方案需要生成多对公私密钥对，因此不同签名者方案中密钥生成阶段耗时远大于相同签名者方案相应阶段的耗时；在签名与验证过程中，对于相同签名者与不同签名者，它们各部分耗时几乎相同。表1表示在不同消息数量的情况下，相同签名者与不同签名者进行单个验证算法与批量验证算法的运行时间比较。

从图1可以看出，单个验证算法中，点乘运算约占验证时间的95%以上。在数字签名验证过程中，单个验证算法的时间与消息数量成线性关系，随着消息数量的不断增加，验证时间也相应不断增长；批量验证算法中，最耗时的点乘运算与消息数量无关，仅需1次，其他计算虽与消息数量成线性关系，但耗时较少，因此验证时间不会随着消息数量的不断增加而快速增长。图1中横坐标2x(x=0,4,8,…,20)表示消息M的数量，纵坐标2y(y=0,4,8,…,24)表示数字签名验证所需时间。当签名数量达到约100万(220)时，单个验证算法大约需要1 h，而批量验证算法仅需2 s。因此，对于大量消息数据同时进行数字签名的时候，不论是相同签名者还是不同签名者，使用批量验证算法都可以大大缩短运行时间，显著提高效率。

Table 1 Comparison of run time between single verification algorithm and batch verification algorithm

Figure 1 Comparison of run times between single verification and batch verification algorithm图1 单个验证算法与批量验证算法运行时间比较

5 结束语

本文首次提出了一种高效的SM2数字签名批量验证算法，特别适合电子货币等需要验证大量数字签名的应用场景。批量验证算法通过减少验证过程中耗时的点乘运算，显著缩短整个验证过程的时间，极大提高了验证效率。实验结果表明，当数字签名数量达到约100万(220)时，单个验证算法大约需要1 h，而批量验证算法仅需2 s。