密钥密码学（二）(3)

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

12.5 饱和

混淆和扩散是安全框架的两大支柱。为了确保分组密码建立在坚实的基础上，我建议添加第三支柱，我称之为饱和。扩散仅表示给定输出单元是否依赖于给定输入单元。饱和度衡量给定输出单元依赖于给定输入单元的程度。我展示了如何计算类似于前一节扩散指数的饱和指数。饱和实质上是扩散的更精细版本。通过扩散，依赖性只能具有 0 或 1 的值，但通过饱和，依赖性可以具有任何非负值。

这里是饱和的简要解释。假设分组密码 X 由几轮替换组成。在每一轮中，消息的每个字节都与密钥的一个字节进行异或运算，然后对结果进行简单的替换。假设每一轮中使用不同的密钥字节，以便每个密钥字节每次用于每个分组字节。密码 X 的饱和度会很低，因为每个密文字节仅依赖于每个密钥字节一次。要获得更高的饱和度，每个输出字节需要多次依赖于每个输入字节。

另一个示例可能有助于更清晰地说明。想象一个在 48 位块上运行的密码，视为六个 8 位字节。这个密码的每一轮包括两个步骤：（1）块向左循环移动一个位位置，因此最左边的位移动到最右边的位置，然后（2）对每个 8 字节执行简单的替换 S。第一轮后，第一个输出字节C1依赖于第一个明文字节的最后 7 位和第二个明文字节的第一个位，如下所示：

密文字符C1依赖于明文字节P1的 7 位和明文字节P2的 1 位。可以说C1对P1依赖 7/8，对P2依赖 1/8。

让我们看看第二轮。将第二轮输出称为D1 … D6。

密文字符 D1 对 C1 依赖程度为 7/8，对 C2 依赖程度为 1/8。在这里，C1 对 P1 依赖程度为 7/8，对 P2 依赖程度为 1/8，而 C2 对 P2 依赖程度为 7/8，对 P3 依赖程度为 1/8。P1 对 D1 的唯一贡献来自 C1。因为 D1 对 C1 的依赖程度为 7/8，C1 对 P1 的依赖程度为 7/8，因此可以合理地说 D1 对 P1 的依赖程度为 49/64。出于同样的原因，D1 对 P3 的依赖程度为 1/64。让我们称这些数字为 饱和系数，将这个计算称为 S1 计算，当存在单一依赖关系时。

图表可能会使配置更清晰。

P2 呢？D1 通过 C1 和 C2 从 P2 获取贡献。或许认为 D1 对 C1 的依赖程度为 7/8，对 P2 的依赖程度为 1/8，对 C2 的依赖程度为 1/8，而 C2 对 P2 的依赖程度为 7/8，因此 D1 对 P2 的依赖程度为 (7/8)(1/8)+(1/8)(7/8) = 14/64。这是一个合理的计算，它导致了扩散的更复杂版本。然而，使用这个计算，任何给定单位的总贡献总是 1。总数永远不会增长。如果这个计算重复多次，所有这些扩散数字将收敛到 1/48。这并不是饱和概念试图捕捉的内容。只要一个单位从多个不同的来源接收贡献，饱和度就应该增加。

当一个单位获得多个贡献时，使用不同的计算方法来确定饱和系数。假设两个来源的饱和系数分别为 a 和 b，其中 a ≥ b。那么合并后的饱和系数为 a+b/2。如果有三个贡献的饱和系数分别为 a、b 和 c，其中 a ≥ b ≥ c，那么合并后的饱和系数为 a+b/2+c/4。在每种情况下，组件饱和系数按降序排列，a ≥ b ≥ c ≥ d ≥ e… 。总之，当多个饱和系数被合并时，结果如下：

让我们称这个计算为 S2 计算，当存在多个依赖关系时使用 S2 计算。对于单一来源使用 S1 计算。

S2 计算可能看起来是临时的，甚至是古怪的，但它具有饱和计算所需的恰到好处的属性。首先，当一个单位依赖于多个前导时，它总是会增加。这是因为 a+b/2 总是大于 a。其次，它的增长速度不会太快。最多，饱和系数可以从一个回合翻倍到下一个回合。这是因为 a+a/2+a/4+…+a/2^n < 2a 对于任何 n 都成立。例如，1+1/2+1/4+1/8 = 15/8 = 1.875。

在当前情况下，D1依赖于P2，贡献系数分别为 7/8 和 1/8，因此组合系数为 7/8+(1/8)/2 = 15/16。 输出单元的饱和系数可以组成一个向量，就像扩散数一样。 因此，D1的饱和向量为(49/64, 15/16, 1/64, 0, 0, 0)。 然后，这些向量可以组成饱和矩阵。 饱和指数是饱和矩阵中最小的系数。

让我们看一个更现实的密码，这是文献中提出的一种密码，可能已经在实践中使用过。 我将其称为SFlip，简称Substitute and Flip。 它是第 11.7.5 节中多项式三次翻转的近亲。 如果您不记得矩阵翻转是什么意思，请参阅第 11.7 节。 SFlip 密码适用于一个 8 字节的块，并由几个轮次加上一个完成步骤组成。 每一轮都有两个步骤。（1）将简单的替换应用于八个 8 位字节。（2）8×8 比特位矩阵翻转。 完成步骤是再次为每个 8 位字节进行替换。

8×8 比特位矩阵需要一个 64×64 的依赖矩阵。 这个矩阵太大了，无法清晰显示，因此我将以微型形式显示密码。 让我们使用一个 3×3 的比特位矩阵，其具有 9×9 的依赖矩阵。 这个密码将被分析两次，一次使用扩散，一次使用饱和。 先进行扩散。 让我们从在文本块和依赖矩阵中标记比特位开始，就像这样：

在第一轮之前，每个比特位只依赖于自己，因此依赖矩阵看起来像（1）。 在第一轮替换之后，每个比特位依赖于其字符中的所有 3 位，因此依赖矩阵看起来像（2）。 在第一轮翻转之后，依赖矩阵看起来像（3）。 在第二轮替换之后，依赖矩阵看起来像（4）。

换句话说，此时密文的每一位都取决于明文的每一位。 这在第二轮翻转之后以及最后的替换之后仍然成立。 因此，如果我们仅依赖依赖计算，我们会得出结论，此密码在两轮后将是安全的。 这是不正确的。 阿迪·沙米尔已经证明两轮是不够的。

现在让我们使用饱和指数来分析 SFlip 密码。 在第一轮替换之后，密文的每个比特位都依赖于其对应的 3 个明文比特位中的 1/3。 饱和矩阵将看起来像（5）。 在第一轮翻转之后，饱和矩阵将看起来像（6）。

第二轮替换使得输出的每一位取决于第一轮明文的所有 9 位。饱和系数为 1/3+(1/3)/2+(1/3)/4 = 1/3+1/6+1/12 = 7/12，约为 0.583。饱和矩阵中的每个元素都将具有这个值，因此饱和指数将为 7/12。饱和指数的目标值为 1，尽管如果您想要更大的确定性，也可以将其设置得更高。以下是几轮后饱和指数的情况。

所以对于 3×3 密码，3 轮就足够了，但对于 8×8 密码，需要 5 轮。

现在让我们转向其他一些情况，其中输出单元取决于一个或多个输入单元。

当一个 S 盒同时具有明文和密钥输入时，例如 p 个明文单元和 k 个密钥单元，每个输出单元的依赖性将为 1/(p+k)。例如，如果输入为 6 个密钥位和 4 个明文位，则每个输出位的依赖性将为 1/10。如果 S 盒的输入本身依赖于先前的输入，则应根据需要使用 S1 或 S2 计算来计算饱和指数。

同样，如果使用异或或其他组合函数将两个或更多单元组合在一起，则依赖性为 n 个总输入的 1/n。计算饱和指数的方法与具有相同输入的 S 盒相同。

当使用 k 位密钥进行置换时，置换的每个输出单元对每个密钥位的依赖性为 1/k，并对明文输入的依赖性为 1。假设明文字符 p 通过置换从位置 a 移动到位置 b。置换后，p 的饱和向量将与置换前的饱和向量相同，除了那些对应于置换密钥位的列。在这些列中，饱和系数将由 S1 或 S2 计算确定。

这里有一个例子。假设 t 是置换密钥的位之一。如果 p 在置换之前对 t 没有依赖性，即其饱和向量的第 t 列为 0，则在置换之后，第 t 列的值将为 1/k。另一方面，如果 p 已经依赖于密钥位 t，则饱和系数将由 S2 计算确定。如果第 t 列中的系数为 x，则在置换之后，第 t 列中的饱和系数将为 x+1/2k（如果 x ≥ 1/k），或者为 1/k+x/2（如果 x < 1/k）。

当使用 k 位密钥来混合字母表或替代步骤的表时，混合的字母表或表对该密钥的每一位具有 1/k 的依赖性。每次使用该字母表替换一个字符时，输出字符对密钥的每一位都会增加 1/k 的依赖性。这与输入字符的依赖性（和替换密钥，如果有的话）结合使用 S1 或 S2 计算来获得输出字符的饱和系数。

摘要

如果一个块密码遵循所有这些规则，实际上是无法破解的：

1. 它具有足够大的块大小。当前标准为 16 个字符或 128 位。
   
2. 它具有足够大的密钥。当前标准为 128 到 256 位。密钥必须至少与块大小相同，最好更大。
   
3. 要么使用强非线性的固定 S 盒，要么使用使用大密钥混合良好的可变替代表。
   
4. 饱和指数至少为 1。
   

一如既往，要保守。建立一个安全的误差边界。使密钥更长，使用比所需更多的轮数，因为计算机变得更快，新攻击不断被发现。特别是，您可以将饱和指数的目标设定得比 1 更高，也许是 2、3 甚至 5。

第十三章：流密码

本章涵盖

• 伪随机数生成器
  
• 用于将随机数与消息组合的函数
  
• 生成真随机数
  
• 散列函数
  

流密码与分组密码相反。流密码中的字符在遇到时被加密，通常一次一个。基本概念是将一系列消息字符与一系列密钥字符结合起来，以产生一系列密文字符。这种范式非常适合连续操作，其中消息在一端持续加密和传输，另一端持续接收和解密，没有暂停，或者只有短暂的暂停来更换密钥。

我们已经看到了一些流密码。第 5.9 节中的自动密钥和流动密钥密码，第 5.10 节中的转子机器，第 10.4 节中的哈夫曼替换，以及第 10.7 节中基于文本压缩的密码都是流密码的示例。

13.1 组合函数

最常见的流密码类型使用一个密钥单元加密一个明文单元。这些单元通常是字母或字节，但十六进制数字甚至比特也可以使用。密钥单元与明文单元结合使用基本上与第 11.8 节中的涟漪密码使用的组合函数相同，但使用密钥单元代替前一个单元。以下是类似的方法，其中 x[n] 是消息的第 n 个单元，k[n] 是密钥的第 n 个单元，A 和 B 是简单的替换，P 是通用多表替换。替换 A、B 和 P 应该使用密钥混合，而不是固定或内置的。

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

流密码也可以使用一个或多个先前的字符来加密当前字符。有许多组合方式。一个例子是 P(k[n]⊕x[n-i], x[n])，其中 i 是一个小整数。这种密码需要一个初始化向量来加密前 i 个字符。流密码也可以通过在几个组合函数之间切换来加强，例如周期性地在sadd的 3 种形式之间或madd之间进行切换，或者周期性地变化madd中的乘数 p 和 q。

13.2 随机数

前面表格中列出的流密码中使用的长密钥可以来自几个来源：

• 它们可能是一个数字列表，根据需要重复多次。这是从 16 世纪到 19 世纪的标准方法。
  
• 它们可能是通过数学过程生成的。这些数字称为pseudorandom，因为它们最终会重复，而不是真正的随机数，后者永远不会重复。生成这些数字的过程称为pseudorandom number generator（PRNG）。
  
• 它们可能是真正的随机数，可能是由一些物理过程生成的，例如来自爆炸星的伽马射线。这些过程通常对于密码学的需要来说太慢了，因此这些随机数通常会随着时间的推移而收集，并存储在计算机中以供以后使用。也就是说，它们可以连续收集，并且只在您需要发送消息时使用。
  

关于密码学的书籍和文章经常声称，你需要真正的随机数才能获得安全的密码。他们指出，已经数学证明了使用真正随机密钥的一次性密码本是不可破解的。这当然是正确的，前提是对于每个明文单元 p 和每个密文单元 c，都存在一个密钥单元 k 将 p 转换为 c，即 S(k, p) = c。真正的随机密钥足以使一次性密码本无法破解。然而，正如每个学过逻辑的人都知道的，条件可以是充分的，但不是必要的，反之亦然。

例如，要使一个整数成为质数，必须大于 1。这是必要的，但不充分，因为 4 是一个大于 1 的整数，但不是质数。要使一个整数成为合数，它必须是一个大于 1 的平方数。这是充分的，但不必要，因为 6 是合数，但不是平方数。

