基于椭圆曲线的数字签名方案，也称为椭圆曲线数字签名算法。椭圆曲线数字签名方案是DSA算法在椭圆曲线上的模拟，只是群元素由素域中的元素数换位有限域上椭圆曲线上的点。
椭圆曲线数字签名算法的安全性
椭圆曲线密码体制的安全性是基于椭圆曲线离散对数难题的。与整数因子分解问题和模P的离散对数问题一样,目前还没有对椭圆曲线离散对数问题的有效解法,所以本方案是安全的。椭圆曲线公钥密码体制(ECC)的安全性依赖于椭圆曲线离散对数问题的困难性。
椭圆曲线数字签名算法的应用
椭圆曲线数字签名算法具有计算参数更小、密钥更短、安全强度更高、运算速度更快、签名也更加短小、软硬件实现节省资源等特点,尤其适用于处理能力、存储空间、带宽及功耗受限的场合。
椭圆曲线数字签名算法的不足之处
(1)在 椭圆曲线数字签名算法的签名和验证算法中,都含有求逆运算,这种运算复杂而费时。一般对一个大整数求逆,若是采用扩展欧几里德算法来求逆,平均需完成0.8413log2n+1.47次除法,运算是很慢的。
(2)由签名算法中s=k-1(e+rx)mod q可以知道,在生成签名时必须要求k的逆,所以,在这里对进行秘密分享,即密钥分割和合成都是很困难的,也就很难直接运用于群签名和门限签名方案中。
2)改进的椭圆曲线数字签名算法
鉴于 椭圆曲线数字签名算法存在的上述不足之处,提出了一种改进的去逆的椭圆曲线数字签名方案,下面将这个方案完整地叙述如下:
设椭圆曲线公钥密码系统参数为(Fq,E,G,P,q,a,b,h),其中, Fq是有限域;E是Fq上的椭圆曲线;G是E上的q阶生成元(q为一大素数),称为基点;a、b是椭圆曲线E的系数;P为椭圆曲线上的点;h是一个单向安全的哈希函数。
假设用户A要对信息m作数字签名发送给B(Bob),则签名过程如下:
1)签名者密钥对的生成
(1)签名方A随机选择一个整数x(1≤x≤q-1)作为私钥,即签名者的密钥为SK={x}。
(2)计算签名方A的公钥y=xG,即签名者的初始公钥PK={y}。
(3)由以上两步可以得到签名方A的签名密钥和公钥对为(SK,PK),其中SK={x}，PK={y}。
2)签名过程
签名方A随机选取一个整数k(1≤k≤q-1),计算:P=KG=(u, v), r=u mod q
(2)m为消息,计算e=h(m)
(3)计算s=k-erx
(4)以(r,s)作为签名方A对消息m的签名发送给验证方B
3)验证过程
(1)验证方B计算e=h(m)。
(2)P’=(u’,v’)=sG+ery
(3)如果P’=0则验证方B拒绝这个签名;否则计算r’= u’ mod q,若r’=r,则接收这个签名。
只有签名方A才知道他的私钥x,对于任何第三者要假冒签名方A的签名,或更改经签名方A签名后的消息,都是难以通过验证的。同样签名方A对消息签名后,也是不能否认的。
4)该方案的有效性证明
因为
P’=(u’, v’)
=sG+ery
=sG+erxG
=(s+erx)G
=(k-erx+erx)G
又因为:
P=kG=(u, v)
所以
P’=P, u’=u,r’=r
故该方案是正确的、有效的。
5)方案的分析及安全性证明显然,该方案的安全性与 ECDSA的安全性相同,都依赖于由G和kG求解k的难度。它基于椭圆曲线离散对数难题。由于目前还没有对椭圆曲线离散对数问题的有效解法,所以本方案是安全的。
