密钥密码学（二）(2)

密钥密码学（二）(1)https://developer.aliyun.com/article/1508576

11.7.2 可逆多表代换

要构造一个可逆的多表密码，只需使表格的每一行都是一个可逆替换。

11.7.3 可逆置换

如果消息被分成固定大小的块，那么构造可逆置换最容易。让我们假设。称固定块大小为 B。如果每个从位置 X 移动到位置 Y 的字母，位置 Y 的字母移动到位置 X，则置换是可逆的。换句话说，置换将由字母的成对交换组成。

要构造一个可逆置换，首先在列表中写下从 1 到 B 的数字。从列表中选择任意 2 个数字。它们是交换的第一对位置。从列表中删除这 2 个数字，并从列表中选择另一对数字。这是第二对。从列表中删除它们。继续这样做，直到列表最多只剩下 1 个数字。如果您选择在置换中有一些固定点，只需更早地停止配对。创建固定点的另一种方法是随机从列表中一次选择 2 个数字。如果这两个数字相同，那就成为一个固定点。

表示一般置换密码的一种方法是列出块中的所有位置，然后在它们下面显示它们的新位置。例如，

这是计算机使用的最佳格式。当一个人在进行置换时，将其折叠到半宽可能更方便，就像这样：

这是相同的置换，但是在一半的空间中。任何一种形式都可以用作置换的密钥。在这两种情况下，第一个位置的字母移动到第 13 个位置，而第 13 个位置的字母移动到第一个位置，第二个位置的字母移动到第 7 个位置，而第 7 个位置的字母移动到第二个位置，依此类推。

*11.7.4 可逆块密码

现在我们已经看到如何构造可逆替换和置换，我们准备将这些元素结合在一起制作一个可逆块密码。

此时，引入更多符号会有所帮助。设 M 是任意消息，可以是明文或密文。我们将将密码 C 应用于该消息表示为 CM。如果 D 是另一个密码，则将 D 应用于文本 CM 的表示为 DCM。这种表示看起来有点奇怪，因为 DCM 意味着先应用 C，然后是 D，但这很有效。你可以将 DCM 理解为 D(C(M)) 的简写。

DC 然后是通过使用 C 和 D 分别进行加密形成的密码。这个新密码被称为 D 和 C 的 组合。组合是一种将两个密码结合起来形成新密码的操作。（有些作者称之为 C 和 D 的 乘积，并用 C◦D 表示。）

例如，Bazeries 类型 4（第 4.6.1 节）将替换与转位结合起来。组合具有一个对于形成可逆密码而言很重要的数学属性：组合是结合的。这意味着如果 A、B 和 C 是密码，则 (AB)C = A(BC)。由于这个属性，多个密码的组合可以不带括号地写成 ABC 或甚至 ABCDEFGH。在这样的组合中可以插入括号而不改变结果。例如，ABCDEFGH 可以写成 A((BC)(DE))F(GH)。

令 I 代表 单位密码，即将每个明文转换为其本身的密码。也就是说，对于任何消息 M，IM = M。设 C 是任意密码。将其逆表示为 C’。（C 必须有一个逆，否则消息就无法阅读。）然后 CC’ = C’C = I。当 C = C’ 时，密码 C 是可逆的。

假设 T 是一个可逆密码，C 是任意密码。那么密码 CTC’ 就是一个可逆密码。这是因为

类似地，如果 A 和 B 是任意密码，则 BCTC’B’ 和 ABCTC’B’A’ 都是可逆密码，依此类推。

11.7.5 例子，多重翻转

让我们看一个名为 多重翻转 的可逆分组密码的示例。这个密码对 64 位分组进行操作，其形式为 ABCTC’B’A’，其中 A 和 C 是一般的多表密码，B 是对 64 位进行的列转置，T 是对 64 位方阵进行翻转。

密码 A 和 C 是周期为 8 的多表密码。也就是说，每个分组的每一行都有一个单独的字母表。每个密码的表格都将有 8 行，按顺序使用。没有用于选择表格行的密钥。相反，8 个密钥用于混合 8 个字母表。总共，A 和 C 需要 16 个不同的密钥，每个密钥可能是与 SkipMix 算法（第 5.2 节）一起使用的数字序列。我建议这 16 个密钥每个包含 3 到 8 个数字，每个数字的范围是 0 到 255。

Cipher B 是一种列置换密码，将 64 位块视为 4×16 网格，因此有 16! 种列的排列方式。64 位被写入网格，从左到右横穿行读出，从上到下竖直读出。列的顺序由一个关键字、关键短语或等效的 16 位数字字符串确定。

Poly triple flip 被评为 Ten.******

11.8 可变长度替换

块密码可以使用固定长度或可变长度替换来构建。VLA 和 VLB 是使用可变长度替换的块密码的示例。VLA 和 VLB 块密码都使用 128 位块，分别视为每个 32 位的 4 行。其思想是在行中使用可变长度替换，然后通过在列中执行 4 位替换来混合块。每个密码的密钥是用于混合标签集和 4 位替换的密钥。

VLA 和 VLB 使用相同长度的后标签替换，如第 10.5.1 节所述。因此，一个 4 位标签被一个 4 位替换所取代，一个 5 位标签被一个 5 位替换所取代，依此类推。这样，块中的每一行保持为恒定的 32 位长。每次替换后，新标签被移动到其行的末尾，并且行被左移以保持其在 4 字节边界上。标签应该平均长度至少为 6 位。

VLA 是更简单的版本。在每轮中，您首先对行的最左边（高位）进行 4 位替换。然后您对每行执行一次后标签替换，带有位移。这将重复 32 轮。整个加密使用 128 个可变长度替换和 32 个固定长度 4 位替换。这个密码评级为 Eight.

当平均标签长度为 6 位时，我建议 VLB 应该有 4 轮，每轮在第 1 行有 6 次替换步骤，在第 2 行有 7 次替换步骤，在第 3 行有 8 次替换步骤，在第 4 行有 9 次替换步骤。

列中的垂直替换应在第 1、2 和 3 轮之后进行。为了提高速度，不需要在每一列的每一轮都进行列替换。一个合理的选择是例如在第一轮后每 3 列进行一次替换，即在第 1,4,7, … ,31 列，在第 2 轮后在第 2,5,8, … ,32 列进行替换，在第 3 轮后在第 3,6,9, … ,30 列进行替换。

VLB 被评为 Ten，可能是具有这个评级的最快密码。它需要 120 个可变长度替换，带有位移，并且 32 个垂直 4 位替换，因此比 VLA 稍快。

11.9 波纹密码

Ripple 密码，也称为 wraparound 密码或 end-around 密码，是基于本章前面的密码完全不同原理的块密码。其基本思想是，块中的每个 8 位字符都用作加密其右侧的下一个字符的密钥。然后再用这个字符来加密下一个字符，依此类推，一直到块的长度结束并在结尾处环绕。也就是说，块中的最后一个字符用作加密第一个字符的密钥。Ripple 密码最适合软件实现，因为它们几乎不提供并行操作的机会。

有各种各样的 Ripple 密码。它们的块长度可以从 2 开始，长度可以周期性地或随机变化。我建议最小的块长度为 5 个字符，但你可能更喜欢从 8 开始。例如，你可以使用链接的数字生成器来选择块长度。当生成器产生数字 D 时，你可以使下一个块的长度为 D+5，或者可能是 D+8，甚至是 20-D。

块可以重叠。例如，你可以使用固定的块长度为 8，块从位置 1、6、11、16、… 每 5 个字符开始。最后一个块可以环绕到消息的开头。当消息长度为 20 时，最后一个块可以由字符 16、17、18、19、20、1、2、3 组成。

Ripple 密码纯粹是替换密码；它们根本不涉及置换。Ripple 密码的最简单形式是对每个连续的字符进行异或，因此 x[n] 被替换为 x[n-1]⊕x[n]。然后 x[n+1] 被替换为 x[n]⊕x[n+1]，依此类推，通过整个块进行波动。

有很多种方法可以利用前一个字符来对下一个字符进行加密。下面是部分列表。这里 A、B 和 C 是简单的替换密码，P 是一般的多表密码。A(x)、B(x) 和 C(x) 分别表示用 A、B 和 C 加密的字符 x，而 P(k,x) 表示用密钥 k 选择表格中的行来加密 x。

由于xor或sxor可能会泄露有关其操作数的信息，我建议改用xors，这样在执行异或操作后进行简单替换以掩盖波形，即 A(x[n-1]⊕x[n])。

请注意，madd只是sadd的一个特例。也就是说，px[n-1]只是 A(x[n-1])的一个特定选择。madd的优点在于它不需要预先设置阶段来混合替换字母表。同样地，请注意 P(A(x[n-1]), B(x[n]))只是对表格的行和列进行排列，因此等同于 P(x[n-1], x[n])，只是使用了不同的表格。

