密钥密码学（三）

原文：annas-archive.org/md5/b5abcf9a07e32fc6f42b907f001224a1

译者：飞龙

协议：CC BY-NC-SA 4.0

第十六章：三次通行协议

本章内容包括

• 基于指数的三次通行协议

• 基于矩阵乘法的三次通行协议

• 基于双边矩阵乘法的三次通行协议

第 2.2 节和第 2.3 节描述了现代密码学分为 3 个分支，即秘密密钥、公钥和个人密钥。到目前为止，本书仅描述了秘密密钥密码学的方法。公钥密码学在许多书中有描述，因此这里不会涉及。本章将讨论个人密钥密码学，这是密码学的较不为人知的第三个分支。个人密钥密码学有时被称为无密钥密码学，因为各方不需要传输或共享任何密钥。

个人密钥密码学的基本概念是，两个通信者 Sandra 和 Riva 各自有自己的个人密钥。这个密钥永远不会被传输或与任何其他人共享，甚至不会与彼此共享，因此没有可能通过窃听、拦截广播或任何其他形式的窃听来了解任何个人密钥。个人密钥密码学的巨大优势是你不需要提前设置任何东西。不需要有任何秘密、安全的通道来交换密钥。消息可以在公共通道上交换。不需要密钥服务器或其他基础设施。

个人密钥密码学是通过三次通行协议实现的，该协议是由以色列魏茨曼学院的阿迪·沙米尔于大约 1975 年发明的。为了说明这种方法，我想出了一个小故事：

曾经有一位国王爱上了邻国的女王。为了追求女王，国王希望送她一颗珍贵的宝石。国王有一个坚固的保险箱和一个防拆锁。但是他怎么能送钥匙呢？如果信使既有钥匙又有保险箱，他就可以打开箱子并偷走宝石。国王可以用第二位信使送钥匙，但他担心两位信使会在途中相遇并一起偷走宝石。女王提出了一个巧妙的解决方案。

国王会在保险箱上放上他的锁，并将其发送给王后。然后她会添加自己的锁，并带着两把锁把保险箱送回来。国王然后用自己的钥匙取下他的锁，并只带着王后的锁把保险箱送回来。然后她可以用自己的钥匙打开箱子并拿到宝石。

这里的两把锁代表两个加密，两把钥匙代表相应的解密。消息将使用发送者的加密函数加密，发送给接收者，使用接收者的加密函数加密，发送回发送者，使用发送者的解密函数解密，发送回接收者并使用接收者的解密函数解密。这意味着消息发送了 3 次，因此称为三次通行协议。

*****让我们来分解一下。假设消息是 M，Sandra 的加密和解密函数分别是 S 和 S’，Riva 的加密和解密函数分别是 R 和 R’。在第一次传递中，Sandra 用她的加密函数 S 加密消息 M 并将 SM 发送给 Riva。在第二次传递中，Riva 用她自己的加密函数 R 加密消息 SM 并将双重加密消息 RSM 发送回 Sandra。在第三次传递中，Sandra 将她的解密函数 S’应用于消息 RSM 以获得 S’RSM。这旨在去除 S 加密。只有当 R 和 S 可交换，或者 S’和 R 可交换时，才能实现这一点。这意味着 S’RSM = RS’SM = RM。这使得 Riva 可以去除她的加密并读取消息。

因此，为了使这个三次传递方案起作用，我们需要找到一个可交换的加密函数，或者两个彼此可交换的加密函数。我能立刻想到 3 个可交换的加密函数：加法、乘法和异或。很容易想象出一种加密方式，其中密钥与消息长度相同，加密包括逐字节将密钥加到消息中，或将消息字节乘以密钥字节，或将消息与密钥进行异或。这些都是一次性密码的简单形式。

这些都不安全。如果 Emily 设法获取所有三条加密消息，她可以轻松地去除加密。如果函数是加法，那么 3 条消息分别是 M+S、M+S+R 和 M+R。如果 Emily 将第一条和第三条消息相加，然后减去第二条消息，她会得到(M+S)+(M+R)-(M+S+R) = M。结果正是 M。当加密函数是乘法时，同样的方法也适用。3 条消息分别是(M×S)、(M×R)和(M×S×R)。再次进行(M×S)×(M×R)÷(M×S×R)运算得到 M。当加密函数是异或时，找到 M 甚至更简单，因为异或是其自身的逆运算。只需将 3 条加密消息进行异或运算，结果就是原始消息，(M⊕S)⊕(M⊕R)⊕(M⊕S⊕R) = M。

可交换的两个加密函数是替换和置换。这些也是不安全的。由于 Emily 会看到置换前后的消息，她可以轻易确定置换。

所需的是一对可交换的加密函数 S 和 R，使得即使 Emily 拥有 SM、RSM 和 RM，她也无法确定 M。

16.1 Shamir 的方法

Shamir 解决这个问题的方法是使用指数。设 p 是一个大素数，比如在 300 到 600 位十进制数字范围内。Sandra 将选择一个加密指数 s。相应的解密指数是 s’，使得 ss’≡1 (mod p-1)。这是根据费马小定理得出的，如果 0<a<p，则 a^(p-1)≡1 (mod p)。第 14.4.2 节描述了如何选择素数 p，第 15.4 节描述了如何确定 s’。同样，Riva 选择她的加密和解密指数 r 和 r’。这两个加密是可交换的，因为(M^s)r = M^(sr) = M^(rs) = (M^r)s。

Sandra 计算(M^s mod p)并将其发送给 Riva。Riva 计算(M^(sr) mod p)并将其发送回 Sandra。Sandra 计算(M^(srs)’ mod p) = (M^r mod p)并将其发送回 Riva，最终 Riva 计算(M^(rr)’ mod p) = M，这就是原始消息。这种方法被认为是安全的，因为确定 s 或 r 需要解决离散对数问题。正如第 14.4 节所讨论的，这个问题被认为在计算上是困难的。目前没有已知的可计算的算法。

这种方法非常慢。所有这些大数的指数运算和模数减少需要大量计算。下一节描述了一种解决方案的尝试。

16.2 Massey-Omura

Massey-Omura方法是由 ETH Zurich 的 James Massey 和 UCLA 的 Jim K. Omura 于 1982 年发明的。（他的名字在专利上列为 Jimmy Omura。他是我在 MIT 的同学，尽管我不记得他。）Massey-Omura 系统与 Shamir 系统本质上相同，只是模数的形式为 2^k。这意味着模 2^k 的余数可以通过简单地取数字的低 k 位来计算。这比计算模 p 的余数要快得多，后者基本上是通过使用这些 300 到 600 位数字进行长除法来完成的。

哪种方法更快的问题在几年来一直在计算机协会（ACM）和电气电子工程师学会（IEEE）的出版物中激烈讨论。

16.3 离散对数

Diffie-Hellman 密钥交换、Shamir 三次协议和 Massey-Omura 方法的安全性都取决于解决离散对数问题的难度。解决这个问题的三种流行算法是穷举枚举，适用于 10¹²，Daniel Shanks 的 baby-step giant-step 算法，适用于 10¹⁸，以及 John Pollard 的 rho 算法，适用于 10²²。然而，我们需要一个适用于 10³⁰⁰的算法。为了让人们对离散对数问题的困难有所了解，让我们看看一个解决它的复合方法。这不是你可以在家用个人电脑完成的事情。这需要一个具有大量存储空间的大型计算机，或者一个由许多个人合作工作的网络。或者，你可以跳过这一部分，只是接受离散对数问题是困难的。

16.3.1 对数

首先考虑在计算机出现之前人们如何计算普通对数。一种方法是取一个数字 b = 1.000001，费力地计算它的连续幂。你会发现 b⁶⁹³¹⁴⁸是最接近 2 的幂，而 b²³⁰²⁵⁸⁶是最接近 10 的幂。然后你会知道 log10 几乎是 693148/2302586，即 0.3010302。正确值是 0.3010300，所以这种方法给出了一个很好的近似值。

您可以在一个环中进行相同的操作，比如取模某个素数 p。假设桑德拉发送消息 6 模 13，里瓦返回消息 7 模 13。艾米莉想知道里瓦使用了什么指数进行加密。与其使用 1.000001 的幂，不如使用模 13 的一个原根，比如 2。由于模数较小，艾米莉可以轻松列举出模 13 的所有 2 的幂。

现在艾米莉知道桑德拉发送了 2⁵，里瓦回复了 2¹¹。所以 (2⁵)^r≡2(5r)≡2¹¹ (mod 13)。这意味着 5r≡11 (mod 12)。您可以在脑海中解决这个问题。只需想想 11+12 = 23，23+12 = 35。由于 35 是 5 的倍数，即 5×7，这意味着 r 必须是 7。您可以用手计算器检查，6⁷ = 279936≡7 (mod 13)。桑德拉发送了 6，里瓦回复了 7，所以这是正确的。

16.3.2 素数的幂

艾米莉通过穷举法可以找到一种搜索方法，但是当 p 很大时，这种方法行不通。让我们尝试约翰·波拉德的ρ 算法中的一个思想。第一步是生成模 p 的多个幂序列，并寻找重复项。艾米莉可以同时使用多个原根进行这样的操作，每个核心一个原根。现在我们来把它加倍。如果 b 是模 p 的一个原根，她可以在一个处理器上计算出 b²、b³、b⁴、b⁵… (mod p)，在另一个处理器上计算出 b²、b⁴、b⁸、b¹⁶… (mod p)。这给了艾米莉每个使用的原根两个单独的幂序列。

除了原根，艾米莉还可以直接检查。桑德拉发送 SM，里瓦回复 RSM。艾米莉可以生成序列 (SM)²、(SM)³、(SM)⁴、(SM)⁵… 和 (SM)²、(SM)⁴、(SM)⁸、(SM)¹⁶…，以及 RSM 的类似序列。这给了艾米莉另外四个幂序列。

除了这些有序的幂序列之外，她还可以生成一些无序的序列。这些通常被称为随机游走或醉汉游走。一种方法是对生成的最后一个幂进行平方，然后将其乘以之前的某一个幂。艾米莉可以随机选择早期的幂，或者她可以使用列表的中间元素。例如，假设她已经有了幂 x、x²、x⁴、x⁸ 和 x¹⁶。对于下一个幂，她可以对 x¹⁶ 进行平方得到 x³²，然后乘以，比如说，x² 得到 x³⁴。对于下一个幂，她会对 x³⁴ 进行平方得到 x⁶⁸，然后再乘以另一个列表元素，比如说 x⁸，得到 x⁷⁶。依此类推。

