ECDSA数字签名算法

一、ECDSA概述

椭圆曲线数字签名算法（ECDSA）是使用椭圆曲线密码（ECC）对数字签名算法（DSA）的模拟。ECDSA于1999年成为ANSI标准，并于2000年成为IEEE和NIST标准。它在1998年既已为ISO所接受，并且包含它的其他一些标准亦在ISO的考虑之中。与普通的离散对数问题（discrete logarithm problem DLP）和大数分解问题（integer factorization problem IFP）不同，椭圆曲线离散对数问题（elliptic curve discrete logarithm problem ECDLP）没有亚指数时间的解决方法。因此椭圆曲线密码的单位比特强度要高于其他公钥体制。

数字签名算法（DSA）在联邦信息处理标准FIPS中有详细论述，称为数字签名标准。它的安全性基于素域上的离散对数问题。椭圆曲线密码（ECC）由Neal Koblitz和Victor Miller于1985年发明。它可以看作是椭圆曲线对先前基于离散对数问题（DLP）的密码系统的模拟，只是群元素由素域中的元素数换为有限域上的椭圆曲线上的点。椭圆曲线密码体制的安全性基于椭圆曲线离散对数问题（ECDLP）的难解性。椭圆曲线离散对数问题远难于离散对数问题，椭圆曲线密码系统的单位比特强度要远高于传统的离散对数系统。因此在使用较短的密钥的情况下，ECC可以达到于DL系统相同的安全级别。这带来的好处就是计算参数更小，密钥更短，运算速度更快，签名也更加短小。因此椭圆曲线密码尤其适用于处理能力、存储空间、带宽及功耗受限的场合

二、ECDSA原理

签名过程如下：

1、选择一条椭圆曲线Ep(a,b)，和基点G；

2、选择私有密钥k（k<n，n为G的阶），利用基点G计算公开密钥K=kG；

3、产生一个随机整数r（r<n），计算点R=rG；

4、将原数据和点R的坐标值x,y作为参数，计算SHA1做为hash，即Hash=SHA1(原数据,x,y)；

5、计算s≡r - Hash * k (mod n)

6、r和s做为签名值，如果r和s其中一个为0，重新从第3步开始执行

验证过程如下：

1、接受方在收到消息(m)和签名值(r,s)后，进行以下运算

2、计算：sG+H(m)P=(x1,y1), r1≡ x1 mod p

3、验证等式：r1 ≡ r mod p

4、如果等式成立，接受签名，否则签名无效。

原论文如下：

https://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/

在之前的文章中，我们已经认识了什么是椭圆曲线，并且为了更好得使用数学方法来处理椭圆曲线上的点，我们定义了「群」，接着我们又进一步将椭圆曲线限制在了整数取模素数的有限域上，椭圆曲线上的点在有限域上形成了循环子群，并且我们也介绍了「基点」、「阶」和「辅因子」的概念。

最后，我们知道在有限域上计算标量积是一个容易的过程，但是离散对数问题却是非常难的，现在我们就来看看这些理论是如何应用在密码学上的。

主要参数

椭圆曲线算法将会运用在有限域上的椭圆曲线所形成的循环子群上，因此，我们的算法需要以下几个参数：

• 素数 p，用于确定有限域的范围

• 椭圆曲线方程中的 a，b 参数

• 用于生成子群的的基点 G

• 子群的阶 n

• 子群的辅助因子 h

所以，我们算法的主要参数可以定义为一个六元组 (p, a, b, G, n, h)

随机曲线

「离散对数问题很困难」这种说法其实不完全正确，有一类椭圆曲线特别的弱以至于一些不怀好意的算法可以有效率的求解离散对数问题。例如，具有 p = hn（这意味着有限域的阶等于椭圆曲线的阶） 性质的所有曲线对于 smart 攻击是脆弱的，这就可以被用来在经典计算机上，多项式时间内解决离散对数问题。

现在，假设我给你一个曲线的主要参数，有可能我发现了一种新的没人知道的弱曲线，而且我已经在我给你的曲线上构建了一个快速算法，可以用来求解离散对数问题，我怎么样能让你确认我给你的曲线是安全的（换句话说，它不能被我用来做一些特殊攻击）？

为了解决这个问题，有时候我们需要另一个参数：种子 S，这是一个用来生成参数 a， b 或者基点 G，或者三个参数都生成的随机数，这些参数是通过计算种子 S 的哈希值得到的。哈希值，我们知道的，是正向计算容易，反向计算困难的。

通过种子生成的曲线是可验证随机性的，使用哈希来生成参数的原则是众所周知的「Nothing-up-my-sleeve number」，这个原则也被运用在密码学中。

种子 S 可以提供一种保证，使提供曲线的人不会知道一些特殊的攻击漏洞。如果我将种子 S 和曲线一起提供给你，这就意味着我不会任意地选择参数 a 和 b，你也就可以相对确认我不能够发起一些特数目的的攻击，为什么是「相对」的呢，这个稍后解释。

生成和检查随机曲线的标准算法在 ANSI X9.62 中有描述，这是一个基于 SHA-1 的算法。如果你感兴趣，可以了解用于在 SECG 规范上生成可验证随机曲线的算法（找到 "Verifiably Random Curves and Base Point Generators"）

ECDH

ECDH 是椭圆曲线的笛福赫尔曼算法的变种，它其实不单单是一种加密算法，而是一种密钥协商协议，也就是说 ECDH 定义了（在某种程度上）密钥怎么样在通信双方之间生成和交换，至于使用这些密钥怎么样来进行加密完全取决通信双方。

我们需要解决的问题通常是这样的：Alice 和 Bob 想要安全通信，中间人可能会窃听消息，但是没办法解密消息

那么 ECDH 是这样的：

1. Alice 和 Bob 生成各自的私钥和公钥，Alice 的私钥为d_A ,公钥为H_A=d_AG 。Bob 的私钥为d_B,公钥为H_B=d_BG,注意，Alice 和 Bob 需要使用一样的主要参数：在同一条曲线的同一个有限域上选择一样的基点G。

2. Alice 和 Bob 通过不安全信道交换各自的公钥H_A和H_B,中间人可以窃听到H_A 和H_B ,

但是在无法攻破离散对数难题的情况下无法得到d_A 和d_B 。

3. Alice 计算S=d_AH_B (使用自身的私钥和 Bob 的公钥), Bob 计算S=d_BH_A (使用自身的私钥和 Alice 的公钥), 双方求得的S 是一样的，因为

S=d_AH_B=d_A(d_BG)=d_B(d_AG)=d_BH_A

中间人只知道公钥以及椭圆的公共参数，是无法算出共享密钥 S 的，这其实就是笛福赫尔曼问题：

给定三个点 P，aP，bP，那么 abP 的结果是什么？

形如给定三个点，K , K^X,K^Y,那么K^{XY}的结果是什么？

算法的正确性

算法的逻辑一开始看不是很容易理解，如果我们把前面用到的公式整合联立一下，就变得清晰了

我们从P=u_1G+u_2H_A开始，通过公钥的定义我们知道H_A=d_AG所以我们得到：

使用u_1 和u_2 的定义，可以得到：

这里为了简单先忽略 mod n ,因为由G 生成的循环子群的阶为n , 所以这里的 mod n 其实也

是没必要的。再往前，我们定义了,式子两边同乘以k 再同除s ,也就是：

k=s^{-1}(z+rd_A)\operatorname{mod}n,把这个结果带到上面关于 P 的等式中得到：

得证。