这些涟漪方法中最强大的是poly，其中前一个字符 x[n-1]被用作选择用于加密 x[n]的表格中的行的关键。我将这种方法称为关键涟漪。这将需要一个 256×256 字节的表格。如果这太大了，可以通过在使用它作为密钥之前对 x[n-1]应用减少替换来将 x[n-1]减小到更小的范围。例如，x 可以被减小为 x mod 16，或者为(13x+5) mod 32。适当的减小范围是 0 到 15，0 到 31 和 0 到 63。如果 R 是减少替换，P 是多表替换，那么 x[n]将被 Q(R(x[n-1]),x[n])替换，其中 Q 是一个由 P 的表格顶部 16、32 或 64 行组成的减少表的多表密码。

如果您无法使用多表密码，也许是因为即使减少表格也使用了太多空间，或者因为设置时间太长，那么下一个最佳选择是使用 3 个简单替换。将 x[n]替换为 A(B(x[n-1])+C(x[n])或 A(B(x[n-1])⊕C(x[n])。这被称为空间-时间权衡。这 3 个简单替换可能比单个多表替换需要更长的时间，但它们将空间需求从 65,536 字节减少到 768 字节，减少了 98.8%。

涟漪密码不限于仅使用前一个字符来加密当前字符。如果愿意，可以回溯几个字符，例如用 A(x[n-i]⊕x[n])替换 x[n]，其中 i 可以是小于块大小的任何值。也可以使用多个先前的字符，例如 x[n-2]+x[n-1]+x[n]或更一般地 x[n-j]+x[n-k]+x[n]。使用通用多表替换，x[n]可以被 P(x[n-4]⊕x[n-2],x[n])替换，或者 P(x[n-5],P(x[n-1],x[n]))或其他无限组合。

正如我提到的，可以使用任何块大小。替换可以从块中的任何字符开始，并在块中的任何字符结束，只要每个字符至少被替换一次。如果需要，您可以绕块走几次，从最后一个字符到第一个字符。甚至可以重叠超过 2 个块，或者使一个块完全位于另一个块或一组块内。块大小、块内的起始位置、要替换的字符数以及与前一个和/或后一个块的重叠可以固定，可以定期变化，也可以随机生成。

涟漪密码甚至可以进一步发展。一条消息可以使用几轮涟漪密码进行加密。在每一轮中，消息可以被分成不同大小的块，以便块边界很少或从不对齐，并且加密在块中的不同点开始和结束。这会产生马赛克甚至万花筒效果。

涟漪密码的变体太多，无法一一列举。这些密码的评级可以从四到十不等。以下是一些示例。简单的xor涟漪使用固定大小的块，进行 2 轮替换，从块的第一个字节开始，以最后一个字节结束，并且只使用前一个字节作为替换密钥，评级为四。使用不同大小块的sadd涟漪密码，从块中的可变位置开始，进行至少 3 轮替换，以可变位置结束，并且使用前一个字节作为替换密钥，评级为七。使用不同大小块的poly涟漪密码，从块中的可变位置开始，进行至少 3 轮替换，以可变位置结束，并且使用前一个字节加上另一个从块到块变化的字节作为替换密钥，评级为十。马赛克方法比单层方法更强大。

11.10 块链接

块链接是一种增强任何块密码的有价值工具。块链接意味着使用每个块来帮助加密下一个块。实际上，链接是一个在块上操作的涟漪密码，而不是在单个字符上操作。从第 N 块传递到第 N+1 块的字节组称为链向量。由于消息中的第一个块没有前驱，大多数链接方案使用初始化向量（IV）来加密第一个块，就好像它是从某个虚构的前身块的链向量一样。初始化向量可以从加密密钥派生，也可以被视为加密的附加密钥。

旁注：比特币和其他加密货币使用的块链接是密码学中使用的块链接的一种专门形式。这就是他们得到这个想法的地方。

最常见的链接形式是逐字符将链向量与下一块结合起来。结合字符的最常见方法是独占或。然而，在第 11.8 节中描述的任何结合方法都可以使用。这通常以四种模式之一进行。

为了最大的强度，链接操作应该是累积的。首先，将第 N-1 块的链向量与第 N 块组合。这个结果成为新的链向量，与第 N+1 块组合。链接模式 PP 最强，链接模式 PC 次之。模式 CP 和 CC 远远较弱，因为艾米丽可以看到链向量。我建议只有在使用 xors、adds 和 poly 这些组合函数时才使用模式 CP 和 CC。

虽然 CC 和 CP 模式较弱，但使用它们有优势。在 CC 和 CP 模式下，无需单独的初始化向量。桑德拉可以使用明文消息的最后一个块作为初始化向量。瑞娃可以简单地先解密最后一个块。事实上，瑞娃可以解密任何块，而无需解密前一个块。如果密码使用指示符（第 14.3 节），则这可能非常有价值。瑞娃会首先解密指示块。

让我们来看一些更强的块链接方式。

11.10.1 多表链接

独占或（Exclusive-OR）是一种将第 N 块与第 N+1 块结合的弱方法。一种更好的方法是 xors，即首先使用独占或，然后对结果字符进行简单的替换。比那更好的是使用 poly，一种通用的多表密码。使用链向量中的每个字符作为密钥，选择用于加密第 N+1 块中相应字符的表中的行。可以使用任何 4 种链接模式。模式 PP 最强大。

11.10.2 加密链接

链接的标准模式将第 N 块的明文或密文作为链向量使用，不进行修改。将某些加密应用于链向量会更强大。这可以是简单的，如简单的替换或分段反转（第 4.6 节）。如果替换或置换对于每个块都不同，这种简单的方法可能是有效的。钥匙脉冲很适合这个目的（第 11.8 节）。用于链向量的加密应具有自己独立的密钥。如果链向量更强加密，模式 CC 和 CP 将不再是弱项。

11.10.3 拖延链接

链接不仅限于前一个块。链接还可以利用更早的块。块 N 可以与块 N-i 或多个先前的块组合，例如块 N-i 和块 N-j。如果 i > j，则需要 i 个块的初始化向量。

同样，链接向量可以跨越多个先前的块。例如，链接向量可以来自第 N-2 块的后半部分和第 N-1 块的前半部分。

11.10.4 内部 tap

使用明文或密文作为链接向量的一个弱点是，这些内容可能为 Emily 所知。一个解决方案是对链接向量进行加密，如第 11.10.2 节所述。第二个解决方案是从块加密的某个中间轮获取链接向量。这称为 tap。例如，如果块密码有 10 轮，您可以使用第 5 轮的输出作为链接向量。在开始加密下一个块之前，将此链接向量与下一个块的明文组合。这是模式 IP。

这可以进一步发展。您可以使用多个 tap，它们可以与以下块的多个位置组合，可以与明文、密文或加密的轮之间组合。每个 tap 产生一个单独的链接向量，因此对于 N 个 tap，您必须有 N 个初始化向量。这些链接向量可以使用相同的密钥加密，或者每个都可以有自己独立的密钥。涟漪密码（第 11.8 节）非常适合加密链接向量。

11.10.5 密钥链接

通常，链接是在每个块的文本上进行的。但是，也可以将链接与密钥一起使用。假设您有一个块密码，其中每个块都使用相同的密钥 K。通过链接，可以极大地增强该密码。您使用 K 作为密钥对第一个块进行加密（初始化向量对于密钥链接是可选的）。然后，您可以使用 K●P[1]、K●C[1] 或 K●I[1] 作为密钥对第二个块进行加密，其中 ● 表示逐字节执行的某种组合函数，例如 xors 或 adds。同样，您可以使用 K●P[2]、K●C[2] 或 K●I[2] 作为密钥对第三个块进行加密，依此类推。这给您带来了三种新的链接模式，PK、CK 和 IK。可以同时使用密钥链接和块链接，例如 PK 与 IP。这是一种非常强大的组合。

11.10.6 链接模式总结

总共有 12 种可能的链接模式。链接向量可以来自三个来源之一：明文、内部阶段或当前块的密文。链接向量可以与四个目标之一结合使用：密钥、明文、内部阶段或下一个块的密文。

除了这些选择之外，链向量可以每次都新生成，也可以与前一个分组的链向量合并。链向量可以原样使用，也可以在与目标合并之前加密。链接可以作用于连续的分组，也可以滞后。有很多很多选择。

11.10.7 链接短分组

当消息中的最后一个分组较短，并且您使用重叠方法（11.2.4 节）来处理短分组时，不清楚如何链接重叠的分组。解决方法是从倒数第二个分组开始链接。如果有 N 个分组，则从第 N-2 个分组的链接向量用于第 N-1 个分组和第 N 个分组。

11.10.8 链接可变长度分组

在我们离开分组链接主题之前，还有一个问题需要解决，即可变分组大小。我建议链向量保持固定长度。如果消息分组的长度 L 小于链向量的长度，则将链向量的前 L 个字节与消息分组结合。替换链向量的这些 L 个字节，保持其余部分不变。例如，如果链向量为 1234567890，而分组为 SAMPLE，则将 123456 与 SAMPLE 结合。如果结果是 ZQm”w+，则分组变为 ZQm”w+，链向量变为 ZQm”w+7890。

如果链接向量短于消息分组，则使用所需数量的自身副本扩展此分组的链接向量。例如，如果链接向量为 123456，而分组为 CONVENTION，则将 1234561234 与 CONVENTION 结合。如果结果是 qA&Vm!7^oS，则分组变为 qA&Vm!7^oS，链接向量变为 qA&Vm!。

在两种情况下，分组在链接后仍保持相同的长度，链向量也保持相同的长度。

11.11 加强分组密码

一旦您拥有了强大的分组密码，就可以通过很少的额外工作进一步加固它。所需的只是在应用分组密码之前轻微地加密明文，并在完成分组密码后轻微地加密密文。我称之为三明治技术，额外的步骤称为预加密和后加密步骤。如果你感觉顽皮，你可以称之为鲁宾三明治。所谓“轻微地”，我是指使用简单的一轮一步密码，例如简单替换或密钥置换（7.6 节）。例如，您可以在分组密码之前使用简单替换，之后使用密钥置换，或者反之亦然。一种更强大但更快速的选择是将分组的前 8 个字节视为两个 32 位整数，并将每个整数乘以范围在 3 到 2³²-1 的奇数乘数模 2³²。

由于块密码已经足够强大，这些额外步骤的主要目的是增加总键大小，以阻止暴力破解攻击和中间人攻击。这在预密码和后密码步骤具有长键且与块密码键独立的情况下效果最佳。例如，如果预密码或后密码是简单的替代，它可能具有长的 SkipMix 密钥。

作为一个实际的例子，DES 使用了一个小的 56 位密钥。如果您添加了简单的替换预密码和后密码步骤，每个步骤都有一个独立的 64 位混合密钥，那么总密钥大小将达到 184 位。这比 3DES 更强大，几乎快 3 倍。

DES，然而，是没有任何设置阶段的设计。预密码可以轻松完成，没有设置。只需将一个 64 位的预密码密钥与明文进行异或运算。这将总键大小从 56 位增加到 120 位。这单独就比 2DES 更强大，更抵抗中间人攻击。后密码步骤有点棘手。我们希望避免使用异或作为最后一步，原因前面已经讨论过，并且我们也不想有设置。这可以通过使用固定的多表密码来实现。也就是说，表格是事先选择并内置到设备或软件中。

一个可能性是使用 16×16 的 4 位组表。64 位块被视为十六个 4 位组。每个 4 位组使用 64 位后密码键的 4 位进行加密。因此，总键大小再次为 184 位。这也比 3DES 更强大，几乎快 3 倍。

这种方法有效的原因是 DES 本身已经足够强大，以至于唯一实际的攻击是暴力破解。将额外的 128 位添加到密钥使暴力破解变得不可行。

第十二章：安全加密的原则

本章涵盖

• 安全加密的五个原则
  
• 大块和长密钥
  
• 混淆或非线性
  
• 扩散和饱和
  

让我们将在第十一章学到的一切汇总起来。在 12.1 到 12.5 节中，我们将概括出使块密码安全的 5 个基本原则。安全块密码的一个标志是，改变密钥中的任何位或明文中的任何位将导致密文块中约 50%的位发生变化，最好是以看似随机的模式。改变任何其他位也会导致密文块中约 50%的位发生变化，但是以不同的模式。让我们称之为五五开特性。本章将描述如何实现这一点。

12.1 大块

我们已经看到，双字母密码可以像简单替换密码一样解决，方法是编制双字母频率和接触频率。这也可以用于三字母和四字母，尽管需要大量的密文。对于手工完成的块密码，应考虑的最小块大小是 5 个字符。对于计算机密码，最小块大小是 8 字节。大块大小的一个目的是防止 Emily 像解码一样解决密码。也就是说，Emily 会找到重复的密文块，并从它们的频率和在消息中的位置推断它们的含义。以极端情况为例，如果块大小为 1 个字符，那么无论密钥有多大，使用了多少加密步骤，密码仍然只是一个简单的替换。

在英语中有许多 8 个字符的序列是足够常见的，以至于在长消息中会重复出现。以下是一打例子，使用省略号…表示空格。

如今的标准块大小是 16 字节。没有那么长的高频英文短语。可能会有一些长的上下文短语，比如 UNITED STATES GOVERNMENT，EXECUTIVE COMMITTEE，INTERNATIONAL WATERS 等等。然而，要产生重复的密文块，这些明文重复必须以相同的方式与块边界对齐。例如，16 字节的明文块 UNITED**…STATES…GO 和 NITED…STATES…**GOV 在使用强大的块密码时不会产生可识别的密文重复。

当您使用块链接（第 11.9 节）时，重复的密文块问题消失了。使用块链接时，可以使用任何大于等于 8 字节的块大小。

12.2 长密钥

我们知道，安全的密码必须具有一个大密钥以防止暴力破解攻击。当前的标准是 128 位密钥。如果您希望您的消息保密 20 年或更长时间，我建议最低使用 160 位。这相当于约 48 个十进制数字，40 个十六进制数字或 34 个单个字母。

如果你是手动输入密钥，我建议你以统一的方式构建你的密钥。用一致的格式将密钥分成相同大小的块。这里有两种统一结构密钥的样式。在第一种样式中，每个块中的所有字符都是相同类型的，大写字母、小写字母或数字。在第二种样式中，块的格式相同，有两个大写字母和三个数字。

这两个密钥中的第一个相当于约 191 位，第二个相当于约 174 位。对于这样长的密钥，你必须能够在输入时看到字符，以便在需要时进行复查和更正。当密钥完成时，应用程序应显示一个校验和，以便您验证密钥是否正确。

这种规律的一个好处是防止将字母 O 误认为数字 0，或者字母 I 误认为数字 1。我不建议随机混合字符，比如**KaTeX parse error: Expected 'EOF', got '}' at position 7: v94H;t}̲=Nd⁸**，因为这会导致错误…v94H;t}=Nd⁸加密了一个数据文件，然后你用密钥$V94H;t}=Nd⁸**解密它，那么该数据文件现在可能无法恢复。你可能永远都不知道出了什么问题以及如何解决。在你的密钥中使用统一的块有助于防止这种灾难发生。