要求一次性密码本的密钥必须是真随机是过度的。为了使一次性密码本无法破解，密钥必须是不可预测的，也称为密码学安全的。使用真随机密钥，无论 Emily 知道多少个密钥单位，她都无法确定其他单位。使用不可预测的密钥，Emily 只需无法计算地确定其他单位。具体而言，Emily 需要做的工作量来确定另一个密钥单位必须大于 2^k，其中 k 是你选择的密钥大小（以比特为单位）。当密钥流仅为伪随机时，您无法再证明密码本是不可破解的，但这在实践中没有实际意义。

本章后面我将描述几种使伪随机数生成器具有密码学安全性的方案，并指出一个看起来安全但实际上是不安全的方案，即第 13.13 节中描述的 CG5。

之前列出的所有流密码都可以利用伪随机数生成器产生密钥流，因此让我们来看一些 PRNG 的变体，首先从上世纪 50 年代的一些经典方法开始。这些生成器使用一个小的初始值，称为种子或初始状态，以及一些简单的数学函数，从当前状态生成下一个状态，称为状态向量。常见的生成函数包括加法、乘法和异或。由于它们的速度快且易于实现，这些生成器今天仍然被广泛使用。

每个生成器都会产生一个整数序列，在依赖于种子的周期之后最终会重复。可能会有一个永远不会重复种子的重复数字序列，例如 1,2,3,4,5,4,5,4,5,4,5, … ，但本书中的生成器都没有这种行为。周期受状态向量大小的限制。例如，一个状态向量为三个 31 位整数的生成器的周期不能超过 2⁹³。

13.3 乘法同余生成器

一个乘法同余伪随机数生成器使用两个参数，一个是乘数 m，一个是模数 p。从种子 s 开始，伪随机数序列 x[n] 通过递推生成。

换句话说，要获取下一个伪随机数，你需要将上一个数乘以 m，然后取模 p 的余数。种子可以是任何整数 1,2,3, … ,p-1。模数 p 几乎总是选择为质数，因为质数产生最长的周期。选择 p 通常取决于您使用的计算机中寄存器的大小。对于 32 位寄存器，常见选择是素数 2³¹-1，即 2,147,483,647，这是由伯克利数论学家 Derrick H. Lehmer（不要与他的父亲伯克利数论学家 Derrick N. Lehmer 混淆）在 1949 年发布的这一类中的第一个 PRNG。

乘数 m 必须谨慎选择。乘法同余生成器的周期可以是任何均匀地整除 p-1 的整数。由于 p 是一个素数，且可能远大于 2，p-1 将是偶数，因此非常糟糕的选择 m，比如 p-1，可能会得到一个周期为 2 的结果。具有最长周期的乘数，即 p-1，称为 p 的 原根。这意味着 m、m²、m³、…、m^(p-1) 在模 p 下有不同的余数。对于乘法同余生成器，最好使 m 成为原根，以获得最长可能的周期。

幸运的是，这很容易做到。在范围为 2 到 p-2 的数中，平均约有不到 3/8 的数字是 p 的原根。这个确切的比率被称为 阿丁常数，以奥地利数学家埃米尔·阿丁（Emil Artin）的名字命名，他于 1937 年逃离纳粹德国，并在普林斯顿完成了他的职业生涯。它的值约为 .373956。如果您可以因式分解 p-1，那么很容易测试给定的乘数 m 是否是 p 的原根。我们知道 m 的周期必须整除 p-1，因此首先将 p-1 进行因式分解。假设 p-1 的不同素因子是 a、b、c 和 d。然后，您只需要测试 m^((p-1)/a) (mod p)，m^((p-1)/b) (mod p)，m^((p-1)/c) (mod p) 和 m^((p-1)/d) (mod p)。如果这些值中没有一个是 1，则 m 是一个原根。例如，如果 p = 13，则 p-1 的不同素因子为 2 和 3，因此您只需要测试指数 12/2 和 12/3，即 m⁶ 和 m⁴。例如，5 不是 13 的原根，因为 5⁴ = 625 ≡ 1 mod 13。

有有效的方法来通过连续的平方来计算 m^x。例如，要计算 m²¹，您可以连续计算 m²、m⁴、m⁸、m¹⁶、m²⁰、m²¹，只需进行 6 次乘法运算。您可以通过使用这些乘积来计算下一个幂值来获得进一步的效率。例如，如果要测试的下一个值是 m³⁷，您可以只使用 3 次乘法运算计算出 m³²、m³⁶、m³⁷。在每次乘法运算后计算模 p 的余数要比计算庞大的数 m²¹ 并在最后取余更有效。有更复杂的方案可以使用稍少的乘法运算，可能减少 10% 到 15%，但如果您只做几次，额外的努力是不值得的。

如果您使用的是乘法同余伪随机数生成器（PRNG），则重要的是要知道每个数字的大小显示出随机特性。要将生成器的输出 R 转换为范围在 0 到 N-1 的整数，正确的计算方式是⌊RN/p⌋，其中⌊x⌋表示“x 的地板”，意思是将 x 向下舍入到下一个较低的整数。例如，⌊27⌋是 27，⌊27.999⌋是 27。表达式⌊RN/p⌋略微偏向于较小的值，即，它会比较频繁地产生较小的数字。但是，当 p 远远大于 N，比如 p > 1000N 时，这对于加密目的并不重要。

历史旁注

顺便说一句，符号⌊x⌋和相应的⌈x⌉（读作“x 的 ceil”，意思是将 x 四舍五入到下一个更高的整数，因此⌈27.001⌉为 28）都是由肯尼斯·艾弗森（Kenneth Iverson）在 1962 年发明的，他是 APL 编程语言的创造者。APL 是第一种交互式编程语言。今天的计算机用户认为交互性理所当然。您按下一个键或点击鼠标，计算机就会执行某些操作。他们没有意识到这个概念必须被发明。在那之前，计算的标准模型是您通过卡片阅读器运行一叠卡片，计算机打印结果，几个小时后您得到一叠纸。

警告：不要使用(R mod N)作为您的随机数。R mod N 可能严重偏向低值。例如，如果模数 p = 11，N = 7，那么(R mod 7)的 11 个可能值为 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3，因此 0, 1, 2 和 3 的生成频率是 4, 5 或 6 的两倍。

只要 m > √p，乘法同余生成器将具有良好的随机特性。最好是乘法逆 m’ > √p。这意味着 m 的位数至少需要是 p 位数的一半。您希望 p 尽可能大，以便生成器具有长周期，同时希望 m 足够大，以便生成器是随机的。您可以走多远？m 和 p 的大小受计算机寄存器的大小限制。如果超过一个寄存器，速度将受到惩罚。

每个伪随机数 x[n]是通过将前一个数字 x[n-1]乘以 m 生成的。数字 x[n-1]可以有与 p 相同数量的位，因此如果 p 有 b 位，则 x[n-1]也可以有 b 位。由于 m 必须至少有 b/2 位，因此乘积 mx[n-1]可以有 3b/2 位。如果寄存器大小为 63 位，则 b 最多可以是 63 的 2/3，即 42，这意味着 m 最多可以有 21 位。最好使 m 大于√p。一个合理的折衷方案是 m 为 25 位，p 为 38 位。这样可以让周期长达 2³⁸。

使生成器不可预测所需的属性是生成的单位具有相等或均匀的频率，成对的单位具有相等的频率，三元组和四元组具有相等的频率，依此类推。实际上，您不需要超过八元组或最多十元组的字节。如果您想要绝对确定，可以将所需的密钥大小除以生成的单位的大小。例如，如果您的密钥大小为 128 位，PRNG 生成 4 位十六进制数字，则您可能需要使 n 元组在所有 n 值上的频率相等，直到 32。 （那些这样做的人显然是强迫症患者，应该寻求治疗。）即使对于 4 位随机数，也没有必要也没有用处超过 16 元组或最多 20 元组（sexdecuples 或 vigintuples），即 64 或 80 位。

Emily 需要超过 2⁶⁴或 2⁸⁰字节的已知明文才能利用这些不均匀的频率。即使 Sandra 从不更改她的密钥，Emily 也不可能积累那么多的材料。从长远来看，假设有一颗卫星以每秒 1 MB 的速率发送遥测数据。进一步假设，它同时使用两个不同的密钥流发送这些数据，而 Emily 拥有其中一个密钥。即使她以每秒 1 MB 的速度获取明文/密文对，她仍需要大约 585,000 年才能收集到 2⁶⁴字节。即使有 1000 颗卫星都使用相同的密钥，也需要 585 年。

如果对于每个 n 的所有值，n 元组的频率都相等，则您的生成器是真随机的。您已经找到了一种生成真随机数的数学算法。恭喜。去领取您的菲尔兹奖。

为了使元组频率在 n 元组中相等，通常需要生成器的种子本身至少是 n 元组。对于乘法同余生成器来说，单个单位和对频率是均匀的，但三元组频率从不均匀，而对于 n > 3 的 n 元组频率则远非均匀；其中大多数频率为 0。

如果你有几个已知明文字符，并且密码使得很容易从明文/密文对确定随机输出，即，如果组合函数是xor、add或madd，那么破解乘法同余密码就很简单。例如，如果密码通过对密钥字节和明文字节进行异或运算来获取密文字节，那么 Emily 所需要做的就是将明文字节与密文字节进行异或运算以获取密钥字节。

如果生成器有一个 31 位或 32 位的模，即使在个人电脑上，Emily 也可以尝试所有 2³¹或 2³²种种子的值。已知的明文字符仅用于验证。如果模数更大，例如 48 位或 64 位，则前 2 个或 4 个已知的明文字符用于限制搜索范围。第一个随机输出将当前生成器状态限制在一个窄范围内，即总范围的 1/256。第二个已知的明文字符给出第二个输出，将状态限制在该范围的 1/256，依此类推。

因此，单个乘法同余生成器在密码学上并不安全。可以使用更大的模数，使用卡拉兹巴或图姆-库克等大整数乘法技术，但这会牺牲这一类生成器的高速度。有更快的方法来生成密码安全的生成器，因此本书不会涉及大整数乘法方法。

13.4 线性同余生成器

线性同余生成器是对乘法同余生成器的扩展。它们在递推公式中添加一个线性常数项 c。从种子 s 开始，通过递推生成伪随机数序列 x[n] 的是公式是

换句话说，要获得下一个伪随机数，你将前一个数字乘以 m，加上 c，然后取该和对 P 的模。种子可以是任何整数 1、2、3、…、P-1。当满足以下三个条件时，生成器将具有最长可能的周期：

1. c 与 P 互质，
   
2. 对于每个是 P 因子的素数 p，m 的形式为 pk+1，且
   
3. 如果 P 是 4 的倍数，则 m 的形式为 4k+1，
   

其中 k 可以是任意整数。这些被称为 T. E. Hull 和 A. R. Dobell 在 1962 年发表的Hull-Dobell 条件。

例如，假设 P = 30，即 2×3×5。那么 m-1 必须是 2、3 和 5 的倍数。换句话说，m 必须是 1。所以，如果 s = 1，c = 7，伪随机序列将是 1、8、15、22、29、…。这是一个等差数列，一点也不随机。因此，通常选择模数 P 为质数的幂，最常见的是 2。找到产生良好随机特性的 m、c 和 P 的值是困难的。

然而，线性同余生成器有一个很好的用途。如果你想产生一个具有极长周期的生成器，你可以将两个或多个模数为不同质数幂的线性同余生成器的输出相加，以获得具有良好随机特性和周期等于这些模数乘积的生成器。例如，假设你添加了以下三个 PRNG 的输出。我选择了 3 个模数尽可能大，但仍适合于 32 位机器字，我选择了乘数和常数以满足 Hull-Dobell 条件。除此之外，我任意选择了它们。

让 w[n] = (x[n]+y[n]+z[n]) mod 2³¹。通过将其右移 23 位来选择 w[n] 的高阶字节，即 v[n] = w[n]/2²³。只要 (1) 三个乘数中至少有一个，以及它的乘法逆元，大于其对应模数的平方根，且 (2) 其余两个乘数都不是 1 或 P-1，那么 v[n] 序列将具有良好的随机特性。v[n] 序列的周期为 2³¹3¹⁹5¹³ = 3.0468×10²⁷。

13.5 链式异或生成器

最简单的链式异或生成器操作的是一串比特，例如 10111。基本思想是将第一个比特与最后一个比特进行异或操作，删除第一个比特，并将新比特附加到字符串的末尾，即 x[i] = x[i-1]⊕x[i-n]。由于 n 位字符串有 2^n 种可能的值，而且由于全零字符串产生一系列全零，链式异或生成器的最长周期为 2^n-1。让我们用 3 位字符串的一个小例子来看一下。

经过 7 步后，初始字符串 001 重复，因此该生成器的周期为 7。这称为完整周期生成器。当 n 为 2、3、4、6、7、15 或 22 时，链式异或生成器具有完整周期。对于 n = 37，该生成器接近于完整周期的概率为 0.00057%。也就是说，99.99943% 的所有 37 位值形成一个大循环，而其余的属于较短的循环。对于某些目的，n = 37 可能是一个不错的选择。对于大多数 n 值，存在若干个重复的比特序列，有些短，有些长。它们的总长度为 2^n-1。只有对于完整周期生成器才能谈论周期。否则会有多个循环，可能长度不同。

