真实世界的密码学（三）

原文：annas-archive.org/md5/655c944001312f47533514408a1a919a

译者：飞龙

协议：CC BY-NC-SA 4.0

第十一章：用户认证

本章涵盖了

• 认证人员和数据之间的区别

• 用户认证，根据密码或密钥对用户进行身份验证。

• 用户辅助认证以保护用户设备之间的连接

在本书的介绍中，我将密码学简化为两个概念：机密性和认证。 在实际应用中，保密性（通常）不是你的问题所在； 认证是大部分复杂性产生的地方。 我知道我已经在整本书中大量谈论了认证，但是它在密码学中使用的含义不同，可能是一个令人困惑的概念。 因此，本章从介绍认证的真正含义开始。 与密码学一样，没有协议是万能药，本章的其余部分将教你大量在实际应用中使用的认证协议。

11.1 认证回顾

到目前为止，你已经多次听说过认证，所以让我们回顾一下。 你学到了关于

• 在密码学原语中的认证，如消息认证码（在第三章中介绍）和认证加密（在第四章中介绍）

• 密码协议中的认证，如 TLS（在第九章中介绍）和 Signal（在第十章中介绍），其中协议的一个或多个参与者可以被认证

在第一种情况下，认证指的是消息的真实性（或完整性）。 在后一种情况下，认证是指向别人证明自己是谁。 这些是由相同单词涵盖的不同概念，这可能会相当令人困惑！ 但是牛津英语词典（www.oed.com/）指出，这两种用法都是正确的：

认证。证明或展示某事物为真实、真正或有效的过程或行为。

由于这个原因，你应该将认证视为密码学术语，根据上下文传达两个不同的概念：

• 消息/有效载荷认证—你正在证明一条消息是真实的，并且自其创建以来没有被修改过。 （例如，这些消息是否已经认证，还是有人可能篡改它们？）

• 源/实体/身份认证—你正在证明一个实体确实是他们声称的那个人。 （例如，我是否真的在与google.com通信？）

底线：认证是关于证明某物是它应该是的，而某物可以是人、消息或其他东西。 在本章中，我将仅使用术语认证来指代识别人或机器。 换句话说，身份认证。 顺便说一句，你已经看到了很多关于这种类型认证的内容：

• 在第九章，关于安全传输，你学到了机器如何通过使用公钥基础设施（PKI）来大规模认证其他机器。

• 在第十章中，关于端到端加密，您了解了人类如何通过使用首次使用信任（TOFU）（然后稍后验证）或使用信任网络（WOT）技术来规模化认证彼此。

在本章中，您将学习到前面未提及的其他两种情况。（我在图 11.1 中进行了回顾。）

• 用户认证，或者说机器如何认证人类——滴滴滴滴

• 用户辅助认证，或者说人类如何帮助机器认证彼此

图 11.1 在本书中，我讨论了三种情景下的源认证。当设备认证人类时，就发生了用户认证。当机器认证另一台机器时，就发生了机器认证。当一个人参与机器认证另一台机器时，就发生了用户辅助认证。

身份认证的另一个方面是身份部分。确实，我们如何在密码协议中定义像爱丽丝这样的人？机器如何认证你和我？遗憾的是（或者幸运的是），肉体和比特之间存在固有的差距。为了弥合现实和数字世界之间的鸿沟，我们总是假设爱丽丝是唯一知道一些秘密数据的人，为了证明她的身份，她必须证明她知道那些秘密数据。例如，她可以发送她的密码，或者她可以使用与她的公钥相关联的私钥签署一个随机挑战。

好了，介绍就到此为止。如果这一部分让你感到有些迷糊，接下来的众多例子会让你明白的。现在让我们首先看看机器找到的认证我们人类的多种方式！

11.2 用户认证，或摆脱密码的追求

本章的第一部分是关于机器如何认证人类，换句话说就是用户认证。有很多方法可以做到这一点，没有一种解决方案是万能的。但在大多数用户认证场景中，我们假设

• 服务器已经经过认证。

• 用户与之共享安全连接。

例如，您可以想象服务器通过网络公钥基础设施（PKI）对用户进行了认证，并且连接通过 TLS（在第九章中都有涉及）。在某种意义上，本节的大部分内容都是关于将单向认证连接升级为双向认证连接，就像图 11.2 所示的那样。

图 11.2 用户认证通常发生在已经安全的通道上，但只有服务器经过认证的情况。一个典型的例子是当您使用 HTTPS 浏览网页并使用您的凭据登录网页时。

我必须警告你：用户认证是一个充满了空头支票的广阔领域。您肯定已经多次使用密码对不同的网页进行认证，而您自己的经历可能类似于这样：

1. 您在网站上注册了用户名和密码。

2. 使用新凭据登录网站。

3. 当您恢复您的账户或者因为网站强制要求时，您需要更改密码。

4. 如果您运气不佳，您的密码（或其哈希值）可能会在一系列数据库泄露中泄露。

听起来耳熟吗？

请注意，本章节将忽略密码/账户恢复，因为它们与密码学关系不大。只需知道它们通常与您最初注册的方式相关联。例如，如果您在工作场所的 IT 部门注册，那么如果您忘记密码，您可能需要去找他们，如果不小心的话，他们可能是系统中最薄弱的环节。事实上，如果我可以通过拨打一个号码并告诉某人您的生日来恢复您的账户，那么在登录时进行的任何酷炫的密码学都无济于事。

实现先前用户认证流程的一个天真的方法是在注册时存储用户密码，然后在登录时要求用户输入密码。正如第三章所述，一旦成功认证，用户通常会获得一个可以在每个后续请求中发送的 cookie，而不是用户名和密码。但是等等；如果服务器以明文形式存储您的密码，那么其数据库的任何泄露都会将您的密码暴露给攻击者。这些攻击者随后将能够使用它登录您在其中使用相同密码注册的任何网站。

更好的存储密码的方法是使用像您在第二章中学到的标准化的 Argon2 这样的密码哈希算法。这将有效地防止对数据库进行的一种破坏性攻击，以泄露您的密码，尽管一个过度进入的入侵者仍然可以在您每次登录时看到您的密码。然而，许多网站和公司仍然以明文形式存储密码。

练习

有时，应用程序试图通过让客户端在发送密码之前对密码进行哈希处理（也许使用密码哈希）来解决服务器在注册时了解用户密码的问题。您能确定这是否真的有效吗？

此外，人类在密码方面天生就不擅长。我们通常更喜欢使用简单易记的短密码。而且，如果可能的话，我们希望可以在所有地方都重复使用相同的密码。

81%的黑客入侵事件利用了被盗或弱密码。

—Verizon 数据泄露报告（2017）

弱密码和密码重用的问题导致了许多愚蠢和恼人的设计模式，试图迫使用户更加认真对待密码。例如，一些网站要求您在密码中使用特殊字符，或者强制您每 6 个月更改一次密码，等等。此外，许多协议试图“修复”密码或完全摆脱它们。每年，新的安全专家似乎都认为“密码”这个概念已经过时。然而，它仍然是最广泛使用的用户认证机制。

所以在这里，密码可能会一直存在。然而，存在许多可以改进或替代密码的协议。让我们看看这些。

11.2.1 一切由一个密码控制：单点登录（SSO）和密码管理器

好的，密码重用是不好的，那我们能做些什么呢？天真地，用户可以为不同的网站使用不同的密码，但这种方法有两个问题：

• 用户不擅长创建许多不同的密码。

• 记住多个密码所需的心理负担是不切实际的。

为了缓解这些问题，已经广泛采用了两种解决方案：

• 单点登录（SSO）—SSO 的理念是允许用户通过证明他们拥有单个服务的帐户来连接到许多不同的服务。这样，用户只需记住与该服务关联的密码，就能连接到许多服务。想象一下“使用 Facebook 登录”类型的按钮，正如图 11.3 所示。

• 密码管理器—如果您使用的不同服务都支持前述 SSO 方法，那么这种方法很方便，但显然对于像网页这样的场景来说并不可扩展。在这些极端情况下，一个更好的方法是改进客户端，而不是试图在服务器端解决问题。如今，现代浏览器内置了密码管理器，当您在新网站注册时可以建议复杂的密码，并且只要您记住一个主密码，它们就可以记住您的所有密码。

图 11.3 网页上单点登录（SSO）的示例。通过在 Facebook 或 Google 上拥有帐户，用户可以连接到新服务（在此示例中是 Airbnb），而无需考虑新密码。

单点登录（SSO）的概念在企业世界并不新鲜，但它在普通终端用户中的成功是比较近期的。如今，在建立 SSO 时，有两个主要竞争者协议：

• 安全断言标记语言 2.0（SAML）—一种使用可扩展标记语言（XML）编码的协议。

• OpenID Connect（OIDC）—OAuth 2.0（RFC 6749）授权协议的扩展，使用 JavaScript 对象表示法（JSON）编码。

SAML 仍然被广泛使用，主要是在企业环境中，但（目前）它是一种遗留协议。另一方面，OIDC 可以在网页和移动应用程序中随处可见。你很可能已经使用过它！

认证协议通常被认为很难正确使用。OIDC 依赖的协议 OAuth2 以易被滥用而臭名昭著。另一方面，OIDC 被很好地规范化（参见openid.net）。确保你遵循标准并查看最佳实践，因为这可以避免许多麻烦。

注意 这里有另一个例子，一个相当大的公司决定不遵循这些建议。2020 年 5 月，苹果登录 SSO 流程不遵循 OIDC 的做法被发现存在漏洞。任何人都可以通过查询苹果的服务器获得任何苹果账户的有效 ID 令牌。

SSO 对用户很有好处，因为它减少了他们需要管理的密码数量，但它并没有完全消除密码。用户仍然必须使用密码连接到 OIDC 提供者。接下来，让我们看看密码学如何帮助隐藏密码。

11.2.2 不想看到他们的密码？使用非对称密码身份验证密钥交换

前一节调查了试图简化用户身份管理的解决方案，允许他们使用仅链接到单个服务的一个帐户来认证到多个服务。虽然 OIDC 等协议很好，因为它们有效地减少了用户需要管理的密码数量，但它们并不改变某些服务仍然需要以明文形式查看用户密码的事实。即使密码在密码哈希后存储，每次用户注册、更改密码或登录时仍然以明文形式发送。

称为非对称（或增强型）密码身份验证密钥交换（PAKEs）的加密协议试图提供用户身份验证，而无需用户直接将其密码传递给服务器。这与对称或平衡的 PAKEs协议形成对比，后者双方都知道密码。

目前最流行的非对称 PAKE 是安全远程密码（SRP）协议，该协议于 2000 年首次标准化于 RFC 2944（“Telnet Authentication: SRP”），后来通过 RFC 5054（“Using the Secure Remote Password (SRP) Protocol for TLS Authentication”）集成到 TLS 中。它是一个相当古老的协议，并且存在许多缺陷。例如，如果注册流程被中间人攻击者拦截，那么攻击者将能够冒充并登录为受害者。它还不能很好地与现代协议配合使用，因为它无法在椭圆曲线上实例化，更糟糕的是，它与 TLS 1.3 不兼容。

自 SRP 发明以来，已经提出并标准化了许多非对称 PAKE。2019 年夏季，IETF 的 Crypto Forum Research Group（CFRG）开始了一个 PAKE 选择过程，目标是为每个 PAKE 类别（对称/平衡和非对称/增强型）选择一个算法进行标准化。2020 年 3 月，CFRG 宣布 PAKE 选择过程结束，选择

• CPace——由 Haase 和 Benoît Labrique 发明的推荐的对称/平衡 PAKE

• OPAQUE——由 Stanislaw Jarecki、Hugo Krawczyk 和 Jiayu Xu 发明的推荐的非对称/增强型 PAKE

在本节中，我将讨论 OPAQUE，在 2021 年初仍在标准化过程中。在本章的第二节中，您将了解更多关于对称 PAKEs 和 CPace 的信息。

OPAQUE 从同音异义词 O-PAKE 中取其名称，其中 O 指的是术语 oblivious。这是因为 OPAQUE 依赖于本书中尚未提到的密码原语：一个 oblivious pseudorandom function（OPRF）。

无意识伪随机函数（OPRFs）

OPRFs 是一个模拟第三章中所学的 PRFs 的两方协议。作为提醒，PRF 在某种程度上等同于人们对 MAC 的预期：它接受一个密钥和一个输入，并给出一个固定长度的完全随机输出。

注意：密码学中的术语 oblivious 通常指的是一个参与方计算加密操作而不知道另一方提供的输入的协议。

下面是 OPRF 的高层次工作方式：

1. Alice 想要对输入计算一个 PRF，但希望输入保持秘密。她使用一个随机值（称为 blinding factor） “盲化” 她的输入，并将其发送给 Bob。

2. Bob 使用他的秘钥在这个被盲化的数值上运行 OPRFs，但输出仍然被盲化，所以对 Bob 毫无用处。Bob 然后将这个返回给 Alice。

3. Alice 最后使用与之前用于获取真实输出相同的盲化因子 “解盲” 结果。

需要注意的是，每次 Alice 想要执行这个协议时，她都必须创建一个不同的盲化因子。但无论她使用什么盲化因子，只要她使用相同的输入，她总是会得到相同的结果。我在图 11.4 中进行了说明。

图 11.4 一个无意识 PRF（OPRF）是一种构造，允许一个参与方在不了解该参与方输入的情况下计算 PRF。为了实现这一点，Alice 首先生成一个随机的盲化因子，然后使用它来盲化她的输入，然后发送给 Bob。Bob 使用他的秘密密钥在被盲化的数值上计算 PRF，然后将盲化输出发送给 Alice，Alice 可以对其进行解盲。结果不依赖于盲化因子的值。

这是在离散对数问题难度高的群中实现的 OPRF 协议的一个示例：

1. Alice 将她的输入转换为一个群元素 x。

2. Alice 生成一个随机的盲化因子 r。

3. Alice 通过计算 blinded_input = x^r 来盲化她的输入。

4. Alice 将 blinded_input 发送给 Bob。

5. Bob 计算 blinded_output = blinded_input^k，其中 k 是秘密密钥。

6. Bob 将结果发送回给 Alice。

7. Alice 然后可以通过计算 output = blinded_output^(1/r) = x^k 来解盲产生的结果，其中 1/r 是 r 的倒数。

OPAQUE 如何使用这个有趣的构造是非对称 PAKE 的整个技巧。

OPAQUE 非对称 PAKE，它是如何工作的？

我们的想法是，我们希望客户端，比如 Alice，能够与某个服务器进行经过身份验证的密钥交换。我们还假设 Alice 已经知道服务器的公钥或已经有一种方法对其进行身份验证（服务器可以是 HTTPS 网站，因此 Alice 可以使用 Web PKI）。让我们看看如何逐步构建这个来逐渐理解 OPAQUE 的工作原理。

第一个想法： 使用公钥密码学来验证 Alice 的连接一侧。如果 Alice 拥有长期密钥对并且服务器知道公钥，她可以简单地使用她的私钥与服务器进行相互验证的密钥交换，或者她可以签署服务器给出的挑战。不幸的是，非对称私钥太长了，Alice 只能记住她的密码。她可以在当前设备上存储一对密钥，但她也想以后能够从另一台设备登录。

第二个想法： Alice 可以使用类似 Argon2 这样的基于密码的密钥派生函数（KDF）从她的密码派生非对称私钥，你在第二章和第八章学到了。然后，Alice 的公钥可以存储在服务器上。如果我们想要在数据库泄露的情况下避免有人对整个数据库进行密码测试，我们可以让服务器为每个用户提供一个不同的盐，他们必须将其与基于密码的 KDF 一起使用。

这已经相当不错了，但 OPAQUE 想要抛弃一种攻击：预计算攻击。我可以尝试以你的身份登录，接收到你的盐，然后离线预计算大量非对称私钥及其关联的公钥。在数据库被破坏的那一天，我可以迅速查看是否可以在我的大量预计算的非对称公钥列表中找到您的公钥和关联的密码。

第三个想法： 这就是 OPAQUE 的主要技巧所在！我们可以使用 OPRF 协议和 Alice 的密码来派生非对称私钥。如果服务器为每个用户使用不同的密钥，那么这就等同于有盐（攻击只能针对一个用户）。这样，想要基于我们密码的猜测预先计算非对称私钥的攻击者必须执行在线查询（防止离线暴力攻击）。在线查询很好，因为它们可以进行速率限制（例如，每小时不超过 10 次登录尝试），以防止这种类型的在线暴力攻击。

注意，这实际上并不是 OPAQUE 的工作方式：与其让用户派生非对称私钥，OPAQUE 让用户派生对称密钥。然后，对称密钥用于加密您的非对称密钥对的备份和一些附加数据（例如可以包括服务器的公钥）。我在图 11.5 中说明了算法。

图 11.5 使用 OPAQUE 注册到服务器时，Alice 生成一个长期密钥对并将其公钥发送到服务器，服务器将其存储并与 Alice 的身份关联起来。然后，她使用 OPRF 协议从她的密码获取一个强对称密钥，并将密钥对的加密备份发送给服务器。要登录，她从服务器获取她的加密密钥对，然后使用她的密码执行 OPRF 协议以获取能够解密她的密钥对的对称密钥。现在只需使用这个密钥执行一个互认证的密钥交换（或者可能签署一个挑战）。

在进入下一节之前，让我们回顾一下你在这里学到的内容。图 11.6 对此进行了说明。

图 11.6 密码是验证用户身份的方便方式，因为它们存在于某人的头脑中，并且可以在任何设备上使用。另一方面，用户很难创建强密码，因为用户往往在网站之间重复使用密码，密码泄漏可能会造成严重损失。SSO 允许您使用一个（或几个）服务连接到多个服务，而不对称（或增强）密码验证密钥交换允许您在服务器不了解真实密码的情况下进行身份验证。

11.2.3 一次性密码并不真的是密码：使用对称密钥实现无密码登录

好了，到目前为止一切都很好。你已经了解了应用程序可以利用的不同协议来使用密码对用户进行身份验证。但是，你可能已经听说了，密码也不是那么好。它们容易受到暴力破解攻击，往往被重复使用，被窃取等等。如果我们可以避免使用密码，我们可以使用什么？

答案就是——密钥！正如你所知，在密码学中有两种类型的密钥，而且两种类型都可能很有用：

• 对称密钥

• 不对称密钥

本节介绍基于对称密钥的解决方案，而下一节介绍基于不对称密钥的解决方案。让我们想象一下，Alice 使用对称密钥（通常由服务器生成并通过 QR 码传输给你）注册了一个服务。后来验证 Alice 的一个天真的方法是简单地要求她发送对称密钥。当然，这并不好，因为她的秘密泄漏将给攻击者无限制的访问权限。相反，Alice 可以从对称密钥中派生出所谓的一次性密码（OTPs），并在长期对称密钥的位置发送这些 OTP。尽管 OTP 不是密码，但其名称表明 OTP 可以代替密码使用，并警告不应重复使用。

基于 OTP 的用户身份验证背后的想法很简单：你的安全性来自于一个（通常是）16 到 32 字节的均匀随机对称密钥的知识，而不是一个低熵密码。这个对称密钥允许你按需生成 OTP，如图 11.7 所示。

图 11.7 一次性密码（OTP）算法允许您从对称密钥和一些附加数据创建任意数量的一次性密码。附加数据不同，取决于 OTP 算法。

OTP 身份验证通常在移动应用程序中实现（请参见图 11.8 中的一个热门示例）或安全密钥中（这是一个可以插入计算机 USB 端口的小设备）。可以使用两种主要方案来生成 OTP：

• 基于 HMAC 的一次性密码（HOTP）算法，标准化在 RFC 4226 中，这是一种额外数据为计数器的 OTP 算法。

• 基于时间的一次性密码（TOTP）算法，标准化在 RFC 6238 中，这是一种额外数据为时间的 OTP 算法。

大多数应用程序现在使用 TOTP，因为 HOTP 需要客户端和服务器都存储状态（计数器）。如果一方失去同步，无法再生成（或验证）合法的 OTP，存储状态可能会导致问题。

图 11.8 Google Authenticator 移动应用程序的屏幕截图。该应用程序允许您存储唯一的应用程序专用对称密钥，然后可与 TOTP 方案一起使用生成 6 位数的一次性密码（OTP），仅有效 30 秒。

在大多数情况下，这就是 TOTP 的工作方式：

• 在注册时，服务向用户通信一个对称密钥（也许使用 QR 码）。 然后，用户将此密钥添加到 TOTP 应用程序中。

• 在登录时，用户可以使用 TOTP 应用程序计算一次性密码。 这是通过计算HMAC（symmetric_key，time）来完成的，其中time表示当前时间（四舍五入到分钟，以使一次性密码在 60 秒内有效）。然后

  a) TOTP 应用程序向用户显示派生的一次性密码，截断并以人类可读的基数显示（例如，缩减为 10 进制的 6 个字符，使其全部为数字）。

  b) 用户将一次性密码复制或键入到相关应用程序中。

  c) 应用程序检索用户关联的对称密钥，并以与用户相同的方式计算一次性密码。如果结果与接收到的一次性密码匹配，则用户成功验证身份。

当然，用户的一次性密码（OTP）与服务器计算的密码必须在恒定时间内进行比较。这类似于 MAC 身份验证标签检查。我在图 11.9 中展示了这个流程。

图 11.9 Alice 使用 TOTP 作为认证在 example.com 上注册。她将网站的对称密钥导入到她的 TOTP 应用程序中。稍后，她可以要求应用程序为 example.com 计算一次性密码，并将其用于与网站进行身份验证。网站 example.com 获取与 Alice 关联的对称密钥，并使用 HMAC 和当前时间计算一次性密码。网站接下来以常量时间比较 Alice 发送的一次性密码。

这种基于 TOTP 的身份验证流程并不理想。有许多可以改进的地方，例如：

• 由于服务器也拥有对称密钥，认证可以被伪造。

• 您可以被社会工程学方式获得您的一次性密码。

因此，对称密钥是另一种不完美的密码替代方案。接下来，让我们看看如何使用非对称密钥来解决这些缺点。

钓鱼

钓鱼（或社会工程学）是一种不针对软件漏洞而是针对人的漏洞的攻击。想象一下，一个应用程序要求您输入一次性密码进行身份验证。在这种情况下，攻击者可能会尝试以您的身份登录应用程序，并在提示输入一次性密码时，给您打电话要求您提供有效的密码（假装他们为该应用程序工作）。

你在告诉我你不会上当吗！优秀的社会工程师擅长编织可信度很高的故事，并制造出一种紧迫感，使我们中的大多数人都会不假思索地泄露秘密。如果你仔细想想，我们之前谈论过的所有协议都容易受到这些类型的攻击的影响。

11.2.4 用非对称密钥替换密码

现在我们正在处理公钥密码学，有多种方法可以使用非对称密钥对服务器进行身份验证。我们可以

• 在密钥交换中使用我们的非对称密钥来验证连接的我们这一侧

• 在已经获得验证的连接中使用我们的非对称密钥与认证的服务器

让我们看看每种方法。

密钥交换中的双向认证

你已经听说过第一种方法了：使用密钥交换中的非对称密钥。在第九章中，我提到 TLS 服务器可以要求客户端在握手中使用证书。通常，公司会向其员工的设备配备唯一的员工证书，允许他们对内部服务进行身份验证。图 11.10 从用户的角度提供了一个大致的外观。

图 11.10 一页提示用户的浏览器获取客户端证书。用户然后可以从本地已安装的证书列表中选择要使用的证书。在 TLS 握手中，客户端证书的密钥用于签署握手记录，包括客户端的临时公钥，该公钥用作握手的一部分。

客户端证书相当简单。例如，在 TLS 1.3 中，服务器可以在握手期间通过发送 CertificateRequest 消息来请求客户端进行身份验证。然后，客户端通过在 Certificate 消息中发送其证书，然后在 CertificateVerify 消息中对发送和接收的所有消息进行签名（其中包括用于密钥交换的临时公钥）。如果服务器能够识别证书并成功验证客户端的签名，则客户端经过身份验证。另一个例子是安全外壳（SSH）协议，该协议也要求客户端使用服务器已知的公钥对握手的部分进行签名。

请注意，在握手阶段使用公钥加密进行身份验证的方法不仅限于签名。Noise 协议框架（在第九章中也有介绍）有几种握手模式，可以仅使用 DH 密钥交换进行客户端身份验证。

使用 FIDO2 进行握手后的用户身份验证

使用非对称密钥的第二种身份验证类型使用已经 安全 的连接，仅服务器被验证。为此，服务器可以简单地要求客户端对一个 随机 挑战进行签名。这样，重放攻击就被防止了。

在这个领域有一个有趣的标准是快速身份在线 2（FIDO2）。FIDO2 是一个开放标准，定义了如何使用非对称密钥对用户进行身份验证。该标准专门针对钓鱼攻击，并且为此，FIDO2 只能与硬件认证器一起使用。硬件认证器只是可以生成和存储签名密钥，并能签署任意挑战的物理组件。FIDO2 分为两个规范（图 11.11）：

• 客户端到认证器协议（CTAP）—CTAP 指定了漫游认证器和客户端可以使用的通信协议。漫游认证器是外部于您的主设备的硬件认证器。在 CTAP 规范中，客户端被定义为要查询这些认证器的软件的一部分，作为身份验证协议的一部分。因此，客户端可以是操作系统、本地应用程序（如浏览器）等。

• Web 身份验证（WebAuthn）—WebAuthn 是 Web 浏览器和 Web 应用程序可以使用的协议，用于使用硬件认证器对用户进行身份验证。因此，必须由浏览器来实现它以支持认证器。如果您正在构建一个 Web 应用程序，并希望支持通过硬件认证器进行用户身份验证，则需要使用 WebAuthn。

图 11.11 FIDO2 可用的两种硬件认证器类型：（左侧）Yubikey，一种漫游认证器，以及（右侧）TouchID，一种内置认证器。

WebAuthn 允许网站不仅使用漫游验证器，还可以使用平台验证器。平台验证器是设备提供的内置验证器。它们在各种平台上实现不同，并且通常受生物识别技术保护（例如，指纹识别器、面部识别等）。

我们现在结束了本章的第一部分。但在我这样做之前，图 11.12 总结了我谈论过的非基于密码的认证协议。

图 11.12 要进行无密码认证，应用程序可以允许用户通过基于 OTP 的协议使用对称密钥，或者通过 FIDO2 标准使用非对称密钥。FIDO2 支持不同类型的验证器，例如漫游验证器（通过 CTAP 标准）或内置验证器。

现在，您已经了解了许多不同的技术和协议，这些技术和协议旨在改善密码或将其替换为更强大的加密解决方案，您可能会想知道，应该使用哪一种？每种解决方案都有其自己的局限性，可能没有一种解决方案能够胜任。如果没有，那就结合多种解决方案吧！这个想法被称为多因素认证（MFA）。实际上，很有可能您已经在密码之外使用了 OTP 或 FIDO2 作为第二个身份验证因素。

这结束了本章关于用户身份验证的前半部分。接下来，让我们看看人类如何帮助设备相互认证。

11.3 用户辅助认证：使用人类帮助配对设备

人类每天都在帮助机器相互认证 —— 每一天！您通过将无线耳机与手机配对，或者将手机与汽车配对，或者将某个设备连接到家庭 WiFi，等等来完成了这一点。而且与任何配对一样，底层很可能是密钥交换。