另一种有助于防止输入错误的密钥形式是人工词。制造你自己的可以发音的字母组合，就像这样：

尽量避免模式，比如使用相同的元音组合，palek mafner vadel glabet之类的，所有单词都使用 A-E 元音模式。

这些字母数字密钥可以被软件转换成二进制形式。madd连锁密码（第 11.8 节）非常适合这个任务。

作为加密每条消息或数据文件的关键字的替代方案是使用一个关键字管理器，它生成关键字并将它们与消息或文件关联起来。关键字管理器可以安装在一个对桑德拉和里娃都可访问的网站上。这个话题不会在本书中涵盖。请注意，关键字管理器与密码管理器不同，因为桑德拉和里娃在不同的计算机上工作时必须为每个文件使用相同的关键字。

12.2.1 冗余密钥

在某些情况下，艾米丽可能会设计方程，将密文与明文和密钥相关联。如果艾米丽知道或能够猜测一些明文，这些方程可能使她能够确定密钥。例如，她可能知道一些消息以全大写字母 ATTENTION 开头。这可能足以使她在使用 8 字节块大小时解决 64 位密钥。

战胜这种潜在攻击的一种方法是扩大密钥。 例如，如果块大小为 64 位，但密钥大 32 位，即 96 位，则您可以期望，平均而言，会有大约 2³²个可能的密钥将已知的明文转换为密文。 艾米莉需要筛选这 2³²个解决方案以找到正确的解决方案。 这可能是一项困难的任务，因为超过 4,000,000,000 个可能性中的许多可能看起来像合理的文本。

扩大密钥会使艾米莉的任务变得更加困难，但不一定是不可能的。 如果她有两倍于已知明文的量，则可能使用两个密码块的方程式来解出密钥。 但是，拥有这么多已知明文是非常罕见的，解决两倍数量的方程可能需要的时间远远超过两倍。 根据艾米莉使用的方程式类型，解决一组 64 个方程可能是可行的，但解决一组 128 个方程可能是不可行的。

如果艾米莉没有可解的方程式，则冗余密钥可使暴力攻击变得更加困难和昂贵。 无论如何，冗余密钥都会使艾米莉工作更加艰难。

12.3 混淆

在 1945 年，信息论创始人克劳德·香农描述了强密码必须具备的两个属性。 他称这些为混淆和扩散。 通过混淆，香农指的是明文和密文之间不应有强相关性。 同样，密钥和密文之间也不应有强相关性。 通过扩散，香农指的是密文的每一部分都应该依赖于明文的每一部分和密钥的每一部分。

我将添加到香农两个属性的第三个属性。 我称这个属性为饱和。 这个想法是衡量密文的每一位或每一字节如何依赖于明文的每一位或每一字节以及密钥的每一位或每一字节。 饱和度越高，密码就越强。 本节以及接下来的两节将详细讨论这三个属性，混淆、扩散和饱和。

