签名算法DSA和ECDSA

作者:, 发表于

比特币协议里使用了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\)

  1. 随机选择 \(k\) ,满足 \(0\le k\le q\)
  2. 计算 \(r= (g^k \mod p) \mod q\)
  3. 如果 \(r=0\) ,回到第一步重新选择 \(k\)
  4. 计算 \(s = k^{-1}(H(m)+xr) \mod q\)
  5. 如果 \(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\) ,因此:

\[\begin{array}{rcl}v&=&g^{H(m)w}y^{rw}\mod p \mod q\\ &=&g^{H(m)s^{-1}+xrs^{-1}} \mod p \mod q\\ &=&g^{s^{-1}(H(m)+xr)}\mod p \mod q\\&=&g^k\mod p\mod q \\&=&r\end{array}\]

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.弱点

这篇综述文章的Security Consideration章节提到了DSA和ECDSA的超过20个方方面面的弱点,不恰当的曲线、基点、素数、随机数方法的选择都会带来风险。

维基上提到的最直接的弱点是上面的 \(k\) 。从公式中可以看出,从 \(k\) 可以推断出私钥 \(x\)\(k\) 必须确保随机、保密且唯一,否则便会带来对私钥的攻击。在两次签名中使用同样的 \(k\) (即使 \(k\) 保密)、 \(k\) 可预测、甚至泄漏 \(k\) 的一些字节,都足以攻击DSA。

2010年十月份,一个叫FailOverFlow的组织公开了Sony用来对PlayStation 3的签名算法ECSDA的私钥。这次攻击就是因为sony对签名使用了同样的 \(k\)

 参考

Q.E.D.


上一篇:为什么建议比特币每笔交易都使用新地址2013年12月7日
公钥泄漏会带来可能的密码供给。建议尽量保证比特币的地址的公钥未在网络上泄漏过(亦即,该地址从未对外支付过)。一个简单的方法是,每次支付时,将支付余额转到一个新的账户,废弃旧账户。这也是比特社区推荐的做法。

下一篇:Excel文件作为数据库源时如何判断数据类型2014年3月17日
在前面的文章里,我已经提到Excel数据本身可以当做一张SQL查询的数据表,并在Excel内进行数据库运算操作。数据库查询函数可以用我之前写的Excel数据


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。