上一节中的身份验证协议是在已经安全的通道中进行的（可能是通过 TLS），服务器进行了身份验证。与之相反，本节大部分内容试图为两个不知道如何相互认证的设备提供一个安全通道。在这个意义上，您将在本节中学到的内容是人类如何帮助将一个不安全的连接升级为一个相互认证的连接。因此，接下来您将学到的技术应该让您想起第十章端到端协议中的一些建立信任的技术，只是在那里，两个人试图相互认证。

如今，你将遇到的最常见的不安全连接（不通过互联网），都是基于短程无线电频率的协议，如蓝牙、WiFi 和近场通信（NFC）。 NFC 是你用来用手机或银行卡的“非接触”支付。使用这些通信协议的设备通常从低功耗电子设备到功能齐全的计算机都有。这已经给我们设置了一些限制：

• 您正在尝试连接的设备可能没有屏幕来显示密钥或手动输入密钥的方法。我们称之为配置该设备。例如，今天大多数无线音频耳机只有几个按钮而已。

• *由于人类是验证过程的一部分，必须键入或比较长字符串通常被认为是不切实际和不用户友好的。*因此，许多协议试图将安全相关字符串缩短为 4 位或 6 位数字密码。

练习

想象一种协议，你必须输入正确的 4 位数字密码才能安全连接到设备。只通过猜测选择正确密码的机会有多大？

你可能会回想起你的一些设备配对经历，并且意识到现在很多情况都是自动完成的。例如

1. 你按下了设备上的一个按钮。

2. 设备进入配对模式。

3. 你接着试图在手机的蓝牙列表中找到设备。

4. 在点击设备图标后，它成功地将设备与您的手机配对。

如果你读过第十章，这应该让你想起了第一次使用时信任（TOFU）。不过，这次我们手头还有一些其他的牌：

• 接近性——两个设备必须彼此靠近，特别是如果使用 NFC 协议。

• 时间——设备配对通常受时间限制。如果，例如，在 30 秒的时间窗口内，配对不成功，必须手动重新启动该过程是很常见的。

与 TOFU 不同，这些真实场景通常不允许你事后验证你是否已连接到正确的设备。这并不理想，如果可能的话，应该努力提升安全性。

注意顺便提一下，这就是蓝牙核心规范实际上将类似 TOFU 的协议称为的内容：“Just Works”。我应该提到，目前所有内置的蓝牙安全协议都因许多攻击而破坏，包括 2019 年发布的最新 KNOB 攻击（knobattack.com）。尽管如此，本章介绍的技术如果设计和实施正确，仍然是安全的。

我们工具箱中的下一步是什么？这就是我们将在本节中看到的内容：人类帮助设备进行身份验证的方法。剧透：

• 你会发现，加密密钥始终是最安全的方法，但不一定是最用户友好的。

• 您将了解关于对称 PAKE 和如何在两个设备上输入相同密码以安全连接它们的内容。

• 你将了解基于短认证字符串（SAS）的协议，这些协议通过让你比较和匹配两个设备显示的两个短字符串来验证密钥交换的有效性。

让我们开始吧！

11.3.1 预共享密钥

幼稚地，将用户连接到设备的第一种方法将是重用你在第九章或第十章学到的协议（例如，TLS 或 Noise），并向两个设备提供对称共享密钥或更好地，提供长期公钥以为将来的会话提供前向保密性。这意味着每个设备学习另一个设备的公钥需要两件事：

• 你需要一种方法来导出设备的公钥。

• 你需要一种方法来导入公钥。

正如我们将看到的，这并不总是简单或用户友好的。但请记住，我们有一个参与的人可以观察和（也许）操纵这两个设备。这与我们以前见过的其他场景不同，我们可以利用这一点！

认证问题 - 密码学中的一个主要问题是在不安全的通道上建立安全的点对点（或群组）通信。在没有额外安全通道的假设下，这个任务是不可能的。但是，假设有一些前提条件，存在许多建立安全通信的方法。

—Sylvain Pasini（《使用认证通道进行安全通信》，2009 年）

所有接下来的协议都基于这样一个事实：你（负责人类）拥有一个额外的带外通道。这使您可以安全地通信一些信息。添加此带外通道可以被建模为两个设备可以访问两种类型的通道（如图 11.13 所示）：

• 一个不安全的通道——想象一下与设备连接的蓝牙或 WiFi 连接。默认情况下，用户无法对设备进行身份验证，因此可能会受到中间人攻击（MITM）。

• 一个经过认证的通道——想象一下设备上的屏幕。该通道提供了所传输信息的完整性/真实性，但机密性较差（有人可能在你旁边偷看）。

图 11.13 用户辅助身份验证协议允许用户配对两个设备，这些协议模拟了设备之间的两种类型的通道：一个不安全的通道（例如，NFC、蓝牙、WiFi 等），我们假设该通道由对手控制，以及一个经过认证的通道（例如，现实生活中的通道），该通道不提供机密性，但可以用于交换相对较小的信息量。

由于这种带外通道提供的保密性较差，我们通常不希望使用它来导出机密信息，而是用于公共数据。例如，设备的屏幕可以显示公钥或某些摘要。但是一旦您导出了一个公钥，您仍然需要另一个设备来导入它。例如，如果密钥是一个二维码，那么另一个设备可能能够扫描它，或者如果密钥以人类可读的格式编码，那么用户可以使用键盘在另一个设备上手动输入它。一旦两个设备都配置了彼此的公钥，您可以使用我在第九章中提到的任何协议来执行两个设备之间的相互认证密钥交换。

我希望您从本节中了解到，在您的协议中使用加密密钥始终是实现某些目标的最安全方式，但并不总是最用户友好的方式。然而，现实世界的密码学充满了妥协和权衡，这就是为什么下面的两种方案不仅存在，而且是认证设备最流行的方式。

让我们看看在无法导出和导入长公钥的情况下如何使用密码启动双向认证密钥交换。然后我们将看看短认证字符串如何在无法将数据导入到一个或两个设备的情况下提供帮助。

11.3.2 使用 CPace 进行对称密码认证密钥交换

如果可能的话，您应该采用上述解决方案，因为它依赖于强大的非对称密钥作为信任的根源。然而，实践中发现，手动使用一串长字符串表示的密钥在一些笨重的键盘上输入是很繁琐的。那么这些亲爱的密码呢？它们要短得多，因此更容易处理。我们喜欢密码对吧？也许我们不喜欢，但用户喜欢，而现实世界的密码学充满了妥协。所以就这样吧。

在关于对称密码认证密钥交换的部分中，我提到了存在一个对称（或平衡）版本，其中知道共同密码的两个对等方可以执行相互认证密钥交换。这正是我们需要的。

可组合密码认证连接建立（CPace）于 2008 年由 Björn Haase 和 Benoît Labrique 提出，并于 2020 年初被 CFRG（密码论坛研究小组）选为官方推荐。该算法目前正在作为 RFC 标准化。简化的协议看起来类似于以下内容（图 11.14 说明了该算法）：

• 两个设备基于一个共同的密码派生一个生成器（用于某个预定循环群）。

• 然后两个设备使用这个生成器在其上执行临时 DH 密钥交换。

图 11.14 CPace PAKE 的工作原理是让两个设备基于一个密码创建一个生成器，然后将其用作通常的临时 DH 密钥交换的基础。

当然，魔鬼在细节中，作为一个现代规范，CPace 针对椭圆曲线的“陷阱”，并定义了何时必须验证接收到的点是否在正确的群中（由于时髦的 Curve25519，不幸的是，它不构成一个素数群）。它还指定了如何基于密码在椭圆曲线群中派生生成器（使用所谓的哈希到曲线算法）以及如何做到这一点（不仅使用普通密码，还使用唯一的会话 ID 和一些附加的上下文元数据，比如对等方 IP 地址等等）。

这些步骤很重要，因为双方都必须以防止它们知道其离散对数 x 的方式派生生成器 h，使得 g^x = h。最后，会话密钥是从 DH 密钥交换输出、记录（临时公钥）和唯一的会话 ID 派生的。

直觉上，你可以看到冒充其中一方并在握手的一部分发送一个群元素意味着你发送了一个公钥，这个公钥与你无法知道的私钥相关联。这意味着如果你不知道密码，你永远无法执行 DH 密钥交换。记录看起来就像一个正常的 DH 密钥交换，所以，没有运气（只要 DH 是安全的）。

11.3.3 我的密钥交换被 MITM 攻击了吗？只需检查一个短认证字符串（SAS）。

在本章的第二部分中，你看到了不同的协议，它们允许两个设备在人类的帮助下配对。然而，我提到有些设备受限制以至于无法使用这些协议。让我们来看看一种方案，当两个设备无法导入密钥但可以向用户显示一些有限的数据时使用（也许通过屏幕、或者通过打开一些 LED、或者通过发出一些声音等等）。

首先，记住在第十章中，你学到了如何在 握手后（密钥交换后）使用 指纹（传输的哈希）对会话进行认证。我们可以像这样使用一些东西，因为我们有我们的带外信道来传递这些指纹。如果用户能够成功比较和匹配从两台设备获取的指纹，那么用户就知道密钥交换没有被 MITM 攻击。

指纹的问题在于它们是长字节串（通常为 32 个字节长），可能难以显示给用户。它们也很笨重，难以比较。但对于设备配对，我们可以使用更短的字节串，因为我们在实时进行比较！我们称这些为 短认证字符串（SAS）。SAS 被广泛使用，特别是由于它们相当用户友好（请参见图 11.15 中的示例）。

图 11.15 要通过蓝牙将手机与汽车配对，可以使用数字比对模式生成一个短的经过身份验证的字符串（SAS），该字符串是两个设备之间协商的安全连接的一部分。不幸的是，正如我在本章早些时候所述，由于 KNOB 攻击，蓝牙的安全协议目前已经破解（截至 2021 年）。如果你控制着这两个设备，你需要实现自己的 SAS 协议。

SAS-based schemes 没有任何标准，但大多数协议（包括蓝牙的数字比对）实现了一种变种的手动认证迪菲-赫尔曼（MA-DH）。MA-DH 是一种简单的密钥交换协议，其附加的技巧使得攻击者很难在中间人攻击中主动干预协议。你可能会问，为什么不只是从截断的指纹中创建 SAS？为什么需要一种技巧？

SAS 通常是一个 6 位数，可以通过将传输的哈希值截断为少于 20 位并将其转换为十进制数字来获得。因此，SAS 实际上非常小，这使得攻击者更容易在截断的哈希上获取第二个前像。在图 11.16 中，我们以两个设备为例（尽管我们使用了 Alice 和 Bob），执行一个未经身份验证的密钥交换。一个主动的 MITM 攻击者可以在第一个消息中用他们自己的公钥替换 Alice 的公钥。一旦攻击者收到 Bob 的公钥，他们就会知道 Bob 将计算什么样的 SAS（基于攻击者的公钥和 Bob 的公钥的截断哈希）。攻击者只需生成许多公钥，以找到一个（public_key[E]2），使得 Alice 的 SAS 与 Bob 的匹配。

图 11.16 典型的未经身份验证的密钥交换（左侧）可以被主动的 MITM 攻击者（右侧）拦截，后者可以替换 Alice 和 Bob 的公钥。如果 Alice 和 Bob 都生成相同的短的经过身份验证的字符串，则 MITM 攻击成功。也就是说，如果 HASH(public_key[A] || public_key[E2]) 和 HASH(public_key[E2] || public_key[B]) 匹配。

生成一个公钥以使两个 SAS 匹配实际上相当容易。想象一下 SAS 是 20 位，那么只需要 2²⁰ 次计算，你就应该能够找到一个第二个前像，使得 Alice 和 Bob 都生成相同的 SAS。即使在一部廉价手机上，这也应该是相当快速的计算。

SAS-based key exchanges 的技巧在于防止攻击者能够选择他们的第二个公钥，从而强制两个 SAS 匹配。为了做到这一点，Alice 在看到 Bob 的公钥之前简单地发送了她的公钥的一个承诺（如图 11.17 所示）。

图 11.17 左侧的图示了一个安全的 SAS-based 协议，其中 Alice 首先发送她的公钥的承诺。在收到 Bob 的公钥后，她只在之后才揭示自己的公钥。因为她已经对其进行了承诺，所以她不能根据 Bob 的密钥自由选择她的密钥对。如果交换被主动进行了 MITM 攻击（右侧的图示），攻击者将无法选择任何密钥对以强制 Alice 和 Bob 的 SAS 匹配。

与以前的不安全方案一样，攻击者选择的 public_key[E1] 不会给他们任何优势。但现在，他们也不能选择一个 public_key[E2] 来帮助，因为在协议的这一点上他们不知道 Bob 的 SAS。他们被迫“盲目射击”，希望 Alice 和 Bob 的 SAS 会匹配。

如果 SAS 是 20 位，那么概率是 1,048,576 中的 1。攻击者可以通过多次运行协议来增加机会，但请记住，协议的每个实例都必须由用户手动匹配 SAS。实际上，这种摩擦自然地防止了攻击者获得过多的彩票。

图 11.18 你学到了关于配对两台设备的三种技术：（1）用户可以帮助设备获取彼此的公钥，以便它们可以执行密钥交换；（2）用户可以在两台设备上输入相同的密码，以便它们可以执行对称密码认证密钥交换；或者（3）用户可以事后验证密钥交换的指纹，以确认没有 MITM 攻击者拦截了配对。

故事时间

有趣的是，当我写第十章关于端对端加密时，我开始研究 Matrix 端对端加密聊天协议的用户是如何验证他们的通信的。为了使验证更加用户友好，Matrix 创建了自己的 SAS-based 协议变种。不幸的是，它对 X25519 密钥交换的共享密钥进行了哈希处理，但在哈希中没有包含要交换的公钥。

在第五章中，我提到验证 X25519 公钥是很重要的。Matrix 没有这样做，这使得 MITM 攻击者能够向用户发送不正确的公钥，迫使他们最终得到相同的可预测的共享密钥，进而得到相同的 SAS。这完全破坏了协议的端对端加密声明，并且很快由 Matrix 进行了修复。

这就是全部内容！图 11.18 回顾了本章第二部分中学到的不同技术。下次见在第十二章。

摘要

• 用户身份验证协议（机器验证人类的协议）通常在安全连接上进行，只有机器（服务器）已经通过验证。在这个意义上，它将单向验证连接升级为双向验证连接。

• 用户认证协议大量使用密码。密码已被证明是一种相对实用的解决方案，并被用户广泛接受。但由于密码卫生不佳、熵值低和密码数据库泄露等问题，密码也导致了许多问题。

• 有两种方法可以避免用户携带多个密码（并可能重复使用密码）：

  • 密码管理器—用户可以使用的工具，用于为他们使用的每个应用程序生成和管理强密码。

  • 单点登录（SSO）—一种联合协议，允许用户使用一个帐户注册并登录其他服务。

• 服务器避免了解和存储其用户密码的一个解决方案是使用非对称密码认证密钥交换（非对称 PAKE）。非对称 PAKE（如 OPAQUE）允许用户使用密码对已知服务器进行身份验证，但无需实际向服务器透露密码。

• 避免密码的解决方案包括用户通过一次性密码（OTP）算法使用对称密钥或通过 FIDO2 等标准使用非对称密钥。

• 用户辅助认证协议通常在不安全的连接（WiFi，蓝牙，NFC）上进行，并帮助两个设备相互认证。为了在这些情景下保护连接，用户辅助协议假设两个参与者拥有一个额外的经过身份验证的（但不保密的）通道可供使用（例如，设备上的屏幕）。

• 将设备的公钥导出到另一个设备可以允许进行强相互认证的密钥交换。不幸的是，这些流程不够用户友好，有时由于设备限制（例如无法导出或导入密钥）而不可能。

• 对称密码认证密钥交换（对称 PAKEs）如 CPace 可以通过只需用户手动输入密码而无需导入长公钥来减轻用户的负担。例如，大多数人已经使用对称 PAKEs 来连接到他们的家庭 WiFi。

• 基于短身份验证字符串（SAS）的协议可以为无法导入密钥或密码但能够在密钥交换后显示短字符串的设备提供安全性。为了确保未经认证的密钥交换未被主动中间人攻击，这个短字符串必须在两个设备上相同。

第十二章：加密货币是指加密货币吗？

本章包括

• 共识协议及其如何使加密货币可能

• 不同类型的加密货币

• 比特币和 Diem 加密货币如何在实践中运作

密码学能否成为新金融系统的基础？这是自 2008 年以来加密货币一直在试图回答的问题，当时比特币是由中本聪提出的（至今仍未透露他或他们的身份）。在那之前，术语加密始终是用于指涉密码学领域。但自从比特币的创建以来，我看到它的含义迅速改变，现在也用于指代加密货币。加密货币爱好者反过来越来越有兴趣学习密码学。这是有道理的，因为密码学是加密货币的核心。

什么是加密货币？它有两个方面：

• *它是一种数字货币。*简单来说，它允许人们以电子方式交易货币。有时会使用由政府支持的货币（如美元），有时会使用虚拟货币（如比特币）。你很可能已经在使用数字货币——每当你在互联网上向某人汇款或使用支票账户时，你都在使用数字货币！事实上，你不再需要通过邮件寄送现金，今天大多数货币交易只是数据库中行的更新。

• 它是一种严重依赖密码学来避免使用信任第三方和提供透明度的货币。在加密货币中，没有必须盲目信任的中央权威，如政府或银行。我们经常将这种属性称为去中心化（就像“我们正在去中心化信任”）。因此，正如你将在本章中看到的那样，加密货币被设计为容忍一定数量的恶意行为者，并允许人们验证它们是否正常运作。

加密货币相对较新，因为第一个成功的实验是比特币，它是在 2008 年提出的，当时正值全球金融危机中。虽然危机始于美国，但很快就传播到世界其他地区，侵蚀了人们对金融体系的信任，并为比特币等更透明的倡议提供了平台。那时，许多人开始意识到金融交易的现状是低效、昂贵且大多数人不透明的。其余的就是历史，我相信这本书是第一本包含有关加密货币章节的密码学书籍。

12.1 一种温和的拜占庭容错（BFT）共识算法简介

想象一下，你想要创建一种新的数字货币。构建一个运作良好的系统实际上并不复杂。你可以在专用服务器上设置一个数据库，用于跟踪用户及其余额。通过这样做，你可以为人们提供一个界面，让他们查询余额或允许他们发送支付请求，这将在数据库中减少他们的余额并增加另一行中的余额。最初，你也可以随机将一些虚拟货币分配给你的朋友，以便他们可以开始向你的系统转账。但是这样一个简单的系统有一些缺陷。

12.1.1 弹性问题：分布式协议来拯救

我们刚刚看到的系统是一个单点故障。如果停电，你的用户将无法使用系统。更糟糕的是，如果某种自然灾害意外摧毁了你的服务器，每个人可能会永久丢失他们的余额。为了解决这个问题，存在着一些众所周知的技术，你可以用来为你的系统提供更强大的弹性。分布式系统领域研究了这些技术。

在这种情况下，大多数大型应用程序使用的常见解决方案是将数据库内容（在某种程度上）实时地复制到其他备份服务器上。这些服务器可以分布在各个地理位置，随时准备作为备份使用，甚至在主服务器故障时接管。这被称为高可用性。现在你拥有了分布式数据库。

对于服务大量查询的大型系统，备份数据库通常不仅仅是闲置在一旁等待发挥作用，而是被用于提供状态读取。很难让超过一个数据库接受写入和更新，因为这样可能会引发冲突（就像两个人同时编辑同一份文件一样危险）。因此，你通常希望一个数据库充当领导者，并对所有写入和更新操作进行排序，而其他数据库则用于读取状态。

数据库内容的复制可能会很慢，预计你的一些数据库会落后于主数据库，直到它们追赶上去。这在使用复制数据库读取状态时尤其如此。（想象一下，你和你的朋友查询不同的服务器，因此看到了不同的账户余额。）

在这些情况下，应用程序通常被编写以容忍这种滞后。这被称为最终一致性，因为最终数据库的状态会变得一致。（存在更强的一致性模型，但它们通常速度较慢且不切实际。）这样的系统也存在其他问题：如果主数据库崩溃，哪个数据库将成为主数据库？另一个问题是，如果备份数据库在主数据库崩溃时落后，我们会丢失一些最新的更改吗？

这就是在需要整个系统就某个决定达成一致意见时，更强大的算法—共识算法（也称为日志复制、状态机复制或原子广播）—发挥作用的地方。想象一下，一个共识算法解决了一群人试图就要点什么披萨达成一致意见的问题。如果每个人都在同一个房间里，很容易看出大多数人想要什么。但如果每个人都通过网络进行通信，消息可能会延迟、丢失、被拦截和修改，那么就需要一个更复杂的协议。

让我们看看共识如何用来回答前两个问题。在崩溃的情况下哪个数据库可以接管的第一个问题被称为领导者选举，通常使用共识算法来确定哪个将成为下一个领导者。第二个问题通常通过将数据库更改视为两个不同步骤来解决：待定和已提交。对数据库状态的更改始终首先是待定的，只有足够多的数据库同意提交它才能被设置为已提交（这也是共识协议可以使用的地方）。一旦提交，对状态的更新不容易丢失，因为大多数参与的数据库已经提交了更改。

一些知名的共识算法包括 Paxos（由 Lamport 于 1989 年发表）及其后续简化版本 Raft（由 Ongaro 和 Ousterhout 于 2013 年发表）。您可以在大多数分布式数据库系统中使用这些算法来解决不同的问题。（要了解关于 Raft 的出色互动解释，请查看thesecretlivesofdata.com/raft。）

12.1.2 信任的问题？分权有助于解决

分布式系统（从操作角度）为那些充当单点故障的系统提供了一个弹性的替代方案。大多数分布式数据库系统使用的共识算法不够容错。一旦机器开始崩溃，或由于硬件故障而开始表现不良，或开始与某些其他机器断开连接，比如网络分区，问题就会出现。此外，从用户角度来看，没有办法检测到这一点，如果服务器被入侵，这就更成问题了。

如果我向服务器查询，它告诉我 Alice 的账户里有 50 亿美元，我只能相信它。如果服务器在响应中包含了自她账户开户以来所收到和发送的所有货币转账，并将它们全部加起来，我可以验证她账户中确实有 50 亿美元是正确的。但是谁能保证服务器没有对我撒谎呢？也许当 Bob 询问另一个服务器时，它返回的是完全不同的余额和/或 Alice 账户的历史记录。我们称之为分叉（以两种相互矛盾的状态呈现为有效），这是历史中不应该发生的一个分支。因此，你可以想象，其中一个复制的数据库的妥协可能会导致相当严重的后果。

在第九章中，我提到了证书透明性，这是一种旨在检测 Web 公钥基础设施（PKI）中这种分叉的八卦协议。金钱的问题在于仅仅检测是不够的。你希望首先防止分叉发生！1982 年，Paxos 共识算法的作者 Lamport 提出了拜占庭容错（BFT）共识算法的概念。

我们想象拜占庭军队的几个师分驻扎在一座敌方城市外面，每个师分都由自己的将军指挥。将军们只能通过信使相互通信。观察敌人之后，他们必须决定一个共同的行动计划。然而，一些将军可能是叛徒，试图阻止忠诚的将军达成一致意见。

——Lamport 等人（《拜占庭将军问题》，1982 年）

Lamport 通过他的拜占庭类比开启了 BFT 共识算法领域，旨在防止不良共识参与者在达成决策时对系统产生不同的冲突观点。这些 BFT 共识算法高度类似于之前的共识算法，如 Paxos 和 Raft，只是复制的数据库（协议参与者）不再盲目地相互信任了。BFT 协议通常大量使用密码学来验证消息和决策的真实性，而这反过来可以被其他人用来对共识协议输出的决策进行密码学验证。

这些 BFT 共识协议因此解决了我们的韧性和信任问题。不同的复制数据库可以运行这些 BFT 算法，以便在新系统状态（例如用户余额）上达成一致，同时通过验证状态转换（用户之间的交易）是否有效，并获得大多数参与者的同意来相互监督。我们说信任现在是分散的。

第一个真实世界的 BFT 共识算法是 1999 年发表的实用 BFT（PBFT）。PBFT 是一种基于领导者的算法，类似于 Paxos 和 Raft，其中一个领导者负责提出提案，而其他人试图就提案达成一致。不幸的是，PBFT 相当复杂，缓慢，并且在超过十几个参与者后无法很好地扩展。如今，大多数现代加密货币使用更高效的 PBFT 变体。例如，Facebook 于 2019 年推出的加密货币 Diem 基于 HotStuff，这是一种受 PBFT 启发的协议。

12.1.3 规模问题：无许可和抗审查网络

这些基于 PBFT 的共识算法的一个局限性是它们都需要一个已知且固定的参与者集合。更为棘手的是，超过一定数量的参与者后，它们开始分崩离析：通信复杂性急剧增加，变得极其缓慢，选举领导者变得复杂等等。

加密货币如何决定共识参与者？有几种方式，但最常见的两种方式是

• 权威证明（PoA）—共识参与者事先确定。

• 权益证明（PoS）—共识参与者是动态选择的，基于谁拥有的权益最大（因此，更不愿意攻击协议）。一般来说，基于 PoS 的加密货币根据持有的数字货币数量选举参与者。

话虽如此，并非所有的共识协议都是经典的 BFT 共识协议。例如，比特币在提出一种没有已知参与者名单的共识机制时采取了不同的方法。这在当时是一个相当新颖的想法，比特币通过放宽经典 BFT 共识协议的约束来实现这一点。正如你将在本章后面看到的，由于这种方法，比特币可以分叉，这带来了自己的一系列挑战。

没有参与者，你如何选择领导者？您可以使用 PoS 系统（例如，Ouroboros 共识协议就是这样做的）。相反，比特币的共识依赖于一种称为工作量证明（PoW）的概率机制。在比特币中，这意味着人们试图找到解决方案来成为参与者和领导者。正如你将在本章后面看到的，这个谜题是一个密码学谜题。

由于缺乏已知参与者，比特币被称为无许可网络。在无许可网络中，您无需额外权限即可参与共识；任何人都可以参与。这与有许可网络形成对比，后者有一个固定的参与者集合。我在图 12.1 中总结了一些这些新概念。

图 12.1 一个集中式网络可以被视为单点故障，而分布式和去中心化网络对一些服务器关闭或恶意行为具有弹性。在许可网络中，有一组已知和固定的主要参与者，而在无许可网络中，任何人都可以参与。

直到最近，人们还不知道如何将经典的 BFT 共识协议与允许任何人加入的无许可网络一起使用。如今，存在许多使用 PoS 动态选择参与者子集作为共识参与者的方法。其中最值得注意的是 2017 年发布的 Algorand，它根据持有的货币数量动态选择参与者和领导者。

比特币还声称对审查具有抵抗力，因为你无法预先知道谁将成为下一个领导者，因此无法阻止系统选举新领导者。在 PoS 系统中是否可能实现这一点尚不太清楚，因为在这种系统中更容易确定大量货币背后的身份。

我应该提到，并非所有的 BFT 共识协议都是基于领导者的。有些是无领导者的，它们不是通过选举领导者决定下一个状态转换的。相反，每个人都可以提出变更，共识协议帮助每个人就下一个状态达成一致。2019 年，Avalanche 推出了这样一种加密货币，允许任何人提出变更并参与共识。

最后，如果你认为共识对于去中心化支付系统是必要的，那也不完全正确。2018 年，Guerraoui、Kuznetsov、Monti、Pavlovic 和 Seredinschi 提出了“AT2: 异步可信转账”中的无共识协议。考虑到这一点，我在本章中不会讨论无共识协议，因为它们是相对较新的，尚未经过实战测试。在本章的其余部分，我将介绍两种不同的加密货币，以展示该领域的不同方面：

