本体技术视点|ECDSA中的随机数重用会导致什么问题？

北京时间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 中，如果随机数泄露，也将导致私钥泄露。随机数在密码算法中占据了一个重要地位，我们在应用中应认真对待随机数。

如有任何问题，可通过 [email protected] 联络我们。

添加“ontology_2020”并备注【技术】可进行技术探讨或加入社群。

—-

编译者/作者：本体Ontology

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。