1.3 数字签名-数据结构-机器学习

(function() {var s = "_" + Math.random().toString(36).slice(2); document.write(''); (window.slotbydup = window.slotbydup || [])。推({id: "u3646201",容器: s});})();

(function() {var s = "_" + Math.random().toString(36).slice(2); document.write(''); (window.slotbydup = window.slotbydup || [])。推({id: "u3646162",容器: s});})();

1.3 1196人参与数字签名 2018-09-12 15:09 分类：区块链精品文章

在本节中，我们将讨论数字签名。 数字签名是密码学的第二个重要部分。 该理论与哈希函数一起为我们后面讨论加密货币奠定了基础。 数字签名被认为是纸上手写签名的数字模拟。 我们对数字签名有两个属性要求，符合我们对手写签名的期望。 第一，只有你自己可以签名，但任何人看到它都可以验证它的有效性； 其次，我们希望签名只与特定文件相关联，因此签名不能用于表示您同意或支持不同的文件。 对于手写签名，第二条规则就像确保别人不能将您的签名从一份文件中剪切下来并粘贴到另一份文件的末尾。

那么我们如何通过密码学来构造这些属性呢？ 首先，让我们将前面关于直觉的讨论更具体一些，以便我们可以在未来更好地演示数字签名方案并讨论它们的安全属性。

数字签名方案

数字签名方案由以下三种算法组成：

● (sk, pk) :=generateKeys(keysize) generateKeys方法以keysize为输入，生成一对公钥和私钥。 私钥 sk 安全保存并用于签署消息； 公钥pk大家都可以查到，可以用来验证你的签名。

● sig:=sign(sk, message) 签名过程以一条消息和私钥作为输入，消息的输出是一个签名。

● isValid:=verify(pk, message, sig) 验证过程以一条消息、签名消息和公钥为输入，如果返回结果为真，则证明签名为真； 如果返回结果为false，则证明签名消息是假的。

我们要求以下两个属性有效：

● 可以验证一个有效的签名，即：

验证（pk，消息，签名（sk，消息））==true

● 签名不可伪造。

我们注意到 generateKeys 和 sign 都可以使用随机算法。 实际上，generateKeys 最好是随机的，因为它需要为不同的人生成不同的密钥，而 verify 需要是确定性的。

现在，让我们更详细地研究我们需要的数字签名方案的两个属性。 第一个属性很简单，那就是必须验证有效签名。 如果我用我的密钥 sk 签署一条消息，后来有人试图使用我的公钥 pk 来验证同一消息上的签名，那么签名必须被证明是正确的。 此属性是签名有效的最基本要求。

不可伪造性。 第二个要求在计算上不可能伪造签名。 也就是说，知道你的公钥并且已经看到你在某些信息上的签名的对手不能在他还没有看到的其他信息上伪造你的签名。 这种不可伪造的属性类似于我们和我们的对手之间玩游戏，并且游戏的使用在密码安全证明中很常见。

在不可伪造性博弈中，对手会声称他可以伪造签名，而挑战者会测试他所说的话（见图 1.9）。 我们首先要做的是使用generateKeys方法生成一个密钥，以及对应的公开验证公钥，我们把密钥给挑战者，然后把公钥给挑战者和对手。 因此，对手只知道公开信息，他的任务是试图伪造一条信息。 挑战者知道密钥，因此他可以签名。

图 1.9 不可伪造性博弈

注意：不可伪造性游戏是对手（黑客）和挑战者一起玩的游戏：如果黑客可以签署一条以前没有见过的消息，那么黑客就赢了； 否则，如果黑客做不到，则挑战者获胜，从而证明数字签名方案不可伪造。

从直观上看，这个游戏的设定与现实世界的情况是一致的，现实中的攻击者很可能能够从潜在受害者的许多不同文件中看到有效签名，甚至攻击者可能会操纵受害者签署一份文件，看起来对黑客无害但有益的文件。

为了将其模拟到我们的游戏中，我们将允许黑客为某些文件选择签名，只要有合理数量的猜测即可。 合理猜测的数量意味着我们允许攻击者尝试最多一百万次猜测，但不超过 280 次。渐近地，我们允许攻击者尝试与密钥大小的多项式函数一样多的次数，但不能更多（例如攻击者无法以指数方式猜测）。

一旦攻击者对他看到的签名数量感到满意，他就可以选择一条消息 M 并尝试在其上伪造签名。 对 M 的唯一限制是它必须是攻击者之前没有看到签名的消息（因为很明显攻击者可以发送他已经收到的签名）。 挑战者运行验证算法，通过验证公钥验证后，判断攻击者生成的关于M的信息签名是否真实。 如果验证成功，则攻击者赢得游戏。