假设你需要一个周期长于 2²² 的生成器，并且不愿意冒获得短周期的 0.00057% 的风险。你可以怎么做？一个选择是尝试其他生成函数。而不是使用 x[i] = x[i-1]⊕x[i-n] 的递归关系，尝试使用 x[i] = x[i-1]⊕x[i-j]⊕x[i-k]⊕x[i-n] 的递归关系，其中 j 和 k 的值使得 1 < j < k < n。这些生成器中很有可能有一些具有完整周期。但是请注意，具有 3 项的 x[i] = x[i-1]⊕x[i-j]⊕x[i-n] 的生成器永远不会产生完整周期。项数必须是偶数。

无论你选择哪个生成器，结果都是一系列比特序列。要得到伪随机的字节序列，将比特按照 8 位一组取出，即比特 1 到 8，比特 9 到 16，比特 17 到 24，依此类推。这需要为每个字节生成 8 位比特。有一种更快的方法。不是逐比特进行异或操作，而是一次异或一个字节。实际上，您是同时运行 8 个单比特生成器。这样，每次操作就可以获得一个完整的字节。如果你的编程语言支持，你可以使用完整的 32 位字，并每次获取 4 个字节。

在 13.1 节列出的任何组合函数都可以用于将伪随机流与明文组合成密码。如果 Sandra 选择xor、add或madd作为组合函数，那么密码将很容易让 Emily 解密，前提是她拥有足够的已知明文。她可以轻松确定与明文字符对应的随机输出。这使她可以重构密钥流的一部分。这一部分可以向前和向后延伸，仅通过进行异或操作就可以重构整个密钥流。

Sandra 可以使用一个技巧来迷惑 Emily。假设生成器产生一系列 32 位字，Sandra 将其分成四个单独的字节。Sandra 不一定总是从高阶位开始，而是每次可以从不同位置开始。等效地，Sandra 可以将 32 位字循环左移或右移，位移数量不同。例如，ABCDEF 循环左移 2 位得到 CDEFAB。位移的长度可以是在 0 到 31 范围内的重复数字序列。这样，Emily 无法将生成器的连续输出匹配起来以重构密钥流。

13.6 链式加法生成器

链式加法生成器，也称为滞后斐波那契生成器，类似于链式异或生成器，只是它们使用加法而不是异或。加法被理解为模 2^w，其中 w 是位大小，x[i] = (x[i-1]+x[i-n]) mod 2^w。w 的典型值为 15、31 和 63，使用有符号加法，或者 16、32 和 64，使用无符号加法。另一种看待 mod 2^w 运算的方式是忽略高阶位的进位。

因为加法会从一个位位置产生进位到下一个更高位位置，所以高位的周期是低位的两倍。每个字中低阶位的周期与具有相同种子的异或生成器的周期相同。这是因为加法与带进位的异或相同。如果链式加法生成器中低阶位的周期为 P，则高阶位的周期为 2^(w-1)P。

链式加法生成器是一种简单的方法，可以在很少的额外工作量下获得更长的周期。只需找到一个具有长周期的链式异或生成器，最好是完整周期，然后将其从单比特宽度扩展到完整字宽度。与乘法同余生成器一样，输出序列中最随机的部分是高阶端。对于伪随机字节序列，只使用每个字的高阶 8 位。

再次，您可以使用第 13.1 节中的任何组合函数将伪随机流与明文组合成密码。

13.7 移位和异或生成器

另一类 PRNG 是由佛罗里达州立大学的 George Marsaglia 发明的移位和异或生成器。Marsaglia 最著名的是开发了 Diehard 随机数测试套件。这些生成器使用两个作用于整数的运算符。

• << 左移. 例如，80<<2 将整数 80 左移 2 位，得到值 320。
  

右移. 例如，80>>2 将整数 80 右移 2 位，得到值 20。

被移出计算机字的高位或低位的位将会丢失。例如，25>>1 是 12，而不是 12.5。这些操作与循环左移 <<< 和右移 >>> 相对应，其中被移出计算机字一端的位将被放置在相反端。例如，如果 32 位计算机字中的十六进制数字为 12345678，则 12345678<<<4 得到 23456781，而 12345678>>>12 得到 67812345，因为每个十六进制数字有 4 位。如果字包含在较大的计算机寄存器中，则未使用的位需要清零。

在这个类中有几种不同的生成器。必须仔细选择位移的长度和方向，以使生成器具有长周期。以下是 Marsaglia 设计的两个 Xorshift 生成器的示例。它们具有长周期和强大的随机特性，尽管它们未通过一些更敏感的随机性测试。每个生成器使用左-右-左的模式中的 3 次位移和异或步骤来生成序列中的下一个数字。变量 y 用于保存中间值。任何正整数都是合格的种子。

13.8 FRand

FRand，即快速随机生成器，是我自己的创建。FRand 使用一个宽度为 W 的 S 个二进制字的数组，也就是说，它使用数组中每个字的低位 W 位来保存无符号整数值。周期取决于 S 和 W 的值。我发现 W = 29 效果最好，而且 S = 40 和 S = 64 给出了非常长的周期。种子数组可以看作是一个 40×29 位的矩阵。每一行是一个种子，每一列代表种子字中的一个位位置。

对于 S = 40，周期为 2¹¹⁶⁰-2⁴⁰，约为 1.566×10³⁴⁹，对于合格种子。如果至少有一个 40 个种子字中的一个既不全为零也不全为一，则该种子是 合格 的。该生成器有一个弱点。如果种子数组几乎完全为零，则生成器可能会产生数十甚至数百个连续的输出，其中大部分是零。在极端情况下，当种子数组包含 1159 个零和仅 1 个一时，至少需要 1120 个周期才能在每列中至少有一个 1。

最好是初始种子包含大量随机模式中的 1 和 0。获取适当的种子数组的一种方法是将表达为 UTF-8 代码的助记符或数字密钥，并将其哈希为一个 1160 位值。一个合适的哈希函数是

生成器一旦被初始化，伪随机序列就可以通过递推公式生成。此生成器的递推公式使用索引或标记符号 n。

每次通过种子数组时，当 n = 40 时，索引会重置为 1，并且下一个伪随机数将由 x[1] = (x[1]⊕x[40])>>>1 生成。也就是说，第一个 29 位字 x[1] 循环向右移动一个位位置。

这个伪随机序列通过了许多随机性测试，但远远达不到密码学安全的要求。为了产生一个安全的序列，诀窍是从 29 位字的不同部分获取每个连续的输出字节。伪随机序列本身可以用来选择这些位置。假设下一个 3 个伪随机输出分别是 a、b 和 c。取 s = a mod 25。如果 s 在 0 到 21 的范围内，则将 b 向右移动 s 个位置并取低 8 位。在这种情况下只生成 a 和 b。c 将为下一个伪随机数生成。如果 s > 21，则将 s 位置向右移动会留下少于 8 位。在这种情况下丢弃 a 并取 s = b mod 22。将 c 向右移动 s 个位置并将低 8 位作为随机输出。代数表示如下，

该过程平均使用 2.12 个伪随机输出来产生每个安全密钥字节。这样，密钥字节大约一半的时间来自偶数输出，另一半的时间来自奇数输出。生成器会以不规则的方式大约每 8 个周期在奇数和偶数之间来回切换。

13.9 梅森推土机

梅森推土机 是任何 PRNG 类别中周期最长的。它由广岛大学的松本真和西村拓士于 1997 年开发。它以法国神学家马林·梅森（Marin Mersenne，1588-1648）的名字命名，他以形式为 2^n-1 的素数而闻名，并因传播伽利略、笛卡尔、帕斯卡和费马等人的作品而广为人知。

推土机 具有良好的随机特性，尽管它在一些随机性测试中失败。它比本章描述的其他随机数生成器要慢得多。它的主要重要性在于其庞大的周期，即梅森素数 2¹⁹⁹³⁷-1，该数在 1971 年由 IBM 纽约州约克敦的 IBM 研究院的 Bryant Tuckerman 发现。IBM 研究院为此发现感到非常自豪，将“2¹⁹⁹³⁷-1 是质数”印在了其信笺和邮资表上。

与 FRand 一样，梅森推土机也存在一个缺点，即如果初始状态大部分为零，则可能需要许多周期才能变得看起来随机。对于梅森推土机，通常需要 10,000 或甚至 50,000 个启动周期才能开始使用输出。相比之下，FRand 软件包有一个函数，它可以在不需要任何启动周期的情况下初始化生成器。

13.10 线性反馈移位寄存器

线性反馈移位寄存器（LFSR）是电气工程师的宠儿，因为它在数字电路中实现起来非常简单。LFSR 使用一系列位 x[1]、x[2]、…、x[n]。下一个位通过对前面的几个位进行异或运算来生成，例如

使用 3 个反馈。当然，反馈的数量不一定是 3，但是奇数个反馈通常会比偶数个反馈给出更长的周期。

假设 i < j < k，则此 LFSR 将有 k+1 位位置。生成每个新位后，低阶位被移出，新位被放置在高阶位置，因此寄存器始终包含伪随机序列的最新的 k+1 位。

使用 LFSR 的一个明显缺点是它们速度较慢，因为它们需要 8 个周期才能生成每个伪随机输出字节。LFSR 也是伪随机生成函数中最弱的，因为它们完全是线性的。如果 Emily 有一些已知的明文，并且能够确定相应的关键位，则她可以通过解一组线性方程来重构整个伪随机序列，这很容易。如果 Sandra 使用xor、add或madd作为组合函数，Emily 可以确定关键位。

因此，伪随机输出通常在与明文结合之前通过非线性替换。这可以通过两种方式进行，按位或按字节。非线性按位替换是可能的，因为在每个周期中，寄存器中有 k+1 个位可访问。用作非线性函数输入的位称为taps，可以从寄存器的任何位置获取。使用这些非线性函数使得 Emily 更难确定关键位。

一个合适的非线性函数是多数 函数。如果其输入位的大多数为 1，则此函数的值为 1，否则为 0。对于具有 3 个输入位 A、B 和 C 的情况，多数函数是 AB∨BC∨CA，其中 ∨ 是布尔 OR 函数。多数函数对于任何奇数个输入，如 3、5、7，等等，都是定义的。这个想法的一个扩展是使用 9 个 taps 和三个 3 位多数函数电路。9 位中的三个位进入每个电路。然后，将 3 个输出位通过第四个多数电路。

如果组合函数是sxor、sadd或poly，则字节替换是固有的。这些非线性替换的构造在第 12.3 节中详细讨论。可以将按位和按字节替换组合起来。生成输出字节中的每个 8 位都使用 taps 和非线性位函数，然后将这些电路的 8 个单个位输出馈入按字节替换中。

让我们看看 Emily 必须做些什么来破解一个 LFSR 密码。假设 Sandra 使用一个 40 位的硬件 LFSR， taps 位于位位置 3、6 和 9，进入到一个大多数功能电路 M 中，并且她天真地使用 xor 作为组合函数。进一步假设 Emily 有一些已知纯文本的字符，因此知道了一系列输出位。对于每个已知位，进入 M 的 3 个 LFSR taps 位置只缩小到了 8 个可能值中的 4 个。如果位是 0，则 3 个 taps 必须是 000、001、010 或 100。如果位是 1，则 3 个 taps 必须是 011、101、110 或 111。

经过 4 个周期，12 位已经进入了 3 个 taps，所以对于这 12 位有 4⁴ = 256 种可能的组合。这相比于 2¹² = 4096 种组合大大减少了。更好的是，从 Emily 的角度来看，最初位于位置 3 的位现在位于位置 6，而最初位于位置 6 的位现在已经移动到位置 9。这意味着一些 12 位组合可以被消除。可以消除的组合数量取决于输出位的序列。如果第一个和第四个输出位相同，则消除的组合较少。如果它们不同，则消除的组合较多。每个额外的已知输出位进一步减少了移位寄存器中可能组合的数量。

举个例子。假设 Sandra 使用一个 40 位的 LFSR，带有 3 个 taps，每个 taps 都进入到大多数功能中以产生每个输出位。还假设 Emily 知道设备的所有细节，并知道消息来自总部，所有消息都以 GHQ 开头。这给了她 24 位已知纯文本。如果她将这 24 位与密文的对应位进行异或运算，她就从设备中得到了 24 个输出位。对于这些输出位中的每一个，都有 4 种可能的 3 位输入组合来产生已知值。这就在 3 个 tap 位置产生了 72 位可能的位值。由于 LFSR 中的位每个周期向前移动一个位置，这些位组合会重叠，因此总的组合数量可以不断减少。

Sandra 应该从这个简要分析中学到什么？(1) 扩大移位寄存器，最好至少为 128 位。(2) 将 taps（触发器）远离得越远越好。(3) 不要均匀地分布 taps。在这里，3、6、9 是一个异常糟糕的选择。(4) 使用一种让对手难以确定关键位的组合函数。不要使用 xor、add 或 madd 作为组合函数。更好的选择是 xors 和 adds，但最佳选择是 poly。

13.11 估计周期

