如何简洁、便携和彻底地播种 mt19937 PRNG？

Question

我似乎看到很多答案，其中有人建议使用 <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) 还要糟糕。

更糟糕的是，复制和粘贴上述代码片段非常容易，尽管它们包含问题。对此的一些解决方案需要获取可能不适合所有人的 大型 库。

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

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

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

想法

• 我目前的想法是，来自 std::random_device 的输出可以与 time(NULL) 、来自 地址空间随机化 的值和硬编码常量（可以设置在分发过程中）以获得最大努力的熵。

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

原文由 Richard 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

我认为 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）的相似之处。 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 。

原文由 Alex Huszagh 发布，翻译遵循 CC BY-SA 3.0 许可协议