椭圆曲线数字签名的两种改进算法

李明株，刘瑞芹

(华北科技学院 理学院，北京 东燕郊 065201)

0 引言

上世纪九十年代，通用的是 RSA 公钥密码体制，密钥长度一般为512bit。1999年RSA-512被破解，之后只能用加长密钥保证信息的安全性，导致运行速度更加缓慢。1985年，Koblitz[1]和Miller[2]提出将椭圆曲线用于公钥密码学的思想，标志着椭圆曲线密码体制(ECC，Elliptic Curve Cryptography)的诞生。ECC是建立在基于椭圆曲线上的点构成的Abelian加法群的离散对数问题上的密码体制。研究表明：基于有限域上椭圆曲线的离散对数问题运算位数远小于传统离散对数的运算位数，它可以使用较短的密钥达到较高的安全性，且计算速度快、存储量小、带宽要求低[3]。

数字签名在网络环境中可以代替传统手写签名或印章，是实体签名的信息化实现。使用数字签名技术能够使得发送者事后不能否认发送的签名信息、接收者能够核实但不能伪造或篡改发送者的签名信息。数字签名是提供身份认证、确保信息完整性、不可伪造性、不可否认性的重要信息技术。Jonhson和Menezes于1999年提出了基于椭圆曲线的数字签名算法(ECDSA)。椭圆曲线数字签名算法也成为目前研究的热门问题[4-6]。

1 椭圆曲线密码体制

1.1 有限域上的椭圆曲线

椭圆曲线密码体制[7，8]的有效实现主要用到两种类型的有限域，它们是素数域GF(p)和二元域GF(2)上的扩域GF(2m)。

素数域GF(p)：设p是一个大素数，GF(p)={0，1，2…，p-1}。

二进制扩域GF(2m)：由二元域GF(2)上所有次数小于m的多项式组成，即：

GF(2m)={am-1xm-1+am-2xm-2+…a1x+a0}，ai={0,1}。

域元素(am-1xm-1+am-2xm-2+…+a1x+a0)通常用长度为m的二进制串(am-1，am-2，…，a1，a0)表示，则GF(2m)={(am-1，am-2，…，a1，a0)},ai={0,1}。扩域GF(2m)中包含2m个元素。

(1) 有限域GF(p)上的椭圆曲线是对于给定a,b(4a3+27b2)modp≠0，满足方程：

y2=x3+ax+bmodp

的所有解(x,y)构成的点集，外加无穷远点O构成的一个群E(Fp)。其中a,b,x,y均在有限域GF(p)={0，1，2…，p-1}中取值，E(Fp)称为椭圆曲线群。

(2) 有限域GF(2m)上的椭圆曲线满足方程：y2+xy=x3+ax2+b

的所有解(x,y)构成的点集，外加无穷远点O构成一个椭圆曲线群E(F(2m))。

其中a,b,x,y均在有限域GF(2m)中取值。

在椭圆曲线群中，使nG=0的最小正整数n称为点G的阶数。

椭圆曲线上的离散对数问题：在曲线上两个点P和Q满足Q=kP，其中k为常数。已知k和P求Q容易，已知P和Q求k的问题是离散对数问题，求解却很困难，是建立椭圆曲线密码体制的数学依据。

1.2 椭圆曲线加解密算法

椭圆曲线密码体制是将加密问题转换为椭圆曲线群中元素的计算问题，采取非对称的公、私双秘钥方式进行加解密运算。下面以素数域上的椭圆曲线为例介绍一种利用椭圆曲线群实现加、解密的方法。

首先选定椭圆曲线y2=x3+ax+bmodp。寻找一个阶数为n的点G，要求n为一个大素数，称为基点。把要发送的明文m嵌入到群E(Fp)上的点Pm[9，10]，然后对消息Pm进行加、解密：

用户A，选取一个整数dA作为私钥，对应的公钥为pA=dAG。

用户B，选取一个整数dB作为私钥，对应的公钥为pB=dBG。

用户A向用户B发送信息Pm，进行秘密传输。

1.2.1 加密过程

