3.4 我们的 RNG

8 分钟阅读

原文链接: https://rust-random.github.io/book/guide-rngs.html

RNG 种类很多，各有权衡。Rand 在 [rngs 模块]中提供了一些便捷的生成器。通常可以直接使用 rand::rng，该函数会在线程局部内存中自动初始化 RNG 并返回其引用。它快速、质量高，且（据我们所知）密码学安全。

本文档内容：

生成器
性能与大小
质量与周期长度
安全性
额外特性
延伸阅读

生成器

基础伪随机数生成器（PRNG）

「标准」非密码学 PRNG 的目标通常是在简单性、质量、内存占用与性能之间取得良好平衡。非密码学生成器早于密码学生成器，在某些方面已被后者取代，但非密码学生成器仍有优势：状态小、初始化快、简单、嵌入式 CPU 能耗低。（但并非所有非密码学 PRNG 都具备这些优点，例如 Mersenne Twister 虽易预测但状态很大。）

这些算法对蒙特卡洛模拟非常重要，也适用于随机化算法、游戏等可预测性不成问题的场景。（但赌博类游戏中可预测性可能是问题，建议使用密码学 PRNG。）

Rand 项目提供多种非密码学 PRNG。下面汇总其中一部分。可参考 pcg-random 和 xoshiro 网站。

name	full name	performance	memory	quality	period	features
`SmallRng`	(unspecified)	fast	small	★★★☆☆	≥ `u32` * 2⁶⁴	not portable
`Pcg32`	PCG XSH RR 64/32 (LCG)	5 GB/s	16 bytes	★★★☆☆	`u32` * 2⁶⁴	jump-ahead
`Pcg64`	PCG XSL 128/64 (LCG)	7 GB/s	32 bytes	★★★☆☆	`u64` * 2¹²⁸	jump-ahead
`Pcg64Mcg`	PCG XSL 128/64 (MCG)	8 GB/s	16 bytes	★★★☆☆	`u64` * 2¹²⁶	jump-ahead
`XorShiftRng`	Xorshift 32/128	7 GB/s	16 bytes	★☆☆☆☆	`u32` * 2¹²⁸ - 1	—
`Xoshiro256PlusPlus`	Xoshiro256++	11 GB/s	32 bytes	★★★☆☆	`u64` * 2²⁵⁶ - 1	jump-ahead
`Xoshiro256Plus`	Xoshiro256+	13 GB/s	32 bytes	★★☆☆☆	`u64` * 2²⁵⁶ - 1	jump-ahead
`SplitMix64`	splitmix64	13 GB/s	8 bytes	★☆☆☆☆	`u64` * 2⁶⁴	—
`StepRng`	counter	35 GB/s	16 bytes	☆☆☆☆☆	`u64` * 2⁶⁴	—

此处性能大致以 AMD Ryzen 9 9950X3D 上 u64 输出为基准（注意会因应用差异很大；一般而言密码学 RNG 在字节序列输出上表现更好）。质量评级基于理论与可观测缺陷，大致如下：

★☆☆☆☆ = 适用于简单应用但有明显缺陷
★★☆☆☆ = 定性测试中无重大问题
★★★☆☆ = 理论良好，定性测试中无重大问题
★★★★★ = 密码学质量

密码学安全伪随机数生成器（CSPRNG）

CSPRNG 的要求远高于基础 PRNG。首要考虑是安全性。性能与简单性也重要，但总体而言 CSPRNG 比普通 PRNG 更复杂、更慢。质量不再是关注点，因为 CSPRNG 要求输出与真随机性基本无法区分，任何偏倚或相关性都会使输出更可预测。

CSPRNG 与密码学密码密切相关。任何分组密码都可以通过加密计数器变成 CSPRNG。流密码本质上是 CSPRNG 与组合运算（通常是 XOR）。因此我们可以轻松将任何流密码用作 CSPRNG。

本库提供以下 CSPRNG。我们无法对任何安全声明提供保证。下表省略了上一表的「质量」列，因为 CSPRNG 可能不存在可观测缺陷。