艾米莉可以生成另一种随机游走，使用 2 或 3 个基本素数。每个基本素数应该是一个原根。从这些素数的乘积开始。要生成下一个乘积，她会随机选择其中一个素数并将其乘以。艾米莉拥有的序列越多，她就越快地开始得到结果。

16.3.3 崩溃

好了，现在艾米莉有了所有这些序列。然后呢？她在两个列表上寻找相同的数字。这被称为碰撞或崩溃。假设她发现 3¹⁷²⁹⁶⁴≡103⁴²⁹⁸⁷⁵⁵ (mod p)。通过解决同余式 172964r≡4298755 (mod p-1)，这使得她能够将 103 表示为 3 的幂（模 p）。该方法在第 15.4 节中描述。一旦她积累了足够的崩溃，她就可以建立一个链，例如 RSM≡19^a, 19≡773^b, 773≡131^c, … , 103^y≡(SM)z。将所有指数模 p-1 相乘，她将得到 RSM≡(SM)^r (mod p)。这个指数 r 就是瑞娃的加密函数。艾米莉破解了密码！

这并不像听起来那么简单。当 p 是一个 300 位数素数时，她需要大约 10¹⁵⁰个这样的幂才能开始看到任何崩溃。如果艾米莉有 100 万个处理器，每秒产生 100 万个这样的幂，她可能每年就可以生成 3×10¹⁹个。这意味着她需要大约 10¹³⁰年才能开始看到任何结果，直到她能建立这样一个链为止。此外，它将需要 10¹⁵⁰个字节的存储的倍数。

16.3.4 因式分解

