如何简洁，便携，彻底种子的 mt19937 PRNG？

我似乎看到了很多答案，其中有人建议使用 <random>生成随机数，通常还有这样的代码:

std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, 5);
dis(gen);

通常情况下，这会取代某种“令人厌恶的东西”，比如:

srand(time(NULL));
rand()%6;

我们可以用旧的方法来证明 time(NULL)提供了低熵，time(NULL)是可预测的，并且最终的结果是非均匀的。

但是所有这些对于新的方式来说都是真实的: 它只是有一个更闪亮的表面。

  • 返回单个 unsigned int。它至少有16位，可能有32位。这还不足以播种机器翻译公司19937年的州。

  • 使用 std::mt19937 gen(rd());gen()(使用32位播种并查看第一个输出)不会给出一个很好的输出分布。7和13不可能是第一个输出。两粒种子产生0。12粒种子产生1226181350。(林克)

  • std::random_device可以(有时也是)实现为带有固定种子的简单 PRNG。因此，它可能在每次运行时产生相同的序列。(林克)这比 time(NULL)还要糟糕。

更糟糕的是，尽管前面的代码片段包含一些问题，但是复制和粘贴它们是非常容易的。一些解决这个问题的方案需要获得 很大 图书馆，这可能并不适合每个人。

有鉴于此，我的问题是 如何在 C + + 中简洁、可移植和彻底地播种 mt19937 PRNG？

鉴于上述问题，一个不错的答案是:

  • 必须完全播种 mt19937/mt19937 _ 64。
  • 不能仅仅依靠 std::random_device或 time(NULL)作为熵的来源。
  • 不应依赖 Boost 或其他库。
  • 应该适合在一个小数目的行，这样它会看起来很好的复制粘贴到一个答案。

想法

  • 我目前的想法是，std::random_device的输出可以与 time(NULL)、从 地址空间随机化地址空间随机化得到的值和一个硬编码常数(可以在分配过程中设置)混合(也许通过异或) ，以获得最佳效果。

  • std::random_device::entropy() 没有提供了一个很好的迹象，什么 std::random_device可能会或可能不会做。

19330 次浏览
小开

从某种意义上说，这是不可移植的。也就是说，我们可以设想一个运行 C + + 的有效的完全确定性平台(比如说，一个模拟器，它确定性地步骤机器时钟，并且具有“确定的”I/O) ，其中没有随机性来源为 PRNG 播种。

小开

我正在进行的实现利用 mt19937 PRNG 的 state_size特性来决定在初始化时提供多少种子:

using Generator = std::mt19937;


inline
auto const& random_data()
{
thread_local static std::array<typename Generator::result_type, Generator::state_size> data;
thread_local static std::random_device rd;


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


return data;
}


inline
Generator& random_generator()
{
auto const& data = random_data();


thread_local static std::seed_seq seeds(std::begin(data), std::end(data));
thread_local static Generator gen{seeds};


return gen;
}


template<typename Number>
Number random_number(Number from, Number to)
{
using Distribution = typename std::conditional
<
std::is_integral<Number>::value,
std::uniform_int_distribution<Number>,
std::uniform_real_distribution<Number>
>::type;


thread_local static Distribution dist;


return dist(random_generator(), typename Distribution::param_type{from, to});
}

我认为还有改进的空间，因为 std::random_device::result_type可以不同于 std::mt19937::result_type的大小和范围，所以应该真正考虑到。

关于 : Random _ device的说明。

根据 C++11(/14/17)标准:

26.5.6 Class Random _ device [ rand.device < strong > ]

如果实现限制阻止生成不确定的随机数，那么实现可以使用随机数引擎。

这意味着，如果由于某些限制而无法生成 不确定性值，则实现只能生成 确定性值。

众所周知，Windows上的 MinGW编译器不提供来自 std::random_device的 不确定性值，尽管它们可以从操作系统轻松获得。因此，我认为这是一个 bug，不太可能在实现和平台之间普遍出现。

小开

我认为 std::random_device最大的缺陷是，如果没有 CSPRNG 可用，它允许确定性后退。这本身就是不使用 std::random_device种子 PRNG 的一个很好的理由，因为产生的字节可能是确定性的。遗憾的是，它没有提供一个 API 来查明这种情况何时发生，或者请求故障而不是低质量的随机数。

也就是说，没有完全的 便携式的解决方案: 然而，有一个体面的，最小的方法。您可以使用 CSPRNG (定义为下面的 sysrandom)周围的最小包装器来为 PRNG 播种。

窗户

你可以依靠 CryptGenRandom，一个 CSPRNG。例如，你可以使用以下代码:

bool acquire_context(HCRYPTPROV *ctx)
{
if (!CryptAcquireContext(ctx, nullptr, nullptr, PROV_RSA_FULL, 0)) {
return CryptAcquireContext(ctx, nullptr, nullptr, PROV_RSA_FULL, CRYPT_NEWKEYSET);
}
return true;
}