(1) 用户A随机选取一个正整数k∈[1,n-1]；

(2) 计算点Pk=kG；

(3) 利用用户B的公钥pB，计算点kpB；

(4) 计算点Pm+kpB；

(5) 形成密文C=(Pk,Pm+kpB)，由一对椭圆曲线群E(Fp)中的点组成。

1.2.2 解密过程

(1) 用户B接收到密文C=(Pk,Pm+kpB)；

(2) 用私钥dB计算点dBPk；

(3) 计算点(Pm+kpB)-dBPk，得到消息Pm=(Pm+kpB)-dBPk。

事实上，(Pm+kpB)-dBPk=(Pm+kdBG)-dBkG=Pm。

上述过程表明，用户A通过将kpB与Pm相加来伪装消息Pm，实现加密。因为k是用户A随机选取的，只有用户A知道，加解密过程中的主要计算是点的倍乘运算，其他人无法从Pk=kG中解出k，就无法消除伪装，提高了加密的安全性。

2 椭圆曲线密码数字签名的算法

数字签名算法包括两个部分，即签名算法和验证算法。发送者签名时用私钥对明文或消息摘要实施加密运算，然后把加密的数据传给接受者，因他人无法知道私钥，故不能伪造签名。接收者验证签名时利用发送者的公钥进行验证，将结果与消息或者摘要进行比较，当且仅当两者相同，就接收签名。

在SEC(Standards for Efficient Cryptography)制定的ECC工作草案中[11]，定义椭圆曲线参数的形式是一个六元偶，记作：R={q,a,b,G,n,h}

其中：

(1) 整数q表示椭圆曲线基域F(pm)中域元素的个数；

(2)a,b表示椭圆曲线方程的系数；

(3)G是椭圆曲线点群的一个基点；

(4)n是椭圆曲线基点G的阶；

(5)h是余因子，利用h可以较快地找到基点G。

椭圆曲线数字签名ECDSA(Elliptic Curve Digital Signature Algorithm)是不带有消息恢复功能签名方案[12]，需要使用的参数有：椭圆曲线参数六元偶；待签名消息m；签名者A的密钥对(d,Q)，其中Q=dG，d是私钥、Q是公钥。

签名生成过程：

输入：R={q,a,b,G,n,h}，私钥d、消息m

输出：(r,s)

(1) 随机地选取一个整数k∈[1,n-1]

(2) 计算kG=(x1,y1)，r=x1modn，如果r=0则返回到1；

(3) 计算e=SHA-1(m)；

(4) 利用签名者A的私钥计算s=k-1(e+dr)modn，如果s=0则返回1；

(5) (r,s)是A对消息m的签名。A发送给接收者B消息m及签名(r,s)。

签名验证：

输入：R={q,a,b,G,n,h}，公钥Q、消息m

输出：验证(r,s)是对消息m的签名是否正确。

(1) 验证(r,s)是[1,n-1]中的整数；

(2) 计算e=SHA-1(m)；

(3) 计算w=s-1modn；

(4) 计算u1=ewmodn,u2=rwmodn；

(5) 利用签名者A的公钥计算X=u1G+u2Q=(x2,y2)；

(6) 判定：如果X=O则拒绝签名，否则计算v=x2modn，当v=r时接受这个签名。

签名验证的证明：

因为(r,s)是签名者A对消息m的签名，

则s=k-1(e+dr)modn，

从而

k=s-1(e+dr)=s-1e+s-1dr=we+wdr=u1+u2d

所以X=u1G+u2dG=(u1+u2d)G=kG即v=r。

从上述算法知道，A是利用随机数k和私钥d，对消息m进行的签名，B是利用r和公钥Q对签名进行验证。这个过程中无法通过r和公钥Q来计算k和私钥d，这就使得ECDSA算法非常安全。

3 两种改进的数字签名算法

在数字签名前，对于待签明文m的处理有两种方法，一种方法用密码杂凑函数即哈希函数计算e=H(m)，并转化为一个整数。另一种方法是把明文m与椭圆曲线上的点建立对应关系，利用嵌入算法把明文用椭圆曲线上的点Pm来表示[13，14]。对哈希函数值e和椭圆曲线上点pm的签名就是对明文消息m的签名。根据这两种情况对数字签名算法进行了改进。

