基于椭圆曲线和RSA的数字签名的性能分析
来源： 作者： 时间：2007-02-28 20:16
1 引 言
数字签名是实现认证的重要工具，他在身份认证、数据完整性、抗抵赖性以及匿名性等方面有重要的应用，是电子商务应用、电子政务推广中的核心技术，数字签名能保证文件中每页内容均不会被改动或替换。数字签名是特指以公钥密码实现的签名，或者可以定义为记录的一次变换，通过一个非对称密码系统和一个杂凑函数，使得有初始记录和签名者公钥的任何人都可以准确地判断该变换是否由相对应的私钥产生、初始记录在变换之后是否被修改。
常用的数字签名体制：RSA，EIGamal，ECC。其中基于RSA的数字签名算法现在应用十分广泛，而基于ECC的数字签名算法ECDSA则是未来签名算法的热点方向，本文就两种算法的性能进行了分析和比较，同时讨论了各自的应用范围。
2 RSA的数字签名算法
RSA算法是公钥密码体制中最著名的算法，他是以其发明人Rivest，Shamir和Adleman三人的首字母来命名的。RSA是建立在大整数分解的困难上的，是一种分组密码体制。RSA即可用于数据加密，也可用于数字签名。
2．1 RSA数字签名算法密钥对产生的过程
(1)选择2个大的素数p，q。
(2)计算n：n=pq。
(3)随机选取e，满足1<e<φ(n)，gcd(e．φ(n))=1，那么公钥就是(e，n)。
(4)计算d：满足ed=1 mod φ(n)，那么私钥就是(d，n)。
2．2 RSA数字签名算法的签名过程
假设待签名的消息为M：
(1)计算消息的散列值H(M)。
(2)用私钥(d，n)加密散列值：s=(H(M))dmod n。签名结果就是：s。
(3)发送消息和签名(M，s)。
2．3 RSA数字签名算法的验证过程
(1)取得发送方密钥(e，n)。
(2)解密签名s：h=se mod n。
(3)计算消息的散列值H(M)。
(4)比较，如果h=H(M)，表示签名有效；否则签名无效。
3椭圆曲线数字签名算法ECDSA
椭圆曲线签名算法ECDSA是基于椭圆曲线密码体制(ECC)的数字签名算法。DSA是美国国家标准局制定的数字签名算法，他是建立在有限域乘法群上的。对于有限域上的椭圆曲线密码系统，数字签名标准建议采用椭圆曲线数字签名算法ECDSA，下面给出该算法的过程。
假设一组椭圆曲线的参数组为(q，FR，a，b，G，n，h)。其中q是域的阶，FR指示域中元素的表示方法，a，b是两个系数，G是基点，G的阶为n，余因子h=#E(Fq)／n，他是一个小的素数。
3．1 ECDSA密钥对生成过程
(1)选择一个随机数d，d∈(1，n-1)。
(2)计算Q，Q=dG。
(3)那么公钥为Q，私钥为整数d。
3．2 ECDSA签名过程
假设待签名的消息为，m；
(1)选择一个随机数k，k∈(1，n-1)。
(2)计算kG=(x1,y1)。
(3)计算r=x1 mod n；如果r=O，则返回到步骤(1)。
(4)计算k-1 mod n。
(5)计算e=SHA1(m)。
(6)计算s=k-1(e+dr)mod n，如果s=O，则返回到步骤(1)。
(7)对消息的签名为(r，s)，最后签名者把消息m和签名(r，s)发送给接收者。
3．3 ECDSA密钥对验证过程
获得发送者的公钥Q开始验证：
(1)检查r，s，要求r，s∈(1，n-1)。
(2)计算e=SHA1(m)。
(3)计算w=s-1mod n。
(4)计算u1=ew mod n；u2=rw mod n。
(5)计算X=u1G+u2Q。
(6)如果X=O，表示签名无效；否则，X=(x1，y1)，计算v=x1modn。
(7)如果v=r，表示签名无效；否则表示签名有效。
4两种签名性能比较
本文利用C++编程仿真基于ECC的数字签名算法ECDSA和基于RSA的数字签名算法的运算时间和密钥的字节数。
4．1 比较依据
根据文献[1]的描述，我们可以认为下列对应的密钥长度具有相同的安全性能(表1)。
