問題描述

我似乎看到很多答案中有人建議使用 來生成隨機數，通常還有這樣的代碼:

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;

我們可能會批評舊方法，認為time(NULL) 提供低熵，time(NULL) 是可預測的，最終結果是非均勻的.

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() 返回單個 unsigned int.這至少有 16 位，可能有 32 位.這不足以為 MT 的 19937 位狀態播種.

• 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.

使用 std::mt19937 gen(rd());gen()(用 32 位播種并查看第一個輸出)不能提供良好的輸出分布.7 和 13 永遠不能是第一個輸出.兩顆種子產生 0.十二顆種子產生 1226181350.(鏈接)

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 可以，有時是，作為一個帶有固定種子的簡單 PRNG 來實現.因此，它可能會在每次運行時產生相同的序列.(鏈接) 這比time(NULL)還要糟糕.

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.

有鑒于此，我的問題是如何在 C++ 中簡潔、可移植和徹底地植入 mt19937 PRNG?

鑒于上述問題，一個很好的答案:

Given the issues above, a good answer:

• 必須完全播種 mt19937/mt19937_64.
• 不能僅僅依賴 std::random_device 或 time(NULL) 作為熵的來源.
• 不應依賴 Boost 或其他庫.
• 應該適合少量的行，以便復制粘貼到答案中看起來不錯.

• 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.

想法

• 我目前的想法是 std::random_device 的輸出可以與 time(NULL) 混合(可能通過 XOR)，值來自 地址空間隨機化，以及一個硬編碼常量(可以在分發過程中設置)以獲得最佳效果- 對熵的努力.

• 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() 沒有很好地說明std::random_device可能會或不會做什么.

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

推薦答案

我認為 std::random_device 的最大缺陷是，如果沒有可用的 CSPRNG，它允許確定性回退.僅此一項就是不使用 std::random_device 播種 PRNG 的一個很好的理由，因為產生的字節可能是確定性的.不幸的是，它沒有提供 API 來確定何時發生這種情況，或者請求失敗而不是低質量的隨機數.

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.

也就是說，沒有完全便攜的解決方案:但是，有一種體面的、最小的方法.您可以使用 CSPRNG 周圍的最小包裝器(在下面定義為 sysrandom)來為 PRNG 設定種子.

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.

您可以依賴 CryptGenRandom，一個 CSPRNG.例如，您可以使用以下代碼:

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

在許多類 Unix 系統上，您應該使用 /dev/urandom可能(盡管不保證在符合 POSIX 的系統上存在).

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

其他

如果沒有可用的 CSPRNG，您可以選擇依賴 std::random_device.但是，如果可能的話，我會避免這種情況，因為各種編譯器(最著名的是 MinGW)將其作為 PRNG(實際上，每次生成相同的序列以提醒人們它不是正確隨機的).

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).

現在我們的片段開銷最小，我們可以生成所需的隨機熵位來為我們的 PRNG 做種子.該示例使用(顯然不夠)32 位作為 PRNG 的種子，您應該增加此值(這取決于您的 CSPRNG).

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

對比提升

快速瀏覽源代碼.Boost 在 Windows 上使用 MS_DEF_PROV，這是 PROV_RSA_FULL 的提供程序類型.唯一缺少的是驗證加密上下文，這可以通過 CRYPT_VERIFYCONTEXT 完成.在 *Nix 上，Boost 使用 /dev/urandom.IE，此解決方案可移植、經過充分測試且易于使用.

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.

如果你愿意為了安全而犧牲簡潔性，getrandom 是 Linux 3.17 及更高版本以及最近的 Solaris 上的絕佳選擇.getrandom 的行為與 /dev/urandom 相同，除了它在啟動后內核尚未初始化其 CSPRNG 時會阻塞.以下代碼段檢測 Linux getrandom 是否可用，如果不可用，則回退到 /dev/urandom.

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

最后一個警告:現代 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 都包含一個內部緩沖區，它將通過標準分配器分配(因此不會從內存中擦除).

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).

這可以很容易地通過將 sysrandom 更改為:

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

謝謝

特別感謝 Ben Voigt 指出 FILE 使用緩沖讀取，因此不應使用.

Thanks

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

我還要感謝 Peter Cordes 提到 getrandom，以及 OpenBSD 缺少 /dev/urandom.

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

這篇關于如何簡潔、便攜、徹底地播種 mt19937 PRNG?的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！