如果你是一个密码学爱好者，你可能想要尝试设计自己的伪随机生成器。本书不会涵盖如何测试 PRNG，这是一个很大的主题，但让我们看看你如何估计你的生成器的周期。该方法取决于状态向量的大小（第 13.2 节）。

如果状态向量很小，比如 31 位，您可以只运行您的生成器 2³¹个周期，看看何时重复。不幸的是，初始种子可能永远不会重复。有一个处理这种可能性的技巧。制作 2 个 PRNG 的副本，并使用相同的种子 S 进行初始化。然后逐步运行第一个副本，每次运行第二个副本 2 步。假设您发现在 3000 个周期后，这 2 个副本产生相同的状态向量。这意味着 R[3000] = R[6000]，因此您的生成器的周期至少为 3000，使用种子 S。

如果状态向量较大，比如 64 位，那么运行您的生成器潜在地 2⁶⁴个周期是不可行的。您仍然可以通过抽样来估计周期。制作一个表，比如 T = 1,000,000 个条目。这个表中的第 N 个条目将保存您的生成器产生值 N 时的周期数。最初，将这个表中的所有条目都设置为零，因为尚未产生任何值。选择范围在 1 到 T-1 之间的种子，并运行您的生成器，也许是 G = 1,000,000,000 个周期。在每个周期，如果生成的值 N 小于 T，则记录表中的周期号 N。如果条目不为零，则表示有重复项，这告诉您周期。例如，如果值 12795 在第 33000 个周期和第 73500 个周期再次产生，则该种子的生成器周期为 73500-33000 = 40500。

如果您找不到任何重复项，那么您可以通过查看生成了多少个 T 值来估计周期。如果表中的 E 个条目不为零，则生成的条目比例为 E/T。由于您运行了 G 个周期的生成器，估计周期为 G/(E/T) = GT/E。

正如我们在链式数字生成器（第 4.5.1 节）中看到的，一个生成器可能有几个不同的循环，有些长，有些短。您应该对生成器的周期进行多次估计，使用不同的种子。一个好的策略是首先使用种子 1。对于第二个种子，使用第一个种子未生成的最低值。对于第三个种子，使用第一个或第二个种子未生成的最低值。您可以通过制作累积表来做到这一点。在估计运行之间不要将其重置为零。如果在大约 20 到 100 次这样的运行中周期的估计是一致的，那么您可以确信您的生成器对大多数种子具有长周期。

13.12 加强生成器

加强 PRNG 的一种方法是使用一个选择生成器，将生成数字的操作与选择数字的操作分开。 这可以通过在数组中保留 N 个数字来完成，比如 32、64 或 256 个数字。 数组中的每个数字应该是所需随机输出的大小。 例如，如果要生成随机字节，则数组应包含 8 位数字。 首先对 PRNG 运行 N 个周期以产生初始数字，这些数字按生成顺序放入数组中。 然后使用新种子重新启动 PRNG。 然后使用生成器生成范围为 1 到 N 的伪随机数序列。 每个数字用于选择数组的一个元素。 该元素成为下一个伪随机输出。 然后使用 PRNG 用新的伪随机数替换所选数组元素。

这意味着第一个、第三个、第五个，… 随机数用于选择，而第二个、第四个、第六个，… 数字用于替换数组中的数字。 使用两个具有不同种子的 PRNG 的两个独立副本可能很方便，但这不会增加周期。 更好的策略是使用两个周期互质的不同生成器。 然后，组合生成器的周期是它们周期的乘积。 例如，如果数字是由具有周期 2³¹-1 的乘法同余生成器生成的，而数字是由具有周期 2³¹的线性同余生成器选择的，那么组合生成器的周期是 2⁶²-2³¹，或 4.612×10¹⁸。

4.612×10¹⁸的周期对于密码工作已经足够长，但选择生成器仍然不具有密码学安全性。 这是因为艾米莉可以穷举选择器序列并尝试所有 2³¹种可能的种子。 有足够的已知明文，这可能会给她第一个生成器的输出序列，这足以解决问题。

有几种可能的解决方法。 (1) 使用像xors、adds或poly这样的组合函数，这样艾米莉就很难确定随机输出。 (2) 使选择器生成器更大，比如说 63 位而不是 31 位。 (3) 使选择器生成器的种子更大，例如通过使乘数和/或加法常数成为种子的一部分，即生成函数 x[n+1] = (mx[n]+c) mod P 中的 m 和 c。 (4) 使用下一节中的技术来构建一个具有更长周期的选择器。

13.13 组合生成器

伪随机数生成器可以以各种方式组合，以获得更长的周期或更好的随机性属性，或者变得具有密码学安全性。 这些改进通常是相辅相成的。 你不会为了实现另一个而牺牲一个。 如果增加周期，通常会同时改善随机性。 有两类组合生成器，固定组合和可变组合。

固定组合

在固定组合中，有几个 PRNG，最好是周期互质的。这些可以是乘法同余、线性同余或 Xorshift 生成器。这些生成器的输出可以按位或按字节组合。一种按位的方法是从每个生成器中取一组固定的位，并将它们输入到某个组合函数中。例如，可以从 8 个生成器中分别取高阶位，或者从 4 个生成器中分别取两个高阶位。然后，这 8 位将被输入到一个高度非线性的替换中。替换步骤防止 Emily 将每个生成器的输出分离并单独解决它们。

一种按字节的方法是从每个生成器中取高阶字节，并通过对它们进行模 256 相加或者异或来组合它们。两个生成器可以通过将它们的输出相乘并取乘积的中间 8 位来组合。另一种技术是取线性组合，例如 (a[1]x[1]+a[2]x[2]+a[3]x[3]+a[4]x[4]) mod 256，其中 x[1]、x[2]、x[3] 和 x[4] 是来自四个 PRNG 的 8 位输出，并且四个系数 a[1]、a[2]、a[3] 和 a[4] 可以是 1 到 255 之间的任意奇数整数。这些系数可以针对每条消息不同。

例如，四个 PRNG 可以使用素数模 2³¹-1 和 4 个不同但固定的乘数来生成。这四个 31 位种子加上四个 7 位系数组成了 152 位的组合种子。

三个 PRNG 可以通过使用循环移位操作（第 13.7 节）来组合。使用 32 位无符号生成器时，32 位输出可以使用 x[1] + (x[2] >>>11) + (x[3] >>>21) mod 2³² 来组合。最佳移位量是 32 位寄存器大小的 1/3 和 2/3。如果你希望使用超过 3 个生成器，请尽可能使移位量均匀。例如，使用 5 个生成器时，移位量应该是字长的 1/5、2/5、3/5 和 4/5，四舍五入到最接近的整数。

另一个固定生成器 CyGen，通过循环移位来组合两个生成器 C 和 G。C 可以是任何大小，但 G 应该是 32 位或 64 位。在每个周期中，分别从 C 中取 5 或 6 位，以获取移位量。然后，从 G 中取得的输出将向左循环移动该数量的位置，以获得 CyGen 的输出。这使得 Emily 无法从其输出序列重构 G。

没有限制线性组合。例如，可以使用 x[n]+y[n]z[n] 或 x[n]+y[n]²+z[n]z[n-1]z[n-3] 将 3 个生成器组合起来。至少求和中的一项应该是线性的。可能性是无限的，当然，你可以在多种方法之间进行切换。

可变组合

可变组合的一个示例是第 13.11 节中显示的选择生成器。但是，让我用一个警示故事开始这一节。这里有一个组合生成器 CG5，似乎是绝对安全的，但实际上不是。

组合生成器 CG5 使用 5 个乘法同余生成器，每个都有不同的乘数和不同的 31 位素数模数。将这些生成器称为 G0、G1、G2、G3 和 SEL。（或者，SEL 可以是一个线性同余或 Xorshift 生成器，具有 2³¹周期。）生产生成器 G0 到 G3 用于产生伪随机数，选择生成器 SEL 用于选择 G0-G3 中的哪一个用于产生下一个伪随机输出。具体来说，SEL 的高 2 位确定了在 G0-G3 中选择哪一个。假设 SEL 生成了 10，这选择了 G2。然后 G2 生成器运行 1 个周期，其输出成为 CG5 的下一个输出。组合生成器的周期约为 2¹⁵⁵，具有良好的随机特性…但不会是密码学安全的。原因如下：

假设艾米莉有足够的已知明文，并考虑从 CG5 中得到的前 17 个输出。这 17 个输出中至少有 5 个必须由同一个生成器产生。（如果 4 个生成器最多产生 4 个输出，那么最多只能有 16 个输出，而不是 17 个。）从 17 个中选择 5 个项目的方式只有 6188 种。艾米莉可以尝试所有这些方式。这样一来，就有大约 1.33×10¹³种放置加种子的组合需要测试，然而，这可以大大减少。艾米莉知道这 5 个选择输出的每个的高 8 位。她不应该从 17 个输出的第一个开始，而应该从 5 个选择输出的第一个开始。然后，她只需要尝试 2²³个值，而不是 2³¹个值。这样一来，她的工作量就减少到了可管理的 5.19×10¹⁰个组合。CG5 组合生成器并不安全。

让我们看一个更安全的生成器。我将其称为Gen5。再次，组合生成器使用 5 个乘法同余生成器，每个都有不同的乘数和不同的 31 位素数模数。模数和乘数是固定的，并且选择得具有良好的随机特性。这次让我们称这些生成器为 G1、G2、G4、G8 和 SEL。只使用选择器 SEL 的 4 个高阶位。在这个 4 位数中，第一个位上的 1 表示选择 G1，第二个位上的 1 表示选择 G2，第三个位上的 1 表示选择 G4，第四个位上的 1 表示选择 G8。当选择少于两个生成器时，SEL 将再运行一个周期以生成新的选择。只使用 SEL 生成的 16 个可能的 4 位输出值中的 11 个，因此 SEL 将额外运行一个周期的时间为 5/16，额外运行两个周期的时间为 25/256，依此类推。

当选择两个或更多发生器时，它们每个都会运行 1 个周期，它们的输出将模 2³¹ 加在一起，以产生 Gen5 伪随机输出。未选择的发生器不会运行，因此 4 个发生器会异步运行。该输出略微偏向较低的数字，但对 Emily 来说并不足以利用。如果您担心这种偏差，可以（1）丢弃高阶位并使用和为输出字节的高阶位 2 到 9，或者（2）使用 Meld8 操作（第 12.3.7 节）。也就是说，通过将和的高阶 8 位与和的第二个 8 位进行异或运算来从 Gen5 发生器形成输出字节，即将位 1 到 8 的异或位与位 9 到 16 的位进行异或。

*****Emily 再也无法分离出任何一个发生器。Emily 可能看起来可以分离出其中的 6 对 Gi+Gj 中的一个，其中 i 和 j 可以是 1、2、4 或 8。这样的一对可以被视为单个发生器处理，然后稍后可以将 Gi 与 Gj 分离出来。让我们首先看看这种方法。为了求解 Gi 和 Gj 的种子，至少需要来自 Gen5 的 9 个随机输出。由于这些配对每次只发生 1/11 的概率，Emily 可能需要查看 89 个或更多的消息字符。这是因为，仅仅由于偶然，3 个或 4 个发生器的 5 个组合可能比 2 个发生器的 6 个组合更频繁地发生。

对于 89 个物品中的 9 个物品，大约有 6.356×10¹¹ 种可能的放置方式，因此 Emily 只需尝试 SEL 发生器的所有约 2³¹ = 2.147×10⁹ 个种子，这样 Emily 就可以找到所有 6 对 Gi+Gj 的下一个 10 个位置。这也让她可以计算出 Gi 和 Gj 在每次出现时已经被使用了多少次。例如，假设 G2+G4 出现在 Gen5 的第 14 个周期。在这 14 个周期中，可能有 6 个周期中使用了 G2，而 9 个周期中使用了 G4。现在 Emily 知道了 G2 的第 6 个输出加上 G4 的第 9 个输出的值。

如果 Emily 可以为 G2+G4 这样的 10 个输出值组合起来，那么她可以在大约 2^(31+31-8) = 2⁵⁴ = 1.801×10¹⁶ 次试验中确定这两个发生器的种子。这必须对 SEL 的约 2³¹ 个种子进行操作，因此总工作量约为 2⁸⁵ = 3.869×10²⁵。这相比于 Gen5 的暴力解决方案需要 2¹⁵⁵ 次试验有了巨大的改进，但远远不及 2¹²⁸ 次试验的目标。此发生器被评为 Nine.******

现在我们已经准备好进行致命一击了。这是 Gen5 的升级版本，我将其称为 GenX。GenX 由伪随机数生成器和密码两部分组成。GenX PRNG 将生成一个 10 位伪随机输出序列，密码将把密钥字节 k[n] 与消息字节 x[n] 结合起来产生密文。这将使密码超出 128 位密钥大小。

GenX 生成器只是 Gen5 生成器的扩展版本。它使用四个生产生成器 G1、G2、G4 和 G8，以及一个选择生成器 SEL。SEL 的高阶 4 位用于选择 2 到 4 个生产生成器的某种组合。所选的生产生成器运行一个周期，它们的输出相加模 2³¹ 以产生一个和 G。G 的高阶 10 位与下一个 10 位的 G 进行异或运算以产生 10 位输出。10 位输出被分为一个 8 位密钥字节 k[n] 和一个 2 位控制位 c[n]。

