C++ 中 random_device 的更好替代品？

Question

我一直在使用random_device rd{}为 Mersenne-Twister 伪随机数生成器生成种子，mt19937 RNG{rd()} 正如此处所建议的那样。然而，文档中写道（文档示例代码中的注释），“random_device一旦熵池耗尽，许多实现的性能都会急剧下降。在实际使用中，random_device通常仅用于播种 PRNG，例如mt19937”。我尝试测试这个“熵池”有多大，对于 10^6 次调用，random_device返回超过 10^2 个重复数字（请参阅下面的示例代码和输出）。换句话说，如果我尝试将random_device其用作 Mersenne-Twister PRNG 的种子，它将生成大量重复种子。

问题：人们是否仍在使用random_deviceC++ 来生成 PRNG 种子，或者是否已经有更好的替代方案？

我的代码：

#include <iostream>
#include <random>
#include <chrono>

using namespace std;

int main(){
    
    auto begin = std::chrono::high_resolution_clock::now();
    
    random_device rd{};
    mt19937 RNG{ rd() };

    int total_n_of_calls = 1e6;
    vector<int> seeds;
    
    for(auto call = 0; call < total_n_of_calls; call++){
    int call_rd = rd();
    seeds.push_back(call_rd);
    }
    
    int count_repeats = 0;
    sort(seeds.begin(), seeds.end());
    for(int i = 0; i < seeds.size() - 1; i++) {
        if (seeds[i] == seeds[i + 1]) {
            count_repeats++;
    }
    }
    
    printf("Number of times random_device have been called: %i\n", total_n_of_calls);
    printf("Number of repeats: %i\n", count_repeats);

    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    printf("Duration: %.3f seconds.\n", elapsed.count() * 1e-9);

    return 0;
}

输出：

random_device 被调用的次数：1000000
重复次数：111
持续时间：0.594 秒。

Answer 1

TL;DR：不，没有什么比这更好的了。你只需要停止滥用它。

\n\n

要点random_device是，它向您的平台请求实际上是随机的位，而不仅仅是来自某些确定性种子的伪随机位。

\n

如果平台/操作系统认为它所拥有的熵已被消耗，那么它就无法为您提供此服务。但老实说，它使用真正的随机源（从 CPU 中的实际随机性硬件到磁盘访问时间）来修改 PRNG 的内部状态。对于外部人员来说，这就是 \xe2\x80\x93 的全部内容，你得到的位仍然是不可预测的。

\n

所以，答案是这样的：

\n

\n
• 你使用是random_device因为你实际上需要随机种子。没有随机性的算法捷径\xe2\x80\x93“算法”这个词已经表明它是确定性的。一般来说，软件是确定性的，除非它从外部获取随机数据。因此，您所能做的就是询问操作系统，它实际上会处理系统中存在的任何随机源。这已经是事实了random_device。
\n
• 所以，不，除了实际的外部熵之外，您不能使用其他东西，这正是您最有效地获得的东西random_device（除非您购买昂贵的专用随机生成器卡并为其编写驱动程序）。
\n
• 由于操作系统使用随机外部源来更改 PRNG 的内部状态，因此它可以安全地产生比随机事件发生更多的随机事件 \xe2\x80\x93 但它需要跟踪从 PRNG 中取出了多少位，因此攻击者永远不可能以高概率正确地重建先前状态。因此，当没有足够的外部随机性来修改内部状态时，它会减慢随机性的消耗。
\n
• 因此，在短时间内生成种子的 10\xe2\x81\xb6 调用听起来像是你做错了什么；如果这些用于提供梅森扭曲器，则需要两倍的时间，梅森扭曲器是一种过于复杂和缓慢的算法，但在加密上并不安全。你从来没有使用过这么多实际的随机性！不要重新播种，继续使用已播种的 PRNG，除非您需要这些种子是独立的加密安全性。
\n

\n

事情正是如此：如果您需要在几秒钟之内生成 10\xe2\x81\xb6 个独立的加密安全密钥，那么您就有点特殊了。您是否正在为 CDN 工作，其中单个操作系统每秒可以服务数百万个新的 TLS 连接？如果没有，请将您的使用量减少random_device到实际有用的程度。

\n

如果您想更多地了解真正的随机性在程序中的最终结果，我建议您阅读此答案。简而言之，如果您实际上每秒需要比默认random_device提供更多的随机字节，请尝试使用 ctor 参数来构造它"/dev/urandom"。对于您提出这个问题的上下文中的含义的任何假​​定定义，它仍然是安全的（这意味着我假设您没有为密钥生成的极高吞吐量编写加密库） ）。

\n