无模逆运算的椭圆曲线数字签名算法

肖 帅，王绪安，潘 峰

1.武警工程大学 网络与信息安全武警部队重点实验室，西安710086

2.武警工程大学 密码工程学院，西安710086

1 引言

数字签名算法（DSA）是1991 年8 月由美国国家研究所（NIST）提出的标准和技术[1-3]，它的安全性是基于离散对数（DL）在Zp*的素数阶子群中的计算不可追溯性的问题（DLP）。作为信息与数据安全的核心技术之一，它可以实现身份认证、数据完整性保护、防篡改、防冒充和不可否认性等数据传输中的重要需求[4]。Johson等人[2]在2001年提出了椭圆曲线数字签名（Elliptic Curve Digital Signature，ECDSA）算法，它是通过2 次模逆运算、3次标量乘运算来实现数字签名的过程的。椭圆曲线数字签名是重要的信息保护技术之一，它通过为信息增加签名，有效保护了信息的完整性、不可否认性、认证性、不可伪造性，目前这一算法得到了广泛认可和应用[5]。图1显示的是ECDSA的发展历程。

图1 ECDSA发展历程

椭圆曲线数字签名算法（ECDSA）是对数字签名算法（DSA）的模拟。椭圆曲线密码（ECC）由Koblitz N[6]和Miller V[7]于1985 年发明，是目前安全性最高的公钥加密算法，它是基于椭圆曲线的一种公钥体制。相较其他公钥体制，椭圆曲线密码的单位比特强度要高一些。椭圆曲线密码体制的主要优势是计算参数更小，密钥更短[8]，运算速度更快，签名也更加短小[9]，效率也更高[10]。因此椭圆曲线密码性能优良，应用广泛，尤其适用于存储空间、处理能力、带宽及功耗受限的场合[11]。

表1 显示的是基于公钥密码的数字签名体制的分类：在这三种分类中，ECDLP 是最难解的，除几类特殊椭圆曲线外，至今仍没有ECDLP的有效求解算法。

表1 基于公钥密码的数字签名体制分类

数字签名应用广泛，电子商务和网络安全认证的核心技术就是数字签名，最近大火的区块链技术，其底层技术之一就是数字签名。由于数字签名方案是许多保密协议的核心构造块，因此提高数字签名方案的效率是非常重要的[12]。

在对ECDSA 的深入研究过程中，一般一致认为影响ECDSA 签名耗时主要有两个计算因素[13]：一是标量乘法运算[14]，标量乘法运算是已知椭圆曲线上两个点：基点G 和随机数k，求kG 的运算过程。另外一个也是最主要的运算就是模逆运算，由于在乘法运算中至少要进行1次求逆运算，而模逆运算所需要消耗的时间是乘法运算的10倍[2]，所以耗时主要由求逆运算产生。针对ECDSA 计算的耗时问题，对求逆运算和标量乘运算的各种改进的方案[15-21]相继被提出，详见表2。

表2 对求逆运算和标量乘运算的各种改进的方案

本文在分析研究经典的椭圆曲线密码理论的基础上，针对经典ECDSA 方案中存在的耗时和伪造攻击的问题，通过引入双参数和避免求逆运算，提出了一种改进的能实现高效率的数字签名方案。

2 预备知识

2.1 方案参数与释义说明

本文方案描述所涉及的参数符号及释义如表3所示。

表3 参数符号与释义

2.2 椭圆曲线密码体制

椭圆曲线密码体制可以看作是旧的离散对数（DL）的椭圆曲线类似物，ZP*的子群被有限域上椭圆曲线上的点群所代替。以下是ECC的一般结构：

设P ∈(FP)，点Q 是P 的倍数，即存在正整数X ，使得q Xp，然后用给定的p 和q 定义ECDLP。基于椭圆曲线离散对数问题，产生了椭圆曲线密码体制。

设E 为椭圆曲线，p 为E 上的一个点，如果存在正整数N ，使得NP=0，则n 是点P 的阶数，其中O 是无穷大点。

椭圆曲线公钥密码（ECC）体制的构造如下：

选择域Fp，椭圆曲线E，选择点P(xp,yp)，n 为E上的素数阶。公开信息：有限域Fp，曲线方程E，点P及其阶n，计算Q=dP，取Q 点为公钥，整数D 为密钥。

要向Alice发送秘密信息M ，需要执行以下步骤：

（1）在域Fp 中将明文M 表示为元素M ；

（2）随机选取[1,n-1]中的整数k；

