本体Ontology 船员 2021-07-15 10:56:22 发布在 区块链社区 7501 0
北京时间7月12日凌晨，跨链协议 Anyswap 遭受攻击，损失将近800万美元。据 Anyswap 官方透露（https://anyswap.medium.com/anyswap-multichain-router-v3-exploit-statement-6833f1b7e6fb），此次攻击是由于 Anyswap 多链路由 V3 曾签出了两笔具有相同 值（签名结果的一个分量）的交易，从而被推导出私钥，遭受了损失。今天，我们就来看看为什么能从两个具有相同 值的签名结果中推导出私钥。
图源网络
01 ECDSA简介
数字签名是区块链技术人员耳熟能详的一种密码算法，它包含密钥生成、签名和验证三个步骤。
密钥生成：该算法的输入是一个安全参数，比如签名长度。该算法的输出是一个公私钥对，其中私钥用来签名，公钥用来验证签名（这里我们省略了公开参数的描述）；
签名：该算法的输入是消息和私钥，输出是用该私钥对该消息的签名结果；
验签：该算法的输入是消息和公钥，输出是一个比特，用来指示该签名是否通过验证。
ECDSA 是定义在椭圆曲线上的一种数字签名算法。在这里，我们不再介绍椭圆曲线以及相关的知识，小伙伴们可以在其它地方进行查阅。我们假设定义在椭圆曲线上的群的生成元是 G ，点 G 的阶为 n 。在合适范围内随机选取一个数 x 作为私钥，那么椭圆曲线上的点 X = x * G 就是该私钥对应的公钥。
签名的过程是这样的：
在合适范围内随机选取一个数 k ，计算椭圆曲线上的点 k * G = (ptx, pty)。该点的横坐标作为签名的分量 r ，即 r = H(ptx) 。签名的另一部分 s 通过上述过程得到的 r ，随机数 k 的逆，私钥 x ，和消息 m 的哈希值 e = H(m) 生成（假定该哈希函数的值域是一个合适范围，例如 Zn ），即
在这里，我们假定 r 和 s 都不为0。
得到签名(r,s)后，签名验证的过程是这样的：
先计算 s 的逆和消息的哈希值。然后计算椭圆曲线上的点
，并判断该点是不是无限远点，它的 x 坐标是否和 r 相同。
一个签名 (r, s) 能通过验证，是因为验证公式可以进行转化：
为了提高效率，以太坊等区块链系统中采用从签名结果中恢复出公钥，并进行比对的验证算法。当然，为了能从签名结果中恢复出公钥，还需要存储额外的信息，我们在这里就不再叙述。
关于 ECDSA 的形式化描述可以在网站：http://www.secg.org/ 上找到。
图源网络
02 随机数重用
我们从上面的说明中可以清晰地看到，具有相同 r 值的签名结果，是因为签名过程中应用的随机数 k 相同。那么对于某一个私钥 x 而言，采用同一个随机数 k 对不同消息 m1 和 m2 签名得到两个签名结果 (r1, s1) 和 (r2, s2) ，为什么能从中间推出私钥呢？
根据 ECDSA 签名过程，随机数相同会导致两个签名的第一个分量相等，即 r1 = r2 。我们假定 r1 = r2 = r 。那么，有如下两个等式：
我们可以看到，上面两个等式，未知变量只有 k 和 x 。两个等式左右分别相除化简，我们可以得到：
在上面的等式中，只有一个未知量，即私钥 x ，我们可以容易求得。另外，ECDSA 具有延展性，即如果 (r, s) 是对某个消息 的数字签名结果，那么 (r, n-s) 也是对这个消息 m 的数字签名结果。因此，我们在对于一般的签名结果导出私钥时，需要进行多次尝试。在这里说句题外话，在比特币等网络中，对 s 的范围进行了限定，以避免 ECDSA 的延展性问题。
另外，如果两个用户使用了同样的随机数，那么我们可以看到，其实对于某一个用户来说，也可以得到另一个用户的私钥，因为在上述等式中也只有另外一个用户的私钥这一未知变量。但对于其它用户来说，则无法推导出这两个用户任意一个的私钥。
03 结语
在 ECDSA 中，随机数是一个十分重要的量。对于同一个用户，同一个随机数在不同签名中使用，会使得用户私钥暴露。此次 Anyswap 被攻击事件便是由此而来。
著名的2010年 Sony PS3 事件也是由于随机数重用的问题。除此之外，在 ECDSA 中，如果随机数泄露，也将导致私钥泄露。随机数在密码算法中占据了一个重要地位，我们在应用中应认真对待随机数。
