比特币协议里使用了 ECDSA （椭圆曲线签名算法），我之前以为它和基于大数分解的 RSA 公钥密码体系差不多。这两天看了下维基百科，才发现它们之间的差异挺大。
最本质的区别是， DSA 和 ECDSA 都只是签名算法，它用来确保信息发布人的身份和信息的完整性，不能用来做加密传输，为了实现这个功能，信息的原文（或者HASH 摘要）必须随着签名一起传输和公布才能被验证。而 RSA 是公钥加密体系，它可以用来加密传输（即信息原文在传输中加密，到达对方后解密），它也可以实现签名验证。
DSA 和 ECSDA 的基本架构和 RSA 一样，签名者持有私钥，对应公钥向全世界公开。当需要对信息签名时，签名者用私钥对信息签名，然后将签名信息和信息原文发给对方（ RSA 协议中，信息原文不需要发给对方，签名信息解密后就是信息原文），验证者可用签名者公开的公钥对签名信息和信息原文验证签名。由于信息长度可能比较长，在实际操作中，大家通常在信息的 HASH 摘要上进行签名。
1、DSA 协议
DSA （ Digital Signature Algorithm ）的密码学基础是$ F_p$ 域上的乘方速度很快（即已知$ a, t$ ，可快速计算$ a^t\mod p$ ），但判断乘方阶却很慢（即已知$ a, b$ ，求$ t$ 使得$ a^t=b\mod p$ 很慢）。
基础信息
- 选择合适的HASH 函数，目前常用的是 SHA-1 和 SHA-2。
- 选择密钥长度 L 和 N ，它们也代表了签名的密码学强度。一般 L=1024 ， N=160。
- 选择 N 个比特位的素数 q （约等于$ 2^N$ )。
- 选择 L 个比特长度的素数 p ，使得 p-1 能被 q 整除。
- 选择 g ，使得它在$ g^q \mod p = 1$ ，并且不存在更小的阶。选取$ g=h^{(p-1)/q}$ ，随机选取$ h$ 得到的不等与 1 的$ g$ 就满足要求。
这些基础信息可以在不同人之间共享，甚至直接写入协议。
生成密钥和公钥：
- 随机选取$ x$ ，满足$ 0 \le x \le q$ 。
- 计算$ y=g^x \mod p$ 。
$ x$ 便是私钥，$ y$ 是公钥。$ p, q, g$ 是基础信息可以作为公钥的一部分，也可以作为公开协议的一部分进行约定。
开始签名：
假设$ H$ 是 Hash 函数，若有信息$ m$
- 随机选择$ k$ ，满足$ 0\le k\le q$ 。
- 计算$ r= (g^k \mod p) \mod q$ 。
- 如果$ r=0$ ，回到第一步重新选择$ k$ 。
- 计算$ s = k^{-1}(H(m)+xr) \mod q$ 。
- 如果$ s=0$ ，回到第一步重新选择$ k$ 。
那么信息的签名便是$ r, s$ ，它随着信息 Hash 码$ H(m)$ 一起向对方提供。
验证者收到签名后进行以下验证：
- 若$ 0\le r \le q$ 或者$ 0\le s\le q$ ，拒绝其签名。
- 计算$ w=s^{-1} \mod q$ 。
- 计算$ u_1 = H(m)w\mod q$ 。
- 计算$ u_2 = rw\mod q$ 。
- 计算$ v=( g^{u_1}y^{u_2}\mod p)\mod q$ 。
- 当且仅当$ v=r$ 时，通过签名验证。
为什么这样可以验证签名：
根据$ g$ 的选择，$ g^q = 1\mod p$ ，因此：
2、ECDSA 协议
ECDSA （ The Elliptic Curve Digital Signature Algorithm ）协议框架和 DSA 基本一致，只不过 ECDSA 使用的椭圆函数域，而 DSA 使用普通乘法域$ Z_p$ 。DSA 中所使用模$ p$ 下的乘法运算对应 ECDSA 的椭圆函数域下的加法运算。
综述文章（http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa-cert.pdf）详细描述了 ECDSA 的代数学原理。
3、有了 RSA 为什么还需要 DSA ？
从功能上说， RSA 的功能比 DSA 更广。DSA 只能用于签名和验证，不能用于加密和解密。双方的安全性和强度也没有明显区别。为什么科学家还要发明 DSA ，工程界也愿意接受呢？
一个可能的原因是专利。RSA 发明后被申请了专利，并且有专门的公司进行商业化运作。而 DSA 的专利被买断然后免费提供给大家用。
不过 RSA 的专利已于 2000 年到期，现在没有使用 RSA 的障碍。业内现在推荐使用 RSA 替代 DSA。
4、弱点
这篇综述文章的 Security Consideration 章节提到了 DSA 和 ECDSA 的超过 20 个方方面面的弱点，不恰当的曲线、基点、素数、随机数方法的选择都会带来风险。
维基上提到的最直接的弱点是上面的$ k$ 。从公式中可以看出，从$ k$ 可以推断出私钥$ x$ 。$ k$ 必须确保随机、保密且唯一，否则便会带来对私钥的攻击。在两次签名中使用同样的$ k$ （即使$ k$ 保密）、 $ k$ 可预测、甚至泄漏$ k$ 的一些字节，都足以攻击 DSA。
2010 年十月份，一个叫 FailOverFlow 的组织公开了 Sony 用来对 PlayStation 3 的签名算法 ECSDA 的私钥。这次攻击就是因为 sony 对签名使用了同样的$ k$ 。
参考
- 综述文章 http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa-cert.pdf
- 维基百科 ECDSA http://en.wikipedia.org/wiki/Elliptic_Curve_DSA
- 维基百科 DSA http://en.wikipedia.org/wiki/Digital_Signature_Algorithm
Q. E. D.