（3）计算点(x1,y1)=kP；

（4）计算点(x2,y2)=kQ，如果x2=0，则重新选择k；

（5）计算c=mx2；

（6）发送(x1,y1,c)给Alice。

当Alice接收到密文时，使用密钥D 计算密文。

这里Q=dP 是公开的。如果破译者能够解决椭圆曲线上的离散对数问题，就可以从dP 中还原出d ，完成解密[22]。

2.3 椭圆曲线离散对数问题（ECDLP）

椭圆曲线离散对数问题是对于椭圆曲线E( GF( q))上任意两点G 和Q，有Q=dG，在已知G 和Q 的前提下求出小于q 的正整数d。己知d 和G 计算Q 比较容易，但是已知Q 和G 计算d 则很困难，这便是椭圆曲线加密体制的核心。椭圆曲线密码体制的安全性基于椭圆曲线离散对数问题，也就是求解ECDLP 算法的时间复杂度。

3 ECDSA数字签名原理与方案分析

3.1 ECDSA数字签名方案描述

ECDSA 是ECC 与DSA 的结合，整个签名过程与DSA类似，所不一样的是签名中采取的算法为ECC，最后签名出来的值也是分为r,s。

（1）方案建立

U 为签名者，V 为验证者：

①U 构建椭圆曲线城参数T=(p,a,b,G,n,h)；

②U 建立密钥对(du,Qu)，且有Qu=duG；

③U 选择一个hash数；

④U 将hash函数和椭圆曲线域参数T 传给V 。

（2）签名算法

①选择一个临时密钥对(k,r)，其中R=kG=(xR,yR)和域参数T 相关。

②令r=xRmod n，如果r=0，返回1。

③计算待签消息的hash值H=H(m)，将H 转换成整数e。

④计算s=k-1(e+rdu)(mod n )，如果s=0，返回1。

⑤输出S=(r,s)为数字签名。

（3）验证算法

V 通过验证从U 发来的数字签名来判断所接收消息以及对方身份的真伪。

①如果r,s ∉[1 ,n-1] ，验证不通过。

②计算待签消息的hash值H=Hash(M) ，将H 转换成整数e。

③计算u1=es-1( mod n ),u2=rs-1(mod n )。

④计算R=(xR,yR)=u1G+u2Qu，如果R=0，验证失败。

⑤令v=xR(mod n )，如果v=r ，验证成功，否则验证失败。

3.2 ECDSA数字签名方案分析

在ECDSA 方案中，公钥的产生算法是Qu=duG ，在签名的生成和验证过程中需要分别计算k-1mod n 和s-1mod n，即需要进行模逆运算。若模乘运算的数据规模为n ，则一次模乘运算的复杂度为O(n2ln n)。表4分析了ECDSA方案的算法复杂度。

表4 ECDSA算法复杂度分析

可以看到，签名算法和验证算法运算很复杂，都有模逆运算。前文中已经提到，在现有的椭圆曲线加密或者签名过程中，主要的运算负担来自求逆运算，求逆是最复杂费时的操作，一次求逆的时间大约相当于80 次点乘运算。如果可以减少甚至是避免模逆运算无疑有助于数字签名效率的提升。

4 改进的ECDSA方案

由以上分析可知，在签名或者验证阶段，如果可以减少甚至是避免模逆运算无疑有助于数字签名效率的提升。但在着力提高运算效率的同时也应兼顾安全问题，基于此，本文提出了一种新的ECDSA的改进方案。

4.1 改进方案的算法描述

设ECC 参数为T={a,b,G,n,h}，用户使用私钥A( d,Q )对消息m 进行签名，图2显示了签名和验证的具体过程。

（1）A随机选择一个整数k，k ∈[1,n-1]；

（2）计算kG=(x1,y1) ，将x 转换成整数xˉ；

（3）随机选择1组α,β ∈[1,n-1] ，α,β 满足条件k=αr+βm；

图2 改进的算法流程图

（4）计算待签名的消息m 的哈希值e，e=H(m)；

（5）计算r=xˉ1mod n；其中若r=0，则跳转到（1）；（6）计算s=r(α+ed)mod n；若s=0，则跳转到（1）；（7）(r,s,β)即为签名m 的信息.用户B收到m 和(r,s,β)后，对签名进行如下验证：

①验证r,s,β 是否属于区间[1,n-1]内的整数，若三者中任何一个参数验证失败，则拒绝签名；

②计算e=H(m)；

③计算γ=(s+βm)mod n，u=er mod n；

