wiki.osdev.org 系列之 - Random Number Generator

type

status

slug

summary

Entropy（熵）

计算机是确定性设备。如果程序相同，所有输入都相同，那么每次都会计算出相同的结果。那么，计算机如何生成随机数呢？计算机不能，但它周围的物理世界可以。许多物理事件在某种程度上是随机的，或者更专业地说，具有一定程度的熵。即使在地球上最好的屏蔽录音室中，录音也会包含一定程度的噪音。人们在键盘上打字的时间不一致，并键入准随机文本，例如您当前正在阅读的文章。甚至其他计算机也可以提供熵：虽然大多数网络流量完全是机器生成的，但网络数据包的确切相对时间最终源自按下电源按钮的那一刻，这是另一个人为操作。因此，输入事件的时间和性质可以为我们提供一些熵。

2 Types of random number generators（随机数发生器的类型）

随机数生成器有多种划分方式；一种方式是数字的生成方式，另一种方式是数字的使用方式。这是很重要的区别：前者可能会影响您设计操作系统的方式，而后者可能会影响或破坏系统的安全性。

2.1 Sources of random numbers（随机数的来源）

有两种随机数：“真”随机和伪随机。

对于“真正的”随机数生成，系统会连续测量一组预期为随机的事件。这可以是从宇宙辐射和原子衰变到用户输入时间和时钟抖动的任何事物。测量结果被去偏并“搅拌”到熵池中，可以从中提取随机数。

伪随机数由算法 (PRNG) 生成，该算法转换某些内部状态并根据请求计算输出值。可以设置初始种子，但之后的下一个状态仅取决于前一个状态。有许多不同的 PRNG，下面将讨论其中的一些。

可以使用一些“真”随机数来为伪随机生成器的状态播种，但这并不能使 PRNG“真正随机”。根据确切的算法，预测所有下一个输出可能是微不足道的，只要给定一个先前的输出。正如下一节所讨论的，这可能会产生严重的影响。

2.2 Applications of random numbers（随机数的应用）

随机数大致可以分为两种应用场景：密码学方面和其他使用场景。

为了理解下一节，我们首先应该回顾一下随机数生成器对于密码安全性的意义。密码学家将安全性分为两种类型：信息论安全性和计算安全性。两者中的前者是更有力的主张。如果密码系统在信息理论上是安全的，则攻击者在没有密钥的情况下无法说出关于加密消息中的任何东西。这种密码系统很少见。由于攻击者不能说出 任何内容 ，因此必须隐藏所有内容，包括模式、时间甚至长度。怎么做才能把消息的长度隐藏掉？唯一的选择是根本不发送消息，这违背了密码系统的目的。或者发送无限长的消息，但是这样的话，一旦你开始发送，就永远无法停止。

这就是为什么计算安全性较弱但更实用的原因：在给定一些合理的计算能力的情况下，密文必须很难找到。选择此限制是希望在未来几十年内不会达到该限制。这也允许用户“泄露”一些关于密文的信息（例如长度），但必须保证找到原始输入仍然非常困难。这些系统通常使用一些除非知道密钥否则难以求解的操作，例如分解非常大的素数。很明显，密钥必须是不可预测的：如果对手知道下一个输出是什么，他们将能够很容易对密钥进行猜测，直到找到正确的密钥。

“真”随机数是加密安全中随机性的最佳来源，但是很难建立一个大型、快速补充的其中每个来源都完全去偏并且不受其他来源的影响熵池。可以使用加密安全随机数生成器 (CSPRNG)，以一种难以逆转的方式“拉伸”熵。CSPRNGs guarantee that it is computationally difficult to guess the next output having seen previous results, and, if the generator's state is known, which values preceded the known outputs. CSPRNG 保证在已经看到以前的结果的前提下，在计算上依旧很难猜测下一个输出，如果生成器的状态是已知的，那么在已知输出之前的值是什么。~~（有点不会翻译）~~

3 True random number generators（真随机数发生器）

真随机数生成器使用物理设备或现象来生成随机数，其不可预测性可以追溯到量子力学定律。

3.1 x86 RDSEED 指令

较新的 x86 和 x86-64 处理器具有用于生成随机数的指令 RDSEED。要使用 RDSEED，您首先需要检查指令是否可用。

如果 EBX 设置为 1（或 ZF 未设置），则该指令可用。然后它可用于生成 16/32/64 位随机数（取决于用作参数的寄存器大小）。如果生成了随机数，则设置进位标志。