• 比特币—基于 PoW 的最流行的加密货币，于 2008 年推出。

• Diem—一种基于 BFT 共识协议的加密货币，由 Facebook 和一群其他公司在 2019 年宣布。

12.2 比特币是如何运作的？

2008 年 10 月 31 日，一位匿名研究人员以化名 Satoshi Nakamoto 发布了“比特币：一个点对点的电子现金系统”。直至今日，仍然不知道 Satoshi Nakamoto 是谁。不久之后，“他们”发布了比特币核心客户端，这是任何人都可以运行以加入和参与比特币网络的软件。比特币所需要的唯一一件事情就是足够多的用户运行相同的软件或至少相同的算法。第一个加密货币诞生了——比特币（或 BTC）。

比特币是一个真正的成功故事。这种加密货币已经运行了十多年（截至撰写本文时），并且已经允许来自世界各地的用户使用数字货币进行交易。2010 年，开发者拉斯洛·汉野奇（Laszlo Hanyecz）用 10,000 BTC 买了两块披萨。当我写下这些文字时（2021 年 2 月），BTC 几乎价值 57,000 美元。因此，我们已经可以得出结论，加密货币有时可能极度波动。

12.2.1 比特币如何处理用户余额和交易

让我们深入了解比特币的内部结构，首先看看比特币如何处理用户余额和交易。作为比特币的用户，您直接处理密码学。您不像在任何银行网站上一样有用户名和密码登录；相反，您有自己生成的椭圆曲线数字签名算法（ECDSA）密钥对。用户的余额只是与公钥关联的一定数量的 BTC，因此，要接收 BTC，您只需与他人共享您的公钥。

要使用您的 BTC，您需要使用您的私钥签署交易。交易基本上说明了您认为的内容，“我将 X BTC 发送到公钥 Y”，忽略了一些我稍后会解释的细节。

注意：在第七章中，我提到比特币使用带有 ECDSA 的 secp256k1 曲线。不要将此曲线与 NIST 的 P-256 曲线混淆，后者被称为 secp256r1。

您的资金安全直接与您的私钥安全性相关。而且，正如您所知，密钥管理很困难。在过去的十年中，加密货币中的密钥管理问题导致了价值数百万美元的密钥的意外丢失（或盗窃）。小心！

比特币存在不同类型的交易，实际上，在网络上看到的大多数交易都通过对其进行哈希来隐藏接收方的公钥。在这些情况下，公钥的哈希被称为帐户的地址。（例如，这是我的比特币地址：bc1q8y6p4x3rp32dz80etpyffh6764ray9842egchy。）地址有效地隐藏了帐户的实际公钥，直到帐户所有者决定花费 BTC（在这种情况下，需要揭示地址的预图，以便其他人可以验证签名）。这使地址的大小更短，并防止有人在某天破解 ECDSA 后检索您的私钥。

不同类型的交易存在是比特币的一个有趣细节。交易不仅仅是包含一些信息的有效载荷；它们实际上是用虚构和相当有限的指令集编写的简短脚本。当交易被处理时，必须执行脚本，然后生成的输出才能确定交易是否有效，以及如果有效，则需要采取哪些步骤来修改所有帐户的状态。

像以太坊这样的加密货币通过允许在执行交易时运行更复杂的程序（所谓的智能合约）将这个脚本思想推向了极限。这里有几件事情我没有触及到：

• 一个交易中包含什么？

• 交易执行意味着什么？谁来执行它？

我将在下一节解释第二项内容。现在，让我们看看一个交易中有什么。

比特币的一个特点是没有真正的账户余额数据库。相反，用户拥有的是可供支出的比特币“零钱”，称为未花费交易输出（UTXOs）。你可以将 UTXOs 的概念想象成一个大碗，对所有人可见，里面装满了只有它们的所有者才能花费的硬币。当一笔交易花费了一些硬币时，这些硬币就会从碗里消失，同时为同一交易的收款方产生新的硬币。这些新硬币就是交易中列出的输出。

要知道你账户里有多少比特币，你需要数一下分配给你地址的所有 UTXOs。换句话说，你需要数一下所有发给你但你尚未花费的钱。图 12.2 举例说明了 UTXOs 在交易中的使用方式。

图 12.2 交易 1 由 Alice 签名，将 1 BTC 转给 Bob。由于它使用了 5 BTC 的 UTXO，该交易还需要将找零发送回 Alice，并保留一些找零作为费用。交易 2 由 Bob 签名，合并了两个 UTXO 以将 2 BTC 转给 Felix。（请注意，实际中，费用要低得多。）

现在有一个先有鸡还是先有蛋的问题：第一个 UTXO 从哪里来？这个问题我将在下一节中回答。

12.2.2 在数字黄金时代挖掘比特币

你现在了解了比特币交易中的内容以及如何管理你的账户或查明某人的余额。但是实际上是谁跟踪所有这些交易的呢？答案是每个人！

实际上，使用比特币意味着每笔交易都必须公开共享并记录在历史中。比特币是一个只追加的分类帐——一本交易记录的书，每页都与上一页相连。我在这里要强调的是，只追加意味着你不能回去修改书中的某一页。还要注意的是，因为每笔交易都是公开的，你唯一能得到的匿名性只是可能很难弄清谁是谁（换句话说，实际上什么公钥与什么人联系在一起）。

任何人都可以通过下载比特币客户端并使用它下载整个历史来轻松检查自比特币创立以来发生的任何交易。通过这样做，你成为了网络的一部分，并且必须根据比特币客户端中编码的规则重新执行每个交易。当然，比特币的历史非常庞大：在撰写本文时，它大约是 300 GB，根据你的连接速度，可能需要几天的时间来下载整个比特币分类账。你可以通过使用一个为你做繁重工作的在线服务更轻松地检查交易（只要你信任在线服务）。我在图 12.3 中给出了这些所谓的区块链浏览器的一个例子。

图 12.3 我选择在blockchain.com上分析的一笔随机交易（mng.bz/n295）。该交易使用一个输入（约 1.976 BTC）并将其分成两个输出（约 0.009 BTC 和 1.967 BTC）。总输入金额与总输出金额之间的差额是交易费（不作为输出表示）。其他字段是使用比特币脚本语言编写的脚本，以便花费输入中的 UTXO 或使输出中的 UTXO 可花费。

比特币实际上只是自其创世以来已处理的所有交易的列表（我们称之为起源）直到现在。这应该让你思考：谁负责选择和排序交易在这个分类账中？

为了就交易的排序达成一致，比特币允许任何人（甚至是你）提出要包含在下一个分类账页面中的交易列表。包含交易列表的这个提案在比特币的术语中被称为一个块。但是，让任何人提出一个块是灾难的预兆，因为比特币中有很多参与者。相反，我们希望只有一个人提出下一个交易块的提案。为了做到这一点，比特币让每个人都在一些概率谜题上工作，并且只允许第一个解决谜题的人提出他们的块。这就是我之前谈到的工作证明（PoW）机制。比特币的 PoW 是基于找到一个哈希值小于某个值的块。换句话说，块的哈希值必须具有以一些给定的零开始的二进制表示。

除了你想要包含的交易之外，块还必须包含上一个块的哈希值。因此，比特币分类账实际上是一系列块，其中每个块都指向前一个块，一直到第一个块，即创世块。这就是比特币所谓的区块链。区块链的美妙之处在于，对块的最轻微修改都会使链无效，因为块的哈希值也会改变，从而破坏下一个块对它的引用。

请注意，作为一个寻求提出下一个区块的参与者，你不需要对你的区块做太多更改来从中派生一个新的哈希。你可以首先固定它的大部分内容（包括其中的交易、它扩展的区块的哈希等），然后仅修改一个字段（称为区块的 nonce），以影响区块的哈希。你可以将这个字段视为一个计数器，递增其值直到找到符合游戏规则的摘要，或者你可以生成一个随机值。我在图 12.4 中阐述了区块链的这个概念。

图 12.4 在andersbrownworth.com/blockchain/blockchain上，人们可以与一个玩具区块链进行互动。每个区块都包含其父区块的摘要，每个区块都包含一个允许其摘要以四个 0 开头的随机 nonce。注意，对于顶部的区块链是如此，但是底部的区块链包含一个已经被修改的区块（编号为 2）（其数据最初为空）。由于修改改变了区块的摘要，所以它不再被后续区块认证。

所有这一切都是因为每个人都在运行相同的协议，使用相同的规则。当你与区块链同步时，你从其他节点下载每个区块，并验证：

• 对每个区块进行哈希确实会产生一个比某个预期值更小的摘要。

• 每个区块都指向历史中的前一个区块。

并非每个人都必须提出区块，但如果你愿意，你可以这样做。如果你这样做，你就被称为矿工。这意味着为了让你的交易进入区块链，你需要矿工的帮助（正如图 12.5 所示）。

图 12.5 比特币网络是许多节点（矿工或其他）相互连接的网络。要提交一个交易，你必须将其发送给一个能够将其放入区块链中的矿工（通过将其包含在一个区块中）。由于你不知道哪个矿工将成功地挖掘一个区块，你必须通过网络传播你的交易，以尽可能多地达到矿工。

矿工不是无偿工作的。如果一个矿工找到了一个区块，他们会收集：

• 奖励 —— 一定数量的比特币将被创建并发送到你的地址。一开始，每个挖掘的区块都会获得 50 个比特币。但是奖励值会在每挖掘 210,000 个区块时减半，并最终减少到 0，限制可以创建的比特币总量为 2100 万。

• 包含在区块中的所有交易费 ——这就是为什么在你的交易中增加费用可以让它们更快被接受，因为矿工倾向于在他们挖掘的区块中包含费用更高的交易。

这就是比特币用户被激励推动协议向前发展的方式。一个区块总是包含所谓的coinbase，即收集奖励和费用的地址。矿工通常将 coinbase 设置为他们自己的地址。

现在我们可以回答本节开头提出的问题：第一个 UTXO 是从哪里来的？答案是，历史上的所有比特币在某个时候都是作为矿工的区块奖励的一部分而创建的。

12.2.3 分叉地狱！解决挖矿中的冲突

比特币通过基于 PoW 的系统分配选择下一组要处理的交易的任务。你挖掘一个区块的机会与你能计算的哈希数量直接相关，因此，你可以产生的计算量。如今，很多计算能力都被用于在比特币或其他基于 PoW 的加密货币中挖矿。

注意：PoW 可以被视为比特币应对西比尔攻击的方式，这些攻击利用了你可以在协议中创建任意多个账户的事实，给不诚实的参与者带来了不对称的优势。在比特币中，获得更多算力的唯一途径实际上是购买更多硬件来计算哈希值，而不是在网络中创建更多地址。

然而，仍然存在一个问题：找到一个低于某个值的哈希的难度不能太低。如果太容易，那么网络中将有太多参与者同时挖掘一个有效的区块。如果发生这种情况，那么在链中哪个被挖掘的区块是合法的下一个区块呢？这本质上就是我们所说的分叉。

为了解决分叉问题，比特币有两种机制。第一种是保持 PoW 的难度。如果区块挖掘得太快或太慢，那么每个人都在运行的比特币算法会根据网络条件动态调整，并增加或减少 PoW 的难度。简单来说，矿工必须找到一个具有更多或更少零的区块摘要。

注意：如果难度要求区块摘要以 0 字节开头，你需要尝试 2⁸个不同的区块（更具体地说是不同的 nonce，如前面所述），直到找到有效的摘要。将这个数字提高到 2 字节，你现在需要尝试 2¹⁶个不同的区块。你达到这个目标所需的时间取决于你拥有的计算能力以及是否有专门的硬件来更快地计算这些哈希值。目前，比特币的算法会动态调整难度，以确保每 10 分钟挖出一个区块。

我们的第二个机制是确保每个人在发生分叉时都有相同的前进方式。为了做到这一点，规则是遵循工作量最大的链。2008 年的比特币白皮书指出，“最长的链不仅作为事件序列的证明，还证明它来自 CPU 算力最大的池”，规定参与者应该尊重他们认为是最长链的链。协议后来更新为遵循具有最高累积工作量的链，但在这里这个区别并不太重要。我在图 12.6 中进行了说明。

图 12.6 区块链中的分叉：两个矿工在高度 3 发布了一个有效区块（意味着创世区块之后的第 3 个区块）。后来，另一个矿工在高度 4 挖掘了一个指向高度 3 的第二个区块的区块。由于第二个分叉现在更长，这是矿工应该继续扩展的有效分叉。请注意，指向区块的箭头指向父区块（它们扩展的区块）。

我之前说过比特币的共识算法不是 BFT 协议。这是因为共识算法允许这样的分叉。因此，如果你正在等待你的交易被处理，绝对不应该仅仅依靠观察你的交易是否被包含在一个区块中！观察到的区块实际上可能是一个分叉，而且是一个失败的分叉（相对于更长的分叉）。

你需要更多的保证来决定你的交易是否已经真正被处理。大多数钱包和交易平台都等待一定数量的确认区块在你的区块之上被挖掘出来。在包含你的交易的那个区块之上挖掘出来的区块越多，链被重新组织成另一条链的机会就越小，因为已存在的分叉更长。

确认数通常设置为 6 个区块，这使得你的交易确认时间大约为一小时。话虽如此，比特币仍然不能提供 100% 的保证，即在 6 个区块之后不会发生分叉。如果挖矿难度调整得很好，那么应该没问题，我们有理由相信比特币是这样的。

随着加密货币变得越来越流行，比特币的 PoW 难度逐渐增加。难度现在已经非常高，大多数人无法负担得起所需的硬件来有机会挖掘一个区块。如今，大多数矿工会聚集在所谓的挖矿池中，以分配挖掘一个区块所需的工作。然后，他们分享奖励。

在区块 632874 [. . .] 中，比特币区块链的预期累积工作量超过了 2⁹² 次双 SHA256 哈希运算。

—Pieter Wuille (2020, mng.bz/aZNJ)

要理解分叉为何具有破坏性，让我们想象以下情景。Alice 从你这里购买了一瓶葡萄酒，而你一直在等待她将她账户中的 5 BTC 发送给你。最终，你观察到高度为 10 的新区块（意味着创世区块之后的第 10 个区块）包含了她的交易。谨慎起见，你决定等待再添加 6 个区块在其上。等待了一段时间后，你最终看到了高度为 16 的区块，延伸了包含你的高度为 10 的区块的链。你将葡萄酒送给了 Alice，并称其为一天结束。但这还不是故事的结束。

后来，高度为 30 的区块突然出现，延伸了一个刚在你的区块之前（高度为 9）分叉出来的不同区块链。由于新链更长，最终被所有人接受为合法链。你之前所在的链（从你的高度为 10 的区块开始）被丢弃，网络中的参与者简单地重新组织他们的链，指向新的最长链。正如你所猜测的，这个新链中没有包含爱丽丝的交易。相反，它包含一笔交易，将她所有的资金转移到另一个地址，阻止你重新发布将她的资金转移到你地址的原始交易。爱丽丝有效地双重花费了她的钱。

这就是51%攻击。这个名称来自爱丽丝执行攻击所需的计算能力的数量；她只需要比其他人多一点点。(crypto51.app有一张有趣的表格，列出了根据 PoW 在不同加密货币上执行 51%攻击的成本。)这不仅仅是一个理论上的攻击！51%攻击在现实世界中发生。例如，在 2018 年，一名攻击者成功地在 Vertcoin 货币上进行了 51%攻击，双重花费了一些资金。

攻击者实质上重写了账本的部分历史，然后利用他们的主导哈希算力生成最长链，说服其他矿工验证这个新版本的区块链。有了这个，他或她可以实施终极的加密犯罪：对先前交易进行双重花费，让先前的收款人持有无效的硬币。

—迈克尔·J·凯西（“Vertcoin 的困境是真实的：为什么最新的加密 51%攻击很重要”，2018）

在 2019 年，以太坊经典（以太坊的一个变种）发生了同样的事情，导致当时损失超过 100 万美元，出现了超过 100 个区块深度的多次重组。2020 年，比特币黄金（比特币的一个变种）也遭受了 51%攻击，从加密货币的历史中删除了 29 个区块，并在不到两天内双重花费了超过 7 万美元。

12.2.4 通过使用默克尔树来减小区块的大小

我想谈谈比特币的另一个有趣方面，即它如何压缩部分可用信息。比特币中的一个区块实际上不包含任何交易！交易是单独共享的，而一个区块包含一个认证一系列交易的单一摘要。该摘要可以简单地是区块中包含的所有交易的哈希值，但它比那更聪明。相反，该摘要是一个Merkle 树的根。

什么是默克尔树？简单来说，它是一个树（数据结构），其中内部节点是它们子节点的哈希值。这可能有点令人困惑，一幅图值千言，所以看看图 12.7。

图 12.7 梅克尔树，一种验证其叶子元素的数据结构。在树中，内部节点是其子节点的哈希值。根哈希可以用来验证整个结构。在图中，H()表示哈希函数，逗号分隔的输入可以实现为连接（只要没有歧义）。

梅克尔树是有用的结构，你会在各种实际协议中找到它们。它们可以将大量数据压缩为一个小的、固定大小的值——树的根。不仅如此，你不一定需要所有的叶子来重建根。

例如，想象一下，你知道梅克尔树的根是因为它包含在一个比特币区块中，你想知道一个交易（树中的一个叶子）是否包含在该区块中。如果它在树中，我可以与你分享路径上的相邻节点作为成员证明。（一种在树的深度上对数大小的证明。）你需要做的是通过对路径中的每一对进行哈希运算，计算出根节点的内部节点直到根节点。在文字上解释这个过程有点复杂，所以我在图 12.8 中用图示来说明这个证明。

图 12.8 知道梅克尔树的根，可以通过重构所有叶子的根哈希来验证一个叶子是否属于树。为此，你首先需要所有叶子，在我们的图中是 8 个摘要（假设叶子是某个对象的哈希）。如果你不需要所有其他叶子，还有一种更有效的方法来构建成员证明：你只需要路径中从叶子到根的相邻节点，这包括你的叶子在内的 4 个摘要。验证者可以使用这些相邻节点来计算路径上所有缺失节点的哈希，直到重建根哈希并查看它是否与他们期望的相匹配。

在一个区块中使用梅克尔树而不是直接列出所有交易的原因是为了减轻下载所需信息以执行对区块链的简单查询。例如，想象一下，你想要检查你最近的交易是否包含在一个区块中，而不必下载比特币区块链的整个历史记录。你可以做的是仅下载区块头，因为它们不包含交易而更轻，一旦你拥有了它，就可以询问一个节点告诉你哪个区块包含了你的交易。如果有这样的一个区块，他们应该能够提供一个证明，证明你的交易在你在区块头中拥有的摘要所认证的树中。

对于比特币还有很多要讲，但这本书的页数有限。因此，我将利用本章剩余的空间带你了解这个领域，并解释经典的 BFT 共识协议是如何工作的。

12.3 加密货币的概览

比特币是第一个成功的加密货币，尽管已经创建了数百种其他加密货币，但比特币仍然保持着最大市场份额和价值。有趣的是，比特币存在许多问题，其他加密货币已经尝试解决（有些成功）。更有趣的是，加密货币领域利用了许多直到现在都没有许多实际应用或甚至不存在的加密原语！所以，话不多说，以下部分列出了自比特币诞生以来已经研究的问题。

12.3.1 波动性

目前大多数人使用加密货币作为投机工具。比特币的价格显然有助于这个故事，因为它已经证明它可以在一天内轻松地上千美元地上下波动。有些人声称稳定性将随着时间的推移而来，但事实仍然是，比特币现在不能用作货币。其他加密货币已经尝试使用稳定币的概念，将其代币的价格与现有的法定货币（如美元）挂钩。

12.3.2 延迟

您可以通过许多方式来衡量加密货币的效率。加密货币的吞吐量是它可以处理的每秒交易数量。例如，比特币的吞吐量相当低，每秒只有 7 笔交易。另一方面，确定性是一旦您的交易被包含在区块链中就被视为已确定的时间。由于分叉，比特币的确定性永远无法完全实现。被认为是在交易被包含在新区块中的至少一小时后，交易被撤销的概率变得可接受。这两个数字都极大地影响了延迟，延迟是从用户的角度来看，交易被最终确认所需的时间。在比特币中，延迟包括交易的创建，将其传播到网络的时间，将其包含在区块中的时间，最后是等待区块确认的时间。

这些速度问题的解决方案可以通过 BFT 协议解决，这些协议通常提供仅需几秒钟即可完成的确定性，并保证不会发生分叉，并且每秒可处理数千笔交易。然而，有时这仍然不够，正在探索不同的技术。所谓的第二层协议尝试提供额外的解决方案，可以在链下更快地进行支付，并周期性地将进度保存在主区块链上（与第一层相比称为层 1）。

12.3.3 区块链大小

比特币和其他加密货币的另一个常见问题是区块链的大小可能迅速增长到不切实际的大小。当用户想要使用加密货币（例如查询其账户余额）时，会出现可用性问题，因为他们预期必须首先下载整个链才能与网络交互。处理大量交易每秒的基于 BFT 的加密货币预计将在几个月甚至几周内轻松达到几 TB 的数据。存在几种解决方案。

其中最有趣的之一是 Mina，它不需要您下载整个区块链的历史记录才能到达最新状态。相反，Mina 使用零知识证明（ZKPs），在第七章中提到，我将在第十五章中更深入地介绍，将所有历史记录压缩成固定大小的 11 KB 证明。这对于像手机这样的轻客户端特别有用，通常必须信任第三方服务器才能查询区块链。

12.3.4 保密性

比特币提供了伪匿名性，因为账户仅与公钥相关联。只要没有人能将公钥与个人联系起来，相关账户就保持匿名。请记住，与该账户有关的所有交易都是公开的，社交图仍然可以创建，以了解谁倾向于与谁更频繁地交易，以及谁拥有多少货币。

有许多加密货币尝试使用 ZKPs 或其他技术来解决这些问题。Zcash是最知名的保密加密货币之一，因为其交易可以加密发送者地址、接收者地址和交易金额。所有这些都使用 ZKPs！

12.3.5 能源效率

比特币因为在电力消耗方面过于庞大而受到了严厉批评。事实上，剑桥大学最近评估，挖掘比特币所花费的所有能源使比特币成为世界前 30 大能源使用国（如果视为一个国家），在一年内消耗的能源比阿根廷还多（2021 年 2 月；cbeci.org/）。另一方面，BFT 协议不依赖于 PoW，因此避免了这种沉重的开销。这无疑是为什么任何现代加密货币似乎都避免基于 PoW 的共识，甚至像以太坊这样重要的 PoW-based 加密货币也宣布计划转向更环保的共识协议。在进入下一章之前，让我们看看基于 BFT 共识协议的这些加密货币。

12.4 DiemBFT：拜占庭容错（BFT）共识协议

许多现代加密货币已经放弃了比特币的 PoW 方面，转而采用更环保和更高效的共识协议。这些共识协议大多基于经典的 BFT 共识协议，这些协议大多是原始 PBFT 协议的变体。在本节中，我将使用 Diem 来说明这种 BFT 协议。

Diem（之前称为 Libra）是一种数字货币，最初由 Facebook 在 2019 年宣布，由 Diem 协会管理，该协会是由公司、大学和非营利组织组成，旨在推动开放和全球支付网络。Diem 的一个特点是它由真实货币支持，使用法定货币储备。这使得数字货币稳定，不像它的老表兄比特币。为了以安全和开放的方式运行支付网络，使用了一种 BFT 共识协议称为 DiemBFT，这是 HotStuff 的一个变种。在本节中，让我们看看 DiemBFT 是如何工作的。

12.4.1 安全性和活性：BFT 共识协议的两个属性

BFT 共识协议旨在在容忍一定比例的恶意参与者的情况下实现两个属性。这些属性包括

• 安全性—不会达成矛盾的状态，意味着不应该发生分叉（或以极小的概率发生）。

• 活性—当人们提交交易时，状态最终会处理它们。换句话说，没有人可以阻止协议完成其任务。

请注意，如果参与者不按照协议行事，则通常被视为恶意（也称为 拜占庭）。这可能意味着他们什么也不做，或者他们没有按照正确顺序执行协议的步骤，或者他们没有遵守一些旨在确保没有分叉的强制性规则，等等。

BFT 共识协议通常很容易实现安全性，而活性则被认为更加困难。事实上，1985 年由 Fischer、Lync 和 Paterson 提出的著名不可能结果（“一个故障进程下的分布式共识不可能性”）与 BFT 协议相关，指出在 异步 网络（消息可以花费任意时间到达）中，没有 确定性 共识协议能够容忍故障。大多数 BFT 协议通过将网络视为某种程度上的 同步（事实上，如果你的网络长时间宕机，任何协议都是无用的）或者在算法中引入随机性来避免这一不可能结果。

出于这个原因，即使在极端网络条件下，DiemBFT 也永远不会分叉。此外，即使存在网络分区，即网络的不同部分无法到达其他部分，只要网络最终恢复和稳定足够长的时间，它总是会取得进展。

12.4.2 DiemBFT 协议中的一轮

Diem 在一个预先知道参与者（称为 验证者）的许可设置中运行。协议在严格递增的轮次（第 1 轮、第 2 轮、第 3 轮等）中前进，在此期间验证者轮流提出交易块。在每一轮中

1. 被选择为领导者（确定性地）的验证者收集一定数量的交易，将它们组合成一个新的区块，延伸区块链，然后对区块进行签名并将其发送给所有其他验证者。

2. 在收到建议的区块后，其他验证者可以通过签名并将签名发送给下一轮的领导者来对其进行认证。

3. 如果下一轮的领导者收到足够多的选票支持该区块，他们可以将所有这些选票捆绑在一个称为quorum certificate（QC）的证书中，该证书证明了该区块，并使用该 QC 提出一个新的区块（在下一轮中）来延伸现在已经被认证的区块。

另一种看待这个问题的方式是，在比特币中，一个区块只包含它所延伸的区块的哈希值，而在 DiemBFT 中，一个区块还包含对该哈希值的一定数量的签名。（签名的数量很重要，但稍后再详细说明。）

请注意，如果验证者在一轮中没有看到建议（例如，因为领导者离线了），他们可以超时并警告其他验证者没有发生任何事情。在这种情况下，将触发下一轮，提议者可以延伸他们已看到的最高认证区块。我在图 12.9 中总结了这一点。

图 12.9 DiemBFT 的每一轮都是由指定的领导者提出延伸他们所见到的最后一个区块的区块开始的。其他验证者随后可以对该区块进行投票，将他们的投票发送给下一轮的领导者。如果下一轮的领导者收集到足够的选票以形成一个 quorum certificate（QC），他们可以提出一个包含 QC 的新区块，有效地延伸之前看到的区块。

12.4.3 协议能容忍多少不诚实行为？

假设我们希望在最多容忍f个恶意验证者的情况下（即使他们全部串通作恶），那么 DiemBFT 规定协议需要至少有 3f + 1 个验证者参与（换句话说，对于f个恶意验证者，至少需要有 2f + 1 个诚实验证者）。只要这个假设成立，该协议就能提供安全性和活力。

有了这个前提，只有获得大多数诚实验证者的投票才能形成 QC，即使有 3f + 1 个参与者，这也需要 2f + 1 个签名。这些数字可能有点难以想象，因此我展示了它们对我们观察到的投票信心的影响，见图 12.10。

