椭圆曲线数字签名简介

椭圆曲线数字签名算法（ECDSA）是使用椭圆曲线对数字签名算法（DSA）的模拟。它先后成为ANSI、IEEE、NIST和ISO的标准，而且其他的一些组织正在考虑将其成为标准。由于ECDSA具有系统参数小、处理速度快、密钥尺寸小、抗攻击性强和带宽要求低等优点，它在电子商务、电子政务、电子选举等领域中得到广泛应用。

1.ECDSA签名的生成与验证算法

（1）参数定义和密钥生成

●E_p（a，b）为定义在有限域GF（p）上的椭圆曲线（p为大于3的素数）；

●G（x，y）是在E_p（a，b）上选取的一个拥有素数阶n的点；

●每个用户选取一个大整数d（1＜d＜n）作为私钥（严格保密）；

●点Q=d·G为公钥。

（2）签名算法

设签名者A拥有私钥d，待签名的消息为M，签名者进行以下操作：

1）用SHA-1算法计算消息摘要h（M），它是一个160bit的整数。

2）在区间[1，n-1]中选择一个随机整数k。

3）计算椭圆曲线上的点（x₁，y₁）=kG，取r≡x₁（mod n），若r=0，返回2）。(www.xing528.com)

4）计算s≡k^-1（h（M）+dr）（mod n），若s=0，返回2）；否则，签名者A把（r，s）作为消息M的数字签名，与M一起发送给接收者B。

（3）验证算法

接收者B在接收到消息M和数字签名（r，s）后，对签名的验证过程如下：

1）验证r和s是否是区间[1，n-1]中的整数，若不是，则拒绝签名。

2）同样用SHA-1算法计算消息摘要h（M）。

3）计算u₁≡h（M）·s^-1（mod n）和u₂≡rs^-1（mod n）。

4）用签名者A的公钥Q计算：（x₂，y₂）=u₁·G+u₂·Q，取v≡x₂（mod n）。

5）若v=r，接受签名，否则拒绝签名。

2.ECDSA的安全性

由于椭圆曲线数字签名算法（ECDSA）是椭圆曲线密码（ECC）的基本原理在数字签名中的应用，故ECC的安全性就是ECDSA的安全性。ECC和其他几种公钥密码体制相比，其抗攻击性具有绝对的优势。以当前应用较为广泛的公钥密码体制RSA为例，RSA的优点主要在于原理简单，易于使用。但是，随着整数因子分解方法的不断完善、计算机速度的提高以及计算机网络的发展，对RSA加/解密安全保障的大整数位数要求越来越长。要保证RSA使用的安全性，就要相应地增加其密钥的位数，但是，密钥长度的增加导致了其加/解密速度大大降低，硬件实现也变得越来越困难，这对使用RSA的应用带来了很重的负担，从而也使得应用范围越来越受到限制。相反，ECC能够对较短的密钥长度提供更大的安全性。如160bit ECC与1024bit RSA、DSA有相同的安全强度，而224bit ECC则与2048bit RSA、DSS具有相同的安全强度。

ECDSA的安全目标是，在现有软、硬件条件下使用选择明文攻击签名不可伪造。对一个合法用户A发动此类攻击的攻击者的攻击目标是：在获取A在攻击者所选择的消息集上的签名之后，能获取A在某一单条消息上的有效签名。Pointcheval和Stern已经证明：基于椭圆曲线离散对数问题且所使用的Hash函数是随机函数的前提下，对于选择明文攻击，ECDSA在现有的情况下是不可伪造的。Brown也证明了在基本群为普通群且所使用的Hash函数是抗碰撞的前提下，ECDSA本身是安全的。