c – 如何简洁,便携,彻底地播种mt19937 PRNG？

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

通常这会取代某种“邪恶的憎恶”,例如：

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

通过争论时间(NULL)提供低熵,时间(NULL)是可预测的,并且最终结果是不均匀的,我们可能是criticize旧方法.

但所有这一切都适用于新的方式：它只有一个更光亮的贴面.

> rd()返回一个unsigned int.这至少有16位,可能是32位.这还不足以为MT的19937位状态提供种子.
>使用std :: mt19937 gen(rd()); gen()(以32位播种并查看第一个输出)不能提供良好的输出分布. 7和13永远不会是第一个输出.两粒种子产生0.十二粒种子产生1226181350.(Link)
> std :: random_device可以(有时是)实现为具有固定种子的简单PRNG.因此,它可能在每次运行时产生相同的序列. (Link)这比时间更糟(NULL).

更糟糕的是,尽管存在它们包含的问题,但复制和粘贴上述代码片段非常容易.对此的一些解决方案需要获取largish libraries,这可能并不适合所有人.

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

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

>必须完全播种mt19937 / mt19937_64.
>不能仅仅依赖于std :: random_device或time(NULL)作为熵源.
>不应该依赖Boost或其他图书馆.
>应该适合少量的线条,以便将其复制粘贴到答案中.

思考

>我目前的想法是std :: random_device的输出可以与时间(NULL)混合(可能通过XOR),从address space randomization派生的值和硬编码常量(可以在分发期间设置)以获得最佳效果 – 熵射击.
> std :: random_device :: entropy()does not很好地指示了std :: random_device可能会或可能不会执行的操作.

也就是说,没有完全可移植的解决方案：但是,有一种体面的,最小的方法.您可以在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);

提升比较

在快速查看source code之后,我们可以看到boost :: 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时阻塞.以下代码段检测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.