在分组密码中有两种替换类型，固定和键入。 键入的替换是可变的，可以为每个消息甚至每个块更改。 在第 11.6 节中讨论了这些方法的利弊。 如果您决定使用键入的替换，或者如果您发现本节中的数学很困难，那么您可以直接跳转到第 12.4 节。 您可以使用在第 5.2 节和 12.3.7 节中描述的 SkipMix 算法构建您的混合字母表或表，然后使用伪随机数生成器选择跳过的顺序。

在香农的理解中，混淆基本上是线性与非线性的问题。 如果您的分组密码使用固定的字母表或表格，线性性质至关重要。 整个线性代数领域都建立在线性概念上。 线性性 这个术语来自解析几何学。 一条直线的方程是 ax+by = c，其中 a、b 和 c 是常数，变量 x 和 y 表示直线上某点的笛卡尔坐标。 如果直线不与 y 轴平行，方程可以表示为 y = ax+b。 ax+by = c 和 y = ax+b 都是线性方程或线性关系的例子。

凯撒密码（第 4.2 节）是线性密码的一个例子。 凯撒密码可以被看作是将密钥加到明文上以获得密文，c = p+k。 这里 c 是密文字母，p 是明文字母，k 是密钥。 密钥是字母已经移动的量。 凯撒大帝使用了一个移位为 3 位的密码，这意味着字母表中的每个字母都被替换为后面 3 位的字母，c = p+3，字母接近字母表末尾的位置将被移到字母表的开头。

顺便说一句，凯撒的方法并不像听起来那样脆弱，因为凯撒用希腊字母写他的信息。 在凯撒时代，受过良好教育的上层罗马人，如凯撒及其将军，懂希腊语，就像 19 世纪的上层英国人学习拉丁语和贵族俄罗斯人说法语一样。

在涉及替换步骤和置换步骤的分组密码中，如果单个替换是非线性的，则整个密码是非线性的。 实际上，如果分组密码有多轮替换，那么只要有一个早期轮次是非线性的，整个密码就是非线性的，前提是该轮次涉及块中的所有单元。 一旦失去了线性性质，就无法在后来的轮次中重新获得它。 让每一轮都是非线性的将会更加强大，但是即使只有一个非线性轮次，特别是如果它出现在开始位置，也比没有强。

有线性和非线性的程度。 替换可以是高度线性的、弱线性的、弱非线性的或高度非线性的。 每种情况的一个例子应该可以说明问题。 我已经在明文字母表中的每个字母位置与密文字母表中的对应位置之间画了一条线。 你可以立即看到，随着替换变得更加非线性，字母表的混合程度有多好。

在接下来的讨论中，我将 S 盒的输入称为明文和密钥，将输出称为密文。这些术语指的是该单个 S 盒的明文和密文，并不一定是整个多轮分组密码的明文和密文。在某些分组密码中，S 盒没有密钥，它们仅执行简单的替换。在这种情况下，你可以想象 S 盒具有一个密钥，其常量值为 0，或者 S 盒密钥的长度为 0 位。

假设 Emily 能够测试 S 盒的线性度，因为密码已经发表，或者她已经获得了该设备的副本。如果 Emily 所拥有的仅仅是第一轮的输入和最后一轮的输出，那么线性度测试可能就不可行了。

12.3.1 相关系数

有一种既定的统计方法用于测试两个数值变量之间的相关性。例如，你可以测试温度和阳光之间的相关性，温度以摄氏度度量，阳光以小时为单位度量。温度和小时是数值变量。你可以进行多次试验，在某个固定的时间测量温度，并记录那天的阳光小时数。这将为你提供两个数字列表，一个列表用于温度，另一个列表用于相应的阳光小时数。该统计量衡量这两个数字列表之间的相关性。

在我们的情况下，两个变量是明文字母和密文字母。“试验"是字母在字母表中的位置。例如，第一个试验可以是"A”，最后一个试验可以是"Z"。字母表中的字母需要以某种方式编号。编号将取决于字母表的大小。例如，一个 27 个字母的字母表可以使用 3 个三进制（基数 3）数字编号，就像我们在第 9.9 节中对三肽密码所做的那样。相关性可以是明文字母的任何三进制数字与密文字母的任何三进制数字之间的相关性。在接下来的两节中，我将详细讨论这一点，分别讨论 26 个字母的字母表和 256 个字符的字母表。

线性度通过计算两个变量之间的相关性来衡量。到目前为止，最广泛使用的相关性度量是由英国数学家卡尔·皮尔逊（Karl Pearson）开发的皮尔逊积差相关系数，他是生物统计学的奠基人，并于 1895 年发表，尽管这个公式本身在 1844 年由法国物理学家奥古斯特·布拉维斯（Auguste Bravais）发布，他以晶体学的工作而闻名。相关系数的目的是得到一个单一的数字，告诉我们两个变量的相关程度，这个数字的含义不受测量单位或所涉及的数字大小的影响。

如果两个变量具有线性关系，则相关性为 1。如果变量之间没有任何相关性，则相关性为 0。如果两者具有反向关系，则相关性为-1。例如，抛硬币 20 次中正面朝上的次数与反面朝上的次数将具有反向关系。相关性为 0.8 表示强烈的线性关系，而相关性为 0.2 表示关系高度非线性。

与大多数教科书一样，我不仅仅是呈现公式，我将解释它是如何以及为什么有效的。理解它的工作原理将帮助您正确和适当地使用它。

这里的目标是比较两个变量。这是通过比较一系列试验中的值来完成的。例如，我们可能想比较在伊斯法罕的凯萨里耶巴扎尔出售的魔毯价格与其尺寸。影响魔毯价格的因素有很多，包括纱线类型、结的密度、设计的复杂性，当然还有飞行速度。

居中

比较变量的第一步是将它们并排放置，就像您通过视觉比较它们一样。换句话说，您希望消除线性关系 P = mA+x 中的+x 项，其中 P 是价格，A 是面积。看起来您可以计算差值 P[i]-A[i]，然后从 P 中减去平均差值。然而，这是没有意义的，因为 P 和 A 是以不同单位表示的。地毯面积 A 以平方阿尔萨尼（大约一米）为单位，而巴扎尔中的地毯价格 P 以图曼（波斯货币）计价。

您需要分别调整面积数字和价格数字，因为它们是以不同单位表示的。诀窍是取平均价格并从所有价格数字中减去以获得新的调整后的价格数字 P’。您通过将地毯价格相加并除以地毯数量来计算平均价格μ[P]。例如，如果价格分别为 1000、1200 和 1700 图曼，您将把这 3 个价格相加 1000+1200+1700，然后除以 3 得到平均价格 1300。您将从每个价格中减去 1300 以获得调整后的价格-300、-100 和 400。正如您所看到的，调整后的价格 P’相加为 0。在某种意义上，调整后的价格围绕 0 居中。

区域图形以相同的方式居中。您将所有区域相加，然后除以地毯数量得到平均面积。例如，如果面积分别为 10、12 和 17 平方阿尔萨尼，您将把这 3 个面积相加 10+12+17，然后除以 3 得到平均面积 13。然后，您将从每个面积中减去 13 以获得调整后的面积-3、-1 和 4。调整后的面积 A’也相加为 0。现在，调整后的面积和调整后的价格都围绕 0 居中。它们并排放置，准备进行比较。

缩放

下一步是将价格和面积放在同一尺度上。价格是以土曼为单位的，面积是以平方阿尔萨尼为单位的，而从土曼到平方阿尔萨尼的转换是不存在的。那就像是从蒲式耳到摄氏度的转换一样。皮尔逊，或者更确切地说是布拉维，使用了线性代数中的一个概念，称为归一化。

假设你有一个向量（a，b），你想找到一个指向同一方向的向量，但长度为 1。任何向量（a，b）的倍数，比如（ma，mb），都会指向同一方向。乘以一个向量会改变它的长度，但不会改变它的方向。如果你将向量除以它的长度，新向量（a/L，b/L）的长度将为 1，并且方向与原始向量相同。这也清除了单位。想象一下，向量的长度是用英尺来衡量的。如果你将向量除以它的长度，那么你得到的就是英尺除以英尺。结果只是一个数字，没有单位。它是无量纲的。当向量用土曼或平方阿尔萨尼来衡量时，情况也是如此。

向量的长度可以很容易地通过使用勾股定理找到，L = √(a² + b²)。这可以扩展到任意维度，L = √(a² + b² + c² + …)。让我们试一个例子来看看这是否有效。尝试向量（3，4）。这个向量的长度是 √(3² + 4²) = √(9 + 16) = √25 = 5。归一化向量是 (3/5,4/5)。因此 √((3/5)² + (4/5)²) = √(9/25 + 16/25) = √25/25 = 1 是归一化向量的长度，如预期的那样。它有效。

P、A、P’ 和 A’ 都是数字列表，因此它们是向量。它们像任何向量一样有长度，并且可以像任何向量一样归一化。在几何学中，通过将向量除以其长度来归一化向量。任何归一化向量的长度始终为 1。