size_t sysrandom(void* dst, size_t dstlen)
{
HCRYPTPROV ctx;
if (!acquire_context(&ctx)) {
throw std::runtime_error("Unable to initialize Win32 crypt library.");
}


BYTE* buffer = reinterpret_cast<BYTE*>(dst);
if(!CryptGenRandom(ctx, dstlen, buffer)) {
throw std::runtime_error("Unable to generate random bytes.");
}


if (!CryptReleaseContext(ctx, 0)) {
throw std::runtime_error("Unable to release Win32 crypt library.");
}


return dstlen;
}

像 Unix 一样

在许多类 Unix 系统上，应该尽可能使用 /dev/urandom(尽管不能保证在符合 POSIX 的系统上存在这种情况)。

size_t sysrandom(void* dst, size_t dstlen)
{
char* buffer = reinterpret_cast<char*>(dst);
std::ifstream stream("/dev/urandom", std::ios_base::binary | std::ios_base::in);
stream.read(buffer, dstlen);


return dstlen;
}

其他

如果没有 CSPRNG 可用，您可以选择依赖于 std::random_device。然而，如果可能的话，我会尽量避免这种情况，因为各种编译器(最显著的是 MinGW)将它作为 PRNG来实现(事实上，每次都生成相同的序列来提醒人们它不是正确的随机序列)。

播种

现在，我们已经有了开销最小的部分，我们可以生成所需的随机熵位来播种我们的 PRNG。该示例使用(明显不足的)32位作为 PRNG 的种子，您应该增加这个值(这取决于您的 CSPRNG)。

std::uint_least32_t seed;
sysrandom(&seed, sizeof(seed));
std::mt19937 gen(seed);

比较推进

在快速浏览了 源代码之后，我们可以看到提升: : Random _ device (一个真正的 CSPRNG)的相似之处。Boost 在 Windows 上使用 MS_DEF_PROV，这是 PROV_RSA_FULL的提供程序类型。唯一缺少的是验证加密上下文，这可以通过 CRYPT_VERIFYCONTEXT完成。在 * Nix 上，Boost 使用 /dev/urandom。IE，这个解决方案是可移植的、经过良好测试的、易于使用的。

Linux 专业化

如果您愿意为了安全性而牺牲简洁性，那么 getrandom在 Linux 3.17及以上版本以及最近的 Solaris 上是一个很好的选择。getrandom的行为与 /dev/urandom相同，只是如果内核在引导之后还没有初始化它的 CSPRNG，它就会阻塞。下面的代码片段检测 Linuxgetrandom是否可用，如果不可用，则返回到 /dev/urandom。

#if defined(__linux__) || defined(linux) || defined(__linux)
#   // Check the kernel version. `getrandom` is only Linux 3.17 and above.
#   include <linux/version.h>
#   if LINUX_VERSION_CODE >= KERNEL_VERSION(3,17,0)
#       define HAVE_GETRANDOM
#   endif
#endif


// also requires glibc 2.25 for the libc wrapper
#if defined(HAVE_GETRANDOM)
#   include <sys/syscall.h>
#   include <linux/random.h>


size_t sysrandom(void* dst, size_t dstlen)
{
int bytes = syscall(SYS_getrandom, dst, dstlen, 0);
if (bytes != dstlen) {
throw std::runtime_error("Unable to read N bytes from CSPRNG.");
}


return dstlen;
}


#elif defined(_WIN32)


// Windows sysrandom here.


#else


// POSIX sysrandom here.


#endif

OpenBSD

最后还有一个警告: 现代 OpenBSD 没有 /dev/urandom。您应该改用 得到熵。

#if defined(__OpenBSD__)
#   define HAVE_GETENTROPY
#endif


#if defined(HAVE_GETENTROPY)
#   include <unistd.h>


size_t sysrandom(void* dst, size_t dstlen)
{
int bytes = getentropy(dst, dstlen);
if (bytes != dstlen) {
throw std::runtime_error("Unable to read N bytes from CSPRNG.");
}


return dstlen;
}


#endif

其他想法

如果需要加密安全的随机字节，可能应该用 POSIX 的未缓冲的 open/read/close 替换 fstream。这是因为 basic_filebuf和 FILE都包含一个内部缓冲区，该缓冲区将通过标准分配器分配(因此不会从内存中删除)。

这可以很容易地通过将 sysrandom改为:

size_t sysrandom(void* dst, size_t dstlen)
{
int fd = open("/dev/urandom", O_RDONLY);
if (fd == -1) {
throw std::runtime_error("Unable to open /dev/urandom.");
}
if (read(fd, dst, dstlen) != dstlen) {
close(fd);
throw std::runtime_error("Unable to read N bytes from CSPRNG.");
}


close(fd);
return dstlen;
}

谢谢

特别感谢 Ben Voigt 指出 FILE使用缓冲读取，因此不应该使用。

我还要感谢 Peter Cordes 提到了 getrandom，以及 OpenBSD 缺少 /dev/urandom。

小开

一个给定的平台可能有一个熵源，例如 /dev/random。自 std::chrono::high_resolution_clock::now()时代以来的纳秒可能是标准图书馆中最好的种子。

