一种改进的椭圆曲线数字签名方案

栗亚敏 张 平

(河南科技大学数学与统计学院 河南 洛阳 471023)

0 引 言

随着网络应用的蓬勃发展和广泛普及，计算机病毒、黑客、电子犯罪和电子窃听事件层出不穷，给人们的生活造成极大的隐患，因此，必须要加强网络安全意识，尽量减少安全漏洞，最大限度地降低网络安全造成的损失[1]。

数字签名是当前网络安全领域的研究热点之一，数字签名机制是保障网络信息安全的手段之一，它可以解决签名的伪造、抵赖、冒充和篡改问题[2]。数字签名在实现身份认证、数据完整性、不可抵赖性等功能方面都有着重要的应用。最初提出它的目的是在网络环境中模拟日常生活中的手工签名或印章[1]。在数字签名中，基于椭圆曲线密码系统的数字签名具有更高的安全性，椭圆曲线密码系统是离散对数密码系统在椭圆曲线上的移植[2]。椭圆曲线密码体制ECC(Elliptic Curve Cryptography)由Koblitz[3]和Miller[4]分别独立提出，它是利用有限域上的椭圆曲线有限群代替基于离散对数问题密码体制中的有限循环群所得到的一类密码体制[5-6]，它的安全性是基于椭圆曲线离散对数问题(ECDLP)的求解困难性基础之上。因此，严格地说，它不是一种新的密码体制，它只是已有密码体制的椭圆曲线型的翻版。椭圆曲线密码体制的研究历史并不太长，但由于它自身突出的优点，得到了密码学界的重视与广泛推广[7]。Johnson等[7]在1992年第一次提出椭圆曲线密码的数字签名算法(ECDSA)，这一算法被国际化标准组织定义为标准数字签名算法。2007年，李复才等[8]设计了一种新的无求逆的签名算法，该算法简化了运算的复杂程度，保证了算法安全性。2008年，张庆胜等[9]对模乘运算进行了改进，提出了一种新的椭圆曲线数字签名方案。同年，潘晓君[10]提出了一个新的基于椭圆曲线的数字签名方案，该方案不需要进行模逆操作，大大提高了签名的效率。杨青等[11]也提出了一种改进的基于椭圆曲线的数字签名方案，该方案能够有效地抵抗生日攻击，提高数字签名的安全性。2009年，武美娜等[12]改进了椭圆曲线数字签名算法，改进算法不需要进行求逆运算，比传统算法具有更少的时间复杂度。2011年，陈亮等[13]改进ECDSA签名算法，提出了一种新的椭圆曲线数字签名方案。此方案在签名和验证过程中避免了求逆运算，也减少了点乘。同年，许德武等[14]将ElGamal签名方案移植到椭圆曲线密码系统中，改进签名生成及验证过程，使用代数运算代替椭圆曲线上的数乘运算，得到了一种新的椭圆曲线数字签名方案。2013年，周克元[15]设计了一种快速椭圆曲线消息恢复数字签名方案，该方案仅仅具有2次模乘运算，并且没有模逆运算。同年，逯玲娜等[16]提出了两个新的不需要模逆操作的基于椭圆曲线的数字签名方案。2014年，严琳等[17]设计了一种分段快速标量乘算法，并将其运用到了ECDSA方案中，提高了ECDSA方案的效率。2015年，陈辉焱等[18]设计了一种具有前向安全的数字签名方案，该方案有效地减少了密钥泄露带来的损失。2016年，周克元[19]设计了一种具有消息恢复功能的椭圆曲线数字签名方案，该方案不仅能抗伪造签名攻击，还具有前向安全性。随着数字签名技术[20-23]的不断进步，近年来，许多新的椭圆曲线数字签名方案[24]被相继提出。

本文重点研究了文献[9]算法，发现该算法可被替换消息伪造签名攻击。本文分析了其原因，提出了一种新的改进方案。

1 文献[9]方案

1.1 参数选择

1.2 签名生成

签名者A利用上面的参数对消息m进行签名：

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

(2)计算kG=(x1,y1)，r=x1modn；

(3)计算e=SHA1(m)；

(4)计算s=(er)-1(k+d)modn；

(5)签名结果为(r,s)。

1.3 签名验证

验证者B验证(r,s)是A对消息m的签名：

(1)检验r,s∈[1,n-1]，若不成立，返回拒绝签名；

(2)计算e=SHA1(m)；

(3)计算w=(er)smodn，那么就有公式(er)s=(k+d)modn成立；

(4)计算wG-Q=(x2,y2)；