不是每次生成新的幂时都要搜索崩溃，艾米莉可以尝试对其在模 p 下的残留进行因式分解。假设她成功地对 97^a (mod p)的残余进行了因式分解，并找到了 97^a≡11b29^c83d (mod p)。她可以解这个同余式得到 97。设模 p-1 的 a 的乘法逆元为 a’。将同余式提升至 a’次幂。97^{(aa)'≡97≡(11}b29^c83d)^a’ (mod p)。将所有指数相乘并将它们减去模 p-1，结果是 97≡11^e29f83^g (mod p)，其中 e、f 和 g 是一些值。（如果 p 有 300 位数字，实际值可能长达 300 位数字。）一旦她得到了一个质数基的表达式，比如说 97，在所有已经有和以后会找到的因式乘积中都可以替换这个值。

艾米莉将无法对每个幂的残留进行因式分解。对一个 300 位数进行因式分解非常困难，也就是说非常耗时。最好的策略是选择一个固定的质数基集 F(B)，比如说所有小于 B = 10⁶的质数，或者也许是所有小于 B = 10⁷的质数。F(B)被称为因子基。尝试仅使用因子基中的质数对每个幂进行因式分解。可以用这种方式进行因式分解的数字称为B-平滑。随着数字变大，B-平滑数字的比例会变得越来越小。在 300 位数中，B-平滑数很少见。当艾米莉找到每个因子时，数字的未因式分解部分就会减少。如果她已经尝试了基础集中的所有质数，数字的一些未因式分解部分仍然存在，她就不应再尝试进一步因式分解它。放弃这个幂并继续下一个幂会更有效率。

这就是 Emily 必须做的事情：继续生成产品并对它们对 p 取余的结果进行因式分解。仅保留 B-smooth 数字并丢弃其余。检查 B-smooth 数字中的崩溃情况。每次发现崩溃时，解决乘积中最大质数的同余式，以便需要越来越少的基本质数来表示每个乘积。她可以保留一个或多个专用于此任务的处理器。

假设 q^n 是一个质数的幂，并且其模 p 的剩余为 x。尝试使用基本集 B 中的质数因式分解 x。如果 x 不是 B-smooth，则尝试因式分解数 x+p，x+2p，x+3p，…。因式分解一个 301 位数或 302 位数的数并不比因式分解一个 300 位数的数更难。设置一个固定数量的这样的尝试，比如说，对于每个剩余设置 10 次尝试。

当她生成这些幂时，她需要特别强调 SM 和 RSM。记住，这个练习的目标是找到指数 r，使得(SM)^r≡RSM (mod p)。她在将 SM 和 RSM 都表示为基本质数的幂之前是无法做到的。首先，她应该开发出多个 SM 和 RSM 幂的序列。一旦她成功找到这样的表达式，她就会寻找表达式中尚未用较小质数的幂表示的质数。接下来重点放在这些质数上。继续直到 SM 和 RSM 都表示为单一质数的幂。她现在可以使用第 15.3.2 节的方法找到 r。

16.3.5 估算

假设她使用了 10⁶ 个基本质数，也就是说，质数达到了 B = 15,485,863。要将所有这些表示为单一质数将需要 10⁶ 个同余式。存储这些需要一个 10⁶×10⁶ 的指数矩阵。矩阵最初是稀疏的，但随着解决方案的进展而变得稠密，因此稀疏矩阵技术将不会有益。每个指数是一个 300 位数。这需要大约 10¹⁵字节，或 1 个petabyte的存储空间。截至撰写本文时（2022 年 3 月），世界上最大的超级计算机是位于奥克里奇国家实验室的 Summit 计算机，拥有 2.76 petabytes 的可寻址存储空间。

显然，运行时间取决于找到 B-smooth 数字需要多长时间。B-smooth 数字的密度由 de Bruijn 函数Ψ(p,B)给出，它给出了小于 p 的 B-smooth 整数的数量。这由荷兰数学家尼古拉斯·戈弗特·德布鲁因研究过。Ψ(x,x^(1/u))的值由精算师卡尔·迪克曼发明的迪克曼函数ρ(u)近似，其中ρ(u)是迪克曼函数。迪克曼函数ρ(u)由 u^(-u)近似。在这种情况下，x = 10³⁰⁰和 x^(1/u) = 15,485,863，所以 u = 41.725。因此，大约需要大约 41.725^(41.725) = 4.08×10⁶⁷次尝试才能找到每个 B-smooth 数字。

总的来说，将需要超过 10⁷³ 次尝试来找到 10⁶ 个 B-平滑幂。对每个数字进行因数分解可能需要多达 10⁶ 次试除，因此总共需要 10⁷⁹ 次试除。由于数字有 300 位，每次试除将需要 300 倍的操作。总共是 10⁸² 次操作。这比崩溃法的 10¹⁵⁰ 有了巨大的改进，但对于当前的计算机仍然是不可及的。

这表明对于可预见的未来，300 位数字已经足够了，也许可以维持 20 到 30 年。随着量子计算机的发展，这可能会改变，但目前 300 位数字是安全的。

16.4 矩阵三次传输协议

用于三次传递算法的 Shamir 和 Massey-Omura 方法都使用了指数运算。三次传递算法的另一种方法是使用矩阵。我们之前已经见过这种情况，比如 Hill 密码，第 15.1 节。消息被分成块。每个块被视为模 256 的整数向量。这个向量被一个模 256 的可逆方阵左乘或右乘。对于三次传递版本，Sandra 将有一个用于加密的矩阵 S 和其逆矩阵 S’，而 Riva 将有一个加密矩阵 R 和解密矩阵 R’。这些矩阵不是在模 256 整数上，而是在一个 256 个元素的环R上，消息的字符被视为该环的元素。假设消息块为 M，所以 Sandra 发送 SM 给 Riva，Riva 将 RSM 返回给 Sandra，Sandra 使用 S’ 解密以获得 S’RSM = RM。现在 Riva 可以使用 R’ 解密它，即 R’RM = M。

棘手的部分是使 S’RSM = RM。矩阵乘法不可交换，所以 Sandra 和 Riva 需要选择彼此可交换的特殊矩阵 S 和 R。明确地说，S 和 R 不是可交换矩阵。如果你随机选择一个矩阵 X，几乎可以肯定 SX ≠ XS 和 RX ≠ XR。这是一个重要的观点，所以让我重复一遍，S 和 R 不是可交换矩阵。它们不与大多数其他矩阵可交换。它们彼此可交换。

16.4.1 可交换矩阵族

Sandra 和 Riva 需要大量的这些矩阵，这样 Emily 就不能简单地尝试它们所有。这意味着他们需要一个大的可交换矩阵族Ғ，从中选择每个消息块的矩阵。

注意Ғ是一个可交换的矩阵族，而不是一组可交换的矩阵。重要的是要理解，可交换的是矩阵族，而不是矩阵本身。Ғ中几乎所有的矩阵都不可交换。它们彼此可交换，但与其他矩阵不可交换。

构造可交换矩阵族的最简单方法是从任意可逆矩阵 F 开始，并取其幂，F⁰、F¹、F²、F³、…，其中 F⁰ 是单位矩阵 I，而 F¹ = F。将 F 称为Ғ族的生成矩阵。

Sandra 和 Riva 每个消息块都需要使用不同的矩阵，否则 Emily 可能会在已知明文的足够消息块 M[i] 的情况下解出线性方程组 R(SM[i]) = RSM[i]。

16.4.2 乘法阶

要使Ғ族变得更大，你需要找到或构造一个具有很高乘法阶的生成矩阵 F。也就是说，需要找到一个最小的整数 n > 0，使得 F^n = I，至少要大于 10^（25），但最好更大。如果矩阵 F 是可逆的，这样的 n 总是存在的，并且 F 的乘法逆 F’ 是 F^(n-1)。在第 15.8 节中给出了一种寻找可逆矩阵的方法。确定 F 的乘法阶有点艺术性。显然，一直计算 F 的连续幂直到 F^n = I 是不可行的，特别是当 n > 10^（25）时。但这是可以做到的。

要找到乘法阶，从 1×1 矩阵开始，即环元素。查看这些元素的乘法阶。这些可以通过枚举轻松找到，因为 n 的最大可能值是 255。可能的值是 2、3、7、15、31、63、127 和 255。更大矩阵的乘法阶往往是这些值的倍数。

假设环元素的乘法阶恰好是 2、7 和 31。当你尝试 2×2 矩阵时，首先将每个矩阵 A 提升到单元素阶的某个倍数，比如 2⁴7²31 = 24304。然后枚举 B = A²⁴³⁰⁴ 的幂。假设你发现 B⁵² = I。你现在可以确定 A 的乘法阶 m 能够整除 x = 24304×52 = 2⁶7²13×31，且是 2⁶13 的倍数。接下来应该尝试 A^(x/7) 和 A^(x/31) 看看它们是否为 I。如果 A^(x/7) 是 I，那么你就尝试 A^(x/49)。在这种情况下，最高的乘法阶可能是 2⁶7×13×31。

接下来你要处理 3×3 矩阵。如果除了 2、3、7、13 和 31 之外，2×2 矩阵的乘法阶中没有其他质因数出现，那么一个好的起始指数可能是 x = 2⁸7²13²31²。枚举 B = A^x 的连续幂，并重复缩小指数的过程。随着矩阵变大，乘法阶可能会增加一个无法通过枚举找到的因子。在这种情况下，你将需要猜测新的可能出现的质因数。

注意乘法阶序列中出现的模式。这需要一些侦探工作。例如，假设出现了 2³-1、2⁶-1、2⁹-1 和 2¹²-1。你不会直接看到这些，因为它们不全是质数。2⁶-1 = 63 = 3²7，2⁹-1 = 511 = 7×73 和 2¹²-1 = 4095 = 3²5×7×13。所以在质因数中找到 13 是指向“真正”因数可能是 2¹²-1 的线索，而找到 73 则强烈表明 2⁹-1 是一个因数。如果出现了 2³-1、2⁶-1、2⁹-1 和 2¹²-1，你应该期待很快出现 2¹⁵-1。如果这些全部出现，它们都可以被 7 整除，所以乘法阶将被 7⁴ 整除。

16.4.3 最大阶

艾米莉在这一切中的目标是尽可能地扩大家族Ғ，这样她和里娃就有很多选择来选择他们的矩阵 S 和 R。一个有用的技巧是观察因子集合之间的乘法阶数差异。例如，如果 A 的乘法阶数为 19m，B 的乘法阶数为 23m，那么 AB 的乘法阶数很可能是 19×23m=437m。如果这不起作用，那么 A’B 或 AB’可能具有乘法阶数 437m。

如果可能的话，桑德拉应该选择一个生成矩阵 F，其乘法阶数具有一个大素数因子，比如$m>10^{35}$，以防止 Silver-Pohlig-Hellman 攻击（第 14.4 节）。桑德拉需要对各种$n$进行因式分解$2^n-1$，找到具有大素数因子的那些，并尝试用逐渐增大的矩阵找到一个乘法阶数可被其中一个$2^n-1$整除的生成矩阵。

16.4.4 艾米莉的攻击

假设桑德拉已经选择了 F 和Ғ，并且她已经向里娃发送了一条消息。由于桑德拉和里娃正在通过公共信道进行通信，比如互联网，假设艾米莉知道 F、Ғ、SM、RSM 和 RM。她的目标是找到 R 或 S，所以她有两次机会。让我们集中讨论艾米莉如何找到 R。艾米莉知道关于 R 的两件事。首先，她知道 SM 和 RSM 的值，这给了她 n 个线性方程，这些方程是关于 R 的$n^2$个未知元素的。其次，她知道 R 在家族Ғ中，所以它必须与 F 交换，即 RF = FR。如果环R是可交换的，那么这给了她 n(n-1)个关于 R 的$n^2$个元素的附加线性方程。

这有效的原因是矩阵方程 RF = FR 的左侧产生了形式为$rf$的项，其中$r$是 R 的未知元素，$f$是 F 的已知元素。右侧产生了形式为$fr$的项。由于环是可交换的，左侧项$rf$可以转换为形式$fr$，并与右侧项组合形成线性方程。

在$n^2$个未知数的$n^2$个线性方程中解决这些线性方程并找到$R$似乎很容易。但事实并非如此。回顾第 15.3.1 节，我们知道有强同余和弱同余。对于任何不是素数的有限环上的线性方程，情况也是如此。环大小有多少素因子，就有多少潜在的弱方程。在当前情况下，环大小为$2^8$，有 8 个素因子，所以许多线性方程很可能是弱方程。如果环R选择得当，矩阵的典型大小可能是 30×30，或者 128×128，甚至 256×256，如果环的选择不佳。即使选择了合适的环，即使一半的方程是强的，你也会期望至少有$2^{450}$个解集合的 30×30=900 个方程。实际上，解的数量要多得多，因为可能有 4、8 或甚至 16 个解的方程。

Emily 有个好消息。Emily 可以解决 R’ 而不是 R，而她得到的那 2⁴⁵⁰ 或更多的解中的任何一个都将是 R 的有效逆，让她通过 R’RM = M 获得消息。

16.4.5 非交换环

Sandra 和 Riva 看起来是失败的。Emily 赢得了这场战斗。

解决这种攻击的一个可能方法是让 Sandra 和 Riva 使用一个非交换环。非交换环的两个例子是矩阵和四元数（第 15.7.2 节）。你可以形成元素本身是矩阵或四元数的矩阵，或者反过来，系数是矩阵或四元数的四元数。但这些都不是好选择。你需要让它们变得非常大才能产生高乘法阶的矩阵。

更好的方法是使用第 15.7 节的技术构造你自己的环N。你应该选择一个具有许多具备以下特征的元素的环：(1) 可逆，(2) 具有高乘法阶，以及 (3) 非交换。要找到一个同时具有所有这些特征的环是一个棘手的平衡行为。例如，一个具有最大乘法阶元素（256 元素环的 255）的环不能有任何非交换元素。如果你能找到一个环，其中一半元素是可逆的，一半具有乘法阶约为环大小一半的元素，一半是非交换的，dayenu（这就足够了）。你不能同时达到这 3 个目标，但你可以在某些目标上超过其他目标，同时接近其他目标。

使用非交换环，矩阵方程 RF = FR 不再能线性化，因为不再确定 rf = fr。相反，矩阵方程导致一组bilinear方程。双线性方程中的一般项的形式为 axb，其中 a 和 b 是环的元素，x 是您希望确定的变量。虽然线性方程可以使用简单的系统方法解决，即高斯消元法，但对于双线性方程却没有这样的方法。甚至对于一个变量 x 的简单方程 ax+xb = c 也没有一个一般的解法。因此，在环上解双线性方程是“不可能的”。

16.4.6 解双线性方程

话虽如此，我现在将向你展示如何解决双线性方程。诀窍在于改变环N中元素的表示。我们已经看到了几个这样做的示例。在环R13中，元素表示为a + b√13。高斯整数表示为 a+bi。四元数表示为 a+bi+cj+dk。这里，i、j 和 k 是决定环行为的抽象单位的乘积，而 a、b、c 和 d 是环的可交换元素。四元数可以是非交换的，因为单位的乘法不是交换的，即，ij ≠ ji，ik ≠ ki，jk ≠ kj。只有一个单位时，高斯整数必然是可交换的。

线性化双线性方程的技巧是通过找到非交换环 N 的表示来完成的。这很容易做到。首先将 N 的元素划分为两组，A 和 B，其中 A 包含具有表示的元素，而 B 包含其余的元素。最初，A 是空的，B 包含环的所有元素。从取可交换的元素并将它们移到集合 A 开始。这些环元素将表示它们自己。它们是表示中的“a”项。选择任意剩余可逆元素作为单位 i。取所有可以表示为 a+bi 的环元素，其中 a 和 b 是环的可交换元素，并将它们从集合 B 移动到集合 A。到目前为止，A 的所有元素仍然是可交换的。

集合 B 不能为空，因为 N 不是交换的。我们已经注意到只有一个单位的环，如高斯整数，必须是可交换的。因此，从集合 B 中取出第二个可逆元素，并称其为第二个单位 j。这次，您将所有可以表示为 a+bi+cj 的元素从集合 B 移动到集合 A。可能仍然存在于集合 B 中的环元素。在这种情况下，您将重复这些步骤，但为简单起见，假设（1）只需要两个单位；（2）环中的所有元素都可以表示为 a+bi+cj，其中 i 和 j 是抽象单位；和（3）a、b 和 c 是环 N 的可交换元素。在实践中，您获得的单位数量可能取决于您选择的 i 和 j，因此您应该进行多次尝试以获得最少的单位。这很重要，因为更多的单位意味着在线性化时会有更多的方程。由于解一组线性方程所需的时间与方程数量的立方成正比，这对计算有很大影响。

回到矩阵方程 RF = FR，并将环元素表示为 a+bi+cj 的形式。 R 的未知元素将具有 x+yi+zj 的形式，其中 x、y 和 z 是未知的可交换环元素。 现在矩阵乘积 RF 的一个项将具有以下形式：

其中 i²、j²、ij 和 ji 将进一步扩展为 1、i 和 j 的线性组合，如 d+ei+fj。当然，实际的展开取决于环的选择以及哪些元素被选择为 i 和 j。

矩阵乘积 FR 中的项也必须进行相同的处理。最终，您将得到 2700 个未知数的 2700 个方程，而不是 900 个未知数的 900 个方程。这将将错误解的数量从 2⁴⁵⁰增加到 2¹³⁵⁰。这对 Emily 来说是个坏消息。错误的解决方案不允许她恢复消息。

16.4.7 弱点

Ғ家族将包括一些弱点，如对角矩阵和三角矩阵，艾米莉可以轻松求逆。这些弱点不应作为密钥使用。在从Ғ中选择矩阵时，请验证主对角线上下至少有一个非零元素。为了快速进行这个测试，只需验证 X[12]、X[13]和 X[23]中至少有一个非零，以及 X[21]、X[31]和 X[32]中至少有一个非零。否则拒绝 X 并重新选择。被拒绝的矩阵的百分比是可以忽略不计的。

16.4.8 加速方法

使用矩阵而不是指数的优势可能还不太明显。从Ғ家族中选择矩阵 S 或 R 需要对生成矩阵 F 进行大幂次运算。这与将大整数求大幂次有何区别或更快？区别在于准备工作。在 Shamir 和 Massey-Omura 方法中，桑德拉和瑞娃必须对对方收到的数字进行大幂次运算。由于他们事先不知道这个数字，所以他们无法做任何准备来加快指数运算。

然而，使用矩阵方法，生成矩阵 F 事先是已知的。桑德拉和瑞娃都可以提前生成一些 F 的幂次，然后保留这个基础矩阵幂集，这样他们就可以通过仅进行 1 或 2 次矩阵乘法来生成新的 F 的幂次。首先，他们可以仅使用 15 次矩阵乘法生成 16 个矩阵 F，F²，F⁴，F⁸，…，F³²⁷⁶⁸的集合。

如果他们只是做到了这一点，那么艾米莉也可以做到同样的事情。她会拥有与桑德拉和瑞娃相同的基础矩阵集，因此她可以轻松确定它们的加密矩阵 S 和 R。为了防止这种情况发生，桑德拉和瑞娃需要随机化他们的矩阵集。他们通过随机选择两个矩阵并将它们相乘来实现这一点。这个乘积将替换基础集中的其中一个矩阵。桑德拉和瑞娃独立地执行这个操作。彼此都不知道对方选择了哪些 F 的幂次。

在设置过程中，应该重复执行这个替换操作很多次，比如 1000 次，这样每个参与方的矩阵集就会彻底随机化。如果 1000 次看起来过多，记住，在 Shamir 方法中使用一个 300 位的素数，每次指数运算将需要约 1000 次乘法和 1000 次模重。桑德拉和瑞娃还需要保留他们矩阵的逆。每次他们将两个 F 的幂次相乘时，他们需要相应地将 F’的幂次相乘，这样他们就永远不需要求逆任何幂次。

此设置步骤，在发送第一条消息之前，只需执行一次。当您拥有这个扩展的生成矩阵集时，您可以通过仅进行一次矩阵乘法和一次其逆矩阵的乘法来生成用于发送消息的矩阵。您随机选择来自基本集的两个不同的矩阵 F^a 和 F^b，相乘得到 F^(a+b)，然后将 F^a 替换为 F^(a+b)，以便每次生成不同的矩阵。

使用这种技术，我发现矩阵方法对于 30×30 矩阵与 1024 位模数相比，约快 2100 倍，而不论是 Shamir 还是 Massey-Omura 指数方法。

16.5 双侧三步协议

前述矩阵方法中的矩阵乘法可以在左侧或右侧执行，这意味着消息可以被加密为 SM 或 MS。也可以在两侧同时进行乘法。在这种情况下，消息被分成 n²个字符的块，并且有两个独立的 n×n 矩阵的可交换的族，Ғ 和 Ɠ，其生成矩阵为 F 和 G。桑德拉将用来自 Ғ 的矩阵 S 和来自 Ɠ 的矩阵 T 加密消息，而丽娃将用来自 Ғ 的矩阵 R 和来自 Ɠ 的矩阵 Q 进行超加密。

桑德拉向丽娃发送加密的消息 SMT。丽娃进行超加密并发送回 RSMTQ。桑德拉通过使用逆矩阵 S’和 T’去除她的加密，发送 S’RSMTQT’ = RMQ 回给丽娃，丽娃使用她的逆矩阵 R’和 Q’来解密，如 R’RMQQ’ = M。对于短消息来说，双侧方法不实用，因为其块大小较大，但对于长消息来说，它比单侧方法快得多，因为每个块中有 n²个字符而不是 n 个字符。对于 30×30 矩阵，它可以比单侧方法快 15 倍，因此约比 Shamir 或 Massey-Omura 方法快约 30,000 倍。

艾米莉必须同时解出两个矩阵。让艾米莉拦截的三个矩阵分别称为 X、Y 和 Z，即 X = SMT，Y = RSMTQ 和 Z = RMQ。艾米莉知道 Y = RXQ 和 Z = S’YT’。看起来艾米莉需要解一个大型的二次方程组，而不是解线性或双线性方程。然而，如果这些方程分别乘以 R’、Q’、S 和 T，它们就会变成 R’Y = XQ、YQ’ = RX、SZ = YT’和 ZT = S’Y。这些矩阵方程展开后会得到双线性方程。我们在第 16.4.6 节中看到了如何解决双线性方程。

艾米丽可以通过找到 R’ 和 Q’，或者找到 S’ 和 T’ 来恢复 M。她可以选择解决这四个方程中的前两个或后两个中的任意一个。让我们继续以 30×30 矩阵的例子，并集中于解决 R’Y = XQ。R’ 中有 900 个未知数，Q 中还有 900 个。这个矩阵方程在这 1800 个未知数中提供了 900 个双线性方程。艾米丽还知道 R’ 在 Ғ 中，Q 在 Ɠ 中，所以 R’F = FR’，QG = GQ。每个方程都产生了额外的 30×29 = 870 个双线性方程。这给了艾米丽总共 2640 个双线性方程，1800 个未知数。通过改变环元素的表示，这些方程可以线性化。

这导致了 7920 个线性方程，5400 个未知数。当方程比未知数多时，系统被称为 过度确定。随着艾米丽减少方程组，多余的方程将被简单地舍弃。也就是说，7920×5400 矩阵的许多行变成了全零。它们可以移到矩阵底部并被忽略。最后，与单边情况一样出现了相同的困难，即存在大量的解决方案。由于双边方程组是过度确定的，它们比单边方程组更强大。另一方面，未知数是两倍多。不清楚哪种方法最终更强大。您可能会选择双边方法，因为它快得多。******

第十七章：密码

本章涵盖

构建密码的思路

尽管在密码、密码机和现在的数字加密方面取得了进步，但军队始终依赖于密码。即使在今天，我们也可以假设军队仍然将密码作为备用，以防电子设备出现故障或电力不可用。

大多数密码将字母、音节、单词或短语替换为固定大小的组，通常是 3、4 或 5 位十进制数字，或者是 3 或 4 个字母的组。可变长度的密码很少见。密码通常分为两种类型，单一密码和双重密码。在单一密码中，单词和短语按字母顺序列出，并且代码组按数字顺序分配，尽管不是连续的，因此可以使用相同的列表查找单词和代码组。这种方法的弱点是显而易见的。如果你的对手已经弄清楚了代码 08452 的含义是 CANNON，那么他们就知道与 08452 接近的任何代码必须有类似 CAMOUFLAGE、CAMPAIGN、CANCEL、CANINE、CANVAS、CAPITAL、CAPITULATE、CAPSIZE、CAPTAIN 等含义。

在双重密码中，代码组是以随机顺序分配的。密码书将包含两个单独的列表，一个按字母顺序列出单词和短语，另一个按数字顺序列出代码组。过去，双重密码需要数月的时间才能编制，并且成本很高。因此，一个政府可能会多年使用相同的代码，从而大大削弱其有效性。自 1960 年代以来，编制双重密码的工作可以在几秒钟内由计算机完成。

密码编制者有很多技巧来使他们的密码更加安全。对于常见的单词和短语，他们会提供许多等效的代码组，或者同义词。因此，海军密码可能有 10 到 20 个代码组代表“ship”，而陆军密码可能有相同数量的代码组代表“artillery”，外交密码可能有同样多的代码组代表“treaty”。密码往往有很多空组。消息的整个部分可能完全为空。某些代码组可能具有多重含义，取决于某个指示器，例如前一组的最后一个数字。

有些密码书是以两列印刷的。根据某个指示器，密码来自左列或右列。例如，如果当前的代码组以偶数数字开头，则从左列取下一个代码组，否则从右列取下一个代码组。

17.1 小丑

小丑 是我自己发明的一种密码风格。如果有读者想要设计自己的密码，小丑可能会给他们一些有用的思路。基本概念是，在每个代码组中，一个字母或数字与其他字母或数字不同。例如，在一个 5 字符组中，4 个字符将携带意义，而另一个字符，称为小丑，存在于此以制造混乱。仅仅有一个空字符就会让对手的工作变得更加困难，但是你还可以用这个特殊的字母或数字做更多的事情。

假设一个 5 位数字组的代码。其中 4 位是代码本身，另一位是小丑。为了开始，假设小丑总是在每条消息中第一个代码组的中间位置。还假设这是一个 2 列代码书，左列的代码与右列的代码完全不同。例如，左列的 0022 可能表示“救援”，而右列的 0022 可能表示“引擎”。

同样，小丑可能有两列含义，因此小丑可以移动到不同的数字位置，也可以移动到不同的列。

这里是您可以为小丑分配的可能含义列表。不止 10 个。您可以选择您想要的 10 个。或者，使用 2 列并为小丑选择 20 个含义。或者，使用字母而不是数字，并为小丑选择 26 个含义。

• 从下一组开始，小丑向左移动 1 个位置。

• 从下一组开始，小丑向右移动 1 个位置。

• 从下一组开始，小丑移动到位置 1。

• 从下一组开始，小丑移动到位置 2，依此类推。

• 仅对于下一组，小丑在位置 1。

• 仅对于下一组，小丑在位置 2，依此类推。

• 切换到代码的左列。

• 切换到代码的右列。

• 切换到代码的相反列。

• 仅对于下一个代码，使用相反的代码列。

• 对于接下来的 2 个代码，使用相反的代码列，依此类推。

• 接下来的组为空。

• 下一组之后为空。

• 接下来的 2 组为空，依此类推。

• 在下一组中，代码为空，但小丑是真实的。

• 在下一组中，代码是真实的，但小丑是空的。

• 交换接下来的 2 组的顺序。

• 在下一组的代码中加上 1111（不进位相加）。

• 在下一组的代码中加上 3030（不进位相加），依此类推。

• 如果下一个代码是偶数，则加上 2222，否则减去 2222（不进位）。

• 在下一组中，将小丑加 1（不进位）。

• 在下一组的小丑中加 2（不进位），依此类推。

• 将这个 4 位代码加到下一个 4 位代码中。小丑除外。

• 反向阅读下一个代码的数字，例如 1075 实际上表示 5701。

• 忽略接下来的代码，直到有一个以 0 开头的代码。

• 下一组是一个特殊指示器。

有关不进位相加的示例，请参见第 4.6 节。

特殊指示器需要更详细的解释。在特殊指示器中，代码组的所有 5 位数字都有特殊用途，比如告诉小丑将在哪里，或者使用哪一列。例如，特殊指示器 13152 可能意味着在接下来的 5 组中，小丑将按顺序出现在位置 1、3、1、5 和 2。特殊指示器还可以告诉接下来的 5 个代码从哪一列取出，奇数表示代码来自左列，偶数表示代码来自右列。特殊指示器 10384 可能意味着在接下来的 5 组中，代码将依次从左、右、左、右和右列中取出。

另一个特殊指示器的用途可能是指定要添加到接下来的 5 组代码中的数字。例如，特殊指示器可能意味着将以下值添加到 4 位代码中：

这些值将使用非进位加法，模 10 加法进行相加。

小丑总是指示接下来的组或组中要采取的行动，而不是当前组或前一组。例如，不应使用意思为“取消前一个小丑”的小丑。当一个小丑指示涵盖几个后续组的行动时，请确保两个不同小丑的行动不冲突。例如，不应该在第 20 组中有一个小丑说，“接下来的 3 个代码取自左列”，然后在第 21 组中有一个小丑说，“接下来的 3 个代码取自右列”。

可以与小丑代码一起使用的另一个技巧是使用字母 A 到 E 代替小丑。这个字母可以出现在任何位置，并取代小丑的预期位置。字母 A 表示下一个小丑将在位置 1，B 表示位置 2，依此类推。您还可以为字母 F、G 和 H 分配含义。例如，F 可以表示代码应从相反的列中取出，下一个小丑将在位置 1。

如果有可能将字母 I 误认为是数字 1，请不要使用字母 I。我喜欢使用字母 J 作为超级小丑。它表示接下来的一切都是空的。您可以继续输入另外 10、20 或 100 组代码的胡言乱语，真的让艾米莉陷入狂喜。或者，您可以使用这些空白来发送一个误导性的虚假消息，比如“诺曼底登陆推迟到 6 月 10 日在犹他海滩进行”。

第十八章：量子计算机

本章内容包括

• 量子计算机的特性

• 使用量子计算机进行通信

• 使用量子计算机进行密钥交换

• 使用量子计算机解决优化问题

• 使用量子计算机解密分组密码

• 超级计算机，超越量子计算机

当我写这本书时，量子计算机还处于萌芽阶段。全世界没有超过 20 台量子计算机，其中没有一台包含超过大约 50 个 qubit 或量子比特。我写这一章时知道其中很多内容可能已经过时，甚至在书发布之前就被证明是错误的。量子力学和量子计算中使用的许多数学远远超出了本书的范围，因此本章的部分内容将简单提及量子方法和算法，而不解释它们的工作原理。

量子计算的基础是量子比特，或qubit。一个 qubit 有两个基态，分别表示为**|0〉和|1〉，对应于传统计算机中普通比特的 0 和 1 状态。符号|1〉被称为bra-ket符号。当尖括号在左边时，如〈0|，称为bra，因此〈0|读作“bra-0”。当尖括号在右边时，称为ket，因此|**1〉读作“ket-1”。这种符号是由诺贝尔物理奖获得者英国物理学家保罗·阿德里安·莫里斯·狄拉克发明的。

在传统计算机中，普通比特具有明确的值，可能是 0 或 1。该值只能是 0 或 1，不能是某个中间值，也不能同时是多个值，有时是 0 有时是 1。物理设备，如表面上的磁点，可以通过施加电流或磁场从一个值切换到另一个值。可能会有一个短暂的过渡，但设备不能停留在任何类型的中间或混合状态。

18.1 叠加

相比之下，qubit 在进行测量或观察之前没有值。在那时，它的值将是 0 或 1。基态**|0〉表示其值为 0 的概率为 1.0，基态|1〉表示其值为 1 的概率为 1.0。一般来说，qubit 将处于两个基态α|0〉+β|**1〉的叠加状态，其中α和β是复数，使得|α|²+|β|² = 1。当测量时，这个 qubit 产生 0 的概率是|α|²，产生 1 的概率是|β|²。符号|α|表示α的幅度。复数 a+bi 的幅度是√(a² + b²)。由于测量结果是概率性的，两个处于相同状态的 qubit 的测量结果可能不同。可以叠加任意数量的状态。

当一个量子态 x 由几个量子比特组成，比如 x[1]、x[2]、x[3]时，态〈x|被表示为一个行向量（x̅[1]，x̅[2]，x̅[3]），其中每个分量上方的横线表示复共轭。如果复数α为 a+bi，则其复共轭α̅为 a-bi。复共轭具有性质，即乘积α**α̅ = a²+b² = |α|²。反之，态|y〉被表示为一个列向量。

由于这个示例中的行向量是一个 1×3 矩阵，列向量是一个 3×1 矩阵，它们可以相乘。矩阵乘积，表示为〈x|y〉，是一个 1×1 矩阵，其单个元素是内积x̅•y。也就是说，〈x|y〉是一个标量。(如果这很陌生，你可以复习第 11.3 节。)

由于任意两个状态可以叠加，并且这些状态反过来又可以叠加，任意量子比特可能处于任意多个状态的叠加中。

叠加态是脆弱的。小的扰动，比如温度波动或机械振动，可以导致量子比特退出叠加态，并回到基态之一。这称为退相干。这种脆弱性是实现大型可靠量子计算机的主要障碍。特别是，当进行测量时，量子比特将退相干并掉入观察到的任一基态。同样，量子比特不能被复制，因为那将需要一个观测。

如果难以理解复数系数的概念，也许这会有所帮助。在笛卡尔坐标中想象点(a,b)。从原点(0,0)到点(a,b)的线段是一个向量。它既有大小又有方向。当两个状态叠加时，根据坐标几何的规则将这些向量相加，这恰好是复数相加的方式。这就是为什么概率被表示为复数的原因。在向量相加后，必须重新调整系数，使|α|²+|β|² = 1。如果α和β用角度描述，则可以消除重新调整，使用角度的三角函数公式描述角度的和与差。

量子比特可以使用一些基本逻辑函数进行操作，以形成量子电路。一个例子是条件非门函数 CNOT，它对 2 比特量子比特**|xy〉进行操作。CNOT 定义为|xy〉如果 x = 0，和|**xy’〉如果 x = 1。换句话说，第一个比特保持不变，第二个比特是两个比特的异或。

18.2 纠缠

除了叠加之外，粒子还可以显示第二个量子力学属性，称为纠缠。如果一个粒子的某个属性与其他粒子的同一属性之间存在相关性，则称该粒子组为纠缠。例如，电子具有称为自旋的属性。关于特定轴（如 x 轴）的自旋可能在粒子组中是相关的。或者，一组光子的极化可能是纠缠的。即使粒子相距很远，这种纠缠也可能存在。这使得纠缠可以用于通信。

该过程始于创建一对纠缠粒子。一种方法是将激光束通过一种特殊类型的晶体。这导致一些高能光子分裂成两个低能光子。其中一些光子对将是纠缠的，尽管产率非常低，例如十亿分之一。下一步是将这些纠缠光子传输到桑德拉和莉娃将要传输和接收的地方。对于长距离传输，通常的方法是通过光纤传输它们，尽管它们也可以通过晶格中的空腔物理携带。

当桑德拉准备发送她的消息时，她将她的光子与一些特别准备好的称为辅助光子的光子相互作用。这种相互作用导致她的光子采取她希望传输的所需状态。这导致了莉娃的纠缠光子，它可能在数英里之外，采取互补状态。过去人们认为这是瞬时发生的，但是变化是以光速传播的。信息不能瞬间传输，尽管几代科幻作家都幻想过这一点。

最后，莉娃测量她的纠缠光子并确定 1 比特的消息——或者不确定，因为这是一个概率过程。这有时被科学家们称为量子传送，他们读了太多科幻小说。据说这是安全的，因为如果艾米丽测量了光子，它会解缠，桑德拉和莉娃应该可以检测到。

这里存在两个缺陷。(1) 艾米丽可能不在乎她的窃听是否被发现。只要她知道这些信息，桑德拉和莉娃知道她知道可能并不重要。(2) 艾米丽的目标可能不是收集信息；她的目标可能是扰乱通讯。艾米丽可能不会得知秘密作战计划，但莉娃也不会。实际上，如果桑德拉和莉娃发现艾米丽在窃听，他们可能会更少地使用量子链接，这对艾米丽也是有利的。

18.3 错误校正

由于量子事件是概率性的，量子计算机的错误率比传统计算机高得多。必须有一些手段来检测和纠正错误。在经典计算机中，有错误检测和纠正码。这些码使用额外的位来检测差异，例如通过为每个字节添加奇偶校验位来检测错误。奇偶校验位通常是 8 个数据位的异或。这意味着带有错误位的 9 位字节将始终具有偶校验。如果奇偶校验是奇数，那表明发生了错误，但它并不告诉错误是什么。

传统计算机最简单的纠错码形式是 2-3 码。每个位有 3 个副本。如果发生单位错误，两个副本仍将具有正确值。如果单位错误的几率是，比如，10⁷中的 1，那么使用这种常见值将将错误几率降低到 10¹⁴中的 3，这是一个巨大的改进。使用 3 位来表示每个数据位是昂贵的，但有几种类型的码，如海明码和卷积码，使用更少的额外位，其中一些可以检测和纠正多位错误。在当前的加密中，无错误的通信是绝对必要的，即使改变一个位也可能使消息无法阅读。

这种类型的错误检测和纠正在量子计算机中是不可能的。这些码依赖于复制位的值并检查码的奇偶性。这些在量子比特中无法完成，因为测量量子比特的值会导致其退相干。提供量子纠错通常依赖于使用额外的量子比特。错误检测和纠正量子比特可以与数据量子比特交错排列在一个被称为表面码的平面晶格结构中。

到目前为止，量子纠错仅仅是理论上的。还没有人建造出实用的设备。额外的纠错位需求增加了实用量子计算机所需的量子比特数量。由于量子错误率很高，实用量子计算机可能仍然遥不可及。在阅读以下各节中各种量子算法的描述时，请记住这一点。

18.4 测量

测量光子的极化是一件棘手的事情。想一想你如何测量一束光的极化。你通过一个极性滤波器传递光束并观察亮度。然后慢慢旋转滤波器，直到经过滤的光达到最大亮度。在那一点上，滤波器与光束的极化对齐，你可以测量角度。

然而，里瓦没有这样的奢侈。她正在处理一个单光子。它穿过她的滤光片或晶体，要么她检测到闪光，要么没有。如果她的滤光片与桑德拉的发射器不对齐，那么她获得与桑德拉相同状态的几率取决于相对角度。例如，如果她的探测器与桑德拉的发射器呈 90º角度，那么她获得量子位相同值的几率正好是 50%。

解决这个问题的方法是桑德拉发送一串光子。里瓦可以对这些光子进行采样，通过各种滤光片进行传输。她可以通过使用光传感器和电压表测量每个样本的亮度，并计算准确的极化角度。然后她以那个角度进行测量，并以非常高的概率获得与桑德拉相同的基态。利用量子计算机进行密码学可能最终取决于区分极化中微小渐变的能力。

18.5 量子三阶段协议

这为 2006 年由俄克拉荷马州立大学的 Subhash Kak 发明的三阶段量子协议奠定了基础。Kak 的 3 阶段协议使用与第 16.1、16.2 和 16.4 节讨论的其他三次传递算法相同的 3 消息框架。在量子版本中，加密操作是围绕选择的空间轴随机旋转极化。桑德拉和里瓦必须就轴达成一致意见，否则旋转将不会交换。 (1) 桑德拉发送经过她随机角度φ旋转的光子， (2) 里瓦将光子旋转她的秘密角度ψ并发送经过φ+ψ旋转的光子， (3) 桑德拉应用逆旋转-φ并发送经过里瓦角度ψ旋转的光子，里瓦移除以读取量子位。如果艾米丽尝试测量任何旋转的量子位，她无法知道她的探测器是否具有正确的角度，因此也无法知道获得正确值的概率。

使用这种方法，桑德拉和里瓦必须经常改变它们的角度，最好是每个比特都要改变。否则，艾米丽可以随意选择一个随机角度并尝试读取每条消息。如果艾米丽的角度接近正确角度，那么她将在 80%甚至 90%的比特上得到正确值。这足以让她能够读取消息。幸运的话，她将能够读取大约 25%的消息。请注意，艾米丽的角度接近 180º也同样有用，因为这将给她 80%到 90%的比特的逆。

18.6 量子密钥交换

有几种类似于 Diffie-Hellman 密钥交换的量子密钥交换算法。其中最著名的算法是BB84，以其发明者 IBM 研究院的查尔斯·H·贝内特和蒙特利尔大学的吉尔·布拉萨德命名。该算法使用 4 个量子位允许在通信信道中检测和纠正噪声。由 Emily 引起的任何扰动都简单地视为通道中的额外噪声，因此不需要进一步检测或纠正。

这项工作的一个推论是，几个松散纠缠的粒子可以结合成更少数量的紧密纠缠粒子。

18.7 格罗弗算法

格罗弗的 密码算法 是一种使用量子计算机破解诸如 DES 和 AES 这样的秘密密钥分块密码的算法。它由贝尔实验室的洛夫·库马尔·格罗弗在 1996 年开发，基于他的量子文件搜索算法。该算法将加密函数的每次评估都视为对未排序数据库的一次读取访问。该算法将期望的评估次数从 K 减少到 √K，其中 K 是可能的密钥数量。实际上，这将密钥大小从 n 位减小到 n/2 位。

格罗弗算法以很高的概率找到密钥 k，使得 E(k,p) = c，其中 E 是加密函数，p 是明文，c 是密文。该算法需要每个这样的密钥一个已知明文块。一个量子物理学家，可能对密码学知之甚少，可能会得出这样的结论，即对抗格罗弗算法需要将所有加密密钥的大小加倍。这是低效的，因为它会需要额外的块密码轮次。例如，使用 128 位密钥的 AES 使用 10 轮，而使用 256 位密钥的 AES 使用 14 轮。

一个更便宜的替代方法是通过在主加密前后添加一个简单快速的密码步骤，如简单替代，来增加密钥大小。用于混合两个简单替代字母表的密钥可以达到每个 1684 位（5.2 节），因为每个字母表可以有 256! 种可能的排列，接近于 2¹⁶⁸⁴。简单的转位也可以帮助扩展密钥大小，但方式更受限，因为 16! 大约是 2⁴⁴。如果选择使用转位，您可以一次转位两个块，因为 32! 大约是 2¹¹⁸，总密钥大小显著增加。

读者们会意识到，格罗弗算法也可以通过使用空值、为每个块使用不同的密钥、链接块或压缩消息等基本手段来进行打败。这意味着在块加密之前通过混合哈夫曼（4.2.1 节）之类的压缩密码实现两个目标，即更大的密钥和压缩，一举两得。混合哈夫曼的缺点是它改变了块大小。在块密码之前和之后使用哈夫曼替换（10.4 节）或者邮件替换（10.5 节）可能更明智。

18.8 方程式

在我们讨论下一个话题——量子模拟退火之前，我们需要讨论方程式。 许多密码可以表示为方程组。 比拉索密码可以表示为 C = P+K，其中 C 是密文，P 是明文，K 是密钥，都是在模 26 的整数中表示的。 希尔密码是一组线性方程。 像普莱费尔和双平方这样的密码会被表示为基于 5 的方程式。

18.8.1 交换

交换可以很容易地表示为相等集合。 例如，列转置

可以表示为 c[1] = m[1], c[2] = m[4], c[3] = m[7], c[4] = m[2], c[5] = m[5], c[6] = m[3], c[7] = m[6]，其中 m[i] 为明文消息字符，c[j] 为密文字符。

逻辑函数可以转换为如下的数值方程：

not x → 1-x

x or y → x+y-xy

x and y → xy

x xor y → x+y-2xy

18.8.2 替换

替换可以通过一个三步过程转换为方程形式。 首先，使用密钥和明文的比特将每个密文比特表示为布尔表达式。 例如，考虑这个替换，它接受一个 1 位密钥 K 和一个 2 位明文 AB，生成一个 2 位密文 XY。

K	AB	XY	布尔输入
0	00	01	K̅A̅B̅
0	01	11	K̅A̅B
0	10	00	K̅AB̅
0	11	01	K̅AB
1	00	10	KA̅B̅
1	01	00	KA̅B
1	10	10	KAB̅
1	11	11	KAB

这里 K̅A̅B̅ 意味着 K = 0，A = 0 和 B = 0， K̅A̅B 意味着 K = 0，A = 0 和 B = 1，依此类推。 现在可以将密文位 X 写为 X = K̅A̅B+KA̅B̅+KAB̅+KAB。 Y 也有类似的表达式。

18.8.3 卡诺图

卡诺图用于简化或简化这些表达式。 这是第二步。 这个概念是贝尔实验室的莫里斯·卡诺纳于 1953 年发明的。 这个想法是把所有可能的 n 位输入集合看作 n 维空间，2×2×2×…×2。 填充每个输出比特为 1 的单元格。 这是输出比特 X 的空间。 Y 也会有一个类似的图。

注意此地图中的列是如何标记的。 当您从一个单元格移到下一个单元格时，从左到右只有一个位改变，包括从第 4 列到第 1 列的环绕步骤。 这种排列被称为格雷码。 格雷码由贝尔实验室的弗兰克·格雷于 1947 年发明。 通过一次附加一个位轻松构造格雷码。 例如，要将这个 2 位格雷码扩展为 3 位格雷码，首先以顺序列出 4 个 A,B 对 A̅B̅，AB̅，AB，A̅B，每个对应的 C̅，然后以相反的顺序列出每个对应的 C。 C 位只更改两次，第四个代码组后和第八个代码组后环绕到开始。

卡诺图让您通过眼睛优化逻辑达到大约 6 位的水平，3 水平和 3 垂直，使用一个 8 单元格乘以 8 单元格的地图。 超过 6 位最好用程序来做。 每个步骤都要添加最大的矩形块，该矩形块适合填充区域内，并覆盖至少一个尚未被覆盖的新单元格。 块的每个维度都必须是 2 的幂，因此其体积也将是 2 的幂。 如果有几个最大尺寸的块，请选择覆盖尚未覆盖的大多数单元格的块之一。 继续，直到所有填充单元都被覆盖。

在 K，A，B 示例中，填充区域中有两个 1×2 块，即 KA 和 KB̅。 每个都覆盖 2 个单元格。 由于它们一起覆盖 3 个单元格，因此两者都是必需的。 这只留下了单元格 KAB̅ 需要被覆盖。 因此，X 的简化表达式为 KA+KB̅+KAB̅。

将替换这些表达式中的and，or和not函数为算术表达式，遵循先前的规则，作为将替换的第三步。

18.8.4 中间变量

如果您尝试将诸如 AES 这样的复杂分组密码中的每个密文位表示为单个表达式，则该表达式的大小将随每轮呈指数增长。 这个问题有时被引用为你不能使用方程式来破解分组密码的原因。 胡扯。 这个问题可以通过使用中间变量来消除。 让每一轮的输出成为一个单独的变量集。

第一轮的输入，密钥，明文和链向量(s)是独立变量。 这些位中的任何一个都可以独立于其他位变化。 每一轮或每一轮内的每个阶段的输出是相关变量。 这包括下一个块的链向量。 它们的值完全由独立变量的值确定。 不能改变其中一个位而不改变其他变量的一些位。

18.8.5 已知明文

假设 Emily 有一定量的已知明文。为简单起见，假设这是一个 n 位的消息块。她的目标是利用已知的明文和拦截的密文确定密钥。假设 Emily 已经找到了每个密文位的表达式，这些表达式是关于明文、密钥和可能的链向量的。设第 i 位的表达式为 E[i]，设 c[i] 为密文的第 i 位。对于任何给定的密钥 K，Emily 可以通过计算对应于使用密钥 K 对已知明文进行加密得到的密文与拦截的密文之间的差异来衡量：

当找到正确的密钥时，D(K) 将为 0。在这里，D(K) 称为目标函数，或简称分数。

18.9 最小化

引入目标函数将找到正确密钥的问题转换为一个最小化问题。目的是最小化函数 D(K) 的值。量子计算机的工作原理是因为系统的量子态总是趋向于最低能量态。如果可以配置量子计算机，使得量子比特或量子比特组表示变量的值，而系统的能量对应于目标函数的值，那么最低能量态将对应于目标函数的最小值。如果可以实现这种配置，那么量子计算机将能够解决各种现实世界的问题，包括破译密码。

起初，用实数替换密钥中的位。最终这些数字必须是 0 或 1，但允许变量在搜索过程中超出 0-1 范围是有利的。从某些初始值开始，例如将所有位设置为 .5，或将它们设置为 0-1 范围内的随机值，然后调整它们的值以减少 D(K) 的值，尝试将其减少到 0。

现在有许多与传统计算机一起使用的优化技术，但让我们只看三种。使用这些算法找到加密密钥将需要大量已知明文。至少已知明文应该是密钥大小的 3 倍。

18.9.1 爬山法

爬山法，也称为最陡下降法或梯度法，是最古老的优化方法之一。其思想是从某一点 P[1] 开始，看看随机方向上的几个等距点。在这些点中，选择改进最大的点 P[2]，也就是具有最小 D(K) 值的点。然后通过查看接近 P[2] 的随机点来细化方向。从 P[2] 到任何这些点的距离将远小于从 P[1] 到 P[2] 的距离。将这个点称为 P[3]。从 P[1] 到 P[3] 的线定义了搜索方向。最后，找到这条线上使 D(K) 最小的点 P[4]。搜索重复使用 P[4] 作为起点。随着搜索的进行，从 P[i] 到 P[i+1] 的步长在找到改进时逐渐增加，如果没有改进则减小。

这种搜索形式在搜索空间形状像 n 维空间中的单个山或被许多较小的山丘包围的大中央山时效果很好。在具有许多局部最优解的更复杂地形中，它可能失败得很严重。在这个图中，颜色越深，分数越好。

18.9.2 千峰

千峰，或千峰，是我在 20 世纪 70 年代参加各种谜题比赛中取得胜利的方法。后来，我开始为一些计算机期刊撰写这种搜索方法，但我陷入了试图表征这种搜索方法比其他搜索方法更好的目标函数类型的困境中。这种方法在 20 世纪 90 年代以粒子群优化的名字重新被发现。

想象搜索空间就像是一个有许多峰、谷和山脊的山脉。现在想象一队飞机飞越这片地形，通过降落伞投放数百名登山者。换句话说，有许多同时的起点。这些登山者会查看附近的点，看看这些地点是更高还是更低。有两种变体。（1）你可以选择这些点中最好的一个，并将登山者移动到那里。在这种情况下，如果没有一个点更好，你会减小步长并重试。如果这次失败，比如连续失败 3 次，那么你会引入一个新的登山者，他会从一个随机位置开始。（2）你保留显示改进的几个点。你可以将这看作是登山队分成几个小组尝试不同的路径。最好不要选择所有改进的解决方案，因为这会迅速将所有登山者集中在几个区域。

我最初的想法是将所有解保留在一个堆结构中，以便顶部条目始终是最差的解。你拿到那个最差的条目并尝试改进它。但这被证明是低效的，因为你花了大量的精力去改进最终被丢弃的差解。相反，总是选择最好的解会把所有爬山者都集中在一个单一的高峰上。最佳策略是随机选择下一个爬山者。同样，在一个解产生多个改进解时，不总是选择其中最好的有利。有时，随机选择几个改进解更好。

18.9.3 模拟退火

模拟退火是一种流行的优化技术，主要是因为它很容易实现。你从搜索空间中的一个随机点开始，并查看附近的一个点。如果那个解更好，那么以概率 B 移动到该点。如果那个解更差，那么以概率 W 移动到该点。

模拟退火的定义特征是在搜索过程中改变概率。最初，你设定拒绝好解的机会或接受坏解的机会相当高。比如，你拒绝 40%的更好解，接受 30%的更差解，即 B = .6 和 W = .3。然后在一段时间后，比如 1000 步之后，你会降低拒绝好解的概率。也许在第二阶段，你拒绝更好解的 20%，接受更差解的 15%。再过一段时间，比如再 2000 步之后，你可能只开始拒绝更好解的 10%，接受更差解的 7%。

这个过程被称为模拟退火，因为它类似于金属热处理中的热退火过程，在这个过程中，金属首先被加热直到发光，然后非常缓慢地冷却。这改变了金属的结晶结构，减少了其硬度，增加了其韧性和延展性，使其更容易加工。在模拟退火中，拒绝更好解和接受更差解的高初始概率类似于金属的高温状态，而这些概率的逐渐降低则类似于金属的缓慢冷却。对模拟退火的描述通常提到概率逐步降低的几个阶段称为降温。

让我传授一些我在模拟退火中的经验：

• 过于缓慢是不值得的。每个阶段的接受/拒绝率应该在前一率的 1/2 到 2/3 之间。例如，第一阶段是 40%，然后 20%，10%，5%，3%。或者，从 40%开始，然后 25%，15%，10%，6%，4%，最后 2.5%。

• 通常五个阶段就足够了。

• 以 50%的接受率开始是浪费时间的。从 60%到 75%之间开始。

• 将接受率降到 0% 是得不偿失的。如果最后一个阶段接受了 2% 到 3% 的更差的解决方案，你将获得更大的改进。

• 当什么都不发生时停止。你可能计划在每个阶段进行 1000 次试验，但如果你已经进行了 100 次尝试而没有改变，就停止吧。

• 让百分比取决于改进的大小。例如，在第一阶段，你可以接受改进分数为 1% 的变化的 60%，改进分数为 2% 的变化的 75%，改进分数为 3% 或更多的变化的 90%。

• 实验。每个优化问题都是不同的。尝试改变阶段的数量、每个阶段的试验次数、改变概率的速率、步长和改进程度与接受率之间的关系。

爬山、千山万峰和模拟退火技术可以自由组合，产生各种混合方法。

18.10 量子模拟退火

有几种提议的方法可以利用量子计算机进行模拟退火。这些方法利用量子现象如叠加来并行执行许多搜索。然而，每次试验都需要在选择的点上评估目标函数。量子计算机不适用于评估表达式。到目前为止，尚无方法可以通过量子手段并行评估这些函数。量子计算机可以利用传统计算机来评估表达式，但这将失去并行性。到目前为止，量子搜索还没有显示出比传统计算机搜索更快的改进。

18.11 量子因式分解

RSA 公钥密码系统的强度取决于大整数因式分解的难度。给定两个大整数 A 和 B，将它们相乘得到乘积 AB 是很容易的，但要反向执行这个过程并确定大整数的因子则非常困难。对一个大数进行因式分解的难度与计算离散对数（第 16.3 节）的难度相同，并且使用许多相同的技术。

这种安全性可能会被用于因式分解大数的 Shor 算法突破。这是第一个量子算法，由 MIT 的 Peter Shor 在 1994 年发明。如果该算法能够成功地用于大整数，那么 RSA 必须被放弃，或者模数必须变得更大，也许是数百万位。到目前为止，使用 Shor 算法，2001 年将数字 15 因式分解为 3×5，2012 年将数字 21 因式分解为 3×7。按照这个速度，我们可以期待到 2023 年左右将数字 35 因式分解为 5×7。

开个玩笑，Shor 算法对 RSA 安全性的真正威胁可能要几十年后才会出现。

18.12 超级计算机

量子计算机并不是为了评估表达式而制造的——至少目前不是。但让我们假设这只是一个技术问题。假设将来会有混合计算机，结合了超级计算机的计算能力和量子计算机的并行性。让我们称这些为超级计算机。

桑德拉今天可以做些什么来为艾米莉拥有超级计算机的时代做准备？我们可以从我们击败格罗弗算法的方式中获得启示（第 18.6 节）。我们扩大了密钥的大小，超过了算法的能力。这在超级计算机上也是可行的。我们可以增加计算机需要处理的未知数的数量，超出您估计超级计算机可能具有的任何能力。让我们看看这两个方面，替换和随机数生成。

这些算法将需要极其庞大的加密密钥。让我们简单地接受，在未来存在超级计算机的世界中，这样巨大的密钥将是可管理的。

18.12.1 替换

如果一个替换没有通过某种数学规则定义，那么它可以通过一个替换表来定义。表中的每个条目是桑德拉知道但艾米莉不知道的值。每个表条目可以被视为数学意义上的一个变量。最初，每个变量可以取任何值。如果艾米莉学到了其中一些值，那么对其他变量的选择就会变得更加狭窄，但最初任何字符都可以替换为任何其他字符。

桑德拉的目标是压倒超级计算机的能力。一个通用的多表密码手动使用 26×26 的表格，但计算机使用 256×256 的表格。这提供了 2¹⁶，或者 65,536 个未知值。然而，并没有理由限制表格中的行数为 256。如果艾米莉有一个超级计算机，那么桑德拉也有一个速度快、内存大的计算机是合理的。桑德拉可以使用 1024 行带有 10 位密钥的表格，或者使用 4096 行带有 12 位密钥的表格，甚至使用 65536 行带有 16 位密钥的表格。这需要 2²⁴ = 16,777,216 字节的内部存储空间用于替换表，远远在当前个人计算机的容量范围内。此外，对于 8 位替换使用 16 位密钥提供了非常理想的冗余性。让我们称这个 2²⁴元素的表格为Tab24。Tab24 的每一行都有自己的混合密钥。如果这个混合密钥有 256 位，那么整个表格就有 256×65536 = 16,777,216 位密钥。

对于桑德拉来说，使用完整的双字母频率表也是可行的。一个 256×256 的双字母频率表，使用 8 位密钥选择一行（实际上是一层），需要 2²⁵ = 33,554,432 字节的内部存储空间。同样，这在今天是可行的。如果表格有 65536 层和 16 位密钥，那么将需要一个更大的计算机。

但请记住，这些替换表必须保密，并且必须是完全随机的。即使它们是由某种算法生成的，也必须绝对超出艾米莉的超级计算机确定生成器的初始状态和参数的能力。请参阅第 13.13 节了解一些相关方法。

18.12.2 随机数

第 13.13 节的方法是一个很好的起点，但要制作一个能经得起超级计算机考验的伪随机数生成器，我们将第 13.11 节的选择生成器概念与第 13.15 节的刷新生成器技术相结合。

超级生成器 UG（发音为 HUGE-ee）使用三个数组，A、B 和 C。数组 A 和 B 各包含 65,536 个条目，每个条目都是 24 位整数。数组 C 包含 2²⁴，即 16,777,216 个条目，每个条目都是 8 位整数。这 3 个数组可以从自然照片中初始化，如第 13.14.2 节所述。桑德拉和里瓦必须有相同的数组。生成器在每个周期中产生一个 8 位输出。第 n 个周期包括以下步骤：

1. 计算 x = (A[n]+A[n-103]+A[n-1071]) mod 16777216，并将 A[n]替换为 x。

2. 减少 x = x mod 65536，并设置 y = B[x]。

   该周期内 UG 生成器的输出是 C[y]。

3. 将 B[x]替换为(B[x]+B[x-573]+B[x-2604]) mod 16777216。

4. 将 C[y]替换为(C[y]+C[y-249]+C[y-16774]) mod 256。

下标根据需要在模 65536 或模 16777216 下循环。103、1071、…、16774 这些滞后值并没有什么特别之处。我没有测试这些值是否产生特别长的周期。有了如此巨大的种子数组，即使是退化周期也会非常长。你可以使用第 13.1 节的任何组合函数，比如madd，或者第 13.14.1 节的滞后线性加法。

当你刷新这些随机数时，第 13.14 节的两种方法在你的对手拥有超级计算机时不足以使用，但它们可以结合起来制作一个强大的刷新函数。每次刷新时，你将需要一个包含 65,536 个或更多 24 位整数的新随机数组 R。让 A、B、C 和 R 的长度分别为 L[A]、L[B]、L[C]和 L[R]。

这里 a = ⌊L[C]/L[R]⌋-1。符号⌊L[C]/L[R]⌋，读作“L[C]/L[R]的底”，表示不超过 L[C]/L[R]的最大整数。例如，⌊8/3⌋是 2，⌊9/3⌋是 3。使用 C[an]而不是 C[n]的效果是将 R 的字节均匀分布在 C 数组中。

这两个步骤应该重复 3 次或更多次。如常，下标循环。

顺便说一句，C 数组的大小不一定必须是 2 的幂。L[C]可以是，例如，77,777,777，这种情况下 A、B 和 R 数组需要包含模 77777777 的整数，而模 16777216 将在上述计算中被 77777777 替换。对于 L[C]的大小的唯一限制是您希望使用的存储量以及分发如此大密钥的实际情况。

这两种技术，替换和随机数生成，可以结合起来制作任意数量的块和流密码，可以抵御超级计算机。接下来的两节介绍了每种类型的一种密码。

18.12.3 超替代密码 US-A

写这一节时的一个巨大诱惑是指定一个巨大的块大小，比如 65,536 甚至 16,777,216 字节。然而，仅仅因为在超级计算机时代加密必须改变，并不意味着消息的类型会改变。少于 100 个字符的消息仍然很常见，将这样的消息填充到 65,536 字节或更大的块大小将是极其低效的。

让我们将样本超替代密码称为US-A。US-A 密码以 32 字节或 256 位的块为单位运行。每个块中的 32 字节交替地被视为 32 个单独的字节和一个 16×16 位的位数组。US-A 密码有 15 轮，每轮包括 3 个步骤：替换、行置换和翻转数组。15 轮后跟着最后的替换步骤。

16 个替换步骤使用 Tab24 替换表，每个字符需要 16 个密钥位，每轮总共需要 16×32 = 512 位，或者 15 轮加上最后的替换需要 8192 位。每个 15 轮中的第二阶段是对每一行进行置换。这可能只是行的循环移位，每行只需要 4 位，因此每轮需要 64 位，总共 960 位。

对于位置换的更强选项是拥有一个置换表，比如 256 个不同的置换，比如密钥置换（第 7.6 节）。16×16 位矩阵的每一行将被单独置换。每行置换将由 16 个十六进制数字指定，比如5A3F1E940B2D68C7，意味着第一个位将移到位置 5，第二个位移到位置 A，即 10，依此类推。每行的置换将由一个 8 位密钥从表中选择，每轮需要 8×16 = 128 位，或者 15 轮总共需要 1920 位。

每轮的第三阶段是翻转位数组，即交换(i,j)处的位和(j,i)处的位。这在第 11.7 节中有描述，并且在第 11.2.3 节中给出了翻转数组的快速方法。这个阶段没有密钥。

让我们将所有 3 个阶段结合起来。US-A 密码需要 8192 位用于替换密钥，以及，比如说，1920 位用于密钥转置，总共是 10,112 位密钥。这远远不足以抵御超级计算机所需的 65,536 位。不用担心。别忘了，替换使用了 Tab24 表格，为了混合其 65,536 行，使用了 16,777,216 位密钥，更不用提用于混合置换表的比特数了。

为了额外的强度，我建议使用明文到明文（模式 PP）分块链接（第 11.10 节）与 US-A 密码。

18.12.4 超流密码 US-B

第 18.11.1 节的 Tab24 替换和第 18.11.2 节的伪随机数生成器可以结合起来制作一个强度极高的流密码。称其为US-B密码。US-B 在加密之前使用一个预处理步骤使明文具有随机外观。假设消息为 M，其长度为 L[M]。预加密步骤为

额外的 16 次循环迭代用于对消息的前 16 个字符进行双重哈希处理。这一步骤并不增加密码强度，但却使 Emily 很难辨认出她找到了正确的密钥。

每个 16 位字符密钥 K[n] 由随机数发生器生成的两个连续输出字节 x 和 y 组合而成，即 256x+y。（或者，你可以将 C 数组设为 16 位整数，但这会使所需存储空间翻倍。）密钥 K[n] 被用来在 Tab24 替换表中对消息字符 M[n] 进行加密，形式为 Tab24(K[n],M[n])。也就是说，M[n] 的替代字符取自表格的第 K[n] 行。

你可能会认出这是使用大型表格和随机密钥的通用多字母密码。请记住，法国人称多字母密码为不可破译的密码。使用 UG 超生成器，US-B 多字母密码最终在超级计算机时代也是不可破译的。我们已经实现了不可破解的加密。

附录 A：娱乐页面

这个图表中有四个独立的密码，从 S1 到 S4。每个密码都是一个简单的单表替换。你的任务是识别类型，比如摩斯码，然后解决它。每个密码都以标准英文书写，使用大写字母，不带空格或标点符号。每个密码长度介于 75 到 90 个字母之间。所有密码都从左上角单元格开始。前 3 个密码从左到右跨越行读取。最后一个密码按照顺时针方向沿着边界读取。

所有方法都在这本书中描述了。唯一的区别是视觉呈现方式。你需要确定每个密码中哪些特征是相关的，比如高度、宽度、位置或颜色。你可以按照本书其他地方隐藏的说明提交你的答案以获取学分。

这里有一些额外的有趣密码，使用了一些最流行的业余爱好者密码。这些密码是标准英文，带有一些专有名词。按照惯例，字母被分组为五个，不论周期。如果你想要更多类似的密码，可以考虑加入美国密码协会，网址为cryptogram.org。你可以按照本书其他地方隐藏的说明提交你的答案以获取学分。你可以在www.contestcen.com/crypt.htm找到更多要解决的密码。

F1：Belaso 密码（第 5.8.1 节）

F2：维吉尼亚密码（第 5.8.2 节）

F3：栏式置换（第 7.2 节）

F4：Playfair 密码（第 9.2 节）

F5：Bifid 密码（第 9.6 节）

区块大小为 7，主题是园艺。

F6：一次性密码本（第十四章）

对于消息中的每个字母，都生成一个随机数。如果这个数字是偶数，就对字母加上 X 对 26 取模，否则对 Y 对 26 取模。

当然，一次性密码本不是一种业余爱好者密码。我把它包括在内是为了说明一些一次性密码本密码在实践中是可以被破解的。你能看出如何找到 X 和 Y 的值而不尝试所有 676 种组合吗？

F7：通用多表密码（第 5.9.3 节）

为了增加乐趣，还有来自几种语言的字符，并且使用了超过 26 个字符。然而，每个字母表只包含了 26 个不同的字符，并且消息是标准英文。

附录 B：挑战

这些密码图被呈现给读者作为挑战。 方法未给出。 您的任务是确定方法并解决密码图。 提供了足够的材料，以便已确定方法的有经验的业余爱好者可以解决它。 在所有情况下，语言都是英语。 文本读起来正常且符合语法。 没有特别努力来扭曲标准英语字母频率或联系频率。

这些都是单步密码。 没有混合方法，比如将替换与置换相结合。 这些挑战密码被评为三级。

C1: 挑战 #1

这是一种纸笔密码。 明文由 250 个大写字母组成，没有单词间隔或标点符号。

C2: 挑战 #2

这个密码可以手工解密，但使用一些计算机辅助来管理十六进制表示会更容易。 明文由混合大小写的 200 个字符组成，带有单词间隔和标点符号。

C3: 挑战 #3

这个密码可以手工加密和解密。 明文由 180 个大写字母组成，没有单词间隔或标点符号。

第十九章：总结

这本书介绍了大约 140 种不同的密码，以及无数的变体。这可能会使一些读者困惑。他们可能只想知道一件事：“对我来说什么是最好的密码？”这个问题很复杂，因为这本书是为如此广泛的读者群体而设计的。在这个结语中，我希望提供一些有用的答案。

儿童：这里有几种儿童可以理解和使用的密码。他们可以使用简单的替换密码，尤其是凯撒密码。儿童特别喜欢字母被图片或符号替换的密码，比如🙂☽♡⚇⚓🎾🧙☼◈☆。儿童也喜欢路径置换。青少年可能会喜欢列置换和贝拉索密码。

爱好者：爱好者可能会喜欢与朋友交换密码，挑战彼此解密。最适合这样做的密码是简单替换、多表替换、自动密钥、流动密钥、Playfair、双密码、对角双密码、三密码、双方密码、路径置换、列置换、巴泽里斯和分数莫尔斯。

我鼓励爱好者加入美国密码协会，www.cryptogram.org，在那里他们可以提交他们的密码供其他会员解决，并解决其他会员提交的密码。他们的网页www.cryptogram.org/resource-area/cipher-types/列出了他们接受的密码类型。

开发者：想要开发或发明自己的密码的人会在这里找到许多方法，这些方法可以以无数种方式组合。字母可以被其他字母替换，或者被固定长度或可变长度的比特组、莫尔斯符号、任何数制的数字或数学环的元素替换。所有这些都可以进行置换和重新分组。组可以再次被替换、压缩、乘以大整数或矩阵，转换为其他数制，或者链接在一起。一些组的部分可以用来加密其他组的部分。

加密服务提供商：提供加密通信服务的公司通常使用自己的专有算法。他们可以使用开发者刚列出的任何技术，但他们必须确保他们的密码符合第十二章的所有标准。密码应该有大块和长密钥。它应该是高度非线性的，具有良好的扩散和饱和度。

如果服务提供商使用标准算法如 3DES 或 AES，那么标准密码应该在前后都加上一个有密钥的秘密替换或秘密置换。

银行业务：银行和金融公司被要求在所有通信中使用 AES，以便它们可以相互之间以及与美联储、证券交易委员会、国税局和其他政府机构进行信息交换。银行还广泛使用公钥密码学来建立加密密钥以及进行身份验证和验证。

军事和外交：美国军方和国务院根据 NSA 规定被强制使用 256 位 AES。这具有法律效力。这在个人电脑、笔记本电脑甚至带有 AES 芯片或 AES 软件的智能手机上完成。然而，军方和情报机构在可能计算机和手机无法工作的地方和条件下操作，或者一个配备 AES 的手机可能会引起怀疑或违法。在许多国家，拥有任何形式的密码设备、文献或工作成果都是非法的。此外，外国军队和外交团体可能会对来自 NSA 或受 NSA 监管的供应商的任何 AES 硬件或软件表示不信任。

由于这些原因，军队和情报机构都备有代码和密码来支持他们的电子加密设备。适用于战斗条件的手写密码包括对角线双字母密码、TwoSquare+1、Two Square ripple 和 Playfair TwoSquare。另一个想法是使用双字母密码或 Two Square，然后是逐块置换。

大文件：对于非常大的文件，使用流密码比块密码要快得多。您可以生成一系列伪随机数，并将其与数据文件组合以模拟一次性密码本。您可以使用 Xorshift、FRand 或 Gen5 进行 PRNG，并且可以使用xors、adds或poly进行组合功能。或者，您可以同时使用 GenX 进行生成和组合。