图 12.10 在 DiemBFT 协议中，至少有三分之二的验证者必须是诚实的，协议才能安全（不会分叉）和活跃（会取得进展）。换句话说，只要有 2f + 1 个验证者是诚实的，该协议就能容忍f个不诚实的验证者。一个已认证的区块至少收到了 2f + 1 个投票，因为这是能够代表大多数诚实验证者的最低投票数。

12.4.4 DiemBFT 投票规则

验证者必须始终遵循两个投票规则，否则将被视为拜占庭式的：

1. 他们不能在过去投票（例如，如果你刚刚在第 3 轮投票，你只能在第 4 轮及以上投票）。

2. 他们只能为延伸到他们首选轮次或更高轮次的区块投票。

什么是首选轮次？默认情况下是 0，但如果你为一个延伸到一个延伸到一个区块的区块投票（我的意思是你为一个有祖父区块的区块投票），那么那个祖父区块的轮次就成为你的首选轮次，除非你之前的首选轮次更高。复杂吗？我知道，这就是为什么我制作了图 12.11。

图 12.11 在为一个区块投票后，验证者将他们的首选轮次设置为祖父区块的轮次，如果它高于他们当前的首选轮次。要为一个区块投票，其父区块的轮次必须大于或等于首选轮次。

12.4.5 交易何时被视为最终确定？

请注意，已认证的区块尚未最终确定，或者我们也可以说是已提交。没有人应该假设包含在待处理区块中的交易不会被撤销。只有当提交规则被触发时，区块和其中包含的交易才能被视为最终确定。提交规则（在图 12.12 中说明）表示，如果：

• 区块开始了一个由 3 个在连续轮次（例如，在第 1、2 和 3 轮）中提出的区块组成的链。

• 这个 3 个区块链的最后一个区块被认证。

图 12.12 三个连续轮次（3、4、5）恰好有一条链由认证的区块组成。观察到第 5 轮的最后一个区块被第 9 轮的 QC 认证的任何验证者可以提交第 3 轮的链的第一个区块，以及其所有祖先（这里是第 1 轮的区块）。任何相矛盾的分支（例如第 2 轮的区块）都会被丢弃。

这就是协议的高层次内容。但是，当然，细节才是关键。

12.4.6 DiemBFT 安全性背后的直觉

虽然我鼓励你阅读 DiemBFT 论文中的一页安全性证明，但我想在这里用几页来让你直观地理解它为什么有效。首先，我们注意到在同一轮中不能认证两个不同的区块。这是一个重要的特性，我在图 12.13 中用视觉方式解释。

图 12.13 假设在一个由 3f + 1 个验证者组成的协议中只能有最多f个恶意验证者，并且一个法定证书是由 2f + 1 个签名投票创建的，那么每轮只能有一个经过认证的区块。图中展示了一个反证法，证明这是不可能的，因为那样会与我们最初的假设相矛盾。

利用只有一个区块可以在给定轮次获得认证的属性，我们可以简化我们讨论区块的方式：区块 3 在第 3 轮，区块 6 在第 6 轮，依此类推。现在，看一下图 12.14，并花点时间弄清楚为什么一个经过认证的区块，或两个经过认证的区块，或三个非连续轮次的经过认证的区块不能在不冒风险的情况下导致提交。

图 12.14 在所有这些场景中，提交区块 5 可能导致分叉。只有在第 4 个场景中提交区块 5 是安全的。你能告诉为什么在所有场景中除了第 4 个场景提交区块 5 是危险的吗？

你能找出所有场景的答案吗？简短的答案是，除了最后一个场景外，所有场景都留有一个区块可以延伸到第 1 轮。这个晚到的区块实际上会分叉并根据共识协议的规则进一步延伸。如果发生这种情况，区块 5 和其他延伸它的区块将被丢弃，因为另一个更早的分支被提交。对于场景 1 和 2，这可能是由于提议者没有看到之前的区块。在场景 3 中，一个更早的区块可能出现得比预期晚，可能是由于网络延迟，或者更糟糕的是，由于验证者在合适的时机才公布它。我在图 12.15 中进一步解释这一点。

图 12.15 在图 12.14 的基础上，除了最后一个场景外，所有场景都允许一个可以最终获胜并丢弃区块 5 分支的并行链。最后一个场景有一个由三个连续轮次的经过认证的区块组成的链。这意味着区块 7 有大多数诚实选民，他们反过来更新了他们的首选轮次到第 5 轮。之后，没有区块可以在区块 5 之前分叉并同时获得 QC。最糟糕的情况是一个区块延伸区块 5 或区块 6，这最终会导致相同的结果—区块 5 被提交。

摘要

• 加密货币是关于去中心化支付网络，以避免单点故障。

• 为了让每个人对加密货币的状态达成一致，我们可以使用共识算法。

• 拜占庭容错（BFT）共识协议于 1982 年发明，并已发展成为更快速和更简单易懂的形式。

• BFT 共识协议需要一个已知且固定的参与者集合（许可网络）。这样的协议可以决定谁是这个参与者集合的一部分（权威证明或 PoA），或者根据他们持有的货币数量动态选举参与者集合（权益证明或 PoS）。

• 比特币的共识算法（中本聪共识）使用工作量证明（PoW）来验证正确的链并允许任何人参与（无许可网络）。

• 比特币的 PoW 让参与者（称为矿工）计算大量哈希以找到具有特定前缀的哈希。成功找到有效摘要允许矿工决定下一个交易区块并收取奖励以及交易费。

• 比特币中的账户只是使用 secp256k1 曲线的 ECDSA 密钥对。用户可以通过查看尚未花费的所有交易输出（UTXO）知道他们的账户持有多少比特币。因此，交易是一条已签名的消息，授权将一定数量的旧交易输出移动到新输出，可以花费给不同的公钥。

• 比特币使用默克尔树来压缩区块的大小，并允许交易包含验证的大小较小。

• 稳定币是一种加密货币，试图通过将其代币与美元等法定货币的价值挂钩来稳定其价值。

• 加密货币使用所谓的第二层协议，以减少其延迟，通过在链下处理交易并周期性地保存进度在链上。

• 零知识证明（ZKPs）在许多不同的区块链应用中使用（例如，在 Zcash 中提供保密性，在 Coda 中将整个区块链压缩为短的有效性证明）。

• Diem 是一种稳定币，它使用称为 DiemBFT 的 BFT 共识协议。只要 3f + 1 参与者中不超过 f 个恶意参与者存在，它就保持安全（没有分叉）和活跃（总是取得进展）。

• DiemBFT 通过在轮次中让参与者提议延伸先前区块的交易的区块来运作。其他参与者随后可以为该区块投票，如果收集到足够的票数（2f + 1），可能会创建一个法定证书（QC）。

• 在 DiemBFT 中，当触发提交规则（一系列连续轮次的 3 个已认证区块）时，区块及其交易将被最终确定。发生这种情况时，链的第一个区块及其延伸的区块将被提交。

第十三章：硬件加密

本章内容包括

• 高度对抗性环境中的密码学问题

• 增加攻击者成本的硬件解决方案

• 侧信道攻击和软件缓解措施

密码学原语和协议经常被描述为孤立的构建模块，仿佛它们在远离任何对手的星系中运行。实际上，这是一个不切实际的假设，经常被证明是错误的。在现实世界中，密码学在各种环境中运行，并受到各种威胁的影响。在本章中，我们将研究更极端的场景——高度对抗性环境——以及您在这些情况下可以采取的措施以保护您的密钥和数据。（剧透警告：这涉及使用专门的硬件。）

13.1 现代密码学攻击模型

当今的计算机和网络安全始于这样一个假设，即存在一个我们可以信任的域。例如：如果我们为了在互联网上传输数据而加密数据，我们通常假设进行加密的计算机没有被损害，并且存在一些其他的“终点”，可以在那里安全地解密它。

— Joanna Rutkowska（《Intel x86 可恶之处》，2015）

密码学曾经是关于“爱丽丝想要将消息加密发送给鲍勃，而不让伊娃能够截获它”。如今，它的大部分内容已经转移到了更类似于“爱丽丝想要将消息加密发送给鲍勃，但爱丽丝已经受到了损害。”这是一个完全不同的攻击者模型，通常在理论密码学中没有被预料到。我这是什么意思？让我给你一些例子：

• 在可能装有读取器假面（skimmer）的自动取款机（ATM）上使用信用卡。读取器假面是窃贼可以放置在读卡器顶部的设备，用于复制您银行卡的内容（见图 13.1）

• 在您的手机上下载一个破坏操作系统（OS）的应用程序

• 在共享网络托管服务中托管网站，另一个恶意客户可能与您共用同一台机器

• 在被来自不同国家间谍访问的数据中心中管理高度敏感的机密

图 13.1 读取器假面，一种恶意设备，可放置在 ATM 或付款终端的读卡器前，以复制磁条中的数据。磁条通常包含账号、到期日期和其他元数据，您用于在线支付或在许多付款终端上支付。假面有时伴随着隐藏摄像头一起使用，以获取您的个人识别码（PIN），从而潜在地使窃贼能够进行取款和要求输入 PIN 的付款终端。

所有这些示例都是在许多密码学家忽视或完全不了解的威胁模型中对密码学的现代应用。事实上，您在文献中读到的大多数密码学原语都假设例如，艾丽丝完全控制她的执行环境，只有当密文（或签名或公钥或……）离开她的计算机进入网络时，中间人攻击者才能执行他们的技巧。但是，在现实和现代，我们经常在更具对抗性的模型中使用密码学。

警告 安全性毕竟是您的假设和对潜在攻击者的期望的产物。如果您的假设是错误的，那么您将度过糟糕的时光。

现实世界中的应用如何将理论加密与这些更强大的攻击者相协调？它们做出妥协。换句话说，他们试图让攻击者的生活更加困难。这些系统的安全性通常是以成本（攻击者需要花费多少来破解系统？）而不是计算复杂性来计算的。

在本章中，您将学到很多不完美的加密技术，这在现实世界中我们称之为深度防御。有很多东西需要学习，这一章带来了许多新的缩略词和不同的解决方案，不同的供应商以及他们的营销团队和销售人员提出了。所以让我们开始学习在不受信任的环境中的可信系统。

13.2 不受信任的环境：硬件拯救

实践中攻击系统有不同的方法。将它们归类的一种方式是这样思考：

• 软件攻击—利用在您设备上运行的代码的攻击。

• 硬件攻击—需要攻击者物理接近您的设备的攻击方式。

在之前的章节中，我已经反复讨论了针对加密的软件攻击以及如何减轻它们的影响，但是如果利用硬件解决方案，有些软件攻击会更容易防御。例如，通过在连接到您计算机的独立设备上生成和使用加密密钥，一个感染您计算机的病毒将无法提取密钥。

然而，硬件攻击更加棘手，因为获得设备访问权限的攻击者几乎可以为所欲为：磁盘上的数据可以任意修改，激光可以瞄准特定位置以迫使计算产生错误值（所谓的故障攻击），芯片可以打开以显示其部件，聚焦离子束（FIB）显微镜可用于逆向工程组件等等。天空是极限，保护免受这种有动机的攻击者是很困难的。通常，可用的不同解决方案归结为尽可能添加更多层次的防御以使攻击者的生活更加困难。这一切都是关于提高成本！

恶意女佣攻击

并非所有的硬件攻击者都是一样的。例如，有些攻击者可以花费一些时间与您的设备相处，而其他人可能只有有限的时间。想象一下以下情景：您把手机或笔记本电脑放在酒店房间里不管，一个“恶意”的女佣进来，打开设备，使用低成本的现成工具修改系统，然后离开设备看起来未经触碰就回到您的房间之前的地方。在文献中，这被称为恶毒女佣攻击，并且可以推广到许多情况（例如，携带设备在飞行时的托运行李中，将敏感密钥存储在不安全的数据中心中等）。

当然，并非所有系统都必须防范最强大的硬件攻击，也不是所有应用程序都面对相同级别的威胁。不同的硬件解决方案适用于不同的情境，因此本节剩余内容是关于理解“这样那样”的区别。

13.2.1 白盒密码学，一个糟糕的想法

在涉及不受信任环境的硬件解决方案之前，为什么不使用软件解决方案呢？密码学能否提供不泄露自己密钥的原语？

白盒密码学正是这样：密码学的一个领域，试图将其使用的密钥与加密实现混合在一起。目标是防止观察者从中提取密钥。攻击者获取了某个带有固定密钥的白盒 AES 实现的源代码，它可以很好地加密和解密，但是密钥与实现混合得太好了，以至于任何人都很难从算法中提取它。这至少是理论上的。在实践中，尚未发现任何已发布的白盒密码算法是安全的，大多数商业解决方案由于这个原因是闭源的。

注意安全通过模糊和混淆（将代码混淆以使其看起来难以理解）是一种通常不受欢迎的技术，因为它们尚未被证明有效。尽管如此，在现实世界中，这些技术有时会有用，并且可以用来延迟和挫败对手。

总的来说，白盒密码学是一个大行业，向需要数字版权管理（DRM）解决方案的企业销售可疑的产品（控制客户对其购买的产品的访问权限的工具）。例如，您可以在播放您在商店购买的电影的硬件中找到这些白盒解决方案，或者在您正在观看的流媒体服务中播放电影的软件中找到这些解决方案。实际上，DRM 并不能强力阻止这些攻击；它只是让他们的客户的生活变得更加困难。更严肃的是，有一个称为不可区分混淆（iO）的密码学分支试图在密码学上实现这一点。iO 是一个理论上的、不切实际的、到目前为止还没有真正被证明的研究领域。我们将看看这个领域的发展如何，但我不会抱太大希望。

13.2.2 它们在你的钱包里：智能卡和安全元素

白盒密码学并不是很好，但这几乎是对抗强大对手的最佳软件解决方案。因此，让我们转向硬件方面寻找解决方案。（剧透警告：事情即将变得更加复杂和令人困惑。）如果您认为现实世界的密码学很混乱，有太多的标准或做同样事情的方法，那么等到您了解硬件世界正在发生的事情时，您会感到更加惊讶。不同的术语已经被创造并以不同的方式使用，标准不幸地像密码学标准一样多样化（如果不是更多）。

要了解所有这些硬件解决方案以及它们之间的区别，让我们从一些必要的历史开始。智能卡是通常包装在塑料卡（如银行卡）内的小芯片，于 20 世纪 70 年代初在微电子技术的进步之后发明。智能卡最初是让每个人都有一个口袋计算机的实用方式！事实上，现代智能卡嵌入了自己的 CPU、不同类型的可编程或不可编程存储器（ROM、RAM 和 EEPROM）、输入和输出、硬件随机数生成器（也称为 TRNG，正如你在第八章中学到的），等等。

他们在“智能”方面是指它们可以运行程序，不像以前的不那么智能的卡片只能通过磁条存储数据，这些数据可以很容易通过我之前提到的偷取器复制。大多数智能卡允许开发人员编写可以在卡上运行的小型、独立的应用程序。智能卡支持的最流行的标准是JavaCard，它允许开发人员编写类似于 Java 的应用程序。

要使用智能卡，您首先需要通过将其插入读卡器来激活它。最近，卡片已经通过近场通信（NFC）协议进行了增强，以通过无线电频率实现相同的结果。这使您可以通过靠近读卡器来使用卡片，而不是物理接触。

银行和传统密码学

顺便说一句，银行利用智能卡存储每张卡的唯一卡密，能够表明：“我确实是您给这位客户的卡。”直觉上，您可能认为这是通过公钥加密实现的，但银行业仍然停留在过去，使用对称加密（由于仍在使用的大量传统软件和硬件）！

更具体地说，大多数银行卡存储着一个三重 DES（3DES）对称密钥，这是一个旧的 64 位分组密码，旨在使不安全的数据加密标准（DES）安全。该算法用于生成 MAC（消息认证码）而不是加密，用于对某些挑战生成 MAC。持有每位客户当前 3DES 对称密钥的银行可以验证 MAC。这是现实世界加密通常涉及的一个绝佳例子：在许多地方以一种危险的方式使用的传统算法。（这也是为什么密钥轮换是一个如此重要的概念，以及为什么你必须定期更换银行卡。）

智能卡结合了许多物理和逻辑技术，以防止其执行环境和存储秘密的部分的观察、提取和修改。存在许多试图破解这些卡片和硬件设备的攻击。这些攻击可以分为三种不同的类别：

• 非侵入式攻击—不会影响目标设备的攻击。例如，差分功耗分析（DPA）攻击评估智能卡在执行加密操作时的功耗，以提取其密钥。

• 半侵入式攻击—利用对芯片表面的访问以非破坏性方式进行攻击以实施利用。例如，差分故障分析（DFA）攻击利用热量、激光等技术修改智能卡上运行的程序的执行，以泄露密钥。

• 侵入式攻击—打开芯片以探测或修改硅片电路，以改变芯片的功能并揭示其秘密的攻击。这些攻击是显著的，因为它们可能损坏设备，并且有更大的可能性使设备无法使用。

硬件芯片非常小且紧密封装的事实可能使攻击变得困难。但专门的硬件通常通过使用不同层次的材料防止解封和物理观察，并使用硬件技术增加已知攻击的不准确性而进一步防范。

智能卡迅速变得非常流行，很快就变得明显，将这样一个安全的黑匣子放入其他设备中可能是有用的。一个安全元件的概念诞生了：一个防篡改的微控制器，可以以可插拔的形式找到（例如，您手机中用于访问运营商网络所需的 SIM 卡）或直接粘贴在芯片和主板上（例如，连接到 iPhone NFC 芯片进行支付的嵌入式安全元件）。安全元件实际上只是一个小型、独立的硬件部件，旨在保护您的机密信息及其在加密操作中的使用。

安全元件是保护物联网（IoT）中的加密操作的重要概念，这是一个口头上的（并且有点过载的）术语，指的是可以与其他设备通信的设备（比如信用卡、手机、生物识别护照、车库钥匙、智能家居传感器等等）。您可以将本节中的所有解决方案视为以不同形式实现的安全元素，使用不同的技术来实现几乎相同的功能，但提供不同级别的安全性和速度。

关于安全元素的主要定义和标准是由 Global Platform 制定的，这是一个由行业内不同参与者的需求而创建的非营利性协会，旨在促进不同供应商和系统之间的互操作性。还有更多关于安全元素的安全声明的标准和认证，来自 Common Criteria（CC）、NIST 或 EMV（欧洲支付、万事达卡和 Visa）等标准机构。

由于安全元素是高度保密的配方，将它们集成到您的产品中意味着您将不得不签署保密协议并使用闭源硬件和固件。对于许多项目来说，这被视为透明度的严重限制，但可以理解，因为这些芯片的安全性部分来自于其设计的模糊性。

13.2.3 银行喜欢它们：硬件安全模块（HSM）

如果你了解什么是安全元件，那么硬件安全模块（HSM）基本上就是一个更大更快的安全元件，而且像一些安全元件一样，一些 HSM 也可以运行任意代码。然而，这并不总是正确的。一些 HSM 很小（比如 YubiHSM，一个微型 USB dongle，类似于 YubiKey），而术语硬件安全模块可能会因人而异地被用来表示不同的事物。

许多人会认为到目前为止讨论的所有硬件解决方案都是不同形式的 HSM，并且安全元素只是由 GlobalPlatform 指定的 HSM，而 TPM（可信平台模块）是由 Trusted Computing Group 指定的 HSM。但大多数时候，当人们谈论 HSM 时，他们指的是大型设备。

HSM 经常根据 FIPS 140-2 进行分类，“加密模块的安全要求”。该文档相当古老，于 2001 年出版，自然而然地，并未考虑在其出版后发现的许多攻击。幸运的是，在 2019 年，它被更现代的版本 FIPS 140-3 所取代。FIPS 140-3 现在依赖于两个国际标准：

• ISO/IEC 19790:2012—为硬件安全模块定义了四个安全等级。一级 HSM 不提供任何防御措施（你可以将其视为纯软件实现），而三级 HSM 如果检测到任何入侵，就会擦除其秘密！

• ISO 24759:2017—定义了 HSM 必须如何测试以标准化 HSM 产品的认证。

不幸的是，这两个标准都不是免费的。如果你想阅读它们，就得付费。

美国、加拿大和一些其他国家规定某些行业（如银行）必须使用根据 FIPS 140 等级认证的设备。全球许多公司也遵循这些建议。

注意：擦除秘密是一种叫做 零化 的做法。与三级 HSM 不同，四级 HSM 可以多次覆盖秘密数据，即使在停电情况下也是如此，这要归功于备份内部电池。

通常，你会发现 HSM 是一个外部设备，有自己的货架放在机架上（见图 13.2），插入到数据中心中的企业服务器上，作为插入到服务器主板上的 PCIe 卡，或者甚至是类似硬件安全令牌的小型 dongle。它们可以通过 USB 设备插入到你的硬件中（如果你不介意较低的性能）。回到原点，其中一些 HSM 可以使用智能卡进行管理，用于安装应用程序，备份密钥等等。

图 13.2 作为 PCI 卡的 IBM 4767 HSM。来自维基百科的照片（mng.bz/XrAG）。

一些行业高度利用 HSM。例如，每当你在 ATM 中输入你的 PIN 时，PIN 最终都会由某个地方的 HSM 进行验证。每当你通过 HTTPS 连接到网站时，信任的根源来自存储其私钥在 HSM 中的证书颁发机构（CA），而 TLS 连接可能是由 HSM 终止的。你有安卓手机或 iPhone 吗？谷歌或苹果很有可能使用一批 HSM 来安全地备份你的手机。最后一种情况很有趣，因为威胁模型被颠倒了：用户不信任云端的数据，因此，云服务提供商声称其服务无法查看用户的加密备份，也无法访问用于加密的密钥。

HSM 实际上没有标准的接口，但其中大多数至少会实现公钥密码标准 11（PKCS＃11），这是由 RSA 公司发起的一个古老标准，2012 年逐渐转移到 OASIS 组织，以促进标准的采用。虽然 PKCS＃11 的最新版本（v2.40）发布于 2015 年，但它只是一个标准的更新，最初始于 1994 年。因此，它规定了许多旧的加密算法或旧的操作方式，这可能会导致漏洞。尽管如此，对于许多用途来说它已经足够好，并且指定了一个允许不同系统轻松互操作的接口。好消息是，PKCS＃11 v3.0 在 2020 年发布，包括许多现代加密算法，例如 Curve25519、EdDSA 和 SHAKE 等。

HSM 的真正目标是确保没有人可以从中提取密钥材料，但它们的安全性并不总是闪耀的。关于这些硬件解决方案的安全性很大程度上依赖于它们的高价格、未公开的硬件防御技术以及主要关注硬件方面的认证（如 FIPS 和 Common Criteria）。实际上，已经发现了严重的软件漏洞，而且你使用的 HSM 是否受到这些漏洞的威胁并不总是一目了然。2018 年，Jean-Baptiste Bédrune 和 Gabriel Campana 在他们的研究中展示了一种软件攻击方法（“Everybody be Cool, This is a Robbery”），可以从流行的 HSM 中提取密钥。

注意一个 HSM 的价格不仅高（根据安全级别，它可能轻松达到数万美元），而且除了一个 HSM 外，您通常至少还有另一个用于测试的 HSM，以及至少还有一个用于备份（以防您的第一个 HSM 因密钥而损坏）。这可能会加起来！

此外，我还没有涉及所有这些解决方案中的“大象在房间里”：虽然你可能会阻止大多数攻击者获取你的秘密密钥，但你无法阻止攻击者破坏系统并对 HSM 进行自己的调用（除非 HSM 具有需要多个签名或存在阈值智能卡的逻辑才能运行）。但是，在大多数情况下，HSM 提供的唯一服务是防止攻击者偷偷窃取秘密并在其他时间使用它们。在集成像 HSM 这样的硬件解决方案时，首先了解您的威胁模型、您要防范的攻击类型以及我在第八章中提到的多签名等阈值方案是否更好。

13.2.4 可信平台模块（TPM）：安全元素的有用标准化

尽管安全元件和 HSM（硬件安全模块）被证明是有用的，但它们仅限于特定用例，并且编写自定义应用程序的过程被认为是乏味的。 出于这个原因，可信计算组（TCG）（由行业参与者组成的另一个非营利组织）提出了一个可用的替代方案，旨在面向个人和企业计算机。 这就是可信平台模块（TPM）。

TPM 不是芯片，而是一个标准（TPM 2.0 标准）；任何选择都可以实现它的供应商。 符合 TPM 2.0 标准的 TPM 是一个安全微控制器，具有硬件随机数生成器、用于存储机密的安全存储器，可以执行加密操作，整个系统是防篡改的。 这个描述可能听起来很熟悉，确实，常见的 TPM 实现方式是作为安全元件的重新打包。 通常情况下，您会在企业服务器、笔记本电脑和台式电脑的主板上直接焊接或插入一个 TPM（见图 13.3）。

图 13.3 实现 TPM 2.0 标准的芯片，插入主板。 该芯片可以被系统的主板组件以及运行在计算机操作系统上的用户应用程序调用。 来自维基百科的照片（mng.bz/Q2je）。

与智能卡和安全元件不同，TPM 不运行任意代码。 相反，它提供了一个明确定义的接口，一个更大的系统可以利用它。 TPM 通常相当便宜，今天许多普通笔记本电脑都携带一个。

现在让我们看看坏消息：TPM 和处理器之间的通信渠道通常只是一个总线接口，如果您设法窃取或获得临时物理访问权限，这个通道很容易被截取。 尽管许多 TPM 提供了高度抵抗物理攻击的水平，但它们的通信渠道有些开放的事实确实将它们的用例大部分限制在防御软件攻击上。

为了解决这些问题，已经出现了将类似 TPM 的芯片直接集成到主处理器中的趋势。 例如，苹果有安全信封，微软有 Pluton。 不幸的是，这些安全处理器似乎没有遵循标准，这意味着用户应用程序可能很难，甚至不可能利用它们的功能。 让我们看一些例子，了解像 TPM 这样的硬件安全芯片可以做些什么。

TPM 的最简单的用例是保护数据。要保护密钥很简单：只需在安全芯片中生成它们，并禁止提取。如果您需要密钥，请要求芯片执行加密操作。要保护数据，就对其进行加密。如果你加密单个文件，那概念就叫做基于文件的加密（FBE）；如果是整个磁盘，那就叫做全盘加密（FDE）。FDE 听起来要好得多，因为它是一种全盘加密的方法。这是大多数笔记本电脑和台式机使用的方式。但实际上，FDE 并不那么好：它没有考虑到我们人类如何使用我们的设备。我们经常将设备锁定，而不是关闭，以便后台功能可以继续运行。计算机通过保留数据加密密钥（DEK）来处理这一点，即使您的计算机已锁定也是如此。 （下次你在星巴克上厕所时，留下你锁定的电脑不受监管时，请考虑一下这一点。）现代手机提供了更多的安全性，根据手机是锁定还是关闭，对不同类型的文件进行加密。

实际上，FDE 和 FBE 都有许多实施问题。2019 年，Meijer 和 Gastel（在“自我加密的欺骗：固态硬盘（SSD）加密中的弱点”中）表明，几个 SSD 供应商完全没有安全的解决方案。2021 年，Zinkus 等人（在“移动设备上的数据安全：现状、存在的问题和提出的解决方案”中）发现手机磁盘加密也存在许多问题。

当然，在解密数据之前，用户应该经过身份验证。通常通过要求用户输入 PIN 码或密码来实现。但是仅仅使用 PIN 码或密码是不够的，因为这会导致简单的暴力攻击（尤其是对于 4 位或 6 位 PIN 码）。一般来说，解决方案尝试将 DEK 与用户凭据和保留在围栏上的对称密钥绑定起来。