④计算γG-uQ=(x′,y′)；

⑤计算v=x′mod n；

⑥若v=r，则验证签名成功。

在以上改进方案的算法描述细节部分，步骤（1）至步骤（3）中关于随机数k 的选取，进行分析说明，以表明方案中随机数选取的合理性和随机性。

通过（1），确定了一个整数k，k 是在[1,n-1]区间随机选取的，在（3）中，等式的两边都要进行模n 运算，由于n 为素数，r,m 为已知信息，k 被随机选取后，再从[1,n-1]区间任意选取一个α，则一定存在一个满足等式k=αr+βm 的整数β，且β ∈[1,n-1]，所以改进方案的构造具有合理性和随机性。

对改进算法的正确性证明如下，若(r,s,β)是对m的签名信息，则：

因此

所以有ν=x′=x=r mod n

4.2 改进方案的算法分析

（1）抗替换信息的伪造攻击

A发送(r,s,β)信息给接收方C后，接收方C可以用伪造消息m′来代替m 进行签名。

C伪造签名过程如下：

①由于s,e，r 为已知量，C 由s=r(α+ed)mod n 可计算出(α+ed)mod n；

②使用替换的消息m′，计算e'=H(m') ；

③计算满足条件k=αr+βm 的α,β；

④计算s′=r(α+e′d)mod n；

⑤伪造签名计算s′=r(α+e′d)mod n，(r,s′,β )为m′的签名数据。