GenX 密码器将密钥字节 k[n] 与消息字节 x[n] 根据控制位 c[n] 使用混合的键控替换 S 进行组合。控制位 c[n] 决定了每个明文字节使用哪种组合函数。解释这 2 个控制位的一种可能方式是

所有的和都是模 256。Cipher GenX 被评为十。该密码的密钥是用于 G1、G2、G4、G8 和 SEL 的五个 31 位种子以及用于混合替换 S 的密钥，例如 SkipMix 密钥。

13.14 真随机数

所有在本章讨论过的生成随机数的技术都产生伪随机数。我看过的每一本讨论随机数的书都重复着这样的观念，即使用软件产生真正的随机数是不可能的。这是因为他们将自己限制在了一种太狭窄的可能方法范围内。在本节中，我将介绍一种使用软件批量生成真正随机数的可行方法。

文献中所有用于生成真正随机数的方法都依赖于诸如宇宙射线、热噪声、振动、核衰变等物理现象。这些方法对于加密目的来说太慢了。

相反，你可以通过一个 3 步过程产生真正的随机数。 (1) 从自然界中获取大量真正的随机数。 (2) 使它们的概率分布均匀。 (3) 通过从这个语料库中选择和组合数字来生成随机数。接下来的几节将详细介绍如何完成这些步骤。

自然界充满了随机性。地球上每一棵植物和树上每片叶子的形状、颜色和位置都是随机的。它们是风和微风、阳光透过叶片、从根部流上的养分、打在叶片上的雨滴和冰雹、咬过叶片的昆虫、鸟类、松鼠、地面震动以及许多其他因素的结果。每一个海洋上的波浪、每一个沙漠中的植物和岩石、每一条河流上的涟漪、每朵云、每一个海滩上的贝壳在大小、形状、颜色、位置、方向甚至速度上都是随机的。

这些随机性的一部分可以通过简单地拍摄这些地点来捕捉。你甚至不需要离开家。只需拿一把爆米花撒在有图案的表面上。你还可以使用你认识的人和你去过的地方的照片。有些照片是你从网站和电子邮件中下载的。还有成千上万张照片被操作系统和你使用的应用程序放在了你的计算机上。你可以使用网络浏览器找到数十亿张照片。作为一个实验，我编造了一个伪单词 ZRMWKNV，并搜索了图片。我得到了超过 6,000 个与 ZRMWKNV 相关的搜索结果，其中一些网站包含了数百张图片。

滞后线性加法

每个这样的图像文件包含大量的随机性，特别是如果分辨率很高，但字节值的分布远非均匀，也远非独立。通过使用滞后线性加法，将整个图像文件，包括头部在内，视为长度为 L 的一个长字节字符串，可以使分布变得平坦。以下是一个示例：

下标总是循环的。如所示，三次传递足够了，但随时可以使用更多。你不希望频率太均匀，因为那将不再是随机的。如果你想使用简化版本，比如 x[n] = (x[n]+x[n-179]) mod 256，请注意需要五次传递。确保在每次传递中使用不同的滞后。

这些系数 7、31 等并没有什么特别之处，我是随意选择的。它们可以是从 1 到 255 的任意奇整数。对于每次传递，滞后 40、1581 等应该被选择得一个远大于另一个。小步长，大步长。一个想法是使较小的滞后约为∛L，而较大的滞后约为∛L²。例如，如果图像文件大小为 1,000,000 字节，你可以分别使滞后约为 100 和约为 10,000。较小的滞后可以在 50 和 200 之间选择，而较大的滞后可以在 5000 和 20,000 之间选择。在滞后线性加法之后使用一个带有密钥的简单替换，使得艾米莉更难重建图像文件。

图像分层

另一种构建真随机序列的方法是取两个图像，使用某种组合函数（如异或或加法，参见第 13.1 节）将它们层叠在一起。一个好的方法是在组合之前对每个图像进行一次滞后线性加法传递，然后在它们被组合后进行最后一次传递。

三个图像可以使用非线性大多数函数（第 13.10 节）逐位进行组合。同样，在组合之前，我建议对每个图像进行一次滞后线性加法的传递，然后在它们被组合之后进行最后一次传递。即使三个图像中没有一个大小相同，也可以使用这种方法。将一个短图像对齐到与最大图像相同的位置，并将另一个短图像对齐到与最长图像相同的位置，就像这样：

当只有两幅图像重叠时，按字节模 256 进行相加。当所有三幅图像重叠时，使用大多数函数逐位进行组合，或者使用模 256 的线性组合，如 c[n]=(113x[n]+57y[n]+225z[n]) mod 256。系数可以是从 1 到 255 的任意奇整数。

对齐图像的另一种替代方法是通过重复来扩展短图像。在这个例子中，x 图像有 22 个字节，y 图像有 33 个字节。通过重复 x 的前 11 个字节，可以将 x 图像扩展到 33 个字节。这样，大多数函数可以在所有 33 个字节位置使用。实际上，这些图像将有数百万个字节。

13.15 刷新随机字节

很好。现在我们有一个名为 T 的表，里面有几百万个真随机字节。它们是真正的随机字节，因为如果艾米丽拥有除了一个字节之外的所有字节，这并不会使她能够确定缺失的那一个字节。桑德拉和莉娃都有一份拷贝。那么呢？我们肯定不能每次发送消息都重复这个过程。

利用 T 的一种方法是将其划分为用于分组密码的密钥。一百万个随机字节可以制作出 62,500 个每个 128 位的密钥。最终这一百万字节将被用完。如果桑德拉正在使用一个强大的分组密码，或许这并不重要。她可以重复使用密钥，只要艾米丽无法知道哪些消息使用了相同的密钥进行了加密。当然，桑德拉不能对流密码重复使用密钥。

假设桑德拉不愿意冒再次使用密钥的风险。一个解决方案是刷新随机数列表。桑德拉可以添加另一幅图像，但这意味着莉娃也必须有同样的图像的拷贝。如果图像来自桑德拉和莉娃都可以访问的网站，那么这可能是一个不错的策略。如果传输的密钥可能被截获，这可能是一个很好的策略。

另一种方法是使用滞后线性加法（第 13.14.1 节）刷新 T。称刷新后的表为 T[1]。现在桑德拉只需要传输 9 个系数和 6 个滞后，她就有另外 62500 个密钥可用。假设每个系数需要 1 字节，每个滞后需要 2 字节，桑德拉只需传输 21 字节即可生成 T[1]。然后为了选择消息的密钥，只需要知道该消息密钥在 T[1]中的位置。对此，两个字节足够了，因为所有位置都是 16 的倍数。当 T[1]用尽时，可以使用新的系数和滞后来构造 T[2]等等。

在第 13.5 节和 13.6 节中，线性函数用于确保生成器具有长周期。这里没有周期，因此没有这样的约束。可以使用一些非线性函数，例如

这里下标循环，a 和 b 是从 1 到 255 的奇整数，i、j 和 k 是介于 1 和 L-1 之间的整数。S 可以是一个固定的非线性替换或者一个变量密钥混合替换。函数 E(x)定义为

当你取 E(x[n-j]x[n-k]) mod 256 时，实际上是将 x[n-j]x[n-k]的各个字节相加。这比仅仅使用 x[n-j]x[n-k]更强，因为 x[n-j]x[n-k]有 3/4 的概率是偶数。

或者，桑德拉可以通过按 1 字节、跳过 3 字节、取下一个字节、跳过 2 字节、取 2 字节、跳过 4 字节等一些周期序列中的步骤，从 T 获得密钥。跳过可以很小，因此 2 或 3 个跳过可以编码在一个密钥字节中。可能如果艾米莉获得了随机源 T，她可以确定小跳过的序列。为防止这种情况，跳过可以与在选定字节上添加一系列数字相结合，对 256 取模，同样周期性。如果跳过的数量和添加的数量是互质的，比如 12 个跳过和 11 个添加，那么是最安全的。使用这种方法，每个消息密钥将使用 2 字节作为起点，6 字节来编码 12 个跳过，再加上 11 个添加，总共 20 字节，或者 160 位。这种方法可以称为跳跃与添加。

在这种类型的系统中，Emily 无法重建 T 是至关重要的。例如，Emily 可能随着时间的推移获得了许多消息的明文并恢复了它们的密钥。如果她还知道这些密钥在 T 中的位置，也许是因为桑德拉在每条消息中将位置传输给了 Riva，那么她可能能够重建 T 的部分。因此，T 本身不应该用于密钥。应该保留 T 以构建 T[1]、T[2]，…，然后可以将其划分为消息密钥。保留 T 可以保护桑德拉和 Riva，以防 T[i]中的任何一个丢失或损坏。T 可以称为基础密钥，T[1]、T[2]，…可以称为派生密钥。

即使 Emily 可以以某种方式重建 T[1] 或 T[2]，她也无法倒退恢复 T，因为 T 是真正的随机。如果 Emily 尝试所有可能的系数和滞后组合，没有任何东西能表明哪个是正确的随机字符串 T，因为有数以万计的字符串。

13.16 同步密钥流

在秘钥密码学中，Sandra 和 Riva 必须使用相同的密钥。通常这意味着要么（1）密钥被加密并与消息一起传输，要么（2）他们有一个密钥列表，并根据日期、时间或其他外部因素从列表中选择每个密钥。还有一种方法是流密码独有的。

Sandra 和 Riva 可以使用同步密钥流。这意味着 Sandra 和 Riva 都持续生成相同的密钥流。当 Sandra 加密一条消息时，她从她的密钥流中的下一个密钥字节开始，这也必须是 Riva 的密钥流中的下一个密钥字节。当 Riva 收到消息时，她必须从密钥流中的相同点开始。Sandra 和 Riva 必须在完全相同的时间从相同的初始种子开始生成。当 Sandra 和 Riva 之间有直接电缆连接，或者有视线塔到塔的连接，或者两者都从同一发射机接收过空中广播时，同步方法最为有用。它非常适合在狭小空间内传输数字化语音。

如果消息是通过具有节点或中继点有显著延迟的网络发送的，特别是分组交换网络，其中消息的部分可能通过不同路径到达并必须在接收端重新组装，发送方必须在传输开始时提供时间戳，比如在消息头中。

由于 Sandra 加密消息需要时间，消息从 Sandra 到 Riva 的传输也需要时间，似乎 Riva 必须比 Sandra 慢几微秒生成随机密钥。同样，当 Riva 发送消息给 Sandra 时，Sandra 也必须比 Riva 慢几微秒生成密钥。

有几种方法可以摆脱这一僵局。一种方法是让 Sandra 只在伪随机流中的特定周期开始消息。例如，Sandra 可能只在每 100,000 个周期开始一条消息。然后当 Riva 在第 123,456,789,123 个周期收到一条消息时，她知道密钥从第 123,456,700,000 个周期开始。如果消息接收时间更接近 100,000 的整数倍，比如第 123,456,701,234 个周期，Riva 可以尝试 123,456,700,000 和 123,456,600,000。Riva 需要存储最后两组 100,000 个伪随机数。100,000 个周期的数字可以根据 PRNG 的速度和两方之间的传输时间调整。

还有一个问题需要解决，即 Riva 如何检测到每个加密消息的起始和结束。如果通信通道有一个空闲状态，在该状态下既不传输零也不传输一，则没有问题。让通道在消息之间保持空闲。否则，让我们假设通道在空闲时发出一串稳定的零。在这种情况下，您需要在消息前后添加额外的 1 位，就像用引号括起消息一样，并要求在下一条消息开始之前必须传输至少 64 个零。在合法消息中发生 64 个零的几率微乎其微。 （此外，请注意，消息之间的平均时间实际上将超过 50,000 个周期；64 个周期只是最坏情况。）因此，当 Riva 检测到至少 64 个零后的 1 位时，她可以确信这是下一条消息的开始，当她发现 1 位后跟着 64 个或更多的零时，那标志着消息的结束。

13.17 哈希函数

哈希函数不是密码，但与密码密切相关，通常与密码学一起使用。在本节中，我将讨论哈希函数的两个用途，并为每个用途提供一个适用的哈希函数。

哈希函数经常用于搜索。假设您有一个人员列表，如客户、患者或学生，并且您经常需要搜索此列表以获取有关这些人的信息。哈希提供了一种快速搜索的方式，即通过将人的姓名转换为可以直接在表中找到的数字。例如，名称“John Smith”可以转换为数字 2307，其中表中的条目 2307 包含有关 John Smith 的信息。

这里有一个专为此目的设计的哈希。对于字母表中的每个字母 L，随机选择某个固定大小（例如 32 位）的二进制值 R(L)。要对名称进行哈希，只需对名称中每个字母的 32 位数字执行异或操作。该哈希的一个弱点是具有相同字母的名称将具有相同的哈希值。例如，ARNOLD、ROLAND 和 RONALD 的哈希值都相同。为了避免这个问题，在添加每个字母后，将哈希值向左循环移动 1 位位置。也就是说，

