第26.17章:随机与熵

English

1. 两个不同的问题

“随机”覆盖两个互不相关的要求。模拟需要可复现、统计性质好的序列; 密码、密钥或 token 需要即使攻击者知道程序也无法预测。fast_io 把两者分开: white-hole 家族读取操作系统熵源;`std::mt19937_64` 是用于复现的带种子 PRNG。

需求 使用 可预测?
可复现模拟 带种子的 PRNG,例如 std::mt19937_64 是,设计如此。
密钥、token、盐 ibuf_white_hole_engine 或直接使用 OS 熵源 否。
洗游戏牌堆 带种子的 PRNG 种子已知时可预测。
洗安全敏感的列表 熵引擎 否。

2. White-hole 家族

“white hole”发射随机字节,不吸收它们。原生类型读取平台熵源; 带缓冲类型批量读取,并在销毁时擦除缓冲区。

名字 角色 模块
native_white_hole 不带缓冲的原始熵源。 fast_io
ibuf_white_hole 带缓冲、带安全擦除的熵源。 头文件侧
native_white_hole_engine 基于原生源的 Uniform random bit generator。 头文件侧
ibuf_white_hole_engine 基于带缓冲源的 Uniform random bit generator。 头文件侧

::fast_io::ibuf_white_hole_engine eng;
::std::uniform_int_distribution<::std::uint32_t> dist{1, 100};
auto const value{dist(eng)};

引擎满足 C++ UniformRandomBitGenerator 要求,所以能和 <random> 里的分布一起用。每个引擎实例拥有自己的源和缓冲区; 不要在多个线程之间无同步地共享一个引擎。

3. 熵报告

basic_white_hole_engine::entropy() 在源提供熵估计时返回平台值, 并夹到结果宽度。没有熵方法的源返回 0.0。 不要把这个值当作安全证明;它是 OS 的提示。

引擎的 min() 是 0,max() 是 result_type 的最大值。operator() 读取一个结果所需的字节并返回。 POSIX 上源是 getrandom 或 /dev/urandom; Windows 上是 RtlGenRandom/BCryptGenRandom 或平台等价物; WASI 上是 random_get。

4. 可复现 PRNG

模拟、测试和程序化内容用 <random> 里的带种子引擎。 种子是实验的一部分:记录下来并重放。


::std::mt19937_64 eng{0x123456789abcdef0ULL};
::std::uniform_real_distribution<double> dist{0.0, 1.0};
double const sample{dist(eng)};

默认构造的引擎使用固定种子,所以每次运行产生同一序列。 这对测试有用,对任何安全敏感的东西都是错的。 想要随机种子,先从熵源读种子,再 seed PRNG。

5. 分布与偏差

不要用取模把引擎值压到范围:


// wrong: biased toward the low end
auto bad{eng() % 100u};

// right: the distribution removes the bias
::std::uniform_int_distribution<::std::uint32_t> dist{0, 99};
auto good{dist(eng)};

标准分布是处理范围、伯努利试验、正态样本和洗牌的正确层。 它们按分布的契约消费引擎原始比特,而不是按手写取模。

6. random_generate

random_generate(distribution, engine) 是一个小包装: 调用分布,并把跨边界的遗留异常转回 herbception 通道。 它在头文件侧,适合分布实现会抛出的情况。


auto value{::fast_io::random_generate(dist, eng)};

7. 模块与头文件边界

fast_io 模块导出 native_white_hole。 带缓冲源、引擎和 random_generate 目前在头文件侧。 分布本身来自 <random>,不是 fast_io 类型。

不要用 PRNG 生成秘密。 带种子的 Mersenne Twister 是可复现的, 这正好和密钥/token 的需求相反。用熵引擎,并且永远不要记录或复用它产生的字节。

要点