真实世界的密码学（二）（1）https://developer.aliyun.com/article/1508665
7.2 零知识证明（ZKP）：签名的起源
理解密码学中签名工作原理的最佳方法是了解它们的来源。因此，让我们花点时间简要介绍 ZKP，然后我会回到签名。
想象一下，佩姬想向维克多证明某事。例如，她想证明自己知道某个群元素的离散对数。换句话说，她想证明自己知道x，给定Y = g^x，其中g是某个群的生成元。
当然，最简单的解决方案是佩姬简单地发送值x（称为见证）。这个解决方案将是一个简单的知识证明，这样就可以了，除非佩姬不希望维克多知道它。
注意 在理论上，我们说用于生成证明的协议如果完备，那么佩姬可以使用它向维克多证明她知道见证。如果她无法使用它证明自己所知，那么这个方案就是无用的，对吧？
在密码学中，我们主要关注不向验证者泄露见证的知识证明。这样的证明被称为零知识证明（ZKP）。
7.2.1 Schnorr 身份验证协议：一个交互式零知识证明
在接下来的页面中，我将逐步从破损的协议构建一个 ZKP，以向您展示爱丽丝如何证明她知道x而不泄露x。
在密码学中解决这种问题的典型方法是用一些随机性“隐藏”这个值（例如，通过加密）。但我们不仅仅是隐藏：我们还想证明它是存在的。为此，我们需要一种代数方法来隐藏它。一个简单的解决方案是简单地将一个随机生成的值 k 添加到证人中。
s = k + x
佩姬随后可以将隐藏的证人 s 与随机值 k 一起发送给维克多。此时，维克多没有理由相信佩姬确实将证人隐藏在 s 中。实际上，如果她不知道证人 x，那么 s 可能只是一些随机值。维克多知道的是，证人 x 正隐藏在 g 的指数中，因为他知道 Y = g^x。
为了确定佩姬是否真的知道这个证人，维克多可以检查她给他的东西是否与他所知的相匹配，这也必须在 g 的指数中进行（因为这是证人所在的地方）。换句话说，维克多检查这两个数字是否相等：
- g^s (= g^(k+x))
- Y × g^k (= g^x × g^k = g^(x+k))
思路是只有知道证人 x 的人才能构造出满足这个方程的“蒙眼”证人 s。因此，这是一种知识证明。我在图 7.4 中重述了这个零知识证明系统。
图 7.4 为了向维克多证明她知道证人 x，佩姬隐藏它（通过将其添加到随机值 k）并发送隐藏的证人 s。
不要那么快。这个方案有一个问题——显然不安全！实际上，由于隐藏证人 x 的方程只有一个未知数（x 本身），维克多可以简单地反转方程以检索证人：
x = s – k
为了解决这个问题，佩姬可以隐藏随机值 k 本身！这次，她必须将随机值隐藏在指数中（而不是将其加到另一个随机值中），以确保维克多的等式仍然成立：
R = g^k
这样，维克多就不会得知值 k（这是第五章介绍的离散对数问题），因此无法恢复证人 x。然而，他仍然拥有足够的信息来验证佩姬是否知道 x！维克多只需检查 g^s (= g^(k+x) = g^k × g^x) 是否等于 Y × R (= g^x × g^k)。我在图 7.5 中审查了这个第二次尝试的零知识证明协议。
图 7.5 为了使知识证明零知识，证明者可以用随机值 k 隐藏证人 x，然后隐藏随机值本身。
我们方案还有一个问题——佩姬可以欺骗。她可以让维克多相信她知道 x，而实际上并不知道 x！她所要做的就是反转她计算证明的步骤。她首先生成一个随机值 s，然后基于 s 计算值 R：
R = g^s × Y^(–1)
维克托然后计算Y × R = Y × g^s × Y(–1)，这确实与*g*s 匹配。（佩吉使用逆来计算值的技巧在密码学中的许多攻击中都有所应用。）
注意 在理论上，我们说方案“可靠”，如果佩吉无法作弊（如果她不知道x，那么她无法愚弄维克托）。
为了使 ZKP 协议可靠，维克托必须确保佩吉从R计算出s而不是反向计算。为此，维克托使协议交互式：
- 佩吉必须对她的随机值k进行承诺，以便以后无法更改。
- 在收到佩吉的承诺后，维克托在协议中引入了一些自己的随机性。他生成一个随机值c（称为挑战）并将其发送给佩吉。
- 佩吉随后可以根据随机值k和挑战c计算她的隐藏承诺。
注意 在第二章中，您学习了承诺方案，我们使用哈希函数对我们可以稍后揭示的值进行承诺。但基于哈希函数的承诺方案不允许我们对隐藏值进行有趣的算术运算。相反，我们可以简单地将我们的生成器提升到该值，g^k，这是我们已经在做的事情。
因为佩吉无法在没有维克托的挑战c的情况下执行最后一步，而维克托又不会在看到随机值k的承诺之前发送挑战给她，所以佩吉被迫根据k计算s。获得的协议，我在图 7.6 中说明，通常被称为Schnorr 身份验证协议。
图 7.6 Schnorr 身份验证协议是一个完备的（佩吉可以证明她知道某个见证人）、可靠的（如果佩吉不知道见证人，她无法证明任何事情）和零知识的（维克托对见证人一无所知）交互式 ZKP。
所谓的交互式 ZKP 系统遵循三个步骤（承诺、挑战和证明）的模式，在文献中通常被称为Sigma 协议，有时写作Σ协议（因为希腊字母的形状具有说明性）。但这与数字签名有什么关系呢？
注意 Schnorr 身份验证协议在诚实验证者零知识（HVZK）模型中运作：如果验证者（维克托）表现不诚实并且不随机选择挑战，他们可以了解见证人的一些信息。一些更强大的 ZKP 方案在验证者恶意时仍然是零知识的。
7.2.2 签名作为非交互式零知识证明
以前的交互式 ZKP 的问题在于，嗯，它是交互式的，而现实世界的协议通常不喜欢交互性。交互式协议会增加一些不可忽略的开销，因为它们需要多个消息（可能通过网络）并且会增加无限延迟，除非两个参与者同时在线。由于这个原因，交互式 ZKP 在应用密码学领域中大多缺席。
所有这些讨论都不是毫无意义的！在 1986 年，Amos Fiat 和 Adi Shamir 发表了一种技术，允许将一个交互式的零知识证明（ZKP）轻松转换为一个非交互式的 ZKP。他们引入的技巧（称为费曼-沙米尔启发式或费曼-沙米尔变换）是让证明者自己计算挑战，以一种他们无法控制的方式。
这是一个诀窍——将挑战计算为到目前为止协议中发送和接收的所有消息的哈希（我们称之为转录）。如果我们假设哈希函数产生的输出与真正的随机数不可区分（换句话说，看起来是随机的），那么它可以成功模拟验证者的角色。
Schnorr 更进一步。他注意到任何东西都可以包含在那个哈希中！例如，如果我们在其中包含一条消息会怎样？我们得到的不仅是一个证明我们知道某个见证者x的证据，而且还是与证据密切相关的密码学链接的消息承诺。换句话说，如果证据是正确的，那么只有知道见证者的人（它变成签名密钥）才能承诺那条消息。
这就是一个签名！数字签名只是非交互式 ZKP。将 Fiat-Shamir 转换应用到 Schnorr 识别协议，我们得到了Schnorr 签名方案，我在图 7.7 中进行了说明。
图 7.7 左边的协议是之前讨论过的 Schnorr 识别协议，这是一个交互式协议。右边的协议是 Schnorr 签名，是左边协议的非交互式版本（其中验证者消息被替换为对转录进行哈希的调用）。
总结一下，Schnorr 签名基本上是两个值，R和s，其中R是对某个秘密随机值的承诺（通常称为nonce，因为它每个签名需要是唯一的），而s是通过承诺R、私钥（见证者x）和一条消息的帮助计算得出的值。接下来，让我们看一下签名算法的现代标准。
7.3 你应该使用（或不使用）的签名算法
像密码学中的其他领域一样，数字签名有许多标准，有时很难理解应该使用哪一个。这就是我在这里的原因！幸运的是，签名算法的类型与密钥交换的类型类似：有基于大数算术模的算法，如 Diffie-Hellman（DH）和 RSA，也有基于椭圆曲线的算法，如椭圆曲线 Diffie-Hellman（ECDH）。
请确保你对第五章和第六章的算法了解足够深入，因为我们现在要基于这些内容进行讨论。有趣的是，引入 DH 密钥交换的论文也提出了数字签名的概念（没有给出解决方案）：
为了开发一种能够用一些纯电子形式的通信替代当前书面合同的系统，我们必须发现一个具有与书面签名相同属性的数字现象。 任何人都必须能够轻松识别签名的真实性，但除了合法签署者之外，任何其他人都不可能产生签名。 我们将称这样的技术为单向认证。 由于任何数字信号都可以精确复制，真正的数字签名必须在不被知道的情况下识别。
——Diffie 和 Hellman（《密码学的新方向》，1976 年）
一年后（1977 年），第一个签名算法（称为 RSA）与 RSA 非对称加密算法一起被引入（您在第六章中学到了）。 RSA 用于签名是我们将学习的第一个算法。
1991 年，NIST 提出了数字签名算法（DSA），试图避开 Schnorr 签名的专利。 出于这个原因，DSA 是 Schnorr 签名的一种奇怪的变体，发布时没有安全性证明（尽管目前尚未发现任何攻击）。 该算法被许多人采用，但很快被一个称为ECDSA（代表椭圆曲线数字签名算法）的椭圆曲线版本取代，就像椭圆曲线 Diffie-Hellman（ECDH）取代 Diffie-Hellman（DH）一样，由于其更小的密钥（请参见第五章）。 ECDSA 是我将在本节中讨论的第二种签名算法。
在 2008 年，Schnorr 签名的专利过期后，Daniel J. Bernstein，也就是 ChaCha20-Poly1305（在第四章中介绍）和 X25519（在第五章中介绍）的发明者，推出了一种新的签名方案，称为EdDSA（代表 Edwards 曲线数字签名算法），基于 Schnorr 签名。 自推出以来，EdDSA 迅速获得了采用，并且现在被认为是实际应用中数字签名的最新技术。 EdDSA 是我将在本节中讨论的第三种也是最后一种签名算法。
7.3.1 RSA PKCS#1 v1.5：一个糟糕的标准
RSA 签名目前被广泛应用，尽管它们不应该被使用（正如您将在本节中看到的，它们存在许多问题）。 这是因为该算法是第一个被标准化的签名方案，并且实际应用领域迟迟未能转向更新更好的算法。 因此，在您的学习过程中很可能会遇到 RSA 签名，我无法避免解释它们的工作原理和采用的标准。 但让我说，如果您理解了第六章中 RSA 加密的工作原理，那么本节应该很简单，因为使用 RSA 进行签名与使用 RSA 进行加密相反：
- 要进行签名，您需要使用私钥（而不是公钥）对消息进行加密，这将生成一个签名（组中的随机元素）。
- 要验证签名，您需要使用公钥（而不是私钥）对签名进行解密。 如果它将原始消息还原出来，则签名有效。
注意 实际上，在签名之前，消息通常会被散列，因为这样会占用更少的空间（RSA 只能签署比其模数小的消息）。结果也被解释为一个大数，以便可以在数学运算中使用。
如果你的私钥是私钥指数d，公钥是公钥指数e和公共模数N，你可以
- 通过计算signature = message^d mod N来签署消息
- 通过计算signature^e mod N来验证签名，并检查它是否等于消息
我在图 7.8 中以图示方式说明了这一点。
图 7.8 要使用 RSA 签名，我们只需对 RSA 加密算法进行逆操作：我们使用私钥指数对消息进行指数运算，然后进行验证，我们使用公钥指数对签名进行指数运算，返回到消息。
这样做的原因是只有了解私钥指数d的人才能对消息产生签名。与 RSA 加密一样，安全性与因子分解问题的难度紧密相连。
那么用 RSA 进行签名的标准是什么？幸运的是，它们遵循与 RSA 加密相同的模式：
- *RSA 用于加密在 PKCS#1 v1.5 文档中松散标准化。*同一文档还包含了 RSA 签名的规范（没有安全证明）。
- *然后在 PKCS#1 v2 文档中对 RSA 进行了重新标准化，采用了更好的构造方法（称为 RSA-OAEP）。*同一文档中也对 RSA 签名进行了标准化，RSA-PSS 方案也在其中标准化（附带安全证明）。
我在第六章关于非对称加密中讨论了 RSA PKCS#1 v1.5。在该文档中标准化的签名方案与加密方案几乎相同。要签名，首先使用所选的哈希函数对消息进行哈希，然后根据 PKCS#1 v1.5 的签名填充进行填充（这与相同标准中的加密填充类似）。接下来，使用私钥指数对填充和散列消息进行加密。我在图 7.9 中说明了这一点。
图 7.9 RSA PKCS#1 v1.5 用于签名。要签名，先使用 PKCS#1 v1.5 填充方案对消息进行哈希和填充。最后一步使用私钥指数d对填充的哈希消息进行指数运算取模N。要验证，只需使用公钥指数e对签名进行指数运算取模N，并验证它是否与填充的哈希消息匹配。
多个 RSAs
顺便说一句，不要被 RSA 周围的不同术语搞混了。有 RSA（非对称加密原语）和 RSA（签名原语）。此外，还有 RSA（公司），由 RSA 的发明者创立。提到用 RSA 加密时，大多数人指的是 RSA PKCS#1 v1.5 和 RSA-OAEP 方案。提到用 RSA 签名时，大多数人指的是 RSA PKCS#1 v1.5 和 RSA-PSS 方案。
我知道这可能会让人感到困惑，特别是对于 PKCS#1 v1.5 标准。 尽管在 PKCS#1 v1.5 中有官方名称来区分加密和签名算法（RSAES-PKCS1-v1_5 用于加密，RSASSA-PKCS1-v1_5 用于签名），但我很少看到这些名称被使用。
在第六章中，我提到了对 RSA PKCS#1 v1.5 进行加密的破坏性攻击；不幸的是，对于 RSA PKCS#1 v1.5 签名也是如此。 1998 年，Bleichenbacher 发现了对 RSA PKCS#1 v1.5 加密的毁灭性攻击后，他决定看看签名标准。 Bleichenbacher 在 2006 年提出了对 RSA PKCS#1 v1.5 的签名伪造攻击，这是对签名的最灾难性的攻击类型之一——攻击者可以在不知道私钥的情况下伪造签名！ 与直接破解加密算法的第一次攻击不同，第二次攻击是一种实现攻击。 这意味着如果签名方案按照规范正确实现，攻击就不会奏效。
实现缺陷听起来不像算法缺陷那么糟糕，也就是说，如果很容易避免并且不影响许多实现。 不幸的是，2019 年已经表明，尴尬的是，许多开源实现的 RSA PKCS#1 v1.5 签名实际上陷入了这个陷阱，并且错误地实现了标准（参见 Chau 等人的“使用符号执行分析语义正确性的案例研究：PKCS#1 v1.5 签名验证”）。 各种实现缺陷最终导致了不同变体的 Bleichenbacher 的伪造攻击。
不幸的是，RSA PKCS#1 v1.5 签名仍然被广泛使用。 如果您真的必须出于向后兼容性原因使用此算法，请注意这些问题。 话虽如此，这并不意味着 RSA 签名是不安全的。 故事并没有在这里结束。
7.3.2 RSA-PSS：更好的标准
RSA-PSS 在更新的 PKCS#1 v2.1 中标准化，并包括了安全性证明（与之前的 PKCS#1 v1.5 中标准化的签名方案不同）。 新规范的工作方式如下：
- 使用 PSS 编码算法对消息进行编码
- 使用 RSA 对编码消息进行签名（就像在 PKCS#1 v1.5 标准中所做的那样）
PSS 编码稍微复杂，类似于 OAEP（Optimal Asymmetric Encryption Padding）。 我在图 7.10 中进行了说明。
图 7.10 RSA-PSS 签名方案使用掩码生成函数（MGF）对消息进行编码，就像你在第六章中学到的 RSA-OAEP 算法一样，然后以通常的 RSA 方式进行签名。
验证由 RSA-PSS 产生的签名只是在将签名提升到公共模数的公共指数模下，反转编码的问题。
PSS 的可证明安全性
PSS（概率签名方案）是可证明安全的，意味着没有人应该能够在不知道私钥的情况下伪造签名。 PSS 并非证明了如果 RSA 安全则 RSA-PSS 安全，而是证明了逆否命题：如果有人能够破解 RSA-PSS，那么该人也能够破解 RSA。这是密码学中证明事物的一种常见方式。当然，这仅在 RSA 安全时才有效，这是我们在证明中假设的。
如果你还记得，我在第六章也谈到了 RSA 加密的第三种算法（称为 RSA-KEM）——这是一种没有任何人使用但被证明安全的更简单的算法。有趣的是，RSA 签名也反映了 RSA 加密历史的这一部分，并且有一个几乎没有人使用的更简单的算法；它被称为完全域哈希（FDH）。 FDH 通过简单地对消息进行哈希，然后使用 RSA 签名（通过将摘要解释为数字）来工作。
尽管 RSA-PSS 和 FDH 都具有安全性证明并且更容易正确实现，但今天大多数协议仍然使用 RSA PKCS#1 v1.5 进行签名。这只是加密算法淘汰通常发生的缓慢的又一个例子。由于旧的实现仍然必须与新的实现一起工作，因此删除或替换算法变得困难。考虑一下不更新应用程序的用户、不提供软件新版本的供应商、无法更新的硬件设备等等。接下来，让我们看看一个更现代的算法。
7.3.3 椭圆曲线数字签名算法（ECDSA）
在本节中，让我们看看 ECDSA，这是 DSA 的椭圆曲线变体，它本身只是为了规避 Schnorr 签名的专利而发明的。该签名方案在许多标准中指定，包括 ISO 14888-3、ANSI X9.62、NIST 的 FIPS 186-2、IEEE P1363 等等。并非所有标准都兼容，希望进行互操作的应用程序必须确保它们使用相同的标准。
不幸的是，与 DSA 一样，ECDSA 没有安全性证明，而 Schnorr 签名却有。尽管如此，ECDSA 已被广泛采用，并且是最常用的签名方案之一。在本节中，我将解释 ECDSA 的工作原理以及如何使用它。与所有这些方案一样，公钥几乎总是根据相同的公式生成：
- 私钥是一个随机生成的大数x。
- 公钥是通过将x视为椭圆曲线密码学中的一个生成器（称为基点）中的索引而获得的。
更具体地说，在 ECDSA 中，公钥是使用[x]G计算的，其中x与基点G的标量乘积。
加法还是乘法符号？
请注意，我使用加法符号（在标量周围放置括号的椭圆曲线语法），但如果我想使用乘法符号，我可以写public_key = G^x。这些差异在实践中并不重要。大多数时候，不关心群的基础性质的加密协议使用乘法符号编写，而专门在椭圆曲线群中定义的协议倾向于使用加法符号编写。
要计算 ECDSA 签名，你需要与 Schnorr 签名所需的相同输入：签署消息的哈希值(H(m))，你的私钥x，以及每个签名唯一的随机数k。ECDSA 签名是两个整数，r和s，计算如下：
- r是[k] G的 x 坐标
- s等于k^(–1) (H(m) + xr) mod p
要验证 ECDSA 签名，验证者需要使用相同的哈希消息H(m)，签名者的公钥，以及签名数值r和s。验证者然后
- 计算[H(m) s^(–1)]G + [rs^(–1)]public_key
- 验证所得点的 x 坐标是否与签名值r相同
你肯定能够认识到与 Schnorr 签名有一些相似之处。随机数k有时被称为nonce，因为它是一个只能使用一次的数字，有时也被称为ephemeral key，因为它必须保持秘密。
警告我再次强调：k绝对不能重复或可预测！没有这一点，恢复私钥就变得微不足道。
一般来说，加密库在幕后执行此 nonce（k值）的生成，但有时不会让调用者提供它。这当然是一场灾难。例如，在 2010 年，索尼的 Playstation 3 被发现使用重复 nonce 的 ECDSA（泄漏了他们的私钥）。
警告更加微妙的是，如果 nonce k不是均匀和随机选择的（特别是，如果你可以预测前几位），仍然存在可以在瞬间恢复私钥的强大攻击（所谓的格攻击）。在理论上，我们称这种密钥检索攻击为全面破解（因为它们破坏了一切！）。这种全面破解在实践中非常罕见，这使得 ECDSA 算法可能以惊人的方式失败。
存在避免 nonce 问题的尝试。例如，RFC 6979 指定了一个基于消息和私钥生成 nonce 的确定性 ECDSA方案。这意味着两次签署相同消息涉及两次相同的 nonce，因此产生两次相同的签名（这显然不是问题）。
倾向于与 ECDSA 一起使用的椭圆曲线基本上与椭圆曲线 Diffie-Hellman（ECDH）算法（参见第五章）中流行的曲线相同，但有一个显着的例外：Secp256k1。Secp256k1 曲线在 SEC 2 中定义：“推荐的椭圆曲线域参数” (secg.org/sec2-v2.pdf)，由高效密码学标准组（SECG）编写。在比特币决定使用它而不是更流行的 NIST 曲线之后，它受到了很多关注，原因是我在第五章中提到的对 NIST 曲线的不信任。
Secp256k1 是一种称为 Koblitz 曲线 的椭圆曲线类型。Koblitz 曲线只是具有一些参数约束的椭圆曲线，这些约束允许在曲线上优化一些操作。椭圆曲线具有以下方程式：
y² = x³ + ax + b
其中 a = 0 和 b = 7 是常数，x 和 y 定义在模素数 p 上：
p = 2¹⁹² – 2³² – 2¹² – 2⁸ – 2⁷ – 2⁶ – 2³ – 1
这定义了一个素数阶的群，与 NIST 曲线相似。今天，我们有有效的公式来计算椭圆曲线上点的数量。这是 Secp256k1 曲线中点的数量（包括无穷远点）的素数：
115792089237316195423570985008687907852837564279074904382605163141518161494337
我们使用固定点 G 作为生成器（或基点）的坐标
x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
和
y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
尽管如此，今天 ECDSA 大多数与 NIST 曲线 P-256（有时称为 Secp256r1；注意区别）一起使用。接下来让我们看另一种广泛流行的签名方案。
7.3.4 Edwards 曲线数字签名算法（EdDSA）
让我介绍一下本章的最后一个签名算法，Edwards 曲线数字签名算法（EdDSA），由 Daniel J. Bernstein 于 2011 年发布，以回应对 NIST 和其他政府机构创建的曲线的不信任。EdDSA 这个名字似乎表明它基于 DSA 算法，就像 ECDSA 一样，但这是误导的。EdDSA 实际上基于 Schnorr 签名，这是由于 Schnorr 签名专利在 2008 年早些时候到期而可能的。
EdDSA 的一个特殊之处在于该方案不需要每次签名操作都产生新的随机数。EdDSA 确定性地生成签名。这使得该算法相当具有吸引力，并且已被许多协议和标准采用。
EdDSA 正在着手包括在 NIST 的即将更新的 FIPS 186-5 标准中（截至 2021 年初仍是草案）。当前的官方标准是 RFC 8032，它定义了两个不同安全级别的曲线，可用于 EdDSA。所定义的两个曲线都是 扭曲的 Edwards 曲线（一种启用有趣的实现优化的椭圆曲线类型）：
- Edwards25519 基于 Daniel J. Bernstein 的 Curve25519（在第五章中介绍）。由于椭圆曲线的类型所启用的优化，其曲线操作可以比 Curve25519 更快地实现。由于它是在 Curve25519 之后发明的，基于 Curve25519 的密钥交换 X25519 并未从这些速度改进中受益。与 Curve25519 一样，Edwards25519 提供了 128 位安全性。
- Edwards448 基于 Mike Hamburg 的 Ed448-Goldilocks 曲线。它提供了 224 位安全性。
在实践中，EdDSA 主要使用 Edwards25519 曲线实例化，该组合被称为 Ed25519（而带有 Edwards448 的 EdDSA 则缩写为 Ed448）。与现有方案不同，EdDSA 的密钥生成略有不同。EdDSA 不直接生成签名密钥，而是生成一个秘密密钥，然后用于派生实际的签名密钥和我们称之为随机数密钥的另一个密钥。那个随机数密钥很重要！它是用于确定性地生成所需每个签名的随机数的密钥。
注意 根据您使用的加密库，您可能正在存储秘密密钥或两个派生密钥：签名密钥和随机数密钥。不是这很重要，但如果您不知道这一点，那么如果遇到将 Ed25519 秘密密钥存储为 32 字节或 64 字节，具体取决于所使用的实现，则可能会感到困惑。
要签名，EdDSA 首先通过将随机数密钥与要签名的消息进行哈希运算来确定性地生成随机数。之后，类似于 Schnorr 签名的过程如下进行：
- 计算随机数为 HASH(nonce key || message)
- 计算承诺 R 为 [nonce]G，其中 G 是群的基点
- 计算挑战为 HASH(commitment || public key || message)
- 计算证明 S 为 nonce + challenge × signing key
签名是（R，S）。我在图 7.11 中说明了 EdDSA 的重要部分。
Figure 7.11 EdDSA 密钥生成产生一个秘密密钥，然后用于派生另外两个密钥。第一个派生密钥是实际的签名密钥，因此可用于派生公钥；另一个派生密钥是随机数密钥，在签名操作期间用于确定性地派生随机数。然后，EdDSA 签名类似于 Schnorr 签名，唯一的异常是（1）随机数是根据随机数密钥和消息确定性生成的，并且（2）签名者的公钥包含在挑战的一部分中。
注意随机数（或临时密钥）如何确定性地而不是概率性地从随机数密钥和给定的消息中派生出来。这意味着签署两个不同的消息应该涉及两个不同的随机数，巧妙地防止签署者重复使用随机数，从而泄漏密钥（就像 ECDSA 可能发生的情况一样）。两次签署相同的消息会产生两次相同的随机数，然后也会产生两次相同的签名。这显然不是问题。可以通过计算以下两个方程式来验证签名：
[S]G
R + [HASH(R || public key || message)] public key
如果这两个值匹配，则签名有效。这与 Schnorr 签名的工作方式完全相同，只是现在我们处于一个椭圆曲线组中，我在这里使用了加法表示法。
EdDSA 的最广泛使用的实例是 Ed25519，它使用 Edwards25519 曲线和 SHA-512 作为哈希函数进行定义。 Edwards25519 曲线的定义包含满足以下方程的所有点：
–x² + y² = 1 + d × x² × y² mod p
其中值 d 是大数
37095705934669439343138083508754565189542113879843219016388785533085940283555
变量 x 和 y 取模 p，即大数 2²⁵⁵ – 19（用于 Curve25519 的相同素数）。基点是坐标为 G
x = 15112221349535400772501151409588531511454012693041857206046113283949847762202
和
y = 46316835694926478169428394003475163141307993866256225615783033603165251855960
RFC 8032 实际上定义了三种使用 Edwards25519 曲线的 EdDSA 变体。所有三种变体都遵循相同的密钥生成算法，但具有不同的签名和验证算法：
- Ed25519（或 pureEd25519） —— 这就是我之前解释过的算法。
- Ed25519ctx —— 此算法引入了一个强制的定制字符串，并且在实践中很少被实现，甚至很少被使用。唯一的区别是在每次调用哈希函数时都添加了一些用户选择的前缀。
- Ed25519ph（或 HashEd25519） —— 这允许应用程序在签名之前对消息进行预哈希（因此名称中有 ph）。它还基于 Ed25519ctx，允许调用者包含一个可选的自定义字符串。
在密码学中增加一个 定制字符串 是相当常见的，就像你在第二章中看到的某些哈希函数，或者在第八章中看到的密钥派生函数一样。当协议中的参与者在不同的上下文中使用相同的密钥对消息进行签名时，这是一个有用的补充。例如，你可以想象一个应用程序，允许你使用私钥签名交易，也可以向你交谈的人签署私人消息。如果你错误地签署并发送了一个看起来像交易的消息给你的邪恶朋友 Eve，她可能会尝试将其重新发布为有效的交易，如果无法区分你签署的两种类型的有效载荷的话。
Ed25519ph 仅为了满足需要签署大型消息的调用者而引入。正如您在第二章中看到的，哈希函数通常提供“初始化-更新-完成”接口，允许您连续哈希数据流，而无需将整个输入保留在内存中。
现在您已经完成了对实际应用中使用的签名方案的介绍。接下来，让我们看看在使用这些签名算法时可能如何自掘坟墓。但首先，让我们回顾一下：
- RSA PKCS#1 v1.5 仍然被广泛使用，但正确实现很困难，许多实现已被发现存在问题。
- RSA-PSS 具有安全性证明，更易于实现，但由于基于椭圆曲线的新方案而受到较少采用。
- ECDSA 是 RSA PKCS#1 v1.5 的主要竞争对手，大多数情况下与 NIST 的曲线 P-256 一起使用，除了在加密货币世界中，Secp256k1 似乎占主导地位。
- Ed25519 基于 Schnorr 签名，已经得到广泛采用，并且与 ECDSA 相比更容易实现；它不需要每次签名操作都产生新的随机数。如果可以的话，这是您应该使用的算法。
7.4 签名方案的微妙行为
签名方案可能具有一些微妙的特性。虽然它们在大多数协议中可能并不重要，但在处理更复杂和非常规的协议时，不了解这些“陷阱”可能会给您带来麻烦。本章的最后部分重点介绍了数字签名的已知问题。
7.4.1 签名替换攻击
数字签名并不能唯一地识别密钥或消息。
——Andrew Ayer（《让我们加密中的重复签名密钥选择攻击》，2015）
替换攻击，也称为重复签名密钥选择（DSKS），对 RSA PKCS#1 v1.5 和 RSA-PSS 都是可能的。存在两种 DSKS 变体：
- 密钥替换攻击——使用不同的密钥对或公钥来验证给定消息上的给定签名。
- 消息密钥替换攻击——使用不同的密钥对或公钥来验证给定消息上的新签名。
再说一遍：第一次攻击同时修复了消息和签名；第二次攻击只修复了签名。我在图 7.12 中总结了这一点。
图 7.12 类似 RSA 的签名算法易受密钥替换攻击的影响，这对大多数密码学用户来说是意外且意想不到的行为。密钥替换 攻击允许某人获取消息的签名，并制作一个新的密钥对，以验证原始签名。一种变体称为消息密钥替换允许攻击者创建一个新的密钥对和一个新的消息，这些消息在原始签名下是有效的。
存在适应性选择消息攻击下的存在性不可伪造性 (EUF-CMA)
替换攻击是理论密码学和应用密码学之间差距的一种综合症。密码学中的签名通常使用 EUF-CMA 模型进行分析，该模型代表自适应选择消息攻击下的存在性不可伪造性。在这个模型中，您生成一对密钥，然后我请求您对一些任意消息进行签名。当我观察您产生的签名时，如果我能在某个时间点生成一个我以前没有请求过的消息的有效签名，那么我就赢了。不幸的是，这个 EUF-CMA 模型似乎并不包括每个边缘情况，而且危险的细微差别，如替换攻击，也没有被考虑在内。
7.4.2 签名可塑性
2014 年 2 月，曾经是最大比特币交易所的 MtGox 关闭并申请破产，声称攻击者利用可塑性攻击来清空其账户。
—Christian Decker 和 Roger Wattenhofer（“比特币交易可塑性和 MtGox”，2014）
大多数签名方案都是可塑的：如果您给我一个有效的签名，我可以修改签名，使其成为一个不同但仍然有效的签名。我不知道签名密钥是什么，但我设法创建了一个新的有效签名。
非可塑性并不一定意味着签名是唯一的：如果我是签名者，通常可以为相同的消息创建不同的签名，这通常是可以接受的。一些构造，如可验证随机函数（你将在第八章中看到），依赖于签名的唯一性，因此它们必须处理这个问题或使用具有唯一签名的签名方案（如 Boneh–Lynn–Shacham，或 BLS，签名）。
强 EUF-CMA
一个称为 SUF-CMA（用于强 EUF-CMA）的新安全模型试图在签名方案的安全定义中包含非可塑性（或抵抗可塑性）。一些最近的标准，如 RFC 8032，规定了 Ed25519，包括对抗可塑性攻击的缓解措施。由于这些缓解措施并不总是存在或常见，您不应该依赖于您的协议中的签名是非可塑的。
如何处理所有这些信息？请放心，签名方案绝对没有问题，如果您使用的签名不太超出常规，那么您可能不必担心。但是，如果您正在设计加密协议，或者您正在实现比日常密码学更复杂的协议，您可能希望将这些微妙的属性记在心中。
摘要
- 数字签名类似于笔和纸签名，但是由密码学支持，使得除了控制签名（私钥）的人之外，任何人都无法伪造。
- 数字签名可以用于验证来源（例如，密钥交换的一方）以及提供传递信任（如果我信任 Alice，她信任 Bob，我就可以信任 Bob）。
- 零知识证明（ZKPs）允许证明者证明对特定信息（称为见证）的知识，而不泄露任何信息。签名可以被视为非交互式 ZKPs，因为在签名操作期间不需要验证者在线。
- 您可以使用许多标准进行签名：
- RSA PKCS#1 v1.5 如今被广泛使用，但不建议，因为很难正确实现。
- RSA-PSS 是一种更好的签名方案，因为它更容易实现并且有安全性证明。不幸的是，由于支持更短密钥的椭圆曲线变体现在更受网络协议青睐，因此它如今并不流行。
- 目前最流行的签名方案基于椭圆曲线：ECDSA 和 EdDSA。ECDSA 经常与 NIST 的曲线 P-256 一起使用，而 EdDSA 经常与 Edwards25519 曲线一起使用（这种组合被称为 Ed25519）。
- 一些微妙的属性可能会很危险，如果签名被以非常规方式使用：
- 始终避免对谁签署了消息产生歧义，因为一些签名方案容易受到密钥替换攻击的影响。外部参与者可以创建一个新的密钥对，该密钥对将验证已经存在的消息上的签名，或者创建一个新的密钥对和一个新消息，该消息将验证给定的签名。
- 不要依赖签名的唯一性。首先，在大多数签名方案中，签名者可以为同一消息创建任意数量的签名。其次，大多数签名方案都是可塑性的，这意味着外部参与者可以获取一个签名并为同一消息创建另一个有效的签名。
第八章：随机性和秘密
本章涵盖了
- 随机性是什么以及为什么它很重要
- 获取强随机性并生成秘密
- 随机性的陷阱
这是本书第一部分的最后一章，在我们转到第二部分并了解实际世界中使用的协议之前，我有最后一件事要告诉你。这是我迄今为止严重忽视的一点 —— 随机性。
你一定注意到了，在你学过的每个密码算法中（哈希函数除外），你都必须在某个时候使用随机性：秘密密钥、随机数、初始化向量、素数、挑战等等。当我讲解这些不同的概念时，随机性总是来自某个神奇的黑盒子。这并不罕见。在密码学白皮书中，随机性通常被用一个带有美元符号的箭头表示。但是在某些时候，我们需要问自己一个问题，“这个随机性到底来自哪里？”
在这一章中，我将为你解释当密码学提到随机性时它意味着什么。我还将为你提供有关现实世界密码应用中获取随机性的实用方法的指引。
注意 对于这一章，你需要已经阅读了第二章关于哈希函数和第三章关于消息认证码。
8.1 什么是随机性？
每个人在某种程度上都理解随机性的概念。无论是玩骰子还是买彩票，我们都曾接触过它。我第一次遇到随机性是在很小的时候，当我意识到计算器上的一个 RAND 按钮每次按下都会产生不同的数字时。这让我感到非常困扰。我对电子学了解甚少，但我觉得我可以理解一些它的限制。当我将 4 和 5 相加时，肯定会有一些电路进行计算并给我结果。但是一个随机按钮？随机数从哪里来的？我无法理解。
我花了一些时间才问出正确的问题，并且了解到计算器其实是作弊的！它们会硬编码大量随机数列表，并逐一遍历这些列表。这些列表会展现出良好的随机性，这意味着如果你看着得到的随机数，1 的数量和 9 的数量相等，1 的数量和 2 的数量相等，依此类推。这些列表会模拟均匀分布：数字均匀分布在等比例中。
当需要用于安全和密码学目的时，随机数必须是不可预测的。当然，在那个时候，没有人会将那些计算器的“随机性”用于与安全有关的任何事情。相反，密码应用从观察难以预测的物理现象中提取随机性。
举例来说，即使投掷骰子是一个确定性过程，预测其结果也很困难；如果你知道了所有的初始条件（你如何投掷骰子、骰子本身、空气摩擦、桌面的摩擦力等），你应该能够预测结果。话虽如此，所有这些因素对最终结果的影响如此之大，以至于对初始条件的知识有轻微的不准确性就会影响我们的预测。结果对初始条件的极度敏感性被称为混沌理论，这就是为什么像天气这样的事情很难在一定数量的天数后准确预测的原因。
下面的图片是我在访问 Cloudflare 在旧金山总部期间拍摄的一张照片。LavaRand 是一堵熔岩灯墙，这些灯产生难以预测的蜡形状。一台摄像机放置在墙前，提取并将图像转换为随机字节。
应用程序通常依赖操作系统提供可用的随机性，而操作系统又根据运行的设备类型使用不同的技巧收集随机性。常见的随机性来源（也称为熵源）可以是硬件中断的时间（例如，您的鼠标移动）、软件中断、硬盘寻道时间等。
熵
在信息理论中，熵一词用于判断一个字符串包含多少随机性。该术语是由克劳德·香农创造的，他设计了一个熵公式，该公式将随着字符串表现出越来越多的不可预测性而输出越来越大的数字（从完全可预测的 0 开始）。对于我们来说，公式或数字本身并不那么有趣，但在密码学中，你经常会听到“这个字符串的熵低”（意思是可预测的）或“这个字符串的熵高”（意思是不太可预测的）。
观察中断和其他事件以产生随机性并不理想；当设备启动时，这些事件往往是高度可预测的，它们也可能受到外部因素的恶意影响。如今，越来越多的设备可以访问额外的传感器和硬件辅助设备，提供更好的熵源。这些硬件随机数发生器通常称为真随机数发生器（TRNG），因为它们利用外部不可预测的物理现象（如热噪声）来提取随机性。
通过所有这些不同类型的输入获得的噪声通常不是“干净”的，有时甚至没有足够的熵（如果有的话）。例如，从某些熵源获得的第一个比特往往是 0，或者连续的比特可能（比机会更大）相等。因此，在用于密码应用之前，随机性提取器必须清理和收集几种噪声源。例如，可以通过将不同源应用哈希函数并将摘要进行异或来完成此操作。
随机性就只有这些吗？不幸的是不是。从噪声中提取随机性是一个可能会很慢的过程。对于一些可能需要快速生成大量随机数的应用程序，这可能成为瓶颈。下一节将描述操作系统和现实世界应用程序如何提高随机数的生成。
8.2 慢随机性？使用伪随机数生成器（PRNG）
随机性随处可见。此时，您应该至少相信这对于密码学是真实的，但令人惊讶的是，密码学并不是唯一一个大量使用随机数的地方。例如，像 ls 这样的简单 Unix 程序也需要随机性！由于程序中的错误如果被利用可能会产生灾难性后果，二进制文件试图通过多种技巧来防御低级攻击；其中之一是ASLR（地址空间布局随机化），它在每次运行时随机化进程的内存布局，因此需要随机数。另一个例子是网络协议 TCP，每次创建连接时都使用随机数来产生不可预测的数字序列，并阻止试图劫持连接的攻击。虽然所有这些都超出了本书的范围，但了解现实世界中出于安全原因使用了多少随机性是很好的。
在上一节中，我暗示了，不幸的是，获得不可预测的随机性有点慢。这有时是因为熵源产生噪声的速度较慢。因此，操作系统通常通过使用伪随机数生成器（PRNGs）来优化它们的随机数生成过程。
注意为了与那些不设计为安全的随机数生成器进行对比（在不同类型的应用程序中很有用，比如视频游戏），PRNG 有时被称为CSPRNGs，代表密码学安全PRNGs。NIST 想要以不同的方式做事情（像往常一样），通常将他们的 PRNG 称为确定性随机位生成器（DRBGs）。
PRNG 需要一个初始秘密，通常称为种子，我们可以通过混合不同的熵源来获得，然后可以快速产生大量随机数。我在图 8.1 中说明了一个 PRNG。
图 8.1 伪随机数生成器（PRNG）基于种子生成随机数序列。使用相同的种子使 PRNG 产生相同的随机数序列。应该不可能使用随机输出的知识来恢复状态（函数next是一种方式）。由此得出，仅从观察产生的随机数就不可能预测未来的随机数或恢复先前生成的随机数。
加密安全的 PRNG 通常具有以下属性：
- 确定性— 使用相同的种子两次会产生相同的随机数序列。这与我之前谈到的不可预测的随机性提取不同：如果你知道 PRNG 使用的种子，那么 PRNG 应该是完全可预测的。这就是为什么这种构造被称为伪随机的原因，这也是使 PRNG 能够非常快速的原因。
- 与随机不可区分— 在实践中，你不应该能够区分 PRNG 输出的随机数与一个小精灵公正地从相同集合中选择随机数的情况（假设该精灵知道一种魔法方式来选择一个数，以使每个可能的数都可以等概率地被选择）。因此，仅观察生成的随机数不应该允许任何人恢复 PRNG 的内部状态。
最后一点非常重要！PRNG 模拟从均匀随机选择一个数字，这意味着集合中的每个数字都有相等的被选中的机会。例如，如果你的 PRNG 生成 8 字节的随机数，那么集合就是所有可能的 8 字节字符串，每个 8 字节值都应该有相等的概率成为可以从你的 PRNG 获得的下一个值。这包括已经由 PRNG 在过去某个时候生成的值。
此外，许多 PRNG 还表现出其他安全性质。如果攻击者学习到状态（例如在某个时间点进入您的计算机），则 PRNG 不会允许其检索先前生成的随机数，那么 PRNG 具有正向保密性。我在图 8.2 中进行了说明。
图 8.2 如果 PRNG 的状态泄露不会导致恢复先前生成的随机数，则 PRNG 具有正向保密性。
获取 PRNG 的状态意味着你可以确定它将生成的所有未来伪随机数。为了防止这种情况发生，一些 PRNG 具有定期“修复”自身的机制（以防出现泄密）。这种修复可以通过在 PRNG 已经被种子化后重新注入（或重新播种）新的熵来实现。这种属性被称为逆向保密性。我在图 8.3 中进行了说明。
图 8.3 如果 PRNG 的状态被泄露，而这并不会导致能够预测 PRNG 生成的未来随机数，则 PRNG 具有逆向保密性。这仅在产生新的熵并在泄密后注入更新函数时才成立。
注意 前向 和 后向保密性 这两个术语经常让人感到困惑。如果你读到这一部分时认为前向保密性应该是后向保密性，反之亦然，那么你并不疯狂。因此，后向保密性有时被称为未来保密性，甚至是事后妥协安全（PCS）。
如果适当地种子化，PRNGs 可以非常快速，并被认为是生成大量用于加密目的的随机值的安全方法。使用可预测的数字或数字过小显然不是安全的种子 PRNG 的方式。这实际上意味着我们有安全的加密方式，可以快速地将适当大小的秘密扩展到数十亿个其他秘密密钥。很酷，对吧？这就是为什么大多数（如果不是全部）加密应用程序不直接使用从噪声中提取的随机数，而是在初始步骤中使用它们来种子 PRNG，然后在需要时切换到从 PRNG 生成随机数。
双重 EC 后门
如今，伪随机数生成器（PRNGs）主要是基于启发式构建的。这是因为基于困难数学问题（如离散对数）的构建方式速度太慢，不够实用。一个臭名昭著的例子是由 NSA 发明的双重 EC，依赖于椭圆曲线。双重 EC PRNG 被推广到各种标准，包括 2006 年左右的一些 NIST 出版物，不久之后，几位研究人员独立发现了算法中的潜在后门。这在 2013 年斯诺登的披露中得到了确认，一年后，该算法被撤回了多个标准。
要保证安全，PRNG 必须用一个不可预测的秘密种子。更准确地说，我们说 PRNG 以* n 字节的密钥均匀随机采样。这意味着我们应该从所有可能的 n * -字节字符串集中随机选择密钥，每个字节字符串被选中的机会相同。
在本书中，我谈到了许多产生与随机输出不可区分的密码算法（从将被均匀选择的值）。直觉上，你应该在想我们能否使用这些算法来生成随机数呢？你是对的！哈希函数、XOFs、块密码、流密码和 MACs 可以用来生成随机数。哈希函数和 MACs 在理论上并没有被定义为提供与随机不可区分的输出，但在实践中，它们经常是如此。另一方面，像密钥交换和签名这样的非对称算法（几乎总是）不可区分于随机。因此，它们的输出在被用作随机数之前经常被哈希。
实际上，因为大多数计算机上都支持 AES，因此通常会看到使用 AES-CTR 来生成随机数。对称密钥成为种子，而密文成为随机数（例如，用于加密无限的 0 字符串）。在实践中，为了提供前向和后向保密性，对这些构造添加了一些复杂性。幸运的是，您现在已经了解足够多的内容，可以进入下一节，该节提供了实际获取随机性的概述。
8.3 在实践中获取随机性
您已经了解了操作系统向其程序提供加密安全随机数所需的三个要素：
- 噪声源 — 这些是操作系统从不可预测的物理现象（如设备温度或鼠标移动）中获取原始随机性的方法。
- 清理和混合 — 虽然原始随机性可能质量较差（一些位可能是偏倚的），但操作系统会清理并混合多个来源，以产生良好的随机数。
- PRNGs — 因为前两个步骤很慢，所以可以使用单个、均匀分布的随机值来种子一个可以快速生成随机数的 PRNG。
在本节中，我将解释系统如何将这三个概念捆绑在一起，以向开发人员提供简化的接口。操作系统提供的这些函数通常允许您通过发出系统调用生成随机数。在这些系统调用背后，确实有一个系统将噪声源、混合算法和 PRNG 捆绑在一起（在图 8.4 中总结）。
图 8.4 在系统上生成随机数通常意味着从不同的噪声源混合熵并用于种子长期 PRNG。
根据操作系统和可用硬件的不同，这三个概念可能会以不同的方式实现。在 2021 年，Linux 使用基于 ChaCha20 流密码的 PRNG，而 macOS 使用基于 SHA-1 散列函数的 PRNG。此外，向开发人员公开的随机数生成器接口将根据操作系统而异。在 Windows 上，可以使用 BCryptGenRandom 系统调用生成随机数，而在其他平台上，则公开了一个特殊文件（通常称为 /dev/urandom），可以读取以提供随机性。例如，在 Linux 或 macOS 上，可以使用 dd 命令行工具从终端读取 16 字节：
$ dd if=/dev/urandom bs=16 count=1 2> /dev/null | xxd -p 40b1654b12320e2e0105f0b1d61e77b1
/dev/urandom 的一个问题是，如果在设备启动后太早使用，可能提供的熵不足（其数字不够随机）。像 Linux 和 FreeBSD 这样的操作系统提供了一种称为 getrandom 的解决方案，它是一种系统调用，几乎提供与从 /dev/urandom 读取相同功能的功能。在很少的情况下，如果初始化其 PRNG 的熵不足，getrandom 将阻止程序的继续运行，并等待适当的种子化。因此，如果系统可用，建议您使用 getrandom。以下清单显示了如何在 C 中安全使用 getrandom：
8.1 在 C 中获取随机数示例
#include <sys/random.h> uint8_t secret[16]; // ❶ int len = getrandom(secret, sizeof(secret), 0); // ❷ if (len != sizeof(secret)) { abort(); // ❸ }
❶ 使用随机字节填充缓冲区（请注意，getrandom 每次调用最多限制为 256 字节）。
❷ 默认标志（0）是不阻塞的，除非适当种子化。
❸ 函数可能失败或返回少于所需的随机字节数。如果是这种情况，则系统已损坏，中止可能是最好的选择。
有了这个例子，还要指出许多编程语言都有标准库和密码库，提供更好的抽象。例如，很容易忘记 getrandom 每次调用最多只返回 256 个字节。因此，您应该始终尝试通过所使用的编程语言的标准库生成随机数。
警告 注意许多编程语言公开了产生可预测随机数的函数和库。这些不适用于密码学用途！确保使用生成密码强度强的随机数的随机库。通常库的名称有助于选择（例如，在 Golang 中，您可能可以猜出应该使用 math/rand 和 crypto/rand 包之间的哪一个），但是阅读手册是无可替代的！
清单 8.2 显示了如何在 PHP 7 中生成一些随机字节。任何密码算法都可以使用这些随机字节。例如，作为使用认证加密算法加密的秘密密钥。每种编程语言都有不同的做法，因此请务必查阅您的编程语言文档，以找到获取密码用途的随机数的标准方法。
8.2 在 PHP 中获取随机数示例
<?php $bad_random_number = rand(0, 10); // ❶ $secret_key = random_bytes(16); // ❷ ?>
❶ 产生 0 到 10 之间的随机整数。虽然快速，但 rand 不会产生密码学安全的随机数，因此不适用于密码算法和协议。
❷ random_bytes 创建并填充一个包含 16 个随机字节的缓冲区。结果适用于密码算法和协议。
现在您已经了解了如何在程序中获得密码学安全的随机性，让我们思考一下在生成随机性时需要牢记的安全考虑事项。
8.4 随机性生成与安全考虑
在这一点上记住是很好的，任何基于密码学的有用协议都需要良好的随机性，一个破损的 PRNG 可能导致整个密码协议或算法不安全。你应该清楚地知道，MAC 只有与其一起使用的密钥一样安全，或者即使有微小的可预测性通常也会破坏 ECDSA 等签名方案，等等。
到目前为止，本章让生成随机性听起来应该是应用密码学的一个简单部分，但实际上并非如此。由于多种问题：使用非密码学 PRNG、错误地种子化 PRNG（例如使用可预测的当前时间）等，随机性实际上是真实世界密码学中许多许多错误的根源。
一个例子包括使用用户空间 PRNG而不是内核 PRNG的程序，后者在系统调用后面。用户空间 PRNG 通常会增加不必要的摩擦，如果被误用，最坏的情况下可能会破坏整个系统。这在 2006 年某些操作系统中补丁到的 OpenSSL 库提供的 PRNG 中就是一个明显的例子，无意中影响了使用受影响 PRNG 生成的所有 SSL 和 SSH 密钥。
删除这段代码的副作用是瘫痪了 OpenSSL PRNG 的种子过程。而不是混合随机数据用于初始种子，唯一使用的随机值是当前进程 ID。在 Linux 平台上，默认的最大进程 ID 是 32,768，导致所有 PRNG 操作只使用了很少的种子值。
—H. D. Moore（“Debian OpenSSL 可预测 PRNG 玩具”，2008）
出于这个原因和其他原因，我将在本章后面提到明智的做法是避免使用用户空间 PRNG，并在可用时坚持使用操作系统提供的随机性。在大多数情况下，坚持使用编程语言的标准库或一个良好的加密库提供的内容应该足够了。
我们不能在开发人员在编写日常代码时需要记住的‘最佳实践’之后不断添加更多内容。
—Martin Boßlet（“OpenSSL PRNG 不是（真的）分叉安全的”，2013）
不幸的是，任何建议都无法真正为你准备好获取良好随机性的许多陷阱。因为随机性是每个加密算法的核心，做出微小错误可能导致灾难性后果。如果你遇到以下边缘情况，记住以下内容是很好的：
- 分叉进程——当使用用户空间伪随机数生成器（一些对性能要求极高的应用可能别无选择）时，重要的是要记住，一个分叉的程序会产生一个新的子进程，其 PRNG 状态与其父进程相同。因此，从那时起，两个 PRNG 将产生相同的随机数序列。因此，如果你真的想使用用户空间 PRNG，你必须小心让分叉使用不同的种子来生成他们的 PRNG。
- 虚拟机（VMs）—当使用操作系统 PRNG 时，克隆 PRNG 状态也可能成为一个问题。想想虚拟机。如果整个 VM 的状态被保存，然后从这一点开始多次启动，每个实例可能会产生完全相同的随机数序列。有时这可以通过虚拟化程序和操作系统来解决，但在运行请求在虚拟机中生成随机数的应用程序之前，最好了解一下您正在使用的虚拟化程序的操作。
- 早期启动熵—虽然操作系统在用户操作设备时应该没有问题收集熵，因为用户与设备的交互产生的噪声，但嵌入式设备和无头系统在启动时需要克服更多的挑战以产生良好的熵。历史表明，一些设备倾向于以类似的方式启动并从系统中积累相同的初始噪声，导致使用相同种子用于其内部 PRNG 并生成相同系列的随机数。
存在一个漏洞窗口—启动时的熵空洞—在这个窗口期内，Linux 的 urandom 可能是完全可预测的，至少对于单核系统来说。[…] 当我们禁用了可能在无头或嵌入式设备上不可用的熵源时，Linux RNG 在每次启动时产生了相同可预测的流。
—Heninger 等人（“挖掘您的 P 和 Q：检测网络设备中普遍存在的弱密钥”，2012）
在这些罕见的情况下，当您确实需要在启动过程中尽早获取随机数时，可以通过提供从另一台机器的良好种子的getrandom或/dev/urandom 生成的初始熵来帮助系统。不同的操作系统可能提供此功能，如果您发现自己处于这种情况，请查阅它们的手册（像往常一样）。
如果可用，TRNG 为这个问题提供了一个简单的解决方案。例如，现代英特尔 CPU 嵌入了一个特殊的硬件芯片，从热噪声中提取随机性。这种随机性可以通过一个名为RDRAND的指令获得。
RDRAND争议
有趣的是，英特尔的RDRAND由于存在后门的恐惧而引起了很大争议。大多数集成了RDRAND作为熵源的操作系统会将其与其他熵源混合在一起，以协同的方式。这里的协同意味着一个熵源不能强制影响随机数生成的结果。
练习
想象一下，如果将不同的熵源简单地通过异或操作在一起，您能看出这可能无法成为协同的吗？
最后，让我提一下避免随机性缺陷的一个解决方案是使用更少依赖于随机性的算法。例如，你在第七章看到了，ECDSA 要求你每次签名时都要生成一个随机的 nonce，而 EdDSA 则不需要。另一个例子是在第四章中看到的 AES-GCM-SIV，如果你偶尔重复使用相同的 nonce，它不会发生灾难性的故障，而 AES-GCM 则会泄露认证密钥，然后失去密文的完整性。
8.5 公共随机性
到目前为止，我主要谈论了私密随机性，即你可能需要用于私钥的类型。有时，不需要隐私，需要公共随机性。在本节中，我简要概述了一些获得此类公共随机性的方法。我区分了两种情况：
- 一对多 —— 你想为其他人产生随机性。
- 多对多 —— 一组参与者希望共同产生随机性。
首先，让我们想象一下，你想以一种许多参与者可以验证的方式生成一系列的随机性。换句话说，这个流应该是不可预测的，但是从你的角度来看不可能被更改。现在想象一下，你有一个签名方案，它基于一个密钥对和一个消息提供唯一的签名。有了这样的签名方案，存在一种叫做可验证随机函数（VRF）的构造来以可验证的方式获得随机数（图 8.5 说明了这个概念）。以下是它的工作原理：
- 你生成一个密钥对并公布验证密钥。你还公布了一个公共种子。
- 为了生成随机数，你对公共种子进行签名并哈希签名。摘要就是你的随机数，签名也被公布为证明。
- 要验证随机数，任何人都可以对签名进行哈希以检查是否与随机数匹配，并使用公共种子和验证密钥验证签名是否正确。
图 8.5 可验证随机函数（VRF）通过公钥密码学生成可验证的随机性。要生成一个随机数，只需使用一个产生唯一签名的签名方案（如 BLS）对种子进行签名，然后对签名进行哈希以生成公共随机数。要验证生成的随机性，确保签名的哈希确实是随机数，并验证种子上的签名。
这个构造可以通过使用公共种子类似于计数器来产生许多随机数。因为签名是唯一的且公共种子是固定的，签署者无法生成不同的随机数。
练习
像 BLS（在图 8.5 和第七章中提到）这样的签名方案会生成唯一的签名，但对于 ECDSA 和 EdDSA 并非如此。你知道为什么吗？
要解决这个问题，互联网草案（一个旨在成为 RFC 的文档）tools.ietf.org/html/draft-irtf-cfrg-vrf-08 指定了如何使用 ECDSA 实现 VRF。在某些场景中（例如，抽奖游戏），几个参与者可能希望随机决定一个赢家。我们称他们为去中心化随机信标，因为他们的角色是即使一些参与者决定不参与协议，也要产生相同的可验证随机性。一个常见的解决方案是使用先前讨论过的 VRF，不是使用单一密钥，而是使用阈值分布密钥，即将密钥分割在许多参与者之间，只有在一定数量的参与者签署消息后才为给定消息生成唯一有效签名。这可能听起来有点混乱，因为这是我第一次谈到分布式密钥。请注意，您将在本章后面更多地了解这些内容。
一个流行的去中心化随机信标称为drand，由几个组织和大学共同运行。它可以在leagueofentropy.com找到。
生成良好随机性的主要挑战在于参与随机性生成过程的任何一方都不应能够预测或偏向最终输出。drand 网络不受其任何成员控制。没有单点故障，也没有任何 drand 服务器运营商可以偏向网络生成的随机性。
—drand.love（“drand 的工作原理”，2021）
现在我已经广泛讨论了随机性以及程序如何获取它，让我们将讨论转向密码学中秘密的作用以及如何管理这些秘密。
真实世界的密码学（二）（3）https://developer.aliyun.com/article/1508667