将最终的哈希值称为 H。H 可以通过缩放转换为大小为 T 的名称表的索引 I，公式为 I = ⌊HT/2³²⌋。例如，如果名称的哈希值为 917354668，表中有 5000 个条目，则索引为 ⌊917354668×5000/4294967296⌋ = ⌊1067.94⌋ = 1067。我们称这种哈希方法为 Hash32。

可能会有几个名称产生相同的索引。有各种方法用于处理这些索引冲突，例如使用一个单独的表来保存重复项，第二次对名称进行哈希以在表中选择不同的插槽，或将重复名称链接在一起。

哈希函数也用于消息认证。在这种情况下，整个消息被哈希为一个长的哈希值。假设是 16 个字节。这个哈希值必须以防篡改的方式发送给 Riva，例如通过一个可信赖的第三方，该第三方记录并加上时间戳的哈希值。然后 Riva 将对消息进行哈希处理并比较哈希值。如果它们不同，那么消息可能已被更改。用于此目的的哈希函数必须使得 Emily 无法修改消息而不改变哈希值成为不可行。也就是说，Emily 无法找到一个产生相同哈希值的不同消息。同样，Sandra 无法更改消息并声称她发送了更改后的消息，因为哈希值将不再匹配。

对于这个哈希函数，我们将使用 4 个高度非线性的替换，分别为 A、B、C 和 D。这些可能是公开已知的固定替换。值得花一些精力使这四个替换高度非线性且彼此之间的相关性最小化。基本操作是使用异或的组合函数将消息的每个字节与前 4 个字节进行组合，即执行异或操作，然后对结果进行简单的替换。让 H 是消息 M 的一个副本，以便消息在哈希处理过程中不被破坏。副本中的每个字符 H[n]都经过以下哈希处理：

这样，哈希的每个字节都依赖于前面的每个字节，并且每个后续的字节都依赖于它。

哈希需要一个初始化向量（第 11.10 节）以便对消息的前 16 个字节进行哈希处理。可以使用消息的前 16 个字节的副本。也就是说，最初字节 H[-15]到 H[0]与字节 H[1]到 H[16]相同，这些字节是消息的字节 M[1]到 M[16]相同。有了初始化向量，就可以将哈希从 H[1]传播到 H[L]，其中 L 是消息的长度。

这使得最后几个字节的哈希相对较弱。Emily 可能很容易改变消息的最后几个字节。解决方法是在消息结束后继续哈希处理。为此，当我们对消息的前 16 个字节进行哈希处理时，我们保存这些哈希值以供以后使用。当我们到达消息的末尾时，我们附加这 16 个字节并继续哈希直到扩展消息的末尾。这最后的 16 个字节成为消息的哈希值。将此哈希方法称为Hash128。

对于某些机器，使用机器的 32 位算术函数，每次对消息进行 4 字节的哈希可能更快。消息和哈希值被视为 L 个 32 位字的列表，而不是 4L 字节。哈希数组 H 最初是消息的一个副本。如果消息长度不是 4 字节的偶数倍，则会附加多达 3 个字节以填充最后一个字。H 的前两个字的副本被附加到前面，即 H[-1] = H[1] 和 H[0] = H[2]。在对消息的前 4 个字进行哈希后，这 4 个字将附加到消息的末尾。

这种哈希，称为 HashPQ，使用两个素数 P = 2³²-5 = 4294967291 和 Q = 2³²-17 = 4294967279，以及魔法乘数 R = 77788888，它是 P 和 Q 的一个原根。哈希操作为

如果总和超过 2³²-1，则通过简单地忽略额外的高位比特来将值截断为 32 位。也就是说，我们可以自由得到模 2³² 运算。H 数组的最后 4 个字是 16 字节哈希值。与 Hash128 相比，HashPQ 使用的存储空间更少，因为它不需要 4 个简单的替换。

Hash32、Hash128 和 HashPQ 都具有良好哈希函数所需的理想属性，即对输入的任何位或位的组合进行更改会导致输出中大约一半的位发生更改。这三种哈希都很快，并且可以在单个从左到右的传递中完成。

第十四章：一次性密码

本章涵盖

• 一次性密码密码
  
• 伪一次性密码，它近似于一次性密码
  
• Diffie-Hellman 密钥交换
  
• 构建 Diffie-Hellman 和公钥密码所需的大素数
  

最著名的流密码是一次性密码。许多作家将这个术语限制为仅指明文和密钥流逐字节进行异或的密码。这在历史上是不准确的。第一个一次性密码密码是由加利福尼亚州萨克拉门托的银行家弗兰克·米勒于 1882 年发表的，目的是通过缩短电报消息来节省费用。米勒的电报代码使用 5 位数字代码组来表示商业电报中常见的单词和短语。为了保密，米勒提出了一个密码，其中包括将 3 位数字添加到每个 5 位数字组中。他的代码值足够小，以至于总和永远不会超过 99999。也就是说，代码都小于 99000。因此，一次性密码最初是一个十进制系统，而不是一个二进制系统。

赋予一次性密码其名称的系统是由德国 Pers Z S（信号情报机构）的密码学家沃纳·昆策在 1922 年左右设计的。昆策的系统基于标准的 5 位数字组外交代码。与米勒的密码类似，昆策的密码将密钥组添加到代码组中。昆策使用了 5 位数字密钥组，逐位地将其添加到代码组中，而不进行进位。因此，33333+56789 将导致 89012，而不是 90122。昆策将密钥分发在 50 张纸的本子中，每张纸包含 8 行，每行包含 6 个密钥组。这些本子的页面一次用于加密一条消息，然后被丢弃。因此得名一次性密码。后来的发展包括使用水溶墨水和水溶纸进行快速处理。

另一个版本的一次性密码是由英国作家和编剧（Peeping Tom）利奥（利奥波德·塞缪尔）·马克斯于约 1940 年发明的。它被英国间谍广泛使用。马克斯的版本使用字母而不是数字。发送者将密钥字母加到明文字母模 26，以获得密文字母。换句话说，马克斯的一次性密码是一个带有随机密钥的贝拉索密码。麻省理工学院教授克劳德·香农在 1940 年至 1945 年之间发明了相同的密码，苏联信息理论家弗拉基米尔·科特尔尼科夫在 1941 年或之前发明了一个版本，但其细节仍属机密。香农和科特尔尼科夫都提出了一次性密码无法被破解的数学证明。它仍然是唯一被证明无法破解的密码方法。

自从米勒的 1882 年一次性密码和昆策的 1922 年一次性密码都使用十进制加法作为它们的组合函数，以及马克斯的 1940 年一次性密码使用模 26 加法，任何人都很难断言��次性密码仅限于使用异或来组合密钥和明文。一次性密码的定义特征是

1. 关键是至少与消息一样长，
   
2. 密钥与真随机不可区分，
   
3. 每个密钥字符或块与一个明文字符或相同大小的明文块组合，并且
   
4. 密钥仅使用一次。
   任何满足这 4 个标准的密码都是一次性密码。然而，要证明一次性密码是无法被破解的，需要另一个更强的条件：
   
5. 任何给定的明文字符转换为任何给定的密文字符的概率相等。
   

说了这么多，让我们看看一个基于异或的历史密码，与一次性密码系统密切相关。

14.1 佛南密码

到 1918 年，许多外交任务已经不再由人类电报操作员发送和接收消息，然后需要手动输入。相反，消息被打孔到由法国电报工程师埃米尔·鲍多特于 1870 年发明的 5 列鲍多码或由新西兰记者唐纳德·默里于 1901 年发明的鲍多特-默里码的纸带卷中。（我不会详细介绍这些代码的细节，因为它们在 1870 年至 1950 年代之间几次改变，当西联电报公司在 1963 年停止使用它们时，鲍多特风格的代码完全被废弃了。）重要的特征是一个人类打字员将消息键入到一个 5 列纸带中，从而可以直接在接收端传输和打印而无需任何进一步的人类参与。

与摩尔斯密码一样，无论是鲍多码还是鲍多特-默里码都没有提供任何保密性。任何人都可以直接从磁带上读取消息。直到 1918 年，如果需要保密性，消息必须由人工密码员手动加密，然后被输入到磁带上，并由接收端的另一名职员手动解密。需要一种方法来加快这个过程。于是佛南出现了。

佛南密码由 AT&T 贝尔实验室的吉尔伯特·桑福德·佛南在 1918 年应陆军信号部的约瑟夫·O·莫伯格纳之邀开发。这个想法非常简单而巧妙。一个人类打字员会像以前一样将消息键入到磁带上，但实际传输的是字符代码与密钥代码的异或。密钥代码来自一个单独的纸带，其上打有看似随机的字符序列。在接收端，传输字符将与该磁带的副本进行异或运算，从而解密它们。每个磁带有 1000 个类似随机的字符，以便长消息每 1000 个字符重复一次密钥。

该图显示了两个包含明文和密钥的磁带，用于读取磁带的拾取器，用于将密钥与明文进行异或运算的电路，以及接收端的打孔机，该打孔机可能位于远程位置。打孔机可以根据设置替换为打印机或发送器。

这是我自己的图表，因为我找不到 Vernam 机器本身的图片，可能是因为它被列为机密。

我将密钥带称为“近似随机”，因为它们是由一个人在类似打字机的键盘上敲击而产生的，这是 Friden Flexowriter 的前身。结果是键盘中心附近的字符比角落附近的字符更经常使用。人类很难产生随机数或字符。但对于 1918 年来说，这是一个非常强大的密码。

许多来源错误地将 Vernam 密码称为一次性密码本，可能是因为它是第一个使用二进制消息与二进制密钥进行异或运算的密码。然而，Vernam 密码并不是一次性密码本，因为它是重复的。它有一个固定的 1000 个字符的周期。此外，一次性密码本早在 36 年前就由米勒发明了，并且最初是一个基于十进制的系统。

对于一个繁忙的大使馆，可能每天会有 100 个或更多的密码消息。如果大使馆与其他几个大使馆通信，就需要多套带子。用于华盛顿到柏林的带子将与用于柏林到华盛顿的交通的带子分开。所有带子都标有 6 位数的序列号。在发送每个消息之前，带子编号将以明文形式传输，即未加密。办事员们需要区分哪些带子是为哪个大使馆准备的，哪些带子已经使用过需要销毁。新的带子必须不断地提供给每个大使馆。

Vernam 很快设计了第二个版本，使用了两个带子，两个带子都与明文进行了异或运算。一个带子有 1000 个字符，另一个带子有 999 个字符，使有效周期为 999,000 个字符。同一两个带子可以在整个一天内使用，只需在每个带子上的不同位置开始每个消息即可。如果一个大使馆有，比如，100 个带子，那么可以在不同的日子使用不同的带子组合，只要纸带能支持。

很容易看出 Vernam 的 2 带机器如何扩展到 3 或 4 带。就我所知，这从未发生过，因为这些基于带子的机器很快就被转子机取代了（参见第 5.10 节）。

14.2 密钥供应

一次性密码本的主要问题是提供足够的密钥。纸带方法可能足够用于每天发送 100 条消息的 10 个站点，但对于每天发送 1000 条消息的 100 个站点来说是行不通的。

许多关于密码学的书籍和论文描述了以下难题：桑德拉和里瓦决定使用一次性密码交换消息。他们每个人都有一份长随机密钥的副本。他们逐段使用这个密钥，直到用完为止。现在他们需要另一个随机密钥。桑德拉可以选择并发送给里瓦，但需要加密以防艾米莉获取。最安全的方法是使用一次性密码对其进行加密，因此他们需要另一个与之长度相同的密钥来加密新密钥。同样，桑德拉可以选择并发送给里瓦，但该密钥也需要加密。因此，他们需要另一个密钥，无穷尽。

这个困境的解决方案是双管齐下的。首先，可以使用第 13.15 节的技术（如滞后加法）刷新随机密钥流。例如，每天一次，或者当各方决定时，可以从基础密钥派生一个新密钥。其次，这些派生的每日密钥不需要直接用作消息密钥。相反，可以从每日密钥构建消息密钥。这样，即使艾米莉恢复了任何消息密钥，她距离恢复基础密钥还有两层。接下来的几节将描述一些生成消息密钥的方法。

每种方法都旨在实现两个目标：要么（1a）该方法必须能够每天生成足够的消息密钥材料，以便没有两个消息密钥重叠，要么（1b）艾米莉不可能检测到消息密钥的重叠部分，以及（2）艾米莉不可能重建派生密钥或基础密钥的部分。

14.2.1 循环密钥

每日密钥是使用第 13.14 节的技术派生的。每日密钥的连续部分用于生成消息密钥，例如通过轻度加密。一个带有密钥的简单替换就足够了。我建议在连续密钥之间留下随机宽度的间隙，例如 1 到 32 字节。当到达每日密钥的末尾时，它会使用滞后线性加法（第 13.14.1 节）的单次传递来延长以供在消息量较大的日子使用。您可以通过想象每次发送消息时，其密钥加上任何间隙都会从每日密钥的前端移动到每日密钥的末尾，并使用滞后线性加法进行刷新来可视化这一点。桑德拉和里瓦必须同步进行此操作。