要将 P’ 归一化，你只需对所有调整后的价格进行平方，然后将这些平方相加并取这个和的平方根。这给出了 P’ 的长度。将调整后的价格 P’ 除以长度得到归一化价格 P’‘。要将 A’ 归一化，你只需对所有调整后的面积进行平方，然后将这些平方相加并取这个和的平方根。这给出了 A’ 的长度。将所有调整后的面积 A’ 除以长度得到归一化面积 A’'。

总结一下，（1）通过减去平均值来将价格和面积居中，然后（2）通过除以长度来归一化价格和面积。结果是一个标准化的价格列表和一个标准化的面积列表，其中每个列表中项的总和为 0，每个列表中项的平方和为 1。

现在我们准备好使用公式了。将价格的归一化列表中的每一项乘以面积的归一化列表中的相应项，即 P’‘[i]×A’'[i]。将这些乘积相加。这就是相关系数。（在线性代数中，这被称为归一化价格向量和归一化面积向量的内积或点积。）

让我们对此进行现实检验。想象我们正在测试摄氏温度和华氏温度之间的相关性。我们知道它们通过线性公式 F = 1.8C+32 相关，因此相关系数应该为 1。假设我们在上午 11 点、下午 3 点、晚上 7 点和 11 点测量温度，并发现摄氏温度分别为（14，24，6，0），华氏温度为（57.2，75.2，42.8，32）。摄氏温度的平均值为（14+24+6+0）/4 = 11，因此调整后的摄氏温度 C’ 为（3，13，-5，-11），对应的调整后的华氏温度 F’ 为（5.4，23.4，-9，-19.8）。摄氏温度 C’ 的长度为 18。将 C’ 除以 18 得到 C’‘，归一化后的摄氏温度（3/18，13/18，-5/18，-11/18）。调整后的华氏温度 F’ 的长度为 32.4，归一化后的华氏温度 F’’ 为（3/18，13/18，-5/18，-11/18）。

我们将 C’’ 逐个元素与 F’’ 相乘，然后将 4 个乘积相加以得到相关系数。这个和是（3/18）²+（13/18）²+（-5/18）²+（-11/18）²。总和为 1。这支持了先前描述的过程，即通过减去平均值进行居中，通过除以长度进行归一化，然后逐项相乘并求和，确实产生了有效的相关系数。

总结一下：通过计算相关系数来测试线性。本节向您展示了如何计算相关系数。计算结果为介于-1 和+1 之间的数字。以下是解释相关系数的图表。

12.3.2 基-26 线性

让我们从基于 26 个字符的字母表的替换开始调查线性。如果您正在设计机械或机电密码设备，或者正在模拟这样一个设备，这可能很有价值。这种机器中的每个转子都对一个包含 26 个字符的字母表进行替换。首先考虑一个没有密钥的 S-box。在使用 26 个字母表时，可能会出现多种形式的线性，这取决于字母的编号方式。可以从 3 种方式来看待字母表：将字母表视为一个 26 个字母的序列，将其视为一个 2×13 的字母数组，或者将其视为一个 13×2 的字母数组。这导致 3 种不同的字符编号方式：N1、N2 和 N3，如所示。对这 3 种编号方案的讨论使用模运算。如果您现在想复习模运算，请参阅第 3.6 节。

编号方案 N2 和 N3 遵循常规约定，使用字母 A、B 和 C 表示 9 以外的数字。也就是说，它们使用了 16 个十六进制数字中的前 13 个。在最简单的线性加密（Belaso 密码）中，密钥只是加到明文中。当将密钥加到明文字符中时，在 N1 编号方案中，它使用传统的模 26 加法。当将密钥加到 N2 编号方案中的明文字符时，第一个数字是模 2 加法，第二个数字是模 13 加法。相反，当将密钥加到 N3 编号方案中的明文字符时，第一个数字是模 13 加法，第二个数字是模 2 加法。以下是展示单词 THE 如何在每种方案中通过添加密钥 J 进行加密的示例。

如果纯文本、密钥和密文字母都使用 N1 方案编号，则线性替换或线性变换会将明文字符 p 转换成密文字符 c = mp+f(k)，其中 m 是一个乘数，必须与 26 互质，f(k) 是任意整数值函数，算术运算是模 26 运算。例如，如果 m = 5，p = 10，k = 3，而 f(k) = k²+6，则 c = 13，因为 5×10+3²+6 = 65 ≡ 13 (mod 26)。常数 m 和函数 f(k) 可以构建到替换表中。

如果纯文本、密钥和密文字母都使用 N2 或 2×13 编号方案进行编号，则第一个数字或第二个数字或两个数字都可以是线性的。假设两个数字都是线性的。那么，一个明文字符 p = a,b 使用密钥 k 转换成密文字符 c = ma+f(k),nb+g(k)，其中 m 必须与 2 互质，即 m = 1，n 必须与 13 互质，而 f(k) 和 g(k) 可以是任意整数值函数。分别进行模 2 和模 13 运算。常数 m 和 n，以及函数 f(k) 和 g(k) 可以构建到替换表中。

如果纯文本、密钥和密文字母都使用 N3 或 13×2 编号方案进行编号，则第一个数字或第二个数字或两个数字都可以是线性的。假设两个数字都是线性的。那么，一个明文字符 p = a,b 使用密钥 k 转换成密文字符 c = ma+f(k),nb+g(k)，其中 m 必须与 13 互质，n 必须与 2 互质，即 n = 1，而 f(k) 和 g(k) 可以是任意整数值函数。分别进行模 13 和模 2 运算。常数 m 和 n，以及函数 f(k) 和 g(k)，可以构建到替换表中。

平文和密文没有必要以相同的方式编号。在任何编号中，平文的任何数字与密文的任何数字之间都可能存在相关性。艾米莉可能会测试这些组合中的任何一个或全部，寻找可利用的弱点。因此，密码的设计者必须测试所有可能的编号和相关性，以验证没有这种弱点存在，或者了解必须采取哪些对策以防止艾米莉利用这种弱点。例如，您可以在分组密码的交替轮次中使用具有不同弱点的替换。在大多数情况下，每个替换都会减弱另一个的弱点。当然，您应该通过搜索明文和最终密文之间的线性关系来测试这一点，后者是由最后一轮产生的。

如果你想测试替换的线性性，就不能直接应用相关系数。这是因为所有这些替换都是使用模算术完成的。考虑一下使用 N1 编号方案进行的这种替换：

这几乎完全是 c = 2p，所以它非常线性。然而，使用该编号方案计算的明文和密文字母之间的相关系数为 0.55556，表明替换只是弱线性的。应该使用以下分布计算相关系数，该分布在模 26 下是等效的。

使用该编号的相关系数为 0.99987，正确显示了非常强的线性性。

这说明了在密码学中使用相关系数的困难。你总是在字母表的大小模下工作。要找到正确的相关性，你需要添加 26，然后是 52、78 等等，对于 N1 编号是这样，或者对于 N2 和 N3 编号是 13、26、39 等等。在前面的例子中，你需要开始添加 26 的地方是显而易见的。它是在密文编号变为22 24 1 3的地方。从 24 降到 1 就表明了这一点。

当密文字母表的线性性较低，即在一定程度上跳动时，可能更难以发现。例如，这种替换的相关性为 0.3265，具有中度非线性。

当通过这种方式调整时

相关性变为 0.9944，非常线性。我已经使用单个、双重和  下划线来显示在密文字符中添加了 26、52 和 ，分别对应的是明文字符。在此要注意的一个重要特征是，在密文字符 2 处添加了 26，对应于明文字符 5，但没有添加到后续的密文字符 21 和 25。同样，对于密文字符 1，添加了 52，对应于明文字符 14，但没有添加到后续的密文字符 24。

当密文字母接近线性时，确定要添加的 26 的倍数相当容易。当密文字母行为不良时，这变得更加困难。但是…那没关系。当替代是非线性的时候，这就是您需要知道的全部。相关系数是 0.01 还是 0.35 都没有关系。在任一情况下，没有足够的相关性供 Emily 利用。不要浪费时间计算精确值。

处理没有密钥的情况。现在假设有一个密钥。如果替代是线性的，那么它将具有形式 d§+f(k)，其中 p 是明文，k 是密钥，d 和 f 是整数值函数。加法可以在任何 3 个编号方案 N1、N2 或 N3 中进行。在这种情况下，密钥在测试线性方面没有任何作用。f(k)只是添加到密文的常量。添加常量对相关系数没有影响，因为当您从每个值列表中减去均值（居中操作）时，它只是被再次减去。很容易测试替换 S(k,p)是否采用形式 d§+f(k)。只需选择两个密钥 k[1]和 k[2]，并取差异 S(k[1],0)-S(k[2],0)，S(k[1],1)-S(k[2],1)，S(k[1],2)-S(k[2],2)，…如果 S-box 具有形式 d§+f(k)，那么所有这些差异将相等。如果您对所有可能的密钥重复这样做，那么您可以确定 S(k,p)具有所需的形式，并且您可以在不考虑密钥的情况下测试线性。