B收到(r,s',β )签名信息后，进行如下签名验证，计算：

因此签名无效。

（2）替换随机数的伪造攻击

接收方C收到签名消息(r,s,β)后，可以伪造随机数k′来代替k 进行签名。C伪造签名过程如下：

①由于s,e,r 已知，B 由s=r(α+ed)mod n 计算出(α+ed)mod n；

②随机生成一个整数t，计算k'=k+t，其中k',k 都是未知的；

③计算k'G=(k+t)G=kG+tG=(x′,y′)；

④计算r'=x'mod n；

⑤计算满足条件k′=α′r′+β′m 的α′,β′；

⑥计算e=H( )m ；

⑦计算s′=r′(α′+ed)mod n。

B 收到( r′,s',β′ )签名信息后，进行如下签名过程：计算γ′=(s′+β′m)mod n=(α′r′+er′d+β′m)mod n ≠(x1,y1)，因此签名无效，通过以上分析可知，改进的ECDSA算法可以有效抵御接收者伪造签名。

4.3 改进方案的性能分析

4.3.1 安全性分析

方案的构造通常不难，但首要的是要考虑到它的安全性，否则即使数字签名计算效率再高，也毫无意义。在本文的改进方案中，即使非法用户设法得到了A或B的私钥，也很难获取到会话密钥。由QA=dAG 可知，如果攻击者在窃取QA和G 后推出了dA，那么就意味着他解决了离散对数难题，而这是不可能的，因此攻击者无法获得私钥。具体安全性有以下几个方面。

（1）抗伪造攻击

对于发送方A和接收方B，虽然e,r′,α′，(α+ed)mod n是公开已知的，但是接收方B验证出来的x′与x 不同，所以可以有效地抵抗伪造攻击。

（2）防数据篡改

通过对消息进行哈希运算可以实现数据的完整性，一旦数据遭到篡改，哈希数值将会发生变化，从前述步骤中可以看出，如果哈希值不相同，则签名无法通过。

（3）抗中间人攻击

在传统的通信过程中，公钥是公开的，私钥可以是随机数r 或分发给用户的d 。攻击者选取随机数rc∈[1,n-1]，截获A发给B的QA=dAG ，B发给A的QB=dBG ，将dAG,dBG 修改成rcG ，协商之后，A与非法用户共享密钥dAdBG，A误认为B是共享的，B与非法用户共享dAdBG，而B认为A是共享的，实际A和B没有共享密钥。当A发送信息给B时用dArcG 对信息进行加密，非法用户截获之后进行解密，伪造信息，用dAdBG 加密后发送给B，这样就欺骗了用户A和B，而事实上A和B是不知情的，这样正常的密钥协商就受到了影响。因此，在不清楚对方真实身份的情况下，通信双方建立的密钥会话易遭受中间人攻击。在本文方案中通信的双方实现了身份的双向认证，非法用户不能伪装成任何一方，从而有效地防止了中间人攻击。

（4）抗抵赖性

接收方根据发送方发送的(r,s,β)，防止发送方事后抵赖。

4.3.2 效率分析

在本文的方案中，签名和验证过程均没有模逆运算，通过具体的数值来分析改进方案的效率变化。在数字签名过程中耗时主要集中在乘法、逆运算和标量乘运算，可分别简记为[l],[i],[h ] ，鉴于加法等运算对耗时的影响因素较小，故可忽略不计。1次求逆运算约相当于10次乘法运算，即[i] =10[l ]，根据文献[18]，标量乘运算是满足在163b 下[h ] =75[i] + 173[l ]=750[l ]+173[l ]=923[l]，设模乘运算的数据规模为m，表5是改进后的新方案与经典的ECDSA 方案的耗时对比，由表5 分析可知，本文改进的方案在签名上的计算效率比经典的ECDSA 方案提高了0.96%，在验证上的计算效率比ECDSA方案提高了50.2%。

表5 两种方案耗时对比

4.3.3 仿真实验

在本文的改进方案中，签名和验证过程均没有求逆运算，理论上无疑会极大提升数字签名的效率，使用MATLAB编程模拟仿真来进行验证，检测效率如图3所示，从图中可以直观地看到两种方案的运算复杂度与数据规模的关系。

由图3可看到，相较经典的ECDSA方案，在同等的数据规模下，本文的改进方案中数据复杂度始终较低，实验仿真结果与本文的理论分析相吻合，即本文的改进方案可以提高数字签名的计算效率。

图3 复杂度与数据规模对比

5 改进的ECDSA方案在电子商务中的应用

信息化网络时代，电子商务的飞速发展使得人们足不出户就可以享受方便快捷的服务。电子商务对信息的保密性、数据完整性、不可否认性有较高要求。人们在享受网上交易带来的便捷服务的同时，也日益关注信息安全。RSA 签名算法曾被广泛使用来保护交易信息的安全，随着MD5算法被破解，SHA-1算法受到挑战和ECDSA在理论上的日益成熟，ECDSA算法的优越性日益凸显，电子商务的安全越来越需要ECDSA来保证。

将改进的ECDSA方案与时下飞速发展的电子商务进行结合，在交易信息的加解密模型中通过构建Meneses-Vanstone 密码体制来对数据进行加解密操作。基于改进的椭圆曲线Meneses-Vanstone（MV）密码体制构造数据加解密模型。

数据加密模型如图4所示。

图4 电子数据加密模型

在电子商务交易过程中主要是客户端与服务器端的互动，客户端即加密的一方，为电子商务中数据信息的发送方。

（1）客户端将待发送传输的数据信息格式化处理生成消息串(m1,m2)。

（2）用数据信息的接收方服务器端的公钥QB和客户端的私钥dA按照MV 密码体制对(m1,m2)进行加密形成密文(x2,y2)。

（3）客户端将自己的公钥QA和加密信息( QA,( x2,y2))一起发送给接收方服务器端。

MV加密过程如下：

（1）获得服务器端的公钥QB，计算( x1,y1)=dAQB，如果x1,y1=0，则客户端重新选择私钥dA，同时生成新的公钥。

（2）计算x2=m1x1mod p,y2=m2y1mod p。

MV解密过程如下：

（1）获得客户端的公钥QA，计算( x1,y1)=dBQA。

（2）计算m1=mod p,m2=mod p。

数据解密模型如图5所示。

图5 电子数据解密模型

服务器端即解密方，为电子商务交易中数据信息的接收方。服务器端接收到客户端发送过来的加密信息( x2,y2)，首先使用客户端的公钥QA和服务器端的私钥dB对加密信息按照MV密码体制进行解密生成( )m1,m2，然后再将其逆向转换为客户端明文消息。

MV 加密体制并没有限制消息明文必须嵌入椭圆曲线上，这种体制的优点是不需要将待加密的数据进行数据类型转换操作，从而降低了成本，同时提高了数据加解密效率。无模逆的椭圆曲线数字签名算法，使运算负担减少，从而加快数字签名和验证签名的速度，进而使电子商务交易过程安全高效。

6 结束语

本文在对经典的椭圆曲线数字签名进行分析的基础上，指出其存在的局限性，由此进行了方案的改进。改进的方案引入了双参数，进行标量乘运算2 次，在签名和验证过程中均没有使用模逆运算，理论分析证明了本文方案的安全性，仿真实验证明了改进方案提高了数字签名的计算效率。最后将改进的方案应用到电子商务中，构建了电子商务交易过程中电子数据的加解密模型。