我以前曾经使用过类似 (uint64_t)( time(NULL)*CLOCKS_PER_SEC + clock() )的东西来为那些不是安全关键的应用程序获得更多的熵。

小开

下面是我自己对这个问题的看法:

#include <random>
#include <chrono>
#include <cstdint>
#include <algorithm>
#include <functional>
#include <iostream>


uint32_t LilEntropy(){
//Gather many potential forms of entropy and XOR them
const  uint32_t my_seed = 1273498732; //Change during distribution
static uint32_t i = 0;
static std::random_device rd;
const auto hrclock = std::chrono::high_resolution_clock::now().time_since_epoch().count();
const auto sclock  = std::chrono::system_clock::now().time_since_epoch().count();
auto *heap         = malloc(1);
const auto mash = my_seed + rd() + hrclock + sclock + (i++) +
reinterpret_cast<intptr_t>(heap)    + reinterpret_cast<intptr_t>(&hrclock) +
reinterpret_cast<intptr_t>(&i)      + reinterpret_cast<intptr_t>(&malloc)  +
reinterpret_cast<intptr_t>(&LilEntropy);
free(heap);
return mash;
}


//Fully seed the mt19937 engine using as much entropy as we can get our
//hands on
void SeedGenerator(std::mt19937 &mt){
std::uint_least32_t seed_data[std::mt19937::state_size];
std::generate_n(seed_data, std::mt19937::state_size, std::ref(LilEntropy));
std::seed_seq q(std::begin(seed_data), std::end(seed_data));
mt.seed(q);
}


int main(){
std::mt19937 mt;
SeedGenerator(mt);


for(int i=0;i<100;i++)
std::cout<<mt()<<std::endl;
}

这里的想法是使用异或结合许多潜在的熵源(快速时间、慢速时间、 std::random-device、静态变量位置、堆位置、函数位置、库位置、程序特定值)来尽最大努力初始化 mt19937。只要源至少一次是“好的”，结果就至少是“好的”。

这个答案并不像想象的那么简短，可能包含一个或多个逻辑错误。所以我认为这是一项正在进行的工作。请评论，如果你有反馈。

小开

你可以使用 std::seed_seq并使用 Alexander Huszagh 得到熵的方法将其填充到至少要求的状态大小:

size_t sysrandom(void* dst, size_t dstlen); //from Alexander Huszagh answer above


void foo(){


std::array<std::mt19937::UIntType, std::mt19937::state_size> state;
sysrandom(state.begin(), state.length*sizeof(std::mt19937::UIntType));
std::seed_seq s(state.begin(), state.end());


std::mt19937 g;
g.seed(s);
}

如果有一个正确的方法来填充或创建一个 种子序列从一个 统一随机位生成器在标准库使用 std::random_device正确的种子将更加简单。

小开

使用时间进行种子化并没有什么错，假设您不需要它来保证安全(而且您也没有说这是必要的)。其中的见解是，您可以使用散列来修复非随机性。我发现这种方法在所有情况下都能很好地工作，包括并且特别适用于重型蒙特卡罗模拟。

这种方法的一个很好的特性是，它可以从其他非真正随机的种子集推广到初始化。例如，如果希望每个线程拥有自己的 RNG (为了线程安全) ，只需基于散列线程 ID 进行初始化。

下面是从 我的代码库中提取的 SSCCE(为简单起见，省略了一些 OO 支持结构) :

#include <cstdint> //`uint32_t`
#include <functional> //`std::hash`
#include <random> //`std::mt19937`
#include <iostream> //`std::cout`


static std::mt19937 rng;


static void seed(uint32_t seed) {
rng.seed(static_cast<std::mt19937::result_type>(seed));
}
static void seed() {
uint32_t t = static_cast<uint32_t>( time(nullptr) );
std::hash<uint32_t> hasher; size_t hashed=hasher(t);
seed( static_cast<uint32_t>(hashed) );
}


int main(int /*argc*/, char* /*argv*/[]) {
seed();
std::uniform_int_distribution<> dis(0, 5);
std::cout << dis(rng);
}
小开
  • 使用 get熵()来播种一个伪随机数生成器(PRNG)。
  • 如果需要随机值(而不是 /dev/urandom或 /dev/random) ，请使用 getrandom ()。

这些在现代的类 UNIX 系统上可用，如 Linux、 Solaris 和 OpenBSD。

小开

这里已经有很多好的答案，但我想补充两点:

  • MinGW 错误，这里引用的确定性 std::random_device实现的最著名的例子，在最近的版本(链接到错误报告)中得到了修复。

  • 在 c + + 20中，有一种方法可以不使用缓冲区数组就用来自 std::random_device的值填充 std::seed_seq:

#include <random>
#include <ranges>


int main(){


std::random_device rd;
auto rd_range = std::ranges::transform_view(std::ranges::iota_view(static_cast<std::size_t>(0), std::mt19937::state_size), [&rd](size_t){return rd();});
std::seed_seq seeds(rd_range.begin(), rd_range.end());
std::mt19937 gen(seeds);


return 0;


}

提交答案