12.3.3 256 进制线性

对于 26 进制线性的分析只是对 256 进制线性的热身，因为在 256 进制中可能会发生两种不同的线性形式。我们称它们为串行和压缩。在串行线性中，每组位代表一个整数。例如，3 位组 000、001、010、…，111 表示数字 0、1、2、…，7。可以将两种形式的线性结合起来，以制作混合形式的线性。这在第 12.3.6 节中讨论。

串行线性是我们在 26 进制中看到的。在 26 进制中，N1、N2 和 N3 编号之间可能存在任何组合和任何顺序的相关性，因此必须测试许多成对是否具有线性。在 256 进制中有更多的可能性。串行线性可能存在于明文字母和/或密钥与密文字母中的任何位组之间。这些位组的大小不必相同。从明文中取出的 4 位组，覆盖范围从 0 到 15，可能与覆盖范围从 0 到 7 的 3 位密文组高度相关，因此可能的配对数量更多。

事情变得更糟，那个 4 位组中的 4 位可能是明文字节中的任意位。按顺序的位 7、2、5、1 和位 1、2、3、4 一样有效。线性替换可能将这 4 位加到密钥字节的 4 个不同位上，取模 16。可能的组合数量变得巨大。总之，明文字符和密钥字符中任何顺序的任何位组合都可能与密文字符中任何顺序的任何位组合线性相关。这是一大堆需要测试的相关性。

在你伸手拿阿司匹林或者龙舌兰酒之前，这里有个好消息。你可能不需要测试它们中的任何一个。除非密码是专门设计成从一轮传递到下一轮保持这些值不变，否则这些相关性不会有所影响。它们会随着每一轮的进行而逐渐削弱，以至于从初始明文到区块密码的最后一轮都不会被检测出来。

添加后门

你可能已经注意到我说了“可能”。例外情况是当你怀疑一个密码可能有后门时，也就是说，它已经被故意设计成让知道秘密的人可以在不知道密钥的情况下阅读消息。例如，一个国家间谍机构可能会向其特工提供一个带有后门的密码，以便该机构可以监视他们的消息并检测叛徒。

此时，让我们换个角色。假设你是 Z，被委派设计这个密码的间谍大师。你需要构建一个看起来和表现得像一个强大的区块密码的密码，这样用户就不会起疑。例如，你希望你的密码具有五十五的属性，即仅改变密钥或明文中的一个比特就会导致大约一半的密文比特以随机的模式改变。如果你的区块密码中的替代不都是线性的，那就是一个强大的区块密码的确切迹象。你希望你的假密码模仿这种属性。

这里有一种方法可以在密码中隐藏后门。它基于串行线性性，所以让我们称之为 后门串行 方法来构建密码，并让使用这种方法构建的密码称为 后门串行 密码。Z 可以阅读使用后门串行密码发送的消息，而无需知道密钥，但是对于不知道后门工作原理的任何人来说，它们看起来像是强大的、安全的区块密码。该方法分为三个部分：伪装、隐藏 和 伪装。

伪装

后门串行密码将对十六进制数字进行线性替换。明文块和密钥的每个块都被视为一个 4 位十六进制数字的序列。加密操作是在消息块和密钥的十六进制数字上进行的模 16 加法。假设字节中的两个十六进制数字是 p[1] 和 p[2]，用于对它们进行加密的密钥的十六进制数字是 k[1] 和 k[2]。线性替换将 p[1] 和 p[2] 替换为

系数 a、b、c、d、e、f、g、h、i 和 j 可以是从 0 到 15 的任意整数，而 ag-fb 必须是奇数。如果您的密码有多轮，这 10 个值可以每轮不同。

这种线性替换易于 Emily 发现。特别是，每个十六进制数位的低阶位纯粹是线性的，因此对线性的简单位对位测试将找到它。为了避免检测，我们可以伪装十六进制数位。首先，按某种乱序列出十六进制数位，就像这样：

要将两个伪装的十六进制数位相加，您将它们在乱序列表中的位置相加，以获得总和在乱序列表中的位置。例如，要计算 1+2，您发现数字 1 在位置 9，数字 2 在位置 F，因此您将 9+F 模 16 得到 8。总和在列表中的位置 8。位置 8 中的数字是 D，因此 1+2 = D。

同样地，要将两个伪装的十六进制数位相乘，您将它们在乱序列表中的位置相乘，以获得乘积在乱序列表中的位置。例如，要计算 2×3，您注意到数字 2 在位置 F，数字 3 在位置 2，因此您将 F×2 模 16 得到 E。该产品位于列表中的位置 E。位置 E 中的数字是 7，所以 2×3 = 7。

本质上，伪装是对十六进制数位进行的简单替换。如果替换是非线性的，则没有一个位将在明文和密文之间具有线性关系。这种伪装的线性性质对于 Emily 来说要难得多，但是要真正迷惑 Emily，您可以隐藏伪装的十六进制数位。

隐蔽性

如果十六进制数的位始终是每个字节的块和密钥的位 1-4 和位 5-8，那么 Emily 仍有可能发现线性性。为了使 Emily 的任务真正艰难，您可以隐藏每个字节中的位。而不是使用明文的位（1,2,3,4）和密钥的位（1,2,3,4），并将结果总和放入密文的位（1,2,3,4），您可以按顺序使用明文的位（2,7,4,1）的十六进制数位，以及密钥的位（4,8,3,5），并将结果总和放入密文字节的位（8,6,1,7）。您可以选择任意顺序的 4 位的任何组合，只要每个字节中的 2 个十六进制数位都使用了所有 8 位。

为了明确起见，我们并不是说 Sandra 从每个字节中提取这些位，解密伪装的线性置换，执行算术，然后以不同顺序重新打包结果位。那样太慢了，而且 Emily 会清楚地知道发生了什么。相反，Sandra 在构建替代表时进行了这项工作。为了加密，她只需使用密钥字节选择表中的一行，然后对明文字节执行替代。所有的伪装和隐蔽都内置在替代表中。

伪装

到目前为止，所描述的密码仅仅是一个非常复杂的多表密码。Emily 可以使用第 5.8.3 节的技术解密消息。为了使后门序列密码看起来像一个强大的区块密码，你需要一些伪装来隐藏其核心的多表密码。

一种方法是在每一轮后对块应用位转置。这将使密码看起来像是一个置换-置换网络（第 11.1 节）。为了保留隐藏的线性性，组成每个十六进制数字的 4 位必须最终位于一个字节中。它们不必在该字节中的相同位位置，也不必是连续的，但它们必须在一个字节中。换句话说，输入的每个字节都被分成两个十六进制数字，这些数字以某种转置顺序被馈送到下一轮的两个其他字节中。不幸的是，如果 Emily 能够获得后门序列密码的发布规范，她很可能会发现这种类型的伪装。

让我们看看另一种更难于 Emily 揭示的伪装方式。这种方法借鉴了数据加密标准（DES）的一个想法（第 11.2 节）。每个密码块被分为两半。在每一轮中，首先使用左半部分作为密钥来加密右半部分，然后使用右半部分作为密钥来加密左半部分。我们已经看到了如何将线性性质伪装并隐藏在替代表中，所以让我们利用这一点来制造一个强大的区块密码的幻觉。

每轮密码会包括四个步骤。(1) 左半部分中的每个字节都使用一个字节的密钥进行加密。(2) 右半部分的每个字节都使用左半部分的一个字节作为密钥进行加密。(3) 右半部分中的每个字节都使用一个字节的密钥进行加密。(4) 左半部分的每个字节都使用右半部分的一个字节作为密钥进行加密。

为了使其看起来非常强大，每个块的每个字节应在每一轮中使用不同的密钥字节进行加密，并且每个块的一半的每个字节应在每一轮中使用来自另一半的不同字节进行加密。您可以通过在每一轮中对块中的字节和密钥中的字节进行洗牌来使其更加复杂。您可以使密钥比块更大，以展示更强大的印象。然而，密码仍然是线性的，因为在每一轮的每一步中都保持了线性性。

存储

让我们来看看后门串行密码的机制。在密钥的每个字节中，明文和密文中都有两个十六进制数字。每个数字可以占据字节的任何 4 位，以任何顺序。让我们称这组有序的 4 位为十六进制数字的位配置，并且字节中的 2 个十六进制数字的组合为字节配置。密钥通常不会更改配置，但是明文和密文的字节配置可以在加密的任何阶段更改。

对于每个替换，有 6 种位配置，2 种用于密钥，2 种用于明文，2 种用于密文。对于每个十六进制数字，16 个十六进制值的排列（乱序）也可以不同，因此对于每个替换，每个位配置和排列也有 6 种排列，2 种用于密钥，2 种用于明文，2 种用于密文。这种 6 种配置和 6 种排列的组合确定了替换表。对于每个不同的位配置和排列组合，都需要一个单独的替换表。

