如何简洁，便携地彻底播种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)是可预测的以及最终结果不均匀来批评旧的方法。

但所有这一切都适用于新的方式：它只是有一个更光滑的单板。

  • rd()返回一个unsigned int 。 这至少有16位，可能是32.这不足以种子MT的19937位状态。

  • 使用std::mt19937 gen(rd());gen() （使用32位播种并查看第一个输出）不能提供良好的输出分布。 7和13永远不会是第一个输出。 两颗种子产生0.十二颗种子产生1226181350.（链接）

  • std::random_device可以是，有时是作为一个简单的PRNG与一个固定的种子实现的。 因此它可能会在每次运行中产生相同的序列。 （链接）这比time(NULL)更差time(NULL) 。

    • 更糟糕的是，尽管存在问题，但复制和粘贴上述代码片段非常容易。 有些解决方案需要获取可能不适合每个人的大型图书馆。

    鉴于此，我的问题是如何简洁，便携地将C ++中的mt19937 PRNG彻底播种？

    鉴于上述问题，一个很好的答案：

  • 必须完全播种mt19937 / mt19937_64。
  • 不能单纯依靠std::random_device或time(NULL)作为熵源。
  • 不应该依赖Boost或其他库文库。
  • 应适合少量的行，以便它看起来很好复制粘贴到答案。

    • 思考

  • 我目前的想法是std::random_device输出可以通过time(NULL) ，从地址空间随机化得到的值和一个硬编码常量（可以在发布期间设置）来混合（也许通过XOR）尽力而为地拍摄熵。

  • std::random_device::entropy()并不能很好地说明std::random_device可能做什么或不可能做什么。

    • 我认为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);

    比较提升

    在快速查看源代码后，我们可以看到boost :: random_device（一个真正的CSPRNG）的相似之处。 Windows上的Boost使用MS_DEF_PROV ，这是PROV_RSA_FULL的提供程序类型。 唯一缺少的是验证密码上下文，这可以通过CRYPT_VERIFYCONTEXT来完成。 在* Nix上，Boost使用/dev/urandom 。 IE，这种解决方案是便携式的，经过了充分测试并且易于使用。

    Linux专业化

    如果您愿意为了安全而牺牲简洁性， getrandom是Linux 3.17及更高版本和最近Solaris上的绝佳选择。 getrandom行为与/dev/urandom行为相同，除非它在引导后内核尚未初始化其CSPRNG时阻塞。 以下片段检测Linux getrandom是否可用，以及是否回退到/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 。 您应该使用getentropy。 

    #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的无缓冲打开/读/关来代替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 。

    从某种意义上说，这不可能轻易完成。 也就是说，人们可以设想一个运行C ++的有效的完全确定性的平台（比如，一个模拟器，它可以确定性地对机器时钟进行步进，并且具有“确定的”I / O），其中没有任何随机性来产生PRNG。

    您可以使用std::seed_seq并使用Alexander Huszagh的获取熵的方法将其填充到生成器的至少需要状态大小： 

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

void foo(){

    std::uint_fast32_t[std::mt19937::state_size] state;
    sysrandom(state, sizeof(state));
    std::seed_seq s(std::begin(state), std::end(state));

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

    如果在标准库中使用std::random_device进行正确种植的UniformRandomBitGenerator填充或创建std::random_device的正确方法会更简单。

    链接地址: http://www.djcxy.com/p/37279.html

    上一篇: How to succinctly, portably, and thoroughly seed the mt19937 PRNG?

    下一篇: duplicate random values from a very large range