如何简洁，可移植和彻底播种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;

我们可能会争论批评旧方法. c1>提供低熵，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)还要糟糕.

更糟糕的是，尽管它们包含了问题，但是复制和粘贴上述代码片段非常容易.为此，一些解决方案需要获取轻巧 图书馆可能并不适合所有人.

鉴于此，我的问题是如何能以C ++简洁，可移植，彻底地播种mt19937 PRNG?

鉴于上述问题，这是一个很好的答案:

• 必须完全植入mt19937/mt19937_64.
• 不能仅仅依靠std::random_device或time(NULL)作为熵的来源.
• 不应依赖Boost或其他库.
• 应该以少量的行显示，这样可以很好地复制粘贴到答案中.

想法

• 我目前的想法是，可以使用time(NULL)(来自地址空间随机化，以及一个硬编码的常量(可以在分发过程中设置)，以尽力而为地获取熵.

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

我会认为std::random_device的最大缺陷是，如果没有CSPRNG可用，则允许确定性回退.仅此一个很好的理由就是不要使用std::random_device播种PRNG，因为产生的字节可能是确定性的.不幸的是，它没有提供API来找出发生这种情况的时间，也没有提供请求失败的API，而不是低质量的随机数.

也就是说，没有完全便携式解决方案:但是，有一种不错的，最小的方法.您可以在CSPRNG(在下面定义为sysrandom)周围使用最小包装，以植入PRNG.

Windows

---

您可以依靠CSPRNG CryptGenRandom.例如，您可以使用以下代码:

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.该示例使用(显然不足)32位来播种PRNG，因此您应该增加该值(取决于CSPRNG).

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

增强对比

---

在快速查看源代码. 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

其他想法

---

如果需要加密安全的随机字节，则可能应将fstream替换为POSIX的无缓冲打开/读取/关闭.这是因为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.

I seem to see many answers in which someone suggests using <random> to generate random numbers, usually along with code like this:

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

Usually this replaces some kind of "unholy abomination" such as:

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

We might criticize the old way by arguing that time(NULL) provides low entropy, time(NULL) is predictable, and the end result is non-uniform.

But all of that is true of the new way: it just has a shinier veneer.

• rd() returns a single unsigned int. This has at least 16 bits and probably 32. That's not enough to seed MT's 19937 bits of state.

• Using std::mt19937 gen(rd());gen() (seeding with 32 bits and looking at the first output) doesn't give a good output distribution. 7 and 13 can never be the first output. Two seeds produce 0. Twelve seeds produce 1226181350. (Link)

• std::random_device can be, and sometimes is, implemented as a simple PRNG with a fixed seed. It might therefore produce the same sequence on every run. (Link) This is even worse than time(NULL).

Worse yet, it is very easy to copy and paste the foregoing code snippets, despite the problems they contain. Some solutions to the this require acquiring largish libraries which may not be suitable to everyone.

In light of this, my question is How can one succinctly, portably, and thoroughly seed the mt19937 PRNG in C++?

Given the issues above, a good answer:

• Must fully seed the mt19937/mt19937_64.
• Cannot rely solely on std::random_device or time(NULL) as a source of entropy.
• Should not rely on Boost or other libaries.
• Should fit in a small number of lines such that it would look nice copy-pasted into an answer.

Thoughts

• My current thought is that outputs from std::random_device can be mashed up (perhaps via XOR) with time(NULL), values derived from address space randomization, and a hard-coded constant (which could be set during distribution) to get a best-effort shot at entropy.

• std::random_device::entropy() does not give a good indication of what std::random_device might or might not do.

解决方案

I would argue the greatest flaw with std::random_device is the that it is allowed a deterministic fallback if no CSPRNG is available. This alone is a good reason not to seed a PRNG using std::random_device, since the bytes produced may be deterministic. It unfortunately doesn't provide an API to find out when this happens, or to request failure instead of low-quality random numbers.

That is, there is no completely portable solution: however, there is a decent, minimal approach. You can use a minimal wrapper around a CSPRNG (defined as sysrandom below) to seed the PRNG.

Windows

---

You can rely on CryptGenRandom, a CSPRNG. For example, you may use the following code:

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-Like

---

On many Unix-like systems, you should use /dev/urandom when possible (although this is not guaranteed to exist on POSIX-compliant systems).

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;
}

Other

---

If no CSPRNG is available, you might choose to rely on std::random_device. However, I would avoid this if possible, since various compilers (most notably, MinGW) implement it with as a PRNG (in fact, producing the same sequence every time to alert humans that it's not properly random).

Seeding

---

Now that we have our pieces with minimal overhead, we can generate the desired bits of random entropy to seed our PRNG. The example uses (an obviously insufficient) 32-bits to seed the PRNG, and you should increase this value (which is dependent on your CSPRNG).

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

Comparison To Boost

---

We can see parallels to boost::random_device (a true CSPRNG) after a quick look at the source code. Boost uses MS_DEF_PROV on Windows, which is the provider type for PROV_RSA_FULL. The only thing missing would be verifying the cryptographic context, which can be done with CRYPT_VERIFYCONTEXT. On *Nix, Boost uses /dev/urandom. IE, this solution is portable, well-tested, and easy-to-use.

Linux Specialization

---

If you're willing to sacrifice succinctness for security, getrandom is an excellent choice on Linux 3.17 and above, and on recent Solaris. getrandom behaves identically to /dev/urandom, except it blocks if the kernel hasn't initialized its CSPRNG yet after booting. The following snippet detects if Linux getrandom is available, and if not falls back to /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

---

There is one final caveat: modern OpenBSD does not have /dev/urandom. You should use getentropy instead.

#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

Other Thoughts

---

If you need cryptographically secure random bytes, you should probably replace the fstream with POSIX's unbuffered open/read/close. This is because both basic_filebuf and FILE contain an internal buffer, which will be allocated via a standard allocator (and therefore not wiped from memory).

This could easily be done by changing sysrandom to:

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;
}

Thanks

---

Special thanks to Ben Voigt for pointing out FILE uses buffered reads, and therefore should not be used.

I would also like to thank Peter Cordes for mentioning getrandom, and OpenBSD's lack of /dev/urandom.

这篇关于如何简洁，可移植和彻底播种mt19937 PRNG?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！