是否信任 RDSEED 取决于您和您的用户。因为它是在硬件中实现的，所以它实际上是一个黑箱，可能包含各种错误，或者更糟的是，后门。

3.2 Dedicated hardware（专用硬件模块）

存在专用于生成“真实”随机数的设备。这些范围从消费级 TPM 到 PCIe“加密加速器”。这些是 RDSEED/RDRAND 的泛化，缺点是您需要额外的驱动程序才能与设备交互，并且用户可能没有安装此类设备。

TPM，或可信平台模块，是可以安装在现代主板上的小型协处理器。除了随机数生成，它们还提供其他可信的计算服务。值得一提的是，Windows 11需要TPM。它们也可以在 CPU 上进行仿真模拟 (例如，Intel PTT 或AMD fTPM )。与 RDSEED 一样，后门可能是一个问题。

3.3 Sampling manually（手动采样）

在运行的系统中，有许多进程实际上是随机发生的。考虑一下每秒到达的所有不同的中断:精度为百万分之一的计时器、外设I/O、用户与整个系统的交互等等。

挑战在于寻找可靠随机且难以从外部影响和观察的来源(矛盾的是)。对于这些来源中的每一个，必须估计它们贡献了多少熵。测量将各自的熵量添加到池中，而读取则减少熵。

因为您可以完全控制这种生成方法，所以还可以合并硬件生成器生成的值。你可以自己决定这几代的熵是多少，甚至是0比特。

当使用时间作为熵源时，读取的时间戳应该尽可能精确。TSC在这方面工作得很好。测量从该操作中获得的熵需要了解事件发生的时间窗口和TSC的滴答率。例如，如果 TSC 的频率为 3 GHz，事件发生的窗口为10ms，那么 TSC 读取值可以是 3000 万个值中的任意一个，这意味着从中获得的熵约为 24.8 位。如果 TSC 较慢，只有 1 GHz，那么熵将只有约 23.2 位。

3.3.1 Adversarial entropy（对抗熵）

如果对手能够以某种方式观察到熵池的状态，并将自己的熵贡献到熵池中，那么他们就有可能以这种方式提供熵，从而迫使熵池进入较低的熵状态。一个简单的例子是一个熵源定期检查池中的某个位是否被设置，然后提供熵，直到它被清除。这样，在大多数情况下，给定的位是明确的，并且熵缓冲区可以处于的可能状态的数量减半。DJB的博客 https://blog.cr.yp.to/20140205-entropy.html 上描述了一种更复杂的攻击。

4 Cryptographically secure pseudorandom number generators（加密安全的伪随机数生成器）

现在关注一些 CSPRNG。重要的是要记住，与所有密码学一样，如果您计划实际使用它，最好不要自行编写它。出错的方式有很多种，算法越复杂，出错的几率就越大。当然，对于业余爱好来说，这是完全没问题的；只是不要使用您手工制作的 TLS 密钥源进行网上银行业务。

4.1 x86 RDRAND Instruction（x86 RDRAND 指令）

RDRAND 比 RDSEED 稍微老一点，并提供（英特尔声称的）CSPRNG。它的存在由 CPUID 叶 1，ECX 位 30 指示：

如果 ECX 设置为 1（或 ZF 未设置），则该指令可用。用法与 RDSEED 相同：

它由 RDSEED 从中读取的相同熵源自动播种，不能手动播种。因此，它受到与 RDSEED 相同的警告。

4.2 Ciphers（密码）

通过播种安全密码（例如 ChaCha20 和 AES）并运行多个循环来构建 CSPRNG 是相当常见的，在该循环中输出与运行计数器一起被重新加密。每隔一段时间，就会创建一个新密钥，可能涉及另一个安全的随机源。

编写（和后门）基于 ChaCha20 的 CSPRNG 可能是一篇关于该主题的一篇有趣的文章，以及它如何以令人惊讶的方式出错。

5 Pseudorandom number generators（伪随机数生成器）

接下来是各种常规的 PRNG。这些产品在质量、简单性和速度的各个方面都有所不同。仔细阅读每个解释！

5.1 The Standard's Example

直接取自 C 标准文档（第 347 页）：

这是一个相当标准但平庸的线性同余发生器(LCG)。它返回15个随机比特。

它基于这个递归公式

其中模数 m 是 LCG 可以产生的随机值的最大数量。对于 C 标准中的示例，a = 1103515245、c = 12345 和 m = 232（隐式）。 LCG 的质量在很大程度上取决于这些值，并且很难找到好的值。维基百科有一个常用参数列表。