3.1 明文m利用哈希函数处理的数字签名改进算法

3.1.1 签名生成过程

输入：R={q,a,b,G,n,h}，私钥d、明文m

输出：(r,s)

(1) 随机地选取一个整数k∈[1,n-1]；

(2) 计算kG=(x1,y1)；

(3) 计算e=SHA-1(m)；

(4) 计算r=(x1+e)modn，如果r=0则返回1；

(5) 利用签名者A的私钥计算s=(k-dr)modn，如果s=0则返回到1；

(6) (r,s)是A对消息m的签名。A发送给接收者B消息m及签名(r,s)。

3.1.2 签名验证

输入：R={q,a,b,G,n,h}，公钥Q、消息m

输出：验证(r,s)是对消息m的签名是否正确。

(1) 验证(r,s)是[1,n-1]中的整数；

(2) 计算e=SHA-1(m)；

(3) 利用签名者A的公钥计算：

X=sG+rQ=(x2,y2)

(4) 判定：如果X=O则拒绝签名。否则计算v=(x2+e)modn，当v=r时接受这个签名。

3.1.3 签名验证的证明

因为(r,s)是签名者A对消息m的签名，则s=(k-dr)modn，从而

X=sG+rQ=(k-dr)modnG+rdmodnG=kG

所以v=r。

3.2 明文m用椭圆曲线上的点Pm来表示的数字签名改进算法

3.2.1 签名生成过程

输入：R={q,a,b,G,n,h}，私钥d、消息Pm

输出：(r,s)

(1) 随机地选取一个整数k∈[1,n-1]

(2) 计算Pm+kG=(x1,y1)；

(3) 计算r=x1modn，如果r=0则返回到1；

(4) 利用签名者A的私钥计算

s=(k-dr)modn，如果s=0则返回到1；

(5) (r,s)是A对消息m的签名。A发送给接收者B消息m及签名(r,s)。

3.2.2 签名验证

输入：R={q,a,b,G,n,h}，公钥Q、消息Pm

输出：验证(r,s)是对消息m的签名是否正确。

(1) 验证(r,s)是[1,n-1]中的整数；

(2) 利用签名者A的公钥计算：

X=Pm+sG+rQ=(x2,y2)

(3) 判定：如果X=O则拒绝签名，否则计算v=x2modn，当v=r时接受这个签名。

3.2.3 签名验证的证明

因为(r,s)是签名者A对消息m的签名，则s=(k-dr)modn，从而

X=Pm+sG+rQ=Pm+[(k-dr)modn]G+[rdmodn]G

=Pm+kG

所以v=r。

3.3 改进的ECDSA算法安全性分析及其特点

安全性分析：

(1) 签名算法中s=(k-dr)modn，一个方程中包含随机数k和私钥d两个量，攻击者无法求解；

(2) 从验证方程X=sG+rQ和X=Pm+sG+rQ中无法求得私钥，保证了消息的真实性；

(3) 如果签名是伪造的，验证方程不能通过，签名不能否认。

改进的数字签名方案对Hash值e应用模n做了约简，具有以下几方面的特点：

(1) 签名算法的生成和验证过程比较简单；

(2) 避免了求模逆的运算，提高了计算速度，对计算机硬软件的要求更低；

(3) 算法能够保证签名文件的安全。

4 结论

(1) 本文对椭圆曲线密码体制和数字签名算法进行了研究,给出了一种明文m利用哈希函数处理的数字签名改进算法；给出了一种明文m用椭圆曲线上的点Pm来表示的数字签名改进算法。

(2) 两种改进的数字签名算法，能够保证签名的安全性，避免了求模逆的问题，减少了运算量，对系统要求更低。研究具有一定的理论意义和实际应用价值。

(3) 从安全性和算法有效性的角度来看，数字签名算法有进一步改进的可能，下一阶段将继续研究。