密钥密码学（三）(1)https://developer.aliyun.com/article/1508610
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。物理设备，如表面上的磁点，可以通过施加电流或磁场从一个值切换到另一个值。可能会有一个短暂的过渡，但设备不能停留在任何类型的中间或混合状态。
密钥密码学（三）(3）https://developer.aliyun.com/article/1508613
