C++ | 如何安全地初始化 std::mt19937

背景

在看到 C++ Seeding Surprises ᴮᵃᶜᵏᵘᵖ 这篇文章之前，我一直使用如下代码初始化 std::mt19937：

std::mt19937 mtr(std::random_device{}());

问题

std::random_device 可能根本不是随机的

旧版 MinGW 中的 GCC 将其实现为确定性的，参见 std::random_device not working properly ᴮᵃᶜᵏᵘᵖ，这一问题已在 MinGW GCC 9.2 中修复。

std::random_device 的值域不够大

std::random_device 的值域同 unsigned int，在我的环境中为 [0,2^{32}-1]，提供了 32 位的随机性。

然而，2^{32} 并不是一个很大的数字。我们进行了一组测试 ᴮᵃᶜᵏᵘᵖ，在 1.75 秒内遍历了 10^6 个数据，因此预计可以在 2.09 小时内遍历完 2^{32} 种情况。

众所周知，只要知道种子，就可以预测整个随机序列。因此，对于需要高安全性的用例来说，32 位的种子远远不够。

需要高安全性的用例应当使用密码学安全伪随机数生成器 ᴮᵃᶜᵏᵘᵖ。

std::seed_seq 的实现不靠谱

上面的代码中，我们只给 std::mt19937 提供了一个 32 位整数，但是 Mersenne Twister 的状态包含 624 个 32 位整数（参见维基百科 ᴮᵃᶜᵏᵘᵖ），因此标准库会使用 std::seed_seq 来扩充状态。

然而 std::seed_seq 的实现有问题。

在使用 32 位整数进行播种时，包括 7 和 13 在内的大约 \frac{2^{32}}e 个数永远不可能作为 std::mt19937 生成的第一个数。如果你运行如下代码，函数 send_detailed_tracking_info_secretly 永远不会被调用。

std::mt19937 mtr(std::random_device{}());
if (mtr() == 7) /* lucky seven! you get to send in a report */
{
    send_detailed_tracking_info_secretly();
}

修复

可以参考 Stack Overflow 上的这个回答 ᴮᵃᶜᵏᵘᵖ 进行简单修复：

using Generator = std::mt19937;

Generator mtr = ([]() {
    static std::array<Generator::result_type, Generator::state_size> data;
    static std::random_device rd;

    std::generate(std::begin(data), std::end(data), std::ref(rd));

    static std::seed_seq seq(std::begin(data), std::end(data));
    static Generator mtr{seq};

    return mtr;
})();

以下代码直接从 /dev/urandom 读取随机数：

using Generator = std::mt19937_64;

Generator mtr = ([]() -> Generator {
    using iv_type = Generator::result_type;
    constexpr size_t iv_length = Generator::state_size;
    constexpr size_t iv_size = sizeof(iv_type) * iv_length;

    iv_type *iv = (iv_type *)std::malloc(iv_size);

    std::FILE *fin = std::fopen("/dev/urandom", "rb");
    [[maybe_unused]] size_t unused = std::fread(iv, 1, iv_size, fin);
    std::fclose(fin);

    std::seed_seq seq = std::seed_seq(iv, iv + iv_length);
    std::free(iv);
    return Generator{seq};
})();

关于熵的来源

在 Linux 上可以通过读取 /dev/urandom 获得良好的随机性，在 Windows 上则可以使用 BCryptGenRandom ᴮᵃᶜᵏᵘᵖ。

关于熵的大小

为了初始化 std::seed_seq，我从 /dev/urandom 中读取了 2496B 的数据。

增强

由于 std::seed_seq 和 /dev/urandom 在我的应用场景中工作良好，我选择使用它们。

如果你对 std::seed_seq 不满意，可以参考 Developing a seed_seq Alternative ᴮᵃᶜᵏᵘᵖ。

关于 std::random_device 的问题，可以参考 Everything You Never Wanted to Know about C++'s random_device ᴮᵃᶜᵏᵘᵖ。

如果你想自行实现一个 random_device，可以参考 Simple Portable C++ Seed Entropy ᴮᵃᶜᵏᵘᵖ。

图片来源 ᴮᵃᶜᵏᵘᵖ