但是芯片制造商不能在他们生产的每个设备中硬编码相同的密钥；这会导致像 DUHK 攻击（duhkattack.com）这样的攻击，其中发现数千个设备都硬编码了相同的秘密。这反过来意味着一个设备的妥协会导致所有设备的妥协！解决方案是每个设备都有一个设备密钥，该密钥可以在制造时被熔入芯片中，或者由芯片自己通过称为物理不可克隆函数的硬件组件创建。例如，每个苹果安全围栏都有一个 UID，每个 TPM 都有一个唯一的认证密钥和证书密钥，等等。为了防止暴力攻击，苹果的安全围栏将 UID 密钥和用户 PIN 与基于密码的密钥导出函数混合（我们在第二章中介绍了这一点）以导出 DEK。除了我撒了个谎：为了允许用户快速更改他们的 PIN，DEK 并不直接派生，而是由一个密钥加密密钥（KEK）加密。

另一个例子是安全启动。当启动计算机时，会经过不同的阶段，直到最终进入想要的屏幕。用户面临的一个问题是病毒和恶意软件，如果它们感染了启动过程，那么你就会运行在一个邪恶的操作系统上。

为了保护引导的完整性，TPM 和集成的安全芯片提供了一个信任根，这是我们百分之百信任的东西，它使我们能够信任后续的其他东西。这个信任根通常是一些只读存储器（ROM），无法被覆盖（也称为一次可编程存储器，因为它在制造过程中被写入，不能更改）。例如，当最近的苹果设备上电时，首先执行的代码是位于苹果安全区 ROM 内部的引导 ROM。这个引导 ROM 非常小，所以通常它所做的唯一的事情就是：

1. 准备一些受保护的内存，并加载下一个要运行的程序（通常是另一个引导加载程序）

2. 对程序进行哈希处理，并针对 ROM 中的硬编码公钥验证其签名

3. 执行程序

下一个引导加载程序也会执行相同的操作，依此类推，直到最终一个引导加载程序启动操作系统。顺便说一句，这就是为什么没有经过苹果签名的操作系统更新无法安装到您的手机上的原因。

TPM 和集成了类似 TPM 的芯片是一个有趣的发展，它们在最近几年极大地增加了我们设备的安全性。随着它们变得更便宜，以及一个胜出的标准出现，越来越多的设备将能够从中受益。

13.2.5 受信执行环境（TEE）的机密计算

智能卡、安全元件、HSM 和 TPM 是独立的芯片或模块；它们带有自己的 CPU、内存、TRNG 等，其他组件可以通过一些导线或 NFC 启用芯片中的无线电频率与它们通信。类似 TPM 的芯片（微软的 Pluton 和苹果的安全区）也是独立的芯片，尽管与系统片上的主处理器紧密耦合。在本节中，我将讨论在这种安全硬件分类法中您可以采取的下一个逻辑步骤，集成安全，硬件强制执行安全性在主处理器内部。

集成安全功能的处理器被称为为用户代码创建了一个受信任执行环境（TEE），通过扩展处理器的指令集，允许程序在一个单独的安全环境中运行。这个安全环境与我们通常处理的环境（通常称为富执行环境）之间的分离是通过硬件实现的。最终发生的是，现代 CPU 同时运行正常的操作系统和安全操作系统。两者都有自己的寄存器集，但大部分 CPU 结构是共享的。通过使用 CPU 强制逻辑，来自安全世界的数据无法从正常世界访问。例如，CPU 通常会分割其内存，将一部分专门用于 TEE 的专用。因为 TEE 直接在主处理器上实现，这不仅意味着 TEE 比 TPM 或安全元件更快、更便宜，而且在许多现代 CPU 中都是免费的。

与所有其他硬件解决方案一样，TEE 是由不同供应商独立开发的概念，标准（由全球平台）试图追赶发展。最知名的 TEE 是英特尔的软件保护扩展（SGX）和 ARM 的 TrustZone。

TEE 有什么用？让我们举个例子。在过去的几年里，有了一个新的范式——云计算——大公司运行服务器来托管您的数据。亚马逊有 AWS，谷歌有 GCP，微软有 Azure。换句话说，人们正在从自己运行事物转向在别人的计算机上运行事物。在一些需要保护隐私的场景中，这会带来一些问题。为了解决这个问题，机密计算试图提供解决方案，以便运行客户端代码而无法查看或修改其行为。SGX 的主要用例似乎正是这些天的客户端运行代码，而服务器不能查看或篡改。

一个有趣的问题是，如何确信响应来自 SGX，例如，而不是来自某个冒充者。这就是 认证试图解决的问题。认证有两种类型：

• 本地认证——在同一平台上运行的两个隔离区需要进行通信并向对方证明它们是安全的隔离区。

• 远程认证——客户端查询远程隔离区，并需要确保它是生成请求结果的合法隔离区。

每个 SGX 芯片在制造时都提供了唯一的密钥对（根密封密钥）。公钥部分然后由一些英特尔 CA 签名。首先假设，如果忽略硬件安全的假设，那么就是 Intel 正确地为安全 SGX 芯片签署公钥。有了这个前提，现在您可以从 Intel 的 CA 获取签名的认证，证明您正在与真实的 SGX 隔离区通信，并且它正在运行某些特定的代码。

TEE 的首要目标是防止软件攻击。虽然声称的软件安全看起来很吸引人，但实际上，由于现代 CPU 的极端复杂性和动态状态，难以在同一芯片上分隔执行。这可以通过针对 SGX 和 TrustZone 的许多软件攻击来证明（foreshadowattack.eu，mdsattacks.com，plundervolt.com和sgaxe.com）。

作为概念的 TEE 提供了一定程度的抵抗物理攻击，因为在这个微观层面上的东西太小、太紧密地包装在一起，以至于没有昂贵的设备无法分析。对于一个积极进取的攻击者，情况可能会不同。

13.3 什么解决方案适合我？

在本章中，你已经了解了许多硬件产品。作为总结，这里是列表，我也在图 13.4 中加以说明：

• 智能卡是需要外部设备（如支付终端）打开的微型计算机。 它们可以运行小型自定义类似 Java 的应用程序。银行卡就是广泛使用的智能卡的一个例子。

• 安全元件是智能卡的一种泛化，依赖于一组全球平台标准。 SIM 卡是安全元件的一个例子。

• HSMs（硬件安全模块）可以看作是企业服务器的较大的可插拔安全元件。 它们更快、更灵活，主要用于数据中心存储秘密密钥，使密钥攻击更加明显。

• TPM（可信平台模块）是插入个人和企业计算机主板的重新打包的安全元件。 它们遵循由可信计算组织制定的标准 API，可以为操作系统和最终用户提供功能。

• 安全处理器是建立在主处理器极为接近的 TPM 样式芯片，不可编程。 它们不遵循任何标准，不同的参与者推出了不同的技术。

• 信任执行环境（TEEs，如 TrustZone 和 SGX）可以被视为实现在 CPU 指令集内的可编程安全元件。 它们更快、更便宜，主要提供对软件攻击的抵抗。大多数现代 CPU 都配备了 TEE，并提供各种级别的硬件攻击防御。

图 13.4 你在本章学到的不同硬件解决方案以及它们的外观概念。

什么是最适合你的解决方案？通过自问一些问题来缩小你的选择范围：

• 采用何种形态？ 例如，在小型设备中需要安全元件的需求决定了你不能使用哪些解决方案。

• 你需要多快的速度？ 需要每秒执行大量加密操作的应用程序将在可以使用的解决方案上受到严格的限制，可能仅限于 HSM 和 TEE。

• 你需要多少安全性？ 供应商的认证和声明对应于不同级别的软件或硬件安全性。天空是极限。

请记住，没有硬件解决方案是万灵药；你只是增加了攻击的成本。对于一个复杂的攻击者来说，所有这些都几乎没有用。设计你的系统，以便一个被 compromized 的设备不意味着所有的设备都被 compromized。

13.4 泄漏弹性密码学或如何在软件中减轻侧信道攻击

我们看到硬件试图防止直接观察和提取秘密密钥，但硬件能做的事情有限。归根结底，软件可能会不在乎并且尽管所有这些硬件加固，仍然提供密钥。软件可以直接这样做 (像后门) ，或者它可以间接地泄漏足够的信息，让某人重构密钥。后者被称为 侧信道，侧信道漏洞大多数情况下是不经意的漏洞 (至少人们希望如此)。

我在第三章提到了定时攻击，你在那里学到了 MAC 认证标签必须在恒定的时间内进行比较；否则，攻击者可以在发送了许多不正确的标签并测量等待你回复的时间后，推断出正确的标签。定时攻击在现实世界中的所有领域通常都受到严肃对待，因为它们可以在网络上潜在地远程执行，而不像物理侧信道那样。

最重要的和已知的侧信道是 电源消耗，我在本章前面提到过。这被发现是一种攻击，称为 差分电源分析 (DPA)，由 Kocher、Jaffe 和 Jun 在 1998 年发现，当他们意识到他们可以将示波器连接到设备并观察设备随时间变化的电力消耗，同时执行已知明文的加密。这种变化显然取决于所使用的密钥位，以及像异或这样的操作是否会消耗更多或更少的电力，这取决于操作数位是否设置。这个观察结果导致了一种 密钥提取攻击 (所谓的 完全破解)。

这个概念可以用 简单的功耗分析 (SPA) 攻击来说明。在理想的情况下，并且没有硬件或软件对抗功耗分析攻击的实施，只需测量和分析涉及秘密密钥的单个加密操作的功耗消耗即可。我在图 13.5 中说明了这一点。

图 13.5 一些加密算法通过其功耗泄露了大量信息，以至于对单个功耗跟踪（一段时间内的功耗测量）进行简单的功耗分析就可以泄漏算法的私钥。例如，本图表示了 RSA 指数运算的跟踪（消息被指数化为私钥指数；见第六章）。RSA 指数运算采用了一个通过私钥指数的位来迭代的平方乘算法；对于每一位，它只在该位被设置时应用一个平方运算，然后是一个乘法运算。在这个例子中，乘法显然消耗了更多的功耗；因此，功耗跟踪的清晰度。

电源并不是唯一的物理侧信道。一些攻击依赖于电磁辐射、振动，甚至是硬件发出的声音。让我再提到另外两种非物理侧信道。我知道我们处于一个硬件为主的章节，但这些非物理侧信道攻击同样重要，因为它们需要在许多现实世界的加密应用中得到缓解。

首先，返回的错误有时可能泄漏关键信息。例如，在 2018 年，ROBOT 攻击找到了一种利用 Bleichenbacher 攻击（在第六章提到）的方法，攻击了许多实现 RSA PKCS#1 v1.5 解密的服务器，在 TLS 协议中（在第九章中有所涉及）。Bleichenbacher 的攻击只在你可以区分 RSA 密文是否具有有效填充时才有效。为了防止该攻击，安全实现在常量时间内执行填充验证，并且在检测到填充无效时避免提前返回。例如，在 TLS 中的 RSA 密钥交换中，如果 RSA 载荷的填充不正确，服务器必须伪造其响应，使其看起来像是已经完成了成功的握手。然而，如果在填充验证的最后，实现决定根据填充的有效性向客户端返回不同的错误，那么这一切都是徒劳的。

第二，访问内存可能需要更多或更少的时间，这取决于数据是否之前已被访问过。这是由于计算机中存在着众多层次的缓存。例如，如果 CPU 需要某些东西，它首先会检查它是否已经被缓存在其内部存储器中。如果没有，它就会到更远的缓存中去寻找。缓存越远，花费的时间就越长。不仅如此，一些缓存是特定于核心的（例如 L1 缓存），而一些缓存是在多核机器中共享的（例如 L3 缓存、RAM、磁盘）。

缓存攻击利用了一个事实：恶意程序有可能在同一台计算机上运行，使用与敏感密码程序相同的密码库。例如，许多云服务在同一台计算机上托管不同的虚拟服务器，许多服务器使用 OpenSSL 库进行密码操作或提供 TLS 页面。恶意程序找到方法将已加载到与受害者进程共享的缓存中的库的部分逐出，然后定期测量重新读取该库的某些部分所需的时间。如果花费了很长时间，那么受害者没有执行该程序的这部分；如果不花费很长时间，则受害者访问了该程序的这部分并重新填充了缓存，以避免再次将程序从远处的缓存中获取或者更糟的是从磁盘获取。您获得的是类似于功率跟踪的跟踪，而且确实可以以类似的方式进行利用！

好了，侧信道攻击就说到这里。如果您对通过这些侧信道攻击攻击密码学感兴趣，那么有比本书更好的资源。在本节中，我只想讨论密码实现可以和应该实施的软件缓解措施，以保护免受侧信道攻击的影响。这个研究领域整体被称为泄漏韧性密码学，因为密码学家在这里的目标是不泄漏任何信息。

防御物理攻击者是一场永无止境的战斗，这解释了为什么许多这些缓解措施是专有的且类似于混淆。这一部分显然不是详尽无遗的，但应该让您了解应用密码学家正在致力于解决侧信道攻击的类型。

常量时间编程

任何密码学实现的第一道防线是在常量时间内实现其密码学敏感部分（考虑任何涉及秘密的计算）。显而易见，以常量时间实现某事会取消时间攻击，但这也会摆脱许多攻击类别，如缓存攻击和简单的电源分析攻击。

如何以常量时间实现某事？永远不要分支。换句话说，无论输入是什么，始终执行相同的操作。例如，列表 13.1 显示了 Golang 语言如何实现 HMAC 算法的认证标签的常量时间比较。直觉上，如果两个字节相等，那么它们的异或将是 0。如果我们比较的每一对字节都满足这个属性，那么对它们进行 OR 运算也将导致一个 0 值（否则是一个非零值）。请注意，如果这是您第一次看到常量时间技巧，那么阅读这段代码可能会令人困惑。

Golang 如何实现两个字节数组之间的常量时间比较

func ConstantTimeCompare(x, y []byte) byte {
    if len(x) != len(y) {                        // ❶
        return 0                                 // ❶
    }                                            // ❶

    var v byte                                   // ❷
    for i := 0; i < len(x); i++ {                // ❷
        v |= x[i] ^ y[i]                         // ❷
    }                                            // ❷

    return v                                     // ❸
}

❶ 如果两个字符串长度不同，那么在常量时间内比较它们就没有意义。

❷ 这就是魔法发生的地方。循环 OR 将每个字节的异或值累加到一个值 v 中。

❸ 当 v 等于 0 时仅返回 0，否则返回非零值

对于 MAC 身份验证标签比较，仅需要在此处停止通过分支（使用条件表达式，如if）来检查结果是否为 0 或非 0。另一个有趣的例子是椭圆曲线密码中的标量乘法，正如你在第五章中学到的那样，它包括将一个点添加到自身x次数，其中x是我们称之为标量的值。这个过程可能有点慢，因此存在一些聪明的算法来加速这部分。其中一个流行的算法称为蒙哥马利阶梯，基本上等同于我之前提到的 RSA 的平方乘算法（但在不同的群中）。

蒙哥马利阶梯算法在两点相加和一个点加倍之间交替进行（将点加到自身）。RSA 的平方乘和蒙哥马利阶梯算法都有一种简单的方法来缓解时间攻击：它们不分支并且总是执行两个操作。 （这就是为什么 RSA 指数算法通常称为square and multiply always的原因。）

注意 在第七章中，我提到签名方案可能以多种方式出错，并且针对泄漏它们使用的一些字节（在 ECDSA 等签名方案中）的非 ces 存在密钥恢复攻击。这就是 Minerva 和 TPM-Fail 攻击发生的情况，它们发生在同一时间。这两次攻击发现了许多设备由于签名操作所花费的时间变化量而易受攻击。

在实践中，缓解时间攻击并不总是直截了当的，因为 CPU 指令是否用于乘法或条件移动并不总是在恒定的时间内。此外，当使用不同的编译标志时，高级代码如何被编译成机器代码并不总是清楚的。因此，有时会对生成的汇编进行手动审核，以便更加信任编写的恒定时间代码。存在用于分析恒定时间代码的不同工具（如 ducdect、ct-verif、SideTrail 等），但它们在实践中很少被使用。

13.4.2 不要使用秘密！屏蔽和 blinding

另一种常见的阻止或至少混淆攻击者的方法是在涉及秘密的任何操作中添加间接层。其中一种技术称为blinding，这通常得益于公钥密码算法的算术结构。你在第十一章看到了类似于密码认证密钥交换算法的遗忘算法中使用了 blinding，我们可以在我们想要让遗忘的一方成为攻击者观察我们计算中的泄漏的地方同样使用 blinding。让我们以 RSA 为例。

记住，RSA 解密是通过将密文c提升到私有指数d来完成的，其中私有指数d取消了用于计算密文的公共指数e，该公共指数e被用于计算密文为m^e mod N。如果你不记得细节，请务必查阅第六章。增加间接性的一种方法是在攻击者所知的不是密文的值上执行解密操作。这种方法称为基础掩码，操作如下：

1. 生成一个随机的掩盲因子r。

2. 计算message = (ciphertext × r^e)d mod N。

3. 通过计算real_message = message × r^(–1) mod N来解除掩码，其中r^(–1)是r的逆。

这种方法对正在使用的值进行了掩盲，但我们也可以对秘密本身进行掩盲。例如，椭圆曲线标量乘法通常与秘密标量一起使用。但是由于计算发生在一个循环群中，将阶的倍数添加到该秘密中不会改变计算结果。这种技术称为标量掩码，操作如下：

1. 生成随机值k[1]。

2. 计算标量k[2] = d + k[1] × order，其中d是原始的秘密标量，order是它的阶数。

3. 要计算Q = P，而不是计算Q = [k[2]] P，结果是相同的点。

所有这些技术都被证明多多少少是有效的，并且通常与其他软件和硬件缓解措施组合使用。在对称密码中，另一种有些类似的技术称为掩码。

掩码的概念是在将输入（在密码中为明文或密文）传递给算法之前对其进行转换。例如，通过将输入与随机值进行异或操作。然后解除掩码以获得最终正确的输出。由于任何中间状态都被掩码，因此这为密码计算提供了一定程度的与输入数据的去相关性，并使得侧信道攻击变得更加困难。算法必须意识到这种掩码，以便在保持原始算法的正确行为的同时正确执行内部操作。

13.4.3 关于故障攻击的问题？

我之前谈到了故障攻击，这是一种更具侵入性的侧信道攻击类型，它通过引入故障来修改算法的执行。注入故障可以通过许多创造性的方式来实现，例如通过物理方式，例如增加系统的热量，或者甚至通过向目标芯片的计算点发射激光。

令人惊讶的是，故障也可以通过软件引起。例如，在 Plundervolt 和 V0LTpwn 攻击中独立发现了一个例子，它们成功地改变了 CPU 的电压以引入自然故障。这也发生在臭名昭著的 rowhammer 攻击中，该攻击发现了在一些 DRAM 设备上重复访问内存可以翻转附近的位。这些类型的攻击可能很难实现，但非常强大。在密码学中，计算出错误结果有时可能会泄漏密钥。这就是例如使用一些特定优化实现的 RSA 签名的情况。

虽然无法完全消除这些攻击，但存在一些技术可以增加成功攻击的复杂性；例如，多次计算相同的操作并在发布之前比较结果以确保它们匹配，或者在发布之前验证结果。对于签名，可以在返回之前通过公钥验证签名。

故障攻击也可能对随机数生成器产生严重后果。一个简单的解决方案是使用不在每次运行时使用新随机性的算法。例如，在第七章中，您了解到了 EdDSA，这是一种签名算法，签名时不需要新的随机性，与 ECDSA 签名算法相比。

总的来说，这些技术都不是绝对可靠的。在高度敌对的环境中进行密码学始终是关于你能承受多大成本以应对攻击者的问题。

总结

• 今天的威胁不仅是攻击者拦截信息传输，而且是攻击者窃取或篡改运行您的密码学的设备。所谓的物联网设备通常会遇到威胁，并且默认情况下不受复杂攻击者的保护。最近，云服务也被认为是用户威胁模型的一部分。

• 硬件可以帮助保护密码应用程序及其密钥在高度敌对的环境中。其中一个想法是提供一个具有防篡改芯片的设备来存储和执行加密操作。也就是说，如果设备落入攻击者手中，提取密钥或修改芯片行为将会很困难。

• 人们普遍认为，必须结合不同的软件和硬件技术来加固密码学以应对敌对环境。但硬件保护的密码学并非万能药；它只是多层防御，有效地减慢和增加了攻击的成本。有无限时间和金钱的对手总是能够破坏你的硬件。

• 减少攻击的影响也可以帮助吓阻攻击者。这必须通过良好设计系统来完成（例如，确保一个设备的妥协不意味着所有设备都妥协）。

• 虽然有很多硬件解决方案，但最流行的是以下几种：

  • 智能卡是最早的这种安全微控制器之一，可用作微型计算机来存储机密信息并执行加密操作。 它们应该使用多种技术来阻止物理攻击者。 智能卡的概念被概括为安全元素，这是一个在不同领域中以不同方式使用的术语，但归结为可以用作辅助处理器的智能卡，用于已经具有主处理器的更大系统中。

  • 硬件安全模块（HSM）通常被称为行为类似安全元素的可插拔卡。 它们不遵循任何标准接口，但通常实现 PKCS#11 标准用于加密操作。 HSM 可以通过一些 NIST 标准（FIPS 140-3）获得不同级别的安全认证。

  • 受信平台模块（TPM）类似于具有规定接口的安全元素，标准化为 TPM 2.0。 TPM 通常被视为插入笔记本电脑或服务器主板中。

  • 受信执行环境（TEE）是在安全环境和潜在不安全环境之间隔离执行环境的一种方式。 TEE 通常作为 CPU 指令集的扩展来实现。

• 在高度对抗环境中，硬件不足以保护加密操作，因为软件和硬件侧信道攻击可以利用以不同方式发生的泄漏（时间、功耗、电磁辐射等）。 为了抵御侧信道攻击，加密算法实施软件减轻措施：

  • 严肃的加密实现基于恒定时间算法，并避免所有分支以及依赖于秘密数据的内存访问。

  • 基于模糊和掩蔽的减轻技术使敏感操作与秘密或已知要操作的数据脱钩。

  • 故障攻击更难以防范。 减轻措施包括多次计算一个操作，并在发布结果之前比较和验证操作的结果（例如，使用公钥验证签名）。

• 在对抗环境中加固加密是一场永无止境的战斗。 人们应该使用软件和硬件减轻措施的组合，将成功攻击的成本和时间增加到可接受的风险水平。 人们还应该通过为每个设备使用唯一密钥以及可能为每个加密操作使用唯一密钥来减少攻击的影响。

第十四章：后量子密码学

本章包括

• 量子计算机及其对密码学的影响

• 后量子密码学抵御量子计算机的攻击

• 今天和明天的后量子算法

“量子计算机可以破解密码学，”麻省理工学院数学教授彼得·肖尔暗示道。那是 1994 年，肖尔刚刚提出了一个新算法。他的发现解锁了整数的高效因式分解，如果量子计算机真的成为现实，将摧毁像 RSA 这样的密码算法。当时，量子计算机只是一个理论，一个基于量子物理的新型计算机概念。这个想法仍然有待证明。2015 年中期，国家安全局（NSA）在宣布他们计划过渡到量子抗性算法（不易受量子计算机攻击的密码算法）后，让所有人都感到意外。

对于那些尚未过渡到 Suite B 椭圆曲线算法的合作伙伴和供应商，我们建议暂时不要在这一点上进行重大支出，而是准备好迎接即将到来的量子抗性算法过渡。[…] 不幸的是，椭圆曲线的使用增长与量子计算研究的持续进展相冲突，这清楚地表明椭圆曲线密码学并不是许多人曾经希望的长期解决方案。因此，我们不得不更新我们的策略。

—国家安全局（“今日密码学”，2015 年）

尽管量子计算的概念（基于量子力学领域研究的物理现象构建计算机）并不新鲜，但近年来在研究资助和实验突破方面都经历了巨大提升。然而，至今还没有人能够展示用量子计算机破解密码学。国家安全局知道我们不知道的事情吗？量子计算机真的会破解密码学吗？量子抗性密码学又是什么？在本章中，我将尝试回答你所有的问题！

14.1 量子计算机是什么，为什么会让密码学家感到恐慌？

自国家安全局的宣布以来，量子计算机已经多次成为新闻头条，因为诸如 IBM、Google、阿里巴巴、微软、英特尔等许多大公司已经投入了大量资源进行研究。但这些量子计算机到底是什么，为什么这么令人担忧？一切都始于量子力学（也称为量子物理学），这是一门研究小东西行为的物理学领域（想想原子和更小的东西）。由于这是量子计算机的基础，这就是我们调查的起点。

曾经有一段时间，报纸上说只有十二个人理解相对论的理论。我不相信真有这样的时候。可能有一个人理解了，因为他是唯一一个在写论文之前就理解了的人。但是在人们读了这篇论文之后，许多人以某种方式理解了相对论，肯定不止十二个。另一方面，我可以肯定地说，没有人理解量子力学。

—— 理查德·费曼（《物理定律的性质》，麻省理工学院出版社，1965 年）

14.1.1 量子力学，研究微观世界

物理学家长期以来一直认为整个世界是确定性的，就像我们的加密伪随机数生成器一样：如果你知道宇宙是如何运作的，如果你有一台足够大的计算机来计算“宇宙函数”，那么你所需要的只是种子（大爆炸中所包含的信息），然后你就可以从那里预测一切。是的，一切，甚至是宇宙开始后仅仅 137 亿年，你将要读到这行文字的事实。在这样一个世界中，没有随机性的余地。你所做的每个决定都是被过去事件所确定的，甚至是在你出生之前发生的事件。

虽然这种对世界的看法令许多哲学家感到困惑——“那我们真的有自由意志吗？” 他们问道——但在 1990 年代开始出现了一个有趣的物理领域，从那时起就困扰着许多科学家，我们称之为量子物理学（也称为量子力学）。原来，非常小的物体（想想原子和更小的物体）的行为往往与我们迄今使用的所谓的古典物理学观察到的和理论化的行为大不相同。在这个（亚）原子尺度上，粒子有时候似乎像波一样行动，就像不同的波可以相叠加到一起形成一个更大的波，或者在短暂的时刻互相抵消。

我们可以对电子等粒子进行的一种测量是它们的自旋。例如，我们可以测量电子是自旋向上还是向下旋转。到目前为止，还没什么太奇怪的。奇怪的是，量子力学说一个粒子可以同时处于这两种状态中，旋转上升和下降。我们称这种粒子处于量子叠加态。

这种特殊状态可以通过不同的技术手段人工诱导，具体取决于粒子的类型。一个粒子可以保持在叠加态直到我们对其进行测量；在这种情况下，粒子将坍缩成这些可能状态中的一个（自旋向上或向下）。这种量子叠加态就是量子计算机最终使用的：与其拥有可以是 1 或 0 的位，一个量子位或qubit可以同时是 0 和 1。

• 更怪异的是，量子理论认为只有当测量发生时，而不是之前，粒子才会随机决定取哪种状态（每种状态有 50%的概率被观察到）。如果这看起来很奇怪，你并不孤单。许多物理学家无法想象这在他们描绘的确定性世界中是如何工作的。爱因斯坦坚信这个新理论有问题，曾经说过“上帝不玩骰子”。然而，密码学家们很感兴趣，因为这是获得真正随机数的方法！这就是量子随机数生成器（QRNGs）通过不断将光子等粒子设置在超定态然后测量它们所做的事情。