name	full name	performance	initialization	memory	security (predictability)	forward secrecy
`StdRng`	(unspecified)	fast	fast	(unspecified)	widely trusted	no
`ChaCha20Rng`	ChaCha20	2.6 GB/s	fast	320 bytes¹	rigorously analysed	no
`ChaCha12Rng`	ChaCha12	4.1 GB/s	fast	320 bytes¹	large security margin	no
`ChaCha8Rng`	ChaCha8	5.8 GB/s	fast	320 bytes¹	sufficient security margin	no
`Hc128Rng`	HC-128	4.6 GB/s	slow	4176 bytes	recommended by eSTREAM	no
`IsaacRng`	ISAAC	2.1 GB/s	slow	2072 bytes	unknown	unknown
`Isaac64Rng`	ISAAC-64	3.7 GB/s	slow	4136 bytes	unknown	unknown

应注意，ISAAC 生成器仅因历史原因保留：自 Rust 语言诞生之初就存在。输出质量良好且尚无已知攻击，但受到密码学专家关注较少。

关于生成器的说明

性能

首先要说明，大多数 PRNG 都很快，很少会成为性能瓶颈。

基础 PRNG 的性能较为微妙。它很大程度上取决于 CPU 架构（32 位与 64 位）、内联，以及可用寄存器数量。周围代码常因内联和其他寄存器使用而影响性能。

为性能选择 PRNG 时，务必在自己的应用中做基准测试，因为 PRNG 与周围代码的交互、CPU 架构依赖以及请求数据大小的影响都很重要。因此我们不在此给出性能数字，仅提供定性评级。

CSPRNG 略有不同：它们通常在缓存中生成一块输出，再从缓存中取用。这使它们具有良好的摊销性能，并减少或完全消除周围代码对 CSPRNG 性能的影响。

最坏情况性能

简单 PRNG 通常按需产生每个随机值。相比之下，CSPRNG 通常一次生成整块，再从缓存读取直至耗尽，因此在抽取少量随机数据时性能一致性较差。

内存占用

简单 PRNG 通常内存占用很小，一般只需几个字，字通常是 u32 或 u64。但并非所有非密码学 PRNG 都如此，例如历史上流行的 Mersenne Twister MT19937 算法需要 2.5 kB 状态。

CSPRNG 通常需要更多内存；由于建议种子大小至少 192 位，算法可能还需要更多，256 位大约是安全的最小尺寸。实践中 CSPRNG 往往使用更多，ChaCha20Rng 相对较小，状态为 136 字节。

初始化时间

初始化新生成器所需时间差异很大。许多简单 PRNG 甚至部分密码学生成器（包括 ChaCha20Rng）只需将种子值和若干常量复制到状态中，因此可非常快速构造。相比之下，状态很大的 CSPRNG 需要昂贵的密钥扩展。

质量

许多基础 PRNG 不过是几次位运算和算术运算。简单性带来良好性能，也意味着生成的随机数流中隐藏着小的规律性。

这些隐藏的规律性有多重要？很难说，取决于 RNG 的用法。若随机数与所用算法之间存在相关性，结果可能错误或误导。

若 RNG 在尽可能多的应用中给出正确结果，则可视为良好。PRNG 算法的质量可在一定程度上通过分析评估，以确定周期长度并排除部分相关性。还有旨在测试 PRNG 在广泛可能用途上表现的经验测试套件，最新且最完整的是 TestU01 和 PractRand。

CSPRNG 往往更复杂，并明确要求不可预测。这意味着输出值之间不得有明显相关性。

质量星级：

三星及以上的 PRNG 对大多数非密码学应用应已足够。一星或二星可能对典型应用和游戏足够，但并非对所有算法都适用。

周期

PRNG 的周期或循环长度是指生成多少值后开始重复同一随机数流。许多 PRNG 有固定大小周期，而对其他（「混沌 RNG」）周期可能取决于种子，且可能存在短周期。

注意长周期并不意味着高质量（例如对 u128 值计数可提供相当长的周期）。反之，短周期可能是问题，尤其在同时使用多个 RNG 时。一般而言，我们建议周期至少为 2¹²⁸。（或者，周期至少 2⁶⁴ 且支持多流的 PRNG 可能足够。但请注意 PCG 的流之间高度相关。）