每个表格使用 65,536 字节，因此存储可能会成为问题。如果这是一个问题，我建议最多使用 2 字节配置，并且对于每个位配置最多使用 2 种不同的排列，也许可以在每一轮中交替使用。为了进一步减少所需的存储量，您可以考虑每次使用任何给定的位配置时都使用相同的排列。

12.3.5 精简线性

在大多数情况下，您将不会在密码中构建后门，也不会关注串行线性性。让我们把注意力转向第二种线性性，即压缩线性性。在这种线性性形式中，一组位通过将它们进行异或运算压缩为单个位。因此，000、011、101 或 110 将被压缩为 0，而 001、010、100 或 111 将被压缩为 1。明文和/或密钥的任何位组合都可能与每个 S-box 的密文的位组合相关。如果块密码使用异或将 S-box 的输出与块的其余部分结合在一起，则此线性性可以从一轮传递到另一轮，并且原始第一轮明文与最终最后一轮密文之间将存在线性关系。密码的设计者必须避免以这种方式使用异或，或者必须进行彻底的检查，以确保 S-box 不包含任何这样的线性性。

假设 S-box 接受一个 8 位明文并产生一个 8 位密文。从明文中选择一组位有 255 种不同的方式，同样地，从密文中选择一组位也有 255 种方式。（位的顺序并不重要，因为 a⊕b = b⊕a。）这使得有 255² = 65,025 种不同的组配对需要测试。每个测试都是 256 个明文值与 256 个密文值之间的相关性。即使在个人电脑上，这也是很容易实现的。

如果 S-box 接受一个 8 位明文加上一个 8 位密钥并产生一个 8 位密文，那么从明文加密钥中选择一组位有 65,535 种不同的方式，同样地从密文中选择一组位也有 255 种方式。这使得有 65,535×255 = 16,711,425 种不同的配对需要测试。这在个人电脑上需要花费一段时间，因为每个相关性都涉及所有 65,536 个明文和密钥组合。这是需要居中、缩放和求和的超过 10¹²个值。

这是谈论如何高效进行这些测试的理想时间。有一些技巧可以大大加快这个过程。 (1) 为了选择一组位，使用一个从每个字节中选择这些位的掩码。例如，如果你想要第 2、4 和 7 位，使用掩码 01010010，它在位位置 2、4 和 7 上有 1。将这个掩码与每个明文字节进行 AND 运算，以选择所需的位。 (2) 要尝试所有可能的位组合，不要逐个构造掩码，只需将掩码步进到所有值 1 到 255。 (3) 要压缩位，不要每次都使用移位和 XOR。只需执行一次并构建压缩值的表。然后，通过表查找可以将位组合压缩。如果有一组密钥位和明文位，这些位可以通过异或在一起，然后使用表来压缩，这样您只需要一次表查找而不是两次。

12.3.6 混合线性性

为了完整起见，我要提到可以有一种混合形式的线性性，将串行和压缩线性结合起来是可能的。假设你将每个 8 位字节分成四个 2 位组。这些 2 位组可以通过加法模 4 串行线性。你可以通过将它们模 4 相加来压缩两个或多个这些组。同样的操作也可以用于模 8 的 3 位组或模 16 的 4 位组。

让我们坚持使用 2 位组。每个组可以由字节中的任何 2 位组成。例如，一个字节可以分解为 4 个组，位 (6,1)，(4,8)，(2,5) 和 (7,3)。你可以通过将几个 2 位组相加模 4 或取任意的线性组合模 4 来压缩几个 2 位组为一个 2 位组。例如，如果 2 位组是 A、B、C 和 D，你可以将它们组合成一个新的 2 位组 pA+qB+rC+sD+t (mod 4)，其中 p、q、r、s 和 t 是固定整数，范围为 0 到 3，其中至少有一个是奇数。

这些类型的压缩组可能与密文中类似的混合组或正常位组或密文中的压缩位组相关联。如果你想要绝对彻底，那么所有可能的线性组、压缩组和混合组的配对都需要进行相关性测试。

12.3.7 构建 S 盒

有三种构建具有良好非线性特性的 S 盒的方法：时钟方法，SkipMix 和 Meld8 方法。

时钟方法

在一张纸上，将字母按照顺时针均匀间隔地排列在一个大圆圈周围，就像时钟表盘上的数字一样。选择一个起始字母和一个第二个字母，并从第一个字母到第二个字母之间画一条直线。然后选择一个第三个字母，并从第二个字母到第三个字母之间画一条直线，依此类推。将每条线的 跨度 定义为从每个字母顺时针移动到下一个字母的字母位置数。例如，使用 26 个字母的字母表，从 C 到 D 的跨度是 1，从 D 到 C 的跨度是 25。为了使替换尽可能非线性，使每个跨度长度都不同。

下面是具体操作。为字母表中的每个字母制作一个列表，其中包含可能跟随它的所有字母。当你开始时，每个字母的列表都会包含其他每个字母，所以你会得到 26 个含有 25 个字母的列表。每次选择一个字母并将其添加到混合字母表中时，从所有列表中删除该字母。如果从前一个字母到该字母的跨度是 s，则还要从所有列表中删除任何跨度为 s 的其他字母。例如，假设你已经将 P 和 R 添加到字母表中。从 P 到 R 的跨度是 2 个位置，PQR。因此，在 A 列表中，你会删除 C，在 B 列表中，你会删除 D，在 C 列表中，你会删除 E，依此类推。

最终，一些列表会变为空。如果只有一个字母的列表为空，那么该字母将成为混合字母表中的最后一个字母。如果有两个空列表，那么你已经陷入了僵局。重新开始，或者回溯并再试一次。每次选择要添加到字母表中的下一个字母时，选择一个列表较短的字母，但不要选择一个空列表的字母，除非那是剩下的最后一个字母。

历史背景

这种启发式方法称为 Warnsdorff 规则，以 H. C. von Warnsdorff 的名字命名，他在 1823 年用于在棋盘上构建骑士之旅。1965 年左右，加州大学圣克鲁斯分校的 Ira Pohl 提出了一个向前看 2 步的改进版本。

这是一个通过时钟方法构建的字母表示例：

有 5 种不同的编号需要测试，以检查该字母表的线性性：N1 编号，N2 编号的第一和第二位数字，以及 N3 编号的第一和第二位数字。每个都必须与标准拉丁字母表的相同 5 个编号相关联，总共有 25 个相关性。你希望所有相关性都在-.5 和+.5 之间。最好的情况是它们都在-.333 和+.333 之间。

这些测试的结果如下，25 个相关系数。

正如你所看到的，所有相关性都在-.226 和+.288 之间，其中有 6 个落在-.1 和+.1 之间，因此时钟方法是构建非线性替换的绝佳方法。

并不保证每次都能获得如此好的结果。你仍然需要测试线性性。

SkipMix

在本节（12.3）的前面，我提到可以使用 SkipMix 算法（第 5.2 节）与伪随机数生成器构建字母表。一般来说，随机选择字母表不会导致良好的非线性特性，所以让我更详细地描述如何最好地使用 SkipMix。这次我将以 256 个字符的字母表为例进行说明。

一如既往，你首先列出 256 个可用字符。在 1 到 256 的范围内生成一个随机数以选择第一个字符。假设那是字母表中的第 54 位。取出该字符，然后从列表中删除它。现在剩下 255 个字符。在 1 到 255 的范围内生成一个随机数。假设该数字是 231。下一个位置将是 54+231 = 285。由于这大于 255，你减去 255 得到 30。从位置 30 取下一个字符，并从列表中删除它。现在你已经取了 2 个字符，剩下 254 个字符，所以你在 1 到 254 的范围内生成一个随机数。依此类推。

生成的字母表具有良好的非线性特性，因为您每次生成不同范围的随机数。这与时钟方法中使所有跨度不同的情况类似。这是通过 SkipMix 的这个版本生成的一个 26 个字母的字母表示例。

这可以像测试时钟字母一样进行测试。结果如下：

这些结果很好。所有相关性都介于 -.127 和 +.344 之间，其中 5 个介于 -.1 和 +.1 之间，但是它们不如时钟方法的结果好。

Meld8 方法

这种方法基本上是一种特殊用途的伪随机数生成器。我将假设您正在使用的计算机语言能够操作 64 位整数。根据大整数的表示方式，您可以处理 2⁶² 或 2⁶³ 的整数。为了谨慎起见，我将假设 2⁶²。第一步是选择两个数字，一个乘数 m，位于 24 到 26 位之间，和一个模数 N，位于 35 到 37 位之间。模数必须是素数。如果 m 是 N 的原根，则最好，但由于我尚未解释那是什么，所以只需使 m 和 N 都是素数。

通过将它们相乘来测试您选择的 m 和 N。如果结果大于 2⁶²，约为 4.611×10¹⁸，则使 m 或 N 中的一个较小。