这在消息量较低且桑德拉和里瓦很少同时发送消息的情况下效果很好。对于更高的消息量，最好使用两个基础密钥和两个每日密钥，一个用于桑德拉到里瓦的消息，另一个用于里瓦到桑德拉的消息。

14.2.2 组合密钥

对于长度为L的每条消息，从每日密钥中取出长度为L的三个段。将这些段称为 x、y 和 z，并将它们在每日密钥中的起始位置称为 p[x]、p[y]和 p[z]。如果这些位置中的任何一个接近每日密钥的末尾，则该段可能回到开头。消息密钥的每个字节都是通过取 x、y 和 z 中相应字节的线性组合形成的。也就是说，

其中系数 a、b 和 c 可以是 1 到 255 之间的任何奇整数。三个系数 a、b 和 c 的值以及三个起始位置 p[x]、p[y]和 p[z]对于每条消息必须是不同的。这些可以事先商定，或者加密并与每条消息一起发送。

14.2.3 选择密钥

对于长度为 L 的每条消息，从每日密钥中随机选择两个不重叠的段。第一个段是选择器，s，长度为 L。第二个段是库存，x，长度为 256。为了加密消息中的第 n 个字符 m[n]，我们首先从选择器中取出相应的字节 p = s[n]。这个 p 选择了库存中取出密钥字节的位置，即 k[n] = x[p]。密钥字节 k[n]与消息字节 m[n]结合使用任何组合函数，如异或或加法。

在使用密钥字节 k[n]后，x[p]在库存中被替换为(ax[p]+b) mod 256。系数 a 和 b 必须满足 Hull-Dobell 条件（第 13.4 节），即 a≡1(mod 4)且 b≡1(mod 2)。实际上，库存 x 中的 256 个位置中的每一个都成为一个独立的线性同余伪随机数生成器（PRNG）。系数 a 和 b 可以对库存中的所有 256 个位置使用相同的值，也可以不同。一种选择是使用两对不同的 a 和 b 值，并根据某种固定模式选择第一对或第二对。无论使用多少对值，对于不同的消息，它们应该是不同的。

另一种更新库存的方案是将 x[p]替换为(ax[p]+bx[p-1]) mod 256，其中 a 和 b 是 1 到 255 之间的任何奇整数。您还可以选择将 x[p]替换为(ax[p]+bx[p-i]) mod 256，其中 i 是从 2 到 255 的任意整数。

由于 a 和 b 只有 8192 个可能的值，并且由于应避免值 a = 1，因此重复是不可避免的。然而，只要 Emily 无法确定每条消息使用了哪对值，这就不是问题。重要的是 Emily 无法累积多条她知道具有相同 a 和 b 值的消息。使用指示器的一个缺点是对手可能收集几条具有相同指示器的消息，因此他们知道这些消息具有相同的密钥。

14.3 指示器

在古典密码学中，通常会长时间使用同一把密钥，有时甚至长达几个月或几年。而在现代，密钥通常只用于单个消息。使用一次性密码本时，消息密钥必须只能使用一次。否则，艾米丽可能会将一条消息滑动到另一条消息上，并使用重合指数（第 5.7 节）来检测重叠。

对于适度的双向消息流量，桑德拉和里瓦可以使用一本小书，列出按照例如时间和星期几来使用的密钥。在计算机出现之前的一种常见做法是给每条消息编号。消息编号可以被加密并与消息一起发送。桑德拉和里瓦将使用消息编号在书中查找密钥。

当消息流量增加或有许多交换消息的参与方时，密钥本就变得不可行。即使将书本替换为计算机文件，情况也是如此。解决这个问题的一个方法是使用指示器。指示器是随消息一起发送的信息片段，接收方可以用来确定密钥。

在早期，指示器只是密钥本身，隐藏在消息中。例如，消息的第三组是密钥，或者前 8 组的第一个字符组成了密钥。稍微复杂一点的版本可能是，第二组的中间数字告诉您哪一组是密钥。这些类型的指示器的明显问题是，一旦艾米丽学会了系统，她就可以阅读所有的消息。即使艾米丽不知道这个系统，她也可以简单地尝试消息中的所有组，看看其中是否有一个是密钥。如果她找到了一些这样的密钥，那么她可能就能推断出模式。

更安全的方法是加密密钥并将其用作指示器。这就是二战期间德国人使用 Enigma 机器所做的。他们有一个特殊的设置，每天更换一次，用于加密消息密钥。他们首先将 Enigma 设置为每日设置，并使用该设置加密消息密钥两次。然后他们将机器重置为消息密钥，个别操作员会随机选择，并加密消息。波兰的Bomba利用了消息密钥的双重加密来推断这些密钥。（bomba kryptologiczna是由波兰首席密码学家玛丽安·雷耶夫斯基于 1938 年设计的一种用于破解德国 Enigma 消息的电机械设备。）当德国人意识到这一点时，他们停止了这种做法，波兰人被封锁了；他们不再能读懂 Enigma 消息。艾伦·图灵预见了这个问题，并设计了他的Bombe来处理密码词，或者是可能的明文。法国的 Enigma 破译机也被称为 bombe，据说是以冻雪糕（一种类似于圆顶形的冰淇淋，像阿拉斯加烤冰淇淋）命名的。

第 14.2 节描述了从每日密钥生成消息密钥的几种方法。每种方法都使用一小组参数来生成每个消息密钥，例如滞后线性加法的系数，或者每日密钥中的位置。这些参数集合非常适合用作指示器。

14.4 Diffie-Hellman 密钥交换

关于传统方法就说这么多。让我们谈谈一个更现代的方法。Diffie-Hellman 密钥交换是由斯坦福大学教授马丁·赫尔曼和他的研究助理贝利·惠特菲尔德·迪菲于 1976 年发明的，后者后来成为 Sun Microsystems 的员工。公钥密码学的基本概念是由加州大学伯克利分校本科生拉尔夫·默克尔于 1974 年发明的。

Diffie-Hellman 密钥交换的关键特点是，即使 Emily 拦截了他们交换的所有消息，Sandra 和 Riva 也可以建立一个安全的加密密钥。为了设置交换，Sandra 和 Riva 必须就一个大素数 P 和该素数的一个原根 w 达成一致。或者，Sandra 可以简单地选择 P 和 w 并将它们发送给 Riva。P 和 w 可以明文发送。回想一下第 13.3 节，找到原根是很容易的。对于大多数素数，2、3、5 或 7 中至少有一个是原根。

Sandra 选择一个秘密指数 s，并计算 x = w^s mod P。她将数值 x 发送给 Riva，但保留 s 的数值。Riva 选择一个秘密指数 r，并计算 y = w^r mod P。她将数值 y 发送给 Sandra，但保留 r 的数值。现在 Sandra 可以计算 y^s mod P，即 w^(rs) mod P，而 Riva 可以计算 x^r mod P，即 w^(sr) mod P。由于 w^(rs) = w^(sr)，Sandra 和 Riva 计算出相同的数值，他们可以将其用作加密密钥，或者将其分割成几个加密密钥。在第 13.3 节中描述了执行指数运算的有效方法。

一些作者（以及维基百科）将 Diffie-Hellman 密钥交换描述为一种公钥方法。他们谈论结合 Sandra 和 Riva 的公钥及其私钥。这是不正确的。Diffie-Hellman 中没有涉及公钥。即使将指数 r 和 s 视为密钥，它们也都是秘密密钥。

假设 Emily 拦截了 Sandra 和 Riva 之间的所有消息。那么 Emily 知道 P、w、x 和 y，即 w^s mod P 和 w^r mod P，但她不知道 s、r 或 w^(rs) mod P。确定 w^(rs) mod P 被称为Diffie-Hellman 问题。目前尚不清楚这是否与确定 r 和 s 相同，但它们被认为是同样困难的问题。在给定 P、w 和 x 或 y 的情况下确定 s 和 r 被称为离散对数问题。这被认为是一个非常困难的问题。当 P、r 和 s 足够大时，这个问题被认为是计算上不可行的。专家们对 P 必须有多大存在分歧，但常见的建议是 300 和 600 位十进制数字。一些实现允许 P 达到 1234 位十进制数字，即 4096 位。指数 r 和 s 可以小得多。专家建议范围从 40 位十进制数字到 150 位十进制数字。

一个名为Silver-Pohlig-Hellman算法，以 Roland Silver、Stephen Pohlig 和 Martin Hellman 命名，使得在 P-1 只有小因子时解决离散对数问题变得容易。该算法让你可以分别解决每个小因子。因此，Sandra 必须确保 P 是一个安全素数，即 P-1 至少有一个大因子，比如 q > 10³⁵。理想情况下，Sandra 应选择 P 为形式为 2Q+1 的素数，其中 Q 也是素数。对应的素数 Q 被称为 Sophie Germain 素数，以法国数论家玛丽-索菲·杰尔曼（Marie-Sophie Germain）命名，她还研究过声学和弹性学。如果 Q-1 和 Q+1 都有大素因子，那就更强大了。在下一节中，我们将明确构造 Q，使得 Q-1 有一个大素因子。很可能 Q+1 也有一个大素因子，仅仅是因为 Q 太大了。只有小因子的数字被称为光滑数。随着数字变大，它们变得非常罕见。

*14.4.1 构造大素数，旧版

构建大素数的传统方法通常可以在许多网站上找到，它首先通过随机选择所需大小的奇数 N，然后测试 N 是否为素数。首先尝试几百个小素数。如果 N 可被其中任何一个整除，则 N 不是素数。重新选择。这种初步测试非常值得，因为它非常快速。接下来，通过应用概率素性测试来测试 N 是否为素数。最常见的测试是由加里·米勒和迈克尔·O·拉宾发明的Miller-Rabin测试。让 N-1 = 2^hd，其中 d 是奇数。也就是说，2^h 是能够整除 N-1 的最大 2 的幂。第一步是在范围 2 到 N-2 中选择一个基数 b，并测试 b^d≡1(mod N)是否成立。如果成立，则 N 通过测试。如果不成立，则查看 b^(2d)≡-1(mod N)是否成立，或者 b^(4d)≡-1(mod N)，依此类推。只要指数 2^gd 仍然小于 2^hd，就一直继续。如果找到这样一个值 g，则 N 通过了测试，b 被称为 N 的见证者。如果找不到这样的 g，则可以确定 N 不是素数，因此必须重新选择 N 的值。

如果 N 通过了测试，仍然有 1/4 的概率 N 是合数。如果你想将 N 不是素数的概率降低到 2¹²⁸的倒数 1，你将需要 64 次 Miller-Rabin 测试，每次都使用不同的底数 b。不幸的是，这仍然不能保证。Miller-Rabin 测试错误地将卡迈克尔数认定为素数。这些数字不是素数，但每个底数 b 都是证明数的见证者。这些数字是由伊利诺伊大学的罗伯特·卡迈克尔于 1910 年发现的。前几个卡迈克尔数是 561、1105、1729、2465、2821、6601、8911、10585、15841、29341 和 41041。卡迈克尔数倾向于有小的素数因子，因此通过 64 次 Miller-Rabin 测试，并且还发现 N 不可被前几百个素数中的任何一个整除，使得 N 是素数的可能性非常大。

这是一种寻找特定大小素数的好方法，但不能保证 N 是一个安全素数，并且比本节方法要慢得多。如果 S 是您需要的素数的大小，那么您需要找到一个素数的尝试次数大约是 ln(S)。因此，对于一个 500 位数的素数，您需要大约 ln(10⁵⁰⁰)或者大约 1151 次尝试，每次尝试需要 64 次 Miller-Rabin 测试和数百次试除。使用我在本节中提出的方法可以节省您几个小时甚至几个星期的计算机时间，这取决于您使用的计算机类型以及所需的素数的大小。

14.4.2 构建大素数，新的

你可以尝试找到一个大质数的一种方式是从任何大整数 N 开始，然后尝试 2N+1, 2N+3, 2N+5, … 测试每个直到找到一个质数为止。对此的一种小改进是测试 6N+1, 6N+5, 6N+7, 6N+11, 6N+13, … 。这样可以从测试中消除所有 2 和 3 的倍数。你也可以尝试 30N+1, 30N+7, 30N+11, 30N+13, … 来消除 2、3 和 5 的倍数，类似的方法还有 2×3×5×7 = 210，以此类推。

测试一个给定的整数 N 是否为质数有多种方法。最简单的方法是试除法。要测试 N 是否为质数，尝试将 N 每个小于等于 √N 的质数整除。如果其中任何一个质数能整除 N，则 N 是合数，否则 N 是质数。试除法适用于约 N = 10¹²，可能是 10¹⁴，但对于更大的 N，试除法耗时太长。大多数其他的质数测试只是概率测试，告诉你这个数可能是质数。