• 物理学家还推测了如果我们的尺度上有物体时量子力学会是什么样子。这导致了薛定谔的猫的著名实验：一个盒子里的猫同时死和活，直到有人观察里面（这引发了关于什么才算观察者的许多争论）。

• 一只猫被困在一个钢制容器里，与以下装置一同（必须防止猫直接干扰）：在一个盖革计数器中，有一小片放射性物质，可能在一个小时内，一个原子会衰变，但也有可能一个都不衰变；如果发生衰变，计数器管就会放电，通过继电器释放一个锤子，破坏一小瓶氰化氢。如果一个小时都让这整个系统自己，而与此同时没有原子衰变，那么我们会说猫还活着。第一个原子的衰变就会毒死它。整个系统的Ψ-函数将通过将活猫和死猫（原谅这个表达）混合或平均分布来表达这一点。

• —艾尔温·薛定谔（“量子力学中的现状”，1935 年）

• 这一切对我们来说都是非常不直观的，因为我们在日常生活中从未遇到过量子行为。现在，让我们再增加一些怪异吧！

• 有时粒子相互作用（例如相互碰撞）并最终处于强烈相关状态，其中描述一个粒子而不包括其他粒子是不可能的。这种现象被称为量子纠缠，它是量子计算机性能提升的秘密之一。比如说，如果两个粒子被纠缠在一起，那么当其中一个被测量时，两个粒子都会坍缩，其中一个的状态被完全地与另一个的状态相关联。好了，那太令人困惑了。让我们举个例子：如果两个电子被纠缠在一起，然后测量其中一个发现它自旋向上，那么我们知道另一个此时是自旋向下的（但在第一个被测量之前是不知道的）。此外，任何这样的实验结果都是一样的。

这很难相信，但更令人震惊的是，已经证明纠缠甚至可以在非常长的距离上起作用。爱因斯坦、波多尔斯基和罗森曾经争论说量子力学的描述是不完整的，很可能缺少隐藏变量，这将解释纠缠（也就是说，一旦粒子分开，它们就知道它们的测量结果将是什么）。

爱因斯坦、波多尔斯基和罗森还描述了一个思想实验（EPR 悖论，以他们姓氏的首字母命名），在这个实验中，两个纠缠粒子被分开了很大的距离（想象一下光年的距离），然后几乎同时被测量。根据量子力学，对其中一个粒子的测量会立即影响另一个粒子，这是不可能的，因为根据相对论的理论，没有信息可以传播得比光速更快（因此产生了悖论）。这个奇怪的思想实验就是爱因斯坦著名地称之为“远距离的诡异作用”。

约翰·贝尔后来提出了一个被称为贝尔定理的概率不等式；如果该定理被证明为真，将证明 EPR 悖论的作者提到的隐藏变量的存在。这个不等式后来在实验中被违反（很多很多次），足以让我们相信纠缠是真实的，排除了任何隐藏变量的存在。

今天，我们说对纠缠粒子的测量会导致粒子相互协调，这就绕过了相对论的预测，即通信不能比光速更快。事实上，试着想想你如何利用纠缠来设计一个通信渠道，你会发现这是不可能的。然而，对于密码学家来说，远距离的诡异作用意味着我们可以开发新颖的方法来进行密钥交换；这个想法被称为量子密钥分发（QKD）。

想象一下将两个纠缠粒子分发给两个同行：然后他们测量各自的粒子以开始形成相同的密钥（因为测量一个粒子会给你关于另一个粒子的测量信息）？量子密钥分发的概念更加吸引人的地方在于不可克隆定理，该定理指出你不能被动地观察这样的交换并创建被发送在通道上的粒子的精确副本。然而，这些协议容易受到简单的中间人攻击，并且在没有已经有一种验证数据的方法的情况下几乎是无用的。这个缺陷导致一些密码学家如布鲁斯·施奈尔声称“量子密钥分发作为一种产品没有未来”。

至于量子物理，这就是我对密码学书籍的讲解。如果你不相信刚刚读到的所有奇异的事情，那你并不孤单。在他的书《工程师的量子力学》中，里昂·范·多姆伦写道：“物理学最终采用了量子力学，并不是因为它似乎是最合乎逻辑的解释，而是因为无数的观察使其不可避免。”

14.1.2 从量子计算机诞生到量子霸权

1980 年，量子计算的概念诞生了。是保罗·贝尼奥夫首次描述了量子计算机可能的样子：一台由量子力学最近几十年的观察结果构建的计算机。同年晚些时候，保罗·贝尼奥夫和理查德·费曼认为，这是模拟和分析量子系统的唯一方法，而不受经典计算机的限制。

仅仅 18 年后，IBM 首次演示了在实际量子计算机上运行的量子算法。快进到 2011 年，量子计算机公司 D-Wave Systems 宣布推出了第一台商用量子计算机，推动整个行业向前迈进，致力于创建第一台可扩展的量子计算机。

目前仍然有很长的路要走，而且有用的量子计算机还没有实现。在撰写本文时（2021 年），最近一个引人注目的成果是谷歌声称在 2019 年用一台 53 量子比特的量子计算机实现了量子霸权。量子霸权意味着，首次有一台量子计算机做到了经典计算机无法做到的事情。在 3 分 20 秒内，它完成了一些分析，而这些分析如果由经典计算机完成，需要大约 1 万年的时间。也就是说，在你激动得太早之前，它在一个无用的任务上胜过了经典计算机。然而，这是一个令人难以置信的里程碑，人们只能想象这将引领我们走向何方。

量子计算机基本上使用量子物理现象（如叠加和纠缠）进行计算，就像经典计算机使用电来进行计算一样。量子计算机不使用比特，而是使用量子比特或qubit，可以通过量子门转换它们以设置特定值或使它们处于叠加状态，甚至是纠缠状态。这在某种程度上类似于经典计算机电路中使用门的方式。计算完成后，可以测量量子比特以经典方式解释它们——作为 0 和 1。此时，可以进一步使用经典计算机解释结果，以完成有用的计算。

一般来说，N个纠缠的量子比特包含等价于 2^N 个经典比特的信息。但是，在计算结束时测量量子比特只会给出N个 0 或 1。因此，并不总是清楚量子计算机如何帮助，量子计算机只对有限数量的应用程序有用。随着人们找到巧妙的方法利用它们的力量，它们可能会变得越来越有用。

今天，你已经可以在家中舒适地使用量子计算机了。像 IBM 量子计算（quantum-computing.ibm.com）这样的服务允许你构建量子电路并在托管在云中的真实量子计算机上执行。当然，目前（2021 年初）这类服务相当有限，只有少量的量子比特可用。但是，创建自己的电路并等待其在真实量子计算机上运行的体验令人叹为观止，而且这一切都是免费的。

14.1.3 Grover 和 Shor 算法对密码学的影响

不幸的是，正如我之前所说的，量子计算机并不适用于每一种类型的计算，因此，它们不是我们经典计算机的更强大的替代品。但是，它们究竟有什么用处呢？

1994 年，在量子计算机的概念只是一种思想实验的时候，彼得·肖尔提出了一个解决离散对数和因子化问题的量子算法。肖尔有洞察力地认为量子计算机可以用于快速计算与密码学中看到的难题相关的问题的解决方案。事实证明，存在一种高效的量子算法，可以帮助找到一个周期，使得f(x + period) = f(x)对于任何给定的x成立。例如，找到值为period的周期，使得 g^(x+period) = g^x mod N。这反过来导致可以有效地解决因子化和离散对数问题的算法，从而影响了像 RSA（在第六章中讨论）和 Diffie-Hellman（在第五章中讨论）这样的算法。

Shor 算法对非对称密码学具有毁灭性影响，因为今天大多数使用的非对称算法依赖于离散对数或因子化问题——实际上，你在本书中看到的大部分内容都是如此。你可能会认为离散对数和因子化仍然是困难的数学问题，而我们可以（也许）增加算法参数的大小以提升其抵抗量子计算机的能力。不幸的是，由 Bernstein 等人于 2017 年证明，尽管提高参数是有效的，但这是极不切实际的。研究估计，将 RSA 的参数增加到 1 TB 可以使其对抗量子计算机。说实话，这是不现实的。

Shor 算法颠覆了部署的公钥加密技术的基础：RSA 和有限域和椭圆曲线上的离散对数问题。长期保密的文件，如患者医疗记录和国家机密，必须在多年内保证安全性，但今天使用 RSA 或椭圆曲线加密的信息，存储到量子计算机可用时，将像今天的 Enigma 加密消息一样容易解密。

—PQCRYPTO：长期安全后量子系统的初始建议（2015）

对于对称加密来说，情况要好得多。Grover 算法于 1996 年由 Lov Grover 提出，作为优化无序列表中搜索的一种方式。在经典计算机上，对 N 个项目的无序列表进行搜索平均需要 N/2 次操作；而在量子计算机上，只需要 √N 次操作。这是相当大的加速！

Grover 算法是一种非常多才多艺的工具，可以在许多密码学领域应用，例如提取密码的对称密钥或在哈希函数中找到碰撞。要搜索一个 128 位密钥，Grover 算法在量子计算机上运行的操作次数为 2⁶⁴，而在经典计算机上为 2¹²⁷。对于我们所有的对称加密算法来说，这是一个相当可怕的说法，但我们只需将安全参数从 128 位提升到 256 位，就足以抵御 Grover 的攻击。因此，如果你想保护对称加密技术免受量子计算机的攻击，你可以简单地使用 SHA-3-512 替代 SHA-3-256，使用 AES-256-GCM 替代 AES-128-GCM，等等。

总结一下，对称加密大部分情况下是安全的，而非对称加密则不然。这甚至比你一开始想象的更糟：对称加密通常需要进行密钥交换，而这一过程容易受到量子计算机的攻击。那么，这是否意味着我们所熟知的加密技术将走向终结呢？

14.1.4 后量子密码学，对抗量子计算机的防御

幸运的是，这并不是加密技术的终结。社区迅速应对量子威胁，通过组织自身并研究新旧算法，以抵御 Shor 和 Grover 的攻击。抗量子密码学领域，也被称为后量子密码学，因此诞生了。互联网上存在着不同地方的标准化努力，但最受尊敬的努力来自 NIST，该机构于 2016 年启动了后量子密码学的标准化进程。

似乎过渡到后量子密码学并不简单，因为我们当前的公钥密码算法不太可能有一个简单的“即插即用”替代方案。将需要进行大量的工作来开发、标准化和部署新的后量子密码系统。此外，这种过渡需要在任何大规模量子计算机建成之前进行，以便任何后期由量子密码分析而泄露的信息在泄露时不再敏感。因此，尽早为这种过渡做好规划是可取的。

—NIST 标准化过程的后量子密码学页面 (2016)

自 NIST 开始这个过程以来，有 82 个候选者申请，并且经过了 3 轮，将候选者名单缩减到了 7 个决赛选手和 8 个备用决赛选手（不太可能被考虑用于标准化，但如果决赛选手中的某个范式被破解了，则是一个很好的选择）。NIST 的标准化工作旨在替换最常见的非对称密码学基元，其中包括签名方案和非对称加密。后者也可以轻松地作为密钥交换基元，正如你在第六章中所学到的。

在本章的其余部分，我将介绍正在考虑标准化的不同类型的后量子密码算法，并指出你今天可以使用哪些算法。

14.2 基于哈希的签名：除了哈希函数外不需要任何东西

尽管所有实际的签名方案似乎都使用哈希函数，但存在一种方法可以构建只使用哈希函数而不使用其他东西的签名方案。更好的是，这些方案倾向于仅依赖于哈希函数的前像抗性而不是它们的碰撞抗性。这是一个相当吸引人的建议，因为应用密码学的巨大部分已经基于稳固和被充分理解的哈希函数。

现代哈希函数也能抵抗量子计算机，这使得这些基于哈希的签名方案自然而然地具有量子抗性。让我们看看这些基于哈希的签名是什么，以及它们是如何工作的。

14.2.1 一次性签名 (OTS) 使用 Lamport 签名

1979 年 10 月 18 日，莱斯利·兰波特（Leslie Lamport）发布了他的 一次性签名 (OTS) 的概念：只能用于签名一次的密钥对。大多数签名方案（部分地）依赖于单向函数（通常是哈希函数）来进行安全证明。兰波特方案的美妙之处在于，他的签名完全依赖于这样的单向函数的安全性。

假设你想要签名一个单个比特。首先，通过生成密钥对

1. 生成两个随机数 x 和 y，它们将作为私钥

2. 对 x 和 y 进行哈希运算得到两个摘要 h(x) 和 h(y)，你可以将其公开为公钥

要将一个比特设为 0，揭示你的私钥的x部分；要将一个比特设为 1，揭示y部分。要验证一个签名，只需对其进行哈希，以检查其是否与公钥的正确部分匹配。我在图 14.1 中说明了这一点。

图 14.1 Lamport 签名是一种仅基于哈希函数的一次性签名（OTS）。为了生成一个可以签署一个比特的密钥对，生成两个随机数，这将是你的私钥，并分别对这两个数进行哈希，以产生你的公钥的两个摘要。要将一个比特设为 0，揭示第一个随机数；要将一个比特设为 1，揭示第二个随机数。

签署一个比特并不那么有用，你说。没问题；Lamport 签名通过为每个比特创建更多的秘密对，一个比特一个秘密对，来对更大的输入进行签名（参见图 14.2）。显然，如果你的输入大于 256 位，你首先会对其进行哈希，然后再对其进行签名。

图 14.2 为了生成一个 Lamport 签名密钥对，可以签署一个n位消息，生成 2n个随机数，这将是你的私钥，并分别对这些数进行哈希，以产生你的公钥的 2n个摘要。要签名，遍历秘密和n位的对，揭示第一个元素以将一个比特设为 0，或揭示第二个元素以将一个比特设为 1。

这种方案的一个主要限制是你只能使用它签名一次；如果你用它签名两次，你最终会授权别人混合这两个签名来伪造其他有效的签名。我们可以通过天真地生成大量一次性密钥对而不是单个密钥对来改善这种情况，然后确保在使用后丢弃一个密钥对。这不仅使你的公钥变得像你认为你可能会使用的签名数量一样大，而且还意味着你必须跟踪你使用过的密钥对（或者更好的是，丢弃你使用过的私钥）。例如，如果你知道你将要使用具有 256 位输出大小的哈希函数签署最大为 256 位的 1,000 个消息，那么你的私钥和公钥都必须是 1000 × (256 × 2 × 256)位，约为 16 兆字节。对于只有 1,000 个签名来说，这是相当多的。

今天提出的大多数基于哈希的签名方案都建立在 Lamport 创造的基础上，以允许更多的签名（有时是几乎无限量的签名），无状态的私钥（尽管一些提出的方案仍然是有状态的），以及更实用的参数大小。

14.2.2 Winternitz 一次签名（WOTS）的较小密钥

在 Lamport 发表几个月后，斯坦福大学数学系的 Robert Winternitz 提出了发布一个秘密的哈希的哈希的哈希* h （ h （… h （ x *）））= * h ^ w （ x *）而不是发布多个秘密的多个摘要，以优化私钥的大小（参见图 14.3）。这个方案被称为作者之后的 Winternitz 一次签名（WOTS）。

例如，选择 w = 16 允许你签署 16 个不同的值，换句话说，4 位输入。你首先生成一个作为私钥的随机值 x，并将其哈希 16 次以获得你的公钥，h¹⁶(x)。现在想象一下，你想要签署位 1001（十进制中的 9）；你发布哈希的第九次迭代，h⁹(x)。我在图 14.3 中进行了说明。

图 14.3 Winternitz 一次签名（WOTS）方案通过仅使用一个被迭代哈希的秘密来优化 Lamport 签名，以获得许多其他秘密和最终的公钥。揭示不同的秘密允许签署不同的数字。

花几分钟时间来理解这个方案是如何工作的。你看到其中有什么问题吗？一个主要问题是这个方案允许伪造签名。想象一下，你看到别人对位 1001 的签名，根据我们之前的例子，这将是 h⁹(x)。你可以简单地对其进行哈希以检索任何其他迭代，比如 h¹⁰(x) 或 h¹¹(x)，这将为你提供位 1010 或 1011 的有效签名。这可以通过在消息后添加一个短的认证标签来规避，你也必须对其进行签名。我在图 14.4 中进行了说明。为了说服自己这解决了伪造问题，请尝试从另一个签名中伪造一个签名。

图 14.4 WOTS 使用额外的签名密钥来验证签名，以防篡改。它的工作原理是：在签名时，第一个私钥用于签署消息，第二个私钥用于签署消息的补码。很明显，在所示的任何情况下，篡改签名都不会导致新的有效签名。

14.2.3 使用 XMSS 和 SPHINCS+ 的多次签名

到目前为止，你已经看到了只使用哈希函数签名的方法。虽然 Lamport 签名是有效的，但它们具有较大的密钥大小，因此 WOTS 通过减小密钥大小改进了这一点。然而，这两种方案仍然不具有良好的可扩展性，因为它们都是一次性签名（重复使用密钥对会破坏方案），因此，它们的参数会随着你认为需要的签名数量的增加而线性增加。

一些方案允许密钥对重复使用几次（而不是一次）。这些方案被称为少次签名（FTS），如果重复使用次数太多，将会破坏，从而允许伪造签名。FTS 依赖于从秘密池中重复使用相同组合秘密的低概率。这是对一次性签名的小改进，允许减少密钥重用的风险。但我们可以做得更好。

在这本书中，你学到的一个技术是将许多事物压缩成一个事物的技术是什么？答案是默克尔树。正如你可能还记得第十二章所述，默克尔树是一种数据结构，为诸如我的数据是否在这个集合中之类的问题提供简短的证明。在 1990 年代，提出默克尔树的默克尔还发明了一种基于哈希函数的签名方案，将多个一次性签名压缩成一个默克尔树。

这个想法非常简单：你的树的每个叶子都是一次性签名的哈希，而根哈希可以用作公钥，将其大小减小到哈希函数的输出大小。要签名，你选择一个之前未使用过的一次性签名，然后按照第 14.2.2 节中的说明应用它。签名是一次性签名，以及证明它属于你的默克尔树的默克尔证明（所有邻居）。这个方案显然是有状态的，因为人们应该小心不要在树中重复使用一次性签名之一。我在图 14.5 中说明了这一点。

图 14.5 默克尔签名方案是一种有状态的基于哈希的算法，利用默克尔树将许多 OTS 公钥压缩为更小的公钥（根哈希）。树越大，它可以产生的签名就越多。请注意，签名现在具有成员证明的开销，这是一些邻居节点，允许验证签名的相关 OTS 是否属于树。

扩展默克尔签名方案（XMSS），在 RFC 8391 中标准化，旨在通过向默克尔方案添加一些优化来实现默克尔签名的生产。例如，为了生成能够签署N条消息的密钥对，你必须生成N个 OTS 私钥。虽然公钥现在只是一个根哈希，但你仍然必须存储N个 OTS 私钥。XMSS 通过使用种子和树中的叶子位置确定性地生成树中的每个 OTS，从而减小了你持有的私钥的大小。这样，你只需要将种子存储为私钥，而不是所有 OTS 私钥，并且可以快速从树中的位置和种子重新生成任何 OTS 密钥对。为了跟踪上次使用的叶子/OTS，私钥还包含一个计数器，每次用于签名时都会递增。

提到这一点，Merkle 树中只能容纳有限的 OTS。树越大，重建树以签署消息就越耗时（因为您需要重建所有叶子以生成 Merkle 证明）。树越小，在签名时需要重建的 OTS 私钥就越少，但这显然违背了初衷：我们现在又回到了有限数量的签名。解决方案是使用一个较小的树，其中叶子中的 OTS 不用于签署消息，而是用于签署其他 OTS 的 Merkle 树的根哈希。这将我们的初始树转换为超树——树的树——是 XMSS 的一种变体称为 XMSS^(MT)。对于 XMSS^(MT)，仅需要基于相同的技术重建与 OTS 路径有关的树。我在图 14.6 中进行了说明。

图 14.6 XMSS^(MT) 有状态基于哈希的签名方案使用多个树来增加方案支持的签名数量，同时减少密钥生成和签名时间的工作量。只有当它们在路径到包含用于签署消息的 OTS 的最终叶子中使用时，每个树才会被确定性地生成。

请注意，XMSS 和 XMSS^(MT) 的状态性在某些情况下可能不是问题，但总的来说不是一种理想的属性。必须跟踪一个计数器是反直觉的，因为我们不希望从主流签名方案的用户那里期待这种行为。这种实践的变化可能会导致 OTS 的重用（从而导致签名伪造），如果不当使用，例如，回滚到文件系统的先前状态或在多个服务器上使用相同的签名密钥可能导致超树中的相同路径两次用于签署消息。

为了解决 XMSS 最大的缺点之一（其状态性）并展现类似于我们习惯的签名方案的接口，SPHINCS+ 签名方案作为 NIST 的后量子密码竞赛的一部分提出。这个无状态签名方案通过三个主要变化来增强 XMSS^(MT)：

• *两次签署相同的消息会导致相同的签名。*与第七章介绍的 EdDSA 类似，超树中使用的路径是根据私钥和消息确定性地派生的。这确保了两次签署相同的消息会导致相同的 OTS，从而导致相同的签名；由于使用了私钥，攻击者也无法预测您在签署其他人消息时将采取哪条路径。

• 使用更多的树. XMSS^(MT)通过追踪上次使用的 OTS 来避免两次重复使用相同的 OTS。由于 SPHINCS+的整个目的是避免追踪状态，因此它需要在选择伪随机路径时避免冲突。为此，SPHINCS+简单地使用了更多的 OTS，减少了两次重复使用相同 OTS 的概率。由于 SPHINCS+还使用了超树，这意味着更多的树。

• 使用少次签名（FTS）。由于方案的安全性是基于两次重复使用相同路径的概率，因此 SPHINCS+还用我之前提到的 FTS 替换了用于签署消息的最终 OTS。这样，重复使用相同路径来签署两个不同的消息仍然不会直接导致签名方案的破坏。

虽然 SPHINCS+正在考虑在 NIST 后量子密码竞赛中进行标准化，但它并不是主要的竞争者。SPHINCS+不仅速度慢，而且与提议的替代方案（如基于格的方案，在本章后面将会介绍）相比，其签名大小也较大。基于状态的哈希签名方案（如 XMSS）提供更快的速度和更好的签名大小（小于 3 KB，而 SPHINCS+的最小签名大小为 8 KB）。（在公钥大小方面，这两种方案提供了与预量子签名方案（如 ECDSA 和 Ed25519）类似的大小。）由于更现实的参数大小和良好理解的安全性，NIST 在 SP 800-208 中推荐了 XMSS 作为早期标准，“基于状态的哈希签名方案的建议”。

接下来，让我们来看看另外两种构建抗量子密码原语的方法。温柔的警告：它们的数学内容要多得多！

14.3 基于格的密码学中的更短密钥和签名

大量的后量子密码方案基于格，这是一种您将在本节中了解的数学结构。NIST 后量子密码竞赛本身已经选定了基于格的方案作为其半决赛选手的一半。这使得基于格的密码学成为最有可能赢得并从 NIST 获得标准的范式。在本节中，我将告诉您关于两种基于格的算法：Dilithium，一种签名方案，以及 Kyber，一种公钥加密原语。但在此之前，让我们先了解一下什么是格。

14.3.1 什么是格？

首先，基于格的概念可能不是你想象的那样。以 RSA 为例（第六章讨论过），我们说 RSA 是基于因子分解问题的。这并不意味着我们在 RSA 中使用了因子分解，而是意味着因子分解是你攻击 RSA 的方法，并且因为因子分解很难，所以我们说 RSA 是安全的。基于格的密码系统也是如此：格是具有困难问题的结构，只要这些问题保持困难，这些密码系统就是安全的。

说到这里，什么是格？嗯，它就像一个向量空间，但带有整数。如果你不记得向量空间是什么，那就是所有可以使用以下内容创建的向量的集合：

• 基—一组向量；例如，(0,1) 和 (1,0)。

• 向量之间的运算—向量可以相加；例如，(0,1) + (1,0) = (1,1)。

• 标量运算—向量可以乘以我们称为标量的东西；例如，3 × (1,2) = (3,6)。

在我们的例子中，向量空间包含所有可以表示为基的线性组合的向量，这意味着任何可以写为a × (0,1) + b × (1,0)的向量。例如，0.5 × (0,1) + 3.87 × (1,0) = (3.87,0.5)在我们的向量空间中，99 × (0,1) + 0 × (1,0) = (0,99)也是如此，等等。

格是一个向量空间，其中涉及的所有数字都是整数。是的，在密码学中，我们喜欢整数。我在图 14.7 中说明了这一点。

图 14.7 左侧绘制了两个向量的基。通过取这两个向量的所有可能的整数线性组合可以形成一个格点（中间图）。所得的格点可以被解释为空间中永远重复的点的模式（右图）。

在格空间中存在几个众所周知的难题，针对这些问题，我们有解决方案。这些算法通常是我们能想到的最好的，但这并不一定意味着它们是高效的，甚至是实用的。因此，这些问题至少被认为是困难的，直到找到更高效的解决方案。最知名的两个困难问题如下。（我在图 14.8 中说明了这两个问题。）

• 最短向量问题（SVP）—回答这个问题：你的格点中最短的非零向量是什么？

• 最近向量问题（CVP）—给定一个不在格点上的坐标，找到该坐标在格点上最近的点。

图 14.8 展示了密码学中使用的两个主要格问题：最短向量问题（SVP）和最近向量问题（CVP）

通常，我们使用像 LLL（Lenstra–Lenstra–Lovász 算法）或 BKZ（Block-Korkine-Zolotarev 算法）这样的算法来解决这两个问题（CVP 可以归约为 SVP）。这些算法会缩减格点的基，意味着它们试图找到一组比给定的更短的向量，并且能够产生完全相同的格点。

14.3.2 含有错误的学习（LWE），密码学的基础？

在 2005 年，Oded Regev 提出了含有错误的学习（LWE）问题，它成为了许多密码方案的基础，包括本章中的一些算法。在继续之前，让我们看看 LWE 问题是什么。让我们从以下方程式开始，它们是相同整数s[0]和s[1]的线性组合：

• 5 s[0] + 2 s[1] = 27

• 2 s[0] + 0 s[1] = 6

我们知道，通过使用高斯消元算法，只要我们有足够多的这些方程，我们就可以快速有效地学到s[0]和s[1]是什么。现在有趣的是，如果我们给这些方程添加一些噪音，问题就变得更加困难：

• 5 s[0] + 2 s[1] = 28

• 2 s[0] + 0 s[1] = 5

当你增加所涉及的数字的大小和s[i]的数量时，通过更多嘈杂的方程可能并不太难找到答案，但一旦增加了这些因素，问题就变得更加困难。

这本质上就是 LWE 问题，尽管通常用向量来表述。想象一下，你有一个带有模一些大数的秘密向量s。给定相同大小的任意数量的随机向量a[i]和计算a[i]s + e[i]的结果，其中e[i]是一个随机小误差，你能找到值s吗？

注意 对于两个向量v和w，可以使用点积计算乘积vw，即每对坐标的乘积之和。让我们看一个例子：如果v = (v[0], v[1])，而w = (w[0], w[1])，那么vw = v[0] × w[0] + v[1] × w[1]。