要生成随机数，从 2 到 N-1 之间选择任何整数 s 作为种子。将种子乘以 m，并对 N 取模以获得第一个伪随机数。将第一个随机数乘以 m 并对 N 取模以获得第二个随机数，依此类推。这给了你一个范围为 1 到 N-1 的随机数序列。您将使用这些随机数来生成字母。

假设 N 有 36 位。从高位开始，将 N 的位编号从 1 到 36。取每个随机数的前 8 位，位于 1 到 8 位。从高位开始删除它们，并将它们与下一个 8 位，即 9 到 16 位，进行异或。这就是 Meld8 操作。它的目的是使字符序列非线性。以下是一个示例：

下一步是使用 28 位随机数生成一个字符。这取决于您是要构建一个 26 个字符还是一个 256 个字符的字母表。对于 26 个字符的字母表，将此数字乘以 26 并除以 2²⁸（或向右移动 28 位）以获得下一个字符。对于 256 个字符的字母表，只需除以 2²⁰，或向右移动 20 位以获得下一个字符。

从空字母表开始，每次添加一个字符。如果这是一个新字符，则将其追加到字母表中。如果这是一个重复字符，则将其丢弃。由于您没有连续的随机数，因此这也适用于使字母表非线性。以下是使用模数 N = 90392754973、乘数 m = 23165801 和种子 s = 217934 生成的此类字母表的示例：

结果相关系数为

相关性范围从-.170 到+.267，其中有 11 个落在-.1 和+.1 之间。这是三个示例中最好的，然而，基于每种技术的单个示例得出 Meld8 是最佳方法的结论是愚蠢的。始终进行测试。

12.3.8 带有密钥的 S 盒

在第 12.3.7 节中，我们处理了没有密钥的 S 盒。它们执行简单的替换。当使用密钥时，S 盒执行一般的多表替换（第 5.8.3 节）。S 盒可以被视为一个表，其中每一行都是一个混合字母表。可以通过使用时钟方法、SkipMix 或 Meld8 构建每个混合字母表来生成 S 盒，或者通过任何组合方法。

如果使用时钟方法或 SkipMix，请每次使用不同的随机种子。如果使用 Meld8，则可以每次使用相同的模数，但使用不同的种子和不同的乘数。一如既往，测试，测试，测试。你的目标是避免密钥和明文与密文的组合之间存在任何线性关系。如果结果不佳，即许多相关系数在-.35 到+.35 范围之外，也许只需替换一个行或交换两个行的表就能解决问题。

12.4 扩散

香农的第二个特性是扩散。这个想法是密文的每一位或每一字节都应该依赖于明文和密钥的每一位或每一字节。

为了说明这一点，让我们回到第 9.6 节中描述的 Delastelle 的 bifid 密码。为了提醒你，bifid 是基于 Polybius 方阵的分组密码。如果块大小为 S，则消息的每个字母将被两个基于 5 的数字替换，并且这些数字被垂直写入一个 2×S 网格并水平读出。然后这些数字对再使用相同或不同的 Polybius 方阵转换回字母。

让块大小为 7，并将明文块中的字母称为 A、B、C、D、E、F、G。让表示这些字母的数字为 aa,bb,cc,dd,ee,ff,gg。我没有写下标，因为这里不重要哪个数字先出现，哪个数字后出现。那么块将是

当字母水平读出时，你会得到 ab,cd,ef,ga,bc,de,fg。请注意，密文的每个字母都取决于明文的两个字母。第一个密文字母取决于 A 和 B，第二个字母取决于 C 和 D，依此类推。

在这一点上，我需要引入一种特殊的符号来显示每个密文字母依赖于哪些明文字母。如果一个密文字母依赖于明文字母 P、Q 和 R，则它被指定为 pqr。使用这种符号，如果你再次加密字母 A、B、C、D、E、F、G，块会像这样：

将这些字母水平读出，你会得到 abcd，efga，bcde，fgab，cdef，gabc，defg。由于数字的顺序无关紧要，这也可以表示为 abcd，aefg，bcde，abfg，cdef，abcg，defg。经过两次加密后，每个密文字母都依赖于四个明文字母。

如果您使用双密码加密这个区块第三次，那么每个密文字母将取决于所有 7 个明文字符。对于区块大小为 7 的双密码，需要三轮加密才能实现完全扩散。如果区块大小为 9、11、13 或 15，那么需要四轮加密。（请回忆一下，双密码中的区块大小应始终为奇数。）

一般来说，要测试扩散，您首先使每个明文字符或位仅依赖于自身。如果密码操作的是整个字节或字符，则根据字节跟踪扩散。如果它操作十六进制数字、其他基数的数字或者单个位，则根据这些单元跟踪扩散。对于双密码，单元是 Polybius 方格坐标，或者是基数为 5 的数字。

为了追踪扩散，您需要一种方式来表示明文单元和密钥单元在区块密码的轮次中随着流动的方式。当只有少数明文单元时，就像双密码示例一样，仅列出它们就能很好地工作。当明文、密钥和密文单元的数量较大时，可能需要更紧凑的表示。一个好的策略是为每个密文单元创建一个二进制向量。让我们称之为依赖向量。依赖向量的每个元素将对应于一个输入，即明文或密钥单元。如果密文单元取决于该输入单元，则该依赖元素的值为 1，否则为 0。

当两个或多个输入单元组合成一个输出单元时，它们的依赖向量将被 OR 运算在一起，形成输出单元的依赖向量。为了说明这是如何工作的，让我们再次使用这种符号通过双密码示例。最初，每个字符仅依赖于自身。这由向量表示

在第一次应用双密码后，每个结果字母都依赖于两个明文字母。第一轮输出字节依赖于第一轮输入字节的前两个字节，因此你将它们的依赖向量进行 OR 运算得到 1100000。第二个输出字母依赖于第三和第四个明文字母，因此你将它们的依赖向量进行 OR 运算得到 0011000，依此类推。第一轮输出由向量表示

在第二轮的双重转置之后，第一个输出字母取决于第一轮的第一个和第二个输出，所以你将它们的依赖向量进行 OR 运算 1100000∨0011000 得到 1111000。第二个输出字母取决于第一轮的第三个和第四个输出，所以你将它们的依赖向量进行 OR 运算 0000110∨1000001 得到 1000111，依此类推。经过两轮的双重转置后，每个字母都取决于四个明文字母，表示为

在第三轮的双重转置之后，每个输出字母都取决于第一轮明文的所有 7 个字母，例如，1111000∨1000111 就是 1111111。第三轮的输出表示为

每当遇到一个 S 盒时，输出单元的依赖向量是通过对贡献到该输出的每个输入的向量进行 OR 运算形成的。让我们看看在块密码中可能发生的其他情况。

如果两个单元进行异或运算，输出单元的依赖向量是通过对每个输入的向量进行 OR 运算形成的。当使用任何组合函数（如sxor或madd）将多个单元组合在一起时，也是如此。

当块的单元使用密钥进行转置时，每个输出单元都依赖于该密钥的所有单元，因此密钥的向量与每个输出单元的向量进行 OR 运算。

假设一个 S 盒是通过使用密钥混合其字母表而创建的。如果 S 盒是固定的或静态的，比如通过嵌入硬件来实现，那么混合密钥将不再参与其中。如果 S 盒是可变的，也许每次加密都使用不同的密钥进行混合，那么该 S 盒的输出单元将依赖于该密钥的所有单元。密钥的向量与每个输出单元的向量进行 OR 运算。

可以将扩散表示为一个单一数字。从所有输出单元的依赖向量构建一个矩阵。矩阵中的每一行代表块密码最终轮的一个输出单元。矩阵中的每一列代表一个输入单元，可以是密钥或明文。扩散的度量，或扩散指数，是矩阵中这些元素中为 1 的部分。如果矩阵中的元素都是 1，那么就有完全扩散，扩散指数为 1。如果 S 盒是非线性的且密钥很长，这表明块密码很强大。

扩散并非全部。有些有效的密码设计中，扩散指数可能小于 1，但密码仍然很强大。一个例子是每轮都有单独密钥的块密码。早期轮次的密钥可能实现完全扩散，但晚期轮次，尤其是最后一轮的密钥可能不会。然而，如果完全扩散的密钥包含您所需的位数，则该密码很可能是安全的，而部分扩散的密钥只是一种保险。

这里有一个示例，可能有助于说明即使扩散不完全，密码也可以很强大。考虑一个具有 12 轮的密码，每轮具有独立的 24 位密钥。在这个密码中，需要 6 轮才能实现完全扩散，因此经过 6 轮后，明文和第一轮密钥完全扩散。经过 7 轮后，明文和第一轮和第二轮密钥完全扩散。依此类推。经过 12 轮后，明文和前 7 轮的密钥完全扩散。使用 24 位轮密钥，这是 168 位完全扩散的密钥。如果您的目标强度是 128 位密钥位，那么您已经超过了目标。第 8 至 12 轮的部分扩散密钥是额外的奖励。

密钥密码学（二）(3)https://developer.aliyun.com/article/1508579