无论对手使用何种算法，当且仅当他成功伪造消息的机会非常小时，我们说签名方案是不可伪造的——小到我们可以假设它在实践中永远不会发生。

实际考虑

为了在现实中将算法概念转化为可执行的数字签名机制，我们还需要考虑很多实际问题。 比如很多签名算法都是随机的（尤其是比特币使用的算法），所以我们需要一个好的随机源。 我们不能低估这一点的重要性，因为糟糕的随机性会使您认为安全的算法变得不安全。

另一个实际问题是关于消息大小。 实际上比特币使用的数字签名方案叫什么，您可以签名的消息的大小是有限制的，因为真正的方案将在有限位长度的字符串上运行。 有一种简单的方法可以解决此限制：对消息的哈希进行签名而不是对消息本身进行签名。 如果我们使用输出值为 256 位的密码哈希函数，那么我们可以有效地对任何长度的消息进行签名，只要我们的签名方案可以对 256 位的消息进行签名。 上面提到，我们可以使用信息的哈希值作为信息摘要比特币使用的数字签名方案叫什么，而哈希函数具有抗碰撞性，所以这种方式是安全的。

我们稍后将使用的另一个技巧是可以对散列指针进行签名。 如果你签署一个哈希指针，该签名覆盖（或保护）整个结构——不仅仅是哈希指针本身，而是哈希指针指向的整个区块链。 例如，如果您在区块链末尾对哈希指针进行签名，则结果是您有效地对整个区块链进行了数字签名。

椭圆曲线数字签名算法

现在让我们来看看具体情况。 比特币使用的数字签名方案称为椭圆曲线数字签名算法（ECDSA）。 ECDSA是美国政府的标准，是早期使用椭圆曲线的DSA[1]算法的升级版。 这些算法经过多年仔细的密码分析，通常被认为是安全的。

更具体地说，比特币使用的是 ECDSA 算法，而不是标准的椭圆曲线“secp256k1”[有望提供 128 位安全性，即破解该算法与执行 2128 次对称密钥操作（例如破解哈希函数）一样困难]。 虽然这条曲线是一个开放标准，但它很少在比特币之外使用，其他使用 ECDSA 的应用程序（例如用于安全网页浏览的 TLS[2] 密钥交换）通常使用更常见的“secp256k1”曲线。 这是比特币的一个怪癖，因为它是比特币系统早期实施时中本聪选择的（见原序），现在很难改变。

我们不会详细讨论 ECDSA 的原理，因为这涉及到一些过于复杂的数学，对本书的其余部分没有太大帮助。 如果您对 ECDSA 感兴趣，请参阅本章末尾的进一步阅读部分。 话虽如此，了解各种参数可能会有用：

个人密钥：256位

公钥（未压缩）：512 位

公钥（压缩）：257 位

待签名信息：256位

签名：512 位

请注意，严格来说，虽然 ECDSA 只能对 256 位的消息进行签名，但这是有问题的，因为消息总是在签名之前进行哈希处理，因此任何大小的消息都可以被有效地签名。

使用 ECDSA 时，确保良好的随机性来源至关重要，因为不良来源可能会导致关键信息泄露。 很容易理解，如果您使用不良随机性生成密钥，那么该密钥可能不安全。 但是ECDSA的诡异之处在于，即使你只是在生成签名时使用了糟糕的随机性，并且你使用的密钥是完美的，你的个人密钥仍然可能会被泄露（熟悉DSA的人都知道这是DSA的诡异之处，但不是对于椭圆曲线）。 然后游戏就结束了，如果您的个人密钥被泄露，对手就可以伪造您的签名。 因此，我们在实践中特别注意使用好的随机源，使用不好的随机源是安全系统的常见陷阱。

我们对作为密码学基础的数字签名的讨论到此结束。 在下一节中，我们将讨论一些有助于构建加密货币的数字签名应用程序。

加密货币和加密

如果你一直期待比特币使用的加密算法，我们可能让你失望了，比特币不使用任何加密，因为不需要加密。 加密只是现代密码学使之成为可能的众多技术之一，其中许多技术（如承诺方案）以某种方式隐藏信息，但与密码学不同。

[1] DSA（Digital Signature Algorithm），电子签名算法。 ——译者注

[2] TLS（Transport Layer Security），传输层安全协议，用于在两个通信应用程序之间提供机密性和数据完整性。 ——译者注