5.2 Fibonacci random number（斐波那契随机数）

斐波那契数列的特殊“重制”可用于生成随机数。这是通过 4 个“种子”来实现的，这些种子一开始都是非常奇怪的值（例如 45、80、22、32）。 seed() 函数将一个新种子添加到序列的末尾，并删除第一个种子（种子称为 A、B、C 和 D）。 rand() 函数只返回种子的总和，并用结果调用 seed() 。 Glidix 就是这种 RNG 实现的一个很好的例子。

5.3 Linear Feedback Shift Register（线性反馈移位寄存器）

给定一个非零种子，线性反馈移位寄存器 (LFSR) 是一种生成非常长的随机数序列的简单方法。思路如下：一个 n 位的 LFSR 有 n 位（0 或 1）。最初，被一个 n 位的种子填充。对于每个下一个要生成的值，从寄存器中“挖掘”某些位并，将它们异或在一起。将生成的二进制值送入最左边的位，将所有位向右移动一位。从最右侧移出 LFSR 的位是生成的随机位。

LFSR 可以产生的位序列最终会重复，但通过仔细选择异或的位，LFSR 的周期可以增加到 2n - 1 位。这意味着在 2n - 1 位序列之后，将返回相同的序列。然而，这是所有伪随机数生成器都具有的一个特性：在不改变种子的情况下，它们最终会重复自己。

下面是一个使用位 11、13、14 和 16 异或运算在一起作为输入的 16 位 LFSR 的示例。这个 LFSR 的周期是 65535 位，所以它会在序列重复之前生成一个 65535 位的伪随机序列。 LFSR 产生的下一位为 1（第 16 位的值），下一个输入位为 0。

更大（和更小）的 LFSR 也是可能的。聪明的人已经推导出多项式，可以确保给定任何非零输入，LFSR 的周期尽可能大 (2n - 1)。这样的多项式写为。对于这个的多项式例子，位 16、14、13 和 11 必须一起异或并作为输入提供，从左边开始计数，从 1 开始。其他 n 值的多项式可以在维基百科和本 PDF 文档的第 5 页上找到。

请注意，种子绝不能为零。这也意味着永远不可能所有寄存器的位值为零，并且在种可能的寄存器组合中，不允许出现全零状态。因此，个状态是可能的最大值。

5.4 Wichmann-Hill（威治曼山）

1982 年，Brian Wichmann 和 David Hill 提出将三个线性同余生成器组合起来，然后将结果归一化并求和，以得到一个在 0 到 1 之间均匀分布的数。一个常见的例子是：

已知此版本的周期约为 7 万亿（30268、30306 和 30322 的最小公倍数）。

5.5 Mersenne Twister（梅森龙卷风）

Mersenne Twister 是一种非常受欢迎的 PRNG，可在大多数平台上使用；例如，它是 C++11 标准库所需的生成器集的一部分。 64位MT-19937版本的C语言实现如下：

根据维基百科实现：

一些实现会自动使用种子 5489 为生成器播种，但这将（显然）在每次初始化时产生相同的输出。

它优于上面列出的所有 PRNG，但由于其较大的状态大小，速度相当慢。它在某些统计领域也存在问题。请参阅“现在是我们放弃 Mersenne Twister 的时候了”。

5.6 PCG family（PCG家族）

PCG 系列是 PRNG 领域中相对较新的成员。最简单的版本使用带有置换运算符的 LCG 来打乱输出。它被设计成通过尽可能多的统计测试，同时仍然保持小而快速。有一篇描述生成器的综合论文，并且提供了 Apache 2.0 许可代码：https://www.pcg-random.org/download.html。

请注意，该站点声称 PCG 的输出比其他 PRNG 的输出更难预测，这意味着 PCG 更安全。仅在三个输出后就可以预测某些生成器，因此不应将其视为“难以破解”，也绝对不是“更安全”。非加密安全 PRNG 的可预测性通常不是问题。

5.7 xoshiro family

与 PCG 一样，xoshiro 和相关的 xoroshiro 系列是相当新的 PRNG。

5.8 Rolling your own

如果您仍然不满意，您可能想要构建自己的 PRNG。您可以通过编写一些看起来不错的东西并将其置于自动统计测试套件（例如 TestU01 的 SmallCrush、Crush 和最后的 BigCrush）中，以一种相当反复试验的方式来做到这一点。这些测试非常容易运行，可以快速指出问题，例如：

SmallCrush 将报告此生成器未通过 15 次统计测试中的 12 次。因此，其他测试也慢得多，因此没有必要。