例如，如果我使用秘密s = (3,6)并给你随机向量a[0] = (5,2)和a[1] = (2,0)，我得到了我在例子中开始的方程。正如我之前所说，基于格的方案实际上并不使用格；相反，它们被证明是安全的，如果 SVP 保持困难（对于某些定义的困难）。只有在我们将以前的方程以矩阵形式写出时，才能看到归约，如图 14.9 所示。

图 14.9 学习中的错误问题（LWE）被认为是基于格的构造，因为存在到格问题的归约：CVP。换句话说，如果我们可以找到 CVP 的解，那么我们就可以找到 LWE 问题的解。

这种矩阵形式很重要，因为大多数基于 LWE 的方案都是以这种形式表达和解释的。花几分钟时间复习矩阵乘法。另外，如果你还没有注意到，我使用了一些常见的符号技巧，这些技巧对于阅读涉及矩阵和向量的方程非常有帮助：两者都以粗体字体书写，矩阵始终是大写字母。例如，A是矩阵，a是向量，b只是一个数字。

注意 LWE 问题存在几个变体（例如，环-LWE 或模-LWE 问题），它们基本上是相同的问题，但坐标位于不同类型的群中。由于它们的紧凑性和解锁的优化，通常更喜欢这些变体。LWE 变体之间的差异不影响接下来的解释。

现在你知道 LWE 问题是什么了，让我们学习一些基于它的后量子密码学：代数格密码套件（CRYSTALS）。 方便的是，CRYSTALS 包含两个密码学原语：一个称为 Kyber 的密钥交换和一个称为 Dilithium 的签名方案。

14.3.3 Kyber，基于格的密钥交换

两个 NIST 最终方案密切相关： CRYSTALS-Kyber 和 CRYSTALS-Dilithium，这两个方案都是来自同一研究团队的候选方案，都基于 LWE 问题。 Kyber 是一个可以用作密钥交换原语的公钥加密原语，在本节中我将解释。 Dilithium 是一个签名方案，我将在下一节中解释。 还要注意，由于这些算法仍在变化中，我将只写出这两个方案背后的思想和直觉。

首先，让我们假设所有操作都在模一个大数 q 的整数群中进行。 我们还假设错误和私钥是从以 0 为中心的小范围内（均匀随机选择）采样的。 具体来说，错误范围是范围 [–B, B]，其中 B 远远小于 q。 这很重要，因为某些项需要比某个值小才能被视为错误。

要生成私钥，只需生成一个随机向量 s，其中每个系数都在错误范围内。 公钥的第一部分是相同大小的随机向量 a[i] 的列表，第二部分是相关的噪声点乘列表 t[i] = a[i] s + e[i] mod q。 这正是我们之前学到的 LWE 问题。 对于其余部分很重要的是，我们可以用矩阵来重写这个问题：

t = As + e

其中矩阵 A 包含随机向量 a[i] 作为行，而错误向量 e 包含单个错误 e[i]。

要使用 Kyber 进行密钥交换，我们使用方案加密一个 1 位的对称密钥（是的，只有一个位！）。 这类似于您在第六章中看到的 RSA 密钥封装机制。 以下四个步骤显示了加密的工作原理：

1. 生成一个短暂的私钥向量 r（系数在错误范围内），及其关联的短暂公钥 rA + e[1] 与一些随机错误向量 e[1]，使用对等方的 A 矩阵作为公共参数。 注意，矩阵乘法在右侧执行，这涉及将向量 r 与 A 的列相乘，而不是计算 Ar（向量 r 与 A 的行的乘积）。 这是一个细节，但对解密步骤的工作是必要的。

2. 我们通过将其与 q/2 相乘将消息向左移动，以避免小错误影响我们的消息。 注意，q/2 模 q 通常意味着 q 乘以 2 模 q 的倒数，但这里它只是意味着 q/2 的最接近的整数。

3. 用我们的临时私钥和对等方的公钥的点积计算共享密钥。

4. 通过将其添加到共享密钥以及随机错误e[2]来加密您的（移位的）消息。这将产生一个密文。

执行完这些步骤后，我们可以将临时公钥和密文都发送给另一个对等方。收到临时公钥和密文后，我们可以按照以下步骤解密消息：

1. 通过计算您的秘密与收到的临时公钥的点积来获得共享密钥。

2. 将共享密钥从密文中减去（结果包含移位的消息和一些错误）。

3. 通过将其除以q/2，将消息移回原始位置，有效地消除错误。

4. 如果消息接近q/2，则为 1，否则为 0。

当然，1 位是不够的，所以当前方案采用不同的技术来克服这个限制。我在图 14.10 中总结了所有三个算法。

图 14.10 Kyber 公钥加密方案。请注意，在加密和解密过程中，共享密钥几乎相同，因为r、s和错误远小于q/2。因此，解密的最后一步（除以q/2，可以看作是向右的位移）消除了两个共享密钥之间的任何差异。请注意，所有操作都是模q进行的。

在实践中，对于密钥交换，您加密到对等方的公钥的消息是一个随机密钥。然后，结果是从密钥交换的记录和对等方的公钥、您的临时密钥和密文中确定性地派生出来的。

Kyber 的推荐参数导致公钥和密文约为 1 千字节，这比我们使用的预量子方案要大得多，但对于大多数用例来说仍然是实用的范畴。虽然时间会告诉我们是否可以进一步减少这些方案的通信开销，但迄今为止，量子后的韵律似乎与更大的尺寸相呼应。

14.3.4 Dilithium，一个基于格的签名方案

我将解释的下一个方案Dilithium也是基于 LWE 的，是 Kyber 的姊妹候选方案。与我们见过的其他类型的签名（如第七章中的 Schnorr 签名）一样，Dilithium 基于一个零知识证明，通过 Fiat-Shamir 技巧使其非交互式。

对于密钥生成，Dilithium 与先前的方案类似，只是我们将错误作为私钥的一部分保留。我们首先生成两个作为私钥的随机向量s[1]和s[2]，然后计算公钥为t = As[1] + s[2]，其中A是以与 Kyber 类似的方式获得的矩阵。公钥是t和A。请注意，我们将错误s[2]视为私钥的一部分，因为我们需要在每次签署消息时重复使用它（不像在 Kyber 中，错误可以在密钥生成步骤之后丢弃）。

要签署，我们创建一个 sigma 协议，然后通过费亚特-沙米尔转换将其转换为非交互式、零知识证明，这类似于第七章中 Schnorr 识别协议转换为 Schnorr 签名的方式。交互式协议如下：

1. 证明者通过发送Ay[1] + y[2]对两个随机向量y[1]和y[2]进行承诺。

2. 在收到此提交后，验证者会回复一个随机挑战c。

3. 然后，证明者计算两个向量z[1] = c s[1] + y[1]和z[2] = c s[2] + y[2]，并仅在它们是小值时将它们发送给验证者。

4. 验证者检查Az[1] + z[2] – c t和Ay[1] + y[2]是否为相同的值。

费亚特-沙米尔技巧通过让证明者从要签名的消息和已承诺的Ay[1] + y[2]值的哈希中生成挑战，取代了第 2 步中验证者的角色。我在图 14.11 中总结了这个转换，使用了第七章中类似的图表。

图 14.11 Dilithium 签名是对秘密向量s的知识证明，通过费亚特-沙米尔转换变为非交互式。左侧的图表显示了交互式证明协议，而右侧的图表显示了一个非交互式版本，其中挑战被计算为y和要签名的消息的承诺。

再次强调，这只是对签名方案的粗略简化。实际上会使用更多的优化来减少密钥和签名的大小。通常，这些优化会尝试通过从较小的随机值确定性生成随机数据来减少任何随机数据，并通过自定义方法压缩非随机数据来减少非随机数据，不一定通过已知的压缩算法。由于 LWE 的独特结构，还有许多其他可能的优化。

在推荐的安全级别下，Dilithium 提供约 3 KB 的签名和不到 2 KB 的公钥。这显然远远超过了前量子方案的 32 字节公钥和 64 字节签名，但也比无状态基于哈希的签名要好得多。值得注意的是，这些方案仍然相当新颖，可能会找到更好的算法来解决 LWE 问题，潜在地增加公钥和签名的大小。同时，我们也可能找到更好的技术来减小这些参数的大小。总的来说，量子抗性很可能总是伴随着尺寸成本。

后量子密码学并不仅仅是这些；NIST 后量子密码学竞赛还有许多基于不同范式的构造。NIST 已宣布将于 2022 年发布初步标准，但我预计这个领域将继续快速发展，至少在后量子计算机被视为合法威胁的情况下。虽然仍有许多未知因素，但这也意味着有很多令人兴奋的研究空间。如果你对此感兴趣，我建议查看 NIST 报告（nist.gov/pqcrypto）。

14.4 我需要恐慌吗？

总结一下，如果量子计算机得以实现，对于密码学来说将是一个巨大的挑战。这里的要点是什么？你需要放弃手头的一切，转向后量子算法吗？嗯，事情并不那么简单。

询问任何专家，你会得到不同类型的答案。对于一些人来说，这可能是 5 到 50 年的事情；对于其他人来说，这永远不会发生。量子计算研究所所长米歇尔·莫斯卡估计“到 2026 年有 1/7 的机会破解 RSA-2048，到 2031 年有 1/2 的机会”，而法国国家科学研究中心研究员米哈伊尔·迪亚科诺夫公开表示“我们能否学会控制定义这种系统量子状态的超过 10³⁰⁰个连续可变参数？我的答案很简单。不，永远不会。”虽然物理学家而非密码学家更了解情况，但他们仍可能被激励夸大自己的研究以获取资金。作为一个非物理学家，我只能说我们应该对不寻常的声明保持怀疑，同时做最坏的准备。问题不是“它会起作用吗？”；而是“它会扩展吗？”

要使可扩展的量子计算机（可能破坏密码学）成为现实存在许多挑战；最大的挑战似乎在于难以减少或纠正的噪声和错误量。德克萨斯大学计算机科学家斯科特·亚伦森将其描述为“你试图建造一艘保持不变的船，即使其中的每块木板都腐烂并需要更换。”

那么 NSA 说了什么呢？人们需要记住政府对保密性的需求往往超过个人和私营公司的需求。认为政府可能希望将一些绝密数据保密超过 50 年并不是疯狂的想法。然而，这让许多密码学家感到困惑（例如，参见 Neal Koblitz 和 Alfred J. Menezes 的“A Riddle Wrapped In An Enigma”），他们一直在思考为什么我们要保护自己免受尚不存在或可能永远不会存在的东西的威胁。

无论如何，如果你真的担心并且你的资产的保密性需要长时间保持，增加你正在使用的每个对称加密算法的参数并不是疯狂的，而且相对容易。话虽如此，如果你正在进行密钥交换以获得 AES-256-GCM 密钥，那么非对称加密部分仍然容易受到量子计算机的攻击，仅保护对称加密是不够的。

对于非对称加密，现在还为时过早真正知道什么是安全的。最好等待 NIST 竞赛结束，以获得更多的密码分析，进而对这些新算法更有信心。

目前，已经提出了几种后量子密码系统，包括基于格的密码系统、基于码的密码系统、多元密码系统、基于哈希的签名等。然而，对于大多数这些提议，需要进一步研究以获得对其安全性（特别是针对拥有量子计算机的对手）更多的信心，并改进其性能。

—NIST 后量子密码学提案征集（2017）

如果你太不耐烦，无法等待 NIST 竞赛结果，你可以做的一件事是在你的协议中同时使用当前方案和后量子方案。例如，你可以使用 Ed25519 和 Dilithium 交叉签署消息，换句话说，附加一条消息，带有来自两种不同签名方案的两个签名。如果 Dilithium 被破解，攻击者仍然需要破解 Ed25519，如果量子计算机真的存在，那么攻击者仍然拥有无法伪造的 Dilithium 签名。

注意：这就是 Google 在 2018 年以及 2019 年与 Cloudflare 一起所做的，尝试在 Google Chrome 用户和 Google 以及 Cloudflare 的服务器之间的 TLS 连接中使用混合密钥交换方案。混合方案是 X25519 和一个后量子密钥交换（2018 年的 New Hope，2019 年的 HRSS 和 SIKE）的混合，其中当前密钥交换和后量子密钥交换的输出被混合在一起进入 HKDF 以产生一个共享密钥。

最后，我将再次强调基于哈希的签名已经得到充分研究和理解。尽管它们存在一些开销，像 XMSS 和 SPHINCS+这样的方案现在就可以使用，而且 XMSS 具有即用的标准（RFC 8391 和 NIST SP 800-208）。

概要

• 量子计算机基于量子物理学，可以为特定的计算提供非常大的加速。

• 并非所有算法都可以在量子计算机上运行，也不是所有算法都能与经典计算机竞争。令密码学家担心的两个显著算法是

  • Shor 算法可以高效地解决离散对数问题和因子分解问题。它破坏了大多数当今的非对称密码学。

  • Grover 算法可以有效地搜索 2¹²⁸个值的空间中的密钥或值，影响大多数具有 128 位安全性的对称算法。将对称算法的参数提升到提供 256 位安全性足以抵御量子攻击。

• 后量子密码学领域旨在寻找新的加密算法来替代今天的非对称加密原语（例如，非对称加密、密钥交换和数字签名）。

• NIST 于 2016 年启动了后量子密码学标准化工作。目前有七个决赛选手，该工作现已进入最后一轮选拔阶段。

• 基于哈希的签名是仅基于哈希函数的签名方案。两个主要标准是 XMSS（一种有状态的签名方案）和 SPHINCS+（一种无状态的签名方案）。

• 基于格的密码学是有希望的，因为它提供了较短的密钥和签名。最有前途的两个候选方案基于 LWE 问题：Kyber 是一种非对称加密和密钥交换原语，而 Dilithium 是一种签名方案。

• 还存在其他后量子方案，并作为 NIST 后量子密码学竞赛的一部分提出。这些包括基于代码理论、同源性、对称密钥密码学和多项式的方案。NIST 的竞赛计划于 2022 年结束，这仍然为发现新攻击或优化留下了很大的空间。

• 尚不清楚量子计算机何时能够足够高效地破坏密码学，或者它们是否能够达到那个水平。

• 如果您有长期保护数据的需求，应考虑过渡到后量子密码学：

  • 将所有对称加密算法的使用升级为提供 256 位安全性的参数（例如，从 AES-128-GCM 迁移到 AES-256-GCM，从 SHA-3-256 迁移到 SHA-3-512）。

  • 使用混合方案将后量子算法与前量子算法混合。例如，始终使用 Ed25519 和 Dilithium 对消息进行签名，或始终使用 X25519 和 Kyber 进行密钥交换（从获得的两个密钥交换输出中派生出共享密钥）。

  • 使用像 XMSS 和 SPHINCS+这样基于哈希的签名算法，这些算法经过了深入研究和广泛理解。XMSS 的优势在于已经被 NIST 标准化和批准。

第十五章：这就是全部吗？下一代密码学

本章涵盖

• 通过安全多方计算（MPC）摆脱信任的第三方

• 允许他人对加密数据进行操作通过全同态加密（FHE）

• 通过零知识证明（ZKPs）隐藏程序执行的部分

我开始写这本书的时候，认为大部分章节读完的读者也会对现实世界密码学的未来感兴趣。虽然您正在阅读一个侧重于当今使用的应用和实用书籍，但密码学领域正在迅速变化（例如，最近几年我们看到的加密货币）。

当您阅读本书时，许多理论密码原语和协议正在进入应用密码学领域——也许是因为这些理论原语终于找到了用例，或者是因为它们终于变得足够高效，可以用于实际应用。无论原因是什么，密码学的现实世界肯定在增长并变得更加令人兴奋。在本章中，我通过简要介绍三种原语，为您展示了未来实际密码学可能会是什么样子（也许在未来 10 到 20 年内）：

• 安全多方计算（MPC）—密码学的一个子领域，允许不同参与者一起执行程序，而不必向程序透露自己的输入。

• 全同态加密（FHE）—密码学的圣杯，一种用于允许对加密数据进行任意计算的原语。

• 通用零知识证明（ZKPs）—您在第七章学到的原语，允许您证明自己知道某事而不泄露该事情，但这次更普遍地应用于更复杂的程序。

本章包含了本书中最先进和复杂的概念。因此，我建议您先浏览一下，然后转到第十六章阅读结论。当您有动力想要了解这些更高级概念的内部机制时，请回到这一章。让我们开始吧！

15.1 人越多越热闹：安全多方计算（MPC）

安全多方计算（MPC）是密码学领域的一个子领域，始于 1982 年的著名百万富翁问题。在他 1982 年的论文“用于安全计算的协议”中，Andrew C. Yao 写道：“两位百万富翁想知道谁更富有；然而，他们不想无意中获得有关对方财富的任何额外信息。他们如何进行这样的对话？”简而言之，MPC 是多个参与者一起计算程序的一种方式。但在了解更多关于这种新原语之前，让我们看看它为什么有用。

我们知道，在可信第三方的帮助下，任何分布式计算都可以轻松解决。这个可信第三方可以可能维护每个参与者输入的隐私，同时可能限制计算所透露给特定参与者的信息量。然而，在现实世界中，我们不太喜欢可信第三方；我们知道它们很难找到，并且它们并不总是遵守自己的承诺。

MPC 允许我们完全将可信第三方从分布式计算中移除，并使参与者能够自行计算计算，而不会向彼此透露各自的输入。这是通过一个加密协议完成的。考虑到这一点，在系统中使用 MPC 基本上等同于使用一个可信第三方（见图 15.1）。

图 15.1 安全多方计算（MPC）协议将一个可以通过可信第三方进行计算的分布式计算（左侧图像）转变为一个不需要可信第三方帮助的计算（右侧图像）。

请注意，您已经看到了一些 MPC 协议。阈值签名和分布式密钥生成，涵盖在第八章中，是 MPC 的示例。更具体地说，这些示例是 MPC 的一个子领域，称为阈值密码学，在近年来受到了很多关注，例如，2019 年中期 NIST 启动了阈值密码学的标准化过程。

15.1.1 私有集合交集（PSI）

另一个众所周知的 MPC 子领域是私有集合交集（PSI）的领域，它提出了以下问题：Alice 和 Bob 有一组单词，他们想知道他们有哪些单词（或者可能只是有多少）是共同的，而不暴露各自的单词列表。解决这个问题的一种方法是使用你在第十一章学到的遗忘伪随机函数（OPFR）构造。（我在图 15.2 中说明了这个协议。）如果您回忆起来

1. Bob 为 OPRF 生成一个密钥。

2. Alice 使用 OPRF 协议为她列表中的每个单词获取随机值PRF（key，word）（因此她不会得知 PRF 密钥，Bob 也不会得知这些单词）。

3. 然后 Bob 可以计算他自己单词的PRF（key，word）值列表，并将其发送给 Alice，然后 Alice 可以将其与她自己的 PRF 输出进行比较，以查看 Bob 的任何 PRF 输出是否匹配。

图 15.2 私有集合交集（PSI）允许 Alice 了解她与 Bob 有哪些共同的单词。首先，她会对她列表中的每个单词进行盲化，并使用 OPRF 协议与 Bob 一起对每个单词应用 PRF，使用 Bob 的密钥。最后，Bob 发送给她他的单词与其密钥的 PRF。然后，Alice 可以查看是否有任何匹配项，以了解他们共有哪些单词。

PSI 是一个前景广阔的领域，近年来开始越来越多地得到应用，因为它显示出比过去更实用的特点。例如，Google 的 Chrome 浏览器集成的密码检查功能使用 PSI 来在密码泄露后的密码转储中检测到您的某些密码时向您发出警告，而不实际看到您的密码。有趣的是，微软也为其 Edge 浏览器做了同样的事情，但使用全同态加密（我将在下一节介绍）执行私有集交。另一方面，Signal 消息应用的开发人员（在第十章讨论）认为 PSI 速度太慢，无法执行联系发现，以便根据您手机的联系人列表确定可以与您交谈的人，并且改用了 SGX（在第十三章介绍）作为可信第三方。

15.1.2 通用型多方计算

总的来说，MPC 有许多不同的解决方案，旨在计算任意程序。通用型 MPC 解决方案提供不同级别的效率（从几小时到几毫秒）和不同类型的属性。例如，协议可以容忍多少不诚实的参与者？参与者是恶意的还是只是诚实但好奇（也称为半诚实，是 MPC 协议中的一种参与者类型，他们愿意正确执行协议，但可能试图了解其他参与者的输入）？如果其中一些参与者提前终止协议，那么所有参与者是否都公平？

在使用 MPC 可以安全计算程序之前，需要将其转换为算术电路。算术电路是一系列的加法和乘法，因为它们是图灵完备的，所以它们可以表示任何程序！有关算术电路的说明，请参见图 15.3。

图 15.3 一个算术电路是一些将输入与输出连接起来的加法或乘法门。在图中，数值从左到右传播。例如，d = a + b。在这里，电路只输出一个值 f = a + b + bc，但理论上它可以有多个输出值。请注意，电路的不同输入由不同的参与者提供，但它们也可以是公共输入（为所有人所知）。

在看下一个原语之前，让我给你一个通过 Shamir 的秘密共享构建的（诚实多数）通用型多方计算的简化示例。存在许多更多的方案，但这个方案足够简单，可以在这里进行三步解释：在电路中共享每个输入的足够信息，评估电路中的每个门，以及重构输出。让我们更详细地看看每一步。

第一步是每个参与者对电路的每个输入都有足够的信息。公共输入是公开分享的，而私有输入是通过 Shamir 的秘密共享（在第八章中介绍）分享的。我在图 15.4 中说明了这一点。

图 15.4 通用 MPC 的第一步是使用 Shamir 的秘密共享方案，让参与者分割各自的秘密输入并将部分分发给所有参与者。例如，在这里，Alice 将她的输入 a 分割成 a[1] 和 a[2]。因为在这个例子中只有两个参与者，她将第一个份额给了自己，将第二个份额给了 Bob。

第二步是评估电路的每个门。由于技术原因，我将在这里省略，加法门可以在本地计算，而乘法门必须通过交互方式计算（参与者必须交换一些消息）。对于加法门，只需将您拥有的输入份额相加；对于乘法门，将输入份额相乘。您得到的是一个结果份额，如图 15.5 所示。此时，份额可以交换（以重建输出）或保持分开以继续计算（如果它们代表中间值）。

图 15.5 通用 MPC 的第二步是让参与者计算电路中的每个门。例如，参与者可以通过添加他们拥有的两个输入 Shamir 份额来计算一个加法门，这将产生一个输出的 Shamir 份额。

最后一步是重建输出。此时，参与者应该都拥有输出的一个份额，他们可以使用这个份额来使用 Shamir 的秘密共享方案的最后一步来重建最终输出。

15.1.3 MPC 的现状

在过去的十年中，MPC 的实用性取得了巨大进展。这是一个涵盖许多不同用例的领域，人们应该密切关注可以从这种新型原语中受益的潜在应用。需要注意的是，不幸的是，目前并没有真正的标准化努力，虽然今天有几种 MPC 实现可以被认为对许多用例来说是实用的，但它们并不容易使用。

顺便提一下，在本节前面我解释的通用 MPC 构造是基于秘密共享的，但构造 MPC 协议的方法还有很多。一个著名的替代方案叫做加密电路，这是姚期智在他 1982 年的论文中首次提出 MPC 时提出的一种构造类型。另一个选择是基于全同态加密，这是你将在下一节中了解的一种基本原语。

15.2 完全同态加密（FHE）和加密云的承诺

在密码学领域长期以来，一个问题困扰着许多密码学家：是否可能在加密数据上计算任意程序？想象一下，您可以分别加密值 a、b 和 c，将密文发送到一个服务，然后要求该服务返回 a × 3b + 2c + 3 的加密结果，然后您可以解密它。这里的重要思想是服务永远不会了解您的值，并始终处理密文。这个计算可能不太有用，但是通过加法和乘法，可以在加密数据上计算实际程序。

这个有趣的概念最初是由 Rivest、Adleman 和 Dertouzos 在 1978 年提出的，我们称之为 完全同态加密（FHE）（或者以前被称为 密码学圣杯）。我在图 15.6 中说明了这个密码学原语。

图 15.6 完全同态加密（FHE）是一种加密方案，允许对加密内容进行任意计算。只有密钥的所有者可以解密计算结果。

15.2.1 使用 RSA 加密的同态加密示例

顺便说一句，您已经看到了一些加密方案，应该让您感觉自己知道我在说什么。想想 RSA（在第六章中讨论过）：给定一个 ciphertext = message^e mod N，某人可以轻松计算密文的某些受限函数

n^e × ciphertext = (n × message)^e mod N

他们想要的任何数字（虽然不能太大）。结果是一个解密为

n × message

当然，这并不是 RSA 想要的行为，这导致了一些攻击（例如第六章提到的 Bleichenbacher 的攻击）。在实践中，RSA 通过使用填充方案来打破同态性质。请注意，RSA 仅对乘法同态，这对于计算任意函数是不够的，因为这需要乘法和加法。由于这个限制，我们说 RSA 是 部分同态。

15.2.2 不同类型的同态加密

其他类型的同态加密包括

• 部分同态—意味着对于一种操作（加法或乘法）部分同态，另一种操作在有限的方式上是同态的。例如，加法在一定数量上是无限制的，但只能进行少量乘法。

• 分层同态—可以进行一定次数的加法和乘法。

• 完全同态—加法和乘法无限制（这才是真正的东西）。

在 FHE 的发明之前，提出了几种类型的同态加密方案，但没有一种能够实现完全同态加密所承诺的功能。原因是通过在加密数据上评估电路，一些噪声会增加；在某个点之后，噪声已经达到了使解密变得不可能的阈值。多年来，一些研究人员试图证明也许有一些信息理论可以表明完全同态加密是不可能的；直到被证明是可能的。

15.2.3 启动引导，完全同态加密的关键

一天晚上，爱丽丝梦见了巨大的财富，洞穴里堆满了银、金和钻石。然后，一只巨龙吞噬了财富，并开始吃自己的尾巴！她醒来时感到平静。当她试图理解她的梦时，她意识到她已经找到了解决问题的方法。

—克雷格·根特里（“计算加密数据的任意函数”，2009）

2009 年，丹·博内的博士生克雷格·根特里提出了有史以来第一个完全同态加密构造。根特里的解决方案被称为启动引导，实际上是每隔一段时间在密文上评估解密电路，以将噪声降低到可管理的阈值。有趣的是，解密电路本身不会泄露私钥，并且可以由不受信任的一方计算。启动引导允许将分层的 FHE 方案转变为 FHE 方案。根特里的构造速度很慢且相当不切实际，每个基本位操作大约需要 30 分钟，但与任何突破一样，随着时间的推移变得更好。它还表明完全同态加密是可能的。

启动引导是如何工作的？让我们看看是否能获得一些见解。首先，我需要提到我们不需要对称加密系统，而是需要一个公钥加密系统，其中公钥可用于加密，私钥可用于解密。现在，想象一下，你在一个密文上执行了一定数量的加法和乘法运算，并达到了一定的噪声水平。噪声足够低，仍然可以正确解密密文，但太高了，不会让你执行更多同态操作而不破坏加密内容。我在图 15.7 中说明了这一点。

图 15.7 在使用完全同态加密算法加密消息后，对其进行操作会将其噪声增加到危险的阈值，解密变得不可能。

你可能认为自己陷入了困境，但启动引导通过从那个密文中去除噪声来解决问题。为此，你需要使用另一个公钥（通常称为启动引导密钥）重新加密有噪声的密文，以获得该有噪声的密文的加密。请注意，新的密文没有噪声。我在图 15.8 中说明了这一点。

