签名算法 DSA 和 ECDSA

作者: , 共 2761 字

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

类似文章:
IT » 比特币, 数字货币
最近看到一篇文章 Satoshi』s Genius: Unexpected Ways in which Bitcoin Dodged Some Cryptographic Bullets ,国内有人翻译过( 中本聪的天才:比特币以意想不到的方式躲开了一些密码学子弹 )。里面说的第一个就是天才的中本聪并不是将公钥而是将公钥两次 HASH 之后作为比特币账户的地址,这可以让比特币系统抵抗量子计算机的攻击。
IT » 比特币
最近 bitcoin 很火,我也是最先从 云风 那里了解到的,后来发现 李笑来 & 霍炬 对其都有涉及。不过他们对其具体技术原理的描述还是不够细致,所以我自己把 bitcoin wiki 又重新看了一遍。 看完之后,疑惑挺多,我对这个体系远没有前面三位这么乐观。诚然,它会成为 "Geeks " 手中的玩物甚至灰色交易的工具,但要说的达到「一出天下反」的程度,那还需要解决一些技术和金融方面的问题。
从 hash 函数到王小云的 MD5 破解 我们介绍了 hash 函数的一些基本概念和 MD5 碰撞的一个「应用」,最近在这个问题上又有了新的进展。
密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在 hash 函数破解上做出重大贡献的王小云教授的工作,不过前两天新闻报道《王小云获得求是杰出科学家奖以及 100 万奖金》,在媒体上又掀起了一轮宣传狂潮,但是有些报道极端弱智,错误百出,所以我趁机纠正一下,并介绍密码学的一个组成部分 ——hash 函数,以及王小云老师在这上面的工作。
风险管理 » VaR Primer
一个场景是所有风险因子的表现序列。历史场景是指风险因子在历史上某天的实际表现,随机场景则是计算机随机模拟生成的。通常蒙特卡洛模拟法需生成至少 1000 个随机场景,然后计算组合在每个场景下的损益,最后取 5% 分位点得到组合的 VaR 值。
编程 » Excel, 数据库
在前面的文章里,我已经提到 Excel 数据本身可以当做一张 SQL 查询的数据表 ,并在 Excel 内进行数据库运算操作。数据库查询函数可以用我之前写的 Excel 数据库操作函数类 。我们可以用以下方式