签名算法 DSA 和 ECDSA

作者: , 共 2528 字

比特币协议里使用了 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 函数,以及王小云老师在这上面的工作。
机器统治世界提到,随着科技的发展,我们可以直接用机器来替代政府。所谓机器统治世界,并不意味着机器是世界的主人。机器还是听命于人类,只不过以一种无法被干预的民主投票的方式。所以,机器统计世界的第一要解决的问题就是投票协议。
英文是 communication complexity ,不知道该翻译成通信复杂性,还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域,在过去 30 年衍生了很多东西。它是我的研究的主要内容,这里简略介绍一下。
机器统治世界,其中一个重要的部分便是安全计算。而这一领域的开创性工作便是姚期智先生的「姚氏百万富翁问题」。相关的工作发表于 1982 年 FOCS 上的的《Protocols for secure computations》
IT » 比特币
上篇大致描述了 bitcoin 的技术原理,只想说明一件事情: bitcoin 的协议是可靠的,它保证了 bitcoin 虚拟货币的信用问题,别人不会偷走我的 bitcoin ,我拿到的 bitcoin 也是真实可靠的。使用 bitcoin 交易有很多好处,可以轻易列出一大堆:
风险管理 » VaR Primer
一个场景是所有风险因子的表现序列。历史场景是指风险因子在历史上某天的实际表现,随机场景则是计算机随机模拟生成的。通常蒙特卡洛模拟法需生成至少 1000 个随机场景,然后计算组合在每个场景下的损益,最后取 5%分位点得到组合的 VaR 值。
编程 » Excel, 数据库
在前面的文章里,我已经提到Excel 数据本身可以当做一张 SQL 查询的数据表,并在 Excel 内进行数据库运算操作。数据库查询函数可以用我之前写的Excel 数据库操作函数类。我们可以用以下方式