ECDSA算法简介及优化方法

ECDSA算法是基于椭圆曲线的数字签名算法，目前已经被标准化，并在IEEEP1363和ANSIX9.62中被采纳，未来几年很可能取代DSA而成为新的数字加密标准。ECDSA是一种不带消息恢复功能的签名方案，其安全性基于计算椭圆曲线离散对数问题的困难性。

椭圆曲线的参数为（E（GF（q）），a，b，G，n，h）。其中G为选择的基点，n为G的阶，h=E（GF（q））/n。

1.密钥生成

ECDSA的密钥对生成很简单。首先选取一个随机数d∈[1，n-1]作为私钥，然后，计算Q=dG，作为公钥。

2.签名生成

对明文m的签名算法如下：

1）选取一个随机数k，1≤k≤n-1。

2）计算kG=（x₁，y₁），r≡x₁mod n。若r=0，则转1。

3）计算k⁻¹modn。

4）计算e=Hash（m）。

5）计算s≡k⁻¹（e+dr）mod n。若s=0，则转1。(www.xing528.com)

签名为（m，r，s）。

3.签名验证

对一个签名（m′，r′，s′）的验证过程如下：

1）验证r′和s′是（1，n-1）间的整数。

2）计算e=Hash（m′）。

3）计算w≡s′⁻¹mod n。

4）计算u₁≡ew mod n，u₂≡r′w mod n。

5）计算X=u₁G+u₂Q=（x₁，y₁），令v≡x₁ mod n。

如果r'=v则接受签名，否则拒绝。