图 15.8 在图 15.7 的基础上，为了消除密文的噪声，你可以对其进行解密。但是因为你没有秘密密钥，所以你将嘈杂的密文重新加密在另一个公钥下（称为引导密钥）以获得一个新的密文，该密文是没有错误的嘈杂密文。

现在来到了魔法的部分：你被提供了初始的私钥，但不是以明文形式，而是在那个引导密钥下加密的。这意味着你可以使用解密电路与同态地解密内部带有噪声的密文。如果解密电路产生的噪声量是可接受的，那么它就起作用了，你将得到第一个同态操作的结果，其密文是在引导密钥下加密的。我在图 15.9 中进行了说明。

图 15.9 在图 15.9 的基础上，你使用了初始的加密到引导密钥的秘密密钥来对新的密文应用解密电路。这有效地在原地解密了带有噪声的密文，消除了错误。由于解密电路，会产生一定数量的错误。

如果剩余的错误量允许你至少进行一次同态操作（+或×），那么你就成功了：你拥有一个完全同态加密算法，因为你可以始终在实践中在每个操作之后或之前运行引导。请注意，你可以将引导密钥对设置为与初始密钥对相同。这有点奇怪，因为你会得到一些循环安全问题，但似乎它可以运行，且没有已知的安全问题。

15.2.4 基于学习中的错误问题的 FHE 方案

在继续之前，让我们看一个基于我们在第十四章中看到的学习中的错误问题的 FHE 方案的示例。我将解释一个简化版本的 GSW 方案，以作者 Craig Gentry、Amit Sahai 和 Brent Waters 的名字命名。为了保持简单，我将介绍算法的秘密密钥版本，但请记住，将这样的方案转换为我们需要的公钥变体是相对简单的，这是我们用于引导的。看看下面的方程式，其中C是一个方阵，s是一个向量，而m是一个标量（一个数字）：

Cs = ms

在这个方程中，s被称为eigenvector而m被称为eigenvalue。如果这些词对你来说很陌生，不用担心；它们在这里并不重要。

我们 FHE 方案中的第一个直觉是通过观察特征向量和特征值得到的。观察到的是，如果我们将m设置为要加密的单个位，C设置为密文，s设置为秘密密钥，则我们有一个（不安全的）同态加密方案来加密一个位。 （当然，我们假设存在一种方法从固定位m和固定秘密密钥s获取随机密文C。）我在图 15.10 中以一种乐高方式进行了说明。

图 15.10 我们可以通过将 m 解释为一个特征值，s 解释为一个特征向量，然后找到关联矩阵 C 来生成一个不安全的同态加密方案，该方案将密文。

要解密密文，您需要用秘密向量 s 乘以矩阵，然后查看是否获得了秘密向量或 0。您可以验证该方案是完全同态的，方法是检查两个密文加在一起的解密结果是否是相应位相加的结果：

(C[1] + C[2])s = C[1]s + C[2]s = b[1]s + b[2]s = (b[1] + b[2])s

此外，两个密文相乘的解密结果 (C[1] × C[2]) 是相应位相乘的结果：

(C[1] × C[2])s = C[1] (C[2]s) = C[1] (b[2]s) = b[2]C[1]s = (b[2] × b[1]) s

不幸的是，该方案不安全，因为很容易从 C 中检索出特征向量（秘密向量 s）。增加一点噪声呢？我们可以稍微改变这个方程，使它看起来像我们的误差学习问题：

Cs = ms + e

这应该更加熟悉了。同样，我们可以验证加法仍然是同态的：

(C[1] + C[2])s = C[1]s + C[2]s = b[1]s + e[1] + b[2]s + e[2] = (b[1] + b[2])s + (e[1]+e[2])

在这里，注意到误差正在增加（e[1] + e[2]），这正是我们预期的。我们还可以验证乘法仍然有效：

(C[1] × C[2])s = C[1] (C[2]s) = C[1] (b[2]s + e[2]) = b[2]C[1]s + C[1]e[2] = b[2] (b[1]s + e[1]) + C[1]e[2]

= (b[2] × b[1]) s + b[2]e[1] + C[1]e[2]

在这里，b[2]e[1] 很小（因为它要么是 e[1] 要么是 0），但 C[1]e[2] 可能很大。这显然是一个问题，我会忽略它以避免深入研究细节。如果你有兴趣了解更多，请务必阅读沙伊·哈莱维（Shai Halevi）于 2017 年发表的《同态加密》报告，该报告在解释所有这些内容及更多内容方面做得非常出色。

15.2.5 它在哪里使用？

FHE 最被吹捧的用例一直是云。如果我可以继续将我的数据存储在云中而不被看到怎么办？而且，此外，如果云可以在加密数据上提供有用的计算呢？事实上，人们可以想到许多应用场景可以使用 FHE。一些例子包括

• 垃圾邮件检测器可以扫描您的电子邮件而不看这些内容。

• 可以对您的 DNA 进行遗传研究，而无需实际存储和保护您的隐私敏感人类编码。

• 数据库可以加密存储，并且在服务器端进行查询而不泄露任何数据。

然而，菲利普·罗加韦在他 2015 年关于“密码工作的道德性质”的开创性论文中指出，“全同态加密[…]引发了一波新的狂热。在资助提案、媒体采访和演讲中，领先的理论家们谈论全同态加密[…]作为我们取得进展的标志性迹象。没有人似乎强调这种假设性的东西是否会对实践产生任何影响。”

尽管罗加韦并没有错，全同态加密仍然非常缓慢，但该领域的进展令人兴奋。截至撰写本文时（2021 年），操作速度比正常操作慢约十亿倍，但自 2009 年以来，已经有了 10⁹倍的加速。毫无疑问，我们正在朝着未来的方向前进，至少对于某些有限的应用来说，全同态加密将成为可能。

此外，并非每个应用都需要全面的原语；有些同态加密可以在广泛的应用中使用，比全同态加密更有效。一个理论密码原语进入现实世界的一个良好指标是标准化，而事实上，全同态加密并不陌生于此。homomorphicencryption.org的标准化工作包括许多大公司和大学。目前尚不清楚全同态加密何时、何地以及以何种形式进入现实世界。但可以肯定的是，它将会发生，敬请关注！

15.3 通用零知识证明（ZKPs）

第七章中我谈到了零知识证明（ZKPs）与签名有关。在那里，我指出签名类似于离散对数的非交互式 ZKPs。这种 ZKPs 是由沙菲·戈德瓦塞、席尔维奥·米卡利和查尔斯·拉科夫教授于上世纪 80 年代中期发明的。不久之后，戈德雷希、米卡利和威格德森发现我们不仅可以证明离散对数或其他类型的难题，还可以证明任何程序的正确执行，即使我们删除了一些输入或输出（参见图 15.11 的示例）。本节重点讨论这种通用类型的 ZKP。

图 15.11 通用 ZKPs 允许证明者说服验证者关于执行轨迹的完整性（程序的输入以及执行后获得的输出），同时隐藏了计算中涉及的一些输入或输出。一个例子是证明者试图证明数独可以被解决。

自其早期以来，ZKP 作为一个领域已经有了巨大的增长。这种增长的一个主要原因是加密货币的繁荣以及对链上交易提供更多保密性以及优化空间的需求。截至撰写本文时，ZKP 领域仍然以极快的速度增长，很难跟上现代方案的发展以及通用 ZKPs 的类型。

幸运的是，这个问题变得足够严重，已经触发了标准化阈值，一条虚拟线，一旦达到，几乎总是会激励一些人共同努力，以澄清该领域。2018 年，来自行业和学术界的人士联合起来，成立了 ZKProof 标准化工作组，旨在“标准化使用加密零知识证明”。直至今日，这仍然是一个正在进行的工作。您可以在zkproof.org上阅读更多信息。

您可以在许多不同的情况下使用通用型 ZKPs，但据我所知，迄今为止它们主要已被用于加密货币领域，可能是因为对密码学感兴趣并愿意尝试最前沿技术的人数众多。尽管如此，通用型 ZKPs 在许多领域都有潜在应用：身份管理（能够证明您的年龄而不暴露它）、压缩（能够隐藏大部分计算）、机密性（能够隐藏协议的某些部分）等等。更多应用采用通用型 ZKPs 的最大障碍似乎是以下几点：

• 大量的 ZKP 方案以及每年都有更多方案被提出。

• 理解这些系统如何工作以及如何将它们用于特定用例的困难。

不同提议方案之间的区别非常重要。由于这是一个极易引起混淆的来源，这是一些方案被分割的方式：

• 零知识或非零知识—如果某些信息需要对某些参与者保密，那么我们需要零知识性。注意，无秘密的证明也可能有用。例如，您可能想将一些密集计算委托给一个服务，而该服务又必须向您证明他们提供的结果是正确的。

• 交互式或非交互式—大多数 ZKP 方案可以变成非交互式的（有时使用我在第七章中讨论的 Fiat-Shamir 变换），而协议设计者似乎最感兴趣的是该方案的非交互式版本。这是因为在协议中来回传输的信息可能会耗费时间，但也因为有时交互性可能不可行。所谓的非交互式证明通常被称为NIZKs，代表非交互式 ZKPs。

• 简洁证明或非简洁证明—聚光灯下的大多数 ZKP 方案通常被称为zk-SNARKs，代表零知识简洁非交互知识证明。尽管定义可能有所不同，但它着重于这些系统生成的证明的大小（通常在数百字节的数量级），以及验证这些证明所需的时间（在毫秒级范围内）。zk-SNARKs 因此简短且易于用于验证 ZKPs。请注意，一个方案不是 zk-SNARK 并不意味着它在现实世界中无法使用，因为通常在不同的用例中可能有用的不同属性。

• 透明的设置或不是—像每个密码原语一样，ZKP 需要一种设置来同意一组参数和公共值。这称为共同参考字符串（CRS）。但是，ZKP 的设置可能比最初想象的限制或危险得多。有三种类型的设置：

  • 可信任的—意味着创建 CRS 的人也可以访问允许他们伪造证明的秘密（因此，这就是为什么这些秘密有时被称为“有毒废物”的原因）。这是一个相当严重的问题，因为我们又回到了需要信任的第三方，然而具有这种属性的方案通常是效率最高且证明大小最短的。为了降低风险，MPC 可以用于让许多参与者帮助创建这些危险的参数。如果单个参与者是诚实的，并在典礼结束后删除他们的密钥，那么有毒废物就会被清除。

  • 通用的—如果信任的设置被称为通用，则您可以使用它来证明任何电路的执行（受某些大小限制）。否则它是特定于单个电路的。

  • 透明的—对于我们来说，幸运的是，许多方案也提供透明的设置，这意味着不需要存在信任的第三方来创建系统的参数。透明的方案按设计是通用的。

• 是否抗量子—一些 ZKP 利用公钥加密和高级原语，如双线性配对（稍后我会解释），而另一些则仅依赖对称加密（如哈希函数），这使它们在本质上抗量子计算（通常以更大的证明为代价）。

由于在撰写本文时，zk-SNARKs 备受关注，让我向您解释一下它们的工作原理。

15.3.1 zk-SNARKs 的工作原理

首先，有许多许多 zk-SNARK 方案—实际上有太多了。大多数都建立在这种类型的构造之上：

• 一个证明系统，允许证明者向验证者证明某些事情。

• 程序的翻译或编译为证明系统可以证明的东西。

第一部分并不太难理解，而第二部分在某种程度上需要一个研究生课程的知识。首先，让我们来看看第一部分。

zk-SNARKs 的主要思想是证明您知道一些多项式f(x)具有一些根。根的意思是验证者心中有一些值（例如，1 和 2），证明者必须证明他们心中的秘密多项式对这些值（例如，f(1) = f(2) = 0）进行评估为 0。顺便说一句，一个具有 1 和 2 作为根的多项式（如我们的例子）可以写为f(x) = (x – 1)(x – 2)h(x)，其中h(x)是某个多项式。 （如果你不相信，请尝试在x = 1 和x = 2 处评估它。）我们说证明者必须证明他们知道一个f(x)和h(x)，使得f(x) = t(x)h(x)，其中t(x) = (x – 1)(x – 2)是目标多项式。在这个例子中，1 和 2 是验证者想要检查的根。

但就是这样！这就是 zk-SNARKs 证明系统通常提供的东西：证明你知道某些多项式。我再次强调这一点，因为我第一次了解这个概念时觉得很难理解。如果你只能证明你知道一个多项式，你怎么能证明你知道程序的某个秘密输入呢？好吧，这就是 zk-SNARK 的第二部分如此困难的原因。它涉及将程序转化为多项式。但稍后再详述。

回到我们的证明系统，如何证明他们知道这样一个函数f(x)？他们必须证明他们知道一个h(x)，使得你可以将f(x)写成f(x) = t(x)h(x)。啊，… 别那么快。我们说的是零知识证明，对吧？我们怎么能在不泄露f(x)的情况下证明这一点？答案就在以下三个技巧中：

• 同态承诺——类似于我们在其他零知识证明中使用的承诺方案（在第七章中讨论）

• 双线性配对——一种具有一些有趣特性的数学构造；稍后详述

• 大多数情况下，不同的多项式求值不同

所以让我们逐个看看这些，好吗？

15.3.2 同态承诺以隐藏证明的部分

第一个技巧是使用承诺来隐藏我们发送给证明者的值。但我们不仅要隐藏它们，还要允许验证者对它们执行一些操作，以便他们可以验证证明。具体来说，他们需要验证，如果证明者对他们的多项式f(x)以及h(x)进行承诺，那么我们就有

com(f(x)) = com(t(x)) com(h(x)) = com(t(x)h(x))

其中承诺com(t(x))由验证者计算为多项式上的约束。这些操作称为同态操作，如果我们使用哈希函数作为承诺机制（如第二章所述），我们无法执行这些操作。由于这些同态承诺，我们可以“隐藏指数中的值”（例如，对于值v，发送承诺g^v mod p）并执行有用的身份验证：

• 承诺的等式——等式g^a = g^b 意味着 a = b

• 承诺的添加——等式g^a = g^b*g*c 意味着 a = b + c

• 承诺的缩放——等式g^a = (g^b)c 意味着 a = bc

注意，最后一个检查只有在c是公共值而不是一个承诺（gc）时才有效。仅通过同态承诺，我们无法检查承诺的乘法，这正是我们所需的。幸运的是，密码学有另一个工具可以将这样的方程式隐藏在指数中——双线性配对。

15.3.3 双线性配对以改进我们的同态承诺

双线性配对可用于解除我们的阻碍，这是我们在 zk-SNARK 中使用双线性配对的唯一原因（真的，只是为了能够在承诺内部相乘的值）。我不想深入讨论什么是双线性配对，但只需知道它是我们工具箱中的另一个工具，允许我们将以前无法相乘的元素从一个群移到另一个群。

使用 e 作为写双线性配对的典型方式，我们有 e(g[1], g[2]) = h[3]，其中 g[1]、g[2] 和 h[3] 是不同群的生成器。在这里，我们将在左侧使用相同的生成器（g[1] = g[2]），这使得配对对称。我们可以使用双线性配对通过这个方程来执行指数中隐藏的乘法：

e(g^b, g^c) = e(g)^(bc)

再次，我们使用双线性配对使得我们的承诺不仅对加法是同态的，而且对乘法也是同态的。（请注意，这不是一个完全同态的方案，因为乘法仅限于单个乘法。）双线性配对也用于密码学的其他地方，并且正在逐渐成为更常见的构建块。它们可以在同态加密方案中看到，也可以在像 BLS（我在第八章提到的）这样的签名方案中看到。

15.3.4 紧凑性来自何处？

最后，zk-SNARK 的紧凑性来自于两个不同函数的评估大多数情况下会得到不同的点。这对我们意味着什么？假设我没有一个多项式 f(x) 真正具有我们与验证者选择的根，这意味着 f(x) 不等于 t(x)h(x)。然后，在随机点 r 上评估 f(x) 和 t(x)h(x) 不会大部分时间返回相同的结果。对于几乎所有的 r，f(r)≠ t(r)h(r)。这就是Schwartz-Zippel 引理，我在图 15.12 中有所说明。

图 15.12 Schwartz-Zippel 引理指出，两个不同的 n 次多项式最多可以在 n 个点相交。换句话说，两个不同的多项式在大多数点上会有所不同。

了解这一点，证明 com(f(r)) = com(t(r)h(r)) 对于某个随机点 r 就足够了。这就是为什么 zk-SNARK 证明如此小的原因：通过比较群中的点，最终你会比较更大的多项式。但这也是大多数 zk-SNARK 构造中需要可信设置的原因。如果证明者知道将用于检查等式的随机点 r，那么他们可以伪造一个无效的多项式，仍然会验证相等。因此，可信设置就是

1. 创建一个随机值 r

2. 承诺不同幂次的 r（例如，g, g^r, g^(r²), g^(r³)，等等），以便证明者可以计算他们的多项式而不知道点 r

3. 销毁值 r

第二点有意义吗？如果我作为证明者的多项式是f(x) = 3x² + x + 2，那么我所要做的就是计算(g^(r²))³ g^r g²，以获得我在那个随机点r处评估的多项式的承诺（不知道r）。

15.3.5 从程序到多项式

到目前为止，证明者必须找到的多项式的约束是它需要有一些根：一些用我们的多项式计算为 0 的值。但是我们如何将一个更一般的语句转换成多项式知识证明？目前最多使用 zk-SNARKs 的应用是加密货币，其中典型的语句的形式为：

• 证明一个值在范围[0, 2⁶⁴]内（这被称为范围证明）

• 证明一个（秘密）值包含在给定的（公开）Merkle 树中

• 证明某些值的和等于另一些值的和

• 依此类推

这就是困难的部分所在。正如我之前所说，将程序执行转换为多项式的知识是非常困难的。好消息是我不会告诉你所有的细节，但我会告诉你足够让你了解事情的工作原理。从那里开始，你应该能够理解我解释中缺少的部分，并根据自己的需要填补缺漏。接下来将会发生以下事情：

1. 我们的程序将首先被转换成算术电路，就像我们在 MPC 部分看到的那样。

2. 那个算术电路将被转换成一种特定形式的方程组（称为秩-1 约束系统或 R1CS）。

3. 然后我们使用一个技巧将我们的方程组转换为一个多项式。

15.3.6 程序适用于计算机；我们需要算术电路而不是

首先，让我们假设几乎任何程序都可以更多或更少地轻松地用数学重写。为什么我们想这样做的原因应该是显而易见的：我们不能证明代码，但我们可以证明数学。例如，以下列表提供了一个函数，其中除了a是我们的秘密输入之外，每个输入都是公开的。

列表 15.1 一个简单的函数

fn my_function(w, a, b) {
  if w == true {
    return a * (b + 3);
   } else {
    return a + b;
   }
}

在这个简单的例子中，如果除了a之外的每个输入和输出都是公开的，人们仍然可以推断出a是什么。这个列表也是一个例子，说明你不应该试图在零知识中证明什么。无论如何，该程序可以用以下方程重写成数学形式：

w × (a × (b + 3)) + (1 – w) × (a + b) = v

其中v是输出，w要么是 0（false）要么是 1（true）。请注意，这个方程实际上不是一个程序或电路，它只是一个约束条件。如果你正确执行程序，然后填写方程中得到的输入和输出，等式应该是正确的。如果等式不正确，那么你的输入和输出就不对应于程序的有效执行。

这就是你必须思考这些通用零知识证明的方式。我们不是在零知识中执行一个函数（实际上这并没有什么意义），而是使用 zk-SNARKs 来证明一些给定的输入和输出正确地匹配了程序的执行，即使其中一些输入或输出被省略了。

15.3.7 从算术电路到 rank-1 约束系统（R1CS）

无论如何，我们只是将我们的执行转换为可以用 zk-SNARKs 证明的东西的过程中的一步。下一步是将其转换为一系列约束条件，然后可以将其转换为证明某个多项式的知识。zk-SNARKs 想要的是rank-1 约束系统（R1CS）。一个 R1CS 实际上只是一系列形式为L × R = O的方程，其中L、R和O只能是一些变量的加法，因此唯一的乘法是在L和R之间。我们为什么需要将我们的算术电路转换为这样的方程系统其实并不重要，除了在将其转换为最终可以证明的东西时会有所帮助。尝试用我们的方程做这个，我们得到的东西就像是

• a × (b + 3) = m

• w × (m – a – b) = v – a – b

我们实际上忘记了w只能是 0 或 1 的约束条件，我们可以通过一个巧妙的技巧来将其添加到我们的系统中：

• a × (b + 3) = m

• w × (m – a – b) = v – a – b

• w × w = w

有意义吗？你真的应该将这个系统看作一组约束条件：如果你给我一组值，声称这些值与我程序的输入和输出匹配，那么我应该能够验证这些值也正确地验证了等式。如果其中一个等式是错误的，那么这必须意味着该程序没有输出你给我的这些输入的值。另一种思考方式是，zk-SNARKs 允许你可验证地删除程序正确执行的传输的输入或输出。

15.3.8 从 R1CS 到多项式

问题仍然是：我们如何将这个系统转化为一个多项式？我们已经快要完成了，而且一如既往的答案是通过一系列的技巧！因为我们的系统中有三个不同的方程，第一步是为我们的多项式确定三个根。我们可以简单地选择 1、2、3 作为根，这意味着我们的多项式对x = 1、x = 2 和x = 3 都解出了f(x) = 0。为什么这样做？通过这样做，我们可以使我们的多项式同时代表我们系统中的所有方程，通过在 1 处求值时代表第一个方程，在 2 处求值时代表第二个方程，依此类推。现在验证者的工作是创建一个多项式f(x)，使得：

• f(1) = a × (b + 3) – m

• f(2) = w × (m – a – b) – (v – a – b)

• f(3) = w × w – w

请注意，如果这些方程的值正确匹配我们原始程序的执行，所有这些方程应该评估为 0。换句话说，我们的多项式f(x)只有在我们正确创建它时才有根 1、2、3。记住，这就是 zk-SNARK 的全部意义：我们有协议来证明，确实，我们的多项式f(x)有这些根（由证明者和验证者都知道）。

如果我的解释到此为止就太简单了，因为现在的问题是证明者在选择他们的多项式f(x)时有太多的自由。他们可以简单地找到一个具有根 1、2、3 的多项式，而不关心值a、b、m、v和w。他们可以做任何他们想做的事情！相反，我们想要的是一个系统，锁定多项式的每个部分，除了验证者必须不了解的秘密值。

15.3.9 两个人评估隐藏在指数中的多项式

让我们回顾一下，我们希望一个证明者必须使用他们的秘密值a和公共值b和w正确执行程序，并获得他们可以发布的输出v。然后，证明者必须创建一个多项式，只填写验证者不应该了解的部分：值a和m。因此，在一个真正的 zk-SNARK 协议中，当证明者创建他们的多项式并将其评估到一个随机点时，你希望证明者在创建他们的多项式时拥有尽可能少的自由。

为了做到这一点，多项式是通过让证明者只填写他们的部分而在一定程度上动态地创建的，然后让验证者填写其他部分。例如，让我们以第一个方程为例，f(1) = a × (b + 3) – m，表示为

f1 = aL1 × (b + 3)R1 – mO1

其中L1、R1、O1 是多项式，当x = 1 时评估为 1，当x = 2 和x = 3 时评估为 0。这是必要的，以便它们只影响我们的第一个方程。（请注意，通过拉格朗日插值等算法很容易找到这样的多项式。）现在，请注意另外两点：

• 我们的多项式的系数是输入、中间值和输出。

• 多项式f(x)是和 f1 + f2 + f3 的总和，其中我们可以定义f2 和f3 来表示方程 2 和 3，类似于f1。

正如你所看到的，我们的第一个方程仍然在点x = 1 处表示：

f(1) = f1 + f2 + f3

= f1

= aL1 × (b + 3)R1 – mO1

= a × (b + 3) – m

采用这种新的表示方程的方式（记住，表示我们程序执行的方程），证明者现在可以通过以下方式评估与他们相关的多项式的部分：

1. 对隐藏在指数中的随机点r进行指数运算，以重构多项式L1 和O1

2. 对秘密值a进行指数运算 g^{(L1)以获得(g}(L1))^a = g^(aL1)，表示a × L1 在未知且随机点x = r处的评估，并隐藏在指数中。

3. 对秘密中间值m进行指数运算 g^{(O1)以获得(g}(O1))^m = g^(mO1)，表示在随机点r处评估mO1，并隐藏在指数中。

验证者可以通过使用与证明者相同的技术，重建(g^(R1))b 和(g^(R0))³来填补缺失的部分，其中b是一个已同意的值。将两者相加，验证者得到 g^(bR1) + g^(3R1)，表示在未知且随机点x = r处(b + 3) × R1 的（隐藏）评估。最后，验证者可以通过使用双线性配对重建隐藏在指数中的f1：

e(g^(aL1), g^((b+3)R1)) – e(g, g^(mO1)) = e(g, g)^(aL1) × (b + 3)R1 – mO1

如果将这些技术推广到整个多项式f(x)，你可以了解最终的协议。当然，这仍然是对真实 zk-SNARK 协议的严重简化；这仍然给证明者留下了太多的权力。

zk-SNARKs 中使用的所有其他技巧都旨在进一步限制证明者的行为，确保他们正确且一致地填补缺失的部分，并优化可以优化的部分。顺便说一句，我读过的最好的解释是 Maksym Petkus 的论文《zk-SNARK 为什么以及如何工作：权威解释》，该论文深入探讨了我忽视的所有部分。

这就是 zk-SNARKs 的全部内容。这实际上只是一个介绍；在实践中，了解和使用 zk-SNARKs 要复杂得多！将程序转换为可被证明的东西的工作量不仅仅是非平凡的，有时还会对密码协议添加新的约束。例如，主流的哈希函数和签名方案通常对于通用 ZKP 系统来说过于重型，这导致许多协议设计者研究了不同的 ZKP 友好方案。此外，正如我之前所说的，有许多不同的 zk-SNARKs 构造，还有许多不同的非 zk-SNARKs 构造，根据您的用例，后者可能更相关作为通用 ZKP 构造。

不幸的是，并不存在一种大小适合所有的 ZKP 方案（例如，具有透明设置、简洁、通用和抗量子的 ZKP 方案），目前尚不清楚在哪些情况下使用哪种方案。该领域仍然很年轻，每年都会发布新的更好的方案。也许几年后会出现更好的标准和易于使用的库，所以如果你对这个领域感兴趣，继续关注吧！

总结

• 在过去的十年中，许多理论密码学原语在效率和实用性方面取得了巨大进步；其中一些正在逐渐走向现实世界。

• 安全多方计算（MPC）是一种原语，允许多个参与者共同正确执行程序，而不暴露各自的输入。阈值签名正在开始在加密货币中被采用，而私密集合交集（PSI）协议正在被用于现代和大规模协议，如谷歌的密码检查。

• 完全同态加密（FHE）允许在不解密的情况下对加密数据进行任意函数计算。它在云中具有潜在应用，可以防止除用户之外的任何人访问数据，同时允许云平台对数据进行用户有用的计算。

• 通用零知识证明（ZKPs）已经找到了许多用例，并且在快速验证小证明方面取得了最近的突破。它们主要用于加密货币，以增加隐私或压缩区块链的大小。然而，它们的用例似乎更广泛，随着更好的标准和更易于使用的库进入现实世界，我们可能会看到它们被越来越广泛地使用。