随机数生成器的 5 个等级

去年夏天，我开始对随机数生成器产生了一些痴迷。我研究并实现了各种生成器，以及用于确定生成器产生的随机性统计质量的测试。我计划在接下来的几周内上传大部分代码，但现在，我想先讨论一些理论。

我在研究过程中注意到的一件事是，存在多种分类 RNG 的方法。

• 分布（均匀分布、高斯分布等）
• 过程（线性同余、乘同余等）
• 用途（物理模拟、密码学、游戏等）

然而，在我看来，你也可以将 RNG 组织成一个层次结构。显然，有些 RNG 比其他的更好。某些算法产生的序列比其他算法质量更好，而硬件随机数生成器（虽然并非总是实用或必需）几乎总是比软件更好。

因此，我想花点时间来介绍一个对我来说用于对各种 RNG 进行排名的系统，我希望你们也能很好地利用它。

随机数生成器的层次结构

1^级 - 低质量

产生低质量随机数的生成器。这些通常用于只需要输出之间存在一些差异，而不太关注这些数字的质量。通常，标准库中的生成器属于此类。这些生成器通常用于调试目的，并且往往速度快且易于实现。

示例：几乎任何标准库中的 RNG。从 C 到 Java，几乎所有都是低质量的。线性同余生成器。

2^级 - 中等质量

这些是产生局部随机性好的序列的生成器，但它们的整个周期并没有显示出适当的质量。简而言之，它们通过标准测试，对于一个短序列，例如 1,000 – 10,000,000 字节，你可能无法将其与真正随机数生成器产生的序列区分开来，但对于更长的序列，或者进行更广泛的测试，它们就会失败。

示例：这实际上很常见。大多数乔治·马萨格利亚 (George Marsaglia) 的生成器也符合条件。

3^级 - 高质量

产生与真正随机序列几乎无法区分的随机数的生成器。它们的周期足够大，以至于在所有实际应用中都不会重复。它们通过标准测试以及更广泛和更详细的统计测试。

示例：梅森旋转算法、Well Equidistributed Long-Period Linear（WELP）

4^级 - 密码学安全

这些是高质量的 RNG，它们也被设计为能够抵抗攻击。流密码应该属于这一级别。我非常清楚，在构建随机数生成器时，必须考虑多个方面才能使其安全，但目前，我想缩小我的关注范围。

1. 使用密码学安全的 RNG，使用当代技术在对生成器进行破解的时间框架内，使其变得不可行。
2. “破解”生成器意味着仅根据生成器的输出以及了解产生输出的算法来恢复内部状态。
3. 如果内部状态受到破坏，那么使用当前状态生成生成器的先前输出也应该变得不可行。

示例：Fortuna, Blum Blum Shub, AES（使用 CTR 和 OFB 模式）

请注意，此定义并未考虑熵池或收集熵。同样，在设计实用且安全的 RNG 时，必须考虑许多方面。

5^级 - 真随机数生成器

也称为硬件 RNG，这些生成器从物理来源获取其输出。这可以是任意数量的来源，例如辐射、大气噪声、熔岩灯、量子过程、摄像头/音频噪声等。

示例：Random.org（大气噪声），HotBits（辐射），LavaRnd（摄像头噪声）

我想提出的几点

1. 这是一个层次结构，而不是一个分类。每个等级之间的区别在于程度，而不是类型。所有真随机数生成器都是密码学安全 RNG，但反之则不然。所有密码学安全 RNG 都是高质量 RNG，但同样，反之亦然。
2. 我根据它们的不确定性对它们进行排名，不确定性是其输出质量和理解创建输出的过程所需的难度的结合。
3. 所有 RNG 都是有罪的，直到被证明是无辜的。你不能简单地创建一个 RNG 然后说它是高质量的。你必须对其进行测试以确定其质量。同样，你不能简单地构建一个硬件生成器并说它是一个真随机数生成器。它是否产生高质量的输出？是否可以预测下一个输出？在它们经过测试之前，所有 RNG 都是 1^级。它们必须被证明值得更高的排名。

我希望你们都觉得这很有趣。请让我知道你的想法。

谢谢，
Jacob W.