(5)计算v=x2modn，若v=r，则接受该签名，否则拒绝该签名。

1.4 安全性分析

在该算法中签名等式如下：

s=(er)-1(k+d)modn

(1)

可以用另一消息m′替换原有消息m进行伪造签名。替换消息伪造签名成功的原因如下：s、e、r已知，由：

s=(er)-1(k+d)modn

(2)

可求得(k+d)modn。然后计算e′=SHA1(m′)，那么就可以计算出：

s′=(e′r)-1(k+d)modn

(3)

从而得到伪造签名(r,s′)。

另外，高伟等[1]设计的快速签名等式如下：

s=k-l-rdmodn

(4)

该式也存在这样的错误。

2 改进方案

2.1 参数的选择

2.2 密钥生成

(1)选择x∈[1,n-1]；

(2)计算Y=xG。若Y=O，跳转至步骤(1)；

(3)公钥为Y，私钥为x。

2.3 签名生成

签名者A利用上面的参数对消息m进行签名：

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

(2)计算R=kG=(x1,y1)，r=x1modn，若r=0，跳至步骤(1)；

(3)计算e=H(m)；

(4)计算s=ke-rxe2modn(其中e2可以通过预处理提高签名速度)，如果s=0，则跳至步骤(1)；

(5)签名结果为(e,s)。

2.4 签名验证

验证者B验证(e,s)是A对消息m的签名：

(1)检验r,s∈[1,n-1]，若不成立，返回拒绝签名；

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

(3)计算w=xemodn；

(4)计算X=w-1sY+rwG=(x2,y2)；

(5)若X=O，拒绝该签名；

(6)计算v=x2modn，若v=r，则接受该签名；否则拒绝该签名。

2.5 方案正确性证明

若v=r，则：

X=w-1sY+rwG=(xe)-1sY+rwG

(5)

由于s=ke-rxe2modn，故：

X=(xe)-1(ke-rxe2)Y+rwG

(6)

则：

X=x-1(k-rxe)Y+rwG

(7)

即：

X=x-1kY-reY+rwG

(8)

由于Y=xG，那么：

X=kG-rexG+rwG

(9)

又因为w=xemodn，所以：

X=kG

(10)

从而v=r得证。

3 安全性证明

证明：

该证明过程实际上是一个敌手A和算法B之间的交互式游戏。算法B接收一个随机的ECDLP问题实例Y=xG，他的目标是计算出x。算法B把敌手A作为子程序，算法B扮演敌手A的挑战者。

1)设置阶段。游戏一开始，算法B将系统参数发送给敌手A。算法B要维护LH、LS、LV三张列表，这些表初始为空，其中：列表LH用来跟踪敌手A对预言机H的询问；列表LS用于模逆签名预言机；列表LV用于模逆验证预言机。

2)查询阶段。

(1)哈希查询。所有之前被签名过的(m,e)被储存在列表LH中，当敌手A对消息m进行哈希查询时，算法B首先检查消息m是否已经出现在列表LH中。若已存在，算法B直接将e返回给敌手A；否则，算法B从{0,1}n中任意选择e，并将(m,e)存储进列表LH中，然后将e返回给敌手A。

(2)签名查询。敌手A向算法B提交消息m，算法B任意选择随机数k∈[1,n-1]，然后计算R=kG=(x1,y1)，提取r=x1modn。算法B在列表LH中搜索(m,e)，若列表LH中存在(m,e)，则返回符号“⊥”，查询终止；否则，算法B计算s=ke-rxe2modn；然后，将签名结果(e,s)返回给敌手A。

证毕。

由于ECDLP问题是数学难题，目前没有算法可以解决该问题，因此不存在能够在t时间内以不可忽略的优势ε攻破改进方案的敌手。因此，改进方案是安全的。

3.1 不可伪造性

传统的椭圆曲线数字签名方案ECDSA方案并没有严格的安全性证明。2005年Brown[28]基于离散对数难解性以及哈希函数具有抗碰撞性的假设，给出了ECDSA方案的不可伪造性证明。该证明同样适用于改进方案，此处省略了其证明。

3.2 抵抗随机数攻击

不同消息使用同一签名方案进行签名时，使用相同的随机数(这种概率非常小)是不行的[29]，因为一旦随机数相同就可以用一个二阶的线性方程组解出私钥，从而造成密钥的泄露。

如果使用ECDSA方案对不同消息进行签名时用相同的随机数，那么就可以根据方程组：

(11)

解出：

k=(s2-s1)-1(e2-e1)modn

(12)

进而解出私钥:

x=r-1(s1k-e1)modn