避免重复使用值！ 在当今硬件上，周期仅为 2⁶⁴ 的快速 RNG 顺序使用数百年才会循环。但当多个 RNG 并行使用（各有唯一种子）时，生成序列重叠的概率显著。对周期很大的生成器 P，n 个独立生成器各生成长度 L 的序列，当 nL / P 接近零时，序列重叠概率可近似为 Ln² / P。更多内容请参阅 Xoshiro 作者的这些说明。

碰撞与生日悖论！ 对输出大小与状态大小相等的生成器，建议不要使用超过 √P 个输出。对 kw 位状态和 w 位输出的推广是确保 kL² < P。该要求来自广义生日问题：从大小为 d = 2^w 的集合中抽取多少无偏样本，重复概率至少为一半。注意对 kL² > P，具有 kw 维等分布的生成器无法产生预期数量的重复样本，但没有该性质的生成器也不保证产生预期数量的重复。

安全性

可预测性

对任何 PRNG，都可以问：给定 PRNG 的某些先前输出，能否预测下一个输出值？ 在可能存在对手的情况下，这是重要性质。

普通 PRNG 往往可预测，尽管难度各异。有些情况下预测轻而易举，例如纯 Xorshift 在不改变状态的情况下输出部分状态，预测只需用四个 u32 输出为新的 Xorshift 生成器播种。其他生成器如 PCG 和截断 Xorshift* 更难预测，但并非超出常见数学和台式 PC 的能力。

CSPRNG 必须提供的基本安全性是预测输出的不可行性。该要求形式化为[下一比特测试]；大致表述为：给定随机序列的前 k 位，若不存在能以合理计算能力预测下一位的算法，则序列满足下一比特测试。

部分 CSPRNG 还提供前向保密：若 CSPRNG 状态在某时刻泄露，必须无法重建先前状态或输出。注意许多 CSPRNG 在通常形式化中没有前向保密。

验证算法的安全声明是困难问题，我们无法对本项目使用或推荐的算法的安全性提供任何保证。请参阅 NIST 和 ECRYPT 的建议。

状态与播种

值得注意的是，CSPRNG 的安全性完全依赖于使用安全随机密钥播种。若密钥已知或可猜测，CSPRNG 的所有输出都易于猜测。这意味着种子应来自可信来源；通常是操作系统或另一个 CSPRNG。为此我们建议使用 getrandom crate，它对接操作系统的安全随机接口。或者，使用用户空间 CSPRNG 如 rand::make_rng() 或 ThreadRng 播种应已足够。代码示例：

1
2
3
4
5
6
7
use rand::{rngs::ChaCha12Rng, rngs::SysRng, SeedableRng};

/// 显式从 SysRng 播种：
let mut rng1 = ChaCha12Rng::try_from_rng(&mut SysRng).unwrap();

/// 从 ThreadRng 播种（若 ThreadRng 不可用则从 SysRng）：
let mut rng2: ChaCha12Rng = rand::make_rng();

此外，CSPRNG 的内部状态显然必须保密。为此，我们的实现不直接暴露大部分内部状态，Debug 实现也不打印任何内部状态。这并不能完全保护 CSPRNG 状态；同一进程内的代码可能读取该内存（为方便起见我们允许克隆和序列化 CSPRNG）。此外，运行中的进程可能被操作系统 fork，使两个进程拥有同一生成器的副本。

不是密码学库

加密和认证等密码学过程复杂，必须非常谨慎地实现以避免缺陷并抵御已知攻击。因此建议尽可能使用专用库，例如 openssl、ring 和 RustCrypto libraries。

Rand crate 试图在有限条件下提供不可预测的数据源。首先，软件按「原样」提供，无任何形式的保证。其次，通常假设程序内存是私有的；若对此有顾虑，可能更倾向使用外部生成器如 getrandom。注意即使已释放内存的隐私也很重要，虽然我们未来可能集成 zeroize 等缓解措施，但这些措施并不完整。注意 Rand 不防范进程 fork（Rand 0.8.x 及更早版本有有限缓解但并非完全保护）。最后，不可预测性的安全性可能以多种方式被破坏，从 Spectre 等复杂硬件缺陷到在日志中打印生成器状态等愚蠢错误。

额外特性

部分 PRNG 可能提供额外特性，例如：

支持多流，有助于并行任务。
能够在随机数流中跳转或定位；周期很大时，可作为流的替代方案。