有一种测试可以确定一个数字是质数：如果一个大于 1 的整数 N 有一个原根，那么它就是质数。回顾第 13.3 节，如果 r^(N-1) mod N = 1，并且 r^((N-1)/p) mod N ≠ 1 对于任何能整除 N-1 的质数 p 都成立，那么 r 是 N 的原根。要测试 N 是否为质数，你只需要对于 N-1 的每个不同的质因数 p，分别计算 r^x mod N，其中 x = N-1 和 x = (N-1)/p。让我们称这种方法为原根质数测试，或者简称为根测试。这种方法是由法国数学家爱德华·卢卡斯在 1876 年发明的，同样是那个创造了斐波那契数（第 3.4 节）这个术语的爱德华·卢卡斯。卢卡斯于 1891 年因一场悲剧性的汤事故去世。

只需尝试 2、3、5、7、11 和 13 作为可能的原根即可。如果 N 有原根，那么至少这 6 个值中的一个很可能是原根。如果这些值中没有一个是原根，请不要浪费时间尝试其他值。更高效的方法是转到下一个质数的候选项。

Lucas 的根测试的问题在于你需要分解 N-1，如果 N 有 300 个或更多的数字，那么分解 N-1 实际上是不可能的，至少在没有量子计算机的情况下是不可能的。这就是为什么你在许多讨论质数测试的书籍或网站中不会看到这个测试被提及的原因。

有一种方法可以避开这个障碍。记住，你的目标不是找到一般的质数测试方法。你的目标是获得一个大质数来用作 Diffie-Hellman 密钥交换的模数。所以，与其找到那个质数，你可以构造出这个质数。

关键是选择具有已知因子的 N-1。例如，你可以选择 N-1 具有 2^n 的形式，因此 N 将具有 2^n+1 的形式。N-1 的唯一质因数将是 2。要找到形式为 2^n+1 的素数，你只需要找到一个数字 b，使得 b^(N-1) mod N = 1，且 b^((N-1)/2) mod N ≠ 1。我建议你尝试 b = 2、3、5、7、11 和 13。如果这些都不是原根，那么跳过 N = 2^n+1，看看 N = 2^(n+1)+1 是否为素数。这个搜索将获得你素数 3、5、17、257 和 65537。尽管人们花费了数千小时的计算机时间搜索，但目前尚不清楚是否还有其他素数。这 5 个素数被称为费马素数，以法国数学家皮埃尔·德·费马特命名，因为他著名的边注是关于方程 a^n+bn = c^n。

概述

在我详细介绍之前，让我概述一下构造一个大素数 P 的一般方法。该方法必须完成三件事：

1. P-1 必须具有一个大的素数因子，以便 P 是安全的，
   
2. 每个候选的 P 应该具有较高的素数概率，以便你需要尽可能少的质数测试，
   
3. P-1 应该具有较少的不同质因数，以便每个质数测试尽可能快速。
   

对于寻找大素数的任何搜索都将涉及测试数百甚至数千个候选者。让我们称预期测试次数为 E。这里的方法是使 P-1 的每个候选者成为两个数的乘积 cK。系数 c 将通过一系列相对较小的数字进行步进，通常与 E 相当。核 K 将是一个大素数、两个大素数的乘积或者最多 2 个质数的乘积的幂，p^aqb，其中至少有一个是大素数。让我们先看看如何选择系数，然后再看如何选择核心。

系数

最简单的选择系数的方法是逐个遍历质数。由于系数必须是偶数，你需要使用每个质数的两倍，2×2、2×3、2×5、2×7，等等。让我们称这个方法为PickPrimes。PickPrimes 最小化了 cK 中不同质因数的数量。c 中最多有 2 个不同的质因数，在 K 中也最多有 2 个不同的质因数。然而，PickPrimes 对减少所需的测试次数几乎没有什么帮助。

第二种选择系数的方法是使它们具有 p^aqb 或 p^aqbr^c 的形式，或类似的形式。这里的 p、q 和 r 是小的质数，如 2、3 和 5，或者 2、5 和 7。（在本节的后面我们将看到必须省略 3 的情况。）这样，P 就永远不可能是 2、3 或 5 的倍数，这显著增加了 P 是素数的机会。如果你使用这种方法，你可能想要预先计算并排序系数的列表。

核心

内核 K 必须至少有一个大素数因子 R。我建议 R 至少为 2¹²⁸，约为 3.4×10³⁸。如果你的对手拥有量子计算机，请将 R 至少设为 2²⁵⁶ = 1.16×10⁷⁷。那么，你从哪里获得这些素数呢？如果你愿意接受 30 位数的素数，你可以从 bigprimes.org 网站在线获取一些。

如果你期望生成许多大素数，或者非常大的素数，你可以自己生成。提前准备，建立一个各种大小素数的表。将此表命名为 PrimeTab。一定要保存 PrimeTab，这样每当你需要更多素数时，就不必重复此过程。你可以从小于 100 的 25 个素数开始你的素数表。你可能能够背诵这些，所以只需将它们输入程序中。接下来，如果你愿意，你可以使用试除法生成一些 3 到 12 位数的素数，比如每个尺寸 2 或 3 个素数。我建议你随机进行，这样每次使用此方法时都不会构造相同的素数（以及每个使用此方法的读者都不会生成相同的素数）。在这个阶段，PrimeTab 可能有大约 50 个素数。

构建 R（小步骤方法）

现在让我们开始尝试构造 R，即 Q-1 的大素数因子。你可以通过找到每个比上一个素数稍大一点的素数来逐步构建 R，也可以一次跳跃到那里。如果你期望生成许多大素数，请分步构建，以便 PrimeTab 后面可以有很多条目供以后使用。为了说明这两种技术，让我们以小步骤构造 R，并以一次巨大的飞跃构造 Q。

假设 PrimeTab 包含 k 个素数，p[1] < p[2] < p[3] < … < p[k]。要构造下一个素数，首先从表中选择任意两个素数，比如 p[i]和 p[j]。让 r 为乘积 p[i]p[j]。如果 r < p[k]，你可能希望选择更大的 i 或 j，以免生成太多小素数。当然，你需要一些小素数，所以我建议当 p[i]p[j] < p[k]^(2/3)时选择更大的 i 或 j。首先，使用 Lucas 测试来确定 R = 2r+1 是否为素数。这很容易，因为你知道 R-1 的唯一素因子是 2、p[i]和 p[j]。如果 2r+1 不是素数，请尝试 4r+1、6r+1、10r+1 等，使用 PickPrimes 方法选择系数。当数字开始超过 20 位数时，找到一个素数可能需要每个素数 50 次或更多的尝试。

减少测试次数

当数字变得非常大时，你可以通过检查每个候选数 nr+1 是否可被许多小素数整除来节省时间，然后再寻找一个原根。例如，你可以验证 nr+1 是否不能被前 100 个素数中的任何一个整除。你可以通过提前计算 x[i] = r mod p[i]来使这个测试更快，其中 i 是前 100 个素数。然后，不是计算(nr+1) mod p[i]，其中 r 可能有几百位数，而是计算(nx[i]+1) mod p[i]，其中 x[i]只有 1 到 3 位数。也就是说，你只需进行一次试除（r mod p[i]），而不是对每个 n 值都进行一次。我们称这种方法为PrimeCheck。

PrimeCheck之所以有效是因为候选素数是按顺序选择的。你无法用传统方法找到大素数，因为候选素数是随机选择的。这使得对小素数的试除对这种方法更快，而且由于速度更快，你可以使用更多的小素数，比如 300 个而不是 100 个，从而减少所需的试验次数。

如前所述，如果 2、3、5、7、11 或 13 中没有一个是 nr+1 的原根，则跳过该候选数，并尝试下一个 n 值，直到找到下一个素数。由于这种方法每个候选数只使用 6 次测试，而传统方法使用 64 次测试，因此这种方法的速度是传统方法的 10 倍以上。将找到的每个素数添加到PrimeTab中。

构建 P 和 Q（巨大飞跃方法）

假设你的目标是找到一个 300 位的Sophie Germain素数。继续扩展PrimeTab，直到它至少有一个大素数，比如 R > 2¹²⁸。现在你已经准备好使用巨大的飞跃来生成你的 300 位素数。首先选择一个所需大小的目标 T，比如 T = 10³⁰⁰。可以使 P 任意接近目标值，但这对 Diffie-Hellman 密钥交换并不需要。T 只是一个所需的最小尺寸。

下一步是找到 Q。记住 Q 必须满足三个要求：Q 必须是素数，Q-1 必须是大素数 R 的倍数，且 P = 2Q+1 也必须是素数。找到 Q 的策略是从一些所有质因数都已知的种子数 t 开始，然后使用PickPrimes尝试 2t+1、4t+1、6t+1、10t+1 等。

警告：如果你让 t 成为 3 的倍数，那么 Q 将具有 3x+1 的形式。这意味着 P = 2Q+1 = 6x+3 将是 3 的倍数。让 t 成为 3 的倍数意味着 P 永远不可能是素数。

由于 T 是 P 的最小值，而 Q 约为 P/2，因此 t 应约为 T/2。要构造 t，从 PrimeTab 中最大的素数 R 开始。取小于 T/2 的最大 R 的幂，称为 R^r。例如，如果 T 为 10³⁰⁰，而 R 约为 10⁴⁰，那么 T/2 约为 5×10²⁹⁹，所以 r 为 7。这意味着 R^r 约为 10²⁸⁰。直接从 10⁴⁰跳到 10²⁸⁰是巨大的飞跃。这个 R^r 远远低于 5×10²⁹⁹，所以设定 t = R⁷S，其中 S 约为 5×10¹⁹。当 S < 10¹²时，您可以使用试除法找到大于 S 的下一个素数。如果这是 S’，那么 t 就是 R⁷S’。当 S > 10¹²时，您可以将 S’设置为 PrimeTab 中的一个素数和您必须选择的小于 10¹²的素数的乘积，或者您可以将 S’设置为素数的平方或立方。假设后者。在这个例子中，S 约为 5×10¹⁹。它的平方根约为 7,071,067,812。下一个更高的素数是 U = 7,071,067,851。因此，t 将是 R⁷U²。

现在你已经构建了 t，并且知道了它的所有素数因子，你可以开始搜索 Q，通过使用根测试测试 2t+1、4t+1、6t+1、10t+1 等。随机选择的数字 N 成为素数的概率约为 1/ln(N)。当 N 的数量级为 10³⁰⁰时，ln(N)约为 690。这意味着大约需要 690 次尝试才能找到 nt+1 形式的素数。P 也必须是素数，这也有约为 1/690 的概率。这意味着大约需要 690² = 476100 次尝试才能找到 Q = nt+1 和 P = 2Q+1，它们都是素数。这是很多次测试。

这些测试非常耗时，因此任何减少测试次数的技术都是宝贵的。在这种情况下，我们可以使用 PrimeCheck 的自然扩展。对于每个素数 p[i]，像之前一样计算 x[i] = t mod p[i]。对于每个 n 值，检查 nx[i]+1 是否能被 p[i]整除，以验证 Q 不是 p[i]的倍数，并且还要检查 2(nx[i]+1)+1，即 2nx[i]+3 是否能被 p[i]整除，以验证 P 不是 p[i]的倍数。这样你就可以从 x[i]列表中获得双倍价值。

秘密素数

对于一些密码，您可能需要使用一个只有您自己和您的合法通信者知道的秘密素数。您仍然可以使用本节的方法构造您的素数，但是，您需要确保任何对手都无法按照相同的步骤发现您的素数。我建议两项预防措施。（1）当您初始化 PrimeTab 时，不要选择 3 到 12 位数字大小的 2 或 3 个素数，而是随机选择 3 到 14 位数字大小的 5 到 10 个素数。目标是在 PrimeTab 中至少有 100 个初始素数。（2）使用构造 P、Q 和 R 的小步方法，最好在初始素数之外使用至少 100 个额外步骤。

精确大小

构建质数的巨大飞跃方法可以轻松修改为找到精确大小的质数。这是一个例子。假设您需要在 10³⁰⁰ 和 1.1×10³⁰⁰ 之间的质数。选择比 10³⁰⁰/2000000 稍大的 r，即 5×10²⁹⁴。使用 PickPrimes，但从 1000000 开始您的质数，即 1000003、1000033、1000037、1000039，依此类推。使用 PrimeCheck 来减少测试次数。

在 1,000,000 和 1,100,000 之间大约有 6700 个质数，在 10³⁰⁰ 和 1.1×10³⁰⁰ 之间的每 690 个数字中，大约有 1 个是质数，因此几乎可以肯定您会找到所需大小的质数。概率可以很容易地计算出来。在所需范围内的任何给定数字不是质数的几率是 689/690。所有 6700 个选择的数字都不是质数的几率是 (689/690)⁶⁷⁰⁰，或者是 0.00006。因此成功的机会是 99.994%。

第十五章：矩阵方法

本章涵盖

• 使用整数矩阵乘法或环元素矩阵的加密
  
• 使用大整数和小整数的加密
  
• 解线性同余方程
  
• 构造环和可逆矩阵
  

矩阵是一种非常适合用于密码学的工具，因为它们可以在一次操作中对任意大的文本块进行加密。通常，消息中的每个块都被视为字节向量，意味着模 256 的整数。

当桑德拉使用矩阵来加密消息时，瑞娃必须使用该矩阵的逆矩阵来解密消息。让我们从讨论矩阵方法的技术开始，这是一种求逆矩阵的技巧。

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