(13)

实际上，有很多方案即使每次使用不同的随机数，也有可能被该攻击方法的推广所破解。比如，记u=xe+smodn，其中：x是私钥；s是签名结果中的s；e是被签名的消息或消息的哈希函数。那么u在区间[0,n-1]的取值是随机的，攻击者只需计算eY+sG。如果对消息m1、m2的签名中计算得：

e1Y+s1G=e2Y+s2Gmodn

(14)

那么就可推出u1=u2modn。因此:

e1x+s1=e2x+s2modn

(15)

从而就可以解出私钥:

x=(e1-e2)-1(s2-s1)modn

(16)

在通过改进方案使用相同随机数对不同消息进行签名时，有如下方程组：

(17)

式中:签名(e1,s1)和(e2,s2)是已知的;k、x和r是未知的，由于方程组中含有两个方程三个未知数，因此无法求解方程组。

另外，如果想通过上述攻击方法的推广来破解改进方案也是不可能的。因为破解时要求计算不同签名的某个随机变量是否取相同的数值，这种概率也是非常小的以至于破解的计算量非常大，比直接计算离散对数还难。假设u取值的概率在区间[0,n-1]上是均匀分布的，那么由生日攻击[30]的结论得a次不同消息的签名中存在两次签名u1=u2的概率为0.5时，则a≈1.17sqrt(n)，这是一个非常大的数。如果没有直接的eY与sG值的话，计算难度是非常大的。所以，改进方案可防止针对随机数的攻击。

3.3 不可否认性

如果签名者想要否认自己曾对某个消息进行签名，那么接受者可以将签名提供给第三方。第三方可以通过验证公式来验证这个签名是否是签名者对该消息的签名。由于第三方在验证过程中不需要签名者的协助，所以这就可以防止签名者否认他的签名。

3.4 不知明文密文对的攻击[31]

(1)攻击者想要直接通过Y=xG解出x是不可实现的，因为这需要求解椭圆曲线上的离散对数的数学难题。

(2)攻击者想要通过验证式(18)伪造m′的签名(e′,s′)是不可实现的，因为攻击者需要先确定一个r′(或s′)，再去求解s′(或r′)，这都需要求解椭圆曲线上离散对数这个数学难题。

kG=w-1sY+rwG

(18)

3.5 抵抗替换消息伪造签名攻击

攻击者想通过加减乘除将式(19)中的e替换成e′是做不到的，因为该签名方程涉及e2项。另外，在替换的同时难以保证r′=xmodn(其中k′G=(x,y))。

s=ke-rxe2modn

(19)

由改进方案的安全性分析可知，改进方案的安全性应该不低于ECDSA方案的安全性。与文献[9]方案相比，改进方案涉及e和e2，大大增加了其对替换消息攻击的抵抗。

4 效率分析

从算法运算量角度分析，设模乘运算的数据规模是n，1次倍点运算复杂度是O(n2)，1次模逆运算复杂度是O(9n2)(相当于9次倍点运算)，1次模乘运算复杂度是O(n2log2n)[32]。将本文方案的运算量与文献[9]方案、ECDSA方案的运算量进行对比，结果如表1所示。

表1 方案效率比较

由表1可知，ECDSA的总运算量为:

N1=O[(4log2n+22)n2]

(20)

文献[9]方案的总运算量为：

N2=O[(4log2n+12)n2]

(21)

本文方案的总运算量为：

N3=O[(6log2n+13)n2]

(22)

本文方案在签名验证上虽然无法与文献[9]方案比较，但是其签名验证效率不低于ECDSA方案。影响复杂度的主要运算是模乘运算和模逆运算。本文方案在密钥生成时与另外两种方案的复杂度相同。在签名阶段，改进方案比另外两种方案多了1次模乘运算，少了1次模逆运算；在签名验证阶段，本文方案虽然比文献[9]方案多了1次模乘运算、1次模逆运算和1次倍点运算，但是本文方案不仅能防止消息伪造签名攻击，还能防止随机数攻击。总体来说，本文方案加强了安全性，适当牺牲了速度。

5 结 语

本文首先对文献[9]方案进行重点研究和分析，发现该方案存在替换消息伪造签名的安全隐患。针对此安全隐患，本文提出了一个新的改进方案，并对其进行安全性证明。本文方案虽然在效率上有待提高，但是其不仅能防止消息伪造签名攻击，还能防止针对随机数的攻击以及不知明文密文对的攻击。总的来说，改进后方案在安全性上有了很大的提高。因此，本文方案适用于对效率要求